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.
Exercises:
-- write a curried version of filter with type
filter : (A -> Bool) -> List<A> -> A
Examples:
-- 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.