Input
Output
TOY4
Hz
ADDR / PC
(0)10
| 0 | 0 | 0 | 0 |
#
| 0 | 0 | 0 | 0 |
#
DATA | INSTRUCTION (0)10
| 0 | 0 | 0 | 0 |
#
| 0 | 0 | 0 | 0 |
#
| 0 | 0 | 0 | 0 |
#
| 0 | 0 | 0 | 0 |
#
REGISTER
| ADDR | #0 | #1 | #2 | #3 | #4 | #5 | #6 | #7 | #8 | #9 | #a | #b | #c | #d | #e | #f |
|---|
TinkerTOY ← Tinkern + TOY + JavaScript
|
TOY Instruction Format
TOY Operations and Associated Tinker Methods
Auxiliary Tinker Methods
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
/** Program IO (Input output).
** by John P. Spurgeon
**/
"use strict"; // Opt into strict mode.
const FA = "5b"; // First Address
const BA = "5e"; // Branch-to Address
const toyProg = [
"80ff", // 5c (FA): R[0] <- M[ff]
"d0" + BA, // 5d: if R[0] > 0 PC <- BA
"0000", // 5e: halt
"90ff", // 5f (BA): M[ff] <- R[0]
"d0" + FA, // 60: PC <- FA
];
storeProgram(FA, toyProg.length, toyProg);
Tinker16.PC(FA);
function storeProgram(firstAddr, n, prog) {
const base = 16;
let currAddr = parseInt(firstAddr, base);
for (let i = 0; i < n; i++) {
const cmd = parseInt(prog[i], base);
Tinker10.M(currAddr, cmd);
currAddr++;
}
}
/** Program S (Store).
** by John P. Spurgeon
**/
"use strict"; // Opt into strict mode.
const FA = "50"; // First Addr
const BA = "55"; // Branch Addr
const HI = "5a"; // addr of Halt Instruction
const toyProg = [
/* A TOY program that reads from standard
* input an address at which to start
* storing values in memory followed by
* a count of the number of values in an
* array of values followed by the values.
* The values are stored in memory in
* sequential order beginning at the
* specified address of the first value.
*
* R[0]: 0 (zero, a constant)
* R[1]: 1 (step size, a constant)
* R[a]: addr to store next value at
* R[c]: count of values remaining
* R[f]: value most recently read in
*/
"7000", // 50: R[0] <- 0
"7101", // 51: R[1] <- 1 (step size)
"8aff", // 52: R[a] <- M[ff] (addr)
"8cff", // 53: R[c] <- M[ff] (count)
"cc" + HI, // 54: Goto HI if R[c] is 0
"8fff", // 55 (BA): R[f] <- M[ff] (value)
"bf0a", // 56: M[R[a]] <- R[f] (value)
"1aa1", // 57: R[a] <- R[a] + R[1]
"2cc1", // 58: R[c] <- R[c] - R[1]
"dc" + BA, // 59: Goto BA if R[c] > 0
"0000" // 5a (HI): halt
];
storeData(FA, toyProg.length, toyProg);
Tinker16.PC(FA);
function storeData(firstAddr, n, values) {
const base = 16;
let currAddr = parseInt(firstAddr, base);
for (let i = 0; i < n; i++) {
const val = parseInt(values[i], base);
Tinker10.M(currAddr, val);
currAddr++;
}
}
/** Program B (Boot).
** by John P. Spurgeon
**/
"use strict"; // Opt into strict mode.
const FA = "00"; // First Addr
const BA = "06"; // Branch Addr
const TC = "0b"; // Transfer Control addr
const toyProg = [
/* A TOY program that reads from standard
* input an address at which to start
* storing a program in memory followed by
* a count of the number of instructions
* in the program followed by the
* instructions. This program (Program B)
* stores the other program (the program
* being loaded) in memory in sequential
* order beginning at the specified
* starting address and then transfers
* control to the other program by setting
* the PC to the starting address of the
* program just loaded.
*
* R[0]: 0 (zero, a constant)
* R[1]: 1 (step size, a constant)
* R[a]: addr of next instruction
* R[b]: boot addr (addr of first value)
* R[c]: count of values remaining
* R[f]: value most recently read in
*/
"7000", // 0: R[0] <- 0
"7101", // 1: R[1] <- 1 (step size)
"8aff", // 2: R[a] <- M[ff] (addr)
"1ba0", // 3: R[b] <- R[a] + R[0]
"8cff", // 4: R[c] <- M[ff] (count)
"cc" + TC, // 5: Goto TC if R[c] is 0
"8fff", // 6 (BA): R[f] <- M[ff] (value)
"bf0a", // 7: M[R[a]] <- R[f] (value)
"1aa1", // 8: R[a] <- R[a] + R[1]
"2cc1", // 9: R[c] <- R[c] - R[1]
"dc" + BA, // a: Goto BA if R[c] > 0
"eb00" // b (TC): PC <- R[b]
];
storeProgram(FA, toyProg.length, toyProg);
Tinker16.PC(FA);
function storeProgram(firstAddr, n, prog) {
const base = 16;
let currAddr = parseInt(firstAddr, base);
for (let i = 0; i < n; i++) {
const cmd = parseInt(prog[i], base);
Tinker10.M(currAddr, cmd);
currAddr++;
}
}
/** Store Program C (Compare).
** by John P. Spurgeon
**/
// The following IIFE (immediately invoked
// function expression) stores a TOY program
// in memory. It takes a starting address
// as input and returns the address that
// immediately follows the address of the
// last instruction stored.
(function storeProgramC(A0) {
console.log("0. Input: #" + A0);
// STEP 1. Opt into strict mode.
//
// Evaluating the string "use strict" may
// affect how a particular JavaScript
// interpreter treats the JavaScript code
// that follows. Many JavaScript programmers
// consider evaluating "use strict" at the
// beginning of a program to be a best
// practice, regardless of the algorithm
// being implemented. On the one hand, we
// don't need to be too concerned about how
// evaluating "use strict" affects this
// program, since it has no bearing on the
// conceptual algorithm. On the other
// hand, it can affect the rules we are
// obliged to follow when implementing any
// algorithm in JavaScript. RTFM.
"use strict";
console.log("1. Opted into strict mode.");
// STEP 2. Define address labels.
const A = {
a: stepHex(A0, 4), // (Begin x <> y).
b: stepHex(A0, 8), // (Find MSB of XOR).
c: stepHex(A0, 12), // (Found MSB of XOR).
d: stepHex(A0, 15) // (End x <> y).
};
console.log("2. Address labels:\n" + A);
// STEP 3. Define the TOY program.
const toyProg = [
/* A TOY function that takes as inputs
* two values representing non-negative
* integers, x and y, and outputs a value
* indicating whether x = y, x > y, or
* x < y.
*
* R[#1]: #0001 (a constant)
* R[#2]: #000f (a constant)
* R[#3]: R[#d] & R[#e]
* R[#4]: R[#a] & R[#e]
* R[#a]: input: x
* R[#b]: input: y
* R[#c]: output (#ffff, #0, or #1)
* R[#d]: R[#a] ^ R[#b]
* R[#e]: a variable bit mask
* R[#f]: return-to address
*/
// INPUTS
//
// R[#a]: An unsigned integer, x.
// R[#b]: An unsigned integer, y.
// OUTPUT
//
// R[#c]: #0000 if x = y; or
// #0001 if x > y; or
// #ffff if x < y.
// LABEL A0 (Start address).
// INSTRUCTION 1 (A0 + 0):
// We presume x = y. If we discover that
// that is false, then we'll update R[#c].
// Recall that a zero in R[#c] indicates
// that x = y.
"7c00", // R[#c] <- #00
// INSTRUCTION 2 (A0 + 1):
// We determine whether any of the bits
// in x (R[#a]) differ from the bits in
// y (R[#b]) by XORing x and y. If x = y,
// then the XOR value will be 0.
// Otherwise, the XOR value will be > 0.
"4dab", // R[#d] <- R[#a] ^ R[#b]
// INSTRUCTION 3 (A0 + 2):
// If XOR value > 0, then x <> y; in that
// case, go to A.a and determine which is
// greater, x or y.
"dd" + A.a, // if R[#d] > 0 PC <- A.a
// INSTRUCTION 4 (A0 + 3):
// If XOR value = 0, then x = y as
// initially presumed. The algorithm
// terminates by transferring control
// to the instruction located at the
// address loaded in R[#f].
"ef00", // PC <- R[#f] (return address)
// LABEL A.a (Begin x <> y).
// INSTRUCTION 5 (A0 + 4):
// We need the constant value 1 in a
// register. We'll use the value in
// subsequent instructions.
"7101", // R[#1] <- #01
// INSTRUCTION 6 (A0 + 5):
// Now we presume x < y. Recall that the
// value 0 - 1 (i.e. #ffff) indicates
// that x < y. Note that the value of
// R[#c] is #0000 (from INSTRUCTION 1),
// and the value of R[#1] is #0001
// (from INSTRUCTION 5).
"2cc1", // R[#c] <- R[#c] - R[#1]
// INSTRUCTION 7 (A0 + 6):
// We put the decimal value 15 (#0f) in a
// register so we can use it to form the
// value #8000, i.e. 1000000000000000 in
// base 2. The value #8000 is the initial
// value of a bitmask that we'll use to
// find the most significant bit (MSB) of
// the XOR value of x and y. That MSB is
// important, because it is the first bit
// from the left that differs in x and y
// and will therefore tell us whether x
// or y is larger. The larger value will
// have a 1 in that position, while the
// smaller value will have a 0 there.
"720f", // R[#2] <- f (shift left amt)
// INSTRUCTION 8 (A0 + 7):
// R[#e] <- 1000000000000000 (bitmask)
"5e12", // R[#e] <- R[#1] << R[#2]
// LABEL A.b (Find MSB of XOR).
// INSTRUCTION 9 (A0 + 8):
// Apply bitmask to R[#d], which holds
// the value of x XOR y. If the result
// is greater than zero, then we will
// have found the MSB. Otherwise, we
// will keep searching.
"33de", // R[#3] <- R[#d] & R[#e]
// INSTRUCTION 10 (A0 + 9):
// If masked value > 0, then found MSB.
"d3" + A.c, // if R[#3] > 0 PC <- A.c
// INSTRUCTION 11 (A0 + 10):
// Otherwise, shift bit mask value one
// place to the right. (Recall that the
// value of R[#1] is 1.)
"6ee1", // R[#e] <- R[#e] >> R[#1]
// INSTRUCTION 12 (A0 + 11):
// Continue searching for MSB: go back
// to LABEL A.b.
"c3" + A.b, // if R[#3] = 0 PC <- A.b
// LABEL A.c (Found MSB in R[#d]).
// INSTRUCTION 13 (A0 + 12):
// Is MSB a 1 in x or y? To find out,
// we AND the bitmask in R[#e] with the
// value of x in R[#a]. If the result
// equals 0, then value of the MSB is
// 0 in x and 1 in y; otherwise, the
// MSB is 1 in x and 0 in y.
"34ae", // R[#4] <- R[#a] & R[#e]
// INSTRUCTION 14 (A0 + 13):
// If MSB of y, then x < y as presumed.
// Jump to A.d (End x <> y).
"c4" + A.d, // if R[4] = 0 PC <- A.d
// INSTRUCTION 15 (A0 + 14):
// Actually, x > y. Our revised
// presumption was wrong too, so we
// update register #f with the correct
// final answer. (It's not a presum-
// tion this time; it's a fact.)
"7c01", // R[#c] <- #01
// LABEL A.d (End x <> y).
// INSTRUCTION 16 (A0 + 15).
// The algorithm terminates. We yield
// control to the instruction at the
// address stored in register #f.
"ef00" // PC <- R[#f] (return)
];
console.log("3. TOY prog:\n" + toyProg);
// STEP 4. Note the program size.
const progSize = toyProg.length;
console.log("4. Program size: " + progSize);
// STEP 5. Store the TOY program in memory.
storeProgram(A0, progSize, toyProg);
console.log("5. Stored program.");
// STEP 6. Compute the address in memory
// following the last instruction stored.
const nextAddr = stepHex(A0, progSize);
console.log("6. Next address: #" + nextAddr);
// STEP 7. Return the value of nextAddr.
console.log("7. Output: #" + nextAddr);
return nextAddr;
/** Utility Functions **/
function storeProgram(firstAddr, n, prog) {
const base = 16;
let currAddr = parseInt(firstAddr, base);
for (let i = 0; i < n; i++) {
const cmd = parseInt(prog[i], base);
Tinker10.M(currAddr, cmd);
currAddr++;
}
}
function getLastTwoDigits(twoOrMore) {
const sliceAt = twoOrMore.length - 2;
return twoOrMore.slice(sliceAt);
}
function stepHex(addr16, stepSize) {
const addr10 = parseInt(addr16, 16);
const newAddr10 = addr10 + stepSize;
const newAddr16 = newAddr10.toString(16);
const digits16 = pad(newAddr16, 2);
return getLastTwoDigits(digits16);
}
function pad(digits, minLength) {
while (digits.length < minLength)
digits = "0" + digits;
return digits;
}
} // storeProgramC ends here.
// Pass the value of the starting address
// as an argument to the IIFE.
)("60"); // A0 <- "60"
/** Store Program M (Mystery).
** by John P. Spurgeon
**/
// The following IIFE (immediately invoked
// function expression) stores a TOY program
// in memory. It takes the starting address
// of the program and the starting address
// of a function as input and returns the
// address that immediately follows the
// address of the last instruction stored.
(function storeProgramM(P0, F0) {
console.log("0. Inputs");
console.log(" P0: #" + P0);
console.log(" F0: #" + F0);
// STEP 1. Opt into strict mode.
//
// Evaluating the string "use strict" may
// affect how a particular JavaScript
// interpreter treats the JavaScript code
// that follows. Many JavaScript programmers
// consider evaluating "use strict" at the
// beginning of a program to be a best
// practice, regardless of the algorithm
// being implemented. On the one hand, we
// don't need to be too concerned about how
// evaluating "use strict" affects this
// program, since it has no bearing on the
// conceptual algorithm. On the other
// hand, it can affect the rules we are
// obliged to follow when implementing any
// algorithm in JavaScript. RTFM.
"use strict";
console.log("1. Opted into strict mode.");
// STEP 2. Define address labels.
const A = {
a: stepHex(P0, 2), // (?).
b: stepHex(P0, 6), // (?).
c: stepHex(P0, 10) // (?).
};
console.log("2. Address labels:\n" + A);
// STEP 3. Define the TOY program.
const toyProg = [
"7101", // P0 + 0
"7a00", // P0 + 1
"8bff", // P0 + 2 (A.a)
"db" + A.b, // P0 + 3
"9aff", // P0 + 4
"0000", // P0 + 5
"ff" + F0, // P0 + 6 (A.b)
"1cc1", // P0 + 7
"dc" + A.c, // P0 + 8
"4abc", // P0 + 9
"da" + A.a // P0 + 10 (A.c)
];
console.log("3. TOY prog:\n" + toyProg);
// STEP 4. Note the program size.
const progSize = toyProg.length;
console.log("4. Program size: " + progSize);
// STEP 5. Store the TOY program in memory.
storeProgram(P0, progSize, toyProg);
console.log("5. Stored program.");
// STEP 6. Set the PC.
Tinker16.PC(P0);
console.log("6. PC <- " + P0);
// STEP 7. Compute the address in memory
// following the last instruction stored.
const nextAddr = stepHex(P0, progSize);
console.log("7. Next address: #" + nextAddr);
// STEP 8. Return the value of nextAddr.
console.log("8. Output: #" + nextAddr);
return nextAddr;
/** Utility Functions **/
function storeProgram(firstAddr, n, prog) {
const base = 16;
let currAddr = parseInt(firstAddr, base);
for (let i = 0; i < n; i++) {
const cmd = parseInt(prog[i], base);
Tinker10.M(currAddr, cmd);
currAddr++;
}
}
function getLastTwoDigits(twoOrMore) {
const sliceAt = twoOrMore.length - 2;
return twoOrMore.slice(sliceAt);
}
function stepHex(addr16, stepSize) {
const addr10 = parseInt(addr16, 16);
const newAddr10 = addr10 + stepSize;
const newAddr16 = newAddr10.toString(16);
const digits16 = pad(newAddr16, 2);
return getLastTwoDigits(digits16);
}
function pad(digits, minLength) {
while (digits.length < minLength)
digits = "0" + digits;
return digits;
}
} // storeProgramM ends here.
// Pass the value of the starting address
// as an argument to the IIFE.
)("70", "60"); // P0 <- "70", F0 <- "60"
/** Program 0 (Playful and serious).
** by John P. Spurgeon
**/
/* .:....1....:....2....:....3....:....4....
* Mathematics and computer science
* can be both playful and serious
* at the same time.
*
* - DONALD E. KNUTH, Selected Papers on
* Fun & Games (2011)
*
*
* The lowercase Greek letter λ (lambda)
* is an unofficial symbol of the field
* of programming language theory. This
* usage derives from the lambda calculus,
* a model of computation introduced by
* Alonzo Church in the 1930s ...
*
* - EN WIKIPEDIA, Programming language
* theory (accessed 11 Aug 2018)
*/
"use strict"; // 0. Opt out of sloppy mode.
// .:....1....:....2....:....3....:....4....
// 1. First, we define a string to print; it
// will be one thing or another depending on
// the value returned by Math.random. Then
// we record the length of the string (i.e.
// the number characters in the string).
const str = Math.random() > 0.5 ?
"l. Programming\n" : "m. Mathematics\n";
const n = str.length;
// .:....1....:....2....:....3....:....4....
// 2. Now we form a list of the unique
// characters in the string we selected in
// section 1 above. (Sorting the characters
// in the string helps us identify any
// characters that appear more than once in
// the string. The sort method we are using
// operates on arrays, so we use the split
// method to convert the string to an array
// of characters before calling sort.) The
// algorithm we employ to filter duplicates
// is concise, but it requires just a little
// bit of effort to understand. Clues are
// provided in the comments below. A more
// detailed explanation and/or proof of the
// correctness of the algorithm is left as
// an exercise for the reader.
const uniqueChars = []; // An array.
const sortedChars = str.split("").sort();
for (let i = 0, j = 0; i < n; i++) {
// Is the value in sortedChars at index
// i different from the value at index j?
// If so, then set the value of j equal to
// the value of i.
if (sortedChars[i] !== sortedChars[j])
j = i;
// If the values of i and j are equal,
// then add the character in sortedChars
// at index i to the end of uniqueChars;
// otherwise, do nothing, because we must
// have already added that character.
if (i === j)
uniqueChars.push(sortedChars[i]);
}
// .:....1....:....2....:....3....:....4....
// 3. We should make sure there aren't too
// many distinct characters in our string,
// in case someone changes the program
// and tries to use it to print something
// like "The quick brown fox jumped over
// the lazy dog." TOY (TOY4, that is) has
// only 16 registers, and this peculiar way
// of printing requires every unique
// character to be stored in a register
// simultaneously.
const m = uniqueChars.length;
if (m > 16) {
let e = "Too many distinct characters!";
e += "\nUse a more flexible algorithm ";
e += "or at most 16 unique characters."
throw Error(e);
}
// .:....1....:....2....:....3....:....4....
// 4. We gather information about each
// unique character in the string. For each
// character, we need to know its numeric
// code, and we need to specify the number
// of a register in which to store the code.
const charInfoSet = {}; // A map.
for (let i = 0; i < m; i++) {
const char = uniqueChars[i];
const code = char.charCodeAt();
const info = {code: code, reg: i};
const id = code.toString();
charInfoSet[id] = info;
}
// .:....1....:....2....:....3....:....4....
// 5. Now we create our ultimate data
// structure: a sequence of character
// information objects corresponding to the
// sequence of characters in the string we
// want to print.
const charInfoSequence = [];
for (let i = 0; i < n; i++) {
const id = str.charCodeAt(i).toString();
charInfoSequence[i] = charInfoSet[id];
}
// .:....1....:....2....:....3....:....4....
// 6. Now we can assemble the machine code.
// We specify the location in memory where
// we'll start loading the TOY instructions;
// we set the program counter (PC) to that
// address; we load the TOY instructions
// that will load character codes into the
// registers; then we load the instructions
// that will write out the string by storing
// each character code, one at a time, in
// TOY's last memory address.
const progStartAddr = 0;
Tinker10.PC(progStartAddr);
for (const id in charInfoSet) {
const info = charInfoSet[id];
Tinker10.LDB(info.reg, info.code);
}
for (let i = 0; i < n; i++) {
const next = charInfoSequence[i];
Tinker10.ST(next.reg, 255);
}
// .:....1....:....2....:....3....:....4....
// 7. Finally, we load the essential HALT
// instruction, which will presumably be
// used to stop the program, and we set
// the PC (the program counter) to the
// address of the first instruction of the
// program to make it easy to get the
// program started via TOY's Run button.
Tinker10.HALT();
Tinker10.PC(progStartAddr);
/** Program 1 (Salutations Thing 1).
** by John P. Spurgeon
**/
"use strict"; // Opt into strict mode.
// 1. Name the constant variables.
const thing1 = "Thing 1";
const phrase = '"Hi, ' + thing1 + '!"\n';
const n = phrase.length;
const stepReg = 0;
const addrReg = 1;
const dataReg = 2;
const stepSize = 1;
const lastMemAddr = parseInt("ff", 16);
const dataStartAddr = parseInt("20", 16);
const endOfString = 0;
// 2. Load the data (character codes).
let addr = dataStartAddr, data;
for (let i = 0; i < n; addr++, i++) {
data = phrase.charCodeAt(i);
Tinker10.M(addr, data);
}
Tinker10.M(addr, endOfString);
// 3. Note where the instructions begin,
// and move the cursor to the beginning.
const progStartAddr = addr + 1;
Tinker10.PC(progStartAddr );
// 4. Load the instructions.
Tinker10.LDB(stepReg, stepSize);
Tinker10.LDA(addrReg, dataStartAddr);
Tinker10.LDI(dataReg, addrReg);
Tinker10.BZ(dataReg, Tinker10.PC() + 4);
Tinker10.ST(dataReg, lastMemAddr);
Tinker10.ADD(addrReg, addrReg, stepReg);
Tinker10.BP(dataReg, progStartAddr + 2);
Tinker10.HALT();
// 5. Reset the cursor.
Tinker10.PC(progStartAddr );
/** Program 2 (Salutations Thing 2).
** by John P. Spurgeon
**/
"use strict"; // Opt into strict mode."use strict"; // Opt out of sloppy mode.
// 1. Name the constant variables.
const thing2 = "Thing 2";
const phrase = "'Hi, " + thing2 + "!'\n";
const n = phrase.length;
const stepReg = 0;
const addrReg = 1;
const dataReg = 2;
const stepSize = 1;
const lastMemAddr = parseInt("ff", 16);
const dataStartAddr = parseInt("38", 16);
const endOfString = 0;
// 2. Load data (character codes).
let addr = dataStartAddr, data;
for (let i = 0; i < n; addr++, i++) {
data = phrase.charCodeAt(i);
Tinker10.M(addr, data);
}
Tinker10.M(addr, endOfString);
// 3. Note the address of the first
// instruction and assign it to the PC.
const progStartAddr = addr + 1;
Tinker10.PC(progStartAddr );
// 4. Load instructions.
Tinker10.LDB(stepReg, stepSize);
Tinker10.LDA(addrReg, dataStartAddr);
Tinker10.LDI(dataReg, addrReg);
Tinker10.ST(dataReg, lastMemAddr);
Tinker10.ADD(addrReg, addrReg, stepReg);
Tinker10.LDI(dataReg, addrReg);
Tinker10.BP(dataReg, progStartAddr + 3);
Tinker10.HALT();
// 5. Reset the program counter (PC).
Tinker10.PC(progStartAddr );
lly Rabbi
i \ V / T
S /. .\ !
==\ T /==
/ R \
a I e
for X kids.