We’ll be recapping things related to the Lambda Calculus.

Multiple arguments

There’s one big difference between the lambda calculus and Scheme: lambda expressions all only take one argument.

How do you represent functions that take multiple arguments? make a function that returns a function, ex.:

λx. λy. (+ x y)

This is a function (λx) that returns a function (λy) that adds the argument to x. This is called currying, and we’ll see this in ML.

The Y-combinator explanation we’ve all been waiting for

If you apply the Y-combinator to a function f (as Y f), it reduces to (f (Y f)). It, in essence, allows you to insert a function into itself.

Here’s the definition of the Y-combinator again:

Y = (λh. (λx. h (x x)) λx. h (x x))

Let’s reduce Y f down:

(λh. (λx. h (x x)) λx. h (x x)) f = Y f
β=> (λx. f (x x)) λx. f (x x)
β=> f ((λx. f (x x)) λx. f (x x))
      ^--------- This ----------^ is equivalent to (Y f),
      since it's identical to the last step.
= f (Y f)

And hopefully that makes more sense.