Solving puzzles using Sentient Lang

I’ve been playing a mobile room-escaping-themed puzzle game (I believe the title is simply Can You Escape 50 Rooms) with a friend, and there was a certain puzzle that we got stuck on. By stuck, I mean that we certainly would’ve figured it out eventually, but it was more frustrating than fun, and it consumed enough time that I thought up a fun way to cheat. I am not against cheating at puzzles that are failing to provide me with joy, or that I’m simply unable to complete, but I have a sort of personal principle that if I’m going to cheat, I’m going to attempt to learn or develop something in the process.

MINOL and the languages of the early micros

This post was updated in May 2020 with an explanatory footnote sent in by a reader.

When I started playing with VTL-2, another small and obscure language was included in the same download: MINOL. Inspired by BASIC syntax and written by a high-schooler in 1976, it “has a string-handling capability, but only single-byte, integer arithmetic and left-to-right expression evaluation.” What I am assuming is the official spec PDF was seemingly submitted over several letters to and subsequently published by the magazine, “Dr. Dobb’s Journal of Computer Calesthenics and Orthodontia.” This article described the purpose and syntax of the language, as well as the code for the Altair interpreter.

MINOL has 12 statements: LET, PR(int), IN(put), GOTO, IF, CALL, END, NEW, RUN, CLEAR, LIST, and OS (to exit the interpreter).As quoted above, there is integer arithmetic (+-*/), and there are three relational operators, =, <, and the inexplicably-designated #1 for not equal. Line numbers are single-byte, with a maximum of 254 lines. Statements can be separated with a colon. Exclamation points are random numbers. If (immediately) running a line without a line number, GOTO calls its line number 0. Rudimentary string-handling seems to be the big sell. This basically entails automatically separating a string into individual code points and popping them into memory locations, as well as some means of inverting this process. An included sample program inputs two strings and counts the number of instances of the second string in the first; being a bunch of code points contiguous in memory, it is certainly functional.

Is MINOL interesting, as a hobbyist/golf language? I may very well try one or two string-based challenges with it. Its limitations are quirky and could make for a fun challenge. I think more than anything, however, I’m just fascinated by this scenario that the Altair and similar early micros presented. Later micros like the Commodore PET booted right into whatever version of BASIC the company had written or licensed for the machine, but these early micros were very barebones. Working within the system restrictions, making small interpreters, and designing them around specific uses was a very real thing. It’s hard to imagine languages like MINOL or VTL-2 with their terse, obscure, limited syntaxes emerging in a world where every machine boots instantly into Microsoft BASIC.

Once again, I don’t know how much value there is in preserving these homebrew languages of yore, but as I mentioned when discussing VTL-2, folks nowadays generate esoteric languages just to mimic Arnold Schwarzenegger’s speaking mannerisms. Given that climate, I think there’s a pretty strong case to keep these things alive, at least in a hobbyist capacity. And given the needs of early micro hobbyists, I find the design of these languages absolutely fascinating. I’m hopeful that I can dig up others.


VTL-2: golfing and preservation

I’ve been playing with Gary Shannon and Frank McCoy’s minimalist programming language from the ‘70s, VTL-2 PDF as of late. Written for the Altair 8800 and 680 machines, it was designed around being very small – the interpreter takes 768 bytes in ROM. It has quite a few tricks for staying lean: it assumes the programmer knows what they’re doing and therefore offers no errors, it uses system variables in lieu of many standard commands, and it requires that the results of expressions be assigned to variables. It is in some ways terse, and its quirks evoke a lot of the fun of the constrained languages of yore. So, I’ve been playing with it to come up with some solutions for challenges on Programming Puzzles and Code Golf Stack Exchange (PPCG)1.

I mentioned that it is in some ways terse, and this is a sticking point for code golf. VTL-2 is a line-numbered language, and lines are rather expensive in terms of byte count. Without factoring in any commands, any given line requires 4 bytes: (always) two for the line number, a mandatory space after the line number, and a mandatory CR at the end of the line. So, at a minimum, a line takes 5 bytes. This became obvious when golfing a recent challenge:

3 B=('/A)*0+%+1

saved a byte over

3 B='/A
4 B=%+1

These almost certainly look nonsensical, and that is largely because of two of the things I mentioned above: the result of an expression always needs to be assigned to a variable, and a lot of things are handled via system variables instead of commands. For example, ' in the code above is a system variable containing a random number. There is no modulo nor remainder command, rather % is a system variable containing the remainder of the last division operation. Thus originally, I thought I had to do a division and then grab that variable on the next line. As long as the division is performed, however, I can just destroy the result (*0) and add the mod variable, making it a single shot. It’s a waste of our poor Altair’s CPU cycles, but I’m simulating that on modern x64 hardware anyway. And despite the extra characters, it still saves a byte2.

Other notable system variables include ? for input and output:

1 A=?
2 ?="Hello, world! You typed "
3 ?=A

Line 1 takes input – it assigns variable A to the I/O variable, ?. Line 2 prints “Hello, world! You typed &rquo;, and then line 3 prints the contents of variable A. Lines 2 and 3 assign values to the I/O variable. The system variable # handles line numbers. When assigned to another variable (I=#), it simply returns the current line number. When given an assignment (#=20), it’s akin to a GOTO. The former behavior seems like it could come in handy for golf: if you need to assign an initial value to a variable anyway, you’re going to be spending 4 bytes on the line for it. Therefore, it may come in handy to, say, initialize a counter by using its line number: 32 I=#.

Evaluation happens left-to-right, with functional parentheses. Conditionals always evaluate to a 1 for true and a 0 for false. Assigning the line number variable to a 0 in this way is ignored. With that in mind, we can say IF A==25 GOTO 100 with the assignment #=A=25*100. A=25 is evaluated to a 1 or a 0 first, and this is multiplied by 100 and # is assigned accordingly. ! contains the last line that executed a #= plus 1, and therefore #=! is effectively a RETURN.

There’s obviously more to the language, which I may get into in a future post3. Outside of the syntactical quirks which make it interesting for hobbyist coding, the matter of running the thing makes it less than ideal for programming challenges. Generally speaking, challenges on PPCG only require that a valid interpreter exists, not that one exists in an online interpreter environment such as Try It Online (TIO). In order to futz around in VTL-2, I’m running a MITS Altair 8800 emulator and loading the VTL-2 ROM. TIO, notably, doesn’t include emulation of a machine from the ‘70s with a bundle of obscure programming language ROMs on the side.

This brings me to my final point: how much effort is being put into preserving the lesser-known programming languages of yore, and how much should be? I personally think there’s a lot of value in it. I’ve become so smitten with VTL-2 because it is a beautiful piece of art and a brilliant piece of engineering. Many languages of that era were, by the necessity of balancing ROM/RAM limitations with functionality and ease of use. Yet, there’s no practical reason to run VTL-2 today. It’s hard to even justify the practicality of programming in dc, despite its continued existence and its inclusion a requirement for POSIX-compliance. New esoteric languages pop up all the time, often for golfing or for sheer novelty, yet little to no effort seems to be out there to preserve the experimental languages of yesteryear. We’re seeing discussions on how streaming gaming platforms will affect preservation, we have archive.org hosting a ton of web-based emulators and ROMs, we have hardware like Applesauce allowing for absolutely precise copies to be made of Apple II diskettes. Yet we’re simply letting retro languages… languish.

To be clear, I don’t think that this sort of preservation is akin to protecting dying human languages. But I do think these forgotten relics are worth saving. Is “Hello, world!” enough? An archive of documentation? An interpreter that runs on an emulator of a machine from 1975? I don’t know. I don’t feel like I have the authority to make that call. But I do think we’re losing a lot of history, and we don’t even know it.


Interpreting 69lang (a ;# dialect) in dc

PPCG user caird coinheringaahing came up with a language, ;#, and a code golf challenge to implement an interpreter thereof. The language has two commands: ; adds one to the accumulator, # mods the accumulator 127, outputs its ASCII counterpart, and resets the accumulator. It is, quite clearly, a language that only exists for the sake of this challenge. I mostly do challenges that I can do in dc, which this challenge is not (dc simply cannot do anything with strings).

What I can do is establish a dialect of ;# wherein the commands are transliterated to digits1. I’ve opted for 6 and 9, because I am a mature adult. So, assuming the input is a gigantic number, the challenge is fairly trivial in dc: 0sa[10~rdZ1<P]dsPx[6=Ala127%P0sa]sR[la1+saq]sA[lRxz0<M]dsMx

0sa initializes our accumulator, a, to zero. Our first macro, [10~rdZ1<P]dsPx breaks a (presumably very large) number into a ton of single-digit entries on the stack. ~ yields mod and remainder, which makes the task quite simple – we keep doing ~10, reversing the top-of-stack, and checking the length of our number. Once it’s down to a single digit, our stack is populated with commands.

The main macro, [lRxz0<M]dsMx runs macro R, makes sure there are still commands left on the stack, and loops until that is no longer true. R, that is, [6=Ala127%P0sa]sR tests if our command is a 6 (nee ;), and runs A if so. A has a q command in it that exits a calling macro, which means everything else in R is essentially an else statement. So, if the command is a 9 (or, frankly, anything but a 6), it does the mod 127, Print ASCII, and reset a to zero stuff. All we have left is [la1+saq]sA, which is macro A, doing nothing but incrementing a.

66666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666669666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666966666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666666666666666696666666666666666666666666666666696666666666666666666666666666666666666666666666666666666666666666666666666666666666666669666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666966666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666669666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666669
0sa[10~rdZ1<P]dsPx[6=Ala127%P0sa]sR[la1+saq]sA[lRxz0<M]dsMx

Hello, World!

Tetris has been implemented in Conway's Game of Life (external)

Over four years ago, a challenge was posed on the Programming Puzzles & Code Golf Stack Exchange: Build a working game of Tetris in Conway’s Game of Life (GoL). Yesterday, an incredibly dedicated team of seven posted a working solution that is just fantastic to read about. I am flabbergasted by the work that went into this, and what these folks achieved. Starting with the concept of a metapixel – essentially a giant block of GoL tiles that can be programmed to behave like a single GoL cell, but with any ruleset – they developed wiring, logic gates, an ALU, a RISC architecture, an assembly language, a higher-level language, and finally (for now) a working game of Tetris. Not the first example of advanced computation in GoL (Wireworld is well known), but almost certainly the largest in scope and likely the best-documented as well. I linked to the Stack Exchange page, and if you have any knowledge of GoL, logic gates, or low-level computing, the multiple write-ups are incredibly clear and fascinating.


wo: 9-byte modulo

While working on a code golf challenge in dc today, my mind turned to if and how I could solve the same challenge with the current instruction set of wo. We left off in the middle of wo5, with six slots to go and the promise of division. Internally, I was filling a couple of slots with additional stack manipulation instructions, with three slots still open. The goal isn’t necessarily to be able to do everything (or, perhaps, much of anything) efficiently at this point, but to leave that bit-shaving option on the table, letting the programmer do the most with the least. Since there’s no fractional input, division was a no-brainer: now you can enter fractions, you can waste a little time making a reciprocal for multiplication, and you can (of course) divide.


wo: Registers

Thoughts on wo have slowed down slightly, largely because I think I’ve gotten a lot of easy answers out of the way. I haven’t yet addressed – no. 4, REGISTER. Delegating as much responsibility to internal registers as possible, and allowing a wo programmer to modify these registers is paramount to opening up the extent of what can be done inside of a limited instruction set. As few system registers as possible will be reset at every turn – this is likely necessary for something like ‘stack depth,’ as it is a valuable value for a user to be able to fetch, but for a user to change it would be both unpredictable and of limited value.


wo: Stacks

At some point the question of stacks in wo needs to come up. How many, how do they work, how do we manipulate them. As mentioned in the first post in the matter, I’ve been operating under the premise of a stack that does not shrink (unless cleared). It takes the theoretically-infinite stack of RPL, and combines it with the repeating bottom of RPN. Thus (pseudocode, obvs):

> 1 2 PRINT_STACK
1
2

> 3 PRINT_STACK
1
2
3

> DROP PRINT_STACK
1
1
2

wo: Implementing the interpreter

I’ve been thinking a lot about instructions for wo, how to eke the most out of low-byte-count programs. And, while I haven’t touched on it here yet (soon!), I’ve been thinking a lot about what system registers could prove useful as well. But a big part of me wonders how I’ll implement the thing, if I ever do. That so many esoteric/golfing languages are just layers on top of another scripting language makes me a bit grumpy, and that isn’t a path I’d like to take with wo. My plan would be to write the reference interpreter in go, but I wouldn’t discount ANSI C either. That decision is trivial, though.


wo: A truth machine in wo3

In wo3, we get two extra instructions for a total of four. OISCs can be Turing complete, so four instructions should be enough to give us some brunt. At this point, some amount of math is probably a good idea. Instruction three, then, is ADD, which does what you think it does. Since we’re capable of entering negatives, we can pretty much get to any number we want at this point, albeit terribly inefficiently.

Branching would be very convenient at this point as well, so a simple SKIPZERO instruction gets the no. 4 position; it pops a value from the stack and if that value is zero, it skips until past the next instruction. All odd (input) words are skipped until an even (instruction) word is encountered, at which point that is skipped and the next word is interpreted. Skip if zero is a standard simple conditional branch, but I’ll likely change this to skip if (skip register), so a user can theoretically set the branch condition via a register (with a command certain to be available in wo4).


wo: Numbers

A draft of this post began:

A few thoughts on numbers in wo. Numbered input is pushed to the stack via LSB==1. LSB==0 signifies an instruction, so in either case, effective word size is 1 bit less than total word size. The stack itself won’t care what sort of numbers it’s holding, input is the tricky part. wo3 would allow you to enter the integers 0-3, or 2-1 depending on unsigned vs. signed input. wo4 0-7 or 4-3. These aren’t big numbers to work with, so getting instructions in early to allow for more complicated input would be welcome. The easiest solution here is simply getting the WORDSIZE instruction out of the way as early as possible, ideally in two bits. With signed input, this would only get a user up to a 4-bit word size with 6 bits of input. Unsigned, a user could get up to 6-bit word size in the same 6-bit input, which raises the question of whether allowing a single word input of 1 is more important than more immediate access to slightly higher integers. Signed input would reduce the need for a sign-changing instruction at the low end of the set, and there are little hacks that could be put in place – for example, if 1s’ complement was used instead of 2s’, 0 could act as a stand-in for the next highest byte size or the like. Thus 6 bits of input could immediately kick word size up to a full byte.

As outlined in this post killing off WORDSIZE, I have changed my thoughts on that matter. I do think input will (by default) be 1s’ complement, with 0 receiving special treatment, what I am internally referring to as the Magic Number or MNum. MNum would allow some instructions to serve multiple purposes, which could theoretically put us on the path to larger integers at lower word sizes. Additionally, MNum can act as a stand-in for a predetermined value for other instructions, again opening up some integer growth options.


wo: Word size

A few things have occurred to me regarding the WORDSIZE instruction in wo. Namely, that changing word size in the middle of a program could be entirely unpredictable – my first thought would be to break every word out into an array before interpreting (aside from the WORDSIZE instruction itself), but that would be impossible – the stack would necessarily have to be computed before WORDSIZE could execute. Even before this, I was wondering if I should really prioritize it so low in the instruction set, or if it just turns into an abuse of a reduced instruction set claim.