Home

31762101777710 - ScholarWorks

1. register ae RIR Gaeiabie register F J op of variable saks top of variable stack top of variable stack IR data This mode accesses the data at the memory location at the top of the variable stack pointed to by the variable register plus the offset stored in the index register This is the addressing method used to access array elements record items and elements BE other high level data structures variable indirect V IR variable register iitop of variable stack memory location IR gt This mode accesses the data at the memory location storedat the memory location at the top of the variable stack pointed to by variable 36 register plus the offset stored in the index register This is the method used to implement high level language pointer variables Index Register IR This mode accesses the value in the index register directly l This is the only register which acts like a standard normal machines It should only be used in Fon INACE TOn with SES matteet a ig modes above Instruction Set This section lists all of the instructions in the ERTE set of the E machine The argument ADDR refers to any addressing mode listed in the last i section The Re TYPE roters to any of the data 5005 integer real boolean char and address most instructions aquir that the type of data being operated upon be specified The 8 refers to an integer constant This Ge from the con
2. end procedure increment var x integer begin x cm x 1 end begin sum 0 n 1 while n lt 4 dei if sum lt 10 then begin sum e sum factorial n increment n o a 7 end end Figure 26 Example Packetized Pascal Program W OD J 10 11 12 var A line 3 ct n sum integer line 70 program recurse input output 1 display should highlight line 1 no E code generated eg 37 display should highlight line 3 4 display should highlight line T ss line push INTEGER integer push INTEGER onto evaluation stack alloc c 1 allocate top of stack bytes to variable 1 line 4 display should highlight line 4 push INTEGER integer push INTEGER onto evaluation stack alloc c 2 allocate top of stack bytes to variable 2 line 4 display should highlight line 4 push INTEGER integer push INTEGER onto evaluation stack alloc c 3 allocate top of stack bytes to variable 3 function factorial n integer integer label c 1 push PPC onto label 1 s stack line 6 display should highlight line 6 Line 6 display should highlight line 6 push INTEGER integer push INTEGER onto evaluation stack alloc c 4 allocate top of stack bytes to variable 4 pop C V4 pop the top of the stack into variable 4 begin ua SRS s s ee line 8 display should highlight line 8 if n 0 7 line 9 display shoul
3. 68 Critical Instructions A program name input output files const const declarat ion type type declaration var variable declaration assignment statement begin end procedure call if boolean expression J then then clause else else clause case expression of const case body end repeat loop body until ecoa expression J while boolean EES ES loop body lt for VAR EXPR to downto EXPR do loop body E procedure name parameter Kas station procedure body function name parameter declaration function body 3 ittype Figure 25 label none none none none none none alloc pop V none none none none none label label after the entire if statement none label label label none after the entire repeat until statement label label after the entire as while statement label label after the entire for statement none alloc link alloc link E EH and Determination of Critical Instructions O OO J O LN GG LU N H WuLNDPDNNNNNNNNNH HH H H H H H p qa H O w o Jo UB W N H O O 0 J AO UU amp W N H O 69 program recurse input output var ct n sum integer function factorial n integer integer begin ifn 0 then factorial 1 else factorial re n factorial n 1
4. Now look at the BEEN program Siven in Figure 16 There are two branch points inthis programs line 1 and line 11 This program contains a loop in which lines 1 through 10 are executed until I and J are BEN Obviously this loop could kes lt a EEN number of times and each time the label instruction of Iina 1 is ezecuted it EE that the previous program counter should be ehe n onto th label stack of label 1 However except for the very first eine line 1 is executed the previous program counter will always contain 10 There should be a way to take advantage of this repetition and save some naos s i lt The E machine does this in Ene E va Each element of the label stack associated with each branch point has two parts one for holding the value of the previous program counter and one for holding a count as shown in Figure 17 Rather than ju pushing the previous geg counter onto the label stack when a label instruction is executed by the ees the E machine ro compares the BE program counter to the uke stored in the top element of the label stack If these two values are equal the associated counter on the stack is simply incremented thus recording the number of times this label instruction was 56 reached Se previous instruction Thus rather than storing n identico previous program counter values where n is the Aonde of cinas the 100p is iterated only one copy of the paasi e E counter value A saved along with n a tre
5. Stepping further through the program will eventually giva screen that looks like the ereen of Figure 5 The user by this time has stepped through four calls of the recursive function factoral this odd speiling of factorial is the result of a program restriction that limits the names of examples to eight characters The memory section on the right of the screen contains e Memory Locations and their corresponding values associated with each call of factoral By this time the student should have a clearer understanding of how recursion works in this case Certainly program dynamics are demonstrated very well var De result integer result factoral gt function factoral n integer integer factoral 3 computes n factorial recursively n 5 SE factoral begin factoral factoral if n 0 then n 4 factoral 1 mme factoral else factoral factoral n factoral n 1 n 3 end factoral 35 se Eki factoral begin fact n 2 readln n DN Poe so if n lt O then Figure 5 Program fact Screen After Four Calls to Function factoral 11 For the instructor DYNAMOD removes nearly all of the work and frustration from doing a program walkthrough by hand in class By usingan overhead projector equipped with a liquid crystal computer output DEE SE the instructor can run a desired Stee from the library and explain tohis or her students key f
6. and this variable register always points to the current top element of the associated variable stack the only location information that can be lost during normal forward execution is the location of a variable s value in data memory as a procedure or function is exited i e the value on top of the variable stack for the variable Thus upon exit of a procedure or function when the values of local variables including parameters and constants their locations in data menory e normally dost the locations of these variables must be saved on the save stack When backing up through a procedure or function call i e SAS the procedure or function in reverse the original looatdons of th local variables in data memory can be restored to the top of their respective variable stacks from the save stack How can one be certain that the original variable values will be in the Bo ane locations upon backing up e how a BR in data 1 memory is changed The only way this can happen is through an EE operation But e SSES in this chapter a mechanism vas introduced that alloved an E Jastsustion to be EEN Kee even n though a memory TEIN may dave been assigned numerous different values since the procedure exited as backing up occurs that memory location will have been a reset to the teguli value by the time the peoceduse is encountered in reverse 49 Consider the example Pascal program fragment in Figure 13 It consists of a h
7. key which will automatically display RER dealings with the word 14 5 The user will be able to add or modify entries in the index in order to gt create a personalized index The example library will be a comprehensive set of expertly constructed example programs that have been designed to illustrate specific programming constructs This library represents the major philosophical difference between the proposed system and other extant systems The library will exist to illustrate programming E tothe beginning programer Each SEET be quite small compared to an actual useful Ro baal However the examples will have been carefully DEE by an EE to convey particular EECH SE and by observing and experimenting with the examples the user will gain insight into aspects of program execution dynamics that are not readily apparent in other systems By aset uat n certain programming concepts this library in conjunction with the dynamic execution E will provide a programming E in which specific simple experiments can be carried out by the user to illustrate and verify the programming concepts under study At present it is proposed that the text editor of the proposed new system be a syntax directed editor The editor will allow instructors to enter carefully designed programs into the library and also allow users to enter and experiment with programs of their own Syntax Usassa editors have been shown to be effective in a lea
8. variable in data memory to arrive at individual elements The Save Stack To see how backing up is accomplished with this method of representing variables the role of the save stack must be explained The first thing to 45 consider is the kinds of information associated with a variable There are two kinds the location of the variable s memory and the data in the variable s memory location Both are subject to destruction or loss during normal program execution It is easier to see how the second type of information the data can be destroyed Whenever an assignment is made into a variable the old data in the variable s memory location is destroyed Therefore in order to restore the E machine s state to the state prior to the assignment it is De to save the old data This is done on the save stack Upon backing up ge old variable value can then be restored by retrieving it from the save stack Now consider the case of a memory location Recall that the data memory location of a variable is kept in the stack corresponding to that variable In the case say of a Pascal global variable the single stack element for that variable continues to point to the proper data memory location for that variable throughout the execution of the program Inthe case of a variable again this refers to both local variables and parameters in a procedure or function however the data memory location and hence the pointer to this location on the v
9. BEER 5 and the E machine Hee just executed line 1 Proceeding sequentially wach the execution of the program results in I and J being compared onde again Ir doai not equal J and the E machine executes EEN Sege incrementing I until line 10 is ahaa At this point the branch to label 1 is executed The execution of label 1 causes the address of the instruction executed just prior to the label 1 10 to be 58 pushed onto label 1 s stack This results in the label stack of Figure 20 Notice that no new address was actually pushed onto the stack Since the top of the stack had the s it value as the value that was to be pushed the counter of the top of the stack was simply incremented from1 to 2 If the address had been different than the value of the top of the stack a new value and counter would have been pushed onto the top of the stack Figure 19 Label Stack After 1 Loop Iteration Figure 20 Label Stack After 2 Loop Iterations How to reverse through a label instruction should now be clear The address on top of that label s stack is simply placed in the program counter If the corresponding count is one the label stack is also popped otherwise the count is just decremented 59 Critical vs Noncritical Instructions Early on in the chapter it was mentioned that machin running backwards ena a high level language EE executing backwards represented similar but not identical processes The reason this is so is that one hi
10. a start on the solution The primary contribution of this work is the design and definition of an Education Machine or E machine The E machine is an abstract computer whose emulat ion on susi computers will allow for the E EE of all of the desired features of the proposed new software system to replace DYNAMOD Chapter 2 contains a description of DYNAMOD its advantages and limitations Chapter 3 provides a description of Ene system proposed to succeed DYNAMOD Chapter 4 is a review of relevant literature and a discussion of some existing systems that employ techniques similar to those to be incorporated into the new system Chapter 5 contains the development and final design of the E machine Chapter 6 provides a number of examples of Pascal programs and demonstrates their translation into E machine code Finally Chapter 7 describes new directions for the 4 project Chapters 1 4 contain background material essential to understanding the original work contained in Chapters 5 7 CHAPTER 2 DYNAMOD DYNAMOD stands for DYNamic Algorithm MODerator DYNAMOD isa software system the result of a pilot project that SE solutions to the problem of teaching and learning program execution dynamics The first primitive version was written by a deaf student to illustrate some concepts which were being presented in class the student could not follow the discussions of the program walkthroughs because the person signing to the student could
11. be set aside for new instance of A A s variable register would point to A s variable stack and the top of A s variable stack would point to the value of the current instance of A in data memory The second stack element would point to the previous instance of A in data memory and so on Most variables are not in recursive procedures and thus will only have at most one instance during E execution In such cases the variable register would point toa variable stack that is just one element deep The case for a variable A with just a single instance is illustrated in Figure 9 Figure 10 shows the situation of a variable A having three instance as the result of three recursive calls to a procedure variable variable data registers stack memory A A s A s stack data Figure 9 E machine Global Variable Implementation 44 Whenever a procedure or function exits the compiled E code will ensure that local variable instances are properly removed from data memory by simply causing the top of the variable stacks to be popped for each affected variable If a variable is totally deactivated as a result its gt variable register will simply point to an empty variable stack variable variable data registers stack memory A A s A s stack data Figure 10 E machine Recursive Variable Implementation Notice that arrays and records can be handled in the usual fashion using offsets in the index register from the first location for the
12. how to compile and run a program Even then the compiled program will generally not give a dynamic display of the Ge in action and no one is around to explain to the student what is happening H What kind of system could be developed to solve the twin problems of teaching and learning program dynamics Such a system should be usable by the instructor to demonstrate a new programming concept to an entire class in a clear flexible error free and repeatable manner The same system should be available for student review at the student s leisure and be easy enough fora true novice to use without detailed knowledge Some of the more important jotai a this system vould be 1 A comprehensive library of expertly constructed examples 3 2 Forward and backward execution of program statements under user control 3 Highlighting of statements being executed 4 Aclear display of variable and parameter values 5 A clear delineation of the variables and parameters local to various procedures and functions A software system called DYNAMOD os 88 was developed over a number of years to incorporate some of these features as an aid to teaching and learning ER While it is still guite useful in this regard both in the See and for individual student use extensive experience with DYNAMOD has uncovered a number of deficiencies It was diretor decided that a completely new approach to this problem was in order this Kesis represents
13. loads it into the program counter Backward Ro operation alloc Lee ra Sg Pops the top value of the evaluation stack pushes the value onto the save stack pushes the address of a chunk of free memory of that size onto the variable stack pointed to by variable register Forward Noncritical Pops the top value of the evaluation stack pushes the address of a Chunk of free memory of that ante onto the variable stack pointed to by variable register Backward Critical Pops the top value of the variable stack Pelaa to by varilabls register and frees the memory allocated pops the top value of the save stack and EE it onto the evaluation stack Backward Noncritical Pops the top value of the variuhie stack e to by variable register and frees the memory allocated Pushes a 0 onto the evaluation stack link Forward Pops the top value of the evaluation stack and pushes it onto the variable stack pointed to by variable register Backward Pops the top value of the variable stack pointed to by variable register and pushes it onto the evaluation stack 42 unlink Forward Pops the top value of the variable stack pototed to by variable register and pushes it onto the save stack Backward Pops the top uo of Ens save stack and Suokas it onto the variable stack pointed to by variable register Source Program Variable Representation in E machine Code Understandin
14. vs Noncritical Instructions e au a wu we 59 6 COMPILING TO E CODE et 0 e e e 0 e e Ei e bs o os e e 00 00 9 06 09 e e 09 0 00 eg 00 0 e e e e 61 7 e CONCLUSIONS AND NEW DIRECTIONS D 5 e N Li e o e Te S e i o e 0 0 0 e e e 0 0 0 e 74 REFERENCES CITED Rei 76 Figure 1 10 11 12 13 14 15 16 17 18 19 LIST OF FIGURES DYNAMOD Welcome Screen LINE J HUN SIEPPI AINO EE DYNAMOD Library Screen rere esmo da O dC E Dr DO 000 SD 000000000 00 DYNAMOD Program fact SCEeen ssa 644A Are de esa O DYNAMOD Program fact Screen After Partial Execution sees Program fact Screen After Four Calls to Function Factoral for Statement Display Window in a Syntax Directed Editor Help Window for a Syntax Directed Editor eene ee eneen ee e e The E machine asa ROERSCH ERENNERT RENE ee E machine Global Variable Implementation i E machine Pacursive Variable Implementation enee ees Aen a up e Variable and Save stack for a Variable TTT Variable and Save Stack After Assignment to X s sssovsessassssse A pasend Procedure Fragment something dE Variable and Save Stack During Successive Calls to Procedure Something Simple E code Program With a Branch enee enee ae ee a e a pop po e Simple E code Program with a Loop we ge e e ee e e 09900 ee 0 0 oe e e ep 0 o SC e General Label Stack o 0 00 o oe 006 e e e e oe e ee e e e e oe o e e oe e oe e e e oe e e e e e e e oe e e v Label
15. A MONTANA STATE UNIVERSITY The E machine supporting the teaching of program execution dynamics by Samuel Dellette Patton A thesis submitted in partial fulfillment of the reguirements for the degree of Master of Science in Computer Science Montana State University O Copyright by Samuel Dellette Patton 1989 Abstract The teaching of computer programming contains aspects that are found in few other disciplines The mixture of syntactic and semantic knowledge reguired for programming is enough to overwhelm many beginning students An earlier attempt at addressing this problem resulted in a software system called DYNAMOD DYNAMOD 1s a library of expertly constructed Pascal programs and an interpreter that displays the execution of these programs on a computer video terminal in a step by step fashion under user control effectively demonstrating the dynamics or meaning of a program As a proof of concept system DYNAMOD is quite successful but it suffers from several limitations Zn recognition of both the successes and limitations of DYNAMOD it was decided to begin afresh and design an entirely new much more ambitious system The basis of this system is a virtual machine called the E Machine which provides a very flexible structure for displaying the dynamic aspects of algorithms without distracting the student with syntactic details The design of the E machine is the primary work of this thesis Important new features incorporated int
16. CNRS in Geiger of gure 14 shows the state of the stack after procedure something finishes executing for the first time AE se chat it now has the value 1 on rer CR is because vhen the procedure exited the data eet location to vhich P vas pointing vould have ida 51 gt lost so it was saved by the E machine on the top of the save stack Consider now the second call to something in line 2 of Figure 13 and Compare it with section 2 in Figure 14 The top of P s variable stack now contains the value 7 which points to data memory location 7 which contains a 5 Now any references to P will refer to memory location 7 1 e tothe value 5 When procedure something is exited this time the top of the variable stack would again be lost if it were not saved Thus the 7 on top of the variable stack for P is pushed onto the save stack by the E machine resulting in the save stack configuration of section 2 in Figure 14 The third call to procedure something follows in exactly the same manner When the procedure is executing the variable P refers to the data memory location contained on the top of P s variable stack and when the procedure ends that data memory address is pushed onto the save stack Reversing through these procedure calls simply consists of popping the addresses oft the save stack and pushing them onto P s variable stack when reversing through the procedure s exit and popping the top of P s variable stack when rev
17. ICE ALICE 89 ALICE is a anes directed editor and interpreter for Pascal that was specifically designed for student use Some of ALICE s features are 1 Templates for fill inthe blank style program entry gt 2 A comprehensive help system over 600 help screens 3 An E iAtarpretar that allows the user to step through the execution of his or her program one statement at a time 4 E EE setting capability in ther manner of a n debugger another sy system em designed with the student dr in mind is Dr r pascal by Visible Software visible 891 This systen has many educational features Dr Pascal consists of an aivan ang a display system fo for showing program execution The editor is a standard text editor not a syntax directed editor Hat allows users to enter and modify programas The display systen of Dr Pascal is quite good In Dr Pascal each panies is placed on the screen as it is executing If the procedure is too large to fit on the screen the display is adjusted so that the currently executing line is always on the screen 22 As new procedures or instances of procedures are invoked the old procedure calls are scrolled off the top of the screen This gives the user a good intuitive feel for how recursive calls to a function or procedure execute One of the main disadvantages to standard debuggers for student use nis that they give little indication of depth of recursion or even the fact e a recursive call
18. OSTA memory will contain the E code program CUERONEAY being executed by the e E machine l The SE counter will EE the address in program mense of the current E code 1 EE to be executed The previous a SE needed for eet purposes will GEN the DEE ES f program memory of the m most recently executed E code Ee The line numpec gett will ee the line met of the high v es language pz program statement corresponding t to ene gt group of E sde ee currently being executed the Line number will be seeded 1 by the dynamic display ee to highlight the Ge high level source program line belas GE The EES registers are an unbounded number of EES that will be assigned t to E progran variables constants ar and parameters during D e from Ehei source Program ro E code Each identifier name representing memory in cho source EN will Gs assigned one EES E register in the E machine As one ECH SEA in Figure 8 the re registers only Gontela pointers to indi sddu n variable Be EN which in turn contain pointers into J t menory were the EE variable values are REN the SE this complex arrangement will become Ge variables are discussed more thoroughly 1 below The label A pa DH unigue EE of i E machine required for backup PS geg E an unbounded number of these See and as described later they d EH to keep tr ek k of E code TR instructions 4 in an E code program for backup purposes Each E code label statement will be assi
19. Stack After 0 Loop Iterations 0 6 e e e e e 0 ee ee 0 4 4 4 e e ee e e 1 4 e e e Label Stack After 1 Loop Iteration eeeeeneeeeee ee ee ee een o e Page 6 q 49 50 53 56 56 57 58 vi LIST OF FIGURES Continued Figure Page 20 Label Stack After 2 Loop EE Ra 58 21 E code Translation of X X Y 17 2 2 eneen 60 22 Example Pascal PIDE clica nad EEE E E 63 23 Symbol Table For Pascal Program EE EE 65 24 Ad Hoc Packetizing Method for Beet Geesen 66 25 Packetizing and Determination of Critical Instructions EE ep 26 ge Packetized Pascal Program EEN 69 27 Example In Line E code Translation of a A Packetized Pascal Program PP coco rosa cnc 00 000 70 72 vii ABSTRACT The teaching of computer programming contains aspects that are found in few other disciplines The mixture of syntactic and semantic knowledge required for programming is enough to overwhelm many beginning students An earlier attempt at addressing this problem resulted in a software system called DYNAMOD DYNAMOD is a library of expertly constructed Pascal programs and an interpreter that displays the execution of these programs on a computer video terminal in a step by step fashion under user control effectively demonstrating the dynamics or meaning of a program As a proof of concept system DYNAMOD is guite successful but it suffers from several limitations In recognition of both the successes and limitations of DYNAMOD i
20. ackward execution of program statements under user control As stated EEN the virtual E machine will allow seat ee of the necessary dynamic display features especially the forward and backward execution of programs 17 As a prelude to discussing the E machine the next chapter is devoted to an examination of the literature and a number of existing software systems that appear to incorporate many of the features proposed for the new system describedin thisthesis e 18 CHAPTER 4 REVIEW OF LITERATURE AND EXISTING SYSTEMS The idea of a computer based teaching aid for displaying program execution dynamics is not new Some such aids were surely developed for local use only and never polished and published Others had limited appeal because of being restricted to expensive specialized hardware Early references to such systems include Ross 81 82 and Hille 83 The papers by Ross 81 82 describe the early work that led to the DYNAMOD system Ross 88 In Hille 83 a system for the visible execution of Pascal programs is described The system accepts a Pascal program as input and processes it as follows Each of the original statements in the Pascal program is passed through unchanged Immediately after each statement a ee statement is inserted that consists of a writeln statement along with the line number of the statement The new augmented program is then translated into a PL 1 program that is in turn executed step by st
21. and flexible system that would better address the needs of both teachers and students of programming and introductory computer science The proposed system of which this thesis isan important part is described in the next chapter 13 CHAPTER 3 PROPOSED SYSTEM The eventual goal of the system of which this thesis is a small but critical part is to SE a DE E introductory computer science teaching and learning software package The system will run in a windowing ahvir nnent likely X Windows Pountain 89 and include such features as an interactive textbook a large library of expertly constructed example programs an editor for entering and modifying text and programs and a DYNAMOD like driver for interpreting programs and displaying their execution dynamics e The interactive textbook will be a hypertext CACM 88 system that will allow the user to interact with and modify the textual information of the book Some of the planned features are listed below 1 The user will be able to highlight text on the screen the highlighting will E for future readings d E 2 The user will Sa apie to place the cursor on a footnote and hit an expand key and the entire reference will pop onto the screen N 3 The user will be able to execute program Fragmenta and examples from the text in a dynamic DYNAMOD like EECH 4 The user will be abie to interact with the index by highlighting a vora and Kiai the index
22. anslation of X X Y 17 72 2 61 CHAPTER 6 COMPILING TO E CODE The actual design of a compiler for translating some high level programming noussee e g Pascal into E code as well as other applications for the E machine is left for others However this chapter is included as a starting point to assist those who will e developing compilers for the E machine The following description is only a guide to the most important considerations facinga compiler writer and is not meant tobe complete Recall that the purpose of the E machine is to allow high level programming language execution dynamics to be displayed dynamically Sp an aid to teaching and learning programming Therefore when the dynamic geg interface is to show a high level language program executing both the high level language source program and the compiled E code program must both be available DE the E code program will be execut ing However to the user it must appear as if the high level E ER EE were executing This can be accomplished using two E machine components the line number register and the variable registers Recall from Chapter 5 that the line number register contains the line number of the DH program SE that was SE into the E code instruction group that is currently executing The Se display ee will use the information in this register to indicate to the user which source program statement in his or ber program is executing 62 Generatin
23. ar to the one described in this thesis Alone however it does not encompass the needs addressed by this thesis Interactive program debuggers also contain elements of the dynamic display system proposed here Many if not most good program development environments incorporate a debugger A good debugger has such features as 1 Line ata time program EH 2 A display of variable EE during execut ion 3 RR S for PR T break points N e halt ig Ce 4 de e for changing is values of OTA ia EH An example of ge excellent interactive program debugger is the Turbo Debugger that comes with Turbo Assembler produced by Borland Turbo 88 20 It incorporates all of the above features along with other special features including the ability to examine the state of the microprocessor and machine registers It allows the user to easily specify which variables to display and when to display them It also Allows the user to specify break points either by line number or by a condition such as when a variable changes value These features make this a valuable tool for the production DE Similar features are planned for the new system described in this thesis However it should be clearly noted at this point that in spite of apparent similarities between the dynamic display system proposed here and high quality debuggers available on the market there are some crucial Geer that arise from ES EE dicferent koit behind E proposed dynamic d
24. ariable stack may change with each call That is each time a call to the procedure or function is made a different data memory location may be allocated for the value of the variable and pushed onto the top of that variable s stack upon return from the procedure or function that address will be popped off the variable s stack Se the variable is deallocated At this point information critical to backup would be lost if the address popped off were not saved in some way 46 This is where the save stack comes in Whenever any information is about to be lost in one of the above fashions the information instead is pushed onto the save stack Figure 11 shows the initial variable register variable stack and data memory location for a variable X Also included is the save stack variable variable data save registers stack memory stack s LI x X s X s stack data Figure 11 Variable and Save Stack for a Variable X Notice that the save stack is empty now Technically this situation could not arise since x has a valua at this point and therefore at some point in the past must have had an assignment statement performed upon it which would have reguired the old value to be pushed onto the save stack For purposes of this example we will ignore this fact Now let s perform an assignment operation X 27 The effect this will have upon the E machine s structures is shown in Figure 12 Noticethat the top of the sav
25. be identifiable How can branch points be identified by the E machine as it executes an E code program The characteristics of a branch point are easy to categorize A branch point is any instruction that can be executed in some order other than v v uentialiy from the instruction immediately preceding it Most such instructions can be readily identified since branch and call instructions require a label as one of their arguments any instruction that is a branch point because of a branch or call must be an E code label instruction This leaves one class of branch EH still unidentified those arrived at by a return from a procedure or function 54 The return instruction does not and indeed cannot have a label as an argument instead control must be returned to the instruction immediately following the call that invoked the procedure or function the utility of a procedure or function lies in the fact that it can be called from anywhere and after execution will return to the instruction immediately after the call From the above discussion it is clear that each E code instruction that immediately follows a procedure or function call is a branch point However examining an arbitrary E code instruction in isolation does not allow one to determine whether the previous instruction was a call Thus gt some sort of mechanism must be employed to mark such an instruction as a branch point at compile tim
26. d highlight line 9 push V4 integer push value in V4 onto the evaluation stack push O integer push 0 onto the evaluation stack cmp n integer compare top of stack to next lowest SE ee push result Rr 2s Ae da bneq n 2 gt branch to label 2 if the condition is met then an Yv Ok Ter ma i line 10 display should highlight line 10 gt factorial 1 line 11 display should highlight line 11 push 1 integer push 1 onto the evaluation stack br 3 branch to label 3 3 3 2 else label c 2 push PPC onto label 2 s stack line 12 display should highlight line 12 Figure 27 Example In Line E code Translation of a Packetized Pascal Program 13 14 15 16 17 18 19 20 21 22 23 71 factorial ze n factorial n 1 line 13 display should highlight line label c 3 push PPC onto label 3 s stack push V4 integer push v4 onto the evaluation stack push V4 integer push v4 onto the evaluation stack push 1 integer push 1 onto the evaluation stack sub n integer subtract top of stack from next down push result call 1 call label associated with factorial label ed push PPC onto label Ars stack mult n integer multiply the top two values of the stack push result o end o E ze line 14 display should highlight line 14 unlink 4 pop the top of 4 s variable stack deactivate 4 gt return pop top of the return ad
27. dress stack into the program counter a procedure increment var x integer label c 5 push PPC onto label 5 s stack line 16 display should highlight line 16 line 16 display should highlight line 16 link ep pop address from top of stack push onto label 5 s stack begin un Ei ja W si as line 18 display should highlight line 18 cx xt dy a line 19 display should highlight line 19 push VS integer push V5 onto the evaluation stack push 1 integer push 1 onto the evaluation stack add n integer add top two values of stack l push the result gt POP V5 integer pop the top the the evaluation stack into v5 end e a X UN line 20 display should highlight line 20 unlink 5 pop address off Era label stack return gt pop top of the return address into the PC begin ratte o Se M line 22 display should highlight line 22 sum 05 E gd o Ses s line 23 display should highlight line 23 push 0 integer push 0 onto the evaluation stack POP c V3 integer pop the top of the stack into v3 Figure 27 continued 24 25 26 27 28 29 30 31 72 n re 1 line 24 display should highlight line 24 push 1 integer push 1 onto the evaluation stack pop while label line push push cmp bgeq if line push push cmp bgeq line line push push call label add line push call label line br label end
28. e Since all branch points except those arrived at by a SEN are E code label instructions in any case the same E can be employed to branch points arrivedat by a return The e s n simply be designed to BEEN an E code label instruction immediately following each procedure or function call This technigue ensures that all branch points are s Jabel instructions Thus for successful backup when the E machine executes a label instruction in the forward direction it must save the previous program counter value in some fashion Recall that in the E machine the previous program counter is always maintained in the register by that name Every time the current program counter is changed its old value is first placed into the previous program counter Notice that this structure is gt not a stack Only one value is stored at any one time in the previous program counter 55 In order to save the previous program counter for successful backup then whenever an E code label instruction is executed the E machine employs its label stacks and label registers see Figure 8 Each label instruction isto be assigned a label register at compile time where each label register is a pointer to a unique label stack the reason for the stack is given later Thus whenever a label instruction is encountered by the E machine the value in the previous program counter is pushed onto the stack referenced by that label s register N
29. e evaluation stack and discards it Pushes two 0 s onto the evaluation stack label MODE Forward Critical Pushes the previous program counter onto the stack pointed to by label register gt Forward Noncritical No operation Backward Critical Pops the top value of the stack pointed to by label register amp and places it inthe program counter Backward Noncritical No operation brf Forward Load the program counter SE oe address of the label meee done E z o Backward Ma No voisikin beql bneql bless bleql bgtr bgeql MODE Forward Critical Pops the top value of the evaluation stack and pushes it onto the save stack If the value satisfies the conditional on the branch load the program counter with the address of the label instruction Forward Noncritical Pops the top value of the evaluation stack If the value satisfies the conditional on the branch loads the EES counter with the address of the label instruction Backward Critical Pops the top value of the save stack and pushes it onto the evaluation stack Backward Noncritical aces Pushes EQUAL onto the evaluation stack 41 call E Forward Pushes the current program counter onto the return address stack then loads the address of the label f instruction into the program counter Backward J No operat lon sa return Forward Pops the top value of the return address stack and
30. e execution proceeds sequentially through lines 5 and 6 until line 7 is reached The label instruction of line 7 is the interesting instruction inthis case As seen depending on the values of I and J the instruction executed just previous to line 7 could have been either line 4 or 6 How can it be determined for backing up which one really did precede line 7 The brute force method of solving this problem is simple but very inefficient If at each step the current program counter is stored ona stack all that is needed to restore the current program counter upon backing up is to replace its value with the top of stack value This method _ 53 push push cmp breq push pop label halt Q H O JA W AWD H PUHE Figure 15 Simple E code Program With a Branch will work but it is inefficient for the following reason Most instructions in a program have only one possible previous instruction the one that directly precedes it in the program In the example of Figure 15 only line 7 has more than one possible previous instruction All of the other instructions have only one A more elegant and efficient method to solving this problem then is to identify the instructions with more than one possible previous instruction referred to hereinafter as branch points and only save the previous program counter when one of these instructions is executed in the forward direction In order to do this branch point instructions must
31. e stack now contains the old value of X and that the new value of X is stored in the old memory location In 47 this case the information which would have been destroyed was the data not the memory location variable variable data save registers gt stack memory stack x X s X s stack data Figure 12 Variable and Save Stack After Assignment to X In order to back up at this point all that would be necessary would be to pop the top of the save stack and place the popped value into the memory location pointedto by the top of X s variable stack This procedure allows any assignment to be reversed Preparing for the EH execution of statements that lose location ee is somewhat more D n To understand this task EH recall from the EES section how the E machine architecture SSES for the implementation of high level EN variables remember too that the term variable is used ners to stand for any high level language identifier requiring memory such as actual variables Paramet ens and constants Each variable has a permanently assigned variable register Each variakis register points to a unique associated variable stack 48 Each element of the variable stack is a pointer to an instance of the variable value in data memory the top of the variable stack points to the current active instance of the variable Thus since the location of a variable s assigned variable register remains constant throughout program execution
32. ead projector where 1 An algorithm is written down by hand 2 The names of the variables constants and parameters used by the algorithm are written down separately by hand gt a 3 The instructor steps through the algorithm by hand showing how the variables and parameters change during program execution The purpose of this EE is to teach students the dynamics Or semantics ef a program in gett and to caich students HOW to do SE koi ostaa to verity their e own program EEN There are however some serious flaws to this method of teaching program dynamics v 2 1 This method requires the instructor to simulate a computer by hand a very error prone process 2 If the ee take notes they will generally find deciphering the dynamic i flow of the algorithm i later from their static notes impossible Another technigue sometimes used for teaching program dynamics is to give a student a correct program that implements an algorithm The student then must locate a ge or computer TORREA type in the program compile the program and then run the program This method allows the student to enter and execute a correct program Unfortunately in order to benefit from this type of assignment the student must be a somewhat sophisticated computer user to start with which is certainly not the case with many beginning students In ss n the student must have access toa computer know how to use a text editor and Know
33. eader definition D procedure something with one value parameter there are three calls to that procedure from another routine The lines labeled 0 1 2 and 3 have EE sections in Figure 14 Figure 14 contains the variable structures and the save stack that correspond to each of the procedure calls in Figure 13 The section labeled 0 in Figure 14 refers to the state of the structures before any procedure call has been executed Notice that the save stack is empty and notice too that the variable stack for P is also empty Procedure something P integer a e something 7 something 5 something 16 W PD H O Figure 13 A Pascal Procedure Fragment something Now let s Se line 1 in Figure 13 This is the first call to procedure something Notice that during the call P s stack in section 1 of Figure 14 now has a value 1 which is a location in data memory Notice also that the data memory location which this points to data memory location 1 Konalan the value of the parameter which was passed to something Pustan this call any references to P are referring to the data memory location that is eege by the top of P s variable stack 50 Variable structures Save stack after UNI get vets Procedure call Te SEN data save registers stack memory stack 2 SLI 3 ZE en CT Phat Pia i saava stack data stack Figure 14 Variable and Save Stack SES succes sive Calls to Procedure something The save
34. eatures of program dynamics Furthermore students can ge the same program later or perform assignments related to programs in the DYNAMOD library Thus DYNAMOD addresses many of the needs of teaching and learning programming by providing 1 Error free repeatable walkthroughs of algorithms 2 Ease of use ina classroom setting 3 A large library of expertly constructed programs for review by uninitiated students 4 Effective display of the dynamics ofa program in execution DYNAMOD also allows an instructor or student to alter program input and watch the effects of such changes on program execution and statement counts Among other things this feature can be used to demonstrate the notions of time and space complexity As a proof of concept pilot project DYNAMOD is quite successful However DYNAMOD contains many limitations which must be v dresse in order to HEH a truly robust powerful ysten for supporting the goals of teaching and learning SE in a hypertext CACM 88 environment Some of the more crucial limitations are these 1 Pascal is the only programming language supported 2 A user can only step forward in the program 12 3 It is not easily extensible to include complex constructs such as records and user defined types 4 It does not allow general program entry or modification by users Consideration of these drawbacks coupled with extensive use of DYNAMOD led to a vision of a completely new
35. eger loop nesting operator parameter procedure readin real record recursion repeat search sort sqrt stats summing then trailer type var while writeln Select 1 of the following 1 QUIT 2 Display categories 3 List examples in a category 4 Extended listing of examples in a category Execute an example o Figure 2 Sen DYNAMOD Library Screen For example suppose that after reviewing the program names indexed under category recursion the instructor or student wishes to review program fact Typing a 5 causes DYNAMOD to prompt for the program name at 8 which point fact is typed by the user resulting in the screen of Figure 3 On this screen the symbol gt indicates the line currently being executed The Statement Count is the number of lines that ade been executed so far The area on the right of the screen bordered by dashed lines will contain the display of the program ceased at this point no memory is in use since the var RER has not yet been executed Finally the 5 at the bottom left part of the screen is the input that the program will use gt program fact gt e EE an EES n and computes nt var n EE function factoral n integer integer deen n factorial recursively begin W sse if n 0 then factoral ze 1 else E a N gt factoral Ze n factoral n 1 end RES Ge act Statement Count EE EEN Figure 3 DYNAMOD Program fact Scre
36. en At this point the user can step through the program by hitting the return key At each step DYNAMOD moves the arrow to the next statement to a be executed and waits for another return before executing the new statement As can be seen in Figure 3 the entire program rarely fits onto the screen all at once However DYNAMOD keeps as much of the program on the screen as possible Also when an instructor is initially installing a program into the DYNAMOD library he or she can specify blocks of lines that should be displayed together a o 2 lt 5 ba Se Ge re the user has stepped through the variable declarations the screen will appear as shown in Figure 4 Notice that the variables n and result now are displayed in the variable section on the right of the screen the guestion mark indicates that their values are currently undefined From this the user learns what the action of the var statement is no i no esmo fact begin factoral 334500 n if n 0 then result gt factoral 1 saa else M factoral n factoral n 1 end factoral begin fact Kei be YSIN ien EC gt readln n K Dem wy gt if n lt 0 then As writeln bad data n n 1 else begin result Ze factoral n sv writeln n 1 factorial result 1 end end fact tm em Statement Count Figure 4 DYNAMOD Program fact Screen After Partial Execution 10
37. ep by a PL 1 interpreter This system represents a direct solution to the problem of displaying program execution dynamics but it does not include or apparently allow easy inclusion of many desired features such as backward execution SPREE relaten Systems for Keel dese oe program dynamics focus on the RR oa RK ER of data structures and the EES of data sa an algorithm rather than ene overall ias of program dynamics A recent good gt A paper on this SE of ZE RE is Brown 881 This paper 19 describes the Balsa II system Balsa II is a system for displaying the variables and data structures used in a program in an intuitive fashion rather than by their literal meanings For example the data in an array that is being sorted could be displayed in a meaningful manner by interpreting the value in a location of the array as a vertical line with height based on the value in the location Then a sorting routine could run and gradually the lines would be sorted into ascending order by height The user could see the sorting happening by watching the random collection of lines of various heights form into a triangular shape the lines being arranged from smallest to largest in height When the triangle becomes smooth the values will all have been sorted This system shows strong promise of becoming an effective pedagogical tool in the teaching and learning of algorithms Its features could become part ofa new system simil
38. ersing through the procedure s entrance on x S A ue tr The Label Registers Execution in a Program is Bot a Simple linear affair There are EE calls no subroutines returns from subroutines and other non igi laa LAL types of instructions that ada complexity to the problem of backing up We have seen how to reverse many E machine instructions 52 utilizing the save stack What we haven t yet determined is how to reset the current program counter so that it points to the proper previous instruction If the current instruction was arrived at from some instruction other than the immediately preceding instruction e g viaa branch instruction there must be some method aveilebis for recovering the line number of the instruction branched from For example Figure 15 gives a simple E code program for clarity variables are referred to by name rather than their variable registers and addressing modes data types and critical and noncritical designators have been omitted The program does the following I s value is pushed onto the evaluation stack followed by J s value The cmp instruction of line 3 then compares the top two stack values consuming these values and pushing Eis result of the comparison onto the stack Notice line 4 if the top of stack value denotes egual a branch must be made to the label 1 instruction which is in line 7 that is the current program counter must be set to 7 Otherwis
39. f the evaluation stack and Poanes FRERE sum onto the evaluation stack a Backward Critical Pops the top value of the evaluation stack and discards the valaa Pops the top two elements of the save stack and pushes them onto the evaluation stack Backward Noncritical Pushes a 0 onto the evaluation stack sub MODE TYPE Forward Critical Pops the top two values of the evaluation stack pushes the two values onto the save stack and then pushes the bottom value minus the top value onto the evaluation stack Forward Noncritical Pops the top two values of the evaluation stack and pushes the bottom value minus the top value onto the evaluation stack Backward Critical Pops the top value of the evaluation stack and discards it Pops the top two values of the save stack ana pusnee them onto the evaluation stack E we d Backward Noncritical Pushes a 0 onto the evaluation stack 38 mult MODE TYPE div neg mod Forward Critical Pops the top two values of the evaluation stack pushes the two values onto the save stack and then pushes their SCC onto the evaluation stack Forward Noncritical Pops the top two values of the evaluation stack and pushes their product onto the evaluation stack Backward Critical Pops the top value of the evaluation stack and discards it Pops the top two values of the save stack and pushes them onto the evaluation stack Backward Noncritical Pu
40. g E code instructions that correctly update the line number register is one of the most important parts of an E code compiler The variable registers are the second component of the SR that will be used by the dynamic display interface in showing source program execution Recall that each variable that is each variable parameter and constant of the source program will be assigned a unigue variable register at compile time Since it will be necessary for the dynamic display interface to update the values of any variables that have changed with each statement execution in the source program it is essential that the dynamic display interface have access to a symbol tablethat associates each variable inthe source program with its unique variable register The symbol will allow the dynamic display interface to ascertain the value of each variable and update the display of variable values The creation of this symbol table is another important task of an E code compiler Recall from Chapter 5 that many E code instructions have two modes critical SC E olodi An E code compiler must Ae iae during translation whether given i code Ee should be used in critical or in noncritical fode N This decision will perhaps be the most compiles part of designing an E code compiler Later in this chapter an ad hoc method for doing this is presented First let s look at one possible method of building the symbol table S straightforward task Conside
41. g E the E machine provides for the implementation of high level source e language variables ts vital to tte the SEN of the E machine especialy in backing up In this s contexte the cer variable marsa to any ege in the source program SE requires memory such as variables DEE and parameters rizst E compiler that MIROR TARER E code Ee of E Pascal programs salsa EEN variable E the Pascal program a unique E machine variable register This is done statically at compile time so that every variable is associated with a unigue variable register for the duration of program execution regardless of Ger ZE variable is currently active or not The variable register for a variable does not contain the value of the vardahia Rather it ERC ies a painter toa unique variable stack for that variable look at riguce 8 again Since each variable register is really only a pointer it will be the same gen Se of whether the variable isa simple variable or for example an array SE The variable stack pointed to by a variable register also does not contain the value of the variable In this case each element of the 43 variable stack is itself a pointer to the actual variable value in data memory The stack is bie because a particular variable may have multiple associated instances Consider the case of a variable A that is local to a recursive Pascal procedure Each new recursive call to that procedure would require that a new data memory location
42. gh level language statement will in general correspond to many machine language instructions For example the Pascal WE statement Y i X Y 17 Z 7zZ will be translated into at least ten machine eege as shown in Figure 21 saly ane of which has any effect on iie values of the variables in this statement the final pop instruction Since the intent of the proposed system is to display the execution dynamics of high level language programs it is unnecessary to be concerned about precisely backing up the E code instructions that only calculate intermediate values This observation led naturally to a classification system for E machine instructions that reflects this situation If an E machine EN destroys EEN necessary for backup in the high Aei language ER it is classified as critical by the compiler if it does not itis classified as noncritical This identification of E code instructions as either critical or noncritical allows the E machine to save for backup EE that information necessary to reverse statements in the high level language program Since the vast majority of compiled E code instructions will be noncritical a large savings in storage space and time is realized 60 However it should be noted that the flexibility is present to accurately back up E machine code line by line by simply designating each instruction as critical push X push Y push 17 push 2 mult push 2 mult sub add pop Y Figure 21 E code Tr
43. gned a unique label register at compile tines A Label register ae turn points N a label PA that essentially 1 maintains a hi story of previous i instructions that Ce a rane to this label 33 The index registar is found in Li PP JON and serves the sane GEES in the E machine Under ona SE the data in a IKL is icc ssed through Elie appropriate variable register 1 However in in the case of high eset data structures suon as a aaa recorda the address of an individual data TON is not at the TARDEN EES directly sccessibic through a a variable register Rather it is stored at a EE offset MERA this memory seat ona When necessary an SE value can be biassa ER Che index register and the E machine can then access the proper memory location as sas sa by an mddres ina mode called Ee indexed N The evaluation stack pointer is also found in real computers CS evaluation stack pointer A track of the top of e the evaluation stack The evaluation stack is GE the results of all arithmetic and logical operations and RA PANNIA are maintained For example in an arithmet ic operation the e operands esa pushed onto the stack and the operat ic is then performed on them The operands are s nsimed by the operation and the result is pushed onto Se the aa EE are performed by popping the top value of the evaluation stack and placing it into a variable The advantages of a stack architecture are well known several popular PR use this de
44. gorous definition is beyond the scope of this thesis The next chapter contains a 73 recap of some of the main points of this thesis and some new directions that this project could take 74 CHAPTER7 CONCLUSIONS AND NEW DIRECTIONS The goal of this thesis was the design of a virtual machine architecture to support research and development in the realm of dynamic teaching aids for introductory computer science courses primarily beginning programming courses Thus this virtual machine architecture vas to support the execution of high level language programs in a fashion that made the display of all facets of program execution dynamics feasible and flexible The most important specification for the virtual machine DH was the requirement for reverse execution This specification arose from experience with DYNAMOD a common reguest from students viewing DYNAMOD examples in the classroom was for the instructor to back up and repeat certain statements Thus was born the E machine a virtual machine that appears to meet the goals of the thesis quitewell Much remains to be done to realize the ultimate goal of a comprehensive teaching and learning tool for introductory computer science An emulator for the E machine must be written a dynamic display interface must be designed and implemented and a user interface dat be developed Furthermore at least one compiler for example a Pascal to E code compiler ER be written It is prop
45. has happened at all Dr Pascal still falls short of what is required in this regard in several ways When a reference parameter is passed toa procedure there is no indication of where the parameter s reference actually is Also the variable display does not show the values of variables which are not in the current scope even though their values are being changed as a result of being passed as reference parameters S To summarize while the debuggers included in production EEN systems similar to Rares Pascal by Borland are of immense help E experienced programmers attempting to ferret out errors in Ge they are too limited and compilar for the beginning programmer ane vannet be adapted easily to the teaching and learning environment envisioned here ALICE and Dr Pascal are more suited to the teaching and learning environment but they still are oriented towards the production side of programming That is their primary intent is to aid a student in walking through a program of his or her creation in search of errors Neither of these systems incorporates a library of expertly constructed programs for See by students who do not yet have enough knowledge to write a program on their own Also missing are facilities for stepping backwards through execution explaining new programming concepts and SEogkan fragment execution which are all features of the system proposed in this thesis 23 There have been many articles written about using virtual
46. iently In chests 4 some systems a 1 are described that incorporate t these features 16 HELP WINDOW FOR variable Se expression TO IDOWNTO expression DO BEGIN NE END The FOR statement is a statement for repeating a group of statement a given number of times The variable identifier put in place of the variable location is given the value of the first expression If the variable is greater than the second expression in the case of TO the loop is ended and the statements following the END are executed If the variable is less then the second expression in the case of DOWNTO the loop is also ended Otherwise the statements between the BEGIN and END are executed Then the variable is incremented if the TO was chosen or decremented if DOWNTO was chosen and the loop goes back to the comparison above The variable used in the FOR statement is treated as a normal variable in all ways except one It can not be used on the left side of an assignment statement Also after the loop is ended the value of the variable becomes undefined It does not retain the value it hadinside the loop Figure 7 Help Window for a Syntax Directed Editor In summary the new system proposed to succeed DYNAMOD will have all of the features of DYNAMOD with some notable improvements The most notable enhancement to the display of Program execution dynamics will be the capacity for both forward and b
47. iginal value of the variable on the left The intermediate values computed by various E code instructions are of no consequence Hence such instructions can be classified as noncritical and their effects ignored for backup purposes A particular E code instruction can be classified as either critical or noncritical in different circumstances Different high level languages will often have quite different statement sets and what needs to be remembered for backup purposes may differ substantially from one language to another It will be the responsibility of the compilers for each high level language to produce the correct E code involving critical and noncritical instructions for allowing backup E machine System Overview With chase DEE for backing up in mind it is now De to describe the architecture of the E machine in more detail Figure 8 depicts the logical structure of the E machine After some deliberation a stack based architecture was chosen over other possibilities for its inherent simplicity As can be seen however there are a number of components not found in real stack based computers 31 Label Label Registers Stacks st Evaluation Stack Evaluation Register Stack Return Address Return Stack Address Register Stack Save Stack Save Register Stack Figure 8 The E machine Variable Registers Variable S Stacks 5 a Program e e Counter Previous Program Counter 32 TE
48. ion with Changing Machines A Proposed Solution Communications of the ACM vol 1 no 8 Turbo Debugger 1988 1800 Green Hills Road Scotts Valley CA Borland Internat ional User Manual for Dr Pascal 1989 P O Box 7788 Princeton NJ Visible Software
49. is a method ss dividing the EE EE into a set of packets where aach packet represents the smallest unit of a source program to be highlighted by the dynamic display interface as execution progresses Until now it has been assumed that th dynamic display interface would simply highlight the current source program statement being executed However in Steg high level languages a statement can be guite complex e g an if statement A packet will represent smaller components of the source program that will need to be highlighted by the dynamic display interface The compiler writer must use his Or her knowledge of the high level programming language to decide how to packetize that language Then it must be deteratasd dn the E code where critical instructions are to occur in translation of packets and EN types of critical instructions to employ Figure 24 is a diagram showing how Pascal can be packetized Following the example of Figure 24 a packet is defined as the smallest element a user of the dynamic display interface would find interesting This is a venyi dd hoc definition but it should help direct the efforts of a compiler writer who obviously must work in close DEEN with the designer of the dynamic display interface 65 E factorial n 2ncrement x Figure 23 Symbol Table For Pascal Program o The packetizing method EE in Figure 24 can be used in compilation as follows Take each packet in the Avera and wr
50. isplay and BE EEN EES The purpose of Ge debugger as the name implies is to e ON the user to dekas a program The purpose of the dynamic display is to aken che user the dynanio changes in a program during execution A debugger helps a person who already knows how to write a program uncover and fix errors In fact a user must be quite a sophisticated programmer ES obtain the true benefit of a debugger The proposed dynamic display avatea on the other hand is meant to let a beginner see how various program constructs function Because of this the proposed dynamic display must show much more and different information than a debugger and do this in a clearer fashion It must also accomplish this in a manner that is useful to the utter novice This naturally will make the dynamic display slower and larger than a DE which is not a disadvantage in the setting in which the dynamic display is meant to be used A debugger is meant to be used in a production environment where 21 speed and the production of sophisticated useful programs is all important The dynamic display is meant to be used in a learning environment where an dssstaadins is Che key and small programs for presenting educational concepts is the overriding concern There are Sehes systems on the market that incorporate nen oE tke features of debuggers and the proposed dynamic display but which are aimed more specifically towards education One such system is AL
51. ite out if and where critical instructions may occur in the translation of the packet PSN 25 shows the result of this process applied to the diagram in Figure 24 Notice that the only critical E code instructions are aioe link pop and label Since this is the case a usable heuristic for identifying critical instructions is to make every instance of those instructions critical This will ensure that proper backup will occur but not necessarily in the most efficient fashion If some of these instructions were designated critical when in fact they could have been designated noncritical this would mean some information that is unnecessary for backing up is being stored Finding an optimal way to generate soda for backing up is beyond the scope of this thesis however and will be left for others 66 program name input output files const const declaration type type declaration var s oe variable declaration assignment statement begin end procedure call if boolean expression then then clause else else clause case expression of const case body end repeat loop body until boolean expression while boolean expression dei loop body for VAR ze EXPR tokownto EXPR do loop body procedure name parameter declaration procedure body function name parameter declaration type function body e As Figure 24 Ad Hoc Packet iz ing Meth
52. line halt c V2 integer pop the top of the stack into v2 n lt 4 do 6 push PPC onto label 6 s stack 25 display should highlight line 25 V2 integer push V2 onto the evaluation stack 4 integer push 4 onto the evaluation stack n integer compare the top two values of the stack n 7 if the top of the stack matches the condition branch to label 7 sum lt 10 26 display should highlight line V3 integer push V3 onto the evaluation stack 10 integer push 10 onto the evaluation stack n integer compare top of stack to next down n 8 branch if the top of stack matches the condition then begin 27 display should highlight line sum sum factorial n 28 display should highlight line 27 V3 integer push V3 onto the evaluation stack v2 integer push V2 onto the evaluation stack 1 call subroutine at label 1 Ge 9 push PPC onto label 9 s stack n integer add top two values of the evaluation stack increment n 29 display should highlight line 29 R2 address push V2 s address onto the stack 5 call procedure increment end c 8 push PPC onto label 8 s stack 30 display should highlight line 30 6 branch to label 6 c 7 push address of PPC onto label 7 s stack 31 display should highlight line 31 stop executing Figure 27 continued The translation in Figure 27 provides the intuition for the way that compiling a Pascal program to E code should proceed A more ri
53. machines in computer science applications see for example Elsworth 78 The earliest is probably Share 58 In all cases cited in the literature the purpose of the virtual machine is to reduce the effort needed in constructing compilers See for example Kornerup 80 Just one compiler is nes s to translate a programming language say FORTRAN into the EEN of a virtual machine Then the problem remains of either emulating the virtual machine on each real computer or further translating the virtual machine See into the machine language of each real computer The emulation approach has SE unsatisfactory in real life because an emulation program is invariably slow However this approach was used EE with the P machine and P code of Pascal SE the time when Pascal was viewed as an academic language Ellsworth 78 attributes the design of the P machine to Nori e al and cites Nori 74 As Pascal has become production oriented this emulation approach has been dropped for efficiency reasons In spite of the efficiency problems encountered by others the abstract machine the DEEN approach incorporating an emulator is the most attractive for the new system proposed here The entire purpose of this new system is academic involving the teaching and learning of programming rather NE the development of production programs Speed of program execution will never be a primary mee The E machine and its emulator will require just one E machine emulato
54. mendous savings e o inva NN 1 label 1 2 push I 3 push J 4 cmp 5 breq 2 6 push I 7 push 1 8 add 9 pop I 10 br 1 11 label 2 12 halt gt Figure 16 simple E Ean N SES a Loop Aadress Counter Figure 17 General Label Stack Look again at Figure 16 and consider what will happen to the label stack for the branch point instruction at line 1 as the E machine executes the instructions Assume that I equals 3 and J eguals 5 The E machine will step sequentially through the instructions starting 57 at 0 When the label 1 instruction at line 1 is executed for the first ime the address of the the instruction executed just prior to it at this ink instruction 0 is pushed onto label Lia label stack resulting An the label stack of Figure 18 Figure 18 Label Stack After 0 Loop Iterations As the E machine continues dred eina I and J will be compared they will be found to be geg equal and so the E machine will continue executing sequentially incrementing I in the process until line 10 is reached At that point a branch to the label 1 instruction is executed which loads 1 into the program counter When A label 1 instruction is executed the address of the instruction that was executed just prior to this is pushed onto label 1 s stack Since that instruction was the branch instruction at line 10 a 10 must be pushed as shown in Figure 19 At this e in the DEEN the loop has executed once I egiala 4 J
55. ne state at a time is a much simpler proposition than backing up to an arbitrary state in one step Rather than storing the entire state of the machine at each step it is only necessary to store the difference between the previous eat and the current state Ee example suppose the instruction load A A loads the value 4 into the register A No other registers would have been changed by executing this instruction so the only changes to cha state of the machine in most computer models would be to the value in A the program counter and perhaps some status information Saving these changes rather than the entire state of the machine takes much less memory and in a real computer memory is a valuable commodity Therefore the E machine was designed with this method of backing up in mind A natural guestion to ask at this point is whether it is possible to do even better could the previous state be constructed directly from the 29 current state without relying on some saved portion of the execution history The answer is no because of one class of instructions assignment instructions An assignment instruction destroys the value in the register or memory location receiving the assignment the value being destroyed must therefore be saved in order for backup to be possible we One other aspect of the proposed dynamic display interface influenced the design of the E machine The dynamic display is meant to work with high level la
56. nguage programs This led to an important observation the E machine actually has to be able to reverse only high level language statements in one reversal step not each individual low level E code instruction involved in the translation of some high level language statement In particular the state of the E machine has to be restored to the state it was in prior to the execution of the a OUR of E code instructions that are the translation of the corresponding high level language statement This observation led to further efficiencies in ne design of the E machine and to the incorporation of two classes of E machine code 7 instructions critical and noncritical As will be explained further later an E machine instruction is classified as critical if EE information essential to backing up through a high level language statement it is classified as noncritical otherwise In the translation of a high level language statement into E code a number of E machine instructions will be used only for dealing with intermediate values For example in a high level language arithmetic ee a number of intermediate values are likely to be needed in computing the arithmetic value on the right side of the assignment statement before this 30 value can be as signed to the variable on the left However the only value that sado W be restored as far as the high level programming language is concerned Sid backing up through this assignment statement is the or
57. not convey program dynamics along with the words of the lecture This version inspired a formal test system called LOPLE Library Of Programming Language Examples DEE 81 Ross 81 A grant from the apple Education Foundation Ross 80 led to the development of a more BEE version called LING Ng RES 1 82 2 A subsequent geant Se the National Science Foundation Ross 83 allowed LING to be SES and ported from Kuole II mE CECE aroa to other EES including an Amdahl aintsame computer a VAX minicomputer and IBM PC and compatible microcomputers The current vezo lon which runs Agi on VAX and IBM PC and compatible microcomputers is DYNAMOD Version 2 0 Release 2 Ross 88 DYNAMOD is simple for an instructor Or student to use It consists ofa ER of ready to run programs installed by an expert E which i ER can be selected and executed under user control as TARY facets of program SMSen displayed on the is oN can use a mis l in the classroom with relatively little siat By utilizing a personal 6 computer connected to a liquid crystal computer output display device and an overhead projector the instructor can use DYNAMOD to illustrate programming concepts clearly and easily Students can have their own disk containing DYNAMOD which they can then use at their leisure to study concepts that are particularly difficult for them When DYNAMOD is started the first thing displayedis a welcome screen as shown in Figure 1 Option 1 en
58. npublished MS project Computer Science Department Washington State University Nori K V et al 1974 The Pascal lt P gt Compiler Implementation Notes Berichte des Instituts fur Informatik 10 Eidgenossiche Technische Hochschule Zurich Pountain D 1989 The X Window System BYTE Jan 89 353 360 Rezvani S 1981 A Dynamic Library of Interactive Language Examples Unpublished MS project Computer Science Department Washington University 77 Ross R J 1980 A Microprocessor System for the Dynamic Presentation of Programming Language Concepts Grant from the Apple Education Foundation Foundation for the Advancement of Computer Aided Education no 441 1980 1982 1981 LOPLE A Dynamic Library of Programming Language Examples ACM SIGCUE Bulletin 1981 1982 Teaching Programming to the Deaf ACM SIGCAPH Newsletter no 30 Autumn 82 ppl8 24 1983 A Dynamic Library of Programming Language Examples Grant from the National Science Foundation SPE 8263156 SPE 832 0677 1988 DYNAMOD USER S GUIDE Version 2 0 Release 1 1 Technical Report 88 1 Computer Science Department Montana State University Scheftic C and Goldenson D R 1986 Teaching Programming Method and Problem Solving The Role of Programming Environments Based on Structure Editors REES of the National Eeucas tona Comput ing Conference Jun 1986 SHARE Ad hoc Committee on Universal Languages 1958 The Problem of Programming Communicat
59. ns from this thesis are allowable without special permission provided that accurate acknowledgment of source is made Permission for extensive quotation from or reproduction of this thesis may be granted by my major professor or in his absence by the Dean of Libraries when in the opinion of either the proposed use of the material is for schotaviy pucpodas Ray copsias or use of the material in this thesis for financial gain shall not be allowed without my written permission no SE Signature Date iv TABLE OF CONTENTS Page LIST OF FIGURES 2 ccc cece ccc cece cece EE ao EE EE V ABSTRACT EE vii 1 INTRODUCTION sesuais da aa EEN 2 DYNAMOD qtas ana E E E Ee 5 3 PROPOSED SYSTEM PIONI EEE O Ka TAE EE ge a 13 4 REVIEW OF LITERATURE AND EXISTING SYSTEMS OTT 18 5 THE E MACHINE sia A Aa Saeed Wie Ok E eee CEB SK oe eae Poko Design CONSLOSTACLONS EE ha DD O 25 E machine System Overview e e e e e e e oe ee 00 00909009 090 909 00 00 0 0 eege g 00 e e 30 E machine Instruction Set eau soco pa ua E aa ee ee 34 Addres sing Modes e 0 06 0 e e oe o 00 og o eg e e pe e e 0090090 00 e e e e 90 9 0 e 090 o e 35 l Instruction Set e e 6 we o oe SC es Ge e e e Za e e 0 0 0 000 00 00 00 0 90 0 0 e e 4 36 Source Program Variable Representation in E machine Code 42 The Save Stack EE EE 44 The Label Registers 0 9 00 00900 e e e 069 eg eg 00 e e e 0 e ee ee ee ee 0 090 0 ee 6 8 51 Critical
60. o the E machine include among others internal structures which allow forward and backward execution of instructions and simple implementation of value and reference parameters The E machine will eventually form the basis of a comprehensive hypertext system for teaching and learning programming and other fundamental concepts of computer science THE E MACHINE SUPPORTING THE TEACHING OF PROGRAM EXECUTION DYNAMICS by Samuel Dellette Patton A thesis submitted in partial fulfillment of the reguirements for the degree of Master of Science in Computer Science MONTANA STATE UNIVERSITY Bozeman Montana June 1989 ii APPROVAL of a thesis submitted by Samuel Dellette Patton This thesis has been read by each member of the thesis committee and has been found to be satisfactory regarding content English usage format citations bibliographic style and consistency and is ready for submission to the College of Graduate Studies E 6 5 Ja Cet jnd 9 L Date Chairperson Gr duate Committee Approved for the Major Department tala Date Approved for the College of Graduate Studies Jun DS 7709 Aa I ssa D te Gr aduate Dean epartment N iii STATEMENT OF PERMISSION TO USE In presenting this thesis in partial fulfillment of the requirements for a master s degree at Montana State University I agree that the Library shall make it available to borrowers under rules of the Library Brief quotatio
61. od for Pascal 67 There is still one unusual area of code generation that should be mentioned how to generate the E code instructions EE to update the source program line number register This can be done easily once the source program has been packetized Whenever the compiler encounters a left packet symbol inthis case it can generate the command line where is the line number in the source program of the line that contains this packet The line command generated by the nent packet symbol can be considered to be an ena shine interrupt it can have the effect of causing control to Be ere to the dynamic display interface just following the execution of the E machine code corresponding to the See source program s e EE EET and just prior to the execution of the next N packet When the dynamic display interface sends a signal to the E machine to resume the E code corresponding to the next packet of instructions can be executed by the E machine and so A E A sd N EEN of Figure 22 is given in Paure 26 Figure 27 presents a possible in line translation of the program of Figure 26 The mode E e Ee sed for sita instructions and n for noncritical instructions Comments are Deag to help SEH ad translation In the comments PC refers to program Counter and PPC to previous program sent s Figure 27 should also be viewed in conjunction with Figure 23 the associated symbol table for the dynamic display interface Program Packet
62. osed that the emulator all compilers and both interfaces be implemented in C in order to ensure the system s portability to virtually all computer types likely to be used by 75 students Once this has been accomplished the entire package can be incorporated into a hypertext environment built around an online textbook If this looks like a never ending project it is Unlike a commercial system that must support the production people who SSES applications with that system and therefore cannot later EEN E EEN Eeer without disrupting the continued effective use of the system the project envisioned here will suffer no such constraints As a purely academic system it can be changed at will to incorporate pedagogical innovations that support themission Consider the asen E itself As it stands it Ee Cie execution of Pascal a quite well with one exception no provision has been made for handling put n output This wasa conscious mig ion that leaves this portion Of the design to those implementing the dynamic display interface If it turns out that input and output is best handled by the display EEN that will be fine REES if it becomes clear i new EE NN need to be EES to the E machine instruction set to support input and output that will be fane too Other high level programming languages if Bees into this ON may EES require that new instructions be added to the instruction set of the E machine A good example of this eua be the bi
63. r program and then one compiler for each targeted programming language As long as the compilers and the emulator are written in a standard portable high level language they will run with only minor modifications on virtually any computer 24 In the next chapter the E machine s design and implementation will be covered A complete specification is not given because the E machine is intended to have an open ended design that allows later E TERT new features that are deemed important and interesting The specification is however sufficient for the design of an emulator and compilers for the E machine 25 CHAPTERS THE E MACHINE The proposed dynamic display system will consist of various major parts The Education Machine or E machine will be one of the primary components It will be a virtual machine i e computer with its own machine language called E code and it will be responsible for executing the E code translations of high level language e g Pascal programs In addition to the E machine there will be a user interface for user interaction with the system There will alsobea display interface that updates the screen displays These two interfaces together can be thought of as an N operating system with the E machine as the hardware This chapter focuses on the design of the E machine De sign Considerat ions as S E The part sieved by the E machine in the proposed system is central to it
64. r the Pascal program in Figure 22 A simple way to generate a symbol table for this program is juit ee seret at the beginning of the program and scan one line at a time Each time a variable declaration is encountered again this is the extended definition of variable assign the next available E machine variable register to that variable When the last line of the program is reached variable will have been assigned a variable register This would take only a single pass EE the source program The symbol table in igure 23 was 63 Re in this way from the Pascal program in Figure 22 Figure 23 the method used for tagging parameters with the procedure or function to which they belong This same method could be used to tag local variables O O J A LI g U N kA program recurse input output var ct n sum integer function factorial n integer integer begin if n 0 then EES s 1 else o factorial n factorial n 1 end procedure increment var x integer begin x im x 1 end begin sum 0 n em 15 while n lt 4 do if sum lt 10 then begin sum sum factorial n _ increment n end end Figure 22 Example Pascal Program each program 64 Generating E code instructions to update the line number register and deciding whether an instruction is critical or Het can both be handled with the same N technigue This technigue is called packetizing Packetizing
65. rning environment Scheftic 86 n syntax directed editor presents the user with a blank template that the user fills in with the appropriate constructs or phrases Additionally the user can request an explanation of the structure that is currently being used For example the user may be using the Pascal for statement in 15 this case a display similar to Figure 6 may be shen The user eua then fill in the blanks for the entries in s and would then have a valid for structure Ee having to recall from canoes the Esc syntax of a for seat anent This pe of editor eliminates many of the syntax errors ES made by users and allows them to focus on the jay of their x SE program rather than the mans syntactic details of the language e FOR variable i expression FOTDOWNTO expression DO BEGIN END Figure 6 for Statement Display Window in a Syntax Directed Editor gt anotaan seksi EES N tas Er is ksi capacity t to SES b explanations of va various programas de structures For example a user may be able to piac the mn on the FOR Re in the screen of Figure 6 and press a help PS This would then invoke another window that would etsin an explanation of the for BE similar SE chat shown in E SM Figure 7 The combination of the fill in the blank format and the e help windows to tell the users the meanings of the various language constructs enables users ta implement programs more effic
66. s design The E machine will operate as follows It will first be loaded with a compiled E code translation of a particular high level language source program The E machine vill then wait for the user interface to RE E to execute a step SES forward Or backward O Once TA egna has SES received the E machine will execute the segment of E code that corresponds to the current statement in the high level language source program and ines tesa eer ONS the ee EC Following this the display interfaca will note the changes that have occurred in the 26 E machine s state and update the displays accordingly Note that the E machine does not interact directly with the user All input to and output from the E machine is handled through the user and display interfaces The E machine acts as if ie were a dedicated microprocessor whose only purpose is to wait for a signal from outside and then execute its program based upon that signal This definition of how the E machine is to be used allows constraints to be placed upon its design that make the design process somewhat simpler As already noted the E machine is a virtual machine The concept of a virtual machine discussed in the last chapter is central to many computer science applications Compilers and interpreters are the most common examples of systems designed around a virtual machine The design of a virtual machine must take into account the purpose of the application This help
67. s to define and give structure and logic to the virtual Se In the case of the E machine the purpose of the machine is EECH program execution dynamics of high level programming languages to be displayed easily by the dynamic display interface This goal places some considerations upon the E machine s design Most importantly the EE eg 1 Have structures for easy implementation of high level programming language constructs 2 Incorporate a simple method for implementing functions procedures and parameters 3 Be able to execute either forward or backward 27 The driving force in the design of the E machine is the reguirement for backward or reverse EE What does it mean for a machine to run backwards What does it mean for a high level language program to execute backwards As will be seen these two guestions have very similar and related answers but they are not the same In a machine virtual or real the program counter registers main memory and other status information can all be thought of as variables that change as the machine executes instructions These variables can be collectively thought of as the state of the machine If one knows the current state of a machine one knows everything necessary for properly carrying out the next instruction to achieve the proper next state In most machines however the current state does not contain enough information to reset the machine to a prior state That is mo
68. shes a 0 onto the evaluation stack MODE TYPE Forward Critical Pops the top two values of the evaluation stack pushes the two values onto the save stack and pushes the bottom value divided by the top value onto the evaluation stack Forward Noncritical Pops the top two values of the evaluation stack ana pushes the bottom value divided by the top value onto the evaluation stack Backward Critical Pops the top value of the evaluation stack and discards it Pops the top two values of the save stack and pushes them onto the evaluation stack Backward Noncritical Pushes a 0 onto the evaluation stack TYPE Forward Pops the top of the ev luavien stack and EE the negation of that value onto the evaluation stack Backward Pops the top of the evaluation stack and pues the oe of that value onto the evaluation stack MODE TYPE Forward Critical Pops the top two values of the evaluation stack pushes the two values onto the save stack and then pushes the bottom value modulo the top value onto the evaluation stack 39 Forward Noncritical Pops the top two values of the evaluation stack and pushes the bottom value modulo the top value onto the evaluation stack Backward Critical Pops the top value of the evaluation stack and discards it Pops the top two values of the save stack and pushes them onto the evaluation stack Backward Noncritical 2 Pushs a 0 onto the evaluation s
69. sign The return ER aback pointer is a Lee for implenenting EECH and function viin When e call is sain Co a an e machine subroutine the program counter pea one sd saksi onto SE Ee See stack Then nen t the E machine E E a return from subroutine instruction all it has KES do is load the progran s6unter with the top of the SE SC stack 34 The save stack pointer is used to store information required for backup which would otherwise be lost Whenever some critical information as BEE a SCH EE of a ar t len instruction is abate to be destroyed the required information is pushed onto the save stack This ensures that when backing up the instruction that most recently destroyed some D incocmacios san be reversed by retrieving that critical information from the top of the save stack Finally data memory represents the usual random access memory found on real computers but in the E machine it is only used for holding data valuen In real machines a similar situation DEEN in some systems which provide for separate code and data segments in memory On the E machine there is no bound to the available memory or any of the stack memory Implementations on real computers will naturally enforce so bounds but for the academic small program environment envisioned for this system no practical problems are expected to be encountered due to limited memory E machine Instruction Set The E machine s instruction set isa g
70. st machines do not keep track of their history of execution However the machine s history is precisely what must be accessed in order to execute backwards Howcan this information be retained The previous states must be DE That is ven ue present state of the machine there must be a mechanism for changing this state to an arbitrary past state The brute force approach to solving this problem is to store each current state of the machine just before each new instruction is executed all instructions change the state of a machine Then when the machine is to be restored to some prior state all that has to be done is to load the machine with that state and the operation is done With this method the machine can be restored to an arbitrary prior state in one step 28 The brute force method is unnecessarily a and also very inefficient For example this approach would require that all of main memory be stored with each state even though at most one memory location would have changed from state to state as single TAERE were executed A better approach would be to have the machine save the minimal amount of information necessary to recover just the previous state from the current state in a given reversal step The machine could then be restored to an arbitrary prior state by doing the reversal one state at a time until the desired prior state were obtained For the purpose of the E machine this approach is sufficient Backing up o
71. stant mode described above in that this j used ently to BEEN the number of an E code label or o machine variabile register The MODE argument determines whether the eege is to be ege as critical or noncritical The exact method for replacing the ADDR TYPE and MODE designators is unspecified and will be left up to ane ENEE of qe E machine emulator Backing up through a noncritical 4 saatauetien esta requires that something be pushed onto the evaluation stack to keep the stack of the EES size in such cases an arbitrary dummy value ES used push ADDR TYPE Forward e Pushes the value in ADDR onto the evaluation stack 37 Backward POP Pops the SR value of the evaluation stack and stores it in ADDR MODE ADDR TYPE BEE lt Pushes the value in ADDR onto the save stack and then Pops the top value of the evaluation and stores it in ADDR Forward Noncritical Pes ge Eb Pops the top value of the evaluation stack and stores it ia ADDR Backward Critical T 2 i a Pushes the value in ADDR onto the evaluation stack and then pops the top value of the save stack and visa it in ADDR Backward Noncritical Pushes the value in ADDR onto the evaluation stack add MODE TYPE Forward Critical Pops the top two values of the evaluation stack Sashes them onto the save stack and then pushes their sum onto the evaluation stack S E Se EE 35 Forward Noncritical Pops the top two values o
72. t level operations of C The E machine vas intended to be an open ended project from the start a In ns on it is hoped that the E machine will not just sit ona shelf and gather dust but that it will soon be implemented and become a part of the envisioned dynamic sl and learning uneen Taere is every reason to believe that this will be the case 76 REFERENCES CITED ALICE The Personal Pascal Looking Glass Software Limited 124 King St N Waterloo ON N2J2X8 a Brown M H 1988 Exploring Algorithms Using Balsa II COMPUTER vol 21 no 5 May 88 pp14 36 Communications of the ACM 1988 Special issue on hypertext vol 31 no 7 Jul 88 E ss SC Elsworth E F 1978 Compilation via an intermediate language N The Computer Journal vol 22 no 3 Aug 79 pp226 233 L N HilleR F and HigginbottomT F 1983 A System for Visible Execution of Pascal Programs The Australian Computer Journal vol 15 no 2 May Kornerup P Kristensen B B and Madsen O L 1980 Interpretation and Code Generation Based on Intermediate Languages Software Practice and Experience vol 10 no 8 Aug 80 pp635 658 _Meng Kawalek L 1983 A Pascal Pedagogical System for the Conversational Monitor System Unpublished MS project Computer Science Department Washington State University Ng C 1982 Ling Users Guide Unpublished MS project Computer Science Department Washington State University 1982 Ling Programmers Guide U
73. t was decided to begin afresh and design an entirely new much more ambitious system The basis of this system is a virtual machine called the E Machine which provides a very flexible structure for displaying the dynamic aspects of algorithms without distracting the student with syntactic details The design of the E machine is the primary work of this thesis Important new features incorporated into the E machine include among others internal structures which allow forward and backward execut ion of instructions and simple implementation of value and reference parameters The E machine will eventually form the basis of a comprehensive hypertext system for teaching and learning programming and other fundamental concepts of computer science CHAPTER 1 INTRODUCTION Teaching most sciences is relatively straight forward A concept is introduced and then Ei example or experiment is presented to demonstrate the concept in action Asa simple example a physics instructor explains the concept of interference and then does an experiment in front of the class to demonstrate interference Similar pedagogical technigues are employed in mathematics engineering chemistry and other sciences Techniques for teaching computer science on the other hand ERT relatively new and often not effective particularly in demonstrating new conceptsinaction lt _ The most common method of teaching programming concepts utilizesa blackboard or overh
74. tack line Forward d s TIEL ag g ege Loads the line number register with then the machine returns control to the dynamic interface and enters await state Backward Loads the line number register with then the machine returns control to the dynamic interface and enters a wait state cast TYPE TYPE Forward Pops the top value of the evaluation stack transforms the value from the first TYPE to the second then pushes the value onto the evaluation stack Backward Pops the top value of the evaluation stack transforms the value _ from the second TYPE to the first then pushes the value onto the evaluation stack cmp MODE TYPE Forward Critical Pops the top two values of the evaluation stack pushes the two values onto the save stack compares the bottom value with the top value and then pushes the result of the comparison onto the 2 evaluation stack i e one of LESS EO and GREATER is pushed Forward Noncritical a E ads got 3882 5 Pops the top two values of the evaluation stack compares the bottom value with the top value and then pushes the result of the Comparison onto the evaluation stack i e one of LESS EQ and GREATER is pushed ea 5 Backward Critical Pops the top value of the evaluation stack and discards it Pops the top two values of the save stack and pushes them onto the evaluation stack 40 Backward Noncritical Pops the top value of th
75. ters the example tege Option 2 displays an acknowledgement screen option 3 displays an instructional manual and option 4 explains the distribution system for obtaining copies of DYNAMOD Normally the instructor or student types a 1 to enter ES e ur at program library Ef DDDDDD Y D Y D D gt D DDDDDD DDDDDD D D D A D A 00000 DDDDDD a 27 N z Soss Dynamic Pdscal Program Library 3 Version 2 0 Release 2 Copyright 1981 1987 1988 All Rights Reserved Rockford J Ross Computer Science Department Montana State University Bozeman Montana 59717 Se H 2 gt Acknowledgements 3 gt Help 4 gt Distribution Figure 1 7 DYNAMOD Welcome Screen 7 Afteralistypedto enter the program library the screen of Figure 2 is displayed In this new screen option 1 exits DYNAMOD and returns control to the operating system Option 2 refreshes the list of categories shown at the top of the screen Option 3 lists the names of program examples indexed by a category there are usually several examples which illustrate the same concept in slightly different vays Option 4 also lists the names of program examples indexed by a category but in addition it includes a brief explanation of what each example program does Finally option 5 allows the user to execute an example array2d assert boolean bounds case char constant div downto else elseif for gt function global header if int
76. uite small but complete set of pence lona these EE allow an E code program to access data v t and simply All ss Logical and E ee operations occur on the evaluation stack Data is stored and recalled asing the variable registers All operations for backing up occur with a minimum of information from the E code le program in guestion in general all the E code program has to do is use the correct form of the SE EES Or noneritical to ensure that backing up can occur correctly 35 Addressing Modes In this section the various addressing modes available to the E machine instruction set are given variable mode V o fe gt top of variable stack gt This mode accesses the data at the memory location given in the top element of the variable stack pointed to by variable register f constant mode This mode is often called the immediate mode in other architectures is itself the integer real boolean character or address constant operand reguired in the instruction Also there are some defined constants INTEGER REAL BOOLEAN CHARACTER and ADDRESS are the size in bytes of an integer SE boolean Ee and address EEN respectively register mode Rf Warlable register F Eop of variable stack This mode accesses the address at the top of the variable stack pointed gt to by variable register This address is the location in data memory of the current instance of variable

31762101777710 - ScholarWorks

Contents

Download Pdf Manuals

Related Search

Related Contents