Ace Stapp Oortonaut

## every-vm-tutorial-you-ever-studied-is-wrong.md

      
              5 files
            
          
              6 forks
            
          
              2 comments
            
          
              46 stars
            
          
                o11c
                / every-vm-tutorial-you-ever-studied-is-wrong.md
            
            
              Last active
              July 17, 2024 19:08
            
              
                Every VM tutorial you ever studied is wrong (and other compiler/interpreter-related knowledge)
              
          
    Note: this was originally several Reddit posts, chained and linked. But now that Reddit is dying I've finally moved them out. Sorry about the mess.

URL: https://www.reddit.com/r/ProgrammingLanguages/comments/up206c/stack_machines_for_compilers/i8ikupw/
Summary: stack-based vs register-based in general.
There are a wide variety of machines that can be described as "stack-based" or "register-based", but not all of them are practical. And there are a lot of other decisions that affect that practicality (do variables have names or only address/indexes? fixed-width or variable-width instructions? are you interpreting the bytecode (and if so, are you using machine stack frames?) or turning it into machine code? how many registers are there, and how many are special? how do you represent multiple types of variable? how many scopes are there(various kinds of global, local, member, ...)? how much effort/complexity can you afford to put into your machine? etc.)

a pure stack VM can only access the top elemen


## paren_repr.py
# I happened to be looking at some of Cranelift's code, and I noticed that their constant-time dominates()
# check was using a somewhat more ad-hoc version of a hidden gem from the data structures literature called the
# parenthesis representation for trees. As far as I know, this was invented by Jacobson in his 1989 paper
# Space-Efficient Static Trees and Graphs. I first learned about it from the slightly later paper by Munro and Raman
# called Succinct Representations of Balanced Parentheses and Static Trees. I figured I'd give it an extremely
# quick intro and then show how it leads to a (slightly better) version of Cranelift's algorithm.
#
# This parenthesis representation of trees is surprisingly versatile, but its most striking feature is that
# it lets us query the ancestor relationship between two nodes in a tree in constant time, with a few instructions.
# And the idea is extremely simple and intuitive if you just draw the right kind of picture.

## SDLblit.cpp
// This work (SDLblit.cpp, by Cory Bloyd) is free of known copyright restrictions.
// https://creativecommons.org/publicdomain/zero/1.0/
#include <SDL.h>

inline uint32_t argb(uint8_t a, uint8_t r, uint8_t g, uint8_t b) { return (a<<24) | (r << 16) | (g << 8) | (b << 0); }

int main(int argc, char *argv[]) {
    SDL_Init(SDL_INIT_VIDEO);

    SDL_Rect    screenRect = { 0,0,1024,1024 };
	# I happened to be looking at some of Cranelift's code, and I noticed that their constant-time dominates()
	# check was using a somewhat more ad-hoc version of a hidden gem from the data structures literature called the
	# parenthesis representation for trees. As far as I know, this was invented by Jacobson in his 1989 paper
	# Space-Efficient Static Trees and Graphs. I first learned about it from the slightly later paper by Munro and Raman
	# called Succinct Representations of Balanced Parentheses and Static Trees. I figured I'd give it an extremely
	# quick intro and then show how it leads to a (slightly better) version of Cranelift's algorithm.
	#
	# This parenthesis representation of trees is surprisingly versatile, but its most striking feature is that
	# it lets us query the ancestor relationship between two nodes in a tree in constant time, with a few instructions.
	# And the idea is extremely simple and intuitive if you just draw the right kind of picture.
	// This work (SDLblit.cpp, by Cory Bloyd) is free of known copyright restrictions.
	// https://creativecommons.org/publicdomain/zero/1.0/
	#include <SDL.h>

	inline uint32_t argb(uint8_t a, uint8_t r, uint8_t g, uint8_t b) { return (a<<24) \| (r << 16) \| (g << 8) \| (b << 0); }

	int main(int argc, char *argv[]) {
	SDL_Init(SDL_INIT_VIDEO);

	SDL_Rect screenRect = { 0,0,1024,1024 };