Devine Lu Linvega neauoire

Higher-Order Company: Towards an Optimal Computer

What is the true nature of computation?

A hundred years ago, humanity answered that very question, twice. In 1936, Alan invented the Turing Machine, which, highly inspired by the mechanical trend of the 20th century, distillated the common components of early computers into a single universal machine that, despite its simplicity, was capable of performing every computation conceivable. From simple numerical calculations to entire

Solving SAT via interaction net superpositions

I've recently been amazed, if not mind-blown, by how a very simple, "one-line" SAT solver on Interaction Nets can outperform brute-force by orders of magnitude by exploiting "superposed booleans" and optimal evaluation of λ-expressions. In this brief note, I'll provide some background for you to understand how this works, and then I'll present a simple code you can run in your own computer to observe and replicate this effect. Note this is a new observation, so I know little about how this algorithm behaves asymptotically, but I find it quite

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

Concurrency vs Parallelism, in table form

Concurrency is a system-structuring mechanism, parallelism is a resource. (ref)

There's an important distinction between "parallelism" as a resource, and "parallel execution". The two are often confused, but they are in fact distinct. The key separator is "concurrency":

	no parallelism	has parallelism
no concurrency	sequential execution	sequential execution †
has concurrency	concurrent execution ‡	parallel execution

This project is a tiny compiler for a very simple language consisting of boolean expression.

The language has two constants: 1 for true and 0 for false, and 4 logic gates: ! (not), & (and), | (or), and ^ (xor).

It can also use parentheses to manage priorities.

Here is its grammar in BNF format:

expr ::= "0" | "1"

	( artwork )

	\|00 @System [ &vector $2 &pad $6 &r $2 &g $2 &b $2 &debug $1 &halt $1 ]
	\|10 @Console [ &vector $2 &read $1 &pad $5 &write $1 &error $1 ]
	\|20 @Screen [ &vector $2 &width $2 &height $2 &auto $1 &pad $1 &x $2 &y $2 &addr $2 &pixel $1 &sprite $1 ]
	\|c0 @DateTime [ &year $2 &month $1 &day $1 &hour $1 &minute $1 &second $1 &dotw $1 &doty $2 &isdst $1 ]

	\|0000
	@framecount $1
	%MOD { DUP2 DIV MUL SUB } ( a b -- a%b )

	( main method for testing )
	\|0100
	#1234 #0001 ;testcases JSR2
	#0000 #0431 ;testcases JSR2
	#0039 #0003 ;testcases JSR2
	#9321 #ffff ;testcases JSR2
	#ffff #9321 ;testcases JSR2
	#ffff #ffff ;testcases JSR2
	#7654 #8000 ;testcases JSR2
	#8000 #0001 ;testcases JSR2

	from PIL import Image, ImageDraw

	sprite_data = bytes.fromhex('''
	00 00 3c 06 1c 06 3c 00 00 7f c3 f9 e3 f9 c3 ff
	00 00 68 2c 78 2c 34 00 00 fe ff ff ff ff ff ff
	00 01 19 07 0f 1f 07 0f ff ff e7 fb fd fe ff ff
	00 80 f0 e0 c0 f0 f8 f8 ff ff ff ff ff ff 7f 7f
	0f 0e 0c 00 80 ff ff 7f ff ff ff ff 7f 00 00 00
	e8 e0 e0 60 01 ff ff fe 7f ff ff ff fe 00 00 00
	''')

	% bouncing balls

	-initialization(main).

	main :-
	poke(0x4c00, [0x3c, 0x7e, 0xff, 0xff, 0xff, 0xff, 0x7e, 0x3c], D1),
	set_colors(0x0ce9, 0x01c0, 0x0ce5, D2),
	start(D1, D2).

	start([], []) :-

	( maze.tal )
	( )
	( mazes generated by randomized depth-first search )
	( press any key to generate a new maze )
	( )
	( generator uses a simple 16-bit xorshift RNG )
	( based on http://b2d-f9r.blogspot.com/2010/08/16-bit-xorshift-rng-now-with-more.html )

	%DEBUG { #ff #0e DEO }
	%<<5 { #50 SFT2 }