Use the following code as your starting point for this assignment:
Unification pattern-matching is a technique used in automated theorem-provers, type-inferencers, computer algebra systems, and logic programming languages. The unification algorithm determines whether two symbolic expressions, called patterns, can be made equal by substituting values in place of the pattern-variables that occur in the patterns, in a consistent way. We will represent pattern variables as Scheme symbols beginning with a ?, and patterns as arbitrarily nested cons-cell structures. Some examples are shown below:
Pattern 1 Pattern 2 Unifying substitution ?x (apple banana cherry) ?x = (apple banana cherry) (?x (banana ?y)) (apple (banana cherry)) ?x = apple, ?y = cherry (?x . ?rest) (apple banana cherry) ?x = apple, ?rest = (banana cherry) (apple ?x orange) (apple ?y ?x) ?x = orange, ?y = orange (apple ?x ?y) (apple ?z cherry) ?x = ?z, ?y = cherry (apple ?x ?x) (apple banana cherry) None
A substitution is a mapping from pattern variables to patterns. Think of it as a kind of environment. The empty substitution (empty-sub) maps each variable to itself. (extend-sub s v p) returns a new substitution like s, except that variable v is mapped to pattern p. (unit-sub v p) returns a new substitution that maps v to p and everything else to itself. (instantiate p s) applies the substitution s to all of the pattern variables in pattern p and returns the resulting pattern. (compose-subs s1 s2) returns a new substitution s' such that for any pattern p, (instantiate p s') returns the same pattern as (instantiate (instantiate p s1) s2). For example:
(define s0 (empty-sub)) (define s1 (extend-sub s0 '?x 'apple)) (define s2 (extend-sub s1 '?y '(banana cherry))) (s2 '?x) => apple (s2 '?y) => (banana cherry) (s2 '?z) => ?z (instantiate '(?x ?y ?z) s2) => (apple (banana cherry) ?z) (define u1 (unit-sub '?z 'peach)) (instantiate '(?x ?y ?z) u1) => (?x ?y peach) (define u2 (compose-subs s2 u1)) (instantiate '(?x ?y ?z) u2) => (apple (banana cherry) peach)
Here is the code for a unification pattern-matcher. Given two patterns p1 and p2, (unify-patterns p1 p2) returns a unifying substitution s such that (instantiate p1 s) and (instantiate p2 s) are equal, or else #f if no such unifier exists. Many unifying substitutions may be possible, but unify-patterns will always return the most general one. For example:
(define s (unify-patterns '(and ?first . ?rest) '(and a b c d))) (s '?first) => a (s '?rest) => (b c d) (instantiate '(if ?first (and . ?rest) false) s) => (if a (and b c d) false) (unify-patterns '(and) '(and a b c d)) => #f
Complete the code for the pattern-matcher by defining the functions empty-sub, extend-sub, unit-sub, and compose-subs, using a functional representation for substitutions. Test the unifier on all of the above examples to make sure it works.
We will use the pattern-matcher to add support for user-defined macros to our language. Currently, all of our macros are implemented as macro transformer functions stored in the macro environment (see the parser code). Let's generalize this so that in addition to transformer functions, we can store collections of patterns in the macro environment that specify how certain expressions are to be expanded. For example, the following rules specify how to expand and expressions:
(and) => true (and ?first . ?rest) => (if ?first (and . ?rest) false)
We will store the above patterns in the macro environment as a list of macro-clauses bound to the symbol and. The general form of such a list will be:
((left-pattern1 right-pattern1) (left-pattern2 right-pattern2) ... (left-patternN right-patternN))
Write the function process-macro-clauses, which takes a list of clauses of the above form and a concrete syntax expression datum, and goes through the clauses in order, matching datum against each left-pattern. If a matching clause is found, the corresponding right-pattern is instantiated and returned. If no matching clause is found, an error should be reported. For example:
(process-macro-clauses
'(((and) true)
((and ?first . ?rest) (if ?first (and . ?rest) false)))
'(and a b c d))
=> (if a (and b c d) false)
Next, change the definition of expand-once so that it calls process-macro-clauses if the result of looking up the macro keyword in the macro environment is a list instead of a transformer function.
Next, add support to your parser and interpreter for define-syntax, which has the following form:
(define-syntax macro-name macro-clause1 macro-clause2 ... macro-clauseN)
where each macro-clause is of the form (left-pattern right-pattern). A define-syntax expression adds the clauses to the macro environment as a list bound to the specified macro-name symbol. For example, we could define the and macro at the interpreter prompt as follows:
==> (define-syntax and
((and) true)
((and ?first . ?rest) (if ?first (and . ?rest) false)))
==> (and (print 1) (print 2))
1
2
#t
==>
Add define-syntax macro definitions for or, cond, let*, and lambda to the file macros.ploy. Let* and lambda should allow multiple bodies, and cond should allow multiple right-hand side expressions, as well as else clauses. Examples:
Expression Expansion (or) false (or a b c d) (if a true (or b c d)) (cond) true (cond (a b c) (d e) (else f)) (if a (begin b c) (cond (d e) (else f))) (let* ((a 1) (b 2) (c 3)) d) (let ((a 1)) (let* ((b 2) (c 3)) d)) (let* () a b c) (begin a b c) (lambda (x y) a b c) (fun (x y) -> (begin a b c))
Study the definition of the Ploy function filter-map in macros.ploy. Using filter-map, write a define-syntax macro definition for collect expressions. Examples:
==> (load "macros.ploy") ok ==> (collect (n * n) for n in (list 1 2 3 4 5)) (1 4 9 16 25) ==> (collect (n * n) for n in (list 1 2 3 4 5) if (n > 3)) (16 25)
Define-syntax is very powerful, especially in conjunction with lexical scope. Suppose we would like a version of for that makes it easy to iterate through the elements of an N-dimensional matrix by name and coordinates. For example, if matrix2D is a 4 × 2 matrix represented as a list of rows (see macros.ploy), it would be nice to be able to do something like this:
==> (for value at (row col) in matrix2D do (print (list value (list row col)))) (10 (0 0)) (20 (0 1)) (30 (1 0)) (40 (1 1)) (50 (2 0)) (60 (2 1)) (70 (3 0)) (80 (3 1)) #t
Here value gets bound to each matrix element in turn, and row and col get bound to the element's row and column coordinates. Likewise for a 3-dimensional matrix:
==> (for value at (i j k) in matrix3D do (print (list value (list i j k)))) (10 (0 0 0)) (20 (0 0 1)) (30 (0 0 2)) ... (220 (3 1 0)) (230 (3 1 1)) (240 (3 1 2)) #t
Using the expansion rules below as a guide, write a define-syntax macro definition for this type of for expression. You'll need to define the auxiliary Ploy function iterate, which applies a function to each successive element and index position of a list. Test your code on the example matrices in macros.ploy.
(for x at (i) in exp do body) => (iterate 0 exp (fun (x i) -> body))
(for x at (i j ...) in exp do body) => (for x at (i) in exp do
(for x at (j ...) in x do body))
Name your files
and submit them using /common/cs/submit/cs131-submit.
If you have questions about anything, just ask!