Don't panic. The length of code you will
write for this assignment is probably much less than the
length of the assignment itself.
Consider the language AFunExp
, which is
AExp
extended with division and closures.
AFunExp
adds the following two kinds of concrete
syntax terms:
<L> := ...
| (<L> / <L>)
| (fun (<id>) <L>)
| <id>
| (<L> (<L>))
where
/
implements division,
fun
evaluates to a function (closure), and the
id
s
are represented by symbols. Your parser must map this syntax
to values of the following datatype:
(define-datatype AFunExp AFunExp?
[numE (n number?)]
[addE (lhs AFunExp?) (rhs AFunExp?)]
[multE (lhs AFunExp?) (rhs AFunExp?)]
[divE (lhs AFunExp?) (rhs AFunExp?)]
[funE (var symbol?) (body AFunExp?)]
[varE (v symbol?)]
[appE (fun AFunExp?) (arg AFunExp?)])
Your interpreters do not need to deal with type
errors (such as using a number instead of a closure in the
function position of an application, or division by zero).
You can leave the error handling and reporting to Scheme.
Exercises
- Preliminaries:
- Implement the procedure
closed?
:
closed? : AFunExp -> boolean
closed?
accepts a parsed AFunExp?
value. It returns true when there are no free
(unbound) variables in the expression, and false
otherwise. Tip: Use an environment!
- Using the external and internal representations specified
above, extend an interpreter for
AExp
with the
division operation. (Don't implement funE
,
varE
or appE
yet.) Your
interpreter can return numE
values.
- Using the definition of
AFunExp
above,
provide a program that will produce different results under
the eager and lazy disciplines. (You may use let
to simplify writing the expression.) Also provide the
computation steps and value (if any) under each discipline.
The two computations may differ in any way, so long as if they
both yield a value, the value must not be the same number or a
closure that produces the same value for all values it is
applied to. You can assume that evaluators for both
disciplines return values, not compuations. Tip:
There are indeed concise, two-line solutions to this problem,
so think simple.
- For the following problems, your interpreters do not need
to handle programs with free variables. For each problem:
- provide an interface procedure named
main
that accepts a source program (using
the external representation) and returns
- the boolean value
false
if the
program is not closed;
- the symbol
'<closure>
if the
program evaluates to a closure;
- a Scheme number if the program evaluates to a
number.
- use an environment in your interpreter.
Here are the problems:
- Implement (via an interpreter)
AFunExp
with the eager
semantics using a datatype to represent AFunExp
closures.
- Implement
AFunExp
with the eager
semantics using Scheme's closures (lambda
) to
represent AFunExp
closures and Scheme's
procedure application to represent AFunExp
application.
- Consider
AFunExp
with the lazy
semantics using a datatype to represent AFunExp
closures. If you believe this is difficult or impossible to
implement, state and justify your claim; otherwise, provide
an implementation.
- Consider
AFunExp
with the lazy
semantics using Scheme's closures to represent
AFunExp
closures. If you believe this is
difficult or impossible to implement, state and justify your
claim; otherwise, provide an implementation.
Turn in all the code needed to run programs in
AFunExp
(parser, interpreter, libraries, etc).
Your code is due by 11am on 2000-09-22. Email the code to the
TA before, and submit it in print at, the start of class.