ITEC 380 2015fall ibarland

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

hw08
Prolog; Q4 shadowing, and function-application

Due Dec.07 (Mon) in class. Submit all files on D2L, plus hardcopy of any parts you added for Q3/Q4.

We continue to build on the language implementation started in hw06. 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. (5pts) We say that chaperone(A,B,C) (“A and B can be chaperoned by C”) iff A,B,C are three different people who each have some drink preference in common with each other (“pairwise”), and A and B are opposite genders.
   1. define chaperone(A,B,C)
   2. What query will match all the people who could be a chaperone for alice and bob?
   3. What query will match all pairs of people who could be chaperoned by dee?

3. (5pts) Write edb (“extended drinking buddies”): We say two people are extended drinking buddies if they are connected through a chain of drinking-buddy links. For example, alice and kris would be extended drinking buddies if drinksWith(alice,charlie), drinksWith(charlie,ethan), and drinksWith(ethan,kris). (That is: extended-drinking-buddies is the transitive closure of the drinksWith relation.)

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

Q3 is just like Q2, except we now allow one variable to shadow another.

For example, we might have a say x be … in … matey which in turn contains another say x be … in … matey inside of it. In that case the inner x should shadow the outer one:
say x be 3 in say x be 5 in (x add 3) matey matey ⇒ say x be 5 in (x add 3) matey¹ ⇒ (5 add 3) ⇒ 8. And of course, shadowing may occur between non-adjacent scopes: say x be 3 in [[say y be 4 in [[say x be 5 in … matey]]matey]]matey.

In technical terms: when substituting, only substitute “free occurrences” of an Id in E₁, not any “bound occurrences”². Change the purpose-statement of subst to be “substitute any free occurrences of …”.

4. (7pts) Fill in the following blanks:

   1. say y be 3 in say x be 5 in (x add y) matey matey ⇒                    ⇒            ⇒ 8
   2. say y be 3 in say x be y in (x add y) matey matey ⇒                                    ⇒            ⇒ 6
   3. say x be 5 in say y be 3 in (say x be y in (x add y) matey add x)matey matey ⇒                                                                        ⇒                                              ⇒                      ⇒            ⇒ 11

   Hint: Each step of your answer should remove/simplify the outermost (root) expression — don't simplify from the inside out.

   Re-indent the following two Q3 expressions so that each say statement has its three parts equally-indented, on different lines:

   say Id be Expr in Expr matey

   Your answer should be 2n+1 lines long, where n is the number of say expressions you have.
   Q: In each case, what does the expression evaluate to?
   4. say x be 5 in [[say x be (x add 1) in (x add 2) matey]] matey
   5. say y be say z be 4 in [[say y be 99 in z matey]] matey in [[say z be 5 in ([[say z be 10 in y matey]] add (y add z)) matey]] matey
   Put your fill-in-blanks in comments next to your test-cases (with the last two indented as requested). Also, turn all five of the above into runnable test-cases: not just for eval (where the last blank is the expected result), but also for subst (where the first blank is the expected result for a corresponding call to subst). You might find it helpful to try to explain (in English) to a friend, exactly when you do and don't substitute.

5. (5pts) Update Q2 to Q3, by the necessary changes to enable shadowing.
   You are encouraged to build on your own previous solution, but you may also use the Q2 solution (Q2.rkt (D2L), Q2-expr-test.rkt; email me ASAP for Java solution). The change should be quite small, but is surgically precise. Label each section of lines you change with a comment “;>>>Q3”.

Expr ::= … | FuncExpr | FuncApplyExpr

FuncExpr ::= (Id) -> {Expr}
FuncApplyExpr ::= <Expr @ Expr>

Here is an example of a function in Q4:

(x) -> { parity x even: (x sub 1) odd: ((x mul 3) add 1); }

A FuncApplyExpr represents calling a function. Here are two expressions, both evaluating to 5·3+1 = 16:

say tio be (x) -> {parity x even: (x sub 1) odd: ((x mul 3) add 1);}
    in <tio @ 5> matey

    
< (x) -> { parity x even: (x sub 1) odd: ((x mul 3) add 1); } @ 5>

6. First, write the following four functions as Q4 programs. (You can then modify them as part of your tests.)
   1. A constant function that always returns (say) 17.
   2. the function sqr, which squares its input,
   3. the factorial function, written in Q4.

      Note: You won't be able to evaluate function-applications for recursive functions yet (see Q5), but we can still write the test cases! (You can comment out that one test case for now, since it'll trigger a run-time exception otherwise.)

   and
   4. The Q4 equivalent of the following racket definition make-adder:

      (define (make-adder n) (lambda (m) (+ n m))) ; Two examples of applying this function: ; (make-adder 3) ; evals to (lambda (m) (+ 3 m)) ((make-adder 3) 4) ; evals to 7

   Then, upgrade Q3 so that it implements functions; label each section of lines you change with a comment “;>>>Q4”.
   1. (2pts) Add a struct/class for representing FuncExprs internally.
   2. (2pts) expr->string (and tests)
   3. (6pts) parse/string->expr (and tests).

      hint:If you see “(” while parsing a Q4 program, what types of expression might you have? How do you differentiate between them? You might have a cond branch for “(”, and then inside of that you will need a nested if/cond.

   4. (2pts) eval (and tests)
7. Implement function-application.
   1. (2pts) Add a struct/class for representing FuncApplyExprs internally.
   2. (2pts) parse/string->expr (and tests)
   3. (2pts) expr->string (and tests)
   4. (9pts) eval (and tests). Here, more than half the points are for tests, since you want to try several situations involving shadowing variables.

      The semantics of eval'ing the function-application <Expr₀ @ Expr₁>:

      1. Evaluate Expr₀; let’s call the result f. (f had better be a function-value!)
      2. Evaluate Expr₁; let’s call the result arg.
      3. Substitute f’s parameter with arg in f’s body; call this new expression E′.
      4. Evaluate E′ and return that value.
      Hey, those semantics are practically the same as LetExprs’! Indeed, it's not very different; the function holds the identifier and body; when you eval a function-application then we do the same substitution.

Observe that our programs can now evaluate to either of two types: numbers or functions. In Java, we'll need a class which can represent either, as the return type for our eval. That’s why the abstract class Value was included, of which Number was one subclass.

Make test cases for parse (at least one, for each of functions and function-applictions). Then, make test cases for toString and eval: Write each of the following functions in Q4, and then call the function for your test case:

Note that we're restricting Q4 to only deal with unary functions (functions of one argument).

To think about: If we wanted to 'fake' functions of 2 arguments in Q4, how could we do it? For example, you might think about how to write a function that effectively takes in two numbers i,j and returns 2·i+j. Think about how make-adder does this.

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.

  eval(parse("say x be 5 in (x plus 3) matey"))
= eval(parse("(5 plus 3)"))
= eval(parse("8"))

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

©2015, Ian Barland, Radford University Last modified 2015.Dec.14 (Mon)

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