ITEC 380 2020spring ibarland

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

W4 shadowing, function-application; prolog

Due Apr.25 (Sat) 23:59 Submit all files on D2L, plus hardcopy of any (parts of) files you added for W3/W4. Your prolog queries can be inside a comment of a racket file.

Point values will be changed somewhat, for some problems.

We continue to build on the language implementation of W1/W2. You can implement this homework in either Java or Racket. You may use the provided W2 solution if you want. Please add a comment “>>> W3” or “>>> W4” 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 “all-tests” in the W4-test file, as possible/appropriate.

W3 is just like W2, except we now allow one variable to shadow another.

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

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

As an example, for the expression sweet x mother of 3 pearl |sweet y mother of 4 pearl #x order-up |sweet x mother of 5 pearl #x order-up y}|}|, you’d give the tree drawn at the right. This corresponds to some runnable test-cases³:

(check-expect (eval (expr->stringparse! "sweet x mother of 3 pearl |sweet y mother of 4 pearl #x order-up |sweet x mother of 5 pearl #x order-up y}|}|"))
              (+ 3 (+ 5 4)))
(check-expect (subst "x" 3                    (expr->stringparse! "|sweet y mother of 4 pearl #x order-up |sweet x mother of 5 pearl #x order-up y}|}| "))
              (expr->stringparse!                                 "|sweet y mother of 4 pearl #3 order-up |sweet x mother of 5 pearl #x order-up y}|}| ") )

0. Change the purpose-statement of subst to be “substitute any free occurrences of …”. Note that you will not substitute other binding occurrences, either.
1. For each of the following, fill in the blanks by replacing the outermost LetExpr with just its body, but substituting its variable respecting shadowing.
   For example (using the program/image above):
   ⇒ sweet x mother of 3 pearl |sweet y mother of 4 pearl |#x order-up sweet x mother of 5 pearl #x order-up y}}||
   ⇒ |sweet y mother of 4 pearl |#3 order-up sweet x mother of 5 pearl #x order-up y}}||
   ⇒ ||#3 order-up sweet x mother of 5 pearl #x order-up 4}}||
   ⇒ ||#3 order-up #5 order-up 4}}||
   ⇒ 12
   Complete the blanks in a similar way, below:
   1. ⇒ sweet y mother of 3 pearl sweet x mother of 5 pearl #x order-up y}
      ⇒                                             
      ⇒                                           
      ⇒ 8
   2. ⇒ sweet y mother of 3 pearl sweet x mother of y pearl #x order-up y}
      ⇒                                                                                                                         
      ⇒                                           
      ⇒ 6
   3. ⇒ sweet x mother of 5 pearl sweet y mother of 3 pearl #sweet x mother of y pearl #x order-up y} order-up x}
      ⇒                                                                                                                                                                                                                                             
      ⇒                                                                                                                                                               
      ⇒                                                                                 
      ⇒                                           
      ⇒ 11
   4. ⇒ sweet x mother of 5 pearl sweet x mother of #x order-up 1} pearl #x order-up 2}
      ⇒ sweet      mother of #     order-up 1} pearl #     order-up 2}
      ⇒ sweet      mother of      pearl #     order-up 2}
      ⇒ #     order-up 2}
      ⇒     

2. Update W2 to W3, by the necessary changes to enable shadowing.
   You are encouraged to build on your own previous solution, but you may also use the W2 solution (.rkt files posted).

   • The change should be quite small, but is surgically precise.
   • Recall that W2’s subst is essentially the same code as change-name in AncTrees.
     Hint: What is needed for W3’s (and W4’s) subst would be like a name-change that stops when it reaches the name it’s changing.
   • Please label each section of lines you change with a comment “;>>>W3”.

Expr ::= … | FuncExpr | FuncApplyExpr

FuncExpr ::= <^> Id * Expr          interpretation: function-value; inspired by patrick star
FuncApplyExpr ::= aye aye Expr captain Expr   interpretation: call the function (which is the captain of its argument)

Here is the function (λ (x) (+ (* 3 x) 1)) written in W4 with typos (*) fixed to <*>: <^> x * ##x barnacles! 3} order-up 1}.
And, here is the (uniterated) collatz function in W4:

<^> n * ahoy n me #n barnacles! 0.5} money ##n barnacles! 3} order-up 1}

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 5·3+1 = 16:

aye aye 5 captain <^> x * ##x barnacles! } order-up 1}   Applying a function-literal

sweet      tripleAndInc                                Name the function-value,…
mother of  <^> x * ##x barnacles! 3# order-up 1#
pearl      aye aye 5 captain tripleAndInc              …and then apply it to 5

3. First, write the following four functions as W4 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; give it a name with a W4 LetExpr whose body we’ll just leave as “…”. I.e. write the W4 equivalent of racket (let {[sqr (lambda (x) (* x ))]} …).
   3. the factorial function, written in W4 using a LetExpr with body “…” as in the previous example.

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

4. Then, upgrade W3 so that it allows functions to be represented; label each section of lines you change with a comment “;>>>W4”.
   1. Add a struct/class for representing FuncExprs internally.
   2. parse! (and tests).
   3. expr->string (and tests)
   4. eval (and tests)
5. Implement function-application.
   1. Add a struct/class for representing FuncApplyExprs internally.
   2. parse! (and tests)
   3. expr->string (and tests)
   4. 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 aye aye Expr₀ captain Expr₁:

      1. Evaluate Expr₀; let’s call the result actual-arg.
      2. Evaluate Expr₁; let’s call the result f. (f had better be a function-value!)
      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.

Prolog

As mentioned: Your prolog queries can be inside a comment of a (racket) file, at the top of your submitted hardcopy, thanks! Only include your added rules/facts, not the rest of the provided .pl file.

5. Add another super-person (hero, villain, or neither) and at least three more color-or-weapon preferences to the Prolog superhero knowledge base from lecture.
6. Two super-people are compatible if they share a fighting style, or a color-preference (and they aren’t the same person). Moreover, team(A,B,C) is true if A and B are compatible, and B and C are compatible, but A and C aren’t the same.
   1. define a rule compatible(A,B).
   2. What query will solve for every super-person compatible with bubbles?
   3. define team(A,B,C).
   4. What query will solve for every team starting with bubbles and ending with rafael?

7. Write friendly: We say two super-people are friendly if they are connected through some chain of compatible people. For example, bubbles and rafael would be friendly if compatible(bubbles,magikarp), compatible(magikarp,spongebob), and compatible(spongebob,rafael). (That is: friendly is the transitive closure of the compatible relation.) Everybody, of course, is trivially friendly with themselves (since they’re connected by a chain of 0 compatible others).

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(expr->string("sweet x mother of 5 pearl #x order-up 3}))
= eval(expr->string("#5 order-up 3}"))
= eval(expr->string("8"))

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

This page licensed CC-BY 4.0 Ian Barland Page last generated

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