6 instruction assembly language simulator written in Javascript using only arrow functions and ternary operators

6ic.js

/*
 * @author William Santos
 *
 * Below is a 6 instruction assembly language simulator written in Javascript
 * 	using only arrow functions and ternary operators.
 * There is no point in an assembler here since the assembly program to be
 * 	executed has to be composed as a recursive linked list of instructions
 * 	- which are, of course, each constructed using explicit function calls.
 *
 * How it works:
 * A program is constructed by chaining together pairs of pairs of
 * 	(all the way down) instructions - which are functions that return
 * 	functions which are applied to main memory during execution.
 * Main memory is also represented as a chain of pairs, where each slot is
 * 	initialised to zero to begin with.
 * The state of the execution at timestep t is represented as a pair:
 * 	(program counter, main memory).
 * A program is executed by making recursive calls to the exec function -
 * 	passing a new (not modified) state pair until the base case (program
 * 	counter == length of program) is reached. At each step, the instruction
 * 	at program[program counter] is applied to the current state, which
 * 	does some work, creates a new program counter and new memory, and
 * 	returns a new state pair.
 *
 * Known limitations:
 * 1. complexity of assembly program is bounded by maximum call stack size
 * 2. very inefficient - particularly with memory
 * 3. completely incomprehensible
 *
 * Instructions implemented:
 * 1. add dst src1 src2		// add values at src1 and src 1 and store in dst
 * 2. sub dst src1 src2		// sub values at src1 and src 1 and store in dst
 * 3. mul dst src1 src2		// mul values at src1 and src 1 and store in dst
 * 4. div dst src1 src2		// div values at src1 and src 1 and store in dst
 * 5. beq k src1 src	  	// branch to k if src1 and src2 are equal
 * 6. set dst k	      		// set value at address dst to k
 */

/*
 * Core functions
 */
const eq = (x) => (y) => x == y;
const lt = (x) => (y) => x < y;
const add = (x) => (y) => x + y;
const sub = (x) => (y) => x - y;
const mul = (x) => (y) => x * y;
const div = (x) => (y) => x / y;
const get = (index) => (list) => eq (index) (0) ? head (list) : get (sub (index) (1)) (tail (list));
const len = (list) => eq (list) (null) ? 0 : add (len (tail (list))) (1);
const head = (list) => list.first;
const tail = (list) => list.second;
const pair = (first) => (second) => ({first: first, second: second});
const repeat = (n) => (count) => eq (count) (0) ? null : pair (n) (repeat (n) (sub (count) (1)));
const splice = (start) => (from) => (to) => (list) => lt (start) (from) ? splice (add (start) (1)) (from) (to) (tail (list)) : eq (from) (to) ? null : pair (head (list)) (splice (start) (add (from) (1)) (to) (list));
const concat = (list1) => (list2) => eq (list1) (null) ? list2 : pair (head (list1)) (concat (tail (list1)) (list2));
const stringify = (list) => eq (list) (null) ? '|' : `| ${head (list)} ${stringify (tail (list))}`;

/*
 * Simulator functions
 *
 * Assembly instructions are prefixed with capital I; Imath is higher-order and
 * 	is used to construct the 4 math functions - ignore it.
 *
 * 1. Ibeq (k) (src1) (src1)
 * 2. Iset (dst) (k)
 * 3. Iadd (dst) (src1) (src2)
 * 4. Isub (dst) (src1) (src2)
 * 5. Imul (dst) (src1) (src2)
 * 6. Idiv (dst) (src1) (src2)
 */
const Imath = (dst) => (src1) => (src2) => (op) => (state) => pair (add (head (state)) (1)) (concat (splice (0) (0) (dst) (tail (state))) (pair ((op (get (src1) (tail (state))) (get (src2) (tail (state))))) (splice (0) (add (dst) (1)) (len (tail (state))) (tail (state)))));
const Ibeq = (k) => (src1) => (src2) => (state) => eq (get (src1) (tail (state))) (get (src2) (tail (state))) ? pair (k) (tail (state)) : pair (add (head (state)) (1)) (tail (state));
const Iset = (dst) => (k) => (state) => pair (add (head (state)) (1)) (concat (splice (0) (0) (dst) (tail (state))) (pair (k) (splice (0) (add (dst) (1)) (len (tail (state))) (tail (state)))));
const Iadd = (dst) => (src1) => (src2) => Imath (dst) (src1) (src2) (add);
const Isub = (dst) => (src1) => (src2) => Imath (dst) (src1) (src2) (sub);
const Imul = (dst) => (src1) => (src2) => Imath (dst) (src1) (src2) (mul);
const Idiv = (dst) => (src1) => (src2) => Imath (dst) (src1) (src2) (div);
const exec = (debug) => (prog) => (state) => {
	// not pure, but allows the state of the program to be inspected at
	// each step - which is quite cool
	if (debug) {
		let pc = head (state);
		let mem = tail (state);

		console.log(`program counter: ${pc}`);
		console.log(`memory: ${stringify (mem)}`);
	}

	return eq (head (state)) (len (prog)) ? state : exec (debug) (prog) ((get (head (state)) (prog)) (state));
};

/*
 * Demonstration (Euclid’s Greatest Common Divisor algorithm)
 *
 * Note: to run this you must use node.js with flag --stack-size=10000
 * 	else you will hit max call stack size. Or just make a and b smaller
 * 	numbers: node --stack-size=10000 6ic.js
 */
const debug = true;		        // print each state of execution
const mem = repeat (0) (10);		// memory has 10 slots - all set to zero
const prog =
	pair (Iset (0) (2091)) (  	// a=2091
	pair (Iset (1) (2214)) (    	// b=2214
	pair (Iset (2) (0)) (	    	// counter
	pair (Iset (3) (1)) (	       	// one (constant)
	pair (Ibeq (15) (0) (1)) (	// end loop if a and b are equal
	pair (Ibeq (9) (2) (1)) (	// goto 9 if counter is equal to b
	pair (Ibeq (12) (2) (0)) (	// else goto 12 if counter is equal to a
	pair (Iadd (2) (2) (3)) (	// increment counter using one constant
	pair (Ibeq (5) (3) (3)) (	// goto top of loop
	pair (Isub (0) (0) (1)) (	// subtract b from a, store in a
	pair (Iset (2) (0)) (		// reset counter
	pair (Ibeq (4) (3) (3)) (	// goto top of loop
	pair (Isub (1) (1) (0)) (	// subtract a from b, store in b
	pair (Iset (2) (0)) (		// reset counter 
	pair (Ibeq (4) (3) (3)) (	// goto top of loop
	pair (Iset (4) (1)) (		// finished
	))))))))))))))));

console.log('--- STARTED --');
console.log(`program has ${len (prog)} instructions`);

const finalState = exec (debug) (prog) (pair (0) (mem));
const finalPC = head (finalState);
const finalMem = tail (finalState);

console.log('--- ENDED ---');

console.log(`final program counter: ${finalPC}`);
console.log(`final memory: ${stringify (finalMem)}`);