|
home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)
Due Jul.28 (Thu) 23:59.
Submit:
a hardcopy with
your prolog code.
If doing Q5 for extra credit, submit those files as well, with a
“
We continue to build on
the Q language implementation from previous homeworks
(Q2 specs
Q4 specs
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 “
Write the following Prolog predicates.
Do not use
Note that xsb Prolog contains several list functions which you are NOT to use for this assignment
(e.g.
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 extra credit;
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 problems 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:
Your test cases should include
a recursive function,
as well as the example below.
Also, since
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]]; mates 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 involvesm andn , but not the binding ofm 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> mates add say m be 4 in <addM @ 3> mates ) mates mates |
(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
To think about:
Hmm, when we first parse our expression, we'll
create function-expressions,
but (since we're not
Only later, when we
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.
Extra credit (5pts)
(Scope)
The racket form
(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)]))))))) |
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
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
3You'll have to use the keyword
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
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)
©2015, Ian Barland, Radford University Last modified 2016.Jul.29 (Fri) |
Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu |