home—lectures—recipe—exams—hws—D2L—breeze (snow day)
T6: environments
extra credit
Due Dec.13 (Thu) 17:00
Submit:
T6.rkt and T6-test.rkt (or, T6-java.jar) on D2L,
and hardcopy with the changed code from T4 (tagged ;>>>T5 and ;>>>T6),
under Dr. Barland's door.
Extra Credit:
I'll take your percentage score on this assignment, and replace your lowest homework-score.
We continue to build on
the T language implementation from previous homeworks
(T2 sol'n posted;
T4 sol'n discussed on Monday and full source by Mon 17:00.
Note that T5 can be based off of the T2 solution for full credit).
You may implement this homework in either Java or Racket (or another language, if you clear it with me).
Label each section of lines you change with a comment “;>>>T5”.
You don't need to turn in any hardcopy of unchanged-code
(but do submit a fully-working copy in the drop-box, including all necessary files).
-
T5 (25pts;
This problem and the next are really the crux of the project.)
Deferred evaluation:
T5 doesn't add any new syntax,
but it is a different evaluation model which
will give us more expressive semantics.
There are two problems
with the substitution approach used in T2–T4:
we fundamentaly can't create recursive functions,
and it's hopeless for ever assigning to variables.
We solve these problems with deferred substitution:
-
When interpreting a program,
eval will take two arguments:
the program to interpret, and a set of (pre)existing bindings.
A binding is just an Id and its associated value;
a set of bindings (an environment)
might be implemented with an
association
list
or a java.util.Map<IdExpr,ValExpr>.
-
Upon encountering an Id, we just look up its value
in our list of bindings.
(Recall that in T2, eval never actually
reached an Id;
in T5 it now does.)
-
In this approach, eval'ing function-application and LetExprs
no longer do any substitution —
instead,
each introduce (exactly one) new binding
and proceed recursively.
-
You should not need to be doing any parse-tree-substitutions any more.
Your test cases should include
a recursive function,
as well as the example below.
Also, since eval now takes an extra argument, that suggests three to four check-expects
with various environments (lists of bindings):
-
an empty environment;
-
an environment with no necessary bindings;
-
an environment where some of the bindings are needed;
-
an environment where some of the bindings will get shadowed in the expression.
Re-naming 'eval':
Uh-oh, it'd be a pain to have to go and adapt all our existing test-cases for eval,
to take an extra argument.
I would advise something like:
search-replace all occurrences of eval in your tests to
be instead calling “eval-helper”.
Make that a function which simply calls eval with an empty-environment.
Then, go change eval to have a second input,
and add some two-argument test-cases as just mentioned.
A step sideways:
This algorithm as described lets us add recursive functions,
but it also doesn't handle some expressions that T4 did!
For example,
so make-adder be all func m -> func n -> #n boii m#
in call call make-adder(3)(4)
gives an error "unbound identifier: m" if no substitution has been done.
The problem will be fixed in T6:
calling call make-adder(3)
returns a function whose body still includes m and n,
but lacks the fact that we'd like it's m to be bound to 3.
One approach might be to have eval return both a value and a
set of bindings to use that value with.
T6 will take a slightly different approach,
storing the necessary bindings inside the function-representation.)
Note that this gives us dynamic scoping (which we'll mention in class):
so m be all 100
in so addM be all func x -> #x boii m#
in #so m be all 5 in call addM(3)
boii
so m be all 4 in call addM(3)#
|
evaluates to 15, not 206 as we might prefer.
-
(25pts total) T6: Implement static scope (closures).
(10pts)
Modify your function-structures so that
they include one extra piece of information:
the bindings in effect when the function was declared.
This is the function's closure.
Be sure to make a careful suite of test-cases,
to test for various ways of capturing bindings in different closures.
(For example, consider the
lecture on ways of using
let* to effectively implement objects, classes, and inheritance.)
- (5pts)
When evaluating a function-application, use the environment in effect
back when that function was declared, for its free variables.
-
You should not be doing any substitution.
To think about:
Hmm, when we first parse our expression, we'll
create function-expressions,
but (since we're not eval'ing) we don't have any bindings
right then.
So, initially create it with an dummy environment (a sentinel value like #f).
Only later, when we eval a function,
will we actually know about any bindings
(since that call to eval was given a list of bindings)….
subtlety:
This means that a function won't quite evaluate to itself anymore —
it'll evaluate to a struct that has the same parameter and body as the
original (parsed) structure,
but a fully fleshed-out, non-dummy closure.
(10pts)
Note that getting recursive functions to work is a bit tricky:
their environment (closure) needs to include its own name!
That is, we'll have eventually end up
with a function-struct whose closure-field is a list containing the function-struct.
That's not a problem in racket, no more than it is in Java -- racket struct values
are actually references-to-structs, just like in Java.
However, it will require mutation (read on).
The tricky bit is that when
when you're evaling a func-expr
you don't yet have its associated name, hmmm.
So after the
let-statement has finished evaling its value (which turns
out to be a function, including its closure),
then
you'll want to further
reach in and modify that closure to include
one additional ID/value pair.
You can, if you like, use the struct-setter (something like “set-func-closure!”);
see mutation in racket
(it's not necessary to use mutation, though).
Copy your T0-T4 file/project to a new T5.
You shouldn't need any additional test cases for T6;
the tests for T0-T5 should suffice,
although one or two T5 examples depending on
dynamic binding should now have
a new expected-result.
-
Further extra-credit options (of varying difficulty):
-
Add comments to your language;
Make sure comments nest.
It's up to you whether or not you store comments in the
internal representation, or discard them entirely.
You might want modify your grammar,
or consider a multi-phase approach to parsing.
-
Re-write the code for evaluating let
so that it simply transforms it into a function-application, and evaluates that.
-
Generalize functions to multiple arity,
and/or
generalize let so that it takes any
number of id/value pairs.
(Really this would be like scheme's
letrec,
since T6 allows recursion.)
-
If you want, modify the LetExpr syntax:
instead of
so id be all Expr in Expr,
you can use
Id = Expr ; Expr ; .
(Note that this still represent declaring a new variable,
not mutating an existing one.)
Your programs now look like procedural programs.
Note that parsing is more difficult: after reading an Id,
you have to check for whether it's followed by = or not.
You should satisfy yourself that this grammar not ambiguous.)
-
Add mutation (i.e. assigning to Ids):
Id ← Expr;.
See mutation in racket below.
-
Once we have assignment, add the equivalent of scheme's begin.
(You might use “{” and “}” to delimit
such a “block” of statements;
you now have implemented all the procedural concepts of
a Java or Python interpreter, including first-class functions!
And as seen in lecture,
you also could write
superficial transformations to get most of an object system as well.)
Mutation in Racket
If you want to use mutation in your racket-implementation,
use Advanced Student language.
This language level includes set! (to assign to variables),
and
set-struct-field!
(to assign to struct fields).
Note that these two actions are very different, which is why racket gives
them separate names; in Java assigning-to-field and
assigning-to-local-variable can look identical (syntactically),
despite giving rise to very different behavior.
Since the mutators return #void, and we want to return
a (useful) value from every expression,
we will use mutation inside a
begin expression:
(define times-called 0)
(define (triplify-and-print n)
(begin (printf "We use `begin` to call a function for a side-effect *and* return a value too.\n")
(set! times-called (add1 times-called))
(printf "This function has been called ~a time~a.\n"
times-called
(if (= times-called 1) "" "s"))
(* 3 n)))
(triplify-and-print 5)
(triplify-and-print 2)
|
Btw, it's worth noting that in full-racket, begin is implicit
in almost all forms (e.g. function-bodies and cond-branches).
home—lectures—recipe—exams—hws—D2L—breeze (snow day)
This page licensed CC-BY 4.0 Ian Barland Page last generated | Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu |
|