In education teachers strive to demystify tough concepts by coming up with succinct and minimalistic examples and case studies. Frequently, despite investing great effort, the underlying mechanisms remain surrounded by mystic clouds just because the substrate over which things are exposed is at an overly high abstraction level. This is the case with recursion when illustrated via mainstream programming languages. In this blog, I would like to share a different approach of explaining processes under the hood using a low conceptual programming layer, namely machine language. It is remarkable how students easily comprehend recursion at this level without being dragged into thinking what is really going on in the background in programs written in Java, C#, Python, or any other modern programming language.
Problem Description
For teachers the booksite accompanying the book Computer Science: An Interdisciplinary Approach by Robert Sedgewick and Kevin Wayne is an excellent source of educational materials. I will provide here a solution to exercise that is not published in this book nor on the book site, at the time of writing this document. The main task is to implement a TOY machine language program that punches the 1-based ruler function on output.
Setup
Here are the steps to setup an environment for this case study (I assume that you have Java installed on your computer, otherwise jump here):
- Open a terminal window.
- Create a new folder on your machine and navigate into it.
- Download the Visual X-TOY jar application that implements a nice GUI based IDE with the simulator (there is also a stripped-down simulator TOY.java for working at the command line) and save it inside this folder.
Why TOY?
TOY is an imaginary Turing-complete machine created at Princeton, US. According to the Church-Turing thesis TOY's computational power is equivalent to any modern computer. It has 16 instructions, 256 16-bit words main memory, 16 registers (all 16-bit wide) and a program counter. The principal reason of its usage is simplicity; you can quickly learn the basics without being distracted with unnecessary details. This would be the case had I chosen any existing CPU as a starting point.
The TOY simulator is also a super straightforward piece of software. It accepts a TOY program and executes it instruction by instruction. The input/output system is based on reading/writing to a dedicated memory location at address FF (all values are given in hexadecimal format). The reference card for machine instructions is available from the IDE when edit mode is active.
The following screenshot shows all the main elements of the IDE. There are three supported modes: edit, debug and simulation (resembles the human-machine interface of the PDP-8 computer). Edit mode is used for editing a source code whilst debug to run it with full inspection of registers and memory. A nice capability of the tool is the step-by-step execution where you can monitor what is going on inside the machine. It is amazing that at this level you have a full picture of machine's state.
The above figure reflects the debug mode with a sample run using parameter n=5. You need to enter the value when asked, press Add and once finished press Run. You can see the result of execution in the right panel. The speed of execution is configurable.
The simulation is another way to interact with a machine if you want to get a feeling how was it during 1970s. There are two rows of switches: address and data. To enter something into memory you would type in the address and data via switches using a binary system and press the Load button. The Look button is to watch what is inside a particular memory location based upon address. The lights would turn on where there are ones in binary representation. Finally, you would run the code by entering the start address and press the Run button (or Step if you want to only execute the current instruction).
The Magic behind Recursion
Recursion is a powerful problem-solving approach. The whole functional programming paradigm is built upon an ability to compose and call recursive functions. People are seduced by seeing how recursion does the job and apply wishful thinking while coding a solution. As functional programming became blended into most mainstream languages it is imperative for software developers to understand the underlying mechanics of recursion. Look at the following Java program implementing the recursive ruler function. At first glance it is intuitive but on the other hand seems like hiding a mystery about what is happening in the background for this elegancy to work.
public class Ruler {
public static void ruler(int n) {
if (n == 1)
System.out.println(1);
else {
ruler(n - 1);
System.out.println(n);
ruler(n - 1);
}
}
public static void main(String[] args) {
Ruler.ruler(Integer.parseInt(args[0]));
}
}
Let us change perspective and illuminate the whole process from the very bottom. Below is the source code of ruler.toy. Each line begins with a hexadecimal memory address, followed by a colon and a 16-bit word (usually machine code) as well as disassembled view of instruction. Again, what is an instruction and data depend on the context and is only known during run-time. The rest of the line is a comment. The program by default starts at address 10.
program Ruler Function
// Test client for the ruler function.
10: 8AFF read R[A] n = read from stdin
11: FF20 R[F] <- PC; goto 20
12: 0000 halt;
function ruler
// Input: R[A] = n
// Return address: R[F]
// Output: prints the relative lengths of the
// subdivisions on a ruler.
// Temporary variables: R[1], R[2], R[3], R[B].
20: 7101 R[1] <- 0001
21: 420A R[2] <- R[A]
22: 7AA0 R[A] <- 00A0 R[A] <- top of stack
// Entry point into an inner function.
// R[2] = current level (depth)
23: 4B0F R[B] <- R[F]
24: FFA0 R[F] <- PC; goto A0 push return address
25: 4B02 R[B] <- R[2]
26: FFA0 R[F] <- PC; goto A0 push current level
27: 2321 R[3] <- R[2] - R[1]
28: C32E if (R[3] == 0) goto 2E test for base case
29: 2221 R[2] <- R[2] - R[1]
2A: FF23 R[F] <- PC; goto 23 recursive call
2B: 1321 R[3] <- R[2] + R[1] R[3] <- level (R[2] + 1)
2C: 93FF write R[3] print level
2D: C027 goto 27 tail recursion
// Base case when level is 1.
2E: 92FF write R[2] print 1
2F: FFA4 R[F] <- PC; goto A4 pop current level
30: 420B R[2] <- R[B]
31: FFA4 R[F] <- PC; goto A4 pop return address
32: 4F0B R[F] <- R[B]
33: EF00 goto R[F] return
function Push
// Input: R[A] = stack pointer, R[B] = value to push
// Return address: R[F]
// Output: None
// Temporary variables: R[1]
A0: 7101 R[1] <- 0001
A1: 2AA1 R[A] <- R[A] - R[1] decrement stack pointer
A2: BB0A M[R[A]] <- R[B] push value
A3: EF00 goto R[F] return
function Pop
// Input: R[A] = stack pointer
// Return address: R[F]
// Output: R[B] = popped value
// Temporary variables: R[1]
A4: 7101 R[1] <- 0001
A5: AB0A R[B] <- M[R[A]] R[B] <- value at top
A6: 1AA1 R[A] <- R[A] + R[1] increment stack pointer
A7: EF00 goto R[F] return
How the Code Executes?
There are couple of salient points demonstrated by ruler.toy:
- how inner functions (functions inside functions) work
- mechanics of a regular recursive call
- tail recursion, a.k.a. tail-call optimization technique
The essential part (inner function) is comprised of only 17 machine language instructions (from address 23 to 33). There are two pairs of auxiliary functions that implement a pushdown stack. Each regular recursive call pushes the current return address (kept in register F) and level (kept in register 2) onto stack. When a base case is reached these are popped from stack and execution continues after the last recursive call. The only peculiarity is related to passing arguments to an inner function. Notice that R[2] is decremented before the recursive call and this decremented value is saved on stack. Hence, after returning from a recursive call its value is preserved, and tail recursion can just use it directly.
Observe the difference between a regular recursive call and tail recursion. The latter is an unconditional jump into the beginning of a function's body skipping the part saving R[F] and R[2] on stack. Step through the execution flow in debug mode and trace what is stored in a pushdown stack whilst recursive calls are happening. You will realize that all magic regarding recursion revolves around this stack.
Conclusion
This blog sheds light onto a powerful educational approach of demonstrating high level concepts using a machine language program. You've witnessed the easy of implementing a recursive ruler function in TOY and being able to look at things stripped away from any accidental complexity. Watching actions at bare "metal" level enables you to focus attention onto quintessential mechanisms, so you will better appreciate features provided by contemporary programming languages. It is much easier to use something that you truly understand.
Java currently doesn't support tail-call optimization, but it was a no-brainer to support it in TOY. This is another reason why exposing yourself to machine language programming is beneficial. Core properties of algorithms and data structures coupled with programming paradigms can be fully explored at this level. The reason is that you are not constrained in any way by higher level protocols. You are free to compose instructions and do whatever a machine is capable of.
You may want to take a look at another powerful concept in computing called bootstrapping. This GitHub repository illustrates how this can be realized using TOY as a starting point.
Comments
Post a Comment