Please hand in this homework before 11.06.2015. You may either
submit by email to Yufei Cai
AlumniYufei Cai before 16:00, or hand in a physical copy at the lecture.
You may work in groups of 1, 2, or 3 persons. Please include the names and student numbers (Matrikelnummer) of all group members in the submission. Every group member should understand the material, because you will be tested individually in the exam.
The goal of this exercise is to learn programming in lambda calculus. For those of you who know functional programming already, feel free to do this one in lambda calculus and skip Exercise 7. The rest of you should do this one in Racket.
- Learn Racket. These are some good websites:
Write down the Racket expression to evaluate
1 + 2 + 3 + 4.
Define a racket function
doublethat doubles a number. In racket, semicolon
;starts a line comment.
(double 3) ; evaluates to 6 (double 4) ; 8 (double 5) ; 10
Define the negation of Booleans without using the built-in function
not. You may use
(negate #t) ; evaluates to #f (negate #f) ; evaluates to #t
Define function composition as a racket function
compose. You may need to use lambda expressions:
(lambda (x) body) ; the function mapping `x` to `body`
doublewith itself produces a function that computes the quadruple of a number.
((compose double double) 3) ; evaluates to 12 ((compose double double) 5) ; evaluates to 20
doublecomputes the square root of the double of a number.
((compose sqrt double) 2 ) ; evaluates to 2 ((compose sqrt double) 72) ; evaluates to 12
Note that function definitions in Racket are a shorthand for lambda expressions. If you wrote
(define (double x) ...)
you could have written
(define double (lambda (x) ...))
instead. Translate your definitions of
compose from Racket to lambda calculus, according to the
λx. t == (lambda (x) t) t₁ t₂ == (t₁ t₂)
What exactly is the lambda calculus you are using in Exercise 7? Write down its syntax definition and evaluation rules.