Skip to content

Instantly share code, notes, and snippets.

@talesm
Last active November 17, 2021 16:50
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save talesm/07bf9ca221c18a901d8f6a0d0d67d4c6 to your computer and use it in GitHub Desktop.
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/)
//#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
}
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
<!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