DEV Community: Josh Holbrook

Matanuska ADR 004 - Expect Tests

Josh Holbrook — Thu, 25 Dec 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

Effective interpreters need a lot of tests. One kind of test is an "expect" test - run a script, potentially enter input programmatically, and assert the output.

My test framework, node-tap, has a matchSnapshot functionality which can assert the output. Programmatic input is more complicated, and may require another module.

A type of test recommended by Writing Interactive Compilers & Interpreters includes running absurdly large programs and asserting they cause meaningful errors instead of segmentation faults or similar.

Decision

I will write a series of test scripts in the test directory. A tap test will run each script and assert the output with matchSnapshot.

These scripts will initially not take input, since solving for "expect" use cases is more complicated. This may be tackled in the future.

There will also be (a) script(s) which generate absurdly large programs, which test the limits of the interpreter.

ADR 019 - Identifier Contant Optimization

Josh Holbrook — Mon, 11 Aug 2025 00:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

While working on looping, I discovered an interesting behavior in compilation of global variable access. Consider the following program:

10 rem A simple for loop
20 for i% = 1 to 10
30   print i%
40 endfor

This compiles to the following disassembled bytecode:

20  1   CONSTANT       i%
20  3   CONSTANT       1
20  5   DEFINE_GLOBAL  i%
20  7   CONSTANT       i%
20  9   GET_GLOBAL     i%
20  11  CONSTANT       10
20  13  LE
20  14  JUMP_IF_FALSE  14 -> 44
20  17  POP
20  18  JUMP           18 -> 36
20  21  CONSTANT       i%
20  23  CONSTANT       i%
20  25  GET_GLOBAL     i%
20  27  CONSTANT       1
20  29  ADD
20  30  SET_GLOBAL     i%
20  32  POP
20  33  LOOP           33 -> 7
30  36  CONSTANT       i%
30  38  GET_GLOBAL     i%
30  40  PRINT
40  41  LOOP           41 -> 21
40  44  NIL
40  45  RETURN

With the following constants table:

constant index	value	relevant instructions
0	`i%`	`1 CONSTANT`, `5 DEFINE_GLOBAL`
1	1	`3 CONSTANT`
2	`i%`	`7 CONSTANT`, `9 GET_GLOBAL`
3	10	`11 CONSTANT`
4	`i%`	`21 CONSTANT`, `30 SET_GLOBAL`
5	`i%`	`23 CONSTANT`, `25 GET_GLOBAL`, `29 ADD`
6	1	`27 CONSTANT`, `29 ADD`
7	`i%`	`36 CONSTANT`, `38 GET_GLOBAL`

The op codes are perhaps confusing, but correct. However, we do note that there are seven constants. The constants for 1, 10 and 1 are expected - those are the start, end and increment respectively. But what about the five instances of i%?

On inspection, we will notice that i% is defined once per each call to DEFINE_GLOBAL, GET_GLOBAL and SET_GLOBAL, respectively. DEFINE_GLOBAL is called once (to define i%), GET_GLOBAL is called thrice (once to compare to 10, once to add 1 to i%'s value, once to print i%), and SET_GLOBAL is called once (to increment i% by one). This behavior is simply unoptimized.

The Challenge

It turns out that's intentional within Crafting Interpreters, the primary reference used for implementing this bytecode. In its "Challenges" section, it notes:

The compiler adds a global variable’s name to the constant table as a string every time an identifier is encountered. It creates a new constant each time, even if that variable name is already in a previous slot in the constant table. That’s wasteful in cases where the same variable is referenced multiple times by the same function. That, in turn, increases the odds of filling up the constant table and running out of slots since we allow only 256 constants in a single chunk.

Optimize this. How does your optimization affect the performance of the compiler compared to the runtime? Is this the right trade-off?

Proposed Implementation

Recall the contents of the emitIdent method in the compiler:

  private emitIdent(ident: Token): Short {
    const constant = this.makeConstant(ident.value as Value);
    this.emitBytes(OpCode.Constant, constant);
    return constant;
  }

This function currently creates a constant, and returns its index. This index is then used by methods that need the identifier. These are currently let_:

  private let_(variable: Variable, value: Expr | null): void {
    const target = this.emitIdent(variable.ident);
    if (value) {
      value.accept(this);
    } else {
      this.emitByte(OpCode.Nil);
    }
    this.emitBytes(OpCode.DefineGlobal, target);
  }

assign:

  private assign(variable: Variable, value: Expr) {
    const target = this.emitIdent(variable.ident);
    value.accept(this);
    this.emitBytes(OpCode.SetGlobal, target);
  }

and visitVariableExpr, which currently gets a global value (the only kind of variable currently supported by Matanuska):

  visitVariableExpr(variable: Variable): void {
    const ident = this.emitIdent(variable.ident);
    this.emitBytes(OpCode.GetGlobal, ident);
  }

What this means is that we may create a new method, getIdent, which wraps emitIdent, and call that method instead from current users of emitIdent.

What this likely means is storing the ident as a hash key:

type IdentTable = { [ident: string]: number };

Then, in getIdent:

  private getIdent(ident: Token): Short {
    return typeof this.idents[ident.value] !== 'undefined'
      ? this.idents[ident.value]
      : this.emitIdent(variable);
  }

and in emitIdent:

  private emitIdent(ident: Token): Short {
    const constant = this.makeConstant(ident.value as Value);
    this.emitBytes(OpCode.Constant, constant);
    this.idents[ident.value] = constant;
    return constant;
  }

Ramifications

On one hand, this will keep the constants table small. In this case, the constants table size would go from 7 values down to 4, a decrease of nearly 50%. Note that, even with the addition of the ident table, memory should still be saved overall, since the identifier would be stored at most twice - once in the constants table, and once in the identifier table.

The compute cost in the compiler is unclear. On one hand, it would need to check if the identifier is in the table every time getIdent is called. Additionally, for new identifiers, an additional call would get made to set the ident in the table. However, for reused identifiers, the lookup should be quick, and we avoid a call to makeConstant. Without benchmarks, it's likely that this would operate as a very marginal improvement in runtime performance, due to caching.

The runtime performance would remain largely the same. Array access is roughly O(1), and is unaffected by the size of the constants table. The number of instructions would also remain the same - the calls to the global methods would simply access the same constant.

It may seem like this change would make it easier to understand the output of a chunk, since identifier constants wouldn't be repeated. However, it would necessarily make the code more complex. Again, it would also have no affect on the disassembled bytecode - it would simply access different constants.

Decision

While this change is tempting, I will not move forward with it at this time. Unlike clox, our constants table's size is unbound, and it's unclear as to whether or not the potential memory savings would be worth the change.

In the future, as more complex programs are implemented, we will revisit this question. We will inspect the constants tables for full programs, and make a decision then. For now, we will focus on more important functionality.

Matanuska ADR 018 - Looping Syntax

Josh Holbrook — Fri, 08 Aug 2025 21:58:35 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

The next feature to implement in Matanuska is looping.

Classic BASIC's looping structures are... idiosyncratic, especially as compared to what's expected in a modern language. Therefore, we would like to compare what's offered by BASIC versus a modern language (in this case, Python), and make a decision based on these trade-offs.

It is worth clarifying what design heuristics are important in this decision:

Matanuska BASIC should loosely mirror classic BASIC dialects, such as MSX BASIC.
Matanuska BASIC should support modern features, such as those in Python, as appropriate.
Matanuska BASIC should be internally consistent. Design heuristics leveraged in its conditionals should also be reflected in its looping.

Current Behavior

Blocks

Recall that Matanuska's compiler uses a Block abstraction to track which block is being compiled. These blocks carry context that's relevant to the block type, and uses a visitor pattern to introduce block-specific behavior for instructions.

Currently, conditionals are implemented. For am example Block class:

class IfBlock extends Block {
  kind = 'if';

  constructor(public elseJump: Short) {
    super();
  }

  visitElseInstr(else_: Else): void {
    const endJump = this.compiler.else_(this.elseJump);
    this.next(else_, new ElseBlock(endJump));
  }

  visitElseIfInstr(elseIf: ElseIf): void {
    const endJump = this.compiler.else_(this.elseJump);
    const elseJump = this.compiler.if_(elseIf.condition);
    this.next(elseIf, new ElseIfBlock(elseJump, endJump));
  }

  visitEndIfInstr(_endIf: EndIf): void {
    // TODO: Optimize for no 'else'
    const endJump = this.compiler.else_(this.elseJump);
    this.compiler.endIf(endJump);
    this.end();
  }
}

However, these blocks are intended to meet other block-like use cases, such as looping and functions.

The good news is that, for abstractions which have clear blocks, the abstraction should gracefully carry state at compile time and help ensure that blocks are well-formed. The bad news is that, for things which don't create blocks but do create state, that state would need to be tracked separately.

Conditionals

Recall that in https://dev.to/jfhbrook/matanuska-adr-013-if-then-and-else-syntax-7m6, we introduced specific syntax for conditionals. Of particular note is that it followed BBC BASIC's lead, and closed multi-line if blocks with an ENDIF token. Ideally, we would like to continue those themes here.

Implementations in Other Languages

MSX BASIC

MSX BASIC, which is typical in terms of a classic BASIC, has only a for/next loop and the classic goto. The structure of a classic for/next loop is like so:

10 FOR x%=1 TO 10 STEP 1
20   FOR y%=1 TO 10 STEP 1
30     PRINT x%
40     PRINT y%
30 NEXT x%,y%

Note that end is inclusive - ie, FOR x=1 TO 10 will print the numbers 1 to 10. Also note that STEP n and the variables to NEXT are optional.

The behavior of NEXT is a little idiosyncratic - it operates as both an end and a continue, and can mark which loop to continue based on a variable.

In terms of how this works under the hood, for loops are not structured as blocks as they are in Matanuska. Instead, they are treated as isolated statements which introduce runtime state. Note that this means MSX BASIC can't guard against "broken" nesting, something that Matanuska attempts to do at compile time.

For completeness, simple GOTO looks like so:

10 PRINT "hello world!"
20 GOTO 10

GOTO is very low level, and can not take advantage of blocks.

BBC BASIC

⚠️ NOTICE ⚠️

This ADR misunderstands the use of the end keyword in BBC BASIC examples. They keyword is used the same way as end in MSX BASIC, and are included in the examples to present complete programs.

BBC BASIC's for loops look a little different:

10 FOR x%=1 TO 10
20   PRINT x%
30   NEXT x%
40 END

What's noteworthy here is that BBC BASIC uses an END keyword to close the loop, but also supports NEXT in a way similar to MSX BASIC. Note that END is inconsistent with other END{begin_block} tokens in BBC BASIC.

Unlike MSX BASIC, BBC BASIC also has while loops:

WHILE x% > 0
  x% = x% / 2
ENDWHILE

Nothing too sophisticated here.

BBC BASIC also supports a repeat/until loop, that is about what one would expect:

REPEAT
  ...
UNTIL ...
END

BASIC8

BASIC8's for loops are similar to those of MSX BASIC. Its while loops are similar to BBC BASIC, but use the WEND keyword instead of the ENDWHILE keyword.

It also has a do/until loop, similar to BBC BASIC, but with significantly different syntax:

DO
  ...
UNTIL ...

Unlike BBC BASIC, BASIC8 does not require an END keyword. It treats UNTIL as similar to MSX BASIC's NEXT keyword.

Python

Python's for loops look like so:

for i in range(0, 10):
    print(i)

What's noteworthy here is two things:

Python takes an iterator as an argument. Classic BASIC does not have first class iterators. But it would be nice if Matanuska could implement them in the future.
Python has proper blocks, like Matanuska.

Python also has a while loop:

while True:
    print "hey"

It also supports the break and continue keywords. continue operates similarly to next in MSX BASIC. But break seems novel.

JavaScript

JavaScript supports a standard C-like for loop:

for (let x = 0; i < 10; i++) {
  ...
}

But it also supports syntax for iterating over objects, namely arrays:

for (const x of xs) {
  ...
}

Decision

For

Standard for loops will have the following syntax:

10 FOR x%=1 TO 10 [STEP 1]
20   PRINT x%
30   NEXT
40 ENDFOR

This leans into the design of BBC BASIC, with a few differences.

First, for loops will be closed with an endfor keyword. This is inconsistent with BBC BASIC's implementation of for loops, but consistent with the syntax of its other looping constructs, as well as Matanuska's syntax for conditionals. Additionally, it will allow for clear block semantics.

Second, NEXT will be supported optionally in a way that mirrors continue in Python. However, it will not accept a variable. This is because Matanuska (unlike MSX BASIC) is block structured.

Note that, in this case, we will support BASIC's syntax with regard to the TO keyword. However, in the future, Matanuska will likely support an additional for loop structure that mirrors for...of in JavaScript:

10 FOR x% OF xs%
20   ...
30 ENDFOR

The specifics of this syntax and implementation are out of scope for this ADR, and will be revisited when Matanuska BASIC supports arrays.

While and Repeat

Matanuska BASIC will also support WHILE, similar to BBC BASIC:

WHILE x% > 0
  x% = x% / 2
ENDWHILE

It will also support repeat/until:

REPEAT
  ...
UNTIL ...

Like BASIC8, it will close these blocks with the UNTIL keyword. Including an ENDREPEAT keyword would be redundant. However, it will use the REPEAT keyword in line with BBC BASIC.

GOTO

GOTO is considered out of scope for this ADR, and will be revisited at a later date.

Matanuska ADR 017 - Vitest, Vite, Grabthar, Oh My!

Josh Holbrook — Sun, 09 Feb 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

In October, what began as a change in test frameworks snowballed into a complete refactor of Matanuska's builds. These changes were very significant, and yet happened quietly. This ADR intends to remedy that situation, to document what those changes were and why they happened.

Tap and NodeNext

When I started Matanuska, I chose Node Tap as my test framework. Tap was my favorite test framework in Node for a very long time. It's historically had an API that's less "magical" than some of the other frameworks out there, it outputs TAP by default - always a bonus - and it has pretty high-level reporting.

However, in recent years, Tap has started to grow weary. Its API became more complicated as it needed to support promises and async/await. Its features became more complicated and complex, and it became harder to use.

But what ultimately made me disillusioned was encountering bugs and odd behavior over time. For instance, I have a directory called ./test/helpers which contains helper modules for my tests. This is a convention I learned from Nest tests during my time at Procore. Tap absolutely refused to ignore this directory (which had no tests in it), regardless of my efforts to configure it thusly.

What pushed me over the edge was issues with native import syntax in Node.js modules (called "nodenext" in TypeScript parlance). Up to this point, I was using "commonjs" builds, where TypeScript would compile my files to use require. This was mostly fine and good, but it would struggle with modules using native import. Most of my dependencies used commonjs, but one of my development dependencies was using native import - this in part motivated me to make the switch. Unfortunately, Tap struggled with this when I initially made this attempt.

Vitest

I began searching for a new test framework, and at the recommendation of Nuck, I gave Vitest a shot. It's by the developers of Vite, which I loved. I don't do a lot of frontend development, but when I do, Vite is often my choice. Unlike many other solutions to frontend builds I've tried in the past, Vite "just works" and involves minimal baggage (looking at you, Angular).

It turns out that Vitest is incredible, and I made the change incrementally - but also quickly. I started by configuring Vite to build files named *.spec.ts, and having Tap run tests named *.tap.ts. Within a few days, the switch was complete.

Overall, I have been extremely happy with Vitest. It has the good parts of Jest and Chai, but without the stranger baggage. It really is incredible, and I can't recommend it enough.

Native Imports in TSC and SWC

Switching to Vitest fixed native import in the tests, and I was quite happy with that. However, I was not out of the woods when it came to using native import in the main project - that effort was still failing.

The issue I ran into is deep in the weeds. When in module mode, Node likes to have imports specify the extension of the file you're importing, and doesn't like importing directories - you have to spell out ./directory/index.mjs, rather than simply specifying ./directory. tsc (TypeScript's standard compiler) doesn't rewrite these import paths in "nodenext" mode. This alone made things awkward.

But I also had my Vitest build configured to use SWC, the compiler backend I had configured for Vitest, and it had issues of its own. SWC is cool. It's a TypeScript compiler written in Rust that is extremely fast, and - unlike tsc - it mostly handles rewriting import paths just fine. However, I did find that it rewrites index.mjs imports into directory imports.

I also found that SWC's standard command line interface was really immature. This seems to be because it was really intended to run within other build and bundling tools, such as Vite and Nextjs.

By this point, I was finding the impedance mismatch between Vitest's SWC-based build and my project's tsc build to be overwhelming, and I yearned to make the two match. I considered switching Vitest to use tsc. But I also found that SWC was SO much faster (it nearly doubled the speed of my tests) that I couldn't say no. By this point, I was committed to using SWC in my build.

Vite

I realized that the way to use SWC successfully in Matanuska's main build was going to involve a singular bundle. At this point, I started asking if Vite itself could run my main build. After all, it was building my tests with SWC successfully!

As it turns out, Vite is more than capable of doing this, through its server-side rendering functionality (SSR). This is a bit of a misnomer. The motivation is to support server-side rendering of React projects, but the actual feature is bundles for server-side JavaScript runtimes like Node.js.

It's a little limited as compared to its frontend builds - but only a little. For one thing, it can only really handle one SSR entry point. The biggest issue, though, is that Vite's standard dev mode is geared towards hot module replacement of frontend code through a proxy over a server - not something that benefits Matanuska. The ramifications of that, though, were simply that I would need to run Vite in batch build mode - not all that different from the pre-existing build process.

Ultimately, I've been pretty happy with Vite as a build tool. It's blazing fast and does exactly what I need!

Type Checking, SWC and TSC

SWC is a great tool when it comes to compiling TypeScript. But it's a bad tool for type checking TypeScript. This is because part of why it's so fast is that it mostly ignores types completely. This meant that, while SWC was being used for the builds, I still needed tsc in the mix for type checking.

Luckily, tsc is much more flexible with inputs when it comes to type checking than it is with generating compiled output. After all, it doesn't need to concern itself with output at all if it's running with the --noEmit flag.

Unfortunately, this did mean that configuration began to sprawl. At this point, I had configurations not just for Vite (shared with Vitest) and tsc, but also for Prettier, ESLint and even ShellCheck. Many of these files had shared settings that needed to match each other. This was somewhat manageable, until Vite was also in the mix.

Grabthar

My instincts when presented with this configuration sprawl was to begin writing some scripts to generate and update configuration for me. The first draft can be seen in the PR that initially implemented the Vite build. These scripts reflected off a shared JSON file (later YAML) and generated the configurations for the downstream tools. In the case of Vite, this happened through an import, but for other tools, it just wrote JSON to disk.

I began to realize that these scripts were becoming elaborate enough that I wanted to massage them into a proper tool. I created a new package, moved the scripts into it, and named the project grabthar.

This name has a funny background. Many years ago, I was in an IRC conversation with a developer who began describing a build tool he was making. I was a jerk and scoffed at the API, and began sketching out my own build tool. I named it grabthar after my favorite joke from Galaxy Quest. It didn't go anywhere, but I kept the source around. When it came time to write a tool for Matanuska, I decided to reuse the name. But anyway, it turns out I was talking to the author of Grunt, and boy did I look silly.

Either way - Matanuska now has a custom build tool. This tool runs hooks to generate configurations, exports functions for tools using JavaScript configs (ie., Vite and ESLint), and runs the appropriate tools in an opinionated manner.

Make no mistake, grabthar is extremely opinionated. Aside from the shared configurations, it's not all that customizable. Any tools using it would need to support exactly the same underlying build stack as Matanuska. But there are benefits to that, too. I'm currently only using it for Matanuska and a handful of its tools, but may use it outside Matanuska in the future if it ages well.

citree

A brief note on citree. citree is a tool I wrote for generating Matanuska's AST classes. This tool is heavily inspired by the script used in Crafting Interpreters' jlox interpreter. It uses a DSL implemented in ts-parsec that takes a specification for an AST and generates classes implementing a visitor pattern. The DSL is a little janky, but it does exactly what I need for Matanuska.

I considered rewriting citree to run as a step in the Vite build. However, I decided to keep it as a separate code generation step. This is because, while hacking, I need the TypeScript files to exist in order to do type checking - simple enough.

jscc

A final consequence of these refactors was the introduction of jscc.

Matanuska has included build-time code generation from pretty early on. In particular, it uses an environment variable (MATBAS_BUILD) to control whether or not to include certain debugging hooks. During development, good debugging output is extremely desirable. But for a release, it slows things down to an unacceptable level - or, at least, that's the common wisdom.

Initially, I solved this through using nunjucks templates for a constants.ts file and a debug.ts file. Under MATBAS_BUILD=debug, the latter file would contain debug output, including tracing (see ADR 14 for more context here). But under MATBAS_BUILD=release, those hooks would be empty "no-op" functions. This all worked, but was dissatisfying.

JSCC was a simple, general purpose tool for the kind of conditional logic I was looking for. Not only did it have a nice syntax that constituted valid JavaScript; it also had a build plugin that would integrate it into my build for all my files. To me, this was a major win.

Summary

That was a lot, so I wanted to quickly summarize what happened here.

Before

citree for generating the AST
tsc for both TypeScript compiling and type checking
No bundling
Prettier for formatting
ESLint for TypeScript linting
ShellCheck for bash linting
Node Tap for testing
Nunjucks for build-time configuration and conditional compiling
No shared build tool

After

citree for generating the AST, as before
tsc for type checking only
swc for TypeScript compiling
Vite for bundling
Prettier, ESLint and ShellCheck used for formatting and linting, as before
Vitest for testing
jscc for build-time configuration and conditional compiling
Custom grabthar build tool

Matanuska ADR 016 - ECMA-55 Compliance

Josh Holbrook — Wed, 05 Feb 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

I discovered in my research that there is an actually an old (and largely obsolete) ECMA standard for a minimal BASIC implementation, which can be found here:

https://ecma-international.org/publications-and-standards/standards/ecma-55/

I also discovered two fantasy console implementations which discuss adherence to ECMA-55:

M16BASIC, which describes specific deviations from the standard
bas55, which purports to be spec-compliant and not much else

Having read the specification - it's about 30 pages - I can say that, generally speaking, it's not worth trying to adhere to in any meaningful way.

One obvious deficit is that its treatment of variables and values is extremely limiting, and even 80s era BASIC implementations deviated from it significantly. In fact, ECMA-55 only supported strings and numbers, while many other dialects support distinct integers and floats.

It also, naturally, has specifications for error handling which would be considered odd by today's standards. It doesn't specify exceptions, of course. But, for instance, its recommendation for integer overflows is to assign an "infinity" value and move forward.

It does, however, have a few areas worth referencing in the future.

Number Literals

The standard includes a specification for how to parse number literals. It only supports decimal representations - no hex or binary - but it does include a specification.

Matanuska's current behavior isn't specified. The scanner converts strings into numbers with parseInt, and otherwise appears to follow a subset of a number formatting standard that's compatible with JavaScript. It would be worth considering a specification for numbers.

Of course, there are many other places to look than ECMA-55. JavaScript's numbers aren't particularly controversial - that specification, or Python's, would suffice. Alternately, VB.NET could be a good source of inspiration.

It's unlikely that ECMA-55 would play a major role in informing such a number literal specification. But it could be a useful refrence, and may not be a stretch to support as a subset.

Built-In Functions

ECMA-55 includes a very short list of implementation-supplied functions. Supporting these would likely not be difficult, and in fact they may make for a good start.

GOTOs

In general, I don't like the semantics of BASIC's GOTOs, and have no interest in adhering to any given standard. That said: the ECMA-55 standard specifies two keywords (go to) rather than one (goto). I don't actually know if that's common in 80s era BASICs. But supporting it wouldn't be difficult either.

FOR/NEXT

The standard includes a tight specification for FOR and NEXT. The FOR statement in BASIC is relatively uncontroversial, and I do intend to develop at least a variant that's more or less a straight cut. It could prove to be a useful reference.

DATA, READ and RESTORE

A feature that I've seen in many BASIC implementations, but have had a hard time wrapping my head around, is built around the keywords DATA, READ and RESTORE. Lucky for us, ECMA-55 includes a straightforward explanation of how this works.

This is important, as BASIC doesn't have syntax for array literals - it uses these keywords to fill in the values of an array instead. While I'm heavily motivated to develop syntax for array literals, these keywords are the likely alternative.

PRINT

As discussed in ADR 15, the ECMA-55 standard reveals that PRINT's behavior is bizarre and strange. When deciding how to implement the PRINT statement, it will be an invaluable reference.

Decision

Having read the standard, I do not feel the need to attempt to adhere to it in any way. By extension, I also do not feel the need to test for any particular behavior as informed by the specification.

That said, we have identified some areas where the standard can operate as a useful reference. No decisions will be made currently in those identified avenues at this time, but the standard is there when I'm ready.

Matanuska ADR 015 - String Concatenation Operator

Josh Holbrook — Sun, 02 Feb 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

Atto

While researching fantasy consoles, I learned about a BASIC implementation called Atto. In its "from BASIC" doc, it mentions that it uses ; as its string concatenation operator.

This seems like an odd decision. But it makes sense when you remember that print in traditional BASIC use ; to separate expressions. As I understand it, this is ad-hoc syntax in those commands. What Atto does here is take this syntax and generalizes it. That makes it a very interesting and clever design choice.

Matanuska BASIC's Current Behavior

Currently, Matanuska BASIC treats + as a concatenation operator. This isn't an unusual choice - BASIC8 goes this route, for example. It's also consistent with many modern languages, such as Python.

Traditional BASIC Behavior

The ECMA-55 Standard describes ; as solely a mechanic within print statements. Other statements which similarly take multiple arguments use , to separate them. In fact, print will allow expressions to be separated by , as well, but treats , and ; differently - put a pin in that.

The specification for PRINT is... interesting. It specifies fixed-width "zones" for print output within a fixed-width "margin". The specification ensures that numbers can be formatted in a way where they'll always fit within one of these zones. It then specifies that, while ; is treated as a concatenation operator, , generates enough space to align the following value to the next zone. TAB(<n>) is treated as special syntax which "tabs over" n number of zones. If a print statement ends in a ; or ,, a newline is not generated and the following print statement appends to the end of that line. Finally, if a print statement has enough values that it overflows the margin (or outputs a string which is long enough to do the same), it inserts newlines as-needed to avoid clipping.

Decision

Matanuska will continue to use the + operator for general purpose string concatenation.

First, + is common and well-understood in many modern languages, while ; would be considered strange and unusual. Honestly, that's enough.

But second, ; isn't treated as a concatenation operator in traditional print statements, as much as it is treated as special syntax for formatting print output - and it's odd syntax at that. Rather than implement ; as a general purpose string concatenation operator, I'd rather leave print statements as a potential odd duck - or possibly avoid traditional semantics altogether, in favor of either echo-like behavior or shell-like string "templating".

Matanuska ADR 014 - OpenTelemetry

Josh Holbrook — Wed, 29 Jan 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

Until recently, I was using a hand-rolled class called Tracer to attempt to trace execution for debug purposes. It was becoming unwieldy, and I yearned for a better solution. As part of that effort, I implemented OpenTelemetry tracing in debug builds of Matanuska.

Why Tracing?

Naively, I implemented Tracer for following the path of execution when errors in parsing or compiling occurred. Both the parser and the compiler have very deep call stacks making stateful changes to the called methods' respective classes. When errors occurred during development, it could be difficult to understand the path of execution that got us there.

This implies that there's a strong benefit to good visualizations for traces, something my Tracer class was struggling to provide. By using OpenTelemetry, we can leverage an open source platform, such as Jaeger, to view traces.

In addition, tracing can be valuable for profiling. While my Tracer didn't implement it, OpenTelemetry traces are timed, and the visualizations show the relative length of time a given trace took. In a world where I don't have great profiling tools for JavaScript, this could be really valuable.

When is Inspecting Better?

A challenge when it comes to tracing is understanding the state of the program at a particular point in time. This can be helped by setting attributes on spans. But in many of these situations, it's arguably more prudent to use Node.js's built-in inspector support.

The benefits and usage of the inspector functionality are largely out of scope for this discussion. But I bring it up to highlight that tracing is not expected to solve every issue with debugging - at least, on its own. In the future, it will likely operate as complimentary to the inspector.

Advantages to OpenTelemetry

Before we get into some of the problems with OpenTelemetry, let's nail down the positives which motivate us to use it:

Better visualization and decreased clutter by using a separate GUI backend for viewing traces
Less maintenance of bespoke abstractions
Fully-featured API

Issues with OpenTelemetry

There are, unfortunately, a few major issues with OpenTelemetry, which need to either be accepted or mitigated.

Challenging Onboarding

First - and this is the elephant in the room - OpenTelemetry's API is sprawling and the JavaScript documentation is lacking. I think this is for a few reasons:

The API has historically been fast-moving. This meant that, once documentation was written down, it immediately went out of date. The OpenTelemetry developers then struggled to fix it in post, especially as the old APIs weren't deprecated - just lower level than a user might expect.
The developers are deep subject matter experts on observability, not user experience. This means that, when prompted, they tend to get into the weeds in ways that don't necessarily help a naive user.
There are generalized problems with tracing that are earnestly hard to solve in a manner conducive to facades and other abstractions. The most significant of these is context management - that is, how does a trace know which span is its parent? It's tempting to say that if React can hide the complexity of hooks, that they can hide the complexity of contexts as well. But React has the advantage of having a single entry point for execution - team Otel, in contrast, fundamentally has to deal with arbitrary entry points.

This caused significant issues when onboarding. I am, however, hopeful that with internal abstractions and the relative stability of today's OpenTelemetry libraries, that the maintenance burden will be acceptable.

Deep Stack Traces

Second - and this was a problem with the hand-rolled abstraction as well - tracing creates very deep stack traces. In the case of OpenTelemetry and trace.startActiveSpan, it's at least two added layers to the stack - one when calling trace.startActiveSpan itself, and another when that method calls context.with in turn. In practice, it's often more.

This can be somewhat mitigated by calling context.with directly. But that introduces a lot of boilerplate, in a world where trace.startActiveSpan is already lightweight enough to motivate a framework-specific implementation with more bells and whistles. Macros could help address the problem, though jscc doesn't support them as such. But even with macros or boilerplate, it would still add the overhead of context.with, which is non-optional when using OpenTelemetry.

Rather than going down this road, here are some other techniques to address the issue:

Use span events. These show up as points in time within an owning span, rather than separate spans. Using span events will avoid polluting the stack trace at all, and are plenty sufficient when the method being called is short-lived - for example, as in most parser methods.
Use jscc to optionally include tracing calls. This can make source mapping more challenging, but will decrease the size of the call stack when tracing isn't desired or necessary.

Sensitivity to Load Ordering

The nature of instrumentation is that it must be loaded as early as possible in the lifecycle of an application. In fact, it's so sensitive that OpenTelemetry recommends pushing the setup into a .cjs file and loading it with the --require flag from the CLI.

In production at many companies, this is simply pulled in as one of the first imports - that was my initial approach as well. But the nature of Matanuska's Vite-based build means that load order can be tough to control.

The introduction of this --require flag for debug-only builds means added complexity to the entry point (ie, ./bin/matbas), to the point where templating becomes a reality.

On Backends

One challenge introduced by OpenTelemetry was the need for a separate backend service. Luckily, Docker is good at hiding that complexity in a container, and Terraform is good at spinning up and down stacks in a reproducible manner. Jaeger in particular has a one-container solution for firing up a backend for local use - this worked great for my purposes.

Decision

With all that in mind, here are the design decisions I went with.

Jaeger Backend

I wrote a new tool called fireball (it's an alcohol joke) which uses Terraform and Docker to stand up and tear down a Jaeger instance. The ergonomics are somewhat similar to Docker Compose - fireball up, fireball up -d and fireball down all work as expected.

This technique has worked incredibly well, beyond my dreams. It was the least challenging part of the OpenTelemetry implementation.

Telemetry Library

The --require technique motivated a separate compiled entry point for the setup of the OpenTelemetry SDK. I decided to push this into a module in a workspace, which is now called via node --require '@matanuska/telemetry' .... The major wrinkle, versus the standard Matanuska build, is that I needed to generate a .cjs build, which in turn meant I needed to use the replace plugin instead of the consts plugin (which appears to depend on the use of import syntax). Luckily, this library is simple and these differences are narrowly constrained. It was even able to leverage grabthar, the custom build tool for Matanuska.

Debug Functions

The debug.ts module implements thin wrappers around the OpenTelemetry API. In particular, it implements a function called startSpan, which is somewhat similar to tracer.startActiveSpan but with the added behaviors of attaching exception data to the span and automatically closing it. In addition, it implements a function called addEvent, which will fetch the currently active span and add an event to it. These functions are not hidden behind jscc blocks, as they need to work in the event that they are called in the release build.

Jscc Patterns

As mentioned, debug.ts exposes its helper functions regardless of the value of MATBAS_BUILD. Instead, this is handled at the call sites.

First, the functions are conditionally imported:

//#if _MATBAS_BUILD == 'debug'
import { Span } from '@opentelemetry/api';
//#endif

//#if _MATBAS_BUILD == 'debug'
import { startSpan } from './debug';
//#endif

The spans are also called conditionally. For instance, in the main loop of the REPL:

async function repl(executor: Executor, host: Host) {
  while (true) {
    //#if _MATBAS_BUILD == 'debug'
    await startSpan('read-eval-print', async (_: Span) => {
      //#endif
      try {
        const input = await executor.prompt();
        await executor.eval(input);
      } catch (err) {
        if (err instanceof BaseFault || err instanceof Exit) {
          throw err;
        }

        if (err instanceof BaseException) {
          host.writeException(err);
          return;
        }

        throw RuntimeFault.fromError(err, null);
      }
      //#if _MATBAS_BUILD == 'debug'
    });
    //#endif
  }
}

This helps avoid the performance overhead inherent in adding tracing, and additionally may help simplify stack traces for release build errors.

Entrypoint

The entrypoint is now assembled from templates, using Terraform. This is accomplished with another module, similar in interface to fireball or citree. It is called during Matanuska's build process.

Loose Ends

This work lays the foundations for doing some really cool things with tracing. However, it does leave some loose ends.

Incomplete Instrumentation

First, at the time of this writing, the parser and compiler are not fully instrumented. Spans for large parts of Matanuska are in-place, but the end result is fundamentally not as fine-grained as it was previously. This is intentional, even aside from efforts to cap scope. As mentioned, it's unclear how useful traces are for fine-grained debugging as compared to inspector tools. As such, I decided to fully instrument these components on an as-needed basis. That will hopefully lead to more useful traces long term.

Bugs

Second, there are number of small but significant bugs. One of them is that the root span for the REPL appears to log twice within Jaeger, for unknown reasons. Another is that spans for script runs are never received at all, likely due to the process exiting before spans can be flushed. OpenTelemetry was largely assumed to be running in the context of long-running applications, and those assumptions are running counter to my current usage. These weren't considered enough to stop me from shipping, but should be addressed eventually.

Jscc Patterns for Non-Telemetry Use Cases

This ADR outlines a series of patterns for use of the debug module. This pattern is new - older features are given default no-op implementations in the debug module. This is because, historically, the problems solved by jscc in all files were being handled through templating in just the debug module. The work to migrate other uses of this module to follow the same patterns is outstanding, as is an ADR discussing how jscc came into the picture.

Debug Logging

Third, there are some questions around debug logging. By default, the SDK will create a DiagLogger if the OTEL_LOG_LEVEL environment variable is set to a valid value, such as info. However, the output is really basic and does not spark joy.

Related is logging from Nestjs, our dependency injection framework. Prior to these changes, I was using functionality on the tracer to log debug information from Nestjs. Now that this is gone, I'm doing so with the default Nest logger.

Between these two, it's tempting to create some shared logging conventions between both Nest and @matanuska/telemetry. However, @matanuska/telemetry should not have a dependency on a given logging library - the implementation should be inline as to avoid instrumentation ordering bugs. Moreover, the OTEL_LOG_LEVEL behavior is relatively difficult to customize and override.

Debugging and Inspecting

Finally, I want to reiterate that the jury is still out in terms of whether or when debugging will be more useful. I deeply suspect that I'll find the debugger more useful in many of the situations I was trying to solve with my Tracer previously. But until I actually have those issues and attempt to use Node's debugging facilities, it will be a mystery. For now, I'm going to include telemetry as a feature, and see where it leads.

Matanuska ADR 013 - If, Then and Else Syntax

Josh Holbrook — Sun, 26 Jan 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

In order to implement conditional branching, we need to specify a syntax for if, then and else. We would like this syntax to match the expectations of a period-appropriate BASIC, but we would also like it to support modern idioms, particularly multi-line branches.

MSX BASIC supports the following forms:

IF <condition> THEN <lineNo | instructions>
IF <condition> THEN <lineNo | instructions> ELSE <lineNo | instructions>
IF <condition> GOTO <lineNo>
IF <condition> GOTO <lineNo> ELSE <lineNo | instructions>

When supplied a lineNo, BASIC will jump to that line. Otherwise, it will run the listed instructions.

Notable is that MSX BASIC does not support multi-line if statements. For an example of a BASIC which does support them, we can look to BBC BASIC. BBC BASIC supports the following:

IF <condition> THEN
  ...
ELSE
  ...
ENDIF

Also notable is that neither MSX BASIC nor BBC BASIC has an else if - though, MSX BASIC likely parses if <cond> then <ins> else if <cond> then <ins> else <ins> as If(cond, ins, If(cond, ins, ins)), where the second if is simply another instruction.

Decision

We will support two kinds of "if"s: single-line instructions (called ShortIf in the AST) and multi-line collections of instructions (made up of the instructions If, ElseIf, Else and EndIf. Single-line if instructions may be evaluated as commands.

Single-line if statements will initially support the following forms:

if <condition> then <instructions> endif
if <condition> then <instructions> else <instructions> endif

In these forms, instructions may not contain if/else/endif instructions used in a multi-line context. They may, however, support nested short ifs - that is, if and else are allowed if they're closed with an endif on the same line.

Multi-line if blocks will support forms such as the following:

<line_no> if <condition> then
  <lines>
<line_now> else if <condition> then
  <lines>
<line_no> else
  <lines>
<line_no> endif

else if will be treated the same as in JavaScript, or like elif in Python.

What's Not Supported

GOTOs

These forms don't support line numbers for goto. That decision will be made in the future, when goto is existing functionality.

Else If in Short If

As noted, "long if" supports else if. However, "short if" currently parses if <cond_a> then <then_a> else if <cond_b> then <then_b> endif endif as containing a nested "short if" within an "else" block, and if <cond_a> then <then_a> else if <cond_b> then <then_b> endif is considered unterminated. This is because the whitespace in a "long if" is significant!

This issue reveals a wart in Matanuska BASIC's syntax - and, in fact, BBC BASIC does not support an analogous construction.

One way to address this may be to introduce a new keyword, elif, that operates like the corresponding keyword in Python. In fact, if that were the case, we would likely deprecate else if in long ifs in favor of elif.

There's an argument to be made for not supporting "else if" in Matanuska BASIC at this time, in order to avoid such a deprecation. That would be consistent with other decisions made in this ADR. However, unlike those decisions, this one doesn't significantly complicate the parser. Moreover, there isn't a strong motivation to use else if on its own line to represent a discrete if inside a else block, therefore deprecation is anticipation of such a deprecation. That would not expected to be painful.

Unterminated "Short If" and Multi-Line with Then on Same Line

Also not supported are an unterminated short if, as in MSX BASIC and BBC BASIC:

if <condition> then <instructions>

and a long if supporting "then" instructions on the first line, which is not supported by MSX BASIC nor BBC BASIC:

<line_no> if <condition> then <instructions>
<line_no>   else <instructions> endif

Allowing one of these forms doesn't strictly rule out the other. But supporting both requires a more complicated grammar. For instance, an implementation supporting both may require lookahead in the compiler, or possibly backtracking in the parser.

Allowing either form exclusively, on the other hand, is relatively straightforward. This means that, while implementing one of them would be easy, it would make it much more difficult to implement the other.

By implementing neither, we leave the door open on this issue.

Then on Following Line

Finally, a feature for which support was considered but dropped is starting then on the following line, like so:

<line_no> if <condition>
<line_no>   then <instructions>
  <lines>
<line_now> else if <condition>
<line_no>    then <instructions>
  <lines>
<line_no> else
  <lines>
<line_no> endif

There are aesthetic reasons to support this form. However, allowing it also complicates the parser by introducing a new form for lines:

line_with_then := <line_no> then <instructions>

with this form only being valid if the previous line contains an if statement ending before the then. Practically speaking, parsing this form requires maintaining an extra piece of state in the parser - "should we expect a then" - and matching it prior to parsing other instructions in those cases. This isn't a heavy lift, but it's enough of a complication that BBC BASIC did not implement it. In our case, we're deciding to leave it out for now, so as to not immediately commit to the additional complexity in our parser. It may, however, be introduced in the future.

Matanuska ADR 012 - Execution Domain Model

Josh Holbrook — Wed, 22 Jan 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

Matanuska contains a number of domain concepts to describe the syntax and semantics of source code, parsed trees, and compiled programs. Currently, they are named (and defined) as such:

Expressions: Units of code which apply a stack of operations on values and evaluate to another value. Expressions do not cause side effects directly, though function calls may execute commands which do cause side effects.
Values: Elements within memory that represent numbers, booleans, strings, and various object types. May either be contained within a variable, or specified as a "literal" within source code.
Operations and Operators (source and AST): Elements within expressions that add or remove values from the expression stack when they're evaluated. These have varying semantics, such as having infix/prefix/postfix operators and having operator precedence. Note that operators are the syntactic element, and operations are the corresponding units of execution.
Commands: Units of code which generally invoke state when executed. Commands may take expressions as arguments, but may also include non-expression syntactic elements or other commands. These are generally separated by colons (:) within command groups.
Interactive commands: Commands which may only be executed in an interactive session, through use of the command module. These commands are syntactically within non-line command groups.
Runtime commands: Commands which are compiled into chunks and op codes and executed by the runtime.
Simple and complex commands: Complex commands are commands which may contain other commands. This is in contrast to "simple commands", which never contain other commands. This concept is not currently represented within the source code, but is useful to distinguish in the context of this ADR.
Command groups: A series of commands, separated by colons (:). These command groups may form the non-numbered portion of a line, or may constitute "bare" interactive commands.
Lines: A command group combined with a preceding line number. Lines are currently contained on a single source line, though that may not be true in the future if newlines can be escaped (like Bash).
Instructions: Collections of op codes and addresses which, when encountered by the runtime, cause some effect to occur.
Op codes: Integer values which, when combined with addresses into instructions, cause the runtime to execute an "operation". These values are between 0 and 255, and are intended to be represented by bytes (as in bytecode). These are also called "byte codes" - or simply "codes". "Op" is short for "operation".
Operations (bytecode): Stateful actions which occur when the runtime encounters an op code. This is distinct from operations in source or AST code, though they may implement the behavior implied by a source or AST operation.
Chunks: Collections of bytecode, along with various pieces of metadata. These form the base units which are executed by the runtime. This term comes directly from Crafting Interpreters.
Bytecode: The unifying concept around op codes, instructions and chunks. In other words, bytecode is made up of chunks and instructions.

However, in the MSX Wiki, they very consistently call them "instructions" - and it is believed that the domain model in not just MSX BASIC but most other classic BASIC languages as well.

This raises the question: should Matanuska rename "commands" to "instructions"? If so, how would this decision cascade to the rest of the domain model?

Motivations for Renaming Commands

The first, and most obvious reason, to rename "commands" to "instructions" is to maintain consistency with MSX BASIC. While this may allow for borrowing more ideas from MSX BASIC (instead of having to invent them), it also makes Matanuska more of a "true BASIC". One of Matanuska's design goals is to, in fact, invoke classic elements of an 80s era BASIC; therefore, this reason is compelling.

But another motivation is that the term "command" is overloaded in Matanuska right now. This can be seen by having to differentiate between "interactive commands" and "runtime commands". While these types of commands are represented similarly in source code, they are executed through very different mechanics. In the former case, they are executed through the command module directly from the AST. In the latter, they are compiled into "instructions" or "op codes" and executed through the runtime.

This could also be motivated by a desire to align with WIC&I. The idea of a separate execution path for commands, through the command module, comes directly from this source, which implies that "runtime commands" are not commands in the WIC&I model.

Instructions in ASTs and Bytecode

Consider that we rename "commands" to "instructions", and consider "interactive commands" to be simply "commands", a special case of "instructions". This reveals a new problem: the term "instruction" is already used within the runtime to refer to collections of op codes and addresses.

This is not entirely accidental - in traditional BASIC, programs are stored in an uncanny valley between AST and bytecode. Like bytecode, BASIC programs are stored in bytes, with instructions stored in "reverse polish" - but, like an AST, they can be translated back into source code at any time. The structure of BASIC means that source code instructions are exactly equivalent to bytecode instructions. Even as Matanuska diverges from this design, there's still a clear lineage of semantics between the construction of a BASIC source instruction and a bytecode instruction.

On the surface, it may make sense to rename "instructions" in bytecode to some alternative name. However, that's challenging, because "instruction" has particular meaning within the context of bytecode. But consider that "instruction" has general meaning within a language itself, and that - in a sense - the BASIC source and the bytecode constitute different languages. In short, "instruction" has the same semantic meaning with the additional context of them being in the source code and AST or in bytecode. This is different from the case of "command", as "interactive commands" are a subtype of source/AST instructions/commands, rather than a type of command distinct from source/AST instructions/commands.

Decision

Matanuska will modify its definitions for execution domain concepts to align with the following:

Instructions (Source or AST): Units of code which generally invoke state when executed. These were previously called commands. This will extend to other concepts: "instruction groups", "simple instructions", "complex instructions", etc.
Commands: Instructions which are executed in an interactive session. This is similar to the previous idea of interactive commands, but also includes "runtime commands" which were executed interactively. Note that, depending on the context, a command may be made up of multiple colon-separated instructions.
Runtime instructions: Instructions which are compiled into chunks and codes and executed by the runtime. These were previously called "runtime commands". Often these will simply be called "instructions" - we only need to invoke "runtime instructions" when there's a strong need to exclude "commands".
Runtime commands (or compiled commands): Runtime instructions which were sent as commands in the REPL. These are known as "commands" before they are scanned and sorted into runtime instructions, at which point they are known as "runtime commands" or "instructions" depending on the context.
Instructions (Bytecode): Instructions in bytecode will continue to be called "instructions", but may be referred to as "bytecode instructions" to distinguish from source or AST instructions.

Matanuska ADR 011 - Let and Assign Semantics

Josh Holbrook — Sun, 19 Jan 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

In a traditional BASIC, the let keyword is used for both defining variables and assigning new values to them. But this keyword is also optional - most BASIC interpreters understand i% = 1 and let i% = 1 to be synonymous.

On the other hand, many modern languages have semantic division between definition and assignment. For example, JavaScript defines variables with let or const, and uses a simple = for assigning to existing variables. This allows JavaScript to distinguish between local and non-local (or global) variables.

Python handles this in reverse - a simple = will define a local variable if it's unassigned, but the nonlocal and global keywords will allow for assigning to those kinds of variables.

Decision

In Matanuska, let will be used for defining variables, and a simple = will be used for assignment. This will allow supporting non-local variables in the future, while having syntax and idioms similar to a traditional BASIC.

Matanuska ADR 010 - Architecture, Revisited

Josh Holbrook — Wed, 15 Jan 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

In ADR 002, we outlined an initial architecture based on the book Writing Interactive Compilers & Interpreters by PJ Brown. But as implementing Matanuska has progressed, the actual architecture has deviated from that design. This document details these changes, along with their rationale and consequences.

Architecture v1

Let's start with a diagram of the architecture prior to significant refactors away from the design in ADR 002:

In this architecture, that Translator is responsible for reading input from either an interactive session or a script, parsing it, adding lines to the editor, and passing parsed ASTs to the Commander. The commander, meanwhile, is in charge of both compiling and executing runtime commands, and directly executing non-runtime interactive commands (such as editing). The editor is referenced by both the Translator and the Commander - the former writes to it, and the latter reads from it. Finally, the initial architecture called for a "recreator", which would take parsed ASTs and convert them back to source code.

Decision

The architecture after significant refactors looks like this:

I will now dive into the differences between this architecture and the previous architecture.

The Executor and the Command Module

First, the Commander has been renamed to Executor, though it retains much of the responsibilities of the "command module" called for by WIC&I. Second, a second command subsystem (literally in the "commands" module) is in charge of interpreting interactive commands through a visitor pattern - though, crucially, it calls back to the Executor to do the heavy lifting. While the command module implements high-level flows, the Executor remains at the core of executing commands.

The new command module is motivated by the use of a visitor pattern. While I don't think it's entirely accurate to say nobody was doing object oriented programming in the age of PJ Brown, I do think it was uncommon, and the book doesn't indicate the use of any particular patterns. Chief among these is the visitor pattern, as detailed in Crafting Interpreters by Robert Nystrom. Matanuska, in contrast to the implied WIC&I architecture, uses the visitor pattern extensively.

The visitor pattern ends up being a good way to avoid large if/else statements doing instanceof checks on command objects. Instead, it tells a given command object to delegate behavior to the appropriate method on a visitor. Initially, the Commander was intended to be that visitor, but it made sense to separate that visitor from session management and execution - hence, the separation of responsibilities.

The Translator and the REPL

This revised architecture does away with the Translator, moves parsing and editing responsibilities to the Executor, and leaves behind two functions in the index module: script, which tells the Executor to load and run a script, and repl, which implements a simple read-eval-print loop (REPL) on top of the Executor.

The primary driver for this change is pressure to move parsing and editing to the Executor. Prior to this change, input was being interpreted in two layers - once to decide whether input should be put in the Editor or passed to the Commander; and second in the Commander itself.

This created two problems. The first was that script and interactive execution became inconsistent. The former calls load() and run() on the Commander, which then need to call the parser (or the translator as a proxy); while the latter needed to do parsing in order to know if input was destined for the Editor or not.

Additionally, this meant that the Editor was being accessed by two different objects, effectively using it to pass data to each other. This created an awkward division of concerns problem. Ideally, the responsibility of delegating edits would remain with one class, not two.

The idea of a "translator" also seems to combine both the responsibilities of a parser and a REPL.

The concept of a REPL came from Lisp, with origins in 1964 but popularized with Scheme in the 80s. I don't have strong evidence of this, but I suspect the terminology (and implied architecture) wasn't common outside Lisp until non-BASIC, non-shell scripting languages gained popularity in the 1990s; and the Open Source Movement (particularly as related to GNU) spread the gospel of Lisp. I suspect that the advice for implementing a translator is simply out of date.

Moreover, the v1 architecture already provided a separate parser abstraction. This made the translator, at best, a proxy for the parser that also included the baggage of a REPL.

The Interactive Compiler

The compiler module was refactored to handle both interactive and runtime commands, and return different results accordingly. Without this change, the Commander had to separate commands within input and implement switching logic internally. This sounds like a minor issue. But it created challenges when trying to report compiler warning all at once, rather than piecemeal as commands were executed. This change allows all compilation and warning collection to occur in a single pass.

It's also motivated by yet another visitor. The runtime compiler uses a visitor to convert commands into Chunks, while the interactive compiler decides whether or not a command is interactive or not. This is distinct from the visitor that takes an already-known interactive command and decides how to execute it.

The Recreator

Finally, the recreator was removed from the architecture. This is because, as the AST evolved, it ended up retaining the full source code for each line. This was motivated by good error messages - when an error is found during parsing or compiling, error messages are able to take both the original source and offsets to display exactly where the error was located.

Given that parsed lines retain their original source, the recreator was no longer required - hence, removed. Something like the recreator may end up being implemented in the future - however, it would operate less as a requirement for generating listings, and more as a code formatter.

Future Concerns

In the future, I can see a few other changes being made.

First is revisiting ownership of readline management. This is currently handled by the Executor. But it's also squarely an I/O concern, and all other I/O and OS operations are currently handled by the Host. One could argue that readline is "higher level" than the functionality of the Host, or that it's appropriate due to the Executor's ownership of sessions. But I'm not entirely convinced.

Second is revisiting the decision to make the Host a pluggable component in charge of I/O. The surface area of Host is huge. Meanwhile, Node.js - and other potential encoding language targets - have perfectly capable OS and FS modules. There is a need to wrap these capabilities, namely for reifying errors into Exceptions. But there are other ways of doing this. For example, Matanuska could implement OS and FS modules of its own.

A major motivator for a Host module was to make it pluggable. The ideas was that the implementation of Matanuska would be independent of the JavaScript runtime - for example, in the browser, one could use a BrowserHost instead of a ConsoleHost. In fact, this is used for testing, where we implement a MockConsoleHost. But there are other ways to mock these libraries. All that said, we will stay the course for now.

Finally, it may make sense to separate session management from the Executor. The executor has already been separated from command interpreting concerns, which leaves it with execution logic and session management - arguably two easily separable responsibilities. The executor is currently reasonably sized and comfortably owns prompting, so it's OK to keep these responsibilities coupled for now. But if the Executor gets too large, this may end up being a refactor worth considering.

Matanuska ADR 009 - Type Awareness in The Compiler and Runtime

Josh Holbrook — Sun, 12 Jan 2025 12:00:00 +0000

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

In ADR 007, we specified the type semantics for operations on dissimilar types. The takeaway from this ADR is that there are many such operations which are invalid, and the ones which are valid require implicit type casting. In other words, the types of values matter.

In ADR 008, we decided to implement a standard BASIC model for manifest data types. To review, primary variables are typed using a postfix sigil, but those sigils don't distinguish them from arrays and functions. That means that we sometimes have compile time type information.

When available, the advantages of manifest data types are two-fold.

First, the compiler can implement type checks - in other words, this introduces type safety. This can be accomplished by maintaining a stack of types in the compiler and comparing them at compile time. When the compiler detects an operation is being executed on incompatible types, it can throw an error prior to runtime execution. This is generally considered a better user experience.

Second, the runtime can assume data types and use type-specific bytecode instructions. In a fully typed language like Java, the runtime can implement type-specific instructions. For example, suppose we are executing 1 + true and that our language casts boolean arguments to integers. In a dynamic typing regime, we would implement a generic ADD instruction that checks the types of the two values and casts true to 1 on the spot. But if we know a priori that 1 is an integer and true is a boolean, we could instead execute CAST_INT_TO_BOOL, ADD_INTS, and these instructions can assume that their arguments are a bool and two ints respectively. In contrast, a dynamically typed language must use a generic ADD instruction.

The trade-off here is that typed instructions require more instructions, but each instruction requires less work. Unfortunately, a partially typed runtime would mean that we'd need to implement both typed and dynamic instructions - in other words, we would need to implement CAST_BOOL_TO_INT and ADD_INT for when types are known, and generic ADD for when types are unknown. This may still allow for optimized execution in cases where types are known, assuming that switch statements are cheap, but the runtime becomes undenably more complex.

The alternative is to implement a dynamic runtime, and only check types in the compiler. This would mean instructions would still need to check types and do implicit casting, but it would also mean a simpler instruction set - and remember, this doesn't preclude the compiler implementing partial type safety. Note also that a fully dynamic runtime can be an incremental step. If we implement a fully dynamic runtime, we can always add type-specific instructions later.

Decision

First, we will implement type checks in the compiler by simulating a stack. These types will initially support primary types and an Any type. This will allow the compiler to detect and throw type errors, giving an improved user experience.

However, this work may be deferred until an unspecified date. It's more important that runtime behavior is correct than it is that type errors are caught in the compiler, and implementing it is relatively challenging - and low priority.

Second, we will not initially support typed operations in the runtime. This will likely manifest in a slower runtime as compared to one that can assume types. But will also keep the scope of the initial implementation smaller, as well as leaving the door open for typed operations in the future.