Scheme assignment will be up after class is done.

More scheme

Prof’s added a bit more notes in the “Scheme notes typed in class” folder on Classes.

Included in those notes:

letrec

You can use let to assign functions to local variables, because functions are values like any other. But, neither let nor let* allows for recursive or mutually recursive functions to be assigned, because they either can’t refer to any other variables (in the case of let) or can only reference each other in a strict order (in the case of let*). So there’s a letrec, which allows for any variables to reference any other variables, as such:

(define (sillyFac y)
    (letrec ((f (lambda (x) (if (= x 0) 1 (* x (g (- x 1))))))   
             (g (lambda (x) (if (= x 0) 1 (* x (f (- x 1)))))))
       (f y)
    )
)

Combining car and cdr

There are functions that combine multiple car and cdr calls:

> (car (cdr (car (cdr '((1 2) (3 4) (5 6) (7 8))))))
4
> (cadadr '((1 2) (3 4) (5 6) (7 8)))
4

list?

You can check whether something is a list by using the list? function. Both empty and non-empty lists return true, while all atoms (i.e. non-lists) return false.

You can use this to handle arbitrarily nested lists, such as for a function that counts all elements in a (potentially nested) list.

> (define (count-all L)
    (cond ((null? L) 0)   
          ((list? (car L)) (+ (count-all (car L)) (count-all (cdr L))))
          (else (+ 1 (count-all (cdr L))))))
> (count-all '(1 2 (3 4 (5 6) 7) (8 9 (10 11))))
11

pair?

This function can be used to check whether something is a non-empty list. The difference between this and the opposite of null? is that null? returns false for atoms, so it can’t be used to distinguish between non-empty lists and atoms.

Midterm review

Midterm is next class. Covers up to the end of Scheme (not lambda calculus, which will be this class). Finish homework and Scheme assignment before the midterm!

Here’s what we need to know:

• What is a PL?
• Turing completeness
• What is syntax?
• What are semantics?
• What is a compiler and an interpreter, and what’s the difference?
• Imperative vs. functional languages
• High vs. low level languages
• Regular expressions
• Context-free grammars
  • Parse trees
  • Derivations
• Concurrency
• Ada programming
  • Particularly packages and tasks
  • Not too picky on syntax
• Scoping, block structure, static vs. dynamic
• The runtime stack
• Parameter passing methodologies and their differences (pass by value, reference, value result, name…)
• Scheme programming

Doing the homework should give you the necessary overview. But also, there’s a previous exam up on the website with solutions, so review that too.

Lambda calculus

Prof’s notes for this are online, and he recommends using them for reference.

The lambda calculus, initially invented by Alonzo Church, was developed at the same time as Turing’s machine, both inspired by electromechanical computing machines that were starting to come out at the time.

But compared to Turing machines, which presumed a machine with a read/write head and so on, this was purely syntactic, operated by taking some text and substituting it with some different text according to rules.

The text, in this case, is called a lambda expression. We can define the syntax for these expressions by using a context-free grammar. And here’s that CFG:

Expression -> constant
            | variable
            | Expression Expression
            | λ variable . Expression

Constants are things like 3, +, and so on.

In simpler terms, expressions can be constants, variables, two expressions next to each other, or the letter “λ” followed by a variable, a dot, and another expression.

Examples of expressions: 3, x, + y 2, f x, or λx.+ x 2

Free variables

A variable can be free or not free. Intuitively, you can think of “free” as “non-local”. But here’s the formal definition, consisting of a few rules:

1. A variable x is free in the expression x, but not in an expression that contains any other single variable.

2. x is free in exp1 exp2 (expression 1 applied to expression 2) iff x is free in exp1 or exp2.

3. x is free in λy.exp if x and y are different variables and x is free in exp.

4. In no other cases is x free.

Effectively a recursive definition, with the first rule being the base case.

In other words, a variable is free in an expression if it’s not in an expression introduced by a lambda.

Here are some examples in which x is free:

x
+ x y
λy. + x y

Note that in none of these cases is there a λ introducing x. Here’s some examples where x is not free:

3
y
λx.x
f y

So intuitively, the variable is free if the variable is in the expression and is not introduced by a λ in the expression.

If you think of the λ as in scheme, where the λ defines a function taking a single parameter and a body, then a variable is free if it’s not the parameter.

A note on parentheses

Note that we’re going to be using parentheses for clarity in this class, but that these are not part of the official grammar of the lambda calculus. For example, we might write:

(λx.x) y

Just so that we know that this is the function defined by the brackets being applied to y, and not something like this:

λx.(x y) ; WRONG!

Substitution

This is the main computational step in the lambda calculus. We’re going to define it with this syntax:

        x[M/x]
        ^   ^
Take this   And replace all free occurrences
expression  of x by M

This results in just M:

x[M/x] = M

In the case of c[M/x], though, where c is a constant or a variable other than x, we just get c back. There are no occurrences of x to replace.

c[M/x] = c

In the case of multiple expressions, we apply the substitution to each sub-expression:

(E F)[M/x] = (E[M/x] F[M/x])

And remember that you only replace free (i.e. non-local) occurrences:

(λx.E)[M/x] = λx.E ; No change!

Let’s look at some examples.

x[z/x] = z                         ; x is free, replace it!
(+ a b)[(+ 3 4)/a] = (+ (+ 3 4) b) ; a is free too!
(λx. + x y)[y/z] = λx. + x z       ; y is free! Replace away!

But what about this?

(λx. + x y)[(* x 2)/y]  ; Uh-oh, you're introducing a new x
                        ; variable in your replacement

You can’t just do dumb substitution:

(λx. + x y)[(* x 2)/y] ≠ (λx. + x (* x 2))

Because now you’re inserting a reference to the lambda expression’s “parameter”. This is called a name capture. What you have to do instead is change the name of the “parameter” of the λ-expression, then go ahead and apply the substitution:

(λx. + x y)[(* x 2)/y] = (λz. + z y)[(* x 2)/y]
                       = (λz. + z (* x 2))

In more formal language, when you have something like this:

(λy.E)[M/x]

There are two options:

1. If y does not appear free in M, you can go ahead and do the substitution.

   λy.(E[M/x])
   

2. Otherwise, replace the “parameter” with a different one, then apply the substitution.

   λz.(E[z/y])[M/x]
   

In essence, this is very similar to “pass-by-name”, formalized.

(Sidenote: the parameter is often called the bound variable.)

Conversion rules

These rules tell you how to convert one expression to another.

Conversion in the rightwards direction is called reduction.

α (alpha) conversion

Effectively just renaming the bound variable. Converting an expression to something that means the same thing.

(λx.E) <=> (λy.E[y/x])

You can do this as long as y is not free in E.

For example:

(λy. + x y) <=> (λz. + x z)

β (beta) conversion

The most important conversion rule.

(λx.E) M <=> E[M/x]

Applying a function to an argument is the same as replacing the parameter with the value or expression passed in, in the body. Again, formalizing what it means to pass in parameters, just like pass-by-name. For example:

(λa. * a 2)(+ b 1) <=> (* (+ b 1) 2)

η (eta) conversion

Not very important, we’re not going to talk about this again.

(λx.E x) <=> E

Effectively means you can replace no-op functions with the body. The function here just takes x and passes it to E, so it’s useless.

δ (delta) reduction

To simplify our use of the lambda calculus, we define another type of reduction for the sake of convenience that lets us define constructs like if or +. This isn’t really part of the “official” lambda calculus, but is used for our convenience.

This isn’t really one rule, but several, all defining our “built-in” operators and functions.

if true E1 E2 => E1
+ 3 4 => 7
* 4 5 => 20

And so on.

Reduction sequences

This is a sequence of reductions that can be applied to an expression. For example:

(λx.(λy.+ ((λz. + z 3) 7) y) (+ x 1)) 10

We can reduce this one step at a time using our reduction rules, mainly β-reduction:

(λx.(λy.+ ((λz. + z 3) 7) y) (+ x 1)) 10
β=> (λy.+ ((λz. + z 3) 7) y) (+ 10 1))
δ=> (λy.+ ((λz. + z 3) 7) y) 11)
β=> + ((λz. + z 3) 7) 11
β=> + (+ 7 3) 11
δ=> + 10 11
δ=> 21

And this is the way lambda calculus can be used for computation.

Any expression that you can apply a β or δ reduction to is called a redex or reducible expression. An expression that contains no redexes is called a normal form.

So here’s a question: does every expression have a normal form? In other words, can every expression be reduced until it can’t be reduced any more?

Here’s the thing: the lambda calculus is Turing-complete. So you can write non-terminating programs. For example:

(λx. x x)(λy. y y)
β=>(λy. y y)(λy. y y)  ; Exactly the same thing!

In this particular example, (which could also have been written as (λx. x x)(λx. x x)) you end up infinitely getting the same thing over and over again.

We’ll continue this next class, in two weeks, after the midterm.