Archive: Functional programming
Thursday 4 October 2012 20:47
In Shed, we sometimes define functions that usually delegate to a method,
but also have some special cases or defaults if that method isn't implemented.
For instance, the function represent should produce a string
representation of an object. If the argument implements the method
represent, it calls that method. Otherwise, it uses the name
of the class of the object to generate the string. In code:
def represent fun(value: any) =>
if isInstance(value, Representable) then
value.represent()
else
defaultRepresent(value)
A problem arises when we want to call the function represent from
within an implementation of the represent method. For instance,
if we were implementing represent for the Some class:
def Some class(value: any) => {
// Skipping the rest of the implementation of Some for brevity
def represent fun() =>
"Some(" + represent(value) + ")"
}
This code won't compile since we're calling represent with a
single argument, value, but within the scope of the class,
represent refers to the zero-argument function that implements
represent specifically for Some.
There are several possible solutions to this problem, but the simplest one
seems to be to use a different name for the method than for the corresponding
function. For consistency, we can introduce the convention that the method name should be a simple variation on the
function name. For instance, we might choose to use a leading underscore:
def represent fun(value: any) =>
if isInstance(value, Representable) then
value._represent()
else
defaultRepresent(value)
Although the leading underscore is perhaps a little ugly, that ugliness does
help to reinforce the idea that you shouldn't be calling
the method _represent directly. Instead, you should be using
the represent method. More generally, instead of calling a method
_foo, you should be calling foo (unless you're
actually implementing foo).
Topics: Functional programming, Language design, Shed
Sunday 9 September 2012 20:47
Note: this post assumes you already have some familiarity with
applicative functors
In this post, I'll show how to implement applicative functors in JavaScript,
specifically for options, and then show an alternative formulation that's
arguably better suited to languages that generally have uncurried functions
(that is, languages that tend to have functions that accept multiple arguments
rather than a single argument).
First of all, let's implement the option type (otherwise known as the maybe
type) in JavaScript as a functor:
var none = {
map: function(func) {
return none;
},
bind: function(func) {
return none;
},
toString: function() {
return "none";
}
};
function some(value) {
return {
map: function(func) {
return some(func(value));
},
bind: function(func) {
return func(value);
},
toString: function() {
return "some(" + value + ")";
}
};
}
var functor = {
map: function(func, option) {
return option.map(func)
},
unit: some,
applyFunctor: function(funcOption, argOption) {
return funcOption.bind(function(func) {
return argOption.map(func);
});
}
};
We can then use option values as applicative functors. Let's try our
implementation out to make sure it behaves as we expect:
var four = some(4);
var six = some(6);
function add(first, second) {
return first + second;
};
function curry(func, numberOfArguments) {
return function(value) {
if (numberOfArguments === 1) {
return func(value);
} else {
return curry(func.bind(null, value), numberOfArguments - 1);
}
};
}
functor.applyFunctor(functor.map(curry(add, 2), four), six);
// => some(10)
functor.applyFunctor(functor.map(curry(add, 2), none), six);
// => none
functor.applyFunctor(functor.map(curry(add, 2), four), none);
// => none
Note that the use of the functor required us to curry the add
function. This isn't a problem in functional languages such as Haskell, since
functions tend to be curried by default. However, in languages that usually
define functions to have multiple arguments (uncurried languages, for short), such as JavaScript, things
get a little untidy.
My understanding of applicative functors is that they allow functors, or
rather map, to be generalised to functions that accept more than
one argument, such as add. Therefore, in an uncurried language,
we might imagine the following cleaner API:
functor.applyFunctorUncurried(add, four, six);
// => some(10)
functor.applyFunctorUncurried(add, none, six);
// => none
functor.applyFunctorUncurried(add, four, none);
// => none
And such an API turns out to be not too hard to implement:
functor.applyFunctorUncurried = function(func) {
var args = Array.prototype.slice.call(arguments, 1);
return args.reduce(
functor.applyFunctor,
functor.unit(curry(func, args.length))
);
}
Interestingly, the implementation of applyFunctorUncurried is most
easily expressed in terms of the original applyFunctor. I've found
cases like this explain why functional languages tend to favour curried
functions: it often makes the implementation of higher-order functions
such as applyFunctor much more straightforward.
This raises an interesting question: are these two formulations of
applyFunctor of equal power? That is, is it possible to implement
each in terms of the other? It's straightforward to see that we can implement
applyFunctorUncurried in terms of applyFunctor since
it's precisely the implementation above. What about implementing applyFunctor
in terms of applyFunctorUncurried? This turns out to be
pretty straightforward too:
function applyFunctor(funcFunctor, argFunctor) {
return functor.applyFunctorUncurried(apply, funcFunctor, argFunctor);
}
function apply(func, value) {
return func(value);
}
Please let me know if you spot mistakes in any of the above -- I've not
exactly been rigorous in proof!
I'd be curious to know if there are any languages that include the
alternative formulation of applyFunctor, and whether there are
common cases where the original formulation is preferable even in uncurried
languages.
Topics: Functional programming, Language design, JavaScript
Saturday 16 June 2012 12:33
Many advocates of functional programming suggest that the concept of state,
the idea that a value can change and mutate over time, makes reasoning
about your program much harder, leading to more bugs. Most languages allow some
form of mutability, and can therefore implement both functional and imperative
algorithms, even if the preference is strongly towards immutability.
In a completely pure functional language, mutability is
entirely removed. Since some concepts are arguably easier to understand and
implement when using mutable state, this can mean certain problems are
harder to solve in a purely functional language. But what if we allowed a limited
form of mutability in such a way that we still preserve many of the nicer
properties of functional programming, such as referential transparency?
To take a simple example: suppose we want to append an item to the end of a
list. In an imperative language, we might write something like this:
list.append("first")
so now list has an extra item, meaning that the original value
of list no longer exists. In a functional programming
language, we'd create a new value instead of mutating the original list:
val longerList = list.append("first")
We can now use both list and longerList, since
list was not modified during the append. This means we never need
to reason about what state list is in – its value never changes.
The trade-off is that a functional append tends to be more expensive than an
imperative append. If we don't actually want to use list again, then this is
arguably a bad trade-off. What if we could allow the list to be mutated under
the covers, but still be able to present a programming model that appears to
preserve immutability? So, we write the same code:
val longerList = list.append("first")
but list is now implemented as a mutable list. The compiler must
now ensure that list is never used after the append operation.
This means the actual implementation is effectively the same as when written
in an imperative style, but we ensure that whenever we change the value of an
object, we also change the name used to access it.
This approach does have some severe limitations. For instance, sharing
mutable state between many objects is likely to be impossible. If we allowed
mutable state to be shared, then mutating that state inside one object would
require marking all objects that hold that state to be unusable. In general,
having the compiler keep track of this is likely to be unfeasible.
Yet this sharing of mutable state is arguably the worst form of mutablility.
It means that changing something in one part of your system could change something
in another far away part of the system. This idea of changing
the name whenever we change the value is most useful for mutability in the
small, when we just want to implement a particular algorithm efficiently.
However, there still might cases where you'd quite reasonably want to share
mutable state between, say, just two objects. The more interesting question is:
is it possible to handle this case without requiring the user to write an
excessive number of hints to the compiler?
Topics: Language design, Functional programming
Thursday 23 February 2012 13:22
While thinking about what subsets of common languages, such as JavaScript and Java, could be considered pure, it occurred to me that object identity in most languages is an unexpected source of impurity. That is, if you're using object identity, you're not writing purely functional code.
Take, for instance, this piece of JavaScript:
var createEmpty = function () {
return {};
};
var first = createEmpty();
var second = createEmpty();
var isTheSame = first === second
We create two empty objects, and then determine whether they represent the same object using the triple equals operator (using is in Python or == in Java would have much the same effect). Since they were constructed separately, isTheSame holds the value false. Yet in a purely functional language, calling the same function with the same arguments (in this case, no arguments) twice should return the exact same value.
Strictly speaking, it's the construction of the object that is the impure code: calling the identity operator with the same arguments will always return the same value, whereas each time we construct an object, we assign it a different identity. However, code that either contains no use of object identity, or contains no construction of objects can be considered pure. Treating object identity as the impure concept that cannot be used is, in my opinion, the more useful option: it's quite handy being able to construct objects.
Topics: Functional programming, Language design