git clone homework.cs.tufts.edu:/comp/105/build-prove-compare

9. Collection Protocols. Do Exercise 9 on page 986 of Ramsey.

30(a). Interfaces as Abstraction Barriers. Do Exercise 30(a) on page 991 of Ramsey. When the problem says “Arrange the Fraction and Integer classes”, the text means to revise one or both of these classes or define a related class. Think about protocols, not implementation.

Put your solution in file frac-and-int.smt. At minimum, your solution should support addition, subtraction, multiplication, so include at least one unit test for each of these operations.

Hints:

• In a system with abstract data types, you can’t easily mix integers and fractions; they have different types. But in an object-oriented system with behavioral subtyping, you just have to get one object to “behave like” another—which means implementing its protocol. In some cases, this might include implementing private methods.

• If you change Integer, this change doesn’t affect SmallInteger, which continues to inherit from the original version of Integer. So if you change Integer, count on changing SmallInteger as well.

(class Similarity Object
  ()
  (class-method has:to: (ms ns)
    (locals i n equivalent)
    (set n (size ms))
    (if (!= n (size ns))
        {false}
        {(set i 1)
         (set equivalent true)
         (while {(and: equivalent {(<= i n)})}
            {(ifTrue:ifFalse: (!= (at: ms i) (at: ns i))
                {(set equivalent false)}
                {(set i (+ i 1))})})
         equivalent})))

-> (val ns (new List))
List( )
-> (add: ns 1)
-> (add: ns 2)
-> (add: ns 3)
-> ns
List( 1 2 3 )
-> (= ns ns)
<True>
-> (= ns #( 1 2 3 ))
<False>
-> (has:to: Similarity ns #( 1 2 3 ))
<True>

(method digit: (i)
   (at:ifAbsent: digits (+ i 1) {0}))
(method digit:put: (i d)
   (at:put: digits (+ i 1) d))

32. Implementing arbitrary precision natural numbers. Do Exercise 32 on page 991 of Ramsey. Modify the protocol given in the assignment according to these instructions:

• As in the previous assignment, your div: method need only divide a Natural by a small integer, not by another Natural.

• Add to the protocol the method decimal described in Figure 11.21. This method answers a list of decimal digits that represent the number. As in the previous assignment, the decimal method will be used for testing.

The algorithms are the same algorithms you would have used on the sml assignment. And although the book assumes you will represent a natural number using an array, you are free to use a list of digits instead. Just be aware that unlike Standard ML, μSmalltalk has no immutable list abstraction. If you want immutable lists, you will have to simulate them yourself. For example, you could try using the Cons and Nil classes that are already defined, along with the isNil message that is defined on every object.

Please do adapt your code from the sml assignment. Or if you prefer, you may adapt my solutions. Just be sure to attribute the source for whatever code you adapt.

How big is it? My solution for the Natural class, using the array representation and the hints in the book, is over 100 lines of μSmalltalk code.

33. Implementing arbitrary precision integers. Do Exercise 33 on page 994 of Ramsey. You need not implement the div: method. But in order to facilitate testing, you must implement a decimal method like the one you implemented on class Natural. An implementation is shown in the bignums handout.

Because you build large integers on top of Natural, you don’t have to think about array or list representations any more. Instead you must focus on dynamic dispatch and on getting information from where it is to where it is needed.

How big is it? My solutions for the large integer classes are 22 lines apiece.

34. Modifying SmallInteger so operations that overflow roll over to infinite precision. Do Exercise 34 on page 994 of Ramsey.

You must modify SmallInteger without editing the source code of the μSmalltalk interpreter. To do so, you will redefine class SmallInteger using the idiom on page 995:

     (class SmallInteger SmallInteger
        ()
        ... new method definitions ...
     )

This idiom modifies the existing class SmallInteger; it can both change existing methods and define new methods. This code changes the basic arithmetic operations that the system uses internally. If you have bugs in your code, the system will behave erratically. At this point, you must restart your interpreter and fix your bugs. Then use the idiom again.

How big is it? My modifications to the SmallInteger class are about 25 lines.

T. Testing Bignums. You will write 9 tests for bignums:

• 3 tests will test only class Natural.
• 3 tests will test the large-integer classes, which are built on top of class Natural.
• 3 tests will test mixed arithmetic and comparison involving both small and large integers.

Each test will have the same structure:

1. The test will begin with a summary characterization of the test in at most 60 characters, formatted on a line by itself as follows:

        ; Summary: .........

   The summary must be a simple English phrase that describes the test. Examples might be “Ackermann’s function of (1, 1),” “sequence of powers of 2,” or “combinations of +, *, and - on random numbers.”

2. Code will compute a result of class Natural, LargePositiveInteger, or LargeNegativeInteger. The code may appear in a method, a class method, a block, or wherever else you find convenient.

3. The expected result will be written as a literal array, like one of the following:

   #( 1 2 3 9 4 9 )
   #( - 6 5 5 3 6 )

4. The test itself will send the decimal message to the computed result, then compare the decimal representation with the literal array. Comparison will use class method has:to: on class Similarity.

5. Finally, the comparison will appear in a check-expect, expecting the result of has:to: to be true.²

Each test must take less than 2 CPU seconds to evaluate.

Here is a complete example:

; Summary: 10 to the tenth power, mixed arithmetic
(class Test10Power Object
  ()
  (class-method run: (power)
     [locals n 10-to-the-n]
     (set n 0)
     (set 10-to-the-n 1)
     (whileTrue: {(< n power)}
         {(set n (+ n 1))
          (set 10-to-the-n (* 10 10-to-the-n))})
     10-to-the-n)
)
(check-expect (has:to: Similarity (decimal (run: Test10Power 10))
                                  #( 1 0 0 0 0 0 0 0 0 0 0)) 
              true)

Here is another complete example:

; Summary: 20 factorial
(define factorial (n)
  (ifTrue:ifFalse: (strictlyPositive n) 
     {(* n (value factorial (- n 1)))}
     {1}))

(check-expect (has:to: Similarity (decimal (value factorial 20))
                                  #( 2 4 3 2 9 0 2 0 0 8 1 7 6 6 4 0 0 0 0 ))
              true)

A simple sanity check

As a test, the factorial function has grave limitations:

• Factorial only ever multiplies numbers. It does not add, subtract, negate, or compare numbers.

• Factorial never multiplies two large numbers. It only ever multiplies a large number by a small number, or two small numbers.

These properties of factorial make it a poor test of correctness, but they do make it a good initial sanity check. Here, for example, is code that computes and prints factorials:

(class Factorial Object
  ()
  (class-method printUpto: (limit) [locals n nfac]
     (set n 1)
     (set nfac 1)
     (whileTrue: {(<= n limit)}
        {(print n) (print #!) (printu 32) (print #=) (printu 32) (println nfac)
         (set n (+ n 1))
         (set nfac (* n nfac))})))

As a sanity check sending (printUpto: Factorial 25) should print the following table of factorials:

     1! = 1
     2! = 2
     3! = 6
     4! = 24
     5! = 120
     6! = 720
     7! = 5040
     8! = 40320
     9! = 362880
    10! = 3628800
    11! = 39916800
    12! = 479001600
    13! = 6227020800
    14! = 87178291200
    15! = 1307674368000
    16! = 20922789888000
    17! = 355687428096000
    18! = 6402373705728000
    19! = 121645100408832000
    20! = 2432902008176640000
    21! = 51090942171709440000
    22! = 1124000727777607680000
    23! = 25852016738884976640000
    24! = 620448401733239439360000
    25! = 15511210043330985984000000

More advice about testing natural numbers

Try testing your class Natural by generating a long, random string of digits, then computing the corresponding number using a combination of addition and multiplication by 10.

If you don’t have multiplication working yet, you can use the following sequence to multiply by 10:

(set p n)       ; p == n
(set p (+ p p)) ; p == 2n
(set p (+ p p)) ; p == 4n
(set p (+ p n)) ; p == 5n
(set p (+ p p)) ; p == 10n

This idea will test only your addition; if you have bugs there, fix them before you go on.

You can write, in μSmalltalk itself, a method that uses the techniques above to convert a sequenceable collection of decimal digits into a natural number.

Once you are confident that addition works, you can test subtraction of natural numbers by generating a long random sequence, then subtracting the same sequence in which all digits except the most significant are replaced by zero.

You can create more ambitious tests of subtraction by generating random natural numbers and using the algebraic law (m + n)−m = n. You can also check to see that unless n is zero, m − (m + n) causes a run-time error on class Natural.

It is harder to test multiplication, but you can at least use repeated addition to test multiplication by small values. The timesRepeat: method is defined on any integer.

You can also easily test multiplication by large powers of 10.

You can use similar techniques to test large integers.

If you want more effective tests of multiplication and so on, compare your results with a working implementation of bignums. The languages Scheme, Icon, and Haskell all provide such implementations. (Be aware that the real Scheme define syntax is slightly different from what we use in uScheme.) We recommend you use ghci on the command line; standard infix syntax works. If you want something more elaborate, use Standard ML of New Jersey (command sml), which has an IntInf module that implements bignums.

Other hints and guidelines

Start early. Seamless arithmetic requires in-depth cooperation among about eight different classes (those you write, plus Magnitude, Number, Integer, and SmallInteger). This kind of cooperation requires aggressive message passing and inheritance, which you are just learning. There is a handout online with suggestions about which methods depend on which other methods and in what order to tackle them.

For your reference, Dave Hanson’s book discusses bignums and bignum algorithms at some length. It should be free online to Tufts students. You can think about borrowing code from Hanson’s implementation (see also his distribution). Be aware though that your assignment differs significantly from his code and unless you have read the relevant portions of the book, you may find the code overwhelming.

• In Hanson’s code, XP_add does add with carry. XP_sub does subtract with borrow. XP_mul does z := z + x * y, which is useful, but is not what we want unless z is zero initially.
• Hanson passes all the lengths explicitly, which would not be idiomatic in μSmalltalk.
• Hanson’s implementation uses mutation extensively, but the class Natural is an immutable type. Your methods must not mutate existing natural numbers; you can mutate only a newly allocated number that you are sure has not been seen by any client.

If you do emulate Hanson’s code, acknowledge him in your README file.

Avoid common mistakes

Below you will find some common mistakes to avoid.

Extra credit

Seamless bignum arithmetic is an accomplishment. But it’s a long way from industrial. The extra-credit problems explore some ideas you would deploy if you wanted everything on a more solid foundation.

What and how to submit: Individual problems

Submit these files:

• A README file containing
  • The names of the people with whom you collaborated
  • The numbers of the problems that you solved
  • The number of hours you worked on the assignment.

• A file cqs.small.txt containing your answers to the reading-comprehension questions

• A file finhist.smt showing your solution to Exercise 9.

• A file frac-and-int.smt showing whatever definitions you used to do Exercise 30(a). It probably includes new definitions (or redefinitions) of one or more of these classes: Fraction, Integer, and SmallInteger. And it most definitely includes at least four unit tests.

Please identify your solutions using conspicuous comments, e.g.,

     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     ;;;;
     ;;;;  Solution to Exercise 9
     (class Array ...
      )

As soon as you have the files listed above, run submit105-small-solo to submit a preliminary version of your work. Keep submitting until your work is complete; we grade only the last submission.

What and how to submit: Pair problems

Submit these files:

• A README file containing
  • A description of how you tested your bignum code
  • The names of the people with whom you collaborated
  • The numbers of the problems that you solved (including any extra credit)
  • Narrative and measurements to accompany your extra-credit answers, if any
• A file bignum.smt showing your solutions to Exercises 32, 33, and
  34. This file must work with an unmodified usmalltalk interpreter. Therefore if you use results from Exercise 30(a), or any other problem, you will need to duplicate those modifications in bignum.smt.
• A file bigtests.smt containing your solution to Exercise T.

As soon as you have the files listed above, run submit105-small-pair to submit a preliminary version of your work. Keep submitting until your work is complete; we grade only the last submission.

How your work will be evaluated

All our usual expections for form, naming, and documentation apply. But in this assignment we will focus on clarity and structure. To start, we want to be able to understand your code.

Structurally, your code should hide information like the base of natural numbers, and it should use proper method dispatch, not bogus techniques like run-time type checking.