See also
For linguistic comfort, Scheme offers the special form
(case e
[(v1_1 ... vM1_N1)
e1]
[(v2_1 ... vM2_N2)
e2]
...
[(vK_1 ... vMK_NK)
eK]
[else
e0])
to stand for
(let ([v e])
(cond
[(member v '(v1_1 ... vM1_N1))
e1]
[(member v '(v2_1 ... vM2_N2))
e2]
...
[(member v '(vK_1 ... vMK_NK))
eK]
[else
e0])
where v is a “fresh” variable, i.e., one that does not occur in e1, e2, ..., eK, and e0. (Procedure member is predefined, takes two arguments – a value and a list of values – and tests whether the value occurs in the list of values.)
In other words, alternatively to writing, e.g.,
(define 246?
(lambda (x)
(if (member x '(2 4 6))
#t
#f)))
one can write a case expression:
(define 246?
(lambda (x)
(case x
[(2 4 6)
#t]
[else
#f])))
For linguistic comfort, Scheme offers the special form
(begin e1 e2 ... eN-1 eN)
to stand for
(let* ([_whatever_ e1]
[_whatever_ e2]
...
[_whatever_ eN-1])
eN)
where _whatever_ is a “fresh” variable, i.e., one that does not occur in e1, e2, ..., eN-1, and eN.
In other words,
Example:
> (define chatty-factorial
(lambda (n)
(begin
(printf "(chatty-factorial ~s)~n" n)
(if (= n 0)
1
(* n (chatty-factorial (- n 1)))))))
> (chatty-factorial 5)
(chatty-factorial 5)
(chatty-factorial 4)
(chatty-factorial 3)
(chatty-factorial 2)
(chatty-factorial 1)
(chatty-factorial 0)
120
>
Each time it is called, chatty-factorial issues a formatted printout about its actual parameter.
So we can construct lists with cons, list, and append. Quasiquotation is a short-hand for specifying these lists by writing them down as templates with placeholders specified with unquote. If there are no occurrences of unquote, quasiquote behaves as quote:
> (quasiquote (1 2 3 4))
(1 2 3 4)
> (quote (1 2 3 4))
(1 2 3 4)
>
The templates allow arbitrary sub-lists, even improper ones:
> (quasiquote (1 (+ 2 3) 4 . 5))
(1 (+ 2 3) 4 . 5)
>
A placeholder and how to fill it is specified with unquote. For example, unquoting (+ 2 3) entails this expression to be evaluated and its result to fit in the resulting list, without using explicit list constructors:
> (quasiquote (1 (unquote (+ 2 3)) 4 . 5))
(1 5 4 . 5)
> (cons 1 (cons (+ 2 3) (cons 4 5)))
(1 5 4 . 5)
>
Arbitrary expressions can be unquoted:
> (quasiquote (1 (unquote (append '(10 20 30) '(40 50 60))) 4 . 5))
(1 (10 20 30 40 50 60) 4 . 5)
> (cons 1 (cons (append '(10 20 30) '(40 50 60)) (cons 4 5)))
(1 (10 20 30 40 50 60) 4 . 5)
>
Often, the result of unquotation is a list that we want to see “spliced in” in the resulting list. To this end, we use unquote-splicing instead of unquote:
> (quasiquote (1 (unquote-splicing (append '(10 20 30) '(40 50 60))) 4 . 5))
(1 10 20 30 40 50 60 4 . 5)
>
Finally, just like quote is abbreviated with the quote character, quasiquote is abbreviated with the backquote character, unquote is abbreviated with a comma, and unquote-splicing is abbreviated with a comma followed by @:
> `(1 (+ 2 3) 4 . 5)
(1 (+ 2 3) 4 . 5)
> `(1 ,(+ 2 3) 4 . 5)
(1 5 4 . 5)
> `(1 ,(append '(10 20 30) '(40 50 60)) 4 . 5)
(1 (10 20 30 40 50 60) 4 . 5)
> `(1 ,@(append '(10 20 30) '(40 50 60)) 4 . 5)
(1 10 20 30 40 50 60 4 . 5)
>
A popular use of quasiquotation is to write program-generating programs, based on the representational coincidence between Scheme programs and Scheme lists:
> (define make-representation-of-identity-procedure
(lambda (x)
`(lambda (,x)
,x)))
> (make-representation-of-identity-procedure 'x)
(lambda (x) x)
> (make-representation-of-identity-procedure 'y)
(lambda (y) y)
> (make-representation-of-identity-procedure 'z)
(lambda (z) z)
> (make-representation-of-identity-procedure 't)
(lambda (t) t)
> (make-representation-of-identity-procedure 'whatever)
(lambda (whatever) whatever)
>
A popular application of quasiquotation is to generate specialized programs. For example, here is how to generate a representation of a procedure that prepends a given list to its argument:
> (define make-representation-of-prepend-procedure
(lambda (xs ys)
`(lambda (,ys)
,(letrec ([visit (lambda (xs)
(if (null? xs)
ys
`(cons ',(car xs) ,(visit (cdr xs)))))])
(visit xs)))))
> (make-representation-of-prepend-procedure '(a b c) 'ys)
(lambda (ys) (cons 'a (cons 'b (cons 'c ys))))
> ((lambda (ys) (cons 'a (cons 'b (cons 'c ys)))) '(d e f))
(a b c d e f)
> (make-representation-of-prepend-procedure '(a b c d) 'zs)
(lambda (zs) (cons 'a (cons 'b (cons 'c (cons 'd zs)))))
> ((lambda (zs) (cons 'a (cons 'b (cons 'c (cons 'd zs))))) '(f g h))
(a b c d f g h)
>
Pile on many more layersand I’ll be joining you there.
So one writes a program generator by peppering it with quasiquotes and unquotes. If one wants to write a program that generates a program generator, one nests quasiquotes and unquotes. It is an error to specify more unquotes than there are quasiquotes:
> (define foo 42)
> `foo
foo
> `,foo
42
> ``,foo
`,foo
> ``,,foo
`,42
> ``,,,foo
Exception: misplaced aux keyword (unquote foo)
Type (debug) to enter the debugger.
>
Quasiquotation is a source of great expressive power in programs as well as of sumptuous headaches for programmers. As such, if there is a question about quasiquote at the exam, it will only be a simple one.
The goal of this mandatory exercise is to implement the BNF of the following subset of Scheme, and to program a syntax checker that is self-applicable:
where:
An online syntax checker is available here. (As usual, eternal glory and a chocolate piece for you if you find a bug in it.)
Here is some code to get you started. (Note: proper-list-of-given-length? was defined in the lecture notes of Week 17.)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define check-program
(lambda (v)
(cond
[(null? v)
#t]
[(pair? v)
(and (check-toplevel-form (car v))
(check-program (cdr v)))]
[else
#f])))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define check-toplevel-form
(lambda (v)
(cond
[(is-definition? v)
(check-definition v)]
[else
(check-expression v)])))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;
;;; basic predicates and accessors for definitions:
;;;;;;;;;;
;;; predicate:
(define is-definition?
(lambda (v)
(and (proper-list-of-given-length? v 3)
(equal? (car v) 'define))))
;;; 1st accessor:
(define define-1
(lambda (v)
(list-ref v 1)))
;;; 2nd accessor:
(define define-2
(lambda (v)
(list-ref v 2)))
;;;;;;;;;;
;;; the syntax checker proper for definitions:
;;;;;;;;;;
(define check-definition
(lambda (v)
(and (check-variable (define-1 v))
(check-expression (define-2 v)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;
;;; basic predicates and accessors for expressions:
;;;;;;;;;;
;;; predicate:
(define is-time?
(lambda (v)
(and (proper-list-of-given-length? v 2)
(equal? (car v) 'time))))
;;; 1st accessor:
(define time-1
(lambda (v)
(list-ref v 1)))
;;; predicate:
(define is-if?
(lambda (v)
(and (proper-list-of-given-length? v 4)
(equal? (car v) 'if))))
;;; 1st accessor:
(define if-1
(lambda (v)
(list-ref v 1)))
;;; 2nd accessor:
(define if-2
(lambda (v)
(list-ref v 2)))
;;; 3rd accessor:
(define if-3
(lambda (v)
(list-ref v 3)))
;;; predicate:
(define is-quasiquote?
(lambda (v)
(and (proper-list-of-given-length? v 2)
(equal? (car v) 'quasiquote))))
;;; 1st accessor:
(define quasiquote-1
(lambda (v)
(list-ref v 1)))
;;;;;;;;;;
;;; the syntax checker proper for expressions:
;;;;;;;;;;
(define check-expression
(lambda (v)
(cond
[(number? v)
#t]
[(symbol? v)
(check-variable v)]
[(is-time? v)
(check-time-expression v)]
[(is-if? v)
(check-if-expression v)]
[(is-quasiquote? v)
(check-quasiquote-expression v)]
[else
;;; (errorf 'check-expression "unrecognized: ~s" v)
(errorf 'check-expression "not implemented yet: ~s" v)])))
(define check-variable
(lambda (v)
(errorf 'check-variable "not implemented yet: ~s" v)))
(define check-time-expression
(lambda (v)
(check-expression (time-1 v))))
(define check-if-expression
(lambda (v)
(and (check-expression (if-1 v))
(check-expression (if-2 v))
(check-expression (if-3 v)))))
(define check-quasiquote-expression
(lambda (v)
(letrec ([visit (lambda (v number-of-nestings)
(errorf 'check-quasiquote-expression "not implemented yet: ~s" v))])
(visit (quasiquote-1 v) 0))))
;;;;;;;;;;
;;; auxiliaries:
;;;;;;;;;;
(define list-strictly-longer-than?
(lambda (v n)
(letrec ([visit (lambda (v i)
(and (pair? v)
(or (= i 0)
(visit (cdr v)
(- i 1)))))])
(if (>= n 0)
(visit v n)
(errorf 'list-strictly-longer-than? "negative length: ~s" n)))))
;;; reads an entire file as a list of Scheme data
;;; use: (read-file "filename.scm")
(define read-file
(lambda (filename)
(call-with-input-file filename
(lambda (p)
(letrec ([visit (lambda ()
(let ([in (read p)])
(if (eof-object? in)
'()
(cons in (visit)))))])
(visit))))))
;;; interface:
(define check-file
(lambda (filename)
(if (string? filename)
(check-program (read-file filename))
(errorf 'check-file "not a string: ~s" filename))))
Example of use:
Petite Chez Scheme Version 8.4
Copyright (c) 1985-2011 Cadence Research Systems
> (load "syntax-checker.scm")
> (check-file "syntax-checker.scm")
#t
> (check-file "self-interpreter.scm")
#t
> (check-expression '(if 1 2 3))
#t
>
Voilà. Happy hacking.
The constantly vigilant, sorry, CONSTANTLY VIGILANT reader will of course have noticed that much code is repeated, e.g., in the definitions of BNF accessors. For example, just above, the accessors define-1, time-1 and if-1 all are defined to be the same lambda-abstraction:
(lambda (v)
(list-ref v 1))
The what of these accessors is specific to each of them (accessing the first sub-component of: a definition, a time-expression, and an if-expression), but because our data representation is uniform, the how of these accessors is the same (accessing the second element of a list). This situation calls for code reuse: the implementation is independently defined, and the accessors are defined as instances of this implementation:
;;; the single "how"'s:
(define list-ref-1
(lambda (v)
(list-ref v 1)))
(define list-ref-2
(lambda (v)
(list-ref v 2)))
;;; the many "what"'s:
(define define-1
list-ref-1)
(define time-1
list-ref-1)
(define if-1
list-ref-1)
(define if-2
list-ref-2)
To increment a procedure argument by a constant, writing specialized procedures such as
(define add1
(lambda (n)
(+ 1 n)))
(define add2
(lambda (n)
(+ 2 n)))
(define add3
(lambda (n)
(+ 3 n)))
does the job, but at the price of much code replication and adjustment. Instead, one can lambda-abstract the varying part of this code (here: 1, 2, and 3) and obtain a generic adder function:
(define adder
(lambda (m)
(lambda (n)
(+ m n))))
Thus equipped, one can obtain the effect of the definitions above using the generic adder function by applying it to the literal to add, thereby instantiating the generic procedure with a specific integer:
(define add1-alt
(adder 1))
(define add2-alt
(adder 2))
(define add3-alt
(adder 3))
Case in point:
> (add3 10)
13
> (add3-alt 10)
13
>
Along the same line, rather than writing specialized procedures such as
(define adder
(lambda (m)
(lambda (n)
(+ m n))))
(define subber
(lambda (m)
(lambda (n)
(- m n))))
(define muller
(lambda (m)
(lambda (n)
(* m n))))
one can lambda-abstract the varying part of this code and obtain a generic operator-application function:
(define super-duper
(lambda (f)
(lambda (m)
(lambda (n)
(f m n)))))
Thus equipped, one can obtain the effect of the definitions above using the generic super-duper function by applying it to the operator to apply:
(define adder-alt
(super-duper +))
(define subber-alt
(super-duper -))
(define muller-alt
(super-duper *))
Case in point:
> (define adder-alt (super-duper +))
> (define add3-alt-alt (adder-alt 3))
> (add3-alt-alt 10)
13
>
Or again, without any intermediate naming:
> (((super-duper +) 3) 10)
13
>
In the example just above, muller-alt denotes a higher-order value: a procedure that can be applied. Since Peter Landin, the representation of functional values is known as a closure.
On a related note, Haskell Curry, who co-invented the lambda-calculus with Alonzo Church, has shown that a binary function can be encoded as a unary function yielding a unary function. He did it using a function similar to super-duper, that has since been named after him, by Christopher Strachey:
(define curry
(lambda (f)
(lambda (x1)
(lambda (x2)
(f x1 x2)))))
Its inverse reads as follows:
(define uncurry
(lambda (f)
(lambda (x1 x2)
((f x1) x2))))
Case in point:
> ((uncurry (curry +)) 10 20)
30
>
In this mandatory exercise, you are asked to write a ternary version of curry and uncurry (call it curry3 and uncurry3) such that:
> ((((curry3 +) 1) 10) 100)
111
> ((uncurry3 (curry3 +)) 1 10 100)
111
>
Let us get back to the example of code reuse for BNF accessors:
;;; the single "how"'s:
(define list-ref-1
(lambda (v)
(list-ref v 1)))
(define list-ref-2
(lambda (v)
(list-ref v 2)))
This simple example begs for code abstraction, which we achieve by lambda-abstracting the index:
;;; the generic "how":
(define make-list-ref
(lambda (i)
(lambda (v)
(list-ref v i))))
The specific procedures is then obtained by instantiating the generic procedure with the suitable index:
;;; the single "how"'s:
(define list-ref-1
(make-list-ref 1))
(define list-ref-2
(make-list-ref 2))
The chief benefits of code reuse and code abstraction is that the resulting programs are easier to debug and to maintain.
All the recursive procedures over natural numbers we have seen so far follow the inductive definition of natural numbers:
Schematically, all the definitions follow the following pattern:
(define ...
(lambda (n)
(letrec ([visit (lambda (i)
(if (= i 0)
...
... (visit (- i 1)) ...))])
(visit n))))
For example, here is a definition of addition and a definition of multiplication:
(define plus
(lambda (m n)
(letrec ([visit (lambda (i)
(if (= i 0)
n
(+ (visit (- i 1)) 1)))])
(visit m))))
(define times
(lambda (m n)
(letrec ([visit (lambda (i)
(if (= i 0)
0
(+ (visit (- i 1)) n)))])
(visit m))))
Let us capture this feeling of déjà programmé with the following visiting pattern for natural numbers, where the base case and the inductive case are parameterized:
(define right-fold-nat
(lambda (base-case inductive-case)
(lambda (n)
(letrec ([visit
(lambda (i)
(if (= i 0)
base-case
(inductive-case (visit (- i 1)))))])
(visit n)))))
(define right-fold-nat-traced
(lambda (base-case inductive-case)
(lambda (n)
(letrec ([visit
(trace-lambda visit_right-fold-nat (i)
(if (= i 0)
base-case
(inductive-case (visit (- i 1)))))])
(visit n)))))
We can now define, e.g., plus and times as instances of right-fold-nat:
(define plus-alt
(lambda (m n)
((right-fold-nat n
(lambda (c)
(+ c 1)))
m)))
(define times-alt
(lambda (m n)
((right-fold-nat 0
(lambda (c)
(+ c n)))
m)))
If you are curious to see how the computation goes, use right-fold-nat-traced instead of right-fold-nat. And if you are curious to see what the computation is doing, use quasiquote:
> (define times-alt-gen
(lambda (m n)
`(lambda (,n)
,((right-fold-nat 0
(lambda (c)
`(+ ,c ,n)))
m))))
> (times-alt-gen 5 'z)
(lambda (z) (+ (+ (+ (+ (+ 0 z) z) z) z) z))
> ((lambda (z) (+ (+ (+ (+ (+ 0 z) z) z) z) z)) 10)
50
> (times-alt 5 10)
50
>
On the occasion, we use an accumulator in our recursive definitions. For example, here is a definition of addition and a definition of multiplication that use an accumulator:
(define plus-acc
(lambda (m n)
(letrec ([visit (lambda (i a)
(if (= i 0)
a
(visit (- i 1) (+ a 1))))])
(visit m n))))
(define times-acc
(lambda (m n)
(letrec ([visit (lambda (i a)
(if (= i 0)
a
(visit (- i 1) (+ a n))))])
(visit m 0))))
Schematically, these definitions with an accumulator follow the following pattern:
(define ...
(lambda (n)
(letrec ([visit (lambda (i a)
(if (= i 0)
a
(visit (- i 1) ...)))])
(visit n ...))))
The following visiting pattern for natural numbers captures this schema. Again, the base case and the inductive case are parameterized:
(define left-fold-nat
(lambda (base-case inductive-case)
(lambda (n)
(letrec ([visit
(lambda (i a)
(if (= i 0)
a
(visit (- i 1) (inductive-case a))))])
(visit n base-case)))))
(define left-fold-nat-traced
(lambda (base-case inductive-case)
(lambda (n)
(letrec ([visit
(trace-lambda visit_left-fold-nat (i a)
(if (= i 0)
a
(visit (- i 1) (inductive-case a))))])
(visit n base-case)))))
We can now define, e.g., plus-acc and times-acc as instances of left-fold-nat:
(define plus-acc-alt
(lambda (m n)
((left-fold-nat n
(lambda (c)
(+ c 1)))
m)))
(define times-acc-alt
(lambda (m n)
((left-fold-nat 0
(lambda (c)
(+ c n)))
m)))
If you are curious to see how the computation goes, use left-fold-nat-traced instead of left-fold-nat. If you are curious to see what the computation is doing, use quasiquote:
> (define times-acc-alt-gen
(lambda (m n)
`(lambda (,n)
,((left-fold-nat 0
(lambda (c)
`(+ ,c ,n)))
m))))
> (times-acc-alt-gen 5 'z)
(lambda (z) (+ (+ (+ (+ (+ 0 z) z) z) z) z))
> ((lambda (z) (+ (+ (+ (+ (+ 0 z) z) z) z) z)) 10)
50
> (times-acc-alt 5 10)
50
>
And if you want to see both what is going on and how it is going, use both left-fold-nat-traced and quasiquote:
> (define plus-acc-alt-gen
(lambda (m n)
`(lambda (,n)
,((left-fold-nat-traced 0
(lambda (c)
`(+ ,c ,n)))
m))))
> (plus-acc-alt-gen 5 'z)
|(visit_left-fold-nat 5 0)
|(visit_left-fold-nat 4 (+ 0 z))
|(visit_left-fold-nat 3 (+ (+ 0 z) z))
|(visit_left-fold-nat 2 (+ (+ (+ 0 z) z) z))
|(visit_left-fold-nat 1 (+ (+ (+ (+ 0 z) z) z) z))
|(visit_left-fold-nat 0 (+ (+ (+ (+ (+ 0 z) z) z) z) z))
|(+ (+ (+ (+ (+ 0 z) z) z) z) z)
(lambda (z) (+ (+ (+ (+ (+ 0 z) z) z) z) z))
>
All the recursive procedures over proper lists we have seen so far follow the inductive definition of proper lists:
Schematically, all the definitions follow the following patterns:
(define ...
(lambda (vs)
(letrec ([visit (lambda (ws)
(if (null? ws)
...
(... (car ws) (visit (cdr ws)))))])
(visit vs))))
(define ...
(lambda (vs)
(letrec ([visit (lambda (ws a)
(if (null? ws)
a
(visit (cdr ws) (... (car ws) a))))])
(visit vs a))))
The following visiting patterns for proper lists capture these two schemas. Again, the base case and the inductive case are parameterized:
(define right-fold-proper-list
(lambda (nil-case cons-case)
(lambda (vs)
(letrec ([visit (lambda (ws)
(if (null? ws)
nil-case
(cons-case (car ws)
(visit (cdr ws)))))])
(visit vs)))))
(define left-fold-proper-list
(lambda (nil-case cons-case)
(lambda (vs)
(letrec ([visit (lambda (ws a)
(if (null? ws)
a
(visit (cdr ws) (cons-case (car ws) a))))])
(visit vs nil-case)))))
For example, we can define a procedure that computes the length of a proper list by instantiating either right-fold-proper-list or left-fold-proper-list:
(define length-alt
(lambda (xs)
((right-fold-proper-list 0
(lambda (x c)
(+ c 1)))
xs)))
(define length-acc-alt
(lambda (xs)
((left-fold-proper-list 0
(lambda (x c)
(+ c 1)))
xs)))
Similarly, we can define a procedure to concatenate two proper lists as an instance of right-fold-proper-list:
(define append-alt
(lambda (xs ys)
((right-fold-proper-list ys
(lambda (x c)
(cons x c)))
xs)))
And if you want to see what is going on, use quasiquote:
> (append-alt '(a b c) '(e f g))
(a b c e f g)
> (define append-alt-gen
(lambda (xs ys)
`(lambda (,ys)
,((right-fold-proper-list ys
(lambda (x c)
`(cons ',x ,c)))
xs))))
> (append-alt-gen '(a b c) 'zs)
(lambda (zs) (cons 'a (cons 'b (cons 'c zs))))
> ((lambda (zs) (cons 'a (cons 'b (cons 'c zs)))) '(e f g))
(a b c e f g)
>
Often enough, we want to map a procedure pointwise over each element of a proper list and collect the results in a new list. This programming pattern is captured in the following map procedure:
(define map1
(lambda (p vs)
(letrec ([visit (lambda (ws)
(if (null? ws)
'()
(cons (p (car ws))
(visit (cdr ws)))))])
(visit vs))))
Case in point:
> (map1 (lambda (n) (* n 10)) '(1 2 3 4 5))
(10 20 30 40 50)
> (map1 list '(1 2 3 4 5))
((1) (2) (3) (4) (5))
> (map1 symbol? '(a 1 #f "foo" () (hello . world)))
(#t #f #f #f #f #f)
>
Occasionally, the result of the procedure to map is a list, and we want to concatenate this list into a flat list of results. This programming pattern is captured in the following map-append procedure:
(define map1-append
(lambda (p vs)
(letrec ([visit (lambda (ws)
(if (null? ws)
'()
(append (p (car ws))
(visit (cdr ws)))))])
(visit vs))))
Case in point:
> (map1-append (lambda (v) (list v v)) '(1 2 3 4 5))
(1 1 2 2 3 3 4 4 5 5)
>
Occasionally too, the result of the procedure to map is a Boolean, and we want to conjoint all the pointwise Booleans into one. This programming pattern is captured in the following andmap1 procedure:
(define andmap1
(lambda (p vs)
(letrec ([visit (lambda (ws)
(if (null? ws)
#t
(and (p (car ws))
(visit (cdr ws)))))])
(visit vs))))
Case in point:
> (andmap1 number? '(1 2 3))
#t
> (andmap1 number? '(a b c))
#f
> (andmap1 number? '(1 2 c))
#f
>
Express map1 and map1-append in terms of right-fold-proper-list and test them on a few examples.
Define a map procedure for binary procedures that operates over two proper lists, pointwise:
> (map2 + '(1 2 3 4) '(10 20 30 40))
(11 22 33 44)
> (map2 + '(1 2 3 4) '(10 20 30 40))
((1 . 10) (2 . 20) (3 . 30) (4 . 40))
> (map2 cons '(x y z) '(10 20 30))
((x . 10) (y . 20) (z . 30))
>
What do you do if one of the lists is shorter than the other?
The Cartesian product of two sets is the set of all the possible pairs of elements of these two sets. So for each element of the first set, there are as many pairs as there are elements in the second set: these pairs contain this element and all the elements of the second set. Programming the Cartesian product of two sets (represented as the list of their elements, without repetition, as in Exercise 5 in Week 17) is thus an exercise in enumeration:
(define cartesian-product-2
(lambda (xs ys)
(map1-append (lambda (x)
(map1-append (lambda (y)
(list (list x y)))
ys))
xs)))
Likewise, it is very simple to program the Cartesian product of three sets:
(define cartesian-product-3
(lambda (xs ys zs)
(map1-append (lambda (x)
(map1-append (lambda (y)
(map1-append (lambda (z)
(list (list x y z)))
zs))
ys))
xs)))
Case in point:
> (cartesian-product-2 '(x y) '(a b c))
((x a) (x b) (x c) (y a) (y b) (y c))
> (cartesian-product-3 '(x y) '(a b c) '(1 2 3 4 5 6 7))
((x a 1) (x a 2) (x a 3) (x a 4) (x a 5) (x a 6) (x a 7)
(x b 1) (x b 2) (x b 3) (x b 4) (x b 5) (x b 6) (x b 7)
(x c 1) (x c 2) (x c 3) (x c 4) (x c 5) (x c 6) (x c 7)
(y a 1) (y a 2) (y a 3) (y a 4) (y a 5) (y a 6) (y a 7)
(y b 1) (y b 2) (y b 3) (y b 4) (y b 5) (y b 6) (y b 7)
(y c 1) (y c 2) (y c 3) (y c 4) (y c 5) (y c 6) (y c 7))
>
Program the Cartesian product of four sets.
Today, Olaf the Plucky, from a Viking tribe of Eastern Jutland, decides to automate the testing of his normalizer for Boolean expressions, in Exercise 12 of Week 17:
(define test-negational-normalization
(lambda (expression environment)
(equal? (evaluate-Boolean-expression expression
environment)
(evaluate-Boolean-expression_nnf (normalize-Boolean-expression expression)
environment))))
To this end, Olaf wants to program a procedure that takes a list of variables and that returns all the possible environments binding these variables to a Boolean. The way Olaf figures it, if the input list contains one variable, say z, there will be two possible environments: ((z . #t)) and ((z . #f)), assuming they are represented as A-lists. And if the input list contains two variables, say y and z, then there will be four possible environments:
By the same line of reasoning, if the input list contains zero variables, then there will be one possible environment, namely the empty list. And of course if the input list contains three variables, say x, y, and z, then there will be eight possible environments:
In fact, Olaf realizes, the inductive case pretty much writes itself: if the procedure maps the tail of a list of variables to a list of environments, then it should map this list of variables to twice as many environments – the environments where the first variable is bound to #t, and the environments where the first variable is bound to #f. So there he is:
(define all-possible-environments
(lambda (xs)
(if (null? xs)
(list '())
(let ([es (all-possible-environments (cdr xs))])
(append (map (lambda (e)
(cons (cons (car xs) #t) e))
es)
(map (lambda (e)
(cons (cons (car xs) #f) e))
es))))))
Thus equipped, Olaf can pluckily automate the testing of his normalizer for Boolean expressions. Given a Boolean expression and a non-empty list of names, he can enumerate all the possible Boolean environments and check that in each of them, interpreting the given expression gives the same result as (1) compiling it into normal form and (2) interpreting this normal form:
(define test-nnf*
(lambda (expression names)
(let ([results (map (lambda (environment)
(test-nnf expression environment))
(all-possible-environments names))])
(andmap1 (lambda (result)
(or (equal? (car results) result)
(errorf 'test-nnf*
"differing results: ~s and ~s"
(car results)
result)))
(cdr results)))))
Write all-possible-environments using right-fold-proper-list.
The powerset of a set is the set of its subsets. So the powerset of the empty set is a set containing the empty set, and the power set of a singleton set is a set containing both this set and the empty set. As for the powerset of a 2-elements set, it contains 4 subsets: the full set, the empty set, and two singleton sets. And the powerset of a 3-elements set contains 8 subsets. So if a set has size n, the size of its powerset is the power of 2 to the n. Representing sets as in Exercise 5 in Week 17, i.e., as a list of their elements, without repetition, we can see how they “double” up in size:
> (powerset '())
(())
> (powerset '(z))
((z) ())
> (powerset '(y z))
((y z) (y) (z) ())
> (powerset '(x y z))
((x y z) (x y) (x z) (x) (y z) (y) (z) ())
>
The second half of the next powerset is always the previous powerset. As for the first half, it is like the second half, but with a new element prepended to it. Based on this inductive characterization, the code pretty much writes itself:
(define powerset
(lambda (xs)
(letrec ([visit (lambda (ys)
(if (null? ys)
(list '())
(let ([zss (visit (cdr ys))])
(append (map1 (lambda (zs)
(cons (car ys) zs))
zss)
zss))))])
(visit xs))))
Write powerset using right-fold-proper-list.
Mistakes make exceptional possible.Mistakes lead to new directions.
Restored the forgotten non-terminal <definition> [06 May 2012]
Added a precision in the description of quasiquote-expressions [05 May 2012]
Polished the description of quasiquote-expressions and their handling in Exercise 0 [04 May 2012]
Completed this lecture note with the section on recursive programming, including the non-mandatory exercises [03 May 2012]
It’s not a bug. It’s a feature.
Added check-file, as suggested by Jonas ‘Sortie’ Termansen, and almost completed this lecture note, except for the section on recursive programming [03 May 2012]
Preliminary version updated with right-fold-nat [02 May 2012]
Preliminary version updated with code abstraction and code reuse [02 May 2012]
Brother, got a DAIM?—anonymous
Preliminary version updated with quasiquotation [02 May 2012]
Preliminary version created [01 May 2012]