Machine Problem 1: Programming Inductively

Out: Thursday, January 10, 2008

Due: 5 PM Monday, January 21, 2008 (originally January 18, 2008)

Submission: Partners

This assignment is to be done in pairs. If you have not found a partner to work with by the time you hand in MP0, contact your instructor.

The main goal of this assignment is to write programs that process data according to inductive data definitions. A secondary goal is to explore mappings between abstract objects and their representations, and how such mappings relate to program specification and implementation. By the end of this assignment, you should be able to:

• Write programs that perform queries on lists, trees, and other recursive data structures
• Write programs that perform transformations on recursive data structures
• Write programs that process concrete representations of mathematical abstractions such as sequences.

Tasks

1. [12pts] EoPL exercises 1.15, 1.16, 1.18, 1.20, 1.23, 1.27.

   Define the functions in a module named mp1; Provide the six functions from the module (in the sense of the PLT Scheme provide special form), and save the mp1 module definition in a file named mp1.scm.

   Each of the six functions and the extra tests you add to exercise that function will count 2 points each, for a total of 12 points.

   Here is the source for a module, mp1-test (which requires "mp1.scm", implemented by you above, as well as "drscheme-init.scm", linked here), where the staff has transcribed the examples from the book into tests.

   (module mp1-test (lib "eopl.ss" "eopl")
     (require "drscheme-init.scm")
     (require (only "mp1.scm" 
                    duple invert swapper count-occurrences list-index flatten
                    ))
   
     (stop-after-first-error #f) ; (use #t stop testing after failure)
   
     ;; test : Symbol (A B ... -> Z) (list A B ...) Z -> void or error
     ;; usage: (test nm fcn args ans) applies fcn to args; if the 
     ;;        result is not equal to ans, then signals a test failure.
   
     (define test
       (lambda (name function args result)
         (let* ((t (run-experiment function args result equal?))
                (was-a-success (car t))
                (answer-given (cdr t)))
           (cond
             (was-a-success (eopl:printf "Success on test ~a~%" (cons name args)))
             (else
              (cond ((stop-after-first-error) 
                     (eopl:error name
                                 "~a evaluated to ~a, but we want: ~a" 
                                 (cons name args) answer-given result))
                    (else
                     (eopl:printf 
   		  "Failure on test ~a; evaluated to ~a, but we want: ~a~%"
                     (cons name args) answer-given result)
                     )))))))
     
     ;; These two definitions are intended to clarify the roles of the
     ;; arguments in the tests below for *beginning* Scheme programmers.
     ;; Once you are comfortable programming in Scheme, you should not
     ;; need such crutches!
     
     (define test-arguments list)
     (define expects-result
       (lambda (x) x))
   
     ;; EOPL 1.15
     
     (test 'duple duple
           (test-arguments 2 3)
           (expects-result '(3 3)))
     
     (test 'duple duple
           (test-arguments 4 '(ha ha)) 
           (expects-result '((ha ha) (ha ha) (ha ha) (ha ha))))
   
     (test 'duple duple
           (test-arguments 0 '(blah))
           (expects-result '()))
     
     ;; EOPL 1.16
   
     (test 'invert invert
           (test-arguments '((a 1) (a 2) (1 b) (2 b)))
           (expects-result '((1 a) (2 a) (b 1) (b 2))))
   
     ;; EOPL 1.18
     
     (test 'swapper swapper
           (test-arguments 'a 'd '(a b c d))
           (expects-result '(d b c a)))
   
     (test 'swapper swapper
           (test-arguments 'a 'd '(a d () c d))
           (expects-result '(d a () c a)))
   
     (test 'swapper swapper 
           (test-arguments 'x 'y '((x) y (z (x))))
           (expects-result '((y) x (z (y)))))
     
     ;; EOPL 1.20
   
     (test 'count-occurrences count-occurrences
           (test-arguments 'x '((f x) y (((x z) x))))
           (expects-result 3))
     
     (test 'count-occurrences count-occurrences
           (test-arguments 'x '((f x) y (((x z) () x))))
           (expects-result 3))
     
     (test 'count-occurrences count-occurrences
           (test-arguments 'w '((f x) y (((x z) x))))
           (expects-result 0))
   
     ;; EOPL 1.23
   
     (test 'list-index list-index
           (test-arguments number? '(a 2 (1 3) b 7))
           (expects-result 1))
     
     (test 'list-index list-index 
           (test-arguments symbol? '(a (b c) 17 foo))
           (expects-result 0))
   
     (test 'list-index list-index
           (test-arguments symbol? '(1 2 (a b) 3))
           (expects-result #f))
   
     ;; EOPL 1.27
   
     (test 'flatten flatten
           (test-arguments '(a b c))
           (expects-result '(a b c)))
     
     (test 'flatten flatten
           (test-arguments '((a) () (b ()) () (c)))
           (expects-result '(a b c)))
     
     (test 'flatten flatten 
           (test-arguments '((a b) c (((d)) e)))
           (expects-result '(a b c d e)))
   
     (test 'flatten flatten
           (test-arguments '(a b (() (c))))
           (expects-result '(a b c)))
   
     )
     

   Extend mp1-test with any additional tests you create during your development.

The remaining tasks will involve a particular data definition for processing sequences of integers.

A common class of data used in programming is the class of finite length sequences of integers. While a Listof[Integer] is an obvious choice of representation for this kind of data, some applications may prefer a different representation.

Consider the following data definition:

;; A IntegerSequence is one of
;; - '()
;; - (cons (cons Nat Integer) IntegerSequence)
;; with the representation invariant that there is no IntegerSequence
;; ((k1 . n1) (k2 . n2) . seq) such that n1 = n2.
;; 
;; interpretation: 
;;   The empty list () is an empty sequence.
;;   The pair ((k . num) . s) is the sequence of k copies of num followed by 
;;                               the sequence represented by s.

2. [1 pt] In the mp1 module, define and provide a variable two-even-one-odd-upto-six that corresponds an IntegerSequence representation of the following sequence of twelve integers 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 6.
3. [2 pt] This is a short answer question; write your answer in a text file, mp1.txt, and clearly mark it as the answer for question 3. Is there any finite sequence of integers that has more than one IntegerSequence representation?
   • If so, write "Yes, these two lists represent the same sequence", followed by the two representations and the one sequence they represent.
   • If not, then consider what would happen if we were to remove the representation invariant provided with the data definition for IntegerSequence. Would there then be a sequence that has multiple representations? If so, write "Yes, these two lists would be representations of the same sequence if we ignore the represenation invariant", followed by the two lists and the one sequence they would represent.
   • If you did not write anything for the above two bullets, write "No two lists represent the same sequence, regardless of the representation invariant", and explain your reasoning.
4. [1 pt] This is a short answer question; write your answer in the mp1.txt text file, and clearly mark it as the answer for question 4. Question: You come across a function, intseq-append, that is supposed to consume two IntegerSequences and return a single sequence that is the concatenation of the input sequences. The function's author claims that the following implementation is sufficient.

   ;; intseq-append : IntegerSequence IntegerSequence -> IntegerSequence
   ;; usage : (intseq-append [x1 x2 x3 ...xi] [xi+1 xi+2... xn])
   ;;         returns [x1 x2 x3 ... xi xi+1 xi+2 ... xn]
   
   (define (intseq-append s1 s2)
     (append s1 s2))
   
   ;; Examples/Tests for intseq-append
   
   (equal? (intseq-append '() '()) ; [] ++ [] == []
           '())
   (equal? (intseq-append '((3 . 2) (1 . 1))   ;    [2 2 2 1] ++ [6 7 7] 
                          '((1 . 6) (2 . 7)))  ; == [2 2 2 1 6 7 7]
           '((3 . 2) (1 . 1) (1 . 6) (2 . 7)))
   (equal? (intseq-append '((5 . 1)) '((2 . 6))) ;    [1 1 1 1 1] ++ [6 6]
           '((5 . 1) (2 . 6)))                   ; == [1 1 1 1 1 6 6]
     

   Prove the author of intseq-append incorrect by providing an example input for intseq-append where the current implementation misbehaves and explain why the author's implementation is incorrect for the example.
5. [4 pts] Define a function, longest-runs, which takes an IntegerSequence and returns a list of the integers which have the longest runs in the sequence. (A run in an integer sequence is a subsequence of more than one consecutive identical numbers; thus the longest run in two-even-one-odd-upto-six is the number 6.)

   Before you start working on the design of longest-runs, ask yourself why this function needs to return a list of integers rather than just one integer. Make sure you come up with examples that exercise such behavior in your implementation of longest-runs.

Your deliverables are:

1. A PLT Scheme module "mp1.scm". The module should be written in the language (lib "eopl.ss" "eopl").

   This means that top of your module definition should look like the following

   (module mp1 (lib "eopl.ss" "eopl") 
      ...)
   

   which in PLT Scheme is how one indicates the body of the mp1 module is written using the language (lib "eopl.ss" "eopl").
2. A PLT Scheme module "mp1-test.scm". The module should be written in the language (lib "eopl.ss" "eopl"), require the modules "drscheme-init.scm" and "mp0.scm", and continue to run the tests it started with.
3. The output from the tests, named mp1-test-output.txt. One way of doing this is to take the contents of the DrScheme interaction window and paste it into a fixed-width text processor. There is also a "Save Interactions as Text..." command, under the "Save Other" submenu of DrScheme's File menu.

   Whatever technique you use, make sure you double-check that the submission is just plain text and that it matches the output you see when you run the mp1-test module.

4. The file mp1.txt (referenced in questions 3 and 4).
5. A Development Diary

Back to Machine Problems