How to force the evaluation of a lambda term in haskell to the strong normal form

Question

I was wondering if it is possible to turn off lazy evaluation in Haskell;
I would like to force the evaluation of a lambda term to the strong normal form.

For instance: I would like \x -> (\y -> y) x 1 to be reduced to \x -> x 1

Thanks in advance.

See here: http://stackoverflow.com/questions/15627849/turn-off-lazy-evaluation-in-haskell — Tom Savage, Jul 10 '13 at 10:33
I'd just like to point out that the second sentence makes this a much more specific question than the one this is supposedly a duplicate of. — kosmikus, Jul 10 '13 at 11:14
This isn't a duplicate of the suggested question. This is about evaluation under lambda. — augustss, Jul 10 '13 at 11:37
You can't do exactly that with any Haskell implementation I know of. What are you trying to accomplish? — augustss, Jul 10 '13 at 11:38
I think you cannot force the expression in a lambda expression without applying the lambda in the general case. — bennofs, Jul 10 '13 at 11:39

Petr · Answer 1 · 2014-07-06T19:52:38.473

You can't do it. The reason is that Haskell isn't supposed to perform lambda term reductions. Haskell evaluates programs (lambda terms) to values. One possibility how to do this would be to really perform lambda term reductions, but this would be quite inefficient. So Haskell compilers use many sophisticated techniques such as graph reduction instead. Therefore you can't observe differences such as (\x -> x) y vs y during the evaluation process - there are no actual lambda terms to be observed.

Note that GHC has NFData type class which allows to evaluate terms to their normal forms using rnf - r-educe to n-ormal f-orm (but only products or coproducts, it still doesn't evaluate terms under lambdas, as @JakeMcArthur pointed out). However, this doesn't give you access to the normal form expressed as a lambda term. It only tells Haskell to perform this evaluation during the computation.

It's worth noting that `NFData` does not reduce under lambdas, either. — Jake McArthur, Jul 06 '14 at 18:31

score 0 · Answer 2 · answered Jul 17 '13 at 08:29

This question may be tackled by supercompilers. Right now, there is none that works really well with the current ghc and current packages.

There exists an older implementation of a supercompiler: http://community.haskell.org/~ndm/supero/

I you are interested in some newer considerations, this may be of interest: http://pure.ltu.se/portal/files/2231262/nwpt08-scp.pdf

However, I cannot either propose a proper solution.

How to force the evaluation of a lambda term in haskell to the strong normal form

2 Answers2