Hausaufgabe 4

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.

Groups

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.

Exercise 7

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:
- trycode.io: interactive web-based tutorial
- Mobius Techblog: article series on DrRacket in German
Write down the Racket expression to evaluate 1 + 2 + 3 + 4.
Define a racket function double that 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 if.
```
(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`
```
Composing double with 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
```
Composing sqrt with double computes the square root of the double of a number.
```
((compose sqrt double) 2 ) ; evaluates to 2
((compose sqrt double) 72) ; evaluates to 12
```

Exercise 8

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 double, negate and compose from Racket to lambda calculus, according to the following scheme:

λx. t    ==    (lambda (x) t)
t₁ t₂    ==    (t₁ t₂)

Exercise 9

What exactly is the lambda calculus you are using in Exercise 7? Write down its syntax definition and evaluation rules.