ITEC 380 2014fall ibarland

most recent semester

hw07
Prolog, shadowing, and function-application

Due Dec.02 (Mon) in class. It is intended that you can finish Friday before the break, but I will have it due afterwards. (Note that the last homework will be available before the break, should you want to work on that.)
Submit: a hardcopy with the prolog queries for this file, and just the additional tests for O3 and just the function(s) that changed between O2 and O3. On D2L, submit a file for your prolog solution, as well as one set of files for O5/O6.

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 hw06/hw06-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?

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

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

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

   Re-indent the following two O3 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 add 1) in (x add 2) end;) end; let y := let z := 4 in (let y := 99 in z end;)end; in (let z := 5 in ((let z := 10 in y end;) add (y add z)) end;)end;

   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 (O3.rkt or Expr.java), and in the hardcopy code-excerpts.

4. (5pts) Make the necessary changes to O2 to enable shadowing.
   (You are encouraged to build on your solution, but you can also use the posted O2 solutions.) The change should be quite small: similar to the difference between change-blue-to-brown vs. change-blue-to-brown-stopping-at-green.

5. (26pts) O4 adds (non-recursive) functions and function-application to our language:

   Expr ::= … | FuncExpr | FuncApplyExpr FuncExpr ::= {Id => Expr} FuncApplyExpr ::= [Expr @ Expr]

   Here is an example of a function; it happens to compute a number’s absolute value:

   { x => if x isNeg then (-1 mul x) else x;}

   Just like numbers are self-evaluating, so are FuncExprs. If evaluating (an internal representation of) a FuncExpr, just return that same (internal representation of the) function. We won't actually evaluate the body until the function is applied. (This is exactly how racket, python, javascript, etc. treat lambda values.)

   A funcApplyExpr represents calling a function. Here are two expressions, both computing the absolute value of -5:

   [{ x => if x isNeg then (-1 mul x) else x;} @ -5] let abs := {x => if x isNeg then (-1 mul x) else x;} in [abs @ -5] end;

   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 is0Expr or letExpr which evaluates to a function.)

   To evaluate a function-application [Expr₀ @ Expr₁)]:

   • Evaluate Expr₀; let’s call the result f. (f had better be a function-value!)
   • Evaluate Expr₁; let’s call the result arg.
   • Substitute f’s parameter with arg in f’s body; call this new expression E′.
   • Evaluate E′ and return that value.
   Hey, those semantics are practically the same as let!

   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 O4, and then call the function for your test case:

   1. (1pt) A constant function that always returns (say) 17.
   2. The absolute value function given above,
   3. (1pt) the function sqr, which squares its input,
   4. (2pts) the factorial function, written in O4.

      Note: You won't be able to evaluate function-applications for recursive functions yet (see O5), 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
   5. (2pts) The O4 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

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

   To think about: If we wanted to 'fake' functions of 2 arguments in N4, 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("let x := 5 in (x plus 3) end;"))
= eval(parse("(5 plus 3)"))
= eval(parse("8"))

most recent semester

©2014, Ian Barland, Radford University Last modified 2014.Sep.27 (Sat)

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