S-expressions, Patterns, and Abstract Syntax

Matthias Felleisen

A pattern is an S-expression that contains pattern variables. Here is a data definition:

Pattern is one of: 
 Number                    % a number 
 Symbol                    % a symbol 
 empty                     % the empty list
 (list '? Name)            % a pattern variable 
 (cons Pattern Pattern)    % a pair 

Name is 
 Symbol

A pattern is matched against an S-expression as follows:

if the pattern is a number, the only matching S-expression is the same number;
if the pattern is a symbol, the only matching S-expression is the same symbol;
if the pattern is empty, the only matching S-expression is empty;
if the pattern is a pair, a pair matches if its components match against the corresponding components of the pattern;
if the pattern is a variable, any S-expression matches.

When a pattern variable matches some S-expression, we can form an association between the name and the S-expression. Thus, matching a pattern against an S-expression produces a list of associations or false, if the pattern does not match the S-expression.

Examples:

Pattern S-expression Match

(list '? 'x) (cons 1 2) x = (cons 1 2)

(cons (list '? 'x) empty) (cons 'hello empty) x = 'hello

(cons (list '? 'x) (list '? 'y)) (cons 'hello 'world) x = 'hello, y = 'world

(cons (list '? 'x) (cons 1 empty)) (cons 'hello (cons 2 empty)) #f

(cons (list '? 'x) (list '? 'y)) (cons 'hello (cons 'world (cons 'bye empty))) x = 'hello, y = (cons 'world (cons 'bye empty))

Pattern	S-expression	Match
(list '? 'x)	(cons 1 2)	x = (cons 1 2)
(cons (list '? 'x) empty)	(cons 'hello empty)	x = 'hello
(cons (list '? 'x) (list '? 'y))	(cons 'hello 'world)	x = 'hello, y = 'world
(cons (list '? 'x) (cons 1 empty))	(cons 'hello (cons 2 empty))	#f
(cons (list '? 'x) (list '? 'y))	(cons 'hello (cons 'world (cons 'bye empty)))	x = 'hello, y = (cons 'world (cons 'bye empty))

As a test suite:

(equal? (match (cons 1 2) (list '? 'x)) (list (list 'x (cons 1 2)))) (equal? (match (cons 'hello empty) (cons (list '? 'x) empty)) (list (list 'x 'hello))) (equal? (match (cons 'hello 'world) (cons (list '? 'x) (list '? 'y))) (list (list 'x 'hello) (list 'y 'world))) (equal? (match (cons 'hello (cons 2 empty)) (cons (list '? 'x) (cons 1 empty))) #f) (equal? (match (cons 'hello (cons 'world (cons 'bye empty))) (cons (list '? 'x) (list '? 'y))) (list (list 'x 'hello) (list 'y (cons 'world (cons 'bye empty))))) (equal? (match S-expression Pattern) AssociationList or false)

Exercises:

Develop the function

#| ============================================================================
   collect-pv : Pattern -> (listof Symbol)
   to collect the names of the pattern variables in a pattern
|#

It traverses a pattern and produces a list of all the pattern variable names in the pattern.

Develop the function

#| ============================================================================
   subst : Pattern (listof (list Name S-exp)) -> S-exp 
   to substitute all pattern variables in p with the
   corresponding S-expression in al
|#
(define (subst p al) ...)

You may assume that all pattern variables in p are defined in al or, formally,

   (andmap (lambda (x) (memq x (map first al))) (collect-pv p))

Develop the function
```
#| ============================================================================
   my-match : S-exp Pattern -> (union (listof (list Name S-exp)) false)
   to match an S-expression against a Pattern 
   result: (equal? (subst p (my-match s p)) s)
|#   
```
The function attempts to match p against s. If it succeeds, it produces an association list with bindings for all the pattern variables. Even more precisely, the resulting association list suffices to reconstruct the original S-expression from the pattern:
```
   (equal? (subst p (my-match s p)) s)
```
If the matching process fails, the function produces false.

Develop the function

#| ============================================================================
   parse-lambda : S-exp -> A-exp 
   to recognize whether the given s is a Lambda expression, and if so, 
   to translate s into an A-exp
|#   
(define (parse-lambda s) ...)

where an A-exp is defined as follows:

#| ============================================================================
   A-exp is one of: 
    (make-var Symbol)
    (make-lam (listof Symbol) A-exp)
    (make-let Symbol A-exp A-exp)
    (make-app A-exp (listof A-exp))
    (format "ill-formed term: ~a" S-exp)
    (format "free variable: ~s" Symbol)
    
   A proper A-exp is an A-exp that does not contain a string.    
|#   
(define-struct var (name))
(define-struct lam (paras body))
(define-struct let (var lhs body))
(define-struct app (fun args))

The class of A-expressions capture the abstract syntax of a Lambda expression, which is a subclass of Scheme's class of S-expressions:

Short Hand	Long Hand
Lambda is one of: Symbol {lambda {Symbol ...} Lambda} {let {Symbol Lambda} Lambda} {Lambda Lambda ...}	Lambda is one of: Symbol (list 'lambda (listof Symbol) Lambda) (list 'let (list Symbol Lambda) Lambda) (cons Lambda (listof Lambda))

Short Hand

Long Hand

   Lambda is one of: 
      Symbol 
      {lambda {Symbol ...} Lambda}
      {let {Symbol Lambda} Lambda}
      {Lambda Lambda ...}

   Lambda is one of: 
      Symbol 
      (list 'lambda (listof Symbol) Lambda)
      (list 'let (list Symbol Lambda) Lambda)
      (cons Lambda (listof Lambda))

Recall that the notation X ... means a sequence of 0 or more items of kind X. Hence, the last clause in the definition of Lambda means one or more Lambda enclosed by "(" and ")".

Hint 1: Remember to write your examples with curlie syntax so that you can easily tell apart data from program:

(equal? (parse-lambda '{lambda {x} x}) ...)

Hint 2: Use my-match if you trust your solution. To do so effectively, you should know that cond supports the following variant:

(define (parse-lambda s)
  (cond
    [(symbol? s) ...]
    [(my-match s '(lambda () (? body)))
     =>
     (lambda (x)
       ... ; if the condition produces a non-false value, 
       ... ; the test succeeds and x stands for the value 
       ... ; of the (my-match ...) expression 
      )]

Develop the function
```
#| ============================================================================
   closed-lambda : A-exp -> Void
   assume: the input is a proper A-exp
   effect: to replace variable names with strings if they are free
|#
```
The function determines whether a variable occurrence is free. If so, the name of the var structure is replaced with (format "free variable: ~s" x) where x is the name of the variable. Both lambda and let bind variables in their bodies. No other construct binds.

The homework is due on Monday 15 October 2001 before class.

Expected size: 250 lines