let
. Equivalence with
lambda-application.
let*, letrec
.
or, and
using if
.
cond, case
in terms of if
.
define-datatype
.
cases
special form (both
branching and binding in one convenient syntax).
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?)) (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)))))
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 following interface defines the Finite Function (FF) ADT:
% (define dxy-ff (extend-ff 'd 6 (extend-ff 'x 7 (extend-ff 'y 8 (create-empty-ff))))) % (apply-ff dxy-ff 'x) - 7
(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))
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)))))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.