ITEC 380 2012fall ibarland tlewis32

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

hw09
functions, and more functions
functions returning functions; implementing functions in N4

Due Nov.30 (Fri) at the start of class.
Submit: a hardcopy with and just the additional tests for N4

We continue to build on the language implementation started in hw08. 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 hw08/hw08-soln. You don't need to turn in any hardcopy of unchanged-code (but submit a fully-working copy in the drop-box).

1. (7pts) Consider the higher-order function non, which takes in any boolean predicate and returns a new predicate that behaves in the opposite¹ way: (non positive?) is a function that takes in a real number, and returns true if that number is negative or zero. Similarly, (non ship?) takes in any value, and returns true if it’s not a ship structure.
   1. Give two tests of calling the result returned from calling non.
   2. What is the signature of non?
      Remember, you can't just say “function → function”; you have to include the signature of each of those functions. Recall the signature filter : (α → boolean), (listof α) → (listof α).
   3. Write non.
2. (7pts) Consider the function apply-twice, which takes in a function and returns a new function: one which applies (iterates) the original function twice. For example, (apply-twice sqr) returns a function which squares its input twice, so: ((apply-twice sqr) 3) = 81, and (map (apply-twice sqr) '(2 3 4)) = '(16 81 256). Similarly, (apply-twice rest) returns a function which returns the rest-of-the-rest of a list; ((apply-twice rest) '(2 3 4 5)) = '(4 5), and (map (apply-twice rest) '((a b c) (2 3 4 5) ("hi" "bye"))) = '((c) (4 5) ()).
   1. What is the signature of apply-twice?
      Remember, you can't just say “function → function”; you have to include the signature of each of those functions. Recall the signature filter : (α → boolean), (listof α) → (listof α).
   2. Write the function.

3. (extra-credit, 5pts) Generalize apply-twice to a version which applies a function as many times as you like: Write iterate, which takes in a function f and a natural-number n, and returns a function which: repeatedly applies fto that input, then applies f to that result, and so on, a total of n times.

   Clearly, apply-twice is a special case of iterate: Note that² ∀f, (apply-twice f) = (iterate f 2).
   Re-write apply-twice to call iterate.

   By the way, note that natural numbers have a structural definition (the same way lists and trees did): a natural number is either 0, or 1 added to some other (slightly smaller) natural number. Your code for processing a natural number should reflect this data definition, in the same way your code for processing a list or a Ancestor-tree or a Expression-tree all follow the shape of that data.

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

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

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

   func( x, if x isNeg then (-1 times 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:

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

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

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

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

   Note that we're restricting N4 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 problem of the 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)

©2012, Ian Barland, Radford University Last modified 2012.Dec.03 (Mon)

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