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

Brian Davidson

Blocks in Virtual Machines (2 Points)

The following two instance methods on the Number class both compute whether the number (self) is greater than one number and less than another:
Uploaded Image: vm1.png

The following table shows how long it takes for these methods to execute for different numbers:
Uploaded Image: vm2.png

(Part A) Why is it that the first two expressions take the same amount of time to run (0.00143 ms), whereas the last two expressions differ in run time?

The first two use parathensis and the & method, the last two use blocks and the and: method. When using blocks the second argument is only processed when needed, when using parathensis and the & method, both the argument and the receiver are processed in all circumstances. The checks of -500 greater than 0 and less than 1000 turns into (-500>0) and (-500<1000). With the blocks the first one fails so the block is never evaluated since we know the result is false. With parentheses they are both evaluated regardless. The checks of 500 greater tahn 0 and less than 1000 turn into (500>0) and (5001000). With the blocks the first one passes so the second one is evaluated and also check. With parantheses they are both evaluated regardless. Since the same execution is done for parenthesis regardless of the input the running times are the same, but becuase blocks dont evaluate the second part when the first part fails there are different executions of code thus different running times.

The first two experess
The byte codes for the two methods follows:
Uploaded Image: vm3.png

(Part B) Given these byte codes, explain why the block expressions are faster to execute than the parenthesis expressions.

Blocks run faster in both contexts because when you look at the byte code the and: message is not actually sent thus saving the time to look up and send the message. Instead it uses inline compilation and jumps.

The first 3 lines of blockGreaterThan:andLessThan: method perform (self > arg0) pushes the result on the stack. On the 4th line the top of the stack is popped off and if it is false then it jumps to line 13. If it is true it continues on to perform lines 9-11 which perform (self arg1) with the result pushed on to the stack. On the 12th line it jumps to line 14. If line 13 is reached then the check on line 4 failed and false is pushed onto the stack. On line 14 whatever is on the top of the stack is returned, false from line 13 (from failure of test at line 4) or false/true from the check at line 11.

The first 3 lines of parenthesisGreaterThan:andLessThan: method perform (self > arg0) and push the result onto the stack. The next 3 lines perform (self > arg1) and push the result onto the stack. The next line takes the top two items on the stack, performs an & on them and pushs that onto the stack. The final line returns the top of the stack.

From the discussion in part A the partial execution increases the speed up time for blocks over parenthesis even though its actually implemented inline. But even when both parts parts of the 'and' are executed blocks are still more efficent because it saves a method call by not having to send '&' to the top two items on the stack. The blocks only make two calls, one to > and one to < and through the use of jumps save precious execution time by short circuiting when possible. The parentheses must make three calls always, one to >, one to , and one to &. Thus they take longer and have the same execution time regardless of the input.

(Part C) In the blockGreaterThan:andLessThan: method, the message and: is sent to the object returned from (self > greaterThan) with an argument of [self < lessThan]. At least, thatís the way the Smalltalk syntax would lead you to believe. In reality (in the byte code), you can see that there is no and: message sent. Why is this so?

While the syntax of small talk would lead you to believe and my discussion in Part A would also lead you believe that the block context would be sent as an argument to the reciever with the 'and:' message. That is not the case. The compiler optimizes the code, and puts the execution of the block inline. This makes things in smalltalk so much quicker through better optimization. If the intention is to force the 'and:' message, that is still possible with (500>0) perform: #and: withArguments: [500<1000].


Object-Oriented Language Design (2 Points)

OO programming languages differ quite a bit in their philosophy, purpose, and implementation. The following five questions ask you to examine some design choices for creating an OO language. Answer only two of the following:
  1. Java, C++, and C# have primitive types. Eiffel, Ruby, and Smalltalk do not. What are the advantages and disadvantages of having primitive types?
The use of primative types is usefull in the fact that the variables and functions on the variables are closer to actual machine code and machine types. Due to the fact they are closer, less steps are needed to perform actions on the variables thus there is a speed increase. The downside of primative types is the lack of uniformity, maybe a int can peform this, that and the other but a char cant. Smalltalk treats everything like an object so it provides a more uniform foundation for performing actions on varibles and you can edit the object to and your own kind support for this, that and the other. One advance in smalltalk since everything is an object is that all variables have a type of object and nothing else, where as in java some things are ints an other objects and there are type checks done on the code in the compilation thus limiting the ability of the language.
  1. Most OO languages run on a virtual machine. Java and Smalltalk do. C++ does not. What are the advantages and disadvantages of using a virtual machine for OO programming?
Virtual machines are useful because they provide a standard foundation for coding on. The programmer doesnt usually need to worry about what operating system he is designing for, the processing done by the virtual machine will often handle that for him. One of the nicest things about virtual machines is the memory management. In C++ you must allocate memory and free memory when you are done with it, which can often cause problems if you forget to free memory or many other memory problems. The virtual machine does the memory management for you through garbage collection which reduces the effort by the programming to keep track of all the memory issues. For every benifit there must be a drawback, when you program in a language that uses a virtual machine when the code is compiled it is in byte code instead of machine language. It is the is byte code that allows the code to be multiplatform since it will get interpreted by the virtual machine that is installed on whatever operating system you are working on. The key issues here is that one the byte code must be re-interpreted into machine code for execution, so there is a speed loss in using virtual machines. Secondly the virtual machine must be installed on the system, with all the necessary modules also installed. If I program in Python I need the python virtual machine on the client computer and if I use the popular Python GUI toolket wxPython I need to have that installed as well. The same goes with Squeak, I need the virtual machine and the image on the client computer. This is not a problem with C/C++, when I compile an appication for Windows, it generates a machine code application that will run on all windows with very little need for outside resources unless using a non windows standard library.


Debugger: How do we use the debugger to solve a programming bug?

Uploaded Image: davidson_error.jpg

When Programming, bugs will occur and debugging them is easy within squeak. When an error occurs an error window is displayed like the one above that shows there error type in the title bar and the call stack of when and where the error occured. When these error happen, you can attempt to proceed anyways by hitting proceed, ignore it by hitting abandon buttom or debug it by hitting the debug buttom. The squeak debugger is a very useful tool and should be attempted to be used first, the option to proceed and abandon can be done at anytime after you have already chosen to debug it.

Uploaded Image: davidson_debug.jpg

When you choose to debug the error, a new window will pop up looking similar to the one above. The window will have the error listed in the title bar, the call stack below it, and buttons for action below that. You notice proceed is the first button listed, and abandon can be done by using the x in the corner of the window. For this reason it is good to attempt to debug all errors. Below the buttons is the code segment for the current place in the call stack. By clicking on a different point in the call stack list above you can traverse to different code segments, as shown below.

Uploaded Image: davidson_debug2.JPG

As you can see in this example, the error Zero divide in the contxt of SmallInteger checks if the denominator isZero, if so it raises an error. Thus we know the problem. By going up the call stack by one context, we can see that we are calling divide with duration. At the bottom of the debug window are the instance variables for the current class context and the temp variables for the current method. By clicking on duration in the temp variables section (list on the right) the value appears in the text box on the far right, which shows us the value is indead zero. Thus we know the bug, we should have some kind of error checking before hand to take care of the extreme cases of division by zero. You can edit the code right in the window and "restart" the method and see if it works. Other useful things that you can do is in the value box, you can change the value to test out different scnearios. This bug was a rather simple bug for example purposes but often you will need to walk through the code to fix bugs that interact with different parts, that is where the "into" and "over" come into play. Into performs the next step partially, while changing context to that step so you can see the inner workings of that step, and step through the inner step Over performs the next step completely keeping the current context. This allows you to step through the code line by line, call by call, and debug bugs that only occur through complex situations, for example a networking game bug would likely have this problem as you have to determine if the bug is in the network code or the game engine. The "through" button allows you, if you are going to execute a block, to step through the block. Other nice details, are that you dont have to have a bug to bring up the debugger, if you use self halt anywhere in the code, when ever the code is reached, it will halt the process and bring up the debugger. Also the current variables (both instance and temporary can be clicked on and brought up inspectors, exporers, reference finders, and many other useful tools. This allows you to find out where the variable is accessed and modified and its current state to be able to more acurately debug the problem. Becuase the debugger is a very powerful tool it should be used whenever possible, if you have a problem you can can abandon, or proceed at anytime.



Writing Code (1 point)

Implement a method in Squeak that will give you the nth Fibonacci number. For both 0 and 1, the Fibonacci number equals 1. From then on, the next in the series is simply the sum of the previous two in the series (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, etc.). Return an error when applicable. Your code should be based on good OO-style and be an efficient algorithm.

As a suggestion, write the code in Squeak. Then, once you have debugged it, you can post it to the CoWeb by surrounding it with <code> and </code>

Answer

The method would go in Kernel-Numbers::Integer (category: mathematical functions)

The obvious answer is to do this::
fibonacci
	"Answer the fibonacci of the receiver."

	((self = 0) or: [self = 1]) ifTrue: [^ 1].
	self > 1 ifTrue: [^ (self - 1) fibonacci + (self - 2) fibonacci].
	self error: 'Not valid for negative integers'


But I would recommend doing this because time to do a small number fibonacci recursion isnt much but for large numbers its greatly inefficent. So I turned a inefficent recursion problem into a efficent looping problem. But it really only comes into play with numbers greater than 10000::
fibonacci
	| oneLast twoLast temp |
	"Answer the fibonacci of the receiver."

	((self = 0) or: [self = 1]) ifTrue: [^ 1].
	self > 1 ifTrue: [
		oneLast := 1.
		twoLast := 1.
		2 to: self do: [:i | 
			temp := oneLast.
			oneLast := oneLast + twoLast.
			twoLast := temp.].
		^oneLast.].
	self error: 'Not valid for negative integers'.


Tracing Code (1 point)

The following code solves the rainfall problem, which you may have seen in previous CS classes. For each line, describe what the Smalltalk code does. Be as specific as possible. In particular, what is data at the various points in the code?
| data onlyPositiveNumbers |
data := OrderedCollection withAll: #(1 2 3 -4 -5 'error' 6 -7 999 2).
onlyPositiveNumbers := [:i | (i isKindOf: Number) and: [i positive]].
data := data select: onlyPositiveNumbers.
data := data copyUpTo: 999. "not including"
Transcript show: data average


Answer

| data onlyPositiveNumbers | 

This line creates two new local variables data and onlyPositiveNumbers.
data := nil
 data := OrderedCollection withAll: #(1 2 3 -4 -5 'error' 6 -7 999 2).

This line assigns the new local variable data to be a OrderedCollection aka variable List with all (withAll:) the elements of a static list (#(...)).
data := OrderedCollection(1 2 3 -4 -5 'error' 6 -7 999 2)
 onlyPositiveNumbers := [:i | (i isKindOf: Number) and: [i positive]].

This line assigns the new local variable onlyPositveNumbers a special block of code (Block) that when executed will take in an argument and assign it to i (:i |). Then it will check to see if i is a number (i isKindOf: Number) and ( and: [...]) if i is positive (i positve). It will return the result true/false to whatever calls the block. Since data was not changed in this line it is the same as the line before.
data := OrderedCollection(1 2 3 -4 -5 'error' 6 -7 999 2)
 data := data select: onlyPositiveNumbers.

This line of code call onto the list (data) to execute the block of code (onlyPositiveNumbers)for each element of the list, passing in that element. And if the block of code returns true it adds it to a new list which is returned and set to be data. In simple terms it performs a select (select:) on the list and only keeps those which pass the block constraint.
data := OrderedCollection(1 2 3 6 999 2)
data := data copyUpTo: 999. "not including"

This line of code calls onto the list (data) to copyAll the elements of the list one by one (copyUpTo:) until the element 999 is reached and not including said element in the new copied list that is returned to the user. The newly returned list is set to be the value of data.
date := OrderedCollection(1 2 3 6)
Transcript show: data average

This line of code tells the list to average all the elements of the list (data). This average is passed into the Transcript to be displayed (show:) Since data was not assigned to anything data is just the same list as before.
date := OrderedCollection(1 2 3 6)



About Me:


My Weekly Schedule

Key:
(#:##) - Start time if not on hour increment
[###] - Building number

2 - Skiles
50 - College of Computing
55 - Instruction Center
76 - Architecture East
103 - Boggs (Spefically Basement Lecture Halls)

Time Monday Tuesday Wednesday Thursday Friday Saturday Sunday
0800 - - - - - - -
0900 - EAS 1600 (9:30) [76] - EAS 1600 (9:30) [76] - - -
1000 CS 4400 [55] EAS 1600 [76] CS 4400 [55] EAS 1600 [76] CS 4400 [55] - -
1100 FREE [103] FREE [LIBRARY] FREE [103] FREE [50] FREE [103] - -
1200 CS 2340 [103] EAS 1600 Lab [41] CS 2340 [103] FREE [50] CS 2340 [103] - -
1300 CS 4451 [50] EAS 1600 Lab [41] CS 4451 [50] FREE [50] CS 4451 [50] - -
1400 - EAS 1600 Lab [41] - FREE [50] - - -
1500 - LCC 3401 [2] - LCC 3401 [2] - - -
1600 - - - - - - -
1700 - - - - - - -
1800 - - - - - - -
1900 - - - - - - -
2000 - - - - - - -
2100 - - - - - - -
2200 - - - - - - -
2300 - - - - - - -

Links to this Page