ITEC 380 2011fall ibarland

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

hw08
Substitution and lambda values
project, continued

Due Nov.30 (Wed) 23:59 I will accept #4 by Friday night only if you submit #1-3 on Wednesday night.

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. 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 #4.)
   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”¹.

2. (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

   Rewrite (that is: re-indent) the following two N3 expressions so that each let is on a different line from -- but equally indented with -- its corresponding in. 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 can put all your answers in comments near the top of your main file (N4.rkt or Expr.java)

3. (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 solutions.)

4. (30pts) N4 adds (non-recursive) functions and function-application to our language:

   Expr ::= … | FuncExpr | FuncApplyExpr FuncExpr ::= func(Id, Expr) FuncApplyExpr ::= <Expr(Expr)>

   We restrict ourselves to 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?)

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

   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.) For example, here is a function for computing absolute value:

   func( x, if x isNeg then (-1 times x) else x;)

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

   <func( x, if x isNeg then (-1 times x) else x;)(-5)> let abs = func(x, if x isNeg then (-1 times x) else x;) in <abs(-5)>;

   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 to have a class which can represent either, as the return type for our eval.

   Make test cases for parse (optional), toString and eval involving making and calling the following functions:

   • A constant function that always returns (say) 17.
   • The absolute value function given above,
   • the function sqr, which squares its input,
   and
   • The N4 equivalent of the following racket definition make-adder:

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

Here are some examples of the list predicates, for the 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)

©2011, Ian Barland, Radford University Last modified 2011.Nov.28 (Mon)

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