wiki:Tutorial0

Special forms

What we call a special form is an expression which behaves differently from the general application rule - evaluate all the sub-expressions, than apply a procedure's body to its argument's values.

When we have expression like

(+ (square 6) (* 2 3) 9)   ; after evaluating sub-expressions and substitution:
(+ 36 6 9)                 ; now we apply a primitive procedure '+
51

Each special form has its own evaluation rule.

define - associate a symbol with a value, does not evaluate the first argument

Define is a special form that used to create a new binding - an association between a name and value. Name is a symbol. It does not evaluate its first argument and creates a new binding for it in the current environment.

(define pi 3.1459)   ; associate a symbol 'pi with a value 3.1459
pi                   ; now symbol 'pi evaluates to 3.1459

Actually a binding is just a pair '(sym val) while an environment is a list of pairs '((sym1 val1) (sym2 val2) (sym3 val3)) and adding a new binding to the current environment could be implemented as (cons (cons sym val) env).

This is where we begin to appreciate the harmony and beauty of Lisp.

lambda - evaluate a specification of a procedure into actual piece of code

Lambda is a way to create a procedure. To do it we must specify a list of formal parameters and the body of a procedure.

The list of formal parameters is indeed a list, so we write it using parenthesis - (x).

The body of a procedure is, of course, a list of expressions, so we write it as a list too: (* x x)

The lambda expression itself is a list, it contains 3 elements - symbol 'lambda, a list of formal parameters and the body of a procedure which is a list of expressions.

(lambda (x) (* x x))   ; this expression is just a list of lists

The value of this expression will be the actual code of the procedure, which could be applied to an argument at any time.

invoking a procedure - applying a procedure to its arguments

To apply a primitive procedure '+ to its arguments we form a list, containing the procedure's name - a symbol, associated with its body, and all the formal parameters. To apply a procedure means to evaluate such expression using the general evaluation rule.

(+ 5 5)
10

This is how we can apply a procedure, created with lambda expression.

((lambda (x) (* x x)) 5)
25

Fist the lambda expression is evaluated, which creates a procedure from the specs, and then we apply it to an argument 5.

What is this whole expression? It is, of course, a list, where the leftmost element is a binding to a procedure, or lambda expression, which creates a procedure in-place, right there. Do you appreciate the unity?

defining a procedure

Defining a procedure is no different from creating any other binding - a pair of symbol and a value. In this case the value is a procedure itself.

(define square (lambda (x)
	           (* x x)))
square

How could it be? Well, in lisp every value has a tag attached to it, which gives us information about of which type it is. We can think of it as a pair of a tag and value - '(tag . val). So, a procedure could be stored as ('proc ((body) params)) or whatever we wish.

abbreviation - syntactic sugar

There is an alternative syntax of defining a procedure, which is just an abbreviation for creation of a procedure with lambda and a binding with define:

(define (square x)
	   (* x x))

Notice that (square x) is a list of a procedure's name and its parameters. This is called a signature. So, the whole expression's meaning is create a new binding between a signature, which is a list, not a symbol, and the body of a procedure.

Remember, that this is just a syntactic sugar. The logic is described above.

helper procedures

A helper procedure is used to isolate some piece of code for clarity and re-use

(define (sort l)
   (if (null? l)
       '()
       (insert (car l)        ; invoking a helper procedure
          (sort (cdr l)))))

(define (insert n l)
   (cond ((null? l) (cons n '()))
         ((< n (car l)) (cons n l))
         (else (cons (car l) (insert n (cdr l))))))

This sorting procedure calls a helper procedure for each element of given list, to place it properly in the already sorted result list. It works the same way people sort a hand of cards, by taking one card and inserting it into appropriate position.

nested procedures

We could define a procedure inside another procedure:

(define (squares l)
   (define square (lambda (x)     ; defining a procedure inside another procedure
                     (* x x)))
   (if (null? l)
      ()
      (cons (square (car l))
         (squares (cdr l))))) 

The underlying idea is very simple - create a new procedure and a binding for it inside another procedure. That means it will be visible and callable only within that procedure, like any other local bindings.

We do this to make a procedure and associated symbol private to this frame of environment. Each procedure has its own frame of environment, linked to the parent environment, in which the function was created.

So, the global environment is just a list of pre-defined bindings and other frames - a list of lists. Each frame is a list of bindings. Everything in Lisp logically is a list of lists made out of pairs. This is one of the sources of its magic - we could see the structure of everything.

anonymous helper procedure

Sometimes we need a small procedure to perform an operation for each element of a list. We could, of course, define and bind it to some symbol somewhere else, and then just use its name. But in order to see what it does, we must find its source.

If a procedure is small enough, we prefer to create it right there, in-place, to see the whole thing at once. This is why we need lambda expressions - to make our code self-evident and easy to comprehend.

This is a procedure that applies given predicate function to each element of given list. It returns only elements for which application of predicate returns true. This is essentially a filter.

(define keep (lambda (f l)
                 (cond ((null? l) '())
                       ((f (car l)) (cons (car l)
                                          (keep f (cdr l))))
                       (else (keep f (cdr l))))))

This is how anonymous helper procedure makes small miracles.

(keep (lambda (x) (zero? (remainder x 2))) '(1 2 3 4 5 6))

We are defining a predicate function we need right there, in-place. Because the body of a procedure is self-evident, we have no necessity to name it.

It is almost like Math - we could write a function as it is - just x^2 + 2x + 3

let

Let is an syntactic sugar for creating an anonymous procedure with lambda expression and invoking this procedure right in-place.

This expression

(let ((a 1) (b 2))
   (+ a b))

will be transformed into familiar:

((lambda (a b)
    (+ a b)) 1 2)

Note how logically consistent everything is. The list after symbol 'let is a list of bindings - a list of pairs. All those bindings exists only in the body of the let expression - the last element of it - a list of expressions.

The equivalent form is to create a anonymous procedure with lambda expression and then invoke it right there.

Now we can see clearly the scope of 'a and 'b - they are bound only inside this anonymous procedure.

This means that let is the way to create a lexical closure - a procedure with its local list of variables.

To make a recursive helper procedure we need to bind some name to it, to make another call to itself.

(define nth (lambda (x l)
               (define loop (lambda (x l)
                               (cond ((null? l) #f)
                                     ((zero? x) (car l))
                                     (else (loop (- x 1) (cdr l))))))
               (loop x l)))

There is how to use let syntax:

(define nth (lambda (x l)
   	      (let loop ((x x) (l l))
		(cond ((null? l) #f)
		      ((zero? x) (car l))
		      (else (loop (- x 1) (cdr l)))))))

This is just a rewrite - a transformation from one form into another without losing the exact meaning.

Last modified 8 years ago Last modified on Nov 17, 2012, 9:42:55 AM
Note: See TracWiki for help on using the wiki.