home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)
hw09
Q5: Adding environments
prolog lists
Due Dec.11 (Fri) at the start of class.
I will accept it on D2L up to Dec.12 23:59, with hard copy under my door by Monday afternoon.
For section 11, due Dec.14 (Mon) 18:45.
Submit:
a hardcopy with
the additional tests for Q6 (since Q4),
and the additional/changed function(s) for Q5/Q6 (since Q4).
Submit all files on D2L.
Since Q6 is an extension Q5,
if you turn in Q6 you don't need to turn in Q5 separately.
We continue to build on
the Q language implementation from previous homeworks
(Q2 specs, solution (.java,.rkt)
Q4 specs, solution available 2015.Dec.09 0:01
(.rkt).)
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 “;>>>Q5”.
You don't need to turn in any hardcopy of unchanged-code
(but submit a fully-working copy in the drop-box).
- (10pts) Prolog list
Write the following Prolog predicates.
Do not use append.
- (3pts)
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.)
- (2pts)
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.)
- (2pts)
lastTwoReversed(List, ListOf2)
which succeeds exactly when
ListOf2 contains the last and the second-to-last item
of List
(in that order).
- (3pts)
reverseLastTwo(List, NewList)
succeeds exactly when NewList
is like List
except that the last two items have been reversed.
(This rule will fail if List 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 xsb Prolog 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.
As ever,
your program should follow good style,
including
appropriate white space,
meaningful variable names,
and
as well as a header comment with your name, the name of the assignment, etc..
(You can have comments describing how a predicate works if you want;
however, you can also assume your program is being read by somebody
who understands the fundamentals of Prolog.)
-
Q5 (10pts:
This problem and the next are really the crux of the project.)
Deferred evaluation:
Q5 doesn't add any new syntax,
but it is a different evaluation model which
will give us more expressive semantics.
Use a new file/project for Q5, separate from Q0-Q4.
There are two problems1
with the substitution approach used above:
we can't make recursive functions,
and it doesn't generalize to 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 Q2, eval never actually
reached an Id;
in Q5 it now does.)
-
In this approach, eval'ing function-application and say expressions
no longer do any substitution —
instead,
each introduce (exactly one) new binding
and proceed recursively2.
-
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.
A step sideways:
This algorithm as described lets us add recursive functions,
but it also doesn't handle some expressions that Q4 did!
For example,
say make-adder be (m) -> { (n) -> {(n add m)}}
in <<make-adder@3> @ 4> matey
gives an error "unbound identifier: m" if no substitution has been done,
The problem will be fixed in Q6:
in the first example, <make-adder @ 3>
returns a function whose body involves m and n,
but not the binding of m to 3.
(To get this approach to work we'd need
to return the function and its bindings;
however, Q6's static scoping is even better.)
Note that this gives us dynamic scoping (which we'll mention in class):
say m be 100
in say addM be (x) -> {(x add m)}
in (say m be 5 in <addM @ 3> matey
add
say m be 4 in <addM @ 3> matey )
matey
matey
|
evaluates to 15, not 206.
-
(extra-credit — 15pts total) Q6: Implement static scope.
(5pts)
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.
- (5pts)
Note that getting recursive functions to work is a bit tricky,
since their environment (closure) needs to include themselves,
but when you're evaling a func-expr
you don't yet have its associated name, hmmm.
Just after the func-expr is created
then you'll want to go in and change its environment to
include itself.
The easiest way is to do this with mutation
(something like set-func-expr-env!
3).
Be sure to make a copy of your Q5 project files before starting Q6.
You shouldn't need any additional test cases for Q6;
the tests for Q0-Q5 should suffice, although
any Q5 examples depending on dynamic binding should now have
a new expected-result.
-
Further extra-credit options (of varying difficulty):
-
Add comments to your grammar and parser.
Make sure comments nest.
It's up to you whether or not you store comments in the
internal representation, or discard them entirely4.
-
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 Q6 allows recursion.)
-
If you want, modify the LetExpr syntax:
instead of
say id be Expr in Expr matey,
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;.
(If you want to use mutation in your underlying scheme implementation,
you can use set-first!
and
set-struct-field!5.
You can also think about how you might try implementing mutation in Q6
without actually using mutation in your underlying program.)
-
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.)
-
Extra credit (5pts)6
(Scope)
The racket form
set! changes the
binding of a variable:
(define x 5)
(set! x (* 2 x))
; the variable x is now bound to 10. |
1. (define a 10)
2. (define b 20)
3. (define make-foo
4. (let {[b 30]}
5. (lambda () ; ← make-foo is bound to this function.
6. (let {[c 40]}
7. (lambda (cmd) ; ← make-foo returns this function as its answer.
8. (let {[d 50]}
9. (cond [(symbol=? cmd 'incA) (set! a (+ a 1))]
10. [(symbol=? cmd 'incB) (set! b (+ b 1))]
11. [(symbol=? cmd 'incC) (set! c (+ c 1))]
12. [(symbol=? cmd 'incD) (set! d (+ d 1))]
13. [(symbol=? cmd 'get-all) (list a b c d)])))))))
|
-
The scope of the a declared in line 1 is lines through .
-
The scope of the b declared in line 2 is lines through .
-
The scope of the b declared in line 4 is lines through .
-
The scope of the c declared in line 6 is lines through .
-
The scope of the d declared in line 8 is lines through .
Suppose that make-foo is called exactly three times
(but that a function returned by make-foo is not called).
-
How many variables named a are created?
-
How many variables named b are created?
-
How many variables named c are created?
-
How many variables named d are created?
(Hint: Each of the above four answers are different.)
(set! a 500)
(set! b 600)
(define counter1 (make-foo))
(define counter2 (make-foo))
(define counter3 (make-foo))
(counter1 'get-all) ; >>> TODO: (list )
(counter1 'incA)
(counter1 'incB)
(counter1 'incC)
(counter1 'incD)
(counter1 'get-all) ; >>> TODO: (list )
(counter2 'get-all) ; >>> TODO: (list )
|
Here are some examples of the list predicates, for the
prolog list questions:
last([1,2,3], 3).
Yes
last([1,2,3], 4).
No
last([1,2,3], Y).
Y=3
last([], Y).
No
last(Y, 3).
Y=[3].
nextToLast([1,2,3], 2).
Yes
nextToLast([1,2,3], 3).
No
nextToLast([1,2,3], Y).
Y=2
nextToLast([1], Y).
No
nextToLast(Y, 3).
Y=[3, _h114], % does not have to be 114, 'course.
Y=[_h116, 3, _h114].
lastTwoReversed([1,2,3], Y).
Y=[3,2]
lastTwoReversed([1], Y).
No
reverseLastTwo([1,2,3,4], Y).
Y=[1,2,4,3]
reverseLastTwo([1,2], Y).
Y=[2,1]
reverseLastTwo([1], Y).
No
1
A third issue, pointed out in
Programming Languages and Interpretation,
is that
evaluating deeply nested lets
is an O(n2) algorithm.
↩
2
Note that the list/map you recur with has the additional binding,
but that recursive call shouldn't add/modify
the list/map used at the top level.
Since java.util.Map is inherently mutable,
you'll want to make a new copy of that map before recurring.
↩
3You'll have to use the keyword #:mutable
when you define-struct that structure,
to get the setter.
↩
4
You can think about which implementation you prefer, when
using a language:
when seeing the program's internal representation of your code
(when debugging, or seeing the compiled result of your code).
↩
5
Be default, scheme structs are non-mutable;
to make them mutable, you have to provide the keyword #:mutable
to define-struct.
↩
6We will talk about
this in lecture (let-over-lambda, to implement O.O.), but only briefly.
↩
home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)