CSE583 Assignment 1 Solutions (Winter 2000)

CSE Home

About Us

Search

Contact Info

See the basic page on assignments for program weights, rules for working in pairs, etc.

This assignment is due on Friday, January 21, at 5PM PST.  We will make an announcement later about the specific electronic form for turning in the assignment.  

For ML compilers, here is the information:

• SML 110.0.3 is available from the instructional Unix systems:  /cse/courses/misc_lang/linux/sml/bin/sml
• The departmental education PCs also have a version of SML available in \\ifilesrv1\tools\smlnj (which is usually mounted on drive W:).
• If you want to install your own (it's almost all freeware) look on the SML FAQ page, which contains (among other things) a self-installing executable for NT and Win95.

1. 15 points) For your "first" programming language (the one you listed in class on Tuesday 1/4/2000 -- if you are working in a pair, use either of your first languages), identify and carefully (but concisely) characterize three shortcomings of the language with respect to specific programming language design principles discussed in lecture or the Wirth or the Hoare paper.

2.  (15 points) For your "primary" programming language (the one you listed in class on Tuesday 1/4/2000 -- if you are working in a pair, use either of your primary languages), identify and carefully characterize three shortcomings of the language with respect to specific programming language design principles discussed in lecture or the Wirth or the Hoare paper.  [Note: if your "first" and "primary" languages are the same, you can pick an alternative language for either.]
   

Solution: This answer applies to questions 1 and 2.
Most people got most or full credit for these questions. I'm not going to list all answers exhaustively, but here are some of the main ones. Major problems (full credit):

• No guaranteed order of evaluation (Pascal)
• Goto's [More credit for better description of resulting problem]
• Not structured (BASIC)
• No user-defined data types [abstraction] (BASIC)
• No library calls
• No information hiding
Minor problems (partial credit):
• No type declarations - the issue is strong typing, not type declarations. ML is strongly (and statically) typed, but types need not be declared. (This gets almost full credit, full credit if expanded upon.)
• Syntactic requirements like declaration order in Pascal or parentheses in LISP
• Missing "my favorite language feature X", for X not universally considered necessary such as polymorphism, inheritance, sets, parameter labelling.
• Missing a tool - no debugger, compiler (interpreted instead), etc. This is not a language issue, unless the language is defined so as to make such a tool impossible.
3. (10 points) Functional languages provide a composition operator that composes any two compatible functions.  Can such a composition operator be written in existing ALGOL-like languages?  Briefly but clearly justify your answer.
   

Solution: Not with the full generality and ease of functional languages. The most important reason is that, in most imperative languages, functions aren't first class. In particular, you can't create new functions at runtime. Also, you typically can't pass them in as arguments or return them as return values. You can write a function which, for example, takes two function pointers f and g and an argument x, and calls *f(*g(x)), but this doesn't return a function, it returns the value of the composition applied to an argument. Another reason is that strict typing in most imperative languages is difficult to maintain. Most imperative languages have holes in their type system. This makes functional composition difficult because it's hard to determine if two functions are "compatible."

4. (10 points) Böhm and Jacopini proved that all programs written with goto statements can be mechanically converted to programs that only use only sequencing, while loops, and if-then-else statements.  The basic idea is to encode the program counter as an explicit variable that controls the next statement to be executed.   This result enabled the wave of goto-less programming.  Explain why this result is primarily of theoretical interest.  (If you disagree, argue clearly and concisely why.)
   

Solution: While they proved that you never needed a goto, the particular way in which they did away with goto's didn't provide any nice insight into how to program well without goto's. Certainly any program which was written in a style matching their goto-less converted gode would be much more difficult to understand than well structured goto-less code, and probably even more difficult than code with goto's if they were used with some care. In other words, their result wasn't a recipe for how to program without gotos, but rather a proof that you could. More specifically, it was a proof that you could systematically remove all the gotos through some process of compilation, but again, this didn't give insight into how you would want to compile a program with gotos in it. Thus their translation method didn't produce more readable or more efficient code (in fact, it would almost certainly be less efficient.)

People approached this question from several directions. Some argued that the proof that goto-less programming was uninteresting, since another proof exists that any program could be rewritten without structured programming, but just with sequencing, conditionals and gotos (in fact, that's what your compiler does), but that doesn't mean we should all start writing code that way. This is a strong argument and got full credit. Some argued that goto's were really OK, even desirable, which got partial credit, depending on the strength of the argument. Others argued that "the wave of goto-less programming" was of practical value. These answers got less credit, as they missed the point of the question which wasn't "why is goto-less programming only of theoretical value", but rather, "why was the Bohm-Jacopini proof that goto-less programming was possible only of theoretical value."

5. (10 points) Consider the ML functions:
   
   fun twice f x = f (f x);
   fun succ x = x + 1;
   
   If you execute
   
   twice twice twice succ 0
   
   ML returns the answer 16.
   
   Give the clearest answer you can about why this answer is returned. 
   

Solution: The keys to understanding this question are:

1. ML evaluates in innermost-leftmost ("applicative") order
2. All functions have only one argument and return a single value
3. Apparent multiple arguments are handled by currying, that is, taking the first argument and producing a function that handles the next one and so on.
One way to think about this problem is to treat it in two stages, first figure out what the twice's are doing to each other, then apply that to "succ 0". Before we start though, a little aside.

Remember, "fun" is just syntactic sugar for binding an anonymous function to a symbol, and we can bind that function to other symbols too, so for sanity, I'm going to introduce a bunch of aliases.

val g = twice;
val h = twice;
val i = twice;
val S = succ;

The whole expression could now be rewritten as:

g h i S 0;

But remember that this is still twice twice twice succ 0;

OK, back to our regularly scheduled answer...

Here's the full expansion with all parens made explicit, in each case, the x represents the formal that will be bound to the following expression as an argument.

(((((g x) h) i) s) 0)
Apply (g x) to h resulting in (h (h x))
((((h (h x)) i) s) 0)
Apply (h (h x)) to i in two stages, first the inner h is applied, resulting in (i (i))
((((h x) (i (i))) s) 0)
Then the outer h is applied to (i (i)), resulting in (i (i (i (i))))
(((i (i (i (i x)))) s) 0)

Quick station break... we see that, at this point, the twice's have expanded out from (((twice) twice) twice) to (twice (twice (twice (twice x))))

Repeating from before, we have:
(((i (i (i (i x)))) s) 0)
The innermost i is applied to s, resulting in (s (s))
(((i (i (i x))) (s (s))) 0)
The next innermost i is applied to (s (s)) resulting in (s (s (s (s)))) (which I'll call S4 below).
(((i (i x)) (s (s (s (s))))) 0)
The next innermost i is applied to S4 resulting in S8
(((i x) (s (s (s (s (s (s (s (s))))))))) 0)
The last i is applied to S8 resulting in S16
((s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s x)))))))))))))))) 0)

It should be pretty straighforward now to see that 16 successive applications of s results in a function which takes a numeric argument and adds 16 to it. Passing in 0 results in 16.

Here's the much longer, English description of what's going on.

Because in ML all functions have one arg and the application operator (juxtaposition) is left associative, we can consider this one application at a time. I'm going to break it down that way and at each step give a name to the function that gets created. I'll use capital letters for these function names, and the number of letters will indicate the number of time a function is being applied in the expansion. While this is just shorthand for the sake of explanation, it's interesting to note that it's an executable sort of shorthand. For example, consider the application of g to h. g is of type
('a -> 'a) -> 'a -> 'a.
That is, it takes a function whose input and output are both the same type, 'a, and returns a function whose input and output are also both that same type 'a. The definition of g is the same as twice: fun twice f x = f (f x), so g h x = h(h(x)). This is an anonyous function, but for the time being, let's give it a name, HH. In fact, we could write

val HH = g h;

and it would be equivalent to writing

val HH = fn x => h(h(x));

(This is what I mean by executable shorthand, you could actually create the HH function in ML using g(h).)

In other words HH is a function and it's body is h(h(x)). Now what happens when you apply this function to i?

HH(i) = h(h(i)) by definition. But what does this mean? Well, it means apply the h function to i and then apply the h function again to the result of this application? So let's do that. First we apply h to i. h(i) = i(i(x)), which I'll call II. Then we apply h to the result of that application. h(II) = II(II(x)), which, unpacking the temporary names, is i(i(i(i(x)))).

Now let's apply this function to S. What is i(i(i(i(S))))? Well remember, i is the same as twice, so i f x = f(f(x)). So the innermost application of i S x results in S(S x). That is the function you get by apply S to a value and then apply S to the result. Let's call that function SS. So we now have i(i(i(SS))), The next application of i gives SS(SS), which we'll call SSSS, and is the result of composing S 4 times. The next application of i(SSSS) returns the function SSSSSSSS (skipping some steps) and the final application returns SSSSSSSSSSSSSSSS, which is the function in which you apply S to an argument, then apply S to the result, then keep doing that 16 times. Finally, we apply this function to the argument 0, S(0) = 1, S(that) = 2, S(that) = 3, 16 times = 16.

So now, just when you think you might understand this, consider the following questions. In class we saw that the theory behind functional languages (lambda calculus) admits recursive functions which grow on each application rather than shrink. Looking back at my explanation, we see that we started with twice twice twice S 0, and finally got to a point where we had i(i(i(i(S 0)))), which, substituting twice back in for i, is twice(twice(twice(twice(S 0)))). Why isn't this one of those growing recursive calls. It looks like we added an instance of twice. Why didn't the evaluation of this intermediate value result in an even bigger function? The answer is the parentheses. Normally function application is left associative. Notice that the parentheses in this expression effectively make it right associative. At this stage in the computation, each application of twice makes that copy of it go away, replaced by some number of S's. This is why, at the very beginning of this explanation, where I show the expansions at each stage, I included full parentheses.

6. (10 points) The following ML function (from Harper) reverses the elements in a list:
   
   fun rev nil = nil 
     | rev (h::t) = rev t @ [h]
   
   The following LISP program (written in a pretty standard LISP notation) reverses a list as well:
   
   (defun reverse (l) (rev nil l))
   
   (defun rev (out in)
          (cond ((null in) out)
          (t (rev (cons (car in) out) (cdr in))))))
   
   Compare and contrast these definitions of reverse.
   

Solution:

• Both are recursive
• Both successively peel elements off the argument list and add them to their output one element at a time.
• Lisp version is tail recursive. ML version is not
• Lisp version is O(n), ML version is O(n^2)
• ML uses pattern matching, while lisp uses standard LISP syntax for a conditional. You can argue over which is more readable.
Several people seemed to think that lisp couldn't do it with one function, or that something about the languages restricted the way reverse could be implemented. (This lost you some points.) Here are the same two functions, but with languages switched. Also, several people complained that the lisp version was hard to read with all those parens. I agree, but it was also because the formatting wasn't great, hopefully the version below is (a little) better. (This didn't cost any points.)

fun revHelper out nil = out
  | revHelper out (h::t) =  revHelper (h::out) t;

fun rev l = revHelper nil l;

(defun reverse (l)
  (cond
     ((null l)  nil)
     (t         (reverse (append (cdr l) (list (car l)))))))

One final note on tail recursive functions. You may recall from our discussion of scheme that the language requires tail recursive functions to be implemented as efficiently as iteration. Also, there were some homeworks which mentioned the "big jump" at the end of a tail recursive process, allowing you to skip all the intermediate recursive returns. Well, it's even easier than that. A tail recursive function can be implemented (by the compiler) by simply making all recursive calls simply replace the contents of the parameters in the stack frame and jumping to the beginning of the function. You don't even need to allocate a new stack frame for the recursive call. Remember, since you'll never do anything with any of the intermediate recursive calls, none of their local state needs to be remembered. So the tail recursive function

fun last nil = nil 
  | last (h::nil) = h 
  | last (h::t) = last t;

Can be compiled into something resembling the following psuedo machine-code (where arg_1 is the first (and only) argument on the stack frame and contains a pointer to the cons cell at the front of the list being passed in.)

:top
if arg_1 = nil then           # handle last nil case
   return nil
else if arg_1.next = nil then # handle last (h::nil) case
   return arg1
else                          # handle recursive case
   arg1 = arg1.next           # notice that all that needs to be done is
   goto top                   # to change arg1 (essentially simulating a new
end;                          # function call with different args) and jump
                              # back to the top, like an iterative loop would

7. Implement and test any three of the following ML functions (10 points each)
   
   1. Write a function tails that returns a list of lists consisting of the list, and its tails. Examples:
      
      tails [] = []
      tails [1,2,3] = [[1,2,3],[2,3],[3]]
      

      Solution:
      fun tails nil = []
        | tails (h::t) = [h::t] @ tails(t);
      

   2. Write a function deleteSecond that takes an item and a list and returns a list just like the argument list, but with the second occurrence of the item (if any) removed. Examples:
      
      deleteSecond 1 [1,2,3,2,1,3,2,1] = [1,2,3,2,2,3,2,1]
      deleteSecond 4 [1,2,3,2,1,3,2,1] = [1,2,3,2,1,3,2,1]
      deleteSecond 3 [1,2,3] = [1,2,3]
      
      

      Solution:
      fun deleteFirst(item, nil) = nil
        | deleteFirst (item, (h::t)) =
             if (item = h) then
                 t
             else
                 h::deleteFirst(item, t);
      
      fun deleteSecond (item, nil) = nil
        | deleteSecond (item, (h::t)) =
            if item = h then
                h::deleteFirst(item, t)
            else
                h::deleteSecond(item, t);
      

      Note: you could make deleteFirst a local function accessible only to deleteSecond using let, but I thought it was a useful enough function on its own to make top-level.

   3. Write a function notRepeating that takes a list and returns a list leaving only the elements that aren't repeating. Examples:
      
      notRepeating [1,2,3,2,1,3,2,1] = []
      notRepeating [1,2,3,3,2,4] = [1,4]
      notRepeating [1,2,3,3,4] = [1,2,4]
      
      

      Solution:
      fun member(item, nil) = false
        | member(item, (h::t)) =
            if item = h then
                true
            else
                member(item, t);
      
      fun remove(item, nil) = nil
        | remove(item, (h::t)) = 
          if item = h then
             remove(item, t)
          else
             h::remove(item, t);
      
      fun nonRepeatingHelper(nil, seen, retval) = retval
        | nonRepeatingHelper((h::t), seen, retval) = 
            if member(h, seen) = true then
                nonRepeatingHelper(t, seen, remove(h, retval))
            else
                nonRepeatingHelper(t, h::seen, h::retval);
      
      fun nonRepeating(list) = rev(nonRepeatingHelper(list, nil, nil));
      

      Note: I'm assuming the function rev has been defined as in question 6.

   4. Write a function onlyRepeating that takes a list and returns a list leaving only the elements that do repeat. Examples:
      
      onlyRepeating [1,2,3,2,1,3,2,1] = [1,2,3]
      onlyRepeating [1,2,3,3,2,4] = [1,2,3]
      onlyRepeating [1,2,3,3,4] = [3]
      onlyRepeating [1,2,3,4,5] = []
      

      Solution:
      fun member(item, nil) = false
        | member(item, (h::t)) =
            if item = h then
                true
            else
                member(item, t);
      
      fun onlyRepeatingHelper(nil, seen, retval) = retval
        | onlyRepeatingHelper((h::t), seen, retval) = 
            if member(h, seen) = true andalso member(h,retval) = false then
                onlyRepeatingHelper(t, seen, h::retval)
            else
                onlyRepeatingHelper(t, h::seen, retval);
      
      fun onlyRepeating(list) = onlyRepeatingHelper(list, nil, nil);
      

   5. Write a function countOccur that takes a list and returns a count of the number of repeated occurrences. Examples:
      
      countOccur [1,2,3,2,1,3,2,1] = [(1,3),(2,3),(3,3)]
      countOccur ["a","a","b"] = [("a",2),("b",1)]
      

      Solution:
      (* My history as a lisp hacker is made apparent here.  In LISP, *)
      (* an association list is a list of duples, in this case, it's a *) 
      (* list of  duples of the form (item, count).  This function *)
      (* takes an item and an association list of the appropriate form *)
      (* and returns an association list where the tuple for item has *)
      (* had its count incremented *)
      fun assocIncrement(item, nil) = [(item,1)]
        | assocIncrement(item, ((key, count)::t)) =
          if (item = key) then
             (key, count + 1)::t
          else 
             (key, count)::assocIncrement(item, t);
      
      fun countOccurHelper(nil, counts) = counts
        | countOccurHelper((h::t), counts) =
          countOccurHelper(t, assocIncrement(h, counts));
      
      fun countOccur list = countOccurHelper(list, nil);
      

   6. Write a function composeList that takes a list of functions and returns a function that is their composition. Examples:
      
      composeList [] [1,2,3] = [1,2,3]
      composeList [tail,tail,tail] [1,2,3,4,5] = [4,5]
      composeList [(fn x=>x+1),(fn x=>x+2)] 4 = 7
      
      composeList [] is the identity function.
      

   Solution:
   fun composeList (nil, arg) = arg
     | composeList ((h::t), arg) = composeList(t, h(arg));
   

8. (Extra fun, no extra credit) In any language you chose, write a self-replicating program. That is, write a program that takes no input and produces itself exactly as output. (Your program must contain at least one executable statement.)

Solution:

A couple of people had answers for PERL. There are obvious and easy answers for functional languages.

Scheme:
()
#t
#f
(lambda (f) (f f)) (lambda (f) (f f))

ML:
()
[]
something like:
(val f = fn x => x x) (val f = fn x => x x)

PERL: (Although I feel this is cheating, as it reads from file,
which is like input)
#!/usr/bin/perl
open(SRC, $0);
print <SRC>;

A very impressive C example:
char*s="char*s=%c%s%c;main(){printf(s,34,s,34);}";main(){printf(s,34,s,34);}

	Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to notkin@cs.washington.edu]