6.001/Recitation 3

Rob Speer

Contents 1 let 2 It's lambdas all the way down 3 Currying 4 let de-sugared 5 twice 6 Church numerals

let

It's a new special form. let lets you evaluate an expression with certain variables defined. It's nicer than define because it's not a side effect. Here's a kind of unconvincing use of it:

(define (roll-dice)
  (let ([d1 (random 6)]
        [d2 (random 6)])
    (display "die 1: " d1)
    (display "die 2: " d2)
    (display "total: " (+ d1 d2))
    (+ d1 d2)))

Note the implied begin that comes with the let.

It's lambdas all the way down

You asked for it - we'll start talking about the lambda calculus, that ideal lambda-world where everything is made of lambdas with one argument.

Here are the things we're taking for granted so far:

Side effects

That's easy - just forbid side effects. You get to input once and output once, just like a Turing machine. This makes things like begin unnecessary.

define

This one is hard. They won't mention it until the last lecture, where it will go over basically everyone's head.

Numbers and mathematical operations

These are Church numerals. We'll be working with these for most of the recitation. Stay tuned.

Strings

Strings are just big numbers (in ASCII, for example).

Functions with more than one argument

This is relatively easy, so we'll knock it off the list in the following section.

let

This is easy, too, so we'll deal with it after currying.

Currying

Currying takes functions of multiple arguments and turns them into functions of one argument. (The computer scientist Haskell Curry has such a cool name that he gets two things in CS named after him.)

Let's deal with a simple addition procedure that takes two arguments:

(define add
  (λ (x y)
    (+ x y)))

Currying it is easy.

(define curry-add
  (λ (x)
    (λ (y)
      (+ x y)))

You would call it with ((curry-add 5) 3).

Question: What does (curry-add 5) return?

let de-sugared

Remember that let binds variables to values. What else binds variables to values?

See, that was easy.

twice

With currying, we've seen procedures that return other procedures, and with lambda booleans (my-if), we've seen procedures that take other procedures as input. Let's look at a procedure that does both. twice takes a procedure f, and returns a new procedure that does f twice.

• What constraints do we need on what f does?
• Write the procedure:

Church numerals

First, for consistency's sake, let's rename twice.

(define x2 twice)

x2 (twice) is the Church numeral for 2. It represents the number 2 using lambdas.

Write (x3 f) in terms of x2 and f.

What are x1 and x0?

Write (church-inc n), a procedure that increments a Church numeral by 1.

Write (convert n), which takes a Church numeral as input and gives a Scheme number as output. (You are allowed to use existing Scheme values like 1 and + here.)

Write (church-add m n), which returns the sum of two Church numerals as a Church numeral.

Write (church-mul m n), which returns the product of two Church numerals as a Church numeral.

Write (church-pow m n), which returns m to the nth power as a Church numeral.

Hard: Write (church-dec m n), which decrements a Church numeral by 1. (Are there negative Church numerals? What happens if you decrement x0?)

Write (church-sub m n), which returns m - n as a Church numeral, if m >= n.

Write (church-geq m n), which returns my-true or my-false depending on whether m >= n.

Write (church-eq m n), which returns my-true or my-false depending on whether m = n.