CS 461
Lambda Calculus 7: Functional Programming in Racket
Yanling Wang
Computer Science and Engineering Penn State University
Carnegie Mellon
1
How to encode things in 𝝀-Calculus
¢ Booleans (lecture 18/19) § True, False
§ Boolean operations: and, or, …
§ if expression: if condition then-expr else-expr
¢ Natural Numbers (lecture 18/19)
§ Natural numbers 0, 1, 2, …
§ Operations on natural numbers, +, -, *, /
¢ Structures (19, 20)
§ Pair, and left/right selection (lecture 19) § List (lecture 20)
¢ Recursive functions (lecture 21)
Carnegie Mellon
2
Encoding: List
NULL ≜ FALSE ≜ λ𝑥 𝑦.𝑦 CONS ≜ PAIR≜λ𝑥𝑦.λ𝑓.𝑓𝑥𝑦
CAR ≜LEFT≜λ𝑝.𝑝λ𝑥𝑦.𝑥 CDR ≜RIGHT≜λ𝑝.𝑝λ𝑥𝑦.𝑦
NULL? ≜λ𝑙.𝑙(λh𝑡.λ𝑑.FALSE)TRUE LISTFUNCTION ≜ λ𝑙. 𝑙 (λh 𝑡. λ𝑑. tht) tnull
Carnegie Mellon
3
Functional Programming in Racket
¢ Definitions: (define …)
¢ Functions: (lambda (…) …)
¢ Numbers and Booleans § +,-,*,/
§ comparisons
¢ Conditional: (if … … …) (cond [… …] [… …] [else …]) ¢ List: (cons … …), (car …), (cdr …)
¢ Local Bindings (let …) (let* …) (letrec …)
Carnegie Mellon
4
Evaluation Order
¢ Normal Order:
§ Pass in function arguments unevaluated as it is.
§ Used in Macros (define-syntax…), some call-by-need special cases.
§ Can avoid evaluating some arguments that will never be used.
§ May duplicate evaluation of the same argument if it is used multiple times.
¢ Applicative Order:
§ Evaluate function arguments before passing them to a function.
§ Used by most programming languages: Racket/Scheme/Ocaml/C/Java etc.
§ May lead to waste of time (or infinite loops) when try to evaluate some arguments that will never be used.
§ But avoid duplicating evaluation of the same argument.
Carnegie Mellon
5
Evaluation Order Example (1): (define double (lambda (x) (+ x x))
Carnegie Mellon
Applicative Order
(double (* 3 4)) Þ (double12)
Þ (+1212)
Þ 24
Normal Order
(double (* 3 4))
Þ (+(*34)(*34)) Þ (+12(*34))
Þ (+1212)
Þ 24
6
Evaluation Order Example (2):
(if #t 0 ((lambda (x) (x x)) (lambda (x) (x x))))
Applicative Order
Infinite evaluation when (myif…) tries to evaluate:
(λ𝑥. 𝑥 𝑥)(λ𝑥. 𝑥 𝑥)
Normal Order
Returns 0 right away. (if…) did not try to evaluate:
(λ𝑥. 𝑥 𝑥)(λ𝑥. 𝑥 𝑥)
Carnegie Mellon
7
Thunks and Delayed Evaluation ¢ We know how to delay evaluation in Racket
§ Put expression in a function ¢ Thunk
§ A zero argument function used to delay evaluation is called a thunk.
§ To thunk the expression e: § (lambda () e)
¢ Evaluation Order Example (2b)
§ myif2 uses thunks for values in both branch.
Carnegie Mellon
8
Evaluation Order Example (3):
(define (slow-add x y)
(letrec ([slow-id (lambda (m count)
(if (= 0 count)
m
(slow-id m (- count 1))))])
(+ (slow-id x 50000000) y)))
(define (my-mult x y-thunk)
(cond [(= x 0) 0]
[(= x 1) (y-thunk)]
[#t (+ (y-thunk) (my-mult (- x 1) y-thunk))]))
Carnegie Mellon
9
Encoding Factorial in Lambda Calculus FACT ≜ λn. if n = 0 then 1 else n × FACT (n − 1)
FACTʹ ≜ λf.λn.if n = 0 then 1 else n×(f f (n−1)) FACT ≜ FACTʹ FACTʹ
Carnegie Mellon
10