1A Overview and Introduction to Lisp⁠

# Part 1

# Computer science

• It’s not a science, and it’s not really about computers.
• It’s not about computers in the same way that astronomy isn’t about telescopes.
• The ancient Egyptians began geometry using surveying instruments. We now know that the essence of geometry is much bigger than the act of using these primitive tools.
• We often conflate the essence of a field with its tools.
• In a thousand years, they will look back on us in a similar way to how we look at the ancient Egyptians: “They were playing around with these digital computers, but that was only the beginning of the much broader ideas about computation.”

# Declarative vs. imperative

Mathematical declarative statement (what-is knowledge): The square root of $x$ is the $y$ such that $y ≥ 0$ and $y^2 = x\htmlClass{math-punctuation}{\text{.}}$

Imperative instructions (how-to knowledge): approximate the square root of $x$ with the following steps:

1. Make a guess, $G\htmlClass{math-punctuation}{\text{.}}$
2. Improve the guess by averaging $G$ and $x/G\htmlClass{math-punctuation}{\text{.}}$
3. Keep improving until the guess is good enough.

# Processes and Lisp

• The above is an algorithm. More generally, it is a process.
• What is a process? It’s like a magical spirit that lives in the computer.
• The process is directed by a pattern of rules (magical spell) called a procedure.
• We conjure our spirits in a language called Lisp.
• Lisp is easy to learn just as chess is easy to learn.
• Rules stated in minutes, but there are many implications.
• Much more difficult to become a master programmer: understanding all the implications, knowing how to approach problems.

# Complexity and computer science

• Computer scientists are in the business of controlling complexity.
• This is different from the complexity that others, for example aeronautical engineers, deal with, because the complexity in CS in a sense is not real.
• Computer science deals with idealized components.
• We know as much as we want about the components; no worrying about tolerance.
• Not much difference between what I can build and what I can image.
• Other disciplines have physical constraints; in CS, the only constraint is your mind.

# Techniques for managing complexity

Black box abstraction: Take something and build a box around it. The important thing is that you don’t care what is going on inside the box—it’s not important. Black-box abstraction suppresses detail. This allows you to go on and build bigger boxes.

• Primitive objects: primitive procedures, primitive data.
• Means of combination: procedure composition, construction of compound data.
• Means of abstraction: procedure definition, simple data abstraction.
• Capturing common patterns: higher-order procedures, data as procedures.

Conventional interfaces: Agreed upon ways of connecting things together. Like standard impedances in electrical engineering.

• generic operations
• large-scale structure and modularity
• object-oriented programming
• operations on aggregates

Metalinguistic abstraction: Another way of controlling complexity is to choose a new design language (a domain-specific language, or DSL) that will highlight different aspects of the system. It will emphasize some kinds of details and suppress others. This is the technology for building new computer languages.

The process of interpreting Lisp in Lisp is like a giant wheel of two processes, apply and eval, which reduce expressions to each other. Very magical.

• apply and eval
• logical programming
• register machines

# Part 2

# Three main features

Primitive elements: Here are some primitive elements is Lisp: 3, 14.4, 5, +. These are all names that represents things. The first three represent numbers, and the last one represents the concept of addition.

Means of combination:

• We can take the sum using a combination: (+ 3 14.4 5).
• Combination: applying and operator to operands.
• The operator and operands themselves can be combinations.
• Lisp uses fully parenthesized (unambiguous) prefix notation.
• Parentheses are very different in Lisp and in mathematics.
• Nested combinations can be modeled as trees.
• Parentheses are just a way to write trees as a linear sequence of characters.

Means of abstraction: This is accomplished in Lisp with define. Defining something gives a name to an expression. We write this the same way as a regular combination, but define is not a procedure—it is a special form. We can also define procedures this way:

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

We can also make it more clear that we are naming something:

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

The former notation is just syntactic sugar for the latter: a more convenient surface forms for typing something. The former desugars to the latter.

In Lisp, you do not make arbitrary distinctions between things that are defined in the language and things that happen to be built-in.

# Case analysis

We do case analysis in Lisp using cond.

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

Each line is a clause consisting of a predicate (true or false) and an action. We can use if if there is a single case:

(define (abs x)
  (if (< x 0)
      (- x)
      x))

You can think of if as syntactic sugar for cond or vice versa.

# Recursion

• We now know enough to implement any numerical procedure that you could implement in other languages.
• We don’t need any looping constructs in Lisp. We can define things in terms of themselves using recursion.

# Block structure

• We can create a black box by packaging internals inside of a definition. This is called block structure.