In my humble opinion I think you're looking at this problem from a wrong perspective. If you're creating thunks manually then you need to consider refactoring your code. In most cases thunks should be:
- Either returned from lazy functions.
- Or created by composing functions.
Returning Thunks from Lazy Functions
When I first started practicing functional programming in JavaScript I was mystified by the Y combinator. From what I had read online the Y combinator was a divine entity to be worshipped. It somehow allowed functions which didn't know their own name to call themselves. Hence it was the mathematical manifestation of recursion - one of the most important pillars of functional programming.
However understanding the Y combinator was no easy feat. Mike Vanier wrote that the knowledge of the Y combinator is a diving line between those people who are "functionally literate" and those who aren't. Honestly, the Y combinator in itself is dead simple to understand. However most articles online explain it backwards making it difficult to understand. For example Wikipedia defines the Y combinator as:
Y = λf.(λx.f (x x)) (λx.f (x x))
In JavaScript this would translate to:
function Y(f) {
return (function (x) {
return f(x(x));
}(function (x) {
return f(x(x));
}));
}
This definition of the Y combinator is unintuitive and it doesn't make apparent how the Y combinator is a manifestation of recursion. Not to mention that it cannot be used at all in eager languages like JavaScript because the expression x(x) is evaluated immediately resulting in an infinite loop which eventually results in a stack overflow. Hence in eager languages like JavaScript we use the Z combinator instead:
Z = λf.(λx.f (λv.((x x) v))) (λx.f (λv.((x x) v)))
The resulting code in JavaScript is even more confusing and unintuitive:
function Z(f) {
return (function (x) {
return f(function (v) {
return x(x)(v);
});
}(function (x) {
return f(function (v) {
return x(x)(v);
});
}));
}
Trivially we can see that the only difference between the Y combinator and the Z combinator is that the lazy expression x(x) is replaced by the eager expression function (v) { return x(x)(v); }. It is wrapped in a thunk. In JavaScript however it makes more sense to write the thunk as follows:
function () {
return x(x).apply(this, arguments);
}
Of course here we're assuming that x(x) evaluates to a function. In the case of the Y combinator this is indeed true. However if the thunk doesn't evaluate to a function then we simply return the expression.
One of the most epiphanous moments for me as a programmer was that the Y combinator is itself recursive. For example in Haskell you define Y combinator as follows:
y f = f (y f)
Because Haskell is a lazy language the y f in f (y f) is only evaluated when required and hence you don't run into an infinite loop. Internally Haskell creates a thunk for every expression. In JavaScript however you need to create a thunk explicitly:
function y(f) {
return function () {
return f(y(f)).apply(this, arguments);
};
}
Of course defining the Y combinator recursively is cheating: you are just explicitly recursing inside the Y combinator instead. Mathematically the Y combinator itself should be defined non-recursively to describe the structure of recursion. Nonetheless we all love it anyway. The important thing is that the Y combinator in JavaScript now returns a thunk (i.e. we defined it using lazy semantics).
To consolidate our understanding let's create another lazy function in JavaScript. Let's implement the repeat function from Haskell in JavaScript. In Haskell the repeat function is defined as follows:
repeat :: a -> [a]
repeat x = x : repeat x
As you can see repeat has no edge cases and it calls itself recursively. If Haskell weren't so lazy it would recurse forever. If JavaScript were lazy then we could implement repeat as follows:
function repeat(x) {
return [x, repeat(x)];
}
Unfortunately if executed the above code would recurse forever until it results in a stack overflow. To solve this problem we return a thunk instead:
function repeat(x) {
return function () {
return [x, repeat(x)];
};
}
Of course since the thunk doesn't evaluate to a function we need another way to treat a thunk and a normal value identically. Hence we create a function to evaluate a thunk as follows:
function evaluate(thunk) {
return typeof thunk === "function" ? thunk() : thunk;
}
The evaluate function can now be used to implement functions which can take either lazy or strict data structures as arguments. For example we can implement the take function from Haskell using evaluate. In Haskell take is defined as follows:
take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n - 1) xs
In JavaScript we would implement take using evaluate as follows:
function take(n, list) {
if (n) {
var xxs = evaluate(list);
return xxs.length ? [xxs[0], take(n - 1, xxs[1])] : [];
} else return [];
}
Now you can use repeat and take together as follows:
take(3, repeat('x'));
See the demo for yourself:
alert(JSON.stringify(take(3, repeat('x'))));
function take(n, list) {
if (n) {
var xxs = evaluate(list);
return xxs.length ? [xxs[0], take(n - 1, xxs[1])] : [];
} else return [];
}
function evaluate(thunk) {
return typeof thunk === "function" ? thunk() : thunk;
}
function repeat(x) {
return function () {
return [x, repeat(x)];
};
}
Lazy evaluation at work.
In my humble opinion most thunks should be those returned by lazy functions. You should never have to create a thunk manually. However every time you create a lazy function you still need to create a thunk inside it manually. This problem can be solved by lifting lazy functions as follows:
function lazy(f) {
return function () {
var g = f, self = this, args = arguments;
return function () {
var data = g.apply(self, args);
return typeof data === "function" ?
data.apply(this, arguments) : data;
};
};
}
Using the lazy function you can now define the Y combinator and repeat as follows:
var y = lazy(function (f) {
return f(y(f));
});
var repeat = lazy(function (x) {
return [x, repeat(x)];
});
This makes functional programming in JavaScript almost as fun as functional programming in Haskell or OCaml. See the updated demo:
var repeat = lazy(function (x) {
return [x, repeat(x)];
});
alert(JSON.stringify(take(3, repeat('x'))));
function take(n, list) {
if (n) {
var xxs = evaluate(list);
return xxs.length ? [xxs[0], take(n - 1, xxs[1])] : [];
} else return [];
}
function evaluate(thunk) {
return typeof thunk === "function" ? thunk() : thunk;
}
function lazy(f) {
return function () {
var g = f, self = this, args = arguments;
return function () {
var data = g.apply(self, args);
return typeof data === "function" ?
data.apply(this, arguments) : data;
};
};
}
Creating Thunks by Composing Functions
Sometimes you need to pass expressions to functions that are evaluated lazily. In such situations you need to create custom thunks. Hence we can't make use of the lazy function. In such cases you can use function composition as a viable alternative to manually creating thunks. Function composition is defined as follows in Haskell:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
In JavaScript this translates to:
function compose(f, g) {
return function (x) {
return f(g(x));
};
}
However it makes much more sense to write it as:
function compose(f, g) {
return function () {
return f(g.apply(this, arguments));
};
}
Function composition in mathematics reads from right-to-left. However evaluation in JavaScript is always from left-to-right. For example in the expression slow_foo().toUpperCase() the function slow_foo is executed first and then the method toUpperCase is called on its return value. Hence we want to compose functions in reverse order and chain them as follows:
Function.prototype.pipe = function (f) {
var g = this;
return function () {
return f(g.apply(this, arguments));
};
};
Using the pipe method we can now compose functions as follows:
var toUpperCase = "".toUpperCase;
slow_foo.pipe(toUpperCase);
The above code will be equivalent to the following thunk:
function () {
return toUpperCase(slow_foo.apply(this, arguments));
}
However there's a problem. The toUpperCase function is actually a method. Hence the value returned by slow_foo should set the this pointer of toUpperCase. In short we want to pipe the output of slow_foo into toUpperCase as follows:
function () {
return slow_foo.apply(this, arguments).toUpperCase();
}
The solution is actually very simple and we don't need to modify our pipe method at all:
var bind = Function.bind;
var call = Function.call;
var bindable = bind.bind(bind); // bindable(f) === f.bind
var callable = bindable(call); // callable(f) === f.call
Using the callable method we can now refactor our code as follows:
var toUpperCase = "".toUpperCase;
slow_foo.pipe(callable(toUpperCase));
Since callable(toUpperCase) is equivalent to toUpperCase.call our thunk is now:
function () {
return toUpperCase.call(slow_foo.apply(this, arguments));
}
This is exactly what we want. Hence our final code is as follows:
var bind = Function.bind;
var call = Function.call;
var bindable = bind.bind(bind); // bindable(f) === f.bind
var callable = bindable(call); // callable(f) === f.call
var someobj = {x: "Quick."};
slow_foo.times_called = 0;
Function.prototype.pipe = function (f) {
var g = this;
return function () {
return f(g.apply(this, arguments));
};
};
function lazyget(obj, key, lazydflt) {
return obj.hasOwnProperty(key) ? obj[key] : evaluate(lazydflt);
}
function slow_foo() {
slow_foo.times_called++;
return "Sorry for keeping you waiting.";
}
function evaluate(thunk) {
return typeof thunk === "function" ? thunk() : thunk;
}
Then we define the test case:
console.log(slow_foo.times_called);
console.log(lazyget(someobj, "x", slow_foo()));
console.log(slow_foo.times_called);
console.log(lazyget(someobj, "x", slow_foo.pipe(callable("".toUpperCase))));
console.log(slow_foo.times_called);
console.log(lazyget(someobj, "y", slow_foo.pipe(callable("".toUpperCase))));
console.log(slow_foo.times_called);
console.log(lazyget(someobj, "y", "slow_foo().toUpperCase()"));
console.log(slow_foo.times_called);
And the result is as expected:
0
Quick.
1
Quick.
1
SORRY FOR KEEPING YOU WAITING.
2
slow_foo().toUpperCase()
2
Hence as you can see for most cases you never need to create thunks manually. Either lift functions using the function lazy to make them return thunks or compose functions to create new thunks.
eval, but the fact that you loose the ability to close over variables from the scope where you're creating the lambda. – Bhang