(2023-04-27) Brainfuck running in VTL-2 running in AWK. Why not?
----------------------------------------------------------------
Brainfuck is pure art. VTL-2 is pure constraint-driven engineering. Yet I
couldn't find a single BF interpreter in VTL-2. Not even on the Rosetta
Code. Probably because BF was created much later than VTL-2, in 1993, when
almost nobody gave a damn about VTL and even about Tiny BASIC already. But
now, in 2023, here it is - bf.vtl that I was able to run with lvtl.awk which
in turn can run under the "busybox awk" command. I deliberately avoided
using any bitwise operators in the bf.vtl code (although they might make it
more efficient in some places) to make it portable to non-LVTL
implementations. So, anyone who has access to any VTL-2 version should be
able to pick it up from my hoi.st downloads and try it out.
In case you've stumbled upon my phlog by navigating here from some unexpected
place and still don't know what Brainfuck is, well, it's a programming
language operating on an unbounded (although practically finite) virtual
tape of integers (typically unsigned bytes from 0 to 255) that only has 8
single-character instructions and ignores any other characters as comments.
In the canonical BF, these instructions are:
+ increment current cell
- decrement current cell
< move the cell pointer to the previous cell
> move the cell pointer to the next cell
, read a character from stdin and save its code to the current cell
write the current cell as a character to stdout
[ jump past the matching ] if the cell at the pointer is 0
] jump back to the cell after the matching [ if the cell at the pointer is
non-zero
That's it. These instructions (that, by the way, can be 3-bit-encoded in a
straightforward manner or, for instance, remapped onto phone keypad digits,
oh shit, why did I think of this...) are everything that's required to
construct a Turing-complete language. Since its inception in 1993, Brainfuck
gained really huge following, spawning countless variations, improvements
and a whole "esoteric programming" subculture. But this very canonical
variant of BF remains the most popular esolang to this very day. I think
it's safe to say it's more popular now than VTL-2 itself, which is not an
esolang but, as I said, a fine piece of constraint-driven engineering. Yes,
I imagine that a BF interpreter for Altair machines could weigh much less
than 768 bytes of VTL/VTL-2, but how useful would it be with programs that
long and the RAM limit far less than the 30000 bytes of recommended minimum
for BF? And that's only operating RAM (the virtual number tape size), not
counting the length of the program itself. I guess, when VTL was a
necessity, it was too early for something like BF to even appear on the
scene. But now, when RAM is usually not a problem even for the most embedded
tech, we have a perfect opportunity to explore this alternative history
timeline and see how an interpreter of the most popular esoteric programming
language would look when written in the tiniest non-esoteric one. That's how
my first VTL-2 project began.
Yes, I finally started writing something new _in_ VTL-2, not just
interpreters _of_ VTL-2 in other languages. And you know what... I really
like it. In fact, you get used to this weird assignment-driven syntax with
strictly-LTR expressions so quickly that it might even become baffling to
you how every other high-level language didn't implement this and went with
more verbose expression/statement syntax modeled after BASIC. And yes, I
have the guts to say VTL-2 is pretty high-level and abstracts over a lot of
machine-specific stuff, although it also requires you to be precise in your
line number calculations. By the way, the whole idea of using #=0 as nop is
indeed very clever and provides a concise way to do all branching and loops
and everything. You just need to be good at math. Now I guess that BASIC,
its expression model and all its IF/ELSE/FOR/WHILE/UNTIL had been invented
for those who weren't. No wonder that later BASIC generations ditched line
numbering altogether.
But I digress, let's go back to my BF-VTL. Just like with implementing BF in
any other language, the main culprit here were the [ and ] instructions.
Because, as I already had written somewhere in this phlog, I hate
parentheses matching, it slows everything down, especially here where you
have to do code lookahead. Because if we imagine our data as a tape, we can
also imagine our BF code as another tape, and every time the corresponding
condition is triggered at one of these brackets, we have to fast-forward or
rewind this tape to the matching bracket, stopping at intermediate brackets
to increase/decrease the tracking counter. But here, brackets and their
matching are a paramount part of the language, so they had to be implemented
appropriately. At first, I just wanted to use a single subroutine that would
be parameterized for each of the two cases and called from the instruction
subroutines. This would allow to shorten their code significantly. But then,
I remembered the limitation that we only have a single ! variable that
already was being used, so I had to improvise and combine these two routines
into one that returned directly to the original processing loop.
Nevertheless, overall bf.vtl SLOC count turned out to be under 75 lines. Not
bad for such a Very Tiny Language, don't you think?
Of course, when run in LVTL-W, any program in BF-VTL runs extremely slowly.
Because that's a triple interpretation layer. But the point is, it runs. And
runs correctly. It's a good benchmark of both AWK and VTL-2. For example, on
busybox awk, I instantly got a segfault because the interpreter couldn't
allocate memory for all the operations. So, with trial and error, I found
out that I had to tweak the L variable in line 12 and also delete lines 13
to 18 to be able to run my Hello World. Still, on the second run, I could
already see how much memory was leaking. Maybe AWK is not the right tool for
the job, but it's a lot of fun. No issues on GAWK though, maybe it has
proper GC. But, for some factorial code like this one...
..you really want to use the compiled VTL-2 versions to run BF-VTL. By the
way, from now on, all existing LVTL versions except the initial A prototype
(LVTL-O, LVTL-R and LVTL-W) are distributed in a single sharball,
lvtl.shar.gz, and bf.vtl is included in the examples directory of that
sharball.
And yes, since I already mentioned phone keypad mapping... Here's how I'd do
this: