Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bytecode VMs in surprising places (2024)

dubroy.com

Post reply on HN
Print view View original

11–20 of 74 posts

Re: Bytecode VMs in surprising places (2024)

#12

Post by anthk »

pjc50 wrote: post #6
pratikdeoghare wrote: post #4

There is one in golang regular expressions https://swtch.com/~rsc/regexp/regexp2.html I guess that is why you say re.Compile.

All regular expressions are deterministic final automata https://en.wikipedia.org/wiki/Deterministic_finite_automaton (finally, a use for my CS course); the extent to which that counts as a virtual machine varies. Some of the regex syntaxes extend it in ways which don't fit in a DFA and do count as a VM; Perl-compatible RE used to be popular (e.g. in Exim).

Inded:

https://wiki.xxiivv.com/site/rewriting.html

Re: Bytecode VMs in surprising places (2024)

#13

Post by anthk »

yt-dlp's jsinterp.py

https://jxself.org/compiling-the-trap.shtml

I've got subleq+eforth (https://github.com/howerj/muxleq) running in JS which is dead simple to do. No input but I could output ASCII mapping values to an array.

https://esolangs.org/wiki/Subleq

So, yes. yt-dlp runs propietary Youtube JS code defying the original purpose.

Re: Bytecode VMs in surprising places (2024)

#14

Post by pjc50 »

sureglymop wrote: post #5
pratikdeoghare wrote: post #4

There is one in golang regular expressions https://swtch.com/~rsc/regexp/regexp2.html I guess that is why you say re.Compile.

Interesting. Not that surprising that it works like this. But isn't it a little surprising that things like regexes, printf syntax and other DSLs aren't mostly handled and parsed at compile time in 2026?

Kind of language-dependent since regexes are normally specified as strings and most languages are pretty weak at "run this code at compile time". One of the things Rust users are fond of.

C# is in the middle on this one, where specific features get compile-time support and regex is one of them: https://www.devleader.ca/2026/05/03/c-regex-performance-gene...

I have also built a C# source generator myself (XML parser generator), but the developer experience is a bit of a hill to climb compared to what it could be.

Re: Bytecode VMs in surprising places (2024)

#17

Post by kqr »

rhdunn wrote: post #8
pratikdeoghare wrote: post #4

There is one in golang regular expressions https://swtch.com/~rsc/regexp/regexp2.html I guess that is why you say re.Compile.

That goes back to Ken Thompson's NFA regex interpreter from 1968 [1], [2], [3]. Note: that whole regex series by Russ Cox [4] is great. [1] https://dl.acm.org/doi/10.1145/363347.363387 -- Programming Techniques: Regular expression search algorithm [2] https://swtch.com/~rsc/regexp/regexp1.html -- Regular Expression Matching Can Be Simple And Fast [3] https://swtch.com/~rsc/regexp/regexp2.html -- Regular Expression Ma…

I second the Russ Cox recommendation. I read that ages ago and that was what made me realise some theory could actually be useful in practice.

Re: Bytecode VMs in surprising places (2024)

#19

Post by DonHopkins »

chirsz wrote: post #16

SBus peripherals use the Forth language in their PROMs to initialize themselves[1]. [1] https://docs.oracle.com/cd/E19957-01/802-3239-10/sbusandfc.h...

Good call! (Whether it's a directly threaded, indirectly threaded, subroutine threaded, token threaded, Huffman threaded, or string threaded call.)

https://en.wikipedia.org/wiki/Threaded_code#Token_threading

Mitch Bradley created OpenFirmware. It started at Sun as OpenBoot (informally "SunForth") on the SPARCstation 1 in 1989, was standardized as IEEE 1275-1994, and was renamed OpenFirmware at that time. Its lineage runs back through Mitch's earlier Forthmacs (Bradley Forthware, early 80s), which ran on 68k Macs, Sun-2/3, Atari ST, and Amiga. Mitch credits Henry Laxen and Michael Perry's F83 and Glen Haydon's MVP-Forth as the public-domain ancestors.

The metacompiler can target many platforms, word sizes, CPUs, and threading models, and produce stripped ROMable images. It can build the kernel as direct-threaded (DTC), indirect-threaded (ITC), subroutine-threaded (STC), or token-threaded (TTC), with 16, 32, or 64 bit cells. Shipping kernels are DTC native code with cell-sized xt pointers: 32 bit on the original SPARC and PowerPC machines, 64 bit on modern PPC64, SPARC64, and ARM64 builds.

Peripheral expansion cards ship a separate, portable, variable-byte token format called FCode. The kernel interprets FCode at boot/probe time and recompiles it on the fly into the live native dictionary. After probe, FCode-loaded drivers run as ordinary native Forth words. That two-stage design (fast native runtime, portable FCode transport) is what let Sun ship one card PROM image that worked across CPU generations.

https://github.com/MitchBradley

https://github.com/MitchBradley/openfirmware

FCode was designed for SBus on the SPARCstation 1, with cross-CPU portability built in. Sun's earlier and contemporary buses were not interchangeable with SBus (Sun-2 used Multibus, Sun-3 used VMEbus, the Sun386i "Roadrunner" used AT-bus), so the cross-architecture payoff arrived later, when IEEE 1275-1994 standardized OpenFirmware and PCI allowed FCode in option ROMs. After that, the same expansion-card PROM image could boot on Sun SPARC, Apple PowerPC Macs, IBM PowerPC servers (CHRP), and the OLPC XO.

Interview with Mitch Bradley (he's like the Woz of Forth):

https://web.archive.org/web/20120118132847/http://howsoftwar...

In parallel with the OpenBoot work, Mitch also developed an extremely portable C-based Forth (the public version is "C Forth 93"). It runs a switch-threaded inner interpreter over packed tokens, with configurable cell width (16, 32, or 64 bit) and configurable token width (pointer-sized by default, 16 bit with the T16 build flag for tight flash budgets), plus a small hand-rolled FFI built around a fixed-arity 12-argument marshalling trampoline driven by a format string. It is now the embedded variant used in OLPC's OpenFirmware and in PlatformIO targets including RP2040, Teensy, ESP32, ESP8266, and STM32:

https://github.com/MitchBradley/cforth

OpenFirmware even has its own song:

https://www.youtube.com/watch?v=b8Wyvb9GotM

More on Mitch, OpenFirmware, and CForth:

https://news.ycombinator.com/item?id=21822840

https://news.ycombinator.com/item?id=33681531

https://news.ycombinator.com/item?id=38689282

Re: Bytecode VMs in surprising places (2024)

#20

Post by titzer »

pjc50 wrote: post #6
pratikdeoghare wrote: post #4

There is one in golang regular expressions https://swtch.com/~rsc/regexp/regexp2.html I guess that is why you say re.Compile.

All regular expressions are deterministic final automata https://en.wikipedia.org/wiki/Deterministic_finite_automaton (finally, a use for my CS course); the extent to which that counts as a virtual machine varies. Some of the regex syntaxes extend it in ways which don't fit in a DFA and do count as a VM; Perl-compatible RE used to be popular (e.g. in Exim).

It's easier to construct NFAs directly from regular expression definitions (rather than DFAs) because implementing the choice operator is easier. We can convert from NFA to DFA with worst-case exponential blowup.
Post reply on HN