Take-home (Fall 2002)

ML and Lambda Calculus

1. [20%] (a) Using the approach we studied for representing Lambda calculus in ML, implement the XOR function you defined in the in-class exam.

   (b) Does it work for all possible arguments the original lambda definition allows?

   (c) If the answer to (b) is "no", see if you can alter your lambda expression and ML implementation so that it will work for all valid arguments allowed by the Lambda expression.

2. Consider this lambda expression:

      L s ( s s )
   

   This is a function of one argument, that takes the argument, assumes it is a function, and applies the argument to itself.

   [5%] (a) Describe a funtion that you could give as an argument to this lambda expression such that it makes sense to apply the function to itself.

   [10%] (b) If I try to write this lambda expression directly in ML the type system will not allow it. But I would like to find a way to fake out the type system.

   Find a way in ML to write some function, call it "SSS", such that I can execute, in essence, SSS passed some function "f" as argument, and I end up getting the result of "f" applied to "f". Demonstrate your program using the situation you described in (a).

   Model Checking

3. Consider this formal language:

       { a^n b^n c^n | n >= 1 }
   

   [5%] (a) Is this language context free? Why or why not?

   [5%] (b) Can you design and draw a Petri net that will recognize this language? If so draw it. If not explain why.

   A Petri net recognizes a language in a fashion similar to a finite state machine. The string in question is examined one symbol at a time. Transitions are labeled with symbols in the alphabet. When some symbol "a" is seen, then if a transition labeled "a" is enabled it can be fired; if more than one enabled transition is labeled "a" then the net is nondeterministic like an NDFA. The net can signal recognition of a string by having one or more tokens end up some place (or places) designated as final. It will similarly signal non-recognition by there being no token in the final place(s) once the entire input string has been examined.

4. [10%] Design and draw a Petri net that represents a system with 2 critical resources (R1 and R2). Only one use of R1 is allowed at any time, but R2 can have up to 3 concurrent uses. Represent in your net the activities of not using the resources, requesting the resources, and using the resources.

   ML and Functional Programming

5. [15%] Write in ML a higher-order function called HOF. Make it curried. HOF takes two arguments, called them f and g. Argument f is a function, itself requiring one argument. Argument g is a function of one argument (n, an integer). HOF generates and returns a function; this returned function will want two arguments (the argument f needs, and an integer for g) when it is in turn executed.

   This returned function will compute some number of nested applications of f to its supplied argument. The number of nested applications to do is determined by execution of g on its supplied argument (call this argument i). If g(i) is negative, then execute f once on its argument. If g(i) is not negative and even, then execute f twice nested on its argument; if g(i) is not negative and odd, then execute f(i) 3 times nested on its argument.

   Demonstrate your function by creating some function f, and some function g, and explain what you expect to happen when you run the function created by your HOF on them.

6. [10%] Does ML use eager evaluation, or lazy evaluation? Write an ML funtion that will answer this question... that is, if I run the ML function it will print either "eager" or "lazy" depending on which is the correct method ML uses.

   ADT Specs

7. [20%] Here is a SLIGHT MOD of the type Double Ended Stack (DES) for which you designed axioms in class; this is a Double Ended Bounded Stack (DEBS):

      new   : int        --> DEBS
      pushL : DEBS x ELT --> DEBS
      pushR : DEBS x ELT --> DEBS
      popL  : DEBS       --> DEBS
      popR  : DEBS       --> DEBS
      topL  : DEBS       --> ELT
      topR  : DEBS       --> ELT
      empty : DEBS       --> boolean
      size  : DEBS       --> int
      max   : DEBS       --> int
      full  : DEBS       --> boolean
   

   Now the new constructor takes an integer argument that sets the maximum size of the DEBS; the operation max always tells what that maximum size is. Pushing an operation on a full stack will result in the element on the other end being shoved out to make room for the new element. For example, if S if full, and we do a pushR(S,e), then the element that is topL(S) will be removed so there is one more slot open for the element e on the right end.

   Implement the ADT by expressing the appropriate axioms as partial functions in ML, as we did for earlier assignments. Write a suite of tests to convince you the behavior is correctly implemented. Make the test suite thorough.