Help for 1.31

Here are some hints on 1.31:

Writing a function that takes the expression syntax apart is easier if you write some auxiliary functions to recognize if expressions, lambda expressions and to take them apart. Here is the syntax:


<exp> ::= <varref>
         | (if <exp> <exp> <exp>)
         | (lambda ({<var>}*) <exp>)
         | ({<exp>}+)

An example of how to write Scheme code from a BNF is here

Here are the auxiliary functions for that syntax:

    ;;; syntax functions for if

    (define is-if? (lambda (lst) (eq? (car lst) 'if)))

    (define if-test  (lambda (lst) (cadr lst)))

    (define if-true  (lambda (lst) (caddr lst)))

    (define if-else  (lambda (lst) (cadddr lst)))

    ;;; test if syntax functions

    (is-if? '(if test true else))

    (if-test '(if test true else))

    (if-true '(if test true else))

    (if-else '(if test true else))

    ;;; syntax function for lambda

    (define is-lambda? (lambda (lst) (eq? (car lst) 'lambda)))

    (define lambda-vars  (lambda (lst) (cadr lst)))

    (define lambda-body  (lambda (lst) (caddr lst)))

    ;;; test lambda syntax functions

    (is-lambda? '(lambda (vars) body))

    (lambda-vars '(lambda  (vars) body))

    (lambda-body '(lambda (vars) body))

Use a list of lists to keep track of the bound variables at each level. That is, each time you enter a lambda expression, cons the variables onto the front of your list of bound variables. Now, when you get to a symbol, the index of the first list with that symbol in it is the depth and the index of that symbol in the list is the position. Write a function called mk-var-ref that works like this:
```
    (mk-var-ref 'b '((a b) () (c d e) (a b f))) ==> (b : 0 1)
    (mk-var-ref 'c '((a b) () (c d e) (a b f))) ==> (c : 2 0)
    (mk-var-ref 'f '((a b) () (c d e) (a b f))) ==> (f : 3 2)
    (mk-var-ref 'z '((a b) () (c d e) (a b f))) ==> (z free)
```

Write an auxiliary function, lexical-address-aux that takes an expression and a list of bound variables (which will change as it executes) that does most of the work. Here's a skeleton:

(define lexical-address-aux
  (lambda (exp env)
    (cond ((null? exp)      ?)
          ((symbol? exp)    ?)
          ((is-if? exp)     ?)
          ((is-lambda? exp) ?)
          (else             ?))))

Define lexical-address in terms of lexical-address-aux. What should the initial list of bound variables contain?

If there are problems with this page, please send mail to <cs330ta@cs.byu.edu>
If you have a comment about the class, please send mail to <seamons@cs.byu.edu>

© 1994-2009, Phillip J. Windley and Bryan S. Morse. All rights reserved.
Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy.

Last updated at 3:24 pm on Friday, January 31, 2003.