Search code examples
haskellterminologyevaluationreduction

Haskell "Source reduction"

I'm revising for an upcoming Haskell exam and I don't understand one of the questions on a past paper. Google turns up nothing useful

fst(x, y) = x
square i = i * i

i) Source reduce, using Haskells lazy evaluation, the expression:

fst(square(3+4), square 8)

ii) Source reduce, using strict evaluation, the same expression

iii) State one advantage of lazy evaluation and one advantage of strict evaluation

What I don't understand is what is source reduction?

Solution

  • Reduction is a term from the lambda calculus which involves a semantics-preserving transformation that replaces one term with an equivalent term. For the examples you've given, the most important kind of reductions are

    • Replacement of a name by its definition (an instance of substituting equals for equals).
    • Beta-reduction of a function application.

    Beta-reduction is the fundamental rule in the lambda calculus, and in a pure, lazy language like Haskell, it always preserves semantics. The beta rule is the one that says:

    (\x. e) m

    can be replaced by e with m substituted for x. (The substitution must avoid "capturing" free instances of x in m.)

    It's quite possible that your instructor wants you to combine reductions as follows:

    1. Find a function application where the function being applied is a name.
    2. Replace the name with its definition, which will be a lambda abstraction.
    3. Beta-reduce the application.
    4. Do this all in one step.

    Notice you often have a choice about which application to reduce; for example, in the term you give, there are two applications of square and one of fst that could be reduced in this fashion. (The application of + can also be reduced, but reduction involving constants requires different rules.)

    From the questions I see that your instructor wants you to reduce each term repeatedly until it reaches a normal form and that your instructor wants you to demonstrate your understanding of different reduction strategies. The word "source" in "source reduce" is superfluous; reduction means manipulation of source terms in some language. I would have phrased the questions as follows:

    • Using the reduction strategy that corresponds to Haskell's lazy evaluation, reduce the following expression to weak head normal form. Show each step in the sequence of reductions.

    • Using the reduction strategy that corresponds to evaluation in a strict functional language, reduce the following expression to head normal form.

    I probably would have chosen to be less coy and just name the reduction strategies: a call-by-need reduction strategy and a call-by-value reduction strategy.