Chapter 3.6: School -- Reference Locality in Software
"I think we should talk a little more about variables and variable names.
Remember this?" Professor Crane put the second Pascal version of the shoesz
program up on the overhead projector.
program shoesz;
{ Print shoe size table with halves, by Thomas Bright and Rusty Crane }
procedure wrhalf( size: Real );
var
ipart, numer: Integer;
begin
ipart := trunc(size);
numer := trunc((size-ipart+0.25)*2);
if numer > 1 then
begin
numer := 0;
ipart := ipart+1;
end;
write (ipart);
if numer > 0 then
write (' 1/2')
end;
var conv: Char;
st_sz, end_sz, sz, conv_sz: Real;
dbl_sz: Integer;
const cm_in = 2.54;
begin
conv := ' ';
while (conv<>'E') AND (conv<>'M') do
begin
writeln ('Shoe Sizes');
writeln ('Type E for English to Metric.');
writeln ('Type M for Metric to English: ');
readln (conv)
end;
writeln ('Start: ');
readln (st_sz);
writeln ('End: ');
readln (end_sz);
if conv = 'E' then
writeln ('English => Metric')
else
writeln ('Metric => English');
{ Step by halves. }
for dbl_sz := round(st_sz)*2 to round(end_sz)*2 do
begin
sz := dbl_sz/2.0;
if conv = 'E' then
conv_sz := sz*cm_in
else
conv_sz := sz/cm_in;
wrhalf(sz);
write (chr(9), '=> ');
wrhalf(conv_sz);
writeln (chr(9), '(', sz , '=> ', conv_sz, ')')
end
end.
"That was just what, two days ago?"
"Two classes ago. I think I have my copy here."
Several us dug out our notes from that day.
Professor Crane continued, "What do you think would happen if the size variable, sz, in the main procedure were to be renamed 'size', with the exact same spelling as the parameter size in the write-half routine?"
"Problems?" asked Lisa.
Mike's forehead furrowed in thought as he studied his copy of the source. "Well, you're calling the write-half routine from different places, with different variables. That means the names of the parameters you give it must not be going to conflict with the parameter name in the function."
I studied my own copy. "I think Mike's right. A size variable declared inside of write-half would probably conflict with the size parameter, but Pascal keeps the variable itself on the stack, and it must keep the name of variables local to the half write procedure separate in the dictionary somehow."
Professor Crane rolled his eyes and shook his head, then nodded. "They call
that dictionary the symbol table."
Mike turned to give me a sharp look. "Stack?"
George groaned. "What's a stack?"
Pat reached over and poked George in the ribs. "Weren't either of you listening to me the other day?"
Everyone else turned toward Professor Crane. Becky asked, "What are they talking about?"
Professor Crane chuckled. "Something we call locality of reference. In Pascal and certain other languages, variables, constants, and other identifiers are only visible within the block they are declared in, and within blocks declared within the same block."
Pat and I exchanged glances and nods of understanding. Mike, George, and Lisa nodded, hesitantly. The rest of the class just gave him blank looks or shook their heads.
Professor Crane traded the slide for another:
program factfib;
function factorial( number: Integer ): Integer;
begin
if number > 0 then
factorial := number*factorial(number-1)
else
factorial := 1;
end;
function fibonacci( number: Integer ): Integer;
begin
if number > 1 then
fibonacci := fibonacci(number-1)+fibonacci(number-2)
else
fibonacci := number;
end;
var number: Integer;
begin
for number := 0 to 7 do
writeln( number, ': factorial:', factorial(number),
' fibonacci:', fibonacci(number) );
end.
"What do you think will happen? Will it be able to keep track of all those numbers?"
There were nods and shakes of the head and blank looks.
Andrea said, "I sure can't keep track of them all."
She and Becky exchanged looks full of doubt.
"What do you think, Pat?" Professor Crane grinned.
Pat nodded. "Sure."
"How about you, Joe?"
"Oh, yeah. No problem. I'm not sure how the symbols are kept local to each scope in the symbol table, but the values are safe on the stack." I started doodling in 68000 assembler again.
"George?"
George scratched his chin. "Wouldn't factorial calling itself overwrite
number?"
"Mike?"
"Joe and Pat keep saying something about stacks. Is that something magic where you can stack up the numbers and the compiler somehow keeps track of them all?"
"Very good." Professor Crane swapped slides again.
There were a few complaints, but mostly hesitant nods. I put my pencil down to
focus.
"If you put a plate on the stack, where do you put it? Usually, I mean."
Dirk volunteered, "In the center, especially if it's my mom asking me to."
"I don't know you." Lisa turned her head away and sniffed exaggeratedly.
Dirk snickered.
Professor Crane suppressed a chuckle. "And where do you usually take one off from?"
Andrea said, "From the top, of course. Why?"
"We can make stacks in programs, using an array and a pointer." He swapped
slides again.
"The stack pointer points to the number most recently pushed on the stack. If we pop one off, we read it from where the stack pointer is pointing and decrement the stack pointer. If we push another on, we increment the stack pointer and then store it where the stack pointer points."
Pat seemed to be following along okay, I was pretty sure I was, Mike was hanging in there, George was not quite, and the rest of the class were showing various states of confusion.
Professor Crane showed us a slide with the following demonstration code in
BASIC, and walked us through the initialization, the push and pop subroutines,
and the execution of the main part:
10 REM PUSH AND POP SUBROUTINES 20 DIM S(10) 30 LET T = -1 REM STACK POINTER 40 LET V0 = -9999 REM TOP OF STACK TEMPORARY 100 V0 = 10 110 GOSUB 1010 120 V0 = 20 130 GOSUB 1010 140 V0 = 30 150 GOSUB 1010 160 V0 = -9999 170 GOSUB 1110 180 PRINT "POPPED "; V0 190 GOSUB 1110 200 PRINT "POPPED "; V0 210 GOSUB 1110 220 PRINT "POPPED "; V0 1000 END 1010 REM PUSH SUBROUTINE 1020 IF T = 10 THEN GOTO 12OO 1030 T = T + 1 1040 S(T) = V0 1050 RETURN 1100 REM 1110 REM POP SUBROUTINE 1120 IF T = -1 THEN GOTO 1300 1130 V0 = S(T) 1140 T = T - 1 1150 RETURN 1200 REM 1210 REM PUSH ERROR 1220 PRINT "STACK FULL ERROR. CAN'T PUSH "; V0; "." 1230 STOP 1300 REM 1310 REM POP ERROR 1320 PRINT "STACK EMPTY ERROR. CAN'T POP." 1330 STOP
Then he showed us a printout of what running it produced:
POPPED 30 POPPED 20 POPPED 10
We discussed the code for a few minutes, then he showed us demonstration code in Pascal, again walking us through the initialization, pop function, push procedure, and the main execution:
program stackdemo;
const limit = 10;
var
stack: array[0 .. limit] of Integer;
tos: Integer;
errorcode: Integer;
procedure push( value: Integer );
begin
if tos < limit then
begin
tos := tos + 1;
stack[ tos ] := value;
end
else
begin
errorcode := 1;
writeln( 'Stack full ', errorcode, '. Can''t push ', value, '.' )
end
end;
function pop: Integer;
begin
if tos >= 0 then
begin
pop := stack[ tos ];
tos := tos - 1;
end
else
begin
errorcode := 2;
writeln( 'Stack empty ', errorcode, '. Can''t pop.' );
pop := -9999
endfc
end;
begin
TOS := -1;
errorcode := 0;
push( 10 );
push( 20 );
push( 30 );
writeln( 'Popping ', pop );
writeln( 'Popping ', pop );
writeln( 'Popping ', pop );
if errorcode <> 0 then
writeln( 'errorcode: ', errorcode );
end.
The output was essentially the same as the output of the BASIC demo code:
Popping 30 Popping 20 Popping 10
Becky raised her hand. "Can I see that slide that shows the stack of plates and the, uhm, number stack again?"
Professor Crane grinned some more as he swapped slides.
Becky thought for a moment, then asked, "Why? uhm, ... in the subroutines, you're only adding one or subtracting one, but the picture of the array shows, what is that? They're all even numbers. That's adding two. Why?"
"Very good," Professor Crane adjusted his slide. "Very observant, Becky. Pat, what do you have to say about this? Joe? Mike?"
The three of us exchanged looks, then Pat nodded to Mike. "What do you think, Mike? You got this?"
He shook his head.
She turned to me, and I lifted my fist, showing gu. "Rock, scissors, paper."
She gave me a quizzical look.
"No jung? Toss a coin, then?" I reached for my pocket.
"You start."
I refrained from pulling out my coin purse. "I'm not sure I can make it make sense."
"Me neither."
I nodded my head in resignation. "Well, okay." I turned to Becky and said, "Address versus index. The picture of the stack array is showing addresses in memory, but the code uses numeric indexes into the array."
Pat nodded. Out of the corner of my eye I saw the light come on in Mike's eyes.
Becky's eyes reflected something that looked like the beginning of understanding.
Pat asked, "Integers in Pascal are like, two bytes in memory, Professor Crane?"
"Yep. Well, with the compiler we have, yes."
Becky's eyes lit up, then the flame flickered and was replaced again by doubt. She hesitated, then asked, "So one in Pascal is like two in assembler or memory or whatever that is?"
"Right!" Mike exclaimed. "Pascal converts the index number to an address. Multiplies the index by the size of the elements and adds the base address of the array." He paused, then continued. "But ... the BASIC array is going to be more than two, right? BASIC variable are floating point, not integers."
Now Becky looked more confused.
Professor Crane nodded in agreement. "Yep. Most BASICS don't have small integer variables. Just floating point, and BASIC floating point numbers tend to be five bytes each, as a tradeoff between memory requirements and range."
Becky hesitated again before asking, "So the index would be multiplied by five instead of two?"
Professor Crane smiled and nodded in confirmation.
Becky responded with a proud smile of her own.
After a few more minutes of discussion, Professor Crane looked at me and raised his eyebrows.
"What?"
He grinned again. "I thought I saw you doodling a few minutes back.
I glanced at the code I had jotted down before the lesson had gotten interesting.
"Not really."
He looked disappointed. "So you haven't converted the Fibonacci program to 68000 assembler while we've been discussing how local variables work? Or worked out an assembler version of the stack demonstration code?"
"I got interested in class."
That got a laugh from most of the students.
"Oh."
I scratched behind my ear. "Besides, the stack demonstration wouldn't really be all that interesting."
"Why not?"
"68000 machine language has push and pop built in."
"Built-in, huh?"
"Well, I guess they don't test for overflow or underflow."
"No?"
"I guess the CPU architects leave stack bounds checking to the memory
management hardware."
He raised his eyebrows and nodded. "Yes, most CPUs are like that, although I
hear Intel's iAPX 432 might be different. So you don't want to show us what
the demonstration program would look like in 68000 assembler?"
I set my chin to the right and my mouth the left, and pinched my nose
before scratching my chin. "With no bounds checking?"
"Sure."
"Okay." I stood and went to the whiteboard, and wrote out the following, pausing at moments for thought, but not commenting vocally:
STKSZ EQU 11 SSTACK DS.W STKSZ PSTACK DS.L 64 RSTACK DS.L 64 MESSAGE DC.B 'Popping '
DC.B 0 ; end of string START MOVE.L #RSTACK+STKSZ*4,A7 ; for return addresses MOVE.L #PSTACK+STKSZ*4,A6 ; for the parameters MOVE.L #SSTACK+STKSZ*2,A5 ; for the demonstration stack * Main code
* Push 16 bit values on 32 bit stack: MOVE.W #10,-(A5) CLR.W -(A6) ; High word first in memory. MOVE.W #20,-(A5) CLR.W -(A6) ; High word MOVE.W #30,-(A5) CLR.W -(A6) ; High word * Pop and print MOVE.L #MESSAGE,-(A6) BSR PSTRING MOVE.L (A5)+,-(A6) BSR PINT BSR PCRLF MOVE.L #MESSAGE,-(A6) BSR PSTRING MOVE.L (A5)+,-(A6) BSR PINT BSR PCRLF MOVE.L #MESSAGE,-(A6) BSR PSTRING MOVE.L (A5)+,-(A6) BSR PINT BSR PCRLF RTS
Professor Crane frowned. "Your stacks are all upside down."
"Most CPU stacks are, aren't they?"
He turned to the class. "Can any of you guys tell what his code does?"Even Pat was a little bemused. "Can you make it look more like the Pascal and BASIC demonstration code?" she asked.
I grumbled jokingly as I turned back to the board, erased it, and started rewriting, vocalizing both the code and the comments:
* Fully emulating the demonstration stack: SSTKSZ EQU 11 ; Software stack SSTACK DS.W SSTKSZ ; of 16-bit integers SSTKPTR DS.W 1 ; Don't even need 16 bits. * Planning on doing it upside-up, with base in A5.
"I could keep the index in D7, too. But I guess we want to see me manipulate the stack pointer as an index, anyway."
ERRORCODE DS.L 1 STKSZ EQU 64 PSTACK DS.L STKSZ ; parameter stack RSTACK DS.L STKSZ ; return stack * Both are traditional pushdown.
"Sixty-four levels ought to be enough for whatever the library and OS need."
"Two CPU stacks?" Professor Crane asked.
"I think I like two stacks."
MESSAGE_STR DC.B 'Popping ' DC.B 0
"Not counted strings?" Professor Crane asked.
"Seems easier this way. There's no compiler to keep track of the count for me, and this way I don't need to keep track by hand."
"Makes sense."
PUSHERRMSG_01 DC.B 'Stack full. ERROR ' DC.B 0 PUSHERRMSG_02 DC.B ': Can''t push ' DC.B 0 PUSHERRMSG_03 DC.B '.' DC.B 0
I lifted my marker. "Yeah, that's a lot of bits of the message spread out. Oh, well."
"No formatted I/O in the library code?"
"Well, then I would have to explain the library code."
"Ah. Less to explain this way." Professor Crane seemed satisfied.
I continued:
PUSHERR MOVE.L #PUSHERRMSG_01,-(A6) BSR PSTRING MOVE.L ERRORCODE,-(A6) BSR PINT MOVE.L #PUSHERRMSG_02,-(A6) BSR PSTRING BSR PINT ; value waiting on parameter stack BSR PCRLF MOVE.L #PUSHERRMSG_03,-(A6) BSR PSTRING JMP ERREXIT
"Tedious, but nothing difficult to understand. Put what we want to print on the parameter stack, call the routine to print it."
* Upside-up stack! * A5 is demonstration stack base.
"Oh, I should probably have put the base in a variable, too. But I'm doing it this way, now."
"Go ahead and show us how it turns out."
PUSH MOVE.W SSTKPTR,D7 CMP.W #STKSZ,D7 BHS PUSHERR ; unsigned
"That loads the stack pointer, and then compares it to the size of the stack. By using an unsigned compare, we can skip testing the lower bound of zero. But the Pascal source didn't check the opposite end, anyway."
"True."
ADD.W #1,D7 MOVE.W D7,SSTKPTR ; update pointer ASL.W #1,D7 ; adjust index for 16-bit array
"Arithmetic shifting left one is the same as multiplying by two."
Professor Crane added, "Becky, there's your conversion between index and offset to an address."
"Oh-kay." But she didn't really sound all that okay, yet.
MOVE.L (A6)+,D0 ; pop 32 bits of parameter
"A6 in paranthesis says A6 points to the source value. The plus after says that the CPU updates the pointer after the move, by adding the size of what it moved to D0. The parameter stack that A6 points to is 32 bits wide, to save code. That's four bytes, so A6 gets four added to it."
MOVE.W D0,(A5,D7.W) ; store 16-bit integer
"The value stored was only our 16-bit integer, so we only need to store two bytes. And that funky looking index expression in the parenthesis here says that A6 has the base address of the array, and D7 has the offset -- the index we multiplied by two up there. The CPU adds the base and the offset to get the address of the element of the array to store it in."
Becky hesitated before saying, "A6 plus D7 is the address where it's stored?"
"Yeah."
"What's that period double-u mean?"
"W stands for word, and a 16-bit integer in 68000 assembler is called a word. An 8-bit integer is B for byte, and a 32-bit integer is L for long."
"Hmm. Maybe I'm seeing this."
"Great." I continued.
RTS
"The return from subroutine instruction pops the return address from the return stack and loads it into the program counter, which is what Motorola calls the instruction pointer." I paused.
"And the pop routine just reverses this process."
POPERRMSG_01 DC.B 'Stack empty. ERROR ' DC.B 0
"Error message can't tell anyone about a value that doesn't exist, so the message strings are a little simpler."
POPERRMSG_02 DC.B ': Can''t pop.' DC.B 0 * POPERR MOVE.L #POPERRMSG_01,-(A6) BSR PSTRING MOVE.L ERRORCODE,-(A6) BSR PINT MOVE.L #POPERRMSG_02,-(A6) BSR PSTRING BSR PCRLF JMP ERREXIT * POP MOVE.W SSTKPTR,D7 ; Not testing for too high.
"On the 68000, loading a data register sets the condition codes, so we already know if it's zero or minus. Minus would be a stack underflow. And will ignore testing against the other end of the stack here."
BMI POPERR ASL.W #1,D7 ; adjust index for 16-bit array MOVE.W (A5,D7.W),D0
EXT.L D0 ; Make it 32-bit
"We'll extend the sign bit, since we'll be passing it to library functions."
MOVE.L D0,-(A6) SUB.W #1,SSTKPTR ; update pointer
"Conveniently, the 68000 allows us to add that to the index in memory, so we don't have to keep an extra copy in a register."
"Like you don't have enough extra registers to keep a copy," Professor Crane joked.
"Heh. Plenty of data registers we're not using."
RTS START * Runtime.
"First, we set up the return stack pointer so we can do subroutine calls, and the parameter stack pointer so we can pass parameters."
MOVE.L #RSTACK+STKSZ*4,A7 ; for return addresses MOVE.L #PSTACK+STKSZ*4,A6 ; for the parameters
"Wait a minute." Professor Crane stopped me.
"Yeah?"
"Oh, yeah. You said you like two stacks."
"I think so."
"Does the 68000 have instructions to support stack frames?"
"There's a link instruction and an unlink instruction."
MOVE.L #SSTACK,A5 ; emulating the demonstration stack MOVE.L #0,SSTKPTR ; demonstration stack index
Becky muttered, "Okay, there's the base of that array, and the index."
I nodded and continued writing:
* Main code: * push values MOVE.W #10,-(A6) CLR.W -(A6) ; High word first in memory.
"Woops. That should also be sign-extended." I thought for a minute, erased the last line, and changed the line before it:
MOVE.L #10,-(A6)
Pat asked, "The 68000 is most significant bit first?"
"Yeah."
"Isn't that inefficient?"
"Ask the engineers. It sure seems easier for human eyes to read."
I have much stronger arguments about byte order now, but we don't want to interrupt the story too much.
BSR PUSH MOVE.L #20,-(A6) BSR PUSH MOVE.L #30,-(A6) BSR PUSH * Pop and print MOVE.L #MESSAGE,-(A6) BSR PSTRING BSR POP BSR PINT BSR PCRLF MOVE.L #MESSAGE,-(A6) BSR PSTRING BSR POP BSR PINT BSR PCRLF MOVE.L #MESSAGE,-(A6) BSR PSTRING BSR POP BSR PINT BSR PCRLF RTS
When I turned around, only Daren, Andrea, and Alex still looked lost.
"So, how would that change if you used stack frames?" Professor Crane's eyebrows were raised.
"On a single stack?"
"Most system engineers don't want to go to the trouble of supporting two stacks."
"I sure don't know why. But with something this simple, there really isn't a reason for frames at all."
"That might make it easier to understand frames, if they're there."
"Maybe. But I don't think I remember exactly what the link and unlink instructions do. How about if I just show where we can save a stack frame pointer in this code?"
"You can?"
"Pretty simple, really. On routine entry, you just push a copy of the parameter stack pointer, probably on the return stack to keep the parameter stack clean and give the frame pointer some protection. Then just remember to pop it on exit."
I wrote a fragment on the board:
SUBROUTINEA MOVE.L A6,-(A7) ; Mark frame. ... MOVE.L (A7)+,A6 ; Force restore frame. RTS
"Or, since the parameter stack is balanced, instead of loading the parameter stack pointer back, just drop the saved frame pointer off the return stack:"
"Either way, you can load the frame pointer from the return stack whenever you need it."SUBROUTINEA MOVE.L A6,-(A7) ; Mark frame. ... ADD.L #4,A7 ; Drop frame. RTS
"How do you tell the parameters of a recursive call from those of a non-recursive call?"
I had to think for a moment. "Maybe you have to mark the frame before you call the subroutine. Then, I guess, when a routine calls itself recursively, it would do something else:"
ROUTINEA
... MOVE.L A6,-(A7) ; Mark frame.
BSR RECROUTINE ADD.L #4,A7 ; Drop frame.
... RTS
*
RECROUTINE
...
MOVE.L 4(A7),A4 ; Saved PC is top. MOVE.L A4,-(A7) ; Mark old frame.
BSR RECROUTINE ADD.L #4,A7 ; Drop frame.
... RTS
Professor Crane looked at my code with a puzzled expression. "That looks like it might work, actually."
The bell rang.
"Okay, we'll continue this next class. Homework is to write the Fibonacci series code recursively in BASIC."
Groans echoed through the room.
"I've given you enough tools, I think you can do it. Try, anyway. And, Joe, can you look up the link and unlink instructions and bring some code using them, too?"
"Uh, oh, okay. Sure."
(Could I have produced the 68000 assembler code above during my first year back from Japan? I'm not confident I could. But the me in this story has to be able to.)
[Currrent backup at https://joel-rees-economics.blogspot.com/2020/01/bk-33209-school-parameter-stack.html.
Developed February to April 2021, notes at
https://joel-rees-economics.blogspot.com/2020/01/notes-33209-school-basic-vs-pascal-vs.html.
Extracted and expanded from
https://joel-rees-economics.blogspot.com/2020/01/bk01-33209-school.html.
Earlier backup at
https://joel-rees-economics.blogspot.com/2020/01/bk-33209-school.html.]
