Last active
November 17, 2021 16:50
-
-
Save talesm/07bf9ca221c18a901d8f6a0d0d67d4c6 to your computer and use it in GitHub Desktop.
A forth-like implementation, with stacks and basic operations (see article https://justadevlog.neocities.org/2021/11/14/playing-with-forth/)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//#region dataStack | |
function createStack() { | |
/** @type {number[]} */ | |
const stack = [] | |
return { | |
push: val => stack.push(val | 0), // |0 ensures int32 | |
pop: () => stack.pop(), | |
size: () => stack.length, | |
top: () => stack[stack.length - 1], | |
dump: () => stack.map(v => v), | |
clear: () => stack.splice(0), | |
} | |
} | |
const dataStack = createStack() | |
// These save some keystrokes, as these functions are frequently used | |
const { push, pop, top } = dataStack | |
//#endregion dataStack | |
/** | |
* @typedef {object} Definition | |
* @property {string} name | |
* @property {Function} action | |
* @property {number} [code] | |
* @property {boolean} [immediate] | |
*/ | |
//#region dictionary | |
function createDictionary() { | |
/** @type {Object.<string, Definition>} */ | |
const dictionary = {} | |
return { | |
define: (name, action) => dictionary[name] = { name, action }, | |
find: name => dictionary[name], | |
dump: () => Object.values(dictionary), | |
} | |
} | |
const dictionary = createDictionary() | |
dictionary.define('+', () => push(pop() + pop())) | |
dictionary.define('-', () => push(-pop() + pop())) | |
dictionary.define('DROP', pop) | |
dictionary.define('DUP', () => push(top())) | |
dictionary.define('DEPTH', () => push(dataStack.size())) | |
dictionary.define('SWAP', () => { | |
const a = pop() | |
const b = pop() | |
push(a) | |
push(b) | |
}) | |
//#endregion dictionary | |
//#region rudeEval | |
const evaluateWord = word => { | |
const a = dictionary.find(word)?.action; | |
if (a) { a() } else { push(word) } | |
} | |
const evaluateRudely = str => str.split(/\s+/).forEach(evaluateWord) | |
//#endregion rudeEval | |
//#region codeSpace | |
// All code is stored here | |
const codeSpace = [push] | |
// The address of LIT, as it is not visible on dictionary | |
const xtLIT = codeSpace.length - 1 | |
// Assign the index for already defined words | |
for (const d of dictionary.dump()) { | |
d.code = codeSpace.length | |
codeSpace.push(d.action) | |
} | |
function addressOf(word) { | |
const xt = dictionary.find(word)?.code ?? null | |
if (xt === null) | |
throw new Error(`No word defined with name ${word}`) | |
return xt | |
} | |
// Fills both codeSpace and dictionary | |
function define(name, action) { | |
const code = codeSpace.push(action) - 1 | |
const d = dictionary.define(name, action) | |
d.code = code | |
return d | |
} | |
//#endregion codeSpace | |
//#region executor | |
// Another stack, but mainly used for return address bookkeeping | |
let returnStack = createStack() | |
// Execute sequential steps within a thread | |
// Return the next pc, with the next thread xt on returnStack | |
function executorStep(thread, pc) { | |
const currentAddress = returnStack.pop() | |
while (pc < thread.length) { | |
const address = thread[pc++] | |
const action = codeSpace[address] | |
if (action.thread) { | |
returnStack.push(currentAddress) | |
returnStack.push(pc) | |
returnStack.push(address) | |
return 0 | |
} | |
action.apply(null, thread.slice(pc, pc += action.length)) | |
} | |
return returnStack.pop() | |
} | |
// Execute the thread recursively | |
function executor(root) { | |
const savedStack = returnStack | |
returnStack = createStack() | |
returnStack.push(-1) | |
let pc = 0 | |
while (returnStack.size()) { | |
const address = returnStack.top() | |
const thread = address === -1 ? root : codeSpace[address].thread | |
pc = executorStep(thread, pc) | |
} | |
returnStack = savedStack | |
} | |
//#endregion executor | |
//#region Compiler | |
// Mounts a compilation unit for us | |
function Compiler() { | |
this.buffer = [] | |
} | |
Compiler.prototype.code = function (xt, ...params) { | |
this.buffer.push(xt, ...params) | |
return this | |
} | |
Compiler.prototype.word = function (word) { | |
return this.code(addressOf(word)); | |
} | |
Compiler.prototype.lit = function (num) { | |
return this.code(xtLIT, +num) | |
} | |
Compiler.prototype.build = function () { | |
const thread = this.buffer | |
const runner = () => executor(thread) | |
runner.thread = thread | |
return runner | |
} | |
define('NEGATE', new Compiler().lit(0).word('SWAP').word('-').build()) | |
define('INVERT', new Compiler().word('NEGATE').lit(1).word('-') | |
.build()) | |
//#endregion Compiler | |
//#region inputBuffer | |
// InputBuffer | |
function InputBuffer(text) { | |
this.buffer = text | |
this.offset = 0 | |
} | |
let inputBuffer = new InputBuffer('') | |
InputBuffer.prototype.match = function (delim) { | |
if (this.offset >= this.buffer.length) { | |
return false | |
} | |
const ch = this.buffer[this.offset] | |
if (ch === delim) return true | |
return delim === ' ' && !!ch.match(/[\x00-\x20\x7f]/) | |
} | |
InputBuffer.prototype.skip = function (delim) { | |
const len = this.buffer.length | |
const off = this.offset | |
while (this.offset < len) { | |
if (!this.match(delim)) { | |
break | |
} | |
this.offset++ | |
} | |
return this.offset - off | |
} | |
InputBuffer.prototype.parse = function (delim) { | |
const len = this.buffer.length | |
const off = this.offset | |
while (this.offset < len) { | |
if (this.match(delim)) { | |
const text = this.buffer.slice(off, this.offset) | |
this.offset++ // Discard the delimiter | |
return text | |
} | |
this.offset++ | |
} | |
return this.buffer.slice(off) | |
} | |
InputBuffer.prototype.parseName = function () { | |
this.skip(' ') | |
return this.parse(' ') | |
} | |
//#endregion inputBuffer | |
//#region comments | |
define('(', () => inputBuffer.parse(')')).immediate = true | |
define('\\', () => inputBuffer.parse('\n')).immediate = true | |
//#endregion comments | |
//#region run | |
// Stores the current word being compiled | |
let compiler = new Compiler() | |
// Flag to know if we are compiling or interpreting right now | |
let compiling = false | |
// Do just one step with the given word, respecting the compiling flag | |
function doStep(word) { | |
const d = dictionary.find(word) | |
if (d) { | |
if (!compiling || d.immediate) { | |
return d.action() | |
} | |
compiler.code(d.code) | |
} else if (compiling) { | |
compiler.lit(word) | |
} else { | |
push(word) | |
} | |
} | |
// Run though our current inputBuffer until the end | |
function run() { | |
let word | |
while ((word = inputBuffer.parseName())) { | |
doStep(word) | |
} | |
} | |
// Evaluate code! | |
function evaluate(text) { | |
const savedBuffer = inputBuffer | |
inputBuffer = new InputBuffer(text) | |
run() | |
inputBuffer = savedBuffer | |
} | |
// Compile fragment into the existing compiler | |
Compiler.prototype.compile = function (text) { | |
const savedCompiler = compiler | |
const savedCompiling = compiling | |
compiler = this | |
compiling = true | |
evaluate(text) | |
compiler = savedCompiler | |
compiling = savedCompiling | |
return this | |
} | |
// Compile! | |
function compile(text) { | |
return new Compiler().compile(text).build() | |
} | |
//#endregion run | |
//#region returnStack | |
// These allow using return stack as a temporary stack | |
define('>R', () => returnStack.push(pop())) | |
define('R>', () => push(returnStack.pop())) | |
define('R@', () => push(returnStack.top())) | |
define('OVER', compile('OVER >R DUP R> SWAP')) | |
define('ROT', compile('OVER >R DUP R> SWAP')) | |
//#endregion returnStack | |
//#region output | |
// Pops number top of the stack and show its value plus space. | |
define('.', () => output(pop().toString() + ' ')) | |
// Pops number top of the stack and show it as a UTF16 code point. | |
define('EMIT', () => output(String.fromCharCode(pop()))) | |
// Shows the entire stack. No popping is involved | |
define('.S', () => output(dataStack.dump().join(', ') + '\n')) | |
// Prints space | |
define('CR', compile('10 EMIT')) | |
// Prints new line | |
define('SPACE', compile('32 EMIT')) | |
// Pushes First CHAR on the stack | |
define('CHAR', () => push(inputBuffer.parseName().charCodeAt(0))) | |
//#endregion output | |
if (typeof module === 'object') { | |
let outBuffer = '' | |
function output(str) { | |
const newLineIndex = str.lastIndexOf('\n') | |
if (newLineIndex === -1) { | |
outBuffer += str | |
} else { | |
console.log(outBuffer + str.slice(0, newLineIndex)) | |
outBuffer = str.slice(newLineIndex + 1) | |
} | |
} | |
module.exports.evaluate = evaluate | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const readline = require('readline') | |
const { evaluate } = require("./forth") | |
//#region repl | |
const rl = readline.createInterface({ | |
input: process.stdin, | |
output: process.stdout, | |
prompt: '% ', | |
}) | |
rl.prompt() | |
rl.on('line', line => { | |
if (line.trim() === '.quit') { | |
console.log('Bye!') | |
rl.close() | |
return | |
} | |
evaluate(line) | |
evaluate('CHAR O EMIT CHAR k EMIT CR') | |
rl.prompt() | |
}).on('close', () => { | |
process.exit(0) | |
}) | |
//#endregion repl |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<head> | |
<meta charset="UTF8" /> | |
<title>Forth Demo1</title> | |
<style> | |
.console { | |
background-color: #eee; | |
border: 1px solid #ccc; | |
font-family: monospace; | |
} | |
.history .line { | |
white-space: pre-wrap; | |
} | |
.input-area { | |
border-top: 3px double #ccc; | |
display: flex; | |
} | |
.prompt { | |
white-space: pre-wrap; | |
} | |
.input-line { | |
width: 100%; | |
padding: 0; | |
border: 0; | |
background-color: transparent; | |
font-family: monospace; | |
} | |
</style> | |
</head> | |
<body> | |
<h1>Forth interactive REPL</h1> | |
<div id="console" class="console"> | |
<div id="history" class="history"> | |
<div class="line" v-for="text of history">{{text}}</div> | |
</div> | |
<div class="input-area" @keydown.Enter="commitLine"> | |
<div class="prompt">{{prompt}}</div> | |
<input class="input-line" v-model="inputLine" /> | |
</div> | |
</div> | |
<script src="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script> | |
<script src="forth.js"></script> | |
<script> | |
const app = new Vue({ | |
el: '#console', | |
data: { | |
inputLine: '', | |
history: [], | |
prompt: '>>> ', | |
inputHandler, | |
}, | |
methods: { | |
commitLine() { | |
const input = this.inputLine | |
this.inputLine = '' | |
this.outputLine(input) | |
// here we call some handler method | |
this.inputHandler(input) | |
}, | |
clear() { | |
this.history = [] | |
}, | |
output(text) { | |
text = (text || '').toString() | |
const lastNewLine = text.lastIndexOf('\n') | |
if (lastNewLine >= 0) { | |
this.outputLine(this.prompt + text.slice(0, lastNewLine)) | |
this.prompt = text.slice(lastNewLine + 1) | |
} else { | |
this.prompt += text | |
} | |
}, | |
outputLine(text) { | |
text = this.prompt + (text || '') | |
this.history.push(text) | |
this.prompt = '' | |
} | |
}, | |
}) | |
function output(text) { | |
app.output(text) | |
} | |
function inputHandler(text) { | |
evaluate(text) | |
output('Ok\n>>> ') | |
} | |
</script> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment