Syntactic Abstraction

Definition

Binding forms

• Local binding: let. Equivalence with lambda-application.
• Advantages of the new syntactic form.
• Other binding forms: let*, letrec.

Logical Connectives

• Must be defined as special forms to allow shortcut behavior.
• Definition for or, and using if.

Branching forms

• Definition for cond, case in terms of if.

Records and Unions

• Definition of records using arrays - use define-datatype.
• Variant records and unions.
• Definition of the cases special form (both branching and binding in one convenient syntax).

Abstract Syntax

;; BNF
<exp> ::= <number>
        | <varref>
        | (lambda (<var>) <exp>)
        | (<exp> <exp>)

;; Define abstract syntax
(define-datatype exp exp?
  (lit (datum number?))
  (varref (var symbol?))
  (lambda-exp
    (formal symbol?)
    (body exp?))
  (app-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))))
               (else 
                (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

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

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.

% (define dxy-ff
    (extend-ff 'd 6
      (extend-ff 'x 7
        (extend-ff 'y 8
          (create-empty-ff)))))
% (apply-ff dxy-ff 'x) - 7

Procedural Representation

(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)
        val
        (apply-ff ff symbol))))

(define (apply-ff ff symbol)
  (ff symbol))

Record Representation

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?
  (empty-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)
        val
        (apply-ff next-ff symbol)))))

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