ITEC 380 2016fall ibarland

home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

hw09
R5: Adding environments
prolog lists

Due Dec.09 (Fri) 23:59 Dec.11 (SatSun.) 17:00
Submit: a hardcopy with your prolog code. If doing R6 for extra credit, submit those files as well, with a “>>>R5” comment by your modified lines.

We continue to build on the R language implementation from previous homeworks (R2 sol'n posted; R4 sol'n discussed, and full source by Mon 17:00; note that R5 can be based off of the R2 solution for full credit). (R2 specs R4 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 “;>>>R5”. You don't need to turn in any hardcopy of unchanged-code (but do submit a fully-working copy in the drop-box).

1. (10pts) Prolog list

   Write the following Prolog predicates. Do not use append.

   1. (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.)
   2. (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.)
   3. (2pts) 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).
   4. (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.)

2. R5 (10pts; This problem and the next are really the crux of the project.)
   Deferred evaluation: R5 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 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 R2, eval never actually reached an Id; in R5 it now does.)
   • In this approach, eval'ing function-application and :o expressions 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.

   A step sideways: This algorithm as described lets us add recursive functions, but it also doesn't handle some expressions that R4 did! For example, :o make-adder :B m -> :B n -> |n m ;)| :U ! !make-adder 3! 4! gives an error "unbound identifier: m" if no substitution has been done, The problem will be fixed in R6: 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, R6's static scoping is even better.)

   Note that this gives us dynamic scoping (which we'll mention in class):

   :o m 100 :U :o addM :B x -> |x m ;)| :U | :o m 5 :U !addM 3! :o m 4 :U !addM 3! ;) |

   evaluates to 15, not 206.

3. (extra-credit — 15pts total) R6: Implement static scope (closures).

   • (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: their environment (closure) needs to include its own name! Further explanation added: 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 R0-R4 file/project to a new R5⁴. You shouldn't need any additional test cases for R6; the tests for R0-R5 should suffice, although anyone or two R5 examples depending on dynamic binding should now have a new expected-result.
4. 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 R6 allows recursion.)
   • If you want, modify the LetExpr syntax: instead of :o id Expr :U 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.)

5. Extra credit (5pts)⁶ (Scope)
   In Advanced Student, the 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)])))))))

   
   1. 
      The scope of the a declared in line 1 is lines      through     .
   2. 
      The scope of the b declared in line 2 is lines      through     .
   3. 
      The scope of the b declared in line 4 is lines      through     .
   4. 
      The scope of the c declared in line 6 is lines      through     .
   5. 
      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).
   6. 
      How many variables named a are created?     
   7. 
      How many variables named b are created?     
   8. 
      How many variables named c are created?     
   9. 
      How many variables named d are created?     
   (Hint: Each of the above four answers are different.)
   (0pts) To help you figure out the above, try filling out the following (before you try running it):

   (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

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 Jave assigning-to-field and assigning-to-local-variable look alike, 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, but 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; distance)

©2016, Ian Barland, Radford University Last modified 2016.Dec.11 (Sun)

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu