home—lectures—recipe—exams—hws—D2L—zoom (snow day)
W6: environments
Due
May.02 (Sat) 23:59
Submit:
W6.rkt and W6-test.rkt (or, W6-java/*.java) on D2L
.
Include prolog-code in a block comment near the start of your file,
and (perhaps only)
the changed code from W4 (tagged “;>>>W5” and “;>>>W6”).
- Prolog lists
Write the following Prolog predicates.
Do not use append.
For full credit, give idiomatic Prolog
(no singleton variables, and no = on the right-hand-side).
-
last(List, Item),
which succeeds exactly when
Item is the last item in List.
This rule should fail if List is empty, of course.
(This happens to be the book’s Chpt.16, programming exercise #6.)
-
nextToLast(List, Item)
which succeeds exactly when
Item is the next-to-last item in List.
(This rule should fail if List has fewer than two items, of course.)
-
lastTwoReversed(List, ListOf2)
which succeeds exactly when
ListOf2 contains the last and the second-to-last item
of List
(in that order, and nothing else).
-
reverseLastTwo(List, NewList)
succeeds exactly when NewList
is exactly the same as List
except that the last two items have been reversed.
(This rule will fail if either input has fewer than two items.)
All of the predicates fail if the first argument is not a list.
Some examples (test cases) are provided, below.
Note that the Prolog standard library contains several list functions which you are NOT to use for this assignment
(e.g. append and reverse).
Also, for full credit, don’t merely reverse the input list and operate on that result.
Environments and Closures
We continue to build on
the V language implementation from previous homeworks
(W4 sol'n).
You may implement this homework in either Java or Racket (or another language, if you've cleared it with me).
Copy your W0-W4 file/project to a new W5.
Label each section of lines you change with a comment
“;>>>W5”
or
“;>>>W6”.
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).
Shortcomings of substitution
There are two problems
with the substitution approach used in W2–W4:
(i) we fundamentally can't create recursive functions,
and (ii) it’s hopeless should we want to add assigment to our language.
Less importantly, you might also have thought it's a bit inefficient (by a factor of two),
to do a substitution on an entire sub-tree, and then immediately re-walk through that same subtree
then eval it.
Can't we do those substitutions while we eval, “just in time”?
We solve these problems with deferred substitution:
Rather than substituting,
we’ll just remember what substitutions we want made,
and if we ever encounter an identifier then we look it
up in our set-of-deferred-substitutions — our environment.
So now we can
evaluate #y order-up 3} with an environment where y is bound to 7,
and also
evaluate #y order-up 3} with an environment where y is bound to 99.
-
W5 :
This problem and the next are really the crux of the project.)
Deferred evaluation:
W5 doesn't add any new syntax,
but it is a different evaluation model which
will give us more expressive semantics.
- When interpreting a program,
we'll use a new function
eval-with-env will take two arguments:
the program to interpret, and any set of (pre)existing bindings.
A binding is just an Id and its associated value;
an environment is a set of bindings.
task:
- Decide how you will represent a binding.
(Make an example-of-your-data, e.g. “the Id "x" bound to 17”.)
- Decide how you will represent an environment.
(Make an example-of-your-data, e.g. “an environment where x is bound to 17, and
y is bound to 99”.)
- In Java, the standard class
java.util.Map<IdExpr,ValExpr>
implements the Dictionary abstract-data-type.
In Racket, two contenders are
association
lists
and
immutable hash table
(here are examples of both;
hash-tables available to Student Languages via (require "student-extras.rkt")).
- To do this, we shall:
- re-name
the function eval
as eval-with-env, which takes an environment as a second input.
- Be sure you udpate all the recursive calls inside eval-with-env so that
they pass a second argument!
Then, go back and define eval as
a function which still takes just one input (an Expr),
and simply calls eval-with-env, passing it an empty-environment.
That is, eval-with-env is the helper-function which does all the heavy
lifting,
and eval is a light wrapper around eval-with-env.
This way, all your existing tests to eval can be unchanged,
but you can add some unit-tests for eval-with-env
to help figure out what that function needs to do with its environment.
- Upon encountering an Id, eval-with-env
will just look up its value
in our environment (list-of-bindings).
(Recall that in W2, eval never actually
reached an Id;
in W5 it now does.)
- In this approach, eval-with-env’ing FuncApplyExprs and LetExprs
no longer do any substitution —
instead,
each introduce (exactly one) new binding
and proceed recursively.
Your test cases should include
a recursive W5 function,
as well as the addM example below.
Here are just a few cases you might want to test:
- What does the W5 program #y order-up 3} evaluate to,
with the environment where x is bound to 5 and y is bound to 7?
- What does the W5 program #y order-up 3} evaluate to,
with the environment where x is bound to 5 and y is bound to 99?
- What does the W5 program sweet y mother of 5 pearl #y order-up 3} evaluate to,
with the environment where x is bound to 5 and y is bound to 7?
- What does the W5 program sweet y mother of #x barnacles! 2} pearl #y order-up 3} evaluate to,
with the environment where x is bound to 5 and y is bound to 7?
Discussing W5
A step sideways: This W5 algorithm has improved on W4: we can now hope to handle recursive functions.
But it’s also worse, because it now fails on some expressions that W4 got correct!
For example,
sweet make-adder mother of <^> m * |<^> n * #n order-up m}|
pearl aye aye 3 captain |aye aye 4 captain make-adder|
; racket equivalent to the above W5:
(let {[make-adder (lambda (m)
(lambda (n) (+ m n)))]}
((make-adder 4) 3)) |
gives an error unbound identifier: m
if no substitution has been done.
The problem is that, in W5,
calling aye aye 4 captain make-adder
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 an
environment to use that value with.
We’ll solve the problem in W6 with a slightly different approach,
storing the environment-to-use inside the function-representation.
Note that W5’s eval now gives us dynamic scoping:
sweet m
mother of 100
pearl sweet addM
mother of <^> x * #x order-up m}
pearl # sweet m mother of 5 pearl aye aye 3 captain addM
order-up
sweet m mother of 4 pearl aye aye 3 captain addM
}
; the racket equivalent of the above W5:
(let {[m 100]}
(let {[addM (lambda (x) (+ x m))]}
(+ (let {[m 5]} (addM 3))
(let {[m 4]} (addM 3))))) |
evaluates to 15=(3+5)+(3+4), not 206=(3+100)+(3+100) as we might expect (and, prefer).
In dynamic scope, the use of a free variable (here, m) will refer to its
most recent run-time definition!
If m is free within a function addM, you can't tell where its binding
occurence is
(sweet m mother of 5? Or is it sweet m mother of 100?).
In general, a function far far way might introduce its own, local m and call addM;
the function addM will use that far-distant, “local” m!.
Note that even static-scope can give surprising results,
if we have one variable shared by multiple closures, and then different functions mutate it.
And in Java, the following won't even compile:
for (int i=0; i<10; ++i)
new Thread( () -> System.out.println("in thread #"+i) ).run(); |
It gives you an error message saying mutation and shared state is bad for you
(I'm paraphrasing).
Upshot:
We’ll make W6, to reclaim static scope, and get what we expect!
- Extra credit… but highly recommended W6: Implement static scope (closures).
Modify your function-structures so that
they include one extra piece of information:
the environment (bindings) in effect when the function was declared.
This is the function’s closure.
Update parse and toString.
Also make a careful suite of relevent test-cases involving functions and function-calls
to test for various ways of capturing bindings in different closures.
(On Friday’s lecture, we'll see
on ways of using
let* to effectively implement objects, classes, and inheritance.)
-
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-with-env a function,
will we actually know about any bindings
(since that call to eval-with-env 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.
challenge-extra-credit
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 is a place where you might want to use mutation (read on).
The tricky bit is that 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 “right-hand-side” 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
The “need” for mutation comes from the cyclical data-dependency:
a function-struct contains an environment which refers to that function-struct.
Using shared function, to create cyclical data, removes the need for
you to do mutation, although internally it presumably uses mutation.
But you can also easily avoid the cyclical dependency:
Just keep your function-structure as it was in W5 (does not contain its field),
but then make a `function-with-env` structure which has two fields -- the pure function-struct
plus the environment to use when calling it;
eval will return/use this function-with-env type.
You shouldn't need any additional test cases for W6;
the tests for W0-W5 should suffice,
although one or two W5 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 W6 allows recursion.)
- If you want, modify the LetExpr syntax:
instead of
let id := Expr {: 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 both: 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 still want(need) 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 (as opposed to advanced-student),
begin is implicit
in almost all forms (e.g. function-bodies and cond-branches).
home—lectures—recipe—exams—hws—D2L—zoom (snow day)
This page licensed CC-BY 4.0 Ian Barland
Page last generated | Please mail any suggestions
(incl. typos, broken links)
to ibarland radford.edu |
 |
