SICP 3a
Henderson Escher Example
Table of Contents
1 Recap
How data is used, can be separated from how it is represented.
; vectors (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)))) (define make-vector cons) (define xcor car) (define ycor cdr) ; line segments (define make-segment cons) (define seg-start car) (define seg-end cdr)
Mathematically speaking, the set of data objects in LISP is closed under the operation of forming pairs.
2 Lists
Lists provide a convention for representing sequences. A list is implemented
as a sequence of pairs chained together, where the cdr of a pair is the next
pair, and the last cdr is nil.
The following two instructions are equivalent:
(cons 1
(cons 2
(cons 3
(cons 4 nil))))
(list 1 2 3 4)
3 For each map
We will create procedures to apply/run procedures on each element in a list in turn.
(define 1-to-4 (list 1 2 3 4))
(define (scale-list s l)
(if (null? l)
nil
(cons (* (car l) s)
(scale-list s (cdr l)))))
This can be generalised.
(define (map p l)
(if (null? l)
nil
(cons (p (car l))
(map p (cdr l)))))
(define (scale-list s l)
(map (lambda (item) (* item s))
l))
(map square 1-to-4)
(map (lambda (x) (+ x 10)) 1-to-4)
for-each is also a powerful tool.
(define (for-each proc list)
(cond ((null? list) "done")
(else (proc (car list))
(for-each proc (cdr list)))))
4 Henderson Escher example
4.1 Basics
By exploring a language created by Peter Henderson, for creating Escher-like images, we will cover everything we have seen so far:
list structure
abstraction
representation
higher-order procedures
metalinguistic abstraction
One of the ways of tackling complexity, is to build a suitably powerful language.
As with any language, we must first determine what are the:
primitives;
means of combination;
means of abstraction.
In this language, there is only one primitive: picture. There are many means of
combination: rotate above flip beside etc.
(define (coord-map rect)
(lambda (point)
(+vect
(+vect (scale (xcor point) (horiz rect))
(scale (ycor point) (vert rect)))
(origin rect))))
(define (make-picture seglist)
(lambda (rect)
(for-each
(lambda (s)
(drawline
((coord-map rect) (seg-start s))
((coord-map rect) (seg-end s))))
seglist)))
; To create a picture in a rectangle
(define r (make-rect ...))
(define g (make-pict ...))
(g r)
4.2 Means of combination
By representing data (namely rectangles/pictures) as procedures, means of combination can be easily implemented.
(define (beside p1 p2 a)
(lambda (rect)
(p1 (make-rect
(origin rect)
(scale a (horiz rect))
(vert rect)))
(p2 (make-rect
(+vect (origin rect) (scale a (horiz rect)))
(scale (- 1 a) (horiz rect))
(vert rect)))))
(define (rotate90 pict)
(lambda (rect)
(pict (make-rect
(+vert (origin rect) (horiz rect))
(vert rect)
(scale -1 (horiz rect))))))
4.3 Means of abstraction
The real punchline comes when you look at the means of abstraction.
As we have implemented means of combinations as procedures, when we abstract further, everything that LISP supplies us for manipulating procedures is already available.
Not only is this language implemented in LISP, it is also embedded in LISP.
(define (right-push p n a)
(if (= n 0)
p
(beside p (right-push p (- n 1) a) a)))
Generalise with the power of LISP.
(define (push comb)
(lambda (pict n a)
((repeated (lambda (p) (comb pict p a))
n)
pict)))
(define right-push (push beside))
The language of schemes of combination sits upon the language of geometric positions which in turn is built upon the language of primitive pictures. Each layer is split into a whole language, rendering it more robust than forever splitting out a task into subtasks, as in each layer there is a whole vocabulary to express things in that layer.
The design process is not so much about implementing programs, as it is about implementing languages.
