-
Notifications
You must be signed in to change notification settings - Fork 3
/
functions.html
303 lines (233 loc) · 11.5 KB
/
functions.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
<!DOCTYPE html>
<html lang="en">
<head>
<link rel="stylesheet" href="https://unpkg.com/[email protected]">
<link rel="stylesheet" href="https://unpkg.com/[email protected]/prism">
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>The Little Man Stack Machine</title>
</head>
<body>
<main>
<h1 class="massivetext">🙋 The Little Man Stack Machine</h1>
<nav>
<p class="tool-bar">
<a href="index.html">Intro</a>
<a href="assembly.html">Assembly & Execution</a>
<a href="functions.html">Functions</a>
<a href="firth.html">Firth</a>
<a href="emulator.html">Emulator</a>
<a href="https://github.com/bigskysoftware/littlemanstackmachine.org">Github</a>
</p>
</nav>
<h1>Functions On The LMSM</h1>
<p>
The LSMS is designed to make <a href="https://en.wikipedia.org/wiki/Function_(computer_programming)">functions</a>,
including <a href="https://en.wikipedia.org/wiki/Recursion_(computer_science)">recursive function calls</a>,
possible, despite the limited resources available to the system.
</p>
<p>
This is accomplished by two registers: the <code>stack_pointer</code> register and the <code>return_address_pointer</code>
register.
</p>
<p>
The <code>stack_pointer</code> register points to the "top" of the value stack, and grows <em>down</em> in
memory. The value stack holds values that are used for computation, such as two numbers that are to be added.
</p>
<p>
The <code>return_address_pointer</code> register points to the "top" of the return address stack, and grows <em>up</em> in
memory. The return address stack holds the return address(es) for a series of function calls.
</p>
<h2>The <code>JAL</code> and <code>RET</code> Assembly Instructions</h2>
<p>
Let's look at how the Jump-And-Link (<code>JAL</code>) and Return (<code>RET</code>) instructions work.
</p>
<p>
Here is a simple example of an LSMM assembly program that asks a user for input, calls a function to square
that number, and then prints the result. Here is the assembly and the assembled machine instructions:
</p>
<img src="img/function1.png">
<p>
A fair amount going on here, so lets go through the program first
</p>
<ul>
<li>We ask the user for input and then push that value onto the value stack</li>
<li>We then load the address of the instruction labeled <code>SQUARE</code> into the accumulator</li>
<li>We then push that value onto the value stack</li>
<li>Next we call the "Jump And Link" instruction</li>
<li>After that we (somewhat mysteriously) pop a value off the value stack and print it.</li>
<li>Finally, we halt</li>
<li>Below all that, starting at a location labled <code>SQUARE</code>, we duplicate the top of the stack</li>
<li>We then multiple the top two values on the value stack and replace them with the result</li>
<li>Finally we call the "Return" instruction</li>
</ul>
<p>
We can generate the same machine instructions, and clarify our code a bit, by using the <code>CALL</code>
pseudo-instruction:
</p>
<img src="img/function2.png">
<p>
This generates the same machine code, but is more readable: it is clearer that we are calling the function
defined at memory location <code>SQUARE</code> now.
</p>
<h2>The LMSM Calling Convention</h2>
<p>
What is the mysterious <code>SPUSH</code> just before the <code>CALL</code> instruction, and what is the
<code>SPOP</code> after it? To understand what these instructions are doing we need to discuss the concept
of a <a href="https://en.wikipedia.org/wiki/Calling_convention">Calling Convention.</a>
</p>
<p>
A Calling Convention is a mechanism whereby a function receives arguments from a caller and returns a value
to the caller.4
</p>
<p>
In the case of the LMSM, the calling convention is very simple: arguments are passed to the function on the
value stack, and the result of the function is left on the top of the value stack for the caller.
</p>
<p>
In this program, we wish to pass the value that the user entered to the <code>SQUARE</code> function, so we
"push" it before we call the function.
</p>
<p>
The <code>SQUARE</code> function then duplicates this value and issues a <code>SMUL</code> instruction, which
multiplies the parameter by a duplicate of itself, effectively squaring the value and leaving that
result on the top of the stack.
</p>
<p>
At this point, the <code>SQUARE</code> function can return to the caller. The caller knows that the result
of the function call has been left on the top of the stack, so it can "pop" it off (from the stack into the
accumulator) and then print it out, and, finally, halt.
</p>
<p>
The caller and the callee use the value stack to communicate with one another: the caller passes parameters in
on the value stack and the caller passes the return value out on the top of the stack.
</p>
<h2>A Function Call Step-by-Step</h2>
<p>
Let's go step by step and watch how this function call works.
</p>
<h3>Step 1: Get Input From User</h3>
<p>
The first instruction tells the LMSM to ask the user for input. Let's say the user entered <code>3</code>.
After this instruction is executed the machine will look like this:
</p>
<img src="img/call1.png">
<p>
Note that the accumulator now has the value <code>3</code> in it.
</p>
<h3>Step 2: Push The User Input Onto The Stack</h3>
<p>
The next instruction tells the LMSM to push the value of the accumulator onto the stack, because it will be
the argument the the <code>SQUARE</code> function. When this instruction has executed, the machine will
look like this:
</p>
<img src="img/call2.png">
<p>
The stack pointer has been decremented from <code>200</code> to <code>199</code>, and the accumulator value
<code>3</code> has been stored onto the "top" of the value stack. Recall that the value stack "grows"
downward, which is a common situation with computers.
</p>
<h3>Step 3: Load The Address Of The Function</h3>
<p>
The next instruction tells the LMSM to load the memory address of the function that is going to be called
into the accumulator. The function we are going to call is located at memory location <code>8</code>.
</p>
<img src="img/call3.png">
<p>
When the instruction is complete the value <code>8</code> sits in the accumulator
</p>
<h3>Step 4: Push The Function Address Onto The Stack</h3>
<p>
In the final setup instruction before actually jumping to the <code>SQUARE</code> function code, the value
<code>8</code> is pushed onto the stack.
</p>
<img src="img/call4.png">
<p>
Now we are ready for the magic of the Jump & Link Instruction
</p>
<h3>Step 5: The Magic Jump & Link Instruction</h3>
<p>
We now get to the most magical part of the function call mechanic, the Jump & Link instruction. This instruction
does quite a bit:
</p>
<ul>
<li>It consumes the top of the stack</li>
<li>It sets the program counter to the value that was consumed from the top of the stack</li>
<li>It pushes the address of the <em>next instruction</em> onto the return address stack</li>
</ul>
<img src="img/call5.png">
<p>
You can see that the value stack pointer has been incremented, effectively popping off the top value. The
return address pointer has also been incremented, but that stack is different in that it grows <em>up</em>,
rather than down. The return address of <code>5</code> has been placed on the return address stack because,
when the <code>SQUARE</code> function returns, we wish to jump back to that address.
</p>
<p>
This is really the crux of the whole function call and is very important to understand. Other computer systems
have different mechanisms for storing return addresses (usually there is only one stack) but the core concept
is the same: jump to some location that contains a function definition and simultaneously save address of the
next instruction to return to when that function is complete.
</p>
<p>
This is how we impose the (completely immaterial) idea of "functions" on top of dumb memory slots. This
abstraction is what allows us to build incredibly complicated software on top of these machines. Some trick!
</p>
<h3>Step 6: Duplicating The Argument</h3>
<p>
At this point, the function <code>SQUARE</code> is executing, and the first thing it is going to do is duplicate
the top of the value stack. Recall that the argument to the <code>SQUARE</code> function has been placed on
the stack before it was called.
</p>
<img src="img/call6.png">
<p>
The machine now has two values on the value stack, which sets it up to do a stack multiplication on the next step.
Note that the stack pointer has been decremented and the top of the value stack is now at memory location <code>198</code>.
</p>
<h3>Step 7: Multiplying The Two Values</h3>
<p>
It is finally time to do the actual work of the <code>SQUARE</code> function, were we multiply the top two
values together and replace them with the result.
</p>
<img src="img/call7.png">
<p>
Note that the stack pointer has been incremented and that the result value, <code>9</code> sits on the "top"
of the value stack.
</p>
<h3>Step 8: Returning To The Caller</h3>
<p>
This is the second part of the magic of a function call at the assembly level: returning to the caller. This
is simpler than the Jump & Link instruction: we can just pop the value on the top of the return address
stack into the program counter, and we are done:
</p>
<img src="img/call8.png">
<p>
Note that this is following the calling convention defined for the LMSM: the result of the <code>SQUARE</code>
function has been left on the top of the value stack.
</p>
<h3>Step 9: Popping The Return Value Off The Value Stack</h3>
<p>
We want to print the return value of the <code>SQUARE</code> function out, but we can only print from the
accumulator register, so we need to first pop the value off the stack and into the accumulator:
</p>
<img src="img/call9.png">
<h3>Step 10: Printing The Value</h3>
<p>
Finally, we print the value out, with a successful function call completed!
</p>
<img src="img/call10.png">
<p>
The next instruction is a <code>HLT</code>, which stops the machine. We will omit a diagram for this step.
</p>
<h3>A Function Call... Done!</h3>
<p>
So that is a complete walk through of a function call on the LMSM. Yes, the LMSM is a very simple and
resource constrained machine, but this demonstrates the core concepts of function calls as found on more
sophisticated machines as well.
</p>
<p>
Hopefully you have a better sense of how all this magic works now.
</p>
</main>
<footer>
</footer>
</body>
</html>