Overview
Object-oriented programming has been popular since the 1990s, and like lambdas, object-oriented features are found everywhere. But these features are not always easy to tease out: many object-oriented languages, such as Java and C++, are hybrids, which mix objects with abstract data types or other notions of encapsulation and modularity. When you don’t already know how to program with objects, hybrid designs are more confusing than helpful. For that reason, we study pure objects, as popularized by Smalltalk: even simple algorithms send lots of messages back and forth among a cluster of cooperating, communicating objects. Popular languages that use similar models include Ruby, JavaScript, Objective C, and Swift.
The assignment is divided into three parts.
Part 1: You begin with reading comprehension.
Part 2: You do a small warmup problem, which acquaints you with pure object-oriented style and with μSmalltalk’s large initial basis.Part 3: You implement bignums in μSmalltalk. You will implement both natural numbers and signed integers. You will also use object-oriented dispatch to implement “mixed arithmetic” of large and small integers—a useful abstraction that demonstrates the “open” nature of true object-oriented systems.
This assignment is time-consuming. Many students have experience in languages called “object-oriented,” but few students have experience with the extensive inheritance and pervasive dynamic dispatch that characterize idiomatic Smalltalk programs.
Setup
The μSmalltalk interpreter is in /comp/105/bin/usmalltalk
. Many useful μSmalltalk sources are included the book’s git repository, which you can clone by
git clone homework.cs.tufts.edu:/comp/105/build-prove-compare
Sources that can be found in the examples/usmalltalk
directory include copies of predefined classes, collection classes, shape classes, and other examples from the textbook—including templates for both large integers and natural numbers.
Getting to know μSmalltalk interactively
Smalltalk is a little language with a big initial basis; there are lots of predefined classes and methods. To help you work with the big basis, as well as to debug your own code, we recommend sending the messages printProtocol
and printLocalProtocol
. These messages, which are shown in Figure 10.10 on page 648, are understood by every uSmalltalk class. They provide a quick way to remind yourself what messages an object understands and how the message names are spelled.
One indirect way to learn a protocol is to send an object every message in its protocol, just to see what happens. You might get a stack trace, but that will help you learn.
Assembling documentation for the assignment
The information you need is spread out over multiple sources:
This handout explains everything you are expected to deliver, and it collects hints and other supplementary information.
The main textbook explains how Smalltalk works, and it has the protocols of all the classes and the contracts of all the methods—including the protocols and contracts of methods that you are expected to implement.
The handout “Mastering Multiprecision Arithmetic” explains the algorithms for the arithmetic used in this assignment and the
sml
assignment.The Smalltalk bignums handout goes deep into the details of implementing bignums using objects. It focuses on objects and inheritance, not on algorithms.
The section on diagnostic technique describes some tools that can help you debug your code.
Reading comprehension (10 percent)
These problems will help guide you through the reading. We recommend that you complete them before starting the other problems below. You can download the questions.
Receivers, arguments, and message names. Read the first eleven pages of chapter 10, through the end of section 10.1.4. Now examine these expressions from the definition of class
Picture
, in figure 10.4 on page 627:(shapes add: aShape) (shape drawOn: aCanvas) (shapes do: [block (shape) (shape drawOn: aCanvas)])
In each expression, please identify the receiver, the argument, and the message name:
In
(shapes add: aShape)
,- The receiver is …
- The argument is …
- The message name is …
In
(shape drawOn: aCanvas)
,- The receiver is …
- The argument is …
- The message name is …
In
(shapes do: [block (shape) (shape drawOn: aCanvas)])
,- The receiver is …
- The argument is …
- The message name is …
You can now start to read code examples.
Colons in message names. Now move on to class
TikzCanvas
, which is described in Figures 10.5 and 10.6 on page 628. In both the protocol and the implementation, methodstartDrawing
has no colon in the name, methoddrawPolygon:
has one colon in the name, and methoddrawEllipseAt:width:height:
has three colons in the name.What, if anything, does the number of colons have to do with receivers?
Your answer: …
What, if anything, does the number of colons have to do with arguments?
Your answer: …
If you need to, review the presentation in section 10.1.1 on “Objects and Messages,” which shows messages sent to shapes.
You now know what a message’s name tells you about how to use it.
Class protocols and instance protocols. Every message is part of some protocol. As example messages, study the transcript in code chunks 622b and 622c, which puts three shapes into a picture and then draws the picture.
Of the message names used in the transcript, which ones are part of the class protocol for
Picture
?Which message names are part of the instance protocol for
Picture
?Which message names are part of the class protocol for
TikzCanvas
?Which message names are part of the instance protocol for
TikzCanvas
?In general, what do you do with messages in a class protocol, and how does that differ from what you do with messages in an instance protocol?
You now know what you can do with each kind of message described in the chapter.
Dynamic dispatch, part I: A toy class. For the mechanisms of message send and dynamic dispatch, read section 10.3.4, which starts on page 641. Using the class definitions in that section, message
m1
is sent to an object of classC
. What method definitions are dispatched to, in what order?Please edit this answer to put in the correct methods and classes:
- Dispatch to method m1 on class ?
- Dispatch to method ? on class ? …
You are starting to understand the key mechanism behind all of object-oriented programming.
Dynamic dispatch, part II: Conditionals? What conditionals? Read section 10.5 starting on page 662 in its entirety. (It is about one page.)
Now study this transcript:
-> ('hello isNil) <False> -> (nil isNil) <True> -> ('hello class) <class Symbol> -> (('hello class) superclass) <class Object> -> (nil class) <class UndefinedObject> -> ((nil class) superclass) <class Object>
Answer these two questions:
Explain how it is possible that the
isNil
method can be implemented without an equality test and without any explicit conditional test (like anif
). Your explanation should include a statement of what messages are sent to what objects and what method definition each message dispatches to.Explain why it is desirable to implement object-oriented code without explicit conditional tests, and indeed, without ever asking an object, “how were you formed?”
You are starting to learn how to work effectively in a world where we don’t interrogate objects to see how they were formed or what class they are.
Dynamic dispatch, part III: Number classes. Familiarize yourself with the protocols for magnitudes and numbers, as described in section 10.4.6, which starts on page 658. Now turn to section 10.7, which starts on page 670, and examine the key methods of class
Number
, as well as the implementation of classFraction
are in (section 10.7.2 starting on page 673). Part of classFraction
is relegated to the Supplement, but the only thing you need from there is this implementation of methodnegated
on classFraction
:(method negated () ((Fraction new) setNum:den: (num negated) den))
Now, demonstrate your understanding of dynamic dispatch by explaining what messages are sent when fractions are subtracted.
For example, what messages are sent when we evaluate((1 / 2) - (1 / 3)) ?
The computation dispatches messages to instance methods of classes
Fraction
,Number
, andSmallInteger
, as well as a class method of class Fraction. We are interested in only some of those dispatches—ones that meet both of these criteria:The message is sent from a method defined on class
Fraction
or classNumber
.The message is received by an instance of class
Fraction
or classNumber
.
These criteria rule out class methods of class
Fraction
, messages sent toSmallInteger
, and so on.Starting with what happens when message
-
(minus) is sent to an instance ofFraction
, please identify only the interesting dispatches:Message Sent from method Sent to object Method defined defined on class of class on class - (anywhere) Fraction Number ? Number ? ? ... fill in the ? marks ... ... and complete the rest of this table ...
You are starting to learn how a class can have some of its work done for it by its superclass.
Dynamic dispatch, part IV: Messages to
self
andsuper
. Now study the class methodnew
defined on classList
, which appears in section 10.8, which starts on page 681. The definition sends messagenew
tosuper
. (Keep in mind: becausenew
is a class method, bothsuper
andself
stand for the class, not for any instance.)When class method
new
is executed, what three messages are sent by the method body, in what order? (If you like, you can use the message tracer described under “Diagnostic technique” below, but it is probably easier just to look at the source code.)What does each of the three message sends accomplish?
If we change
new
’s definition so instead of(super new)
it says(self new)
, which of the following scenarios best describes how the changed program behaves?The
new
message will be dispatched to classList
. The same method will run again, and the computation will not terminate.The
new
message will be dispatched to a different class, and the reply to thenew
message will leave the sentinel pointing to the wrong value.Nothing will change; in this example, there’s no difference between
(super new)
and(self new)
.
Your answer: The best description is labeled with letter ?
You are learning how to use
super
to initialize objects.Design of the numeric classes. Read about coercion in section 10.4.6 on page 658. Look at the last part of the instance protocol for
Number
on page 659, which shows the contracts of methodsasInteger
,asFraction
,asFloat
, andcoerce:
. If you are unsure, look at the implementations of these methods on classInteger
, in chunks 678b and 678c.Answer the two questions (a) and (b). Write no English.
Supposing
x
is a variable that holds a number—possibly a floating-point number. In C or C++, you can cast its value toint
by writing(int) x
. In uSmalltalk, what code do you write?…
Now suppose you have a uSmalltalk variable
y
, which also holds a number. You want to addx
andy
, but the contract of the+
message says that it can be used only whenx
andy
have the same representation (both integers, both floats, etcetera). Without interrogating eitherx
ory
to ask what class it is, how can you add them safely? What code do you write?…
You are ready to implement mixed arithmetic, with coercions, in exercise 39.
You are now ready to implement all of the operations on numbers, not just the ones that are familiar from C or C++.
Abstract classes in principle. In section 10.13.1, which starts on page 716 (“Key words and phrases”), you will find a short definition of “abstract class.” What is the purpose of an abstract class? Pick one of the responses below.
To hide the representation of instances so programmers can change internal details without affecting client code
To define methods that other classes inherit, so that subclasses get useful default methods
The same as the purpose of a regular class: to define an abstraction
Your answer: …
You now know what abstract classes are supposed to do, so that when you tackle the homework, you can take advantage of abstract classes like
Magnitude
,Number
, andInteger
.Abstract classes in practice: magnitudes and numbers. Your natural-number class will inherit from abstract class
Magnitude
, and your large-integer code will inherit fromMagnitude
and fromNumber
, which is also an abstract class.Study the implementation of class
Magnitude
(page 665). List all the methods that are “subclass responsibility”:Your answer: ...
These are methods that you must implement in both your
Natural
class and your large-integer classes.On page 672, you will find the definition of class Number, which I will save you the trouble of looking up:
(class Number [subclass-of Magnitude] ; abstract class ;;;;;;; basic Number protocol (method + (aNumber) (self subclassResponsibility)) (method * (aNumber) (self subclassResponsibility)) (method negated () (self subclassResponsibility)) (method reciprocal () (self subclassResponsibility)) (method asInteger () (self subclassResponsibility)) (method asFraction () (self subclassResponsibility)) (method asFloat () (self subclassResponsibility)) (method coerce: (aNumber) (self subclassResponsibility)) <<other methods of class [[Number]]>> )
Your large-integer classes will be subclasses of
Number
. How many of the eightsubclassResponsibility
methods will you have to implement in those classes?Your answer: ...
(Two of these methods,
+
and*
, must also be implemented in classNatural
.)
You now understand in detail what operations your large integers must support.
Double Dispatch. Read section 10.7, which starts on page 670. And read the section “laws for multiple dispatch” in the 7th lesson on program design (“Program Design with Objects”).
Now, of the methods on class
Number
listed in the previous question, list each one that needs to know either of the following facts about its argument (not its receiver):- Whether the argument is large or small
- If the argument is large, whether it is “positive” or “negative”
For example,
+
is such a method.Please list all such methods here:
Your answer: + …
The methods in part (a) are exactly the ones that require double dispatch. The implementation of each such method sends a message to its argument, and the exact message depends on the class of the receiver.
Assume that the receiver is a
LargePositiveInteger
. Please say, for each method in part (a), what message the method implementation sends to the argument.Your answer:
Method
+
sendsaddLargePositiveIntegerTo:
to the argument
…
You are ready to implement arithmetic on large integers (exercise 38).
Individual Problem
Working on your own, please work exercise 36(a) on page 731 of Build, Prove, and Compare. This exercise is a warmup designed to prepare you for the bignum problems in the pair portion of the assignment.
Pair Problems: Bignum arithmetic
For the remaining problems, you may work with a partner. Please work exercise 37 on page 731, exercise 38 on page 732, and exercise 39 on page 732 of Build, Prove, and Compare, and exercises T and ADT below.
Sometimes you want to do computations that require more precision than you have available in a machine word. Full Scheme, Smalltalk, Haskell, Icon, and many other languages provide “bignums,” which automatically expand to as much precision as you need. Unlike languages that use abstract data types, Scheme, Smalltalk, and Icon make the transition from machine integers to bignums transparent—from the source code, it’s not obvious when you’re using native machine integers and when you’re using bignums. You will build transparent bignums in Smalltalk.
Big picture of the solution
Smalltalk code sends lots of messages back and forth, and those messages are dispatched to lots of methods, which are defined on different classes. This model shows both the power of Smalltalk—every method is simple—and a weakness of Smalltalk—every algorithm is smeared out over half a dozen methods defined on different classes, making it hard to debug. But this is the object-oriented programming model that lends power not just to Smalltalk but also to Ruby, Objective-C, Swift, Self, JavaScript, and to a lesser extent, Java and C++. To work effectively in any of these languages, one needs the big picture of which class is doing what. A good starting point is the Smalltalk bignums handout.
Unit testing bignums in Smalltalk
Arithmetic comparisons should be tested using check-assert
in the usual way. But other arithmetic operations can’t easily be tested using check-expect
, because the parser handles only machine integers. You have two options:
Use
check-expect
with thedecimal
method.Use the
check-print
form, which is listed in the textbook but is not otherwise documented.
Using check-expect
The semantics of check-expect
are subtle, but the tests work about the way you would hope. You might remember that in μScheme, check-expect
does not use the built-in =
primitive—instead, it compares values uses something like the equal?
function. This comparison enables μScheme’s check-expect
to accept two different S-expressions that have the same structure. In much the same way, μSmalltalk does not use a primitive equality; instead, it sends the =
message to the checked object.
Using check-expect
with the decimal
method looks like this:
(check-expect ((Power x:to: 10 60) decimal)
'( 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
(check-expect ((Power x:to: 2 64) decimal)
'( 1 8 4 4 6 7 4 4 0 7 3 7 0 9 5 5 1 6 1 6 ))
(check-expect (((Power x:to: 2 64) negated) decimal)
'( - 1 8 4 4 6 7 4 4 0 7 3 7 0 9 5 5 1 6 1 6 ))
Because check-expect
uses the =
method, it can accept a list of decimal digits returned by decimal
as equal to the array written using literal quote syntax—even though the two are not the same object.
Using check-print
Using check-expect
is familiar, but aside from the obvious awkwardness of writing arrays of decimal digits, it has a more serious flaw: it can’t detect bugs in your all-important decimal
method, which supplies digits to print
. To help find such bugs, use the check-print
unit-test form, which takes an expression and a literal result. The literal result must be a single token: either a name or a sequence of digits. Here are some example uses:
(check-print (Power x:to: 10 60)
1000000000000000000000000000000000000000000000000000000000000)
(check-print (Power x:to: 2 64)
18446744073709551616)
(check-print ((Power x:to: 2 64) negated)
-18446744073709551616)
(check-print ((Natural fromSmall: 256492) * (Natural fromSmall: 666481))
170947044652)
As soon as you have a decimal
method working, I recommend using check-print
.
Our unit tests
We provide some unit tests for class Natural
and for bignums. But our tests are not like the unit tests you are used to. We don’t hand-craft each test to exercise a particular method in a particular way. Instead, we use a random-number generator to create relatively big tests that exercise many methods at once—especially the all-important decimal
method. If your code passes our tests, it should give you some confidence. But if your code fails one of our tests, the failure won’t tell you what went wrong. For that reason, our tests are meant to supplement your own unit tests, not to supplant them.
Details of all the problems
37. Implementing arbitrary-precision natural numbers. Do exercise 37 on page 731 of Build, Prove, and Compare. Implement the protocol defined in Figure 10.19 on page 662.
Put your solution in file bignum.smt
.
The book has a starter template for class Natural
, which you can copy and paste (with acknowledgement) from /comp/105/build-prove-compare/examples/usmalltalk/predefined.smt
.
The choice of a base for natural numbers is yours. But for full credit, you must choose a base b such that b > 10, and small enough that (b + 1) ⋅ (b − 1) does not overflow.1
0pt plus 3-200 0pt plus -3
What representation should I use? You’ve got three choices:
Array-based: Every natural number is represented by an array of digits.
List-based: Every natural number is represented by a list of digits, where “list” means the mutable Smalltalk
List
abstraction.Subclass-based: A natural number’s representation depends on its value:
The natural number zero is represented by an instance of concrete class
NatZero
, which represents only zero.A natural number of the form “n times base b plus digit d” is represented by an instance of class concrete class
NatNonzero
, which holds instance variables n and d. Objects of classNatNonzero
represent only nonzero natural numbers, so this class has an invariant that n and d are not both zero.
Both concrete classes should be defined as subclasses of the class
Natural
, which should be an abstract class.
The representations offer these tradeoffs:
The solution based on an array is hardest to get right but easiest to get started. The easy part is that there is no case analysis in the data: every natural number is represented by an array. Hard parts include figuring out array lengths, managing array indices, and making sure not to confuse the index of a digit with the digit itself.
The subclass-based solution, with special subclasses for zero and nonzero numbers, is the easiest to get right but the hardest to get started. The easy part is that every method is specialized, so almost all of the case analysis is handled for you automatically, by method dispatch. The hard part is that you have to understand method dispatch.
A solution based on a mutable
List
is possible in principle, but we recommend against it.
In our opinion, the subclass-based solution is clearly superior. (As a bonus, this representation is also the best at helping you learn about programming with objects.) This representation makes it easy for me to understand my own code: I can look at any method, and I am confident that I understand exactly what it is doing. The array and list representations don’t give me that confidence.
How must I document my representation?
For any choice of representation, it is useful to explicitly document an abstraction function that maps the representation to the value it represents, and an invariant predicate that returns true when applied to a representation iff the representation satisfies the expected invariants. In your submission, you must document the abstraction function and invariant for every concrete class. (A concrete class is one that is instantiated by sending it the new
message, or by sending some other message whose method eventually sends new
.)
Document the abstraction function by writing, in a comment, an equation
A (self) = ...
and using instance variables on the right-hand side.
Document the invariant either by writing a comment like
I (self) = ...
or by defining a private
invariant
method that answers a Boolean.
In each class, place your comments immediately below or to the right of the declaration of the instance variables.
What algorithms should I use?. The handout Mastering Multiprecision Arithmetic describes algorithms for arithmetic operations that you might find useful. The descriptions of the algorithms come after a discussion of how you might represent infinite precision numbers in ML, which you should skim to understand the descriptions of the algorithms.
How big is it? Following the hints in the book, the course solution comprises two implementations of class Natural
:
Using the array representation, the solution is about 130 lines of μSmalltalk code.
Using the subclass-based representation, the solution is about 150 lines of μSmalltalk code.
We have not written a solution that uses Smalltalk lists.
Related reading:
There is a detailed implementation guide in the bignums handout. It discusses both array-based and subclass-based representations.
The handout Mastering Multiprecision Arithmetic describes algorithms for arithmetic operations. It’s written in the context of ML, but the description of the algorithms for arithmetic may be helpful.
In a system with abstract data types, binary operations like
+
and*
are easy: you automatically have access to both representations. In a system with objects, not so! To learn how to get access to multiple representations in the object-oriented way, read section 10.7, which starts on page 670.In the 7th lesson on program design, read the section on how the design steps are adapted for use with objects. Focus on steps 6, 7, and 8: algebraic laws, case analysis, and results. In the same lesson, you may also wish to revisit the three levels of access to representation. You will need level C, but there is no need for double dispatch here.
Class
Natural
is a subclass ofMagnitude
. Study theMagnitude
protocol in section 10.4.6. For information about the implementation ofMagnitude
, which should provide useful ideas aboutNatural
, as well as the “subclass responsibilities,” study the implementation ofMagnitude
on page 665.2For the interface to a Smalltalk array, study the
Collection
protocol in section 10.4.5, which starts on page 651. You have access to the protocol in Figure 10.13 on page 653, including the class methodwithAll:
. Among instance methods, you are more likely to use theKeyedCollection
protocol in Figure 10.14 on page 656, especiallyat:
andat:put:
. You may also want the class methodnew:
that is defined on arrays (page 683).For list construction, which you will need for the
decimal
method, look at theList
protocol in section 10.4.5, especially Figure 10.16 on page 658.For abstraction functions and invariants, you may wish to read the program-design lesson on abstract data types (lesson 6).
38. Implementing arbitrary-precision integers. Do exercise 38 on page 732 of Build, Prove, and Compare. An implementation is shown in the bignums handout. Add your solution to file bignum.smt
, following your solution to exercise 37.
Because you build large integers on top of Natural
, you don’t have to think about array, list, or subclass representations. Instead you must focus on dynamic dispatch and on getting information from where it is to where it is needed.
The book has starter code for class LargeInteger
, which you can copy (with acknowledgement) from /comp/105/build-prove-compare/examples/usmalltalk/large-int.smt
.
How must I document my representation? As on the previous exercise, you must document the abstraction function and invariant for every concrete class. For example if you follow the guidelines and define an abstract class LargeInteger
with two concrete subclasses LargePositiveInteger
and LargeNegativeInteger
, you’ll need to document only the two concrete subclasses.
How big is it? The course solutions for the large-integer classes are 30 lines apiece.
Related reading: This problem is all about dynamic dispatch, including double dispatch.
Read section 10.7, which starts on page 670.
Read the last section, “Laws for double dispatch,” in the 7th lesson on program design.
You’ll also have a chance to practice double dispatch in the second Smalltalk recitation.
Helpful code. Because of the potential for negation (“unary minus”) to overflow, division of signed integers is fiddly. For those of you who prefer not to translate the nested conditionals found in the divide
function in the μScheme chapter, here are some methods defined in the solution large-integer classes.
On class
LargeInteger
:(method div: (n) (self sdiv: n))
On class
LargePositiveInteger
:(method sdiv: (anInteger) ((anInteger isStrictlyPositive) ifTrue:ifFalse: {(LargePositiveInteger withMagnitude: (magnitude sdiv: anInteger))} {((((self - (LargeInteger fromSmall: anInteger)) - (LargeInteger fromSmall: 1)) sdiv: (anInteger negated)) negated)}))
On class
LargeNegativeInteger
:(method sdiv: (anInteger) ((self negated) sdiv: (anInteger negated)))
To help with two’s-complement representations, the following code on class LargeInteger
will ensure that the negated
method defined on SmallInteger
does not overflow:
(class-method fromSmall: (anInteger)
((anInteger isNegative) ifTrue:ifFalse:
{(((self fromSmall: 1) + (self fromSmall: ((anInteger + 1) negated))) negated)}
{((LargePositiveInteger new) magnitude: (Natural fromSmall: anInteger))}))
39. Modifying SmallInteger
so operations that overflow roll over to infinite precision. Do exercise 39 on page 732 of Build, Prove, and Compare. Put your solution in a fresh file, mixnum.smt
. On the first line of file mixnum.smt
, include your other solutions by writing (use bignum.smt)
.3
You must modify SmallInteger
without editing the source code of the μSmalltalk interpreter. To do so, you will use the protocol for classes described Figure 10.10 on page 648. You can see an example of the protocol in use in chunk 732a.
The methods in this protocol will modify the existing class SmallInteger
; they 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? The course modifications to the SmallInteger
class are about 35 lines.
Related reading: Everything about dispatch and double dispatch still applies, especially the example in the 7th lesson on program design. In addition, you need to know how overflow is handled using “exception blocks.”
Review the presentation of blocks, especially the parameterless blocks (written with curly braces) in section 10.4.3, which starts on page 648.
Read the description of
at:ifAbsent:
in the keyed-collection protocol in Figure 10.14 on page 656. Now study this expression:('(0 1 2) at:ifAbsent: 99 {0})
This code attemps to access element 99 of the array
( 0 1 2 )
, which is out of bounds because the array only has only 3 elements. When given an index out of bounds,at:ifAbsent:
sendsvalue
to the “exception block”{0}
, which ultimately answers zero.Study the implementation of the
at:
method in code chunk 694c, which usesat:ifAbsent:
with an “exception block” that causes a run-time error ifvalue
is sent to it.Finally, study the overflow-detecting primitives in exercise 39 on page 732, and study the implementation of
addSmallIntegerTo:
in the code chunk immediately below. That is the technique you must emulate.
T. Testing Bignums. In standalone file bigtests.smt
, 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 involving both small and large integers.
These tests will be run on other people’s code, and they need to be structured and formatted as follows:
The test must 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.”
Code must compute a result of class
Natural
,LargePositiveInteger
, orLargeNegativeInteger
. The code may appear in a method, a class method, a block, or wherever else you find convenient. The code must be included in filebigtests.smt
.The expected result must be checked using the
check-print
form described above.
Each test must take less than 2 CPU seconds to evaluate.
Here is a complete example containing two tests:
; Summary: 10 to the tenth power, linear time, mixed arithmetic
(class Test10Power
[subclass-of Object]
(class-method run: (power)
[locals n 10-to-the-n]
(set n 0)
(set 10-to-the-n 1)
({(n < power)} whileTrue:
{(set n (n + 1))
(set 10-to-the-n (10 * 10-to-the-n))})
10-to-the-n)
)
(check-print (Test10Power run: 10) 10000000000)
; Summary: 10 to the 30th power, mixed arithmetic
(check-print (Test10Power run: 30)
1000000000000000000000000000000)
Here is another complete example:
; Summary: 20 factorial
(define factorial (n)
((n isStrictlyPositive) ifTrue:ifFalse:
{(n * (factorial value: (n - 1)))}
{1}))
(check-print (factorial value: 20) 2432902008176640000)
Related reading: No special reading is recommended for the testing problem. As long as you understand the examples above, that should be enough.
ADT. Collect representations, abstraction functions, and invariants.
In a new file adt.txt
, summarize your design work:
For each concrete class you defined to represent natural numbers in exercise 37,
- List the instance variables.
- Copy and paste the class’s abstraction function and invariant.
For the natural numbers, explain in one or two sentences why you chose the representation that you did. In addition, please tell us what went well and if you have any regrets.
For each concrete class you defined to represent large integers in exercise 38,
- List the instance variables.
- Copy and paste the class’s abstraction function and invariant.
Two simple sanity checks for multiplication
It’s comforting to have an idea that things have started to work. Here are two comforting (but limited) tests. Here, for example, is a version of power:
(class Power
[subclass-of Object]
(class-method x:to: (x n) [locals half]
((n = 0) ifTrue:ifFalse:
{(x coerce: 1)}
{(set half (self x:to: x (n div: 2)))
(set half (half * half))
(((n mod: 2) = 1) ifTrue:
{(set half (x * half))})
half})))
(check-expect (Power x:to: 2 3) 8)
(check-expect (Power x:to: 3 4) 81)
(check-expect (Power x:to: (1 / 3) 3) (1 / 27))
And here is code that computes and prints factorials, from code chunk 757b in the textbook:
(class Factorial
[subclass-of Object]
(class-method printUpto: (limit) [locals n nfac]
(set n 1)
(set nfac 1)
({(n <= limit)} whileTrue:
{(n print) ('! print) (space print) ('= print) (space print) (nfac println)
(set n (n + 1))
(set nfac (n * nfac))})))
Depending on your choice of base, (Factorial printUpto: 20)
may run to completion almost instantly, or it may exhaust the “CPU fuel” used to recover from infinite loops—so you may need to test it while running
env BPCOPTIONS=nothrottle usmalltalk
These tests may be comforting, but they suffer from grave limitations:
They only ever multiply numbers. They do not add, subtract, negate, or compare numbers.
They never multiply two large numbers. They only ever multiply a large number by a small number, or two small numbers.
These limitations make power and factorial poor tests of correctness.
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. You can generate a string of random digits on the command line by launching the bash
shell and running this command:
for ((i = 0; i < 20; i++)); do echo -n ' ' $((RANDOM % 10)); done; echo
0pt plus 3-200 0pt plus -3
You can generate a test command from a list of digits using μScheme:
(define nat-test (ns) ; alert! μScheme code
(letrec ([exp-of (lambda (ns)
(if (null? ns)
0
(list3 (car ns) '+ (list3 10 '* (exp-of (cdr ns))))))])
(let* ([left (lambda () (printu 40))]
[right (lambda () (printu 41))]
[space (lambda () (printu 32))]
[_ (left)]
[_ (print 'check-print)]
[_ (space)]
[_ (print (exp-of (reverse ns)))]
[_ (space)]
[_ (app print ns)]
[_ (right)]
[_ (printu 10)])
'Printed!)))
For example,
-> (nat-test '(1 2 3))
(check-print (+ 3 (* 10 (+ 2 (* 10 (+ 1 (* 10 0)))))) 123)
Printed!
If you don’t have multiplication working yet, you can use the following class to multiply by 10:
(class Times10
[subclass-of Object]
(class-method by: (n) [locals p]
(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
p))
This idea will test only your addition; if you have bugs there, fix them before you go on.
You can write, in μSmalltalk instead of μScheme, 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.
Here’s an example of using ghci
to generate numbers for testing:
$ ghci
GHCi, version 8.0.1: http://www.haskell.org/ghc/ :? for help
Prelude> 256492 * 666481
170947044652
Prelude> 170947044652 * 293847926754
50232434655713663419608
Prelude>
Hints and guidelines from past students
Student’s experiences are in italics; course responses are in the standard font.
We found the contracts in the textbook way too late since we were mainly depending on the specification handout and bignums handout. If we had known the contract of each method on each class in the specification, it would have helped immensely.
The contracts in the book are crazy useful. The full details for each problem are in the related reading, but for a quick look at some of the most useful information, consult this table:
Class Pages Magnitude
page 659 Number
page 659 Natural
page 662 Integer
page 660 LargeInteger
page 732 Array
pages 653, 656, and 657 A key issue we ran into that we found out late into the process was when creating the number zero in some arithmetic operations, we were using a constructor that did not enforce the invariant. I think it would be very helpful if the specification put this as a common error or a grave mistake, because most of the logic was correct.
Enforcing the invariant is a really good idea. You can define a private method
invariant
and a private methodwithInvariant
that looks like this:(method withInvariant () ((self invariant) ifFalse: {(self error: 'invariant-violation)}) self)
We weren’t using regression testing, so one part would work initially then fail in a later step. It was really helpful in the previous assignments when regression tests were required. Including unit tests as a part of the process and emphasizing the point would also help.
You’ve had two assignments with required regression tests. That’s enough for you to decide the value of regression tests.
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 (the “Smalltalk bignums handout”) with suggestions about which methods depend on which other methods and in what order to tackle them.
The whole story about division
We do implement division, but not fully. Here’s why:
Without division and modulus, we can’t print numbers in decimal. Printing numbers is too useful to ignore.
Long division, in which the divisor of a large number can itself be a large number, is painful. The algorithm requires trial and error, and it’s easy to get wrong.
To enable our code to use division without requiring long division, we have invented messages sdiv:
, smod:
, and sdivmod:with:
. These messages accept only short divisors, and each such divisor must be represented as an object of class SmallInteger
. And in order to enable these messages to interoperate with Smalltalk’s standard integer division, we continue to support the standard messages div:
and mod:
. The resulting system design is a little confusing, but here’s what we know:
Method
mod:
is inherited from classInteger
, and it remains good. As long as division rounds toward minus infinity,mod:
does the right thing. This means thatmod:
of a large integer by a small integer might return a large integer, even though the result is representable as a small integer. That’s OK.Methods
sdiv:
,smod:
, andsdivmod:with:
are all well specified and well behaved. They don’t have to support mixed arithmetic (the argument must be aSmallInteger
, always). We just implement each one according to its specification. And because the divisor is always a small integer, there’s never a need for double dispatch.We provide a limited implementation of
div:
that works only when the divisor is a small integer. On large integers, methoddiv:
should delegate tosdiv:
, as shown above. On small integers, the primitive implementation ofdiv:
can be left alone. And natural numbers don’t supportdiv:
; they only supportsdiv:
.Method
reciprocal
is inherited from classInteger
and also remains good: it allocates aFraction
with a large-integer denominator. In a world of mixed arithmetic, arithmetic on such fractions should “just work.”
Avoid common mistakes
Below you will find some common mistakes to avoid.
It is a common mistake to ignore the design process. Don’t be like the students who said,
We followed the design process for assignments where we were to design individual functions but when the specification told us what to do stepwise, like in the Naturals homework, we didn’t.
It is common to overlook class methods. They are a good place to put information that doesn’t change over the life of your program.
It’s a terrible mistake to make decisions by interrogating an object about its class—a so-called “run-time type test.” Run-time type tests destroy behavioral subtyping. This mistake is most commonly made in two places:
If you are representing a
Natural
number as a list of digits, you may be tempted to interrogate the representation to ask “are you nil or cons?” This is the functional way of programming, but in Smalltalk, it is wrong. You must make the decision by sending a message to an object, and the method that is dispatched to will know whether it is nil or cons.If you are mixing arithmetic on large and small integers or on integers and fractions, you may be tempted to interrogate an argument about its class. This interrogation is wrong. You must instead figure out how to accomplish your goals by sending messages to the argument—probably including messages from some private protocol.
There is a right way to do case analysis over representations: entirely by sending messages. For an example, study how we calculate the length of a list: we send the size
message to the list instance. Method size
is dispatched to class Collection
, where it is implemented by using a basic iterator: the do:
method. If you study the implementation of do:
on classes Cons
and ListSentinel
(which terminates a μSmalltalk list), you’ll see the case analysis is done by the method dispatch:
Sending
do:
to a cons cell iterates over thecar
andcdr
.Sending
do:
to a sentinel does nothing (thereby terminating the iteration).
The idea of “case analysis by sending messages” applies equally well to arithmetic—and the suggestions in the bignums handout are intended to steer you in the right direction. If you find yourself wanting to ask an object what its class is, seek help immediately.
On smaller problems, it is surprisingly common for students to submit code without ever even having run it or even loaded it into an interpreter. If you run even one test case, you will be ahead of the game.
It is too common to submit bignum code without having tested all combinations of methods and arguments. Your best plan is to write a program, in the language if your choice, that loops over operator and both operands and generates at least one test case for every combination. Because μSmalltalk is written using S-expressions, you could consider writing this program in μScheme—but any language will do.
It is relatively common for students’ code to make a false distinction between two flavors of zero. In integer arithmetic, there is only one zero, and it always prints as “0
”.
It’s surprisingly common to fail to tag the test summary with the prefix Summary:
, or to forget it altogether.
It’s a common mistake to redefine negated
on class SmallInteger
and to assume that nothing needs to be done with -
. But SmallInteger
is using machine primitives for arithmetic, and machine primitives provide addition and subtraction, but not negation. So the class definition looks like this:
(class SmallInteger
[subclass-of Integer] ; primitive representation
...
(method negated () (0 - self))
(method + (n) (primitive + self n))
(method - (n) (primitive - self n))
...
)
If you are expecting it to look exactly like class Number
and you stick with the default implementation of -
, you might get some baffling infinite recursions in exercise 39.
In exercise 39, it’s a common mistake to try to implement (self - anArgument)
by evaluating (anArgument - self)
—or more precisely, by evaluating ((anArgument asLargeInteger) - self)
. This recursion terminates, but it produces an answer with the wrong sign. If you get “Array index out of bounds” errors, look for this mistake.
It’s not common, but if you rely on the recommended invariant for the subclass-based approach (n and d are not both zero), forgetting to enforce the invariant is a bad mistake.
Three diagnostic techniques
To help you diagnose problems in your code, we recommend three diagnostic techniques: dynamic tracing, static spell checking, and static call-graph analysis.
Tracing
The interpreter can help you debug by emitting a call trace of up to n
message sends and answers. Just enter the definition
(val &trace n)
at the read-eval-print loop. To turn tracing off, (set &trace 0)
.
Here is an (abbreviated) example trace of message new
sent to class List
, which is the subject of one of the reading-comprehension questions:
-> (List new)
standard input, line 3: Sending message (new) to class List
predefined classes, line 499: Sending message (new) to class SequenceableCollection
predefined classes, line 499: (<class List> new) = <List>
predefined classes, line 499: Sending message (new) to class ListSentinel
predefined classes, line 489: Sending message (new) to class Cons
predefined classes, line 489: (<class ListSentinel> new) = <ListSentinel>
predefined classes, line 490: Sending message (pred: <ListSentinel>) to an object of class ListSentinel
predefined classes, line 490: (<ListSentinel> pred: <ListSentinel>) = <ListSentinel>
predefined classes, line 491: Sending message (cdr: <ListSentinel>) to an object of class ListSentinel
predefined classes, line 491: (<ListSentinel> cdr: <ListSentinel>) = <ListSentinel>
predefined classes, line 499: (<class ListSentinel> new) = <ListSentinel>
predefined classes, line 499: Sending message (sentinel: <ListSentinel>) to an object of class List
predefined classes, line 499: (<List> sentinel: <ListSentinel>) = <List>
standard input, line 3: (<class List> new) = <List>
<trace ends>
List( )
One warning: as usual, the interpreter responds to an expression evaluation by printing the result. But in Smalltalk, printing is achieved by sending the println
message to the result object. This interaction is also traced, and the results can be startling. Here, for example, is the result of evaluating the literal integer 3
:
-> 3
internally generated SEND node, line 1: Sending message (println) to an object of class SmallInteger
internal syntax, line 8: Sending message (print) to an object of class SmallInteger
3 internal syntax, line 8: (3<SmallInteger> print) = 3<SmallInteger>
internal syntax, line 8: Sending message (print) to an object of class Char
internal syntax, line 8: (<Char> print) = 10<SmallInteger>
internally generated SEND node, line 1: (3<SmallInteger> println) = 3<SmallInteger>
As you see, even a simple operation like printing a number involves multiple messages. To prevent them from confusing you, load the following code:
(val &trace 0)
(class TraceMethod
[subclass-of Object]
(method traceFor: (n) [locals answer]
(set &trace n)
(set answer (self value))
(set &trace 0)
answer)
(method trace () (self traceFor: -1)))
(Block addMethods:from: '(traceFor: trace) TraceMethod)
You can then run something like ({8 squared} trace)
or ({(List new)} traceFor: 10)
Tools that analyze your code for potential faults
Smalltalk has no type system. But some properties of of your code can still be checked statically:
A “wrong number of arguments” check is built into the language. A symbolic message like
+
or!=
expects exactly one argument (not counting the receiver). An alphanumeric message likeprintln
orifTrue:ifFalse:
expects a number of arguments equal to the number of colons in the message’s name—not counting the receiver. If these expectations aren’t met, the offending code is flagged with a syntax error.We provide a simple static-analysis tool called
lint-usmalltalk
. It spell checks each message send to be sure a method with that name is defined somewhere. If no such method is defined, the message name is misspelled.Normally,
lint-usmalltalk
also checks for unused methods. An unused method might be misspelled, or it might just be one that isn’t used in any code or test. Here’s an example run:% lint-usmalltalk bignum.smt instance method compare: of class Natural is never used anywhere instance method smod: of class Natural is never used anywhere
An analysis you can do by hand
There is a static analysis you can do by hand called call-graph analysis. It can help you understand how classes work together, and it’s the best tool for diagnosing problems with infinite loops and recursions.
Call-graph analysis works by identifying what methods transfer control to what other methods. Every node in the call graph is a combination of class name and message name. For example, Boolean/ifTrue:
or List/select:
. Each node has outgoing edges that illustrate what happens if the node’s message is sent to an instance of the node’s class:4
If the message is implemented by a primitive method, like
+
onSmallInteger
, it has no outgoing edges.If the method is inherited from the superclass, the node has a dotted edge to the same message on the superclass. For example, node
True/ifTrue:
has a dotted edge toBoolean/ifTrue:
.If the method is a subclass responsibility, the node has a dotted edge to each subclass.
If the method is defined on the class, the node has a solid outgoing edge for each message that could be sent during the method’s execution.
You have to look at each message send and figure out what class of object it might be sent to. This part can’t easily be determined by looking at the code; you have to know the protocol. For example, if message
&
is sent to aBoolean
, we know the argument is also aBoolean
. As another example, if message+
is sent to a natural number, the protocol says the argument obeys theNatural
protocol.Usually all the possibilities are covered by a superclass. For example, even though message
size
could be sent to aList
or anArray
, you can just draw a single edge to nodeCollection/size
. Sometimes you might have more then one outgoing edge per message—for example, if a message could be sent to anInteger
or aFraction
, but not to anyNumber
.If the method is not defined and not inherited from a superclass, the message is not understood, and your program is broken.
Here are some tips about call graphs:
If you have a cycle in the graph, it represents a potential recursion. Be sure that on every trip through the cycle, some argument or some receiver is getting smaller, or that the algorithm is making progress in some other way. For example, my code for
*
on classNatural
can sometimes send the*
message to a natural number, but on every trip through this cycle, the receiver of*
gets smaller (by a factor of b).Have a goal in mind, and ignore messages that are unrelated to the goal. For example, if you are building a call graph to study addition, you probably don’t have to include the
max:
message.Loops and conditionals are technically message sends, but I urge you to simplify your call graph by simply assuming that all the code is (eventually) executed.
A call graph can help with unit testing: you want to make sure that every solid edge is exercised by some unit test.
Like any other analysis technique, call-graph analysis is worth it only when you have a problem. You have an infinite recursion? Or you don’t understand how the methods are supposed to work together? Build a call graph. Otherwise, continue to apply your standard design process, and everything will be fine.
A final note: not all of our TAs have used call graphs before. You may be learning together.
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.
Speed variations. For extra credit, try the following variations on your implementation of class Natural
:
Implement the class using an internal base b = 10. Measure the time needed to compute the first 50 factorials. And measure the time needed to compute the first 50 Catalan numbers.
The Catalan numbers, which make better test cases than factorial, are defined by these equations (from Wikipedia):
$$C_0 = 1 \mskip 30mu C_{n+1}=\sum _{i=0}^{n}C_{i}\cdot C_{n-i}$$Determine the largest possible base that is still a power of 10. Explain your reasoning. Change your class to use that base internally. Measure the time needed to compute the first 50 factorials, and also the time needed to compute the first 50 Catalan numbers.
In both cases, measure the additional time required to print the numbers you have computed.
Specialize your b = 10 code so that the
decimal
method works by simply reading off the decimal digits, without any short division. Measure the improvement in printing speed.Finally, try a compromise, like b = 1000, which should use another specialized
decimal
method, making both arithmetic and decimal conversion reasonably fast. Can this implementation beat the others?
Write up your arguments and your measurements in your README file.
Long division. Implement long division for Natural
and for large integers. If this changes your argument for the largest possible base, explain how. This article by Per Brinch Hansen describes how to implement long division.
Mixed Comparisons. Make comparisons work, even with mixed kinds of integers. So for example, make sure comparisons such as (5 < (1000000 * 1000000))
produce sensible answers.
Space costs. Instrument your Natural
class to keep track of the size of numbers, and measure the space cost of the different bases. Estimate the difference in garbage-collection overhead for computing with the different bases, given a fixed-size heap.
Pi (hard). Use a power series to compute the first 100 digits of pi (the ratio of a circle’s circumference to its diameter). Be sure to cite your sources for the proper series approximation and its convergence properties. Hint: I vaguely remember that there’s a faster convergence for pi over 4. Check with a numerical analyst.
What and how to submit: Individual problem
Submit these files by Sunday, November 22 at 11:59pm:
- A
README
file containing- The names of the people with whom you collaborated
A file
cqs.small.txt
containing your answers to the reading-comprehension questionsA filefrac-and-int.smt
showing whatever definitions you used to do exercise 36(a). It probably includes definitions of new methods and probably copies some of those methods to one or more of these classes:Fraction
,Integer
, andSmallInteger
. And it most definitely includes at least three unit tests.
Please identify your solutions using conspicuous comments, e.g.,
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;
;;;; Solution to Exercise XXX
(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 by Tuesday, December 1 at 11:59pm:
- 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 exercises you worked (including any extra credit)
- Narrative and measurements to accompany your extra-credit answers, if any
A file
bignum.smt
showing your solutions to exercises 37 and 38. This file must work with an unmodifiedusmalltalk
interpreter. Therefore if you use results from exercise 36(a), or any other problem, you will need to duplicate those modifications inbignum.smt
.A file
mixnum.smt
showing your solution to exercise 39. This file should incorporate your other solution by reference, using the line(use bignum.smt)
at the beginning. Do not duplicate code from
bignum.smt
.A file
bigtests.smt
containing your solution to exercise T.A file
adt.txt
containing your solution to exercise ADT.
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.
Exemplary | Satisfactory | Must improve | |
---|---|---|---|
Clarity |
• Course staff see no more code than is needed to solve the problem. • Course staff see how the structure of the code follows from the structure of the problem. |
• Course staff see somewhat more code than is needed to solve the problem. • Course staff can relate the structure of the code to the structure of the problem, but there are parts they don’t understand. |
• Course staff see roughly twice as much code as is needed to solve the problem. • Course staff cannot follow the code and relate its structure to the structure of the problem. |
Exemplary | Satisfactory | Must improve | |
---|---|---|---|
Structure |
• The base used for natural numbers appears in exactly one place, and all code that depends on it consults that place. • Or, the base used for natural numbers appears in exactly one place, and code that depends on either consults that place or assumes that the base is some power of 10 • No matter how many bits are used to represent a machine integer, overflow is detected by using appropriate primitive methods, not by comparing against particular integers. • Code uses method dispatch instead of conditionals. • Mixed operations on different classes of numbers are implemented using double dispatch. • Or, mixed operations on different classes of numbers are implemented by arranging for the classes to share a common protocol. • Or, mixed operations on different classes of numbers are implemented by arranging for unconditional coercions.
• Code deals with exceptional or unusual conditions by passing a suitable
• Code achieves new functionality by reusing existing methods, e.g., by sending messages to • Or, code achieves new functionality by adding new methods to old classes to respond to an existing protocol. • An object’s behavior is controlled by dispatching (or double dispatching) to an appropriate method of its class. |
• The base used for natural numbers appears in exactly one place, but code that depends on it knows what it is, and that code will break if the base is changed in any way. • Overflow is detected only by assuming the number of bits used to represent a machine integer, but the number of bits is explicit in the code. • Code contains one avoidable conditional. • Mixed operations on different classes of integers involve explicit conditionals. • Code protects itself against exceptional or unusual conditions by using Booleans. • Code contains methods that appear to have been copied and modified. • An object’s behavior is influenced by interrogating it to learn something about its class. |
• The base used for natural numbers appears in multiple places. • Overflow is detected only by assuming the number of bits used to represent a machine integer, and the number of bits is implicit in the value of some frightening decimal literal. • Code contains more than one avoidable conditional. • Mixed operations on different classes of integers are implemented by interrogating objects about their classes. • Code copies methods instead of arranging to invoke the originals. • Code contains case analysis or a conditional that depends on the class of an object. |