Overview and Introduction to LISP

Table of Contents

1 Overview

Computer science, like geometry (geo- earth, -metron measurement), has an inaccurate name. Computer science is neither a science, nor particularly about computers. Geometry is the formalisation of notions of space and time. Computer science is the formalisation of intuitions about process.

Declarative knowledge: what is a square root?
Imperative knowledge: how do we find a square root?

We will use LISP to write procedures. Procedures invoke processes. Processes are the building blocks of imperative knowledge.

Computer science is really about techniques for controlling complexity, moreso than any other discipline. In computer science we deal with idealised components. Little difference exists between what we can build and what we can imagine. We are limited by our own minds; engineers are not.

The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination.

Fred Brooks, The Mythical Man Month

We will learn three techniques for controlling complexity: black-box abstraction, conventional interfaces, meta-linguistic abstraction.

1.1 Black-box abstraction

  • primitive objects: procedures, data

  • means of combination: procedures, data

  • means of abstraction: procedure definition, simple data abstraction

  • capturing common patterns: high-order procedures, data as procedures

1.2 Conventional interfaces

  • generic operations

  • large-scale structure and modularity

  • object-oriented programming

  • operations on aggregate

1.3 Meta-linguistic abstraction

  • eval/apply

  • interpreter

  • Y combinator

  • creating new languages

2 Introduction to LISP

For any new language, first determine the primitive elements, means of combination, and means of abstraction.

LISP uses prefix notation. The following

(+ 3 17.4 5)

is a combination of an operator +, with operands 3, 17.4 and 5.

To define:

(define A (* 5 5))
(define (square x) (* x x))
(define square (labmda (x) (* x x)))

To use conditionals:

(define (abs x)
  (cond ((< x 0) (- x))
        ((= x 0) 0)
        ((> x 0) x)))
(define (abs x)
  (if (< x 0) (- x) x))

The following square root procedure contains other procedures (this is called block structure). try has a recursive definition.

(define (square x) (* x x))
(define (average x y) (/ (+ x y) 2))
(define (sqrt x)
  (define (improve guess)
    (average guess (/ x guess)))
  (define (good-enough? guess)
    (< (abs (- (square guess) x))
  (define (try guess)
    (if (good-enough? guess)
        (try (improve guess))))
  (try 1))

3 Recap

So far we have covered:

  procedures data
primitive elements + * < = 23 1.738
means of combination () cond if  
means of abstraction define  

Now go make yourself a sandwich.