C431 Project 3 -- Intermediate Code

C431: Fall 1994

Due Dates

Description

Define a procedure opt-form, which takes a datum representing an expression in core form and returns an expression in optimization form, and a procedure code-gen-form, which takes an expression in optimization form and returns an expression in code-generation form. Core form, optimization form, and code-generation form are defined below and are evaluable as Scheme expressions and the transformations performed by the procedures opt-form and code-gen-form should be value-preserving. In a concession to brevity, evaluation of code-generation form assumes vr is bound to the Scheme procedure vector-ref.

Use of the syntactic extension form-case is suggested; see the file form-case.ss. Submit by email to sakumar@copper at least 100 lines of core-form code for use as test data in a message with subject accept3, at least 20 lines of core-form code that parse as a datum but are still syntactically ill-formed for use as test data in a message with subject reject3, and your project solution in a message with subject code3.

Core form

Let core form be the subset of Scheme defined by restricting references to top-level (global) variables to the operator position of procedure calls and amending the R4RS syntax of Scheme with the following rules, which effectively omit definitions, "rest" variables, and all derived expressions.

program --> expression

expression --> variable | literal | procedure-call | lambda-expression | conditional | assignment

body --> expression+

formals --> (variable*)

alternate --> expression

Core form represents the result of expanding all syntactic extensions and derived forms. In a non-interactive implementation, the top-level can be eliminated via straightforward syntactic expansions. Besides being non-interactive, the only concession to simplicity is the omission of "rest" arguments.

Optimization form

Let optimization form be defined by the following productions. Syntactic categories for which productions are omitted are as in the core-form grammar.

expression --> reference | quotation | closure-call | inline-call | lambda-expression | conditional | (begin expression expression)

reference --> (begin variable)

closure-call --> (expression+)

inline-call --> (variable expression*)

lambda-expression --> (lambda formals expression)

Transform procedure calls into inline calls if the operator is a top-level reference other than string->symbol, and into a closure call otherwise. The output of opt-form should not share any pairs with its input. This allows transformations performed by code-gen-form and many optimization steps to be performed in large part via side-effects to the structure returned by opt-form.

Optimization form is suitable for the implementation of a wide variety of optimizations as transducers from this form to itself.

Code-generation form

Let code-generation form be defined by modification of the optimization form grammar via redefinition of the syntactic categories defined by the following productions as the productions indicate.

lambda-expression --> (let ((free (vector reference*))) (lambda (bound) (quote formals) expression)

closure-call --> (expression (vector expression*))

reference --> (vr reference-type number)

reference-type --> bound | free

global-program --> expression | (global-lambda (vector expression*))

global-lambda --> (let ((free (vector (vr bound 0)))) (lambda (bound) (quote formals) (set! global bound) expression))

program --> global-program | (program-lambda (vector expression))

program-lambda -->
(let ((free (vector))) (lambda (bound) (quote (string->symbol)) global-program))

quotation --> (quote immediate) | (vr global number)

immediate --> boolean | number | character | ()

Global-program should be an expression if all quotations in expression are immediate. Program should be a global-program if it contains no symbolic literals. Otherwise, the expression subform of program should be an expansion of the origcode defined in the file string-symbol.ss produced using Chez Scheme's expand procedure composed with opt-form and code-gen-form.

Code-generation form is designed to make code generation relatively straightforward.

Policies

See the courese description for policies common to the projects of this course.

chaynes@indiana.edu