Recitation 19

Today: Separating Analysis from Execution

Staging: A Mechanism
Static Analysis: Why?
Structure of the Analyze-Evaluator

Staging with Currying

The basic idea behind the new evaluator is staging. Instead of taking an expression and an environment and producing a result, the analyzer takes an expression and returns a function which itself takes an environment and gives a result. This transformation of a function from the type

    f : A x B -> C

to the type

    f : A -> (B -> C)

is known as currying, and is named for a mathematician and not an Indian dish. The procedure arrow binds to the right, so this type is usually written A -> B -> C.

The transformation is most easily seen on a tiny toy example. Here is a curried version of addition:

    (define (curried-add x) (lambda (y) (+ x y))

It's type is (Number -> Number -> Number), unlike the primitive addition procedure whose type is
(Number x Number -> Number). The expression

    (curried-add 5)

evaluates to a procedure that adds 5 to its argument, so

    ((curried-add 5) 6)

evaluates to 11, just like (+ 5 6).

Staging can be used to improve the modularity of a program. For example, suppose we are building a browser that makes http requests using URLs over a network connection that it sets up at the start. If the procedure that makes the request has the type

    get-page : Connection x URL -> Page

then we will have to pass the connection around in the code. It would be better to use a function of the form

    get-page : Connection -> URL -> Page

because now we can bind the connection at the start and then bind the URLs later:

   (let* ((connection ...)
           (getp (get-page connection))
      (getp url)

A property of this program that gives us a good tip-off that staging would help is the discrepancy in the frequencies with which new values of the arguments are created. Only one or a few connections are used, but lots of URLs are accessed. Similarly in our evaluator, you might analyze the program once and run it on many different inputs.


-- write a curried version of filter with type

    filter : (A -> Bool) -> List<A> -> A

Pre-Execution Analysis

What can go wrong in a Scheme program?
What can you tell from looking at the code?
What could a computer tell from looking at the code (and without executing it)?

-- Bad syntax
-- Wrong number of args to a procedure
-- Application of non-procedure
-- Infinite loop
-- Missing else clause
-- Taking car of a non-cons cell
-- Division by zero
-- Applying a numeric procedure to a non-number
-- Relying on an implementation-dependent feature
-- Using an undefined value

Which of these always causes runtime failures? Sometimes?

We talked about the advantages of static analysis: checking the program before you run it. I explained how some languages are safe, but achieve it by runtime checks (eg Scheme); some are not safe (eg, C++); and some are safe and achieve it at compile-time (eg, Java).

We discussed expressions like (if #t 1 (+ 1 "hello")) which will not fail but which a type checker would reject. In fact our basic evaluator will successfully execute even an expression with a syntax error in it, such as

    (if #t 1 (define))

since syntax checking is performed at the same time as evaluation. Our new evaluator performs analysis first. In the version we discussed in this recitation, no type checking is done, so (if #t 1 (+ 1 "hello")) is accepted but  (if #t 1 (define)) is rejected.

Is this code bad? Why? Why not?

    (define (f x) (if (= 3 x) (+ 1 x) (car x)))

We didn't have time to discuss this.

Analyzer Code

We looked at the code for the analyze-evaluator and discussed:
-- how it finds errors before evaluation. The expression (+ (display 1) (define)) fails without displaying 1 (unlike our basic evaluator).
-- how it reduces execution time, by translating data structures into procedures, saving the effort of switching on the expression type, etc.
-- how, for the factorial function, this amounts to "compiling" the body.

Daniel Jackson
November 9, 1999