|
home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)
Due Dec.08 (Fri) 15:0009 (Sat) 17:00.
Submit:
a hardcopy with
your prolog code; bring hardcopy to the exam on Wednesday,
or slip it under my office door earlier.
If doing S6 for extra credit, submit those files as well, with a
“
We continue to build on
the S language implementation from previous homeworks
(S2 sol'n posted;
S4 sol'n discussed on Monday and full source by Mon 17:00.
Note that S5 can be based off of the S2 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 “
Write
Note:Because of the nature of Prolog's search, and the fact that there are “cycles” of extended-drinking-buddies (unlike ancestors), it is possible that your query for people who aren't extended-drinking-buddies gets into an infinite loop. This is okay, for this homework. The general solution would be to either (a) add an “exclusion” list of people already tried, or (b) use datalog, a restricted prolog which is always guaranateed to terminate. (See#lang racklog .)
Write the following Prolog predicates.
Do not use
Note that the Prolog standard library 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.)
S5 (10pts;
This problem and the next are really the crux of the project.)
Deferred evaluation:
S5 doesn't add any new syntax,
but it is a different evaluation model which
will give us more expressive semantics.
There are two problems1 with the substitution approach used in S2–S4: 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
Re-naming 'eval': Uh-oh, it'd be a pain to have to go and adapt all our existing test-cases foreval , to take an extra argument. I would advise something like3: search-replace all occurrences ofeval in your tests to be instead calling “eval-helper ”. Make that a function which simply callseval with an empty-environment. Then, go changeeval 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 S4 did! For example,let make-adder func m -> func n -> ?ad n 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 S6: callingcall make-adder(3) returns a function whose body still includesm andn , but lacks the fact that we'd like it'sm to be bound to 3. One approach might be to haveeval return both a value and a set of bindings to use that value with. S6 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):
let m 100 in let addM func x -> ?ad x m in ?ad let m 5 in call addM(3) let m 4 in call addM(3) |
(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.
(5pts) 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 Java4. However, it will require mutation (read on).
The tricky bit is that when
when you're
Extra credit (5pts)7
(Scope)
In Advanced Student,
the 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)]))))))) |
(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
If you want to use mutation in your racket-implementation,
use Advanced Student language.
This language level includes
Since the mutators return
(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,
home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)
©2017, Ian Barland, Radford University Last modified 2017.Dec.09 (Sat) |
Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu |