3A Henderson Escher Example⁠

# Part 1

# Recap

• Now we know about procedural abstraction and data abstraction.
• We can isolate the way data objects are used from the way that they are represented.
• We learned how to make pairs with cons, car, and cdr.
• We can glue together arbitrary things with cons, not just numbers.
• We learned about closure: the things that we combine can themselves be combined. This allows us to build complexity.

# Lists

• There are a lot of different ways of building list structure.
• Lisp has a convention for representing a sequence as chained pairs, called a list.
• The car of the pair is the first item. The cdr of the pair is the rest of the sequence.
• The cdr of the last pair has a special marker. This is the empty list, also called nil or null. It is printed as (). The predicate null? checks if a list is empty (is nil).
• Lisp has a procedure called list, which is just an abbreviation for the nested pairs.

# Mapping lists

• It is common to write a procedure that does the same thing to each item in a list and returns a new list of transformed items.
• The recursive strategy is to apply the operation to the car of the list, and then cons that onto the rest of the list which has already been mapped (wishful thinking).
• Rather than doing this manually each time, we use the higher-order procedure map.
• Thinking in terms of operations on aggregates is a powerful idea. It liberates us from worrying about recursion or other details.
• for-each is like map, but it doesn’t build up a new list. It is just for side-effects.

# Part 2

# Henderson Escher example

• We will build a language for describing self-similar, fractal-like figures.
• This example will blur the line between procedures and data.
• There is only one primitive: a painter. A painter draws its image within a frame.
• We have means of combination: rotate, beside, and below.
• Thanks to the closure property, we can build up complexity in this language quickly.
• A frame is a parallelogram defined by an origin vector and two side vectors.
• All frames are based on transformations from the unit square.
• We can build primitive painters from lists of line segments.
• A painter is a procedure that takes a frame and draws its image within the frame.

# Part 3

# Importance of closure

• Representing painters as procedures is nice because the means of combination just falls out, and you automatically get the closure property.
• The procedures beside and below are trivial to write. rotate is similarly simple.
• The real punchline comes when you look at the means of abstraction. Since painters are just procedures, everything that Lisp supplies for procedures is automatically available to us in this painting language.
• We can write recursive painters without ever having purposely built recursion into the painting language. We can even write higher-order painters.

# The power of Lisp

• The difference between merely implementing something in a language and embedding something in the language: you don’t lose the original power of the language.

• There is no difference between procedures and data.

# Software engineering

• The methodology (or mythology) of software engineering is this: figure out your task, break it into three sub-tasks, and repeat for each sub-task. Work your way up to the top and you’ll end up with this beautiful edifice.
• Each of these nodes in the tree is supposed to fit perfectly into the whole thing.
• The Henderson example didn’t work like that. Instead, we had a sequence of layers of language. Each layer depended on the layers beneath it, but it couldn’t see their details because there was an abstraction barrier in the way.

So what you have is, at each level, the objects that are being talked about are the things that were erected at the previous level. —Abelson

• With the top-down tree, each part does a specific task.
• In the Henderson example, we had a full range of linguistic power at each level. Each level did a whole range of things, not a single task.
• This makes the system more robust: easier to adapt to changes.
• A small change in the top-down tree might cause the whole thing to fall down.
• We are talking about levels of language rather than a strict hierarchy. Each level has its own vocabulary.