Grammar for datatype tools

The form define-datatype is an example of a domain-specific language.

A domain-specific language is a small language for describing a single task among a small, well-defined set of tasks. In this case, the task was defining a recursive data type. Such a language may lie inside a general-purpose language, as define-datatype does, or it may be a standalone language with its own set of tools. In general, one constructs such a language by identifying the possible variations in the set of tasks, and then designing a language that describes those variations. This is often a very useful strategy.

(define-datatype type-name type-predicate-name
	{(variant-name {(field-name predicate)}*)}+)

(cases type-name expression
	{(variant-name ({field-name}*) consequent)}*
	(else default))

Lambda Calculus Representation

Defining the Datatype

(define-datatype lc-exp lc-exp? 
	(var-exp
     (var identifier?))
  (lambda-exp
     (bound-var identifier?)
     (body lc-exp?))
  (app-exp
     (rator lc-exp?)
     (rand lc-exp?)))

occurs-free?

;; occurs-free? : Sym × LcExp → Bool 
(define occurs-free?
	(lambda (search-var exp) 
		(cases lc-exp exp
			(var-exp (var) (eqv? var search-var)) 
			(lambda-exp (bound-var body)
				(and (not (eqv? search-var bound-var)) (occurs-free? search-var body)))
      (app-exp (rator rand)
        (or (occurs-free? search-var rator) 
						(occurs-free? search-var rand))))))

Symbol List Representation

Grammar

S-list ::= ({S-exp}*) S-exp ::= Symbol | S-list

Representation

Separation for each non-terminal node in grammar:

(define-datatype s-list s-list? 
		(empty-s-list) 
		(non-empty-s-list
	     (first s-exp?)
	     (rest s-list?)))

(define-datatype s-exp s-exp? 
	(symbol-s-exp
      (sym symbol?))
    (s-list-s-exp
      (slst s-list?)))

Alternative Representation

Using list-of and scheme lists:

(define-datatype s-list s-list? 
		(an-s-list
	      (sexps (list-of s-exp?))))