CSE583 Assignment 1 (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.]
   
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.
   
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.)
   
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. 
   
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.
   
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],[]]
      
   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]
      
      
   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] = [4]
      notRepeating [1,2,3,3,4] = [1,2,4]
      
      
   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] = []
      
   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] = [(3,1),(3,2),(3,3)]
      countOccur [3.5,3.5,9.5] = [(3.5,2),(9.5,1)]
      
   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.
      
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.)

	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]