RU beehive logo ITEC dept promo banner
ITEC 380
2013fall
ibarland
aaray

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

hw08
O6: Adding environments
static scope; closures

Due Dec.06 (Fri) at the start of class; accepted through Dec.12 (Thu) 17:00.
Submit: a hardcopy with the additional tests for O6 (since O4), and the additional/changed function(s) for O6 (since O4). Put under my office door, if I'm not there. Submit all files on D2L.
Since O6 is an extension O5, you don't need any code or test-cases for O5 different from O6.

We continue to build on the O language implementation from previous homeworks (O2 specs, solution (.java,.rkt) O4 specs, solution available 2013.Dec.03 0:01 (.java,.rkt).) You may implement this homework in either Java or Racket (or another language, if you clear it with me). Please indicate in your submitted file, what sections of code are udpated and what is unchanged from earlier homeworks/solutions. You don't need to turn in any hardcopy of unchanged-code (but submit a fully-working copy in the drop-box).

  1. (10pts) Prolog recursion
    1. Write allLike(Ppl,Drnk) which is true iff every person in the list Ppl drinks Drnk.
      (Note that Ppl does not need to contain only unique people.)
    2. How would you use your relation to find a list-of-three-people who drink pepsi, where the second person in the list is bob?
    3. How would you query all lists of people who drink pepsi? (That is, each solution found by Prolog should be a list of people, where everybody in the list likes pepsi.)
      How many such lists are there, in your knowledge base? When you type this query in, what are the first three results prolog gives you?
    4. Write allLike(Ppl) which is true iff every person in the list Ppl have some drink preference in common. (That is, if there is some drink that everybody in the list likes.)
  2. (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).
    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.)

  3. Optional challenge-problem1 (Scope, 15pts) 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)])))))))

    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).

    1. How many variables named a are created?                 

    2. How many variables named b are created?                 

    3. How many variables named c are created?                 

    4. 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                            )

  4. O5 (10pts: This problem and the next are really the crux of the project.)
    Deferred evaluation: O5 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 O5, separate from O0-O4.

    There are two problems2 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 eval now takes an extra argument, that suggests three to four check-expects with various environments (lists of bindings):

    A step sideways: This algorithm as described lets us add recursive functions, but it also doesn't handle some expressions that O4 did! For example, let make-adder := m -> (n -> (n add m)) in {{make-adder@3} @ 4} end; gives an error "unbound identifier: m" if no substitution has been done, however {m -> (n -> (n add m)) @ 3 } @ 4} does still work just fine(!). The problem will be fixed in O6: in the first example, {make-adder @ 3} returns a function whose body involves m and n, but not the binding of m to 3. We'd need return the function and its bindings.

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

    let m := 100 
in let addM := (x => (x add m))
   in  ((let m := 5 in {addM @ 3} end;)
        add
        (let m := 4 in {addM @ 3} end;))
   end;
end;
    evaluates to 15, not 206.

  5. (15pts total) O6: Implement static scope. Be sure to make a copy of your O5 project files before starting O6. You shouldn't need any additional test cases for O6; the tests for O0-O5 should suffice, although any O5 examples depending on dynamic binding should now have a new expected-result.
  6. Further extra-credit options (of varying difficulty):

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

1We will talk about this in lecture (let-over-lambda, to implement O.O.), but only briefly.      ↩

2 A third issue, pointed out in Programming Languages and Interpretation, is that evaluating deeply nested lets is an O(n2) algorithm.      ↩

3 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.      ↩

4 For example: 

class Id { 
  String id;   

  public int hashcode() { return (this.id).hashCode(); } }  // delegate to .id

  public boolean equals( Object that ) {
    if (this==that) return true;
    else if (that==null) return false;
    else if (that.getClass() != this.getClass()) return false;
    else {
      Id thatt = (Id) that;
      // Whew, we can finally compare `this` and `thatt`:
      return (this.id).equals(thatt.id);  // delegate to .id's
    }

  // ...other methods...
  }
     ↩

5You'll have to use the keyword #:mutable when you define-struct that structure, to get the setter.      ↩

6 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).      ↩

7 Be default, scheme structs are non-mutable; to make them mutable, you have to provide the keyword #:mutable to define-struct.      ↩

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

©2013, Ian Barland, Radford University
Last modified 2013.Dec.03 (Tue)		 Please mail any suggestions
(incl. typos, broken links)
to ibarlandradford.edu		 Powered by PLT Scheme