Project 2: Algol-like syntax for Scheme

C431: Fall 1994

Due dates

Description

Define a Scheme procedure named bundy that takes a target port (defined in Project 1), reads a Bundy program, defined below, and returns the equivalent Scheme program defined by the Bundy-to-Scheme translation below. Use your lexical analyzer from Project 1 and an LL(k) recursive-descent parser.

Submit at least 100 lines total of test code in two email messages to sakumar@copper with subjects accept2 and reject2, including cases that the reader should accept and reject, respectively. Submit your project by email to sakumar@copper with subject code2.

Bundy is an alternative syntax for Scheme. It roughly follows the Algol syntactic tradition, which includes better known grammars such as those of Pascal and Ada.

Non-terminals are indicated by italics. A number is as defined in Project 1. String, character, boolean, and variable are as defined in the R4RS, except that the syntactic keywords (which cannot be variables) are begin, end, define, lambda, let, in, cond, =>, else, <-, :=, ?, hd, and tl. As in Scheme, whitespace must separate tokens that might be confused for a longer token if concatinated. Thus x?3 is a variable, while x ? 3 is an "eq?" expression.

Productions

The empty derivation symbol is "#", the production symbol is "-->", and alternation is indicated by "|".

program --> begin definition-list , expression end

definition-list --> definition | definition , definition-list

definition --> define variable expression

expression --> lambda ( formals ) expression

expression --> let variable bindings in expression

expression --> let bindings in expression

expression --> cond cond-clause-list

expression --> variable := expression

expression --> expression ? expression

expression --> expression . expression

expression --> ? expression

expression --> expression hd

expression --> expression tl

expression --> expression ( actuals )

expression --> ( expression-list )

expression --> variable

expression --> literal

formals --> # | variable-list

variable-list --> variable | variable , variable-list

bindings --> # | binding-list

binding-list --> binding | binding , binding-list

binding --> variable <- expression

cond-clause-list --> cond-clause | cond-clause else cond-clause-list

cond-clasue --> expression => expression

actuals --> # | expression-list

expression-list --> expression | expression , expression-list

literal --> boolean | number | character | string

Precedence and associativity

The precedence of the operators lambda, let, cond, :=, binary ?, ., unary ?, hd, tl, and application are given by their position in the list of productions: each takes precidence over the operators before it in the list, except that lambda, let (both forms), and cond have the same precedence.

The infix operators := and . are right-associateive, while the infix operaators ? and application are left-associative. An else clause is associated with the nearest possible cond expression.

Translation of Bundy to Scheme

The syntax-directed transformation function T is defined by the rewrite rules below. Meta-brackets "[[...]]" surround a Bundy syntactic pattern. Elipsis "..." indicates a sequence of zero or more elements, while ".n." indicates a sequence of n elements.

T[[begin e_1 , .1. , e_n end]] ==> (begin T[[e_1]] .1. T[[e_n]] )

T[[define id e]] ==> (define id T[[e]] )

T[[lambda ( id_1 , ... , id_n) e]] ==> (lambda ( id_1 ... id_n ) T[[e]] )

T[[let id id_1<- , ... , id_n<-e_n in e]] ==> (let id (( id_1 T[[e_1]] ) ... ( id_n T[[e_n]] )) T[[e]] )

T[[let id_1<- , ... , id_n<-e_n in e]] ==> (let (( id_1 T[[e_1]] ) ... ( id_n T[[e_n]] )) T[[e]] )

T[[cond p_1 => e_1 else .1. else p_n => e_n]] ==> (cond ( T[[p_1]] T[[e_1]] ) .1. ( T[[p_n]] T[[e_n]] ))

T[[id := e]] ==> (begin (set! id T[[e]] ) id )

T[[e_1 ? e_2]] ==> (eq? T[[e_1]] T[[e_2]] )

T[[e_1 . e_2]] ==> (cons T[[e_1]] T[[e_2]] )

T[[? e]] ==> (null? T[[e]] )

T[[e hd]] ==> (car T[[e]] )

T[[e tl]] ==> (cdr T[[e]] )

T[[e_0 ( e_1 , ... , e_n )]] ==> ( T[[e_0]] T[[e_1]] ... T[[e_n]] )

T[[( e )]] ==> T[[e]]

T[[( e_1 , .2. , e_n )]] ==> (begin T[[e_1]] .2. T[[e_n]] )

T[[variable]] ==> variable

T[[literal]] ==> literal

Example

The Bundy program 
begin
  define reverse
    lambda (x)
      reverse-help(x , list()) ,
  define reverse-help
    lambda (x , a)
      cond
        ? x => a
      else
        #t => reverse-ehlp(x tl , x hd . a) ,
  define ans 1 . 2 . 3 . list() ,
  ans := reverse(ans)
end

is equivalent to the Scheme program 

(begin
  (define reverse
    (lambda (x)
      (reverse-help x (list))))
  (define reverse-help
    (lambda (x a)
      (cons
	((null? x) a)
	(#t (reverse-help (cdr x)
	      (cons (car x) a))))))
  (define ans
    (cons 1 (cons 2 (cons 3 (list)))))
  (begin (set! ans (reverse ans)) ans))

Policies

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

chaynes@indiana.edu