Functional Programming

History

Book claims Lisp to be the second language after FORTRAN, ignoring another language which came before Lisp

Lisp came into existence in 1958

McCarthy big on AI applications created and used Lisp

Even today, several AI applications are written in Lisp

Lisp makes it easier to handle symbolic computations

Everything in Lisp is a function.

You want to quit the lisp interpreter, you execute a function called (quit)

Basic syntax (page 387):

(define x 25) ; assigned 25 to x

(* 2 3 4 5 6) ; returns 2*3*4*5*6

* is a function, similarly we have a function called +

See page 388

a function can be defined using the define statement

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

a function called square which accepts one parameter returns the multiplication of x by x.

Lambda functions

instead of defining a function

(define (dist x y) (+ (square x) (square y)))

and then calling it as (dist 5 7)

we can combine definition and call in one stroke as

((lambda (x y) (+ (square x) (square y))) 5 7)

We have defined a noname function. That means we can’t call it again and doesn’t support recursion

Conditional execution can be done using two different constructs

(if (= x y) 1 0)

we can use the value of the if expression in an assignment as

(define z (if (= x y) 1 0))

z gets the value of 1 if x is equal to y else z gets the value 0

The language is very flexible and orthogonal

(define x 25)

x

25

(define x ‘(this is a list))

x

(this is a list)

First we had made x to be an integer then we changed it to be a list of symbols: weakly typed language

Another conditional structure is (cond)

cond is similar to switch/case

see the syntax on page 390

let construct as opposed to let*

(let ((sq-3 (sq 3)) (sq-4 (sq 4))) (+ sq-3 sq-4))

assign 9 to sq-3 assign 16 to sq-4 and then add sq-3 and sq-4

The real strength of lisp is in LISt Processing hence the name LISP

You can put a quote in front of any string to let Lisp know that we are talking about a symbol as opposed to a variable

(define e epsilon)

error

(define e ‘epsilon)

then e becomes equal to the symbol epsilon

here quote is giving you something like a string in the imperative language

‘epsilon

(quote epsilon)

It is a really a function called quote. The notation using ‘ only gives you a short form and reduces some of the inconvenient paranthesis

As you can see every construct is LISP is a function. Functional language.

You can’t even quit lisp interpreter without executing a function: (quit)

(this is a list)

((this is) a nested list (which has (lists within a list))))

The above list has five elements

First and last elements are lists themselves. This list is different from

(this is a nested list which has lists within a list)

the above list has 11 elements

See Figure 10.2 for another example, represented pictorially

(car l) gives you the first element

(cdr l) gives you the list except the first element

(define l (this is a list))

(car l)

this

(cdr l)

(is a list)

Many times we use combination of car and cdr so Lisp provides cadr, cdar, caar, cddr. Look at page 395 Fig. 10.4 for the meaning of these

The names "car" and "cdr" were developed based on IBM 704 architecture. That’s why these days they don’t seem very meaningful

car and cdr (an their combinations) are central to the list processing

Lisp generally uses recursion instead of iteration. There is a iterative structure. Just like conditional structures the iterative structure is a function.

Some lisp functions are given in Fig. 10.5

We will study length, append, map

All of these functions use tail recursion

non-recursive step involves trivial case which is when the list is nil

length: when the list is nil length is zero otherwise length is 1 plus the length of the cdr of the list

append: if the first list is nil then the result is the second list otherwise take the cdr of the first list and append it with the second list to get say temp. Put the car of first list in the first location of the temp to get the result

note (cons x y) can also be written as (x . y)

See the recursion trees from the quiz, and other examples from the greenboard

Assignment #6: Do 10.1 and 10.2

If you want to run them to double check your answers

From DOS prompt in the lab type edscheme

Storage allocation for the list

The lisp was first developed for IBM 704, it had two parts first part (car) was used to point the element and the second part (cdr) was used to point to the remaining list. Figure 10.9.

That is the origin of the names car and cdr. See page 413.

Lisp leaves a lot of intermediate lists in the memory

You need garbage collection

When

when you are low on the memory (lazy)

return a cell back if it is not going to be needed after the operation (eager)

How

start from bound variables and mark all the cells that can be reached through the links

sweep off unmarked cells

Garbage collection adds inefficiency to the execution