ITEC 380 2017fall ibarland

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

S4
S4 shadowing, function-application; prolog

Due Dec.03 (Sun) 23:5904 (Mon) 15:00. Submit all files on D2L, plus hardcopy of any (parts of) files you added for S3/S4. Your prolog queries can be inside a comment of a racket file, at the top of your submitted hardcopy, thanks!

We continue to build on the language implementation of S1/S2. You can implement this homework in either Java or Racket. You may use the provided S2 solution if you want. Please add a comment “>>> S3” or “>>> S4” next to places you add/update for this homework. You don't need to turn in any hardcopy of unchanged-code (but submit a fully-working copy in the drop-box). Please put new tests into the list “tests” in the Si-expr-test file, as possible/appropriate.

S3 is just like S2, except we now allow one variable to shadow another.

For example, we might have a let x … in … which in turn contains another let x … in … inside of it. In that case the inner x should shadow the outer one:
let x 3 in let x 5 in ?ad x 3 ⇒ let x 5 in ?ad x 3¹ ⇒ ?ad 5 3 ⇒ 8. And of course, shadowing may occur between non-adjacent scopes: let x 3 in |let y 4 in |let x 5 in …||.

In technical terms: when substituting, only substitute “free occurrences” of an Id in E₁, not any “bound occurrences”².

0. (0pts) Change the purpose-statement of subst to be “substitute any free occurrences of …”. Note that you will not substitute other binding occurrences, either.

1. (7pts) For each of the following five expressions:

   1. Draw an abstract syntax tree³ for the expression;
   2. for each variable, circle the binding-occurrence, and draw a line to all uses of that variable.
   3. Turn the example into a runnable test-cases: not just for eval but also for subst (that is, for the top-level let shown, subst that variable into it's body-expression, as in the example).
   As an example, for the expression let x 3 in |let y 4 in ?ad x |let x 5 in ?ad x y||, you'd give the tree drawn at the right, and

   (check-expect (eval (parse! "let x 3 in |let y 4 in ?ad x |let x 5 in ?ad x y||")) (+ 3 (+ 5 4))) (check-expect (subst "x" 3 (parse! "|let y 4 in ?ad x |let x 5 in ?ad x y||")) (parse! "|let y 4 in ?ad 3 |let x 5 in ?ad x y||"))

   Our goal in doing this is to understand: when substituting free variables, exactly when do we stop and not substitute it in various sub-trees? For example, in the provided image: Why does the top-level "x" bind to the "x" in the middle, but not the "x" in the bottom-right? What rule can you use, when substituting, about precisely where to stop substituting?
   1. let y 3 in let x 5 in ?ad x y
   2. let y 3 in let x y in ?ad x y
   3. let x 5 in let y 3 in ?ad let x y in ?ad x y x
   4. let x 5 in |let x ?ad x 1 in ?ad x 2|
   5. let y let z 4 in |let y 99 in z| in |let z 5 in ?ad |let z 10 in y| ?ad y z|
   You might find it helpful to try to explain (in English) to a friend, exactly when you do and don't substitute.

2. (5pts) Update S2 to S3, by the necessary changes to enable shadowing.
   You are encouraged to build on your own previous solution, but you may also use the S2 solution (posted).

   • The change should be quite small, but is surgically precise.
   • Label each section of lines you change with a comment “;>>>S3”.
   • Recall that S2's subst is essentically the same code as change-eye-color-blue-to-brown in AncTrees.
     Hint: What is needed for S4's subst is essentially the same as brown->green/stop-at-red.

---

S4 adds (non-recursive) functions and function-application to our language:

Expr ::= … | FuncExpr | FuncApplyExpr FuncExpr ::= func Id -> Expr FuncApplyExpr ::= call Expr ( Expr )

Be sure not to confuse functions with function-application (calling a function) — it’s the difference between square-root (as a function), and the square-root-function-applied-to-4 (or put differently: it's the difference between a hammer, and hitting something with a hammer).

Here is the function (λ (x) (+ (* 3 x) 1)) in S4: func x -> ?ad 1 ?mu x 3. And, here is the collatz function in S4:

func n -> (%mo n 2) !0 ?ad ?mu x 3 1 : ?mu n 0.5

Just as numbers are self-evaluating, so are FuncExprs. Evaluating (an internal representation of) a function results in that same (internal representation of the) function. We won't actually evaluate the body until the function is applied. (This is exactly how Java, racket, python, javascript, etc. treat functions.)

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

let tripleAndInc func x -> ?ad 1 ?mu x 3 in call tripleAndInc(5) call func x -> ?ad 1 ?mu x 3 (5)

In FuncApplyExpr, the first Expr had better evaluate to a function. (That is, it might be a FuncExpr, or an Id which gets substitued to a function value. It could also be (say) an IfZeroExpr or LetExpr which evaluates to a function.)
3. First, write the following four functions as S4 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 S4.

      Note: You won't able to evaluate function-applications for recursive functions yet (see S5), 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 S4 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

      Observe:If you wanted, you could certainly write apply-twice in S4. Our language trivially supports higher-order functions!

   Then, upgrade S3 so that it allows functions to be represented; label each section of lines you change with a comment “;>>>S4”.
   1. (2pts) Add a struct/class for representing FuncExprs internally.
   2. (2pts) parse! (and tests).
   3. (2pts) expr->string (and tests)
   4. (2pts) eval (and tests)
4. Implement function-application.
   1. (2pts) Add a struct/class for representing FuncApplyExprs internally.
   2. (2pts) parse! (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. (You don't need to test eval'ing your factorial function, though.)

      The semantics of eval'ing the function-application call 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 actual-arg.
      3. Substitute f’s parameter with actual-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 LetExpr’s! 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.

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

To think about: If we wanted to 'fake' functions of 2 arguments in S4, 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.

---

5. (1pt) Add another person and at least three more drink preferences to the Prolog drink-preference knowledge base from lecture. Make sure that at least two different people like pepsi.
6. (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 an optimist and a pessimist (in either order).
   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?

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("let x 5 in (x plus 3)"))
= eval(parse("(5 plus 3)"))
= eval(parse("8"))

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

©2017, Ian Barland, Radford University Last modified 2017.Dec.03 (Sun)

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