14 Jan
2008
14 Jan
'08
5:35 p.m.
Ben Franksen wrote:
Lennart Augustsson wrote:
What is a reduction anyway?
I am not an expert but I thought in lambda calculus one has primitive rules for evaluation, e.g. beta reduction. So a reduction is a 'smallest step' in reducing an expression to normal form, no?
Yes and no, a single beta reduction step like (\x.c(d(e(f(x))))) g => c(d(e(f(g)))) may take 5 steps in some reduction strategies since you have to walk down the expression tree to find the variable and replace it with its value. In the end, seconds are a better measure for time :) Regards, apfelmus