View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

William Rorabaugh

Coweb Assignment 3


Blocks in Virtual Machines


A) Why do -500 and 500 evaluate parenthesisGreat... in the same amount of time and take different amounts of time to evaluate blockGreat...?
When using parenthesisGreaterThan, we have a consistent running time because the VM always checks both conditions, even if the (self > greaterThan) returns false. When using blockGreaterThan, the VM will not check the argument of "and:" if the reciever of "and:" is false. This means that -500 and 500 process the blockGreaterThan message with different running times because 500 evaluates both conditions and -500 only evaluates the first condition.

Uploaded Image: vm.PNG
B) Given these byte codes, why are the block expressions are faster to execute than the parenthesis expressions?
The byte codes of these expressions are very similar. The key difference is that parenthesisGreat... has a "send: &" instruction whose functionality in blockGreat... is implemented with one pushConstant and two jump instructions. Because send: has all the extra overhead of jumping to a new method and passing arguments, it is (apparently) significantly slower than the simplified push and jump instructions. Thus, even when both conditions in the blockGreat... must be evualated, blockGreat... is significantlty faster because it doesn't have the overhead of the "send: &" instruction.

C) In reality (in the byte code), you can see that there is no and: message sent. Why is this so?
That's because Squeak, which is always in need of performance enhancement, decided to inline all and: messages, and most other boolean messages. As always, its best to go the source for the real explanation, so here is part of the class comment for False:
"Be aware however that most of these methods are not sent as real messages in normal use. Most are inline coded by the compiler as test and jump bytecodes - avoiding the overhead of the full message sends. So simply redefining these methods here will have no effect"



Collection Classes


1)How do OrderedCollection and Set differ?
Every element in an OrderedCollection is stored at a distinct location that can be referenced with an index, but each element in a set has no official location and can only exist or not exist in the set. Futhermore orderedCollections can have duplicate and nil elements but Sets cannot.

2)How do OrderedCollection and Array differ? Why would you use one over the other?
OrderedCollections allow you to insert elements at the beginning, middle, and end of the collections while Arrays only allow you to overwrite an existing location. Futhermore, OrderCollections can grow bigger, but an Array can never have more elements than it had originally allocated. Obviously, you use OrderedCollections when you need the flexibility of a linked list, stack, queue, or other similar growable structures. The only time to use an Array is when you don't need any special functionality and want to take advantage of the really fast primitive methods for accessing elements in an array.

3)How do you use a Dictionary? Why is accessing a Dictionary so fast?
You use a dictionary by adding and reading associations between keys and values. This means that every element stored in a dictionary (the values) is labeled with a unique object (the key). Each key is associated with at most one value, so the dictionary can return the object (if any) that is associated with any given key. The dictionary can also add new associations and overwrite old ones if you give it a key and a new object to associate with the key. You can also you the dictionary as a Set, but it's best used with keys and values. Under the hood, the associations in a dictionary are stored in an array, and the index for each association is computed using a very fast "hash" function. Using the index from the hash function as a starting point, the Dictionary can (on average) quickly search and find the desired key and it's associated value in the array. Google Hash Maps for more information, because Dictionary is Squeak's name for Hash Map.



History of Object-Oriented Programming



One of Kent Beck's more popular contributions is X'treme Programming. This design methodology provides a clear and efficient step by step process for rapidly building an system with object orientated programming. Specific techniques that are especially useful in an OO environment are the use of unit testing and the constant process of identifying and reorganizing key responsibilities in the system. These methods tend to break the big problem into well defined and modularized parts that are more easily solved with objects. By providing such a powerful design methodology, Kent Beck helped make OO design the most useful design methodology in today's market.

Alan Kay help pioneer Smalltalk and it's reincarnation in the form of Squeak. While others found object orientated problems and design methodologies, Kay and others provided a powerful tool for exploring the possibilities of this revolutionary perspective. Kay himself drew inspiration from biological systems when designing smalltalk, and the results have been with us ever since. The implementation of literally everything in Smalltalk as objects and with all computation done thru direct interactions between objects, Kay's work provided the kind of "pure" theoritical playground that was real enough for CS people to play with Object Orientated. In fact, with Smalltalk's multimedia capabilities, it looked real enough to potential customers, to generate interested in Object Orientated design in the bussinness community. In short, Object Orientated programming would probably not be as pure and balanced today without its evolution in Smalltalk.




Midterm Review Assignment


Writing a Squeak Fibonacci "Method":
I want to note that I compute my fibonacci numbers exactly, with no round off error. I decided not to use a recursive or iterative algorithm because it is just plain stupid to use anything more complex than big O log( N ). This functions basically computes the value of the explicit (as apposed to implicit) formula of fibonacci N. This explicit formula is well known and can be derived with a little a combinatorics.
"Computes the "i-th" Fibonacci number in time order log( i )"
"See the performance for yourself by calling fibonacci: 10000"
"Unfortunately, I didn't take the time to learn the exact details of bigIntegers in smallTalk, and so fibonacci: 100000 and higher seems to crash; I think that it might be a printing problem"

fibonacci: i
	| total5 total1 n power5 power1 |
	(i isKindOf: Integer) ifFalse: [ ^'Error: Fibonacci index was not an integer' ].
	(i < 0) ifTrue: [ ^'Error: Can only compute Fibonacci numbers with a indexes >= 0' ].
	n _ i + 1.
	"We have now checked for and corrected the index for the Fibonacci number I want to compute".
	
	total5 _ 0. total1 _ 2.
	power5 _ 1. power1 _ 1.
	"I am going to compute the value of (1 + sqrt(5))^i / 2^(i - 1) using repeated squaring"
	"because I don't like decimals, I am going to store the coefficents of the root of 5 in total5 and power5, and the coefficent of the integral portion in total1 and power1"
	
	[n > 0] whileTrue: [
		| b |
		"check to see if I need to multiply the accumalated total by the current power"
		( (n \\ 2) = 1 ) ifTrue: [
			| a |
			a _ ((power1 * total1) + (5 * (power5 * total5))) / 2.
			total5 _ ((power1 * total5) + (power5 * total1)) / 2.
			total1 _ a.
		].
		"count down to the power to be computed by a factor of 2 and then square the power"
		n _ n // 2.
		b _ ((power1 * power1) + (5 * (power5 * power5))) / 2.
		power5 _ power1 * power5.
		power1 _ b.
	].

"If you expand the formula for fibonacci, the actual answer is the coefficent of sqrt(5) in (1 + sqrt(5))^i / 2^(i - 1)"
	^(total5)


Tracing Code:


 | data onlyPositiveNumbers | 
declares data and onlyPositiveNumbers as temporary local variables


 data := OrderedCollection withAll: #(1 2 3 -4 -5 'error' 6 -7 999 2). 
data stores a new constructed OrderedCollection with the elements (1 2 3 -4 -5 'error' 6 -7 999 2)


 onlyPositiveNumbers := [:i | (i isKindOf: Number) and: [i positive]]. 
onlyPositiveNumbers stores a new block of code


 data := data select: onlyPositiveNumbers. 
data stores a subset of the original collection stored in data. This subset contains only the elements for which onlyPositiveNumbers finds to be positive numbers


 data := data copyUpTo: 999. "not including" 
data stores a collection of all the positive integers that come before the position where 999 is stored. This means that data now stores #(1 2 3 6)


 Transcript show: data average 
Has the transcript print out the average of the positive numbers stored in data. This prints 3.


Links to this Page