ITEC 380 2012fall ibarland tlewis32

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

hw08
Shadowing; Prolog

Due Nov.16 (Fri) in class. I suggest, by Monday, having completed test-cases for N3, and at least two of the prolog queries.
Submit: a hardcopy with the prolog queries for this file, and just the additional tests for N3 and just the function(s) that changed between N2 and N3.

We continue to build on the language implementation started in hw07. You can implement this homework in either Java or Racket. Please indicate in your submitted file, what sections of code are udpated and what is unchanged from hw07/hw07-soln. You don't need to turn in any hardcopy of unchanged-code (but submit a fully-working copy in the drop-box).

1. (1pt) Add another person's drink preferences to the Prolog drink-preference knowledge base from lecture. Make sure that at least two different people like pepsi.
2. (3pts) We say that chaperone(A,B,C) (“A and B can be chaperoned by C”) iff A,B,C are three different people who all have some drink preference in common, and A and B are opposite genders.
   1. define chaperone(A,B,C)
   2. How would you query all the people who could be a chaperone for alice and bob?
   3. How would you query all pairs of people who could be chaperoned by dee?
3. 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 query all lists-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.)

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

N3 is just like N2, except we now allow one variable to shadow another. For example, we might have a let x = … which in turn contains another let x = … inside of it. In that case the inner x should shadow the outer one:
let x = 3 in let x = 5 in (x plus 3);; ⇒ let x = 5 in (x plus 3); ⇒ (5 plus 3) ⇒ 8. And of course, shadowing may occur between non-adjacent scopes: let x = 3 in (let y = 4 in (let x = 5 in …;););.

Thus, when substituting, only substitute “free occurrences” of an Id in E₁, not any “bound occurrences”¹.

5. (5pts) Fill in the following blanks:
   let y = 3 in let x = 5 in (x plus y);; ⇒                                ⇒                  ⇒ 8
   let y = 3 in let x = y in (x plus y);; ⇒                  ⇒                  ⇒ 6
   let x = 5 in let y = 3 in (let x = y in (x plus y); plus x);; ⇒                                          ⇒                                ⇒                ⇒                  ⇒ 11

   Re-indent the following two N3 expressions so that each let is on a different line from -- but equally indented with -- its corresponding in. Q: In each case, what does the expression evaluate to?

   let x = 5 in (let x = (x plus 1) in (x plus 2);); let y = let z = 4 in (let y = 99 in z;); in (let z = 5 in ((let z = 10 in y;) plus (y plus z)););

   You might find it helpful to try to explain (in English) to a friend, exactly when you do and don't substitute.

   You can put all your answers in comments near the top of your main file (N3.rkt or Expr.java), and in the hardcopy code-excerpts.

6. (5pts) Make the necessary changes to N2 to enable shadowing.
   (You are encouraged to build on your solution, but you can also use the posted N2 solutions.) The change should be quite small; you'll submit your entire running project on D2L, but a hardcopy that only has the function(s) you change. Be sure to indicate (for Java) which class contains the changed function.

Here are some examples of the list predicates, for the second prolog question:

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

The interpreter project is based on the first chapters of Programming Languages and Interpretation, by Shriram Krishnamurthi. As a result, this homework assignment is covered by the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License. Although we're using a different dialect of racket than that book, you might find it helpful to skim it.

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

©2012, Ian Barland, Radford University Last modified 2012.Nov.28 (Wed)

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