Recitation 3

Handouts: none.

Today's idea: lambda

Failing Evaluations

Does evaluation always succeed?
Several things can go wrong:
-- type error in primitive operation
-- never terminates with a value
-- (overflows system resources)

Examples
(/ 1 0)
(+ 1 false)
(define (f x) (f x)) (f 1)

Probing

A probe: can use (/ 1 0) to see where evaluation happens
-- (if false (/ 1 0) 3)
-- (if true (/ 1 0) 3)

What kind of thing is and?
-- (and true true)
-- (and false true)
-- (and false 0)
-- (and false (/ 1 0))

Trying to implement if as a procedure
-- (define (my-if cond then else) (if cond then else))
-- (my-if true 1 2)
-- (my-if false 1 2)
-- (my-if false (/ 1 0) 2)

And now, what about defines?
-- (define x (/ 1 0))
-- (define (f x) (/ 1 0))

Why the difference?
-- define always evals the expr
-- but the second has a hidden lambda

By the way, can I make my probe handier by writing ...
-- (define probe (/ 1 0)) ?
-- (define (probe) (/ 1 0)) ?

Which of these would also work as probes?
-- (2)
-- (+ +)
-- (if)

Probing Lambda

What do these eval to?
-- +
-- (define (f x) (+ 1 x))
-- f
-- (lambda (x) (+ 1 x))
-- (lambda (x) (/ 1 0))

The basic idea of lambda
-- in math, we sometimes write a function like this: x -> 2x
-- in Scheme, (lambda (x) (* x 2))
-- lambda makes an anonymous function

What are these functions?
-- (lambda (x) (+ 1 x))
-- (lambda (x) (+ x x))
-- (lambda (x y) (+ x y))
-- (lambda (x y) x)
-- (lambda (x y) (x))
-- (lambda (x) 2)
-- (lambda () 2)

Exercise: Write a lambda that evals to a procedure that ...
-- computes the min of two ints

Definition Sugar

A "syntactic sugar" is a shorthand.
-- (define (f x) e)
is short for
-- (define f (lambda (x) e))

What are these short for?
-- (define (f x y) 2)
-- (define (f) (2))

What is this short for?
-- (define (f x) (if (= 1 x) 1 (* x (f (- x 1)))))

Why does this work?
-- why does the "f" on the right refer to the function being defined?
-- what if I did (define f 2) before?
-- appeal to eval rule for lambda

Exercise

Replace the dots by an expression in which no division op appears:
-- (define is-odd ...)

You might want to use cond. Only required to work for positive args.

Now do it again with mutual recursion:
-- (define is-even ...)
-- (define is-odd ...)

(define is-odd (lambda (n)
                   (cond [(= n 0) false]
                         [(= n 1) true]
                         [else (is-odd (- n 2))])))

A bad version:
(define (is-odd n) (or (= n 1) (is-even (- n 1))))
(define (is-even n) (or (= n 0) (is-odd (- n 1))))

A good version:
(define (is-odd n) (and (not (= n 0)) (is-even (- n 1))))
(define (is-even n) (or (= n 0) (is-odd (- n 1))))

Lessons
-- Termination can be a tricky issue! Wishful thinking can be too wishful
-- Bad version works when answer is true: be skeptical of testing

Daniel Jackson
September 15, 1999