Advanced Methods in Programming Languages (201-2-4411-01)
Notes 3 - Michael Elhadad
previous class main page next class

Syntactic Abstraction


Forms which are precisely equivalent to existing forms: syntactic abstraction.

Binding forms

Logical Connectives

Branching forms

Records and Unions

Abstract Syntax

Support for syntax-directed programs (interpreters, compilers, program transformers). Abstract syntax: annotated data structure that can be viewed as the result of parsing an expression using a BNF. The parse-tree is encoded as a structure of records. Can be extended with lists to support Kleene-star directly. Define two abstract operations: parse and unparse to translate to/from abstract syntax and concrete syntax of expression. You can use the sllgen Scheme package to parse from strings given a concrete syntax grammar. (Sllgen provides the same services as Lex and Yacc in C.)
;; BNF
<exp> ::= <number>
        | <varref>
        | (lambda (<var>) <exp>)
        | (<exp> <exp>)

;; Define abstract syntax
(define-datatype exp exp?
  (lit (datum number?))
  (varref (var symbol?))
    (formal symbol?)
    (body exp?))
    (rator exp?)
    (rand  exp?)))
;; Parse/Unparse

(define (parse datum)
  (cond ((number? datum) (make-lit datum))
        ((symbol? datum) (make-varref datum))
        ((pair? datum)
         (cond ((eq? (car datum) 'lambda)
                (lambda-exp (caadr datum) (parse (caddr datum))))
                (app-exp (parse (car datum)) (parse (cadr datum))))))
        (else (error "parse: Invalid concrete syntax" datum))))

(define (unparse e)
  (cases e exp
    (lit (datum) datum)
    (varref (var) var)
    (lambda-exp (formal body) (list 'lambda (list formal) (unparse body)))
    (app-exp (rator rand) (list (unparse rator) (unparse rand)))))

From Procedural to Data Structure Representation

When data abstraction is used, programs have the property of representation independence: that is, you can change the representation of the data structure, the program using the ADT will not be changed and will continue working.

We show here how to use the power of Scheme's first-class citizen functions to prepare a high-level representation of a data type. We then show how to convert this high-level semantic representation into a record-based representation which is generally more efficient and can be encoded in low-level languages (assembly).

The Finite Function ADT
A finite function associates a value with each element of a finite set of symbols. Finite functions are central to interpreters: an environment is a finite function; a symbol table is a finite function.

The following interface defines the Finite Function (FF) ADT:

  1. (create-empty-ff) returns the empty finite function.
  2. (extend-ff symbol value ff) returns a new finite function that preserves the associations of ff and also associates symbol with value. Any association with symbol that might already exist in ff is ignored by the new finite function.
  3. (apply-ff ff symbol) returns the value associated with symbol by ff. An error is triggered if no value is associated with symbol by ff.
Using this ADT, the Finite Function {(d, 6), (x, 7), (y, 8)} can be build and used as follows:
% (define dxy-ff
    (extend-ff 'd 6
      (extend-ff 'x 7
        (extend-ff 'y 8
% (apply-ff dxy-ff 'x) - 7
Procedural Representation
A finite function can be represented by a Scheme procedure that takes a symbol and returns the associated value. The ADT can then be implemented as follows:
(define (create-empty-ff)
  (lambda (symbol)
    (error "Empty ff: no association for symbol" symbol)))

(define (extend-ff sym val ff)
  (lambda (symbol)
    (if (eq? symbol sym)
        (apply-ff ff symbol))))

(define (apply-ff ff symbol)
  (ff symbol))
Record Representation
The procedural representation of the FF ADT requires first-class procedures (extend-ff returns a newly created procedure and receives a procedure as parameter).

We can systematically transform a procedural representation into a record-based representation by noting which information is contained in each of the finite function procedures.

There are only 2 kinds of finite functions: the ones returned by creating an empty finite function (returned by create-empty-ff); and the ones returned by extend-ff. When a FF is applied, the specification of what to do is given by the body of these functions. The body of these functions does not change -- only the parameters do.

So the key of the transformation from procedural to record-based representation is to transfer the complexity from the object to the one using the object -- in this case, from the constructors (create-empty-ff and extend-ff) to the accessor (apply-ff).

The new record-based representation follows:

(define-datatype ff ff?
  (extended-ff (sym symbol?) (val number?) (next-ff ff?)))
(define (create-empty-ff) (empty-ff))
(define (extend-ff sym val f) (extended-ff sym val f))

(define (apply-ff f symbol)
  (cases ff f
    (empty-ff () (error "Empty ff: no association for symbol" symbol))
    (extended-ff (sym val next-ff)
      (if (eq? sym symbol)
        (apply-ff next-ff symbol)))))
NOTE: The consequent of the clauses are EXACTLY the same as the bodies of the corresponding constructors in the procedural representation.

This transformation is completely general and we will reuse it in the continuation.

Last modified 2 Mar 2003 Michael Elhadad