Programming Languages

# Hausaufgabe 4

Please hand in this homework before 11.06.2015. You may either submit by email to Yufei Cai
Alumni
Yufei 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.

1. Learn Racket. These are some good websites:
2. Write down the Racket expression to evaluate `1 + 2 + 3 + 4`.

3. 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
``````
4. 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
``````
5. 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.