SICP - Lists in LISP and the Henderson Escher functional geometry language

Today's lecture built on some of the concepts we already learned regarding combinations, introducing the concept of lists in LISP.  About half the lecture dealt with a language implemented in LISP that describes Escher like tiling pictures.  It was an interesting segment but because I can't really reproduce the graphics I didn't take very thorough notes on it.  The University of Oxford Computing lab has an exercise on their website that looks at the same Escher fish tiling problem in their own language called GeomLab. It doesn't appear to be implemented in LISP, but it does follow the same principles discussed in today's lecture. An example of the complete "Functional Geometry" language developed by Henderson implemented in LISP can be seen here.



The notes I did take:

Some review and talking about lists:

Data abstraction isolates the way an object is used from the way it is represented. We make a contract with George to represent an object and we really don't care how he implements that object as long as it adheres to our requirement or axiom.

(DEFINE (+VECT V1 V2)
(MAKE-VECTOR
(+ (XCOR V1)(XCOR V2))
(+ (YCOR V1)(YCOR V2))))

(DEFINE (SCALE S V)
(MAKE-VECTOR (* S (XCOR V))
(* S (YCOR V))))
 
These are implemented using vectors, which could be represented using pairs.
(DEFINE MAKE-VECTOR CONS)
(DEFINE XCOR CAR)
(DEFINE YCOR CDR)
Differs from prior definition of vectors, emphasizes that procedures can be objects.
We can represent line segments in the same way as above.
(MAKE-SEG (MAKE-VECTOR 2 3)
 (MAKE-VECTOR 5 1))

Closure allows us to build up complexity. The things we make can themselves be combined to make more complicated things. Set of data objects is closed under the operation of making pairs.

Arrays in Basic and Fortran is not closed, because you can make arrays of numbers but not arrays of arrays.

Many ways to glue things together:
      [ | ]
      /   \ 
  [ | ]   [ | ]
  /   \   /   \ 
 1     2 3     4

 OR

      [ | ]
 /   \ 
 [ | ]     4
 /   \
1  [ | ]   
      /   \
     2     3
 
Good idea to establish conventions so we know how things are glued together. LISP represents a chain of pairs as a list. List of 1 2 3 4 would look like this;
[ | ] -- [ | ] -- [ | ] -- [ |/]
 |        |        |        |
 1        2        3        4

 In LISP this list is constructed as such:
 (CONS 1
(CONS 2
(CONS 3
(CONS 4 nil))))

(LIST 1 2 3 4) is an abbreviation of the above chain of CONS calls, syntactic sugar.
(DEFINE 1TO4 (LIST 1 2 3 4))
(CAR 1TO4) -> 1
(CAR (CDR 1TO4)) -> 2
(CAR (CDR (CDR 1TO4))) -> 3

Using CDR to manually traverse a list is a drag, so we write procedures to do it for us.

CDR-ing down a list:
(DEFINE (SCALE-LIST S L)
(IF (NULL? L)
NIL
(CONS (* (CAR L) S)
 (SCALE-LIST S (CDR L)))))

MIT/GNU Scheme doesn't like "nil" so I used (LIST) instead, which is basically the same thing.

Higher order procedure "map" actually accomplishes list traversal in the above pattern.
(DEFINE (MAP P L)
(IF (NULL? L)
(LIST)
(CONS (P (CAR L))
 (MAP P (CDR L)))))
 
MAP takes a list and applies procedure P to every element in a list.

(DEFINE SCALE-LIST S L)
(MAP (LAMBDA (ITEM)(* ITEM S))
L))

 
Recursion should be built into general strategy rather than every particular procedure. Map could also be written as an iteration. Stop thinking about control structures and start thinking about aggregates. Similar to MAP is FOR-EACH
(DEFINE (FOR-EACH PROC LIST)
(COND ((NULL? LIST) "DONE")
(ELSE (PROC (CAR LIST))
 (FOR-EACH PROC
(CDR LIST)))))

Henderson Escher Example:

When thinking about a language, think about:
Primitives
Means of Combination
Means of Abstraction
Peter Henderson developed a language to describe Escher figures, creating and printing them.
Only primitive in Henderson's language is a "picture", which is basically a figure that has been scaled to fit a rectangle. The "picture" doesn't change when its rectangle changes.
Means of Combination (operation): 
Rotate, 
Flip, 
Decide: takes two pictures, A and B, and puts them together in a box with A scaled by horizontally by factor s, with B filling the remainder.
Beside, Above also operations.

Because of closure, we can combine pictures and then combine the combinations. Allows us to quickly build up complexity.

Basic building block is a rectangle, includes an origin, horizontal vector, vertical vector.
Assume we have a constructor MAKE-RECTANGLE
Assume we have selectors for ORIGIN, HORIZ, VERT
Implementation of these things is Georges problem (data representation problem, divorced from use {i.e. data abstraction})

We want to be able to define the transformation of a picture inside a standard 1x1 square at origin 0 and into a picture scaled to our rectangle.

(DEFINE (COORD-MAP RECT)
(LAMBDA (POINT)
(+VECT
(+VECT (SCALE (XCOR POINT)
 (HORIZ RECT))
  (SCALE (YCOR POINT)
 (VERT RECT)))
(ORIGIN RECT))))

COORD-MAP takes a rectangle as an argument and returns a procedure to map points into that rectangle.

Picture can be defined as a list of line segments. We can define picture as a procedure (lambda) that takes a rectangle as an argument and draws the transformed line segments into the rectangle.

He makes the interesting comment that LISP is lousy at solving any one problem, but what it is good at is implementing a language that is embedded in LISP that addresses a problem.

Talks about the mythology of "software engineering" where you take your task and break it into subtasks repeatedly until you get this tree "edifice" with precisely defined nodes. Apparently large systems are not defined that way.

In the tree scheme, each node is designed to do a specific task. In the henderson example, we defined a language to talk about primitives, then built on it a language to talk about geometric positions, and on that built a language of combination schemes. Each level is designed to talk about a whole family of ideas. "Levels of language" vs a strict hierarchy.