I have written some useful small programs in uxn, such as: hex decoder in 39 bytes (which handles optional spaces and line breaks, uppercase and lowercase, etc), a program to convert JSON to NDJSON in 125 bytes, a program to convert DER to a subset of TER in 220 bytes, BLAKE2s in 1024 bytes (although some of it is padding for alignment, which is why it comes out to exactly 1024), a card game (including graphics, sound effects, fonts, scoring, etc) in 1853 bytes, etc. (These do not always check for errors (although the card game does check that you had made a valid move), which is one of the things that makes them short; since you might want such things sometimes that makes other programs longer, and this is not specific to uxn or to programs I wrote.) Other people might have also done.
The description of uxn and varvara are also small and might need only two pages (I did not write it).
I also remember reading in a book that someone made a game on Atari in 2 kilobytes, and described how they could make it fit (by making the map symmetric, etc), which was rejected because they had 4 kilobyte cartridges by then. (The article in this submission also links to a different game that (probably) someone else made in 2 kilobytes, but this time with JavaScript and HTML. Atari and uxn/varvara are much simpler systems than HTML/JavaScript, though.)
WalterBright
Hal Finney wrote a BASIC interpreter for the Mattel Intellivision in about 2K of ROM.
Of course, Hal was a genius.
Skwid
uxntal and varvara bring me such joy, it's that perfect complexity where everything feels like a fun puzzle you can approach one step at a time.
The first time I saw it years back I was skeptical. As foremost a hardware guy I saw instructions in transistor count and gate delay, all that spaffed away on 16x16 multiply and you couldn't spare one flip flop for an overflow flag? Preposterous!
But the software already written was cool enough to convince me it was worth emulating, and once you've got an emulator you may as well write some software. A few short programs and I was in love.
It's not about running code efficiently, it's about making it fun to write efficient code.
No sharp edges, no corner cases, generally minimal machine state. The cognitive load is so much smaller than any real world assembly I've used.
I didn't mean to write such a lot of meandering offtopic fluff, but damn, I just love that little guy
( ⊖-w-⊖)
Great read (: This is precisely how I learn, even though these days it all feels a little futile.
The other part for me is working within tight constraints. A couple of years back I made an Operating System that fits a bootloader (I was low-key hoping to find in the list :P) Not really golfing but surely a good exercise in playing within constraints.
"An honorable mention must be made here for SNOBOL, which is kind of like assembly language both for the rigid syntactic reasons listed above and also because it presents a similar control flow challenge. Like a CPU, it only understands jumps and call/return."
"So how about something that is both small and simple and doesn't require a blood sacrifice?
I think the Lua programming language fits the bill."
For me, spitbol is smaller binary than lua/luajit and faster than lua when, e.g., printing 5001 strings containing incremented variable using a computer with below average specifications^1
* 1.spt
x = 0
a output = "http://example.com/" x
x = x + 20
le(x,1000000) :f(end)s(a)
end
-- 1.lua
local x=0
while x<=1000000 do
print("http:///example.com/"..x)
x=x+20
end
busybox time luajit 1.lua >/dev/null
busybox time spitbol 1.spt >/dev/null
busybox time lua 1.lua >/dev/null
That's a very interesting website with a lot of info.
Thanks for sharing.
bryancoxwell
This was such an enjoyable read. I’ve been a bit meh on software development recently and this really re-piqued some old interests.
abainbridge
I'm interested in making a really simple compiled scripting language. I don't understand why most scripting languages compile to bytecode and then interpret that. This requires the following steps:
1: Design a bytecode. 2: Write a compiler. 3: Write an interpreter.
It seems like it would be simpler to not bother with 1 and 3 and instead use machine code as the bytecode. A side benefit is that programs will run faster.
I think it is easy to generate machine code for x86_64, ARM64 and risvc64, as long as you don't mind it being 3x larger and slower than an optimizing compiler would generate. It ought to be easy because it is possible to only target the common subset of features these architectures support.
I made a start, https://github.com/abainbridge/mortar, but haven't got much past being able to compile and run a Fibonacci sequence generator. I have no experience with language design or compiler implementation. I was somewhat gobsmacked when the fib generator ran 380x faster than an almost identical looking Python program.
Any comments or suggestions, including, "that's a bad idea, you will fail because of XYZ", or, "save yourself the effort, here's one I wrote earlier..."?
mrkeen
I think the viewpoint that your're missing is: how do I make sure the machine code means the same thing as the source code?
is probably a non-starter, so compiler writers tend to attack the problem by breaking it down into lots of passes.
Parsing into an AST is obviously the first, then you might opt into other passes, like type-checking, handling closures, simplifying into some kind of IR, and finally generating code. Each of those stages can be effectively unit-tested (except maybe the last). If you make a mistake in parsing (e.g. mistaking a statement for an expression), you don't want to have to catch that error by inspecting machine code. It's nice if each pass can be easily tested. And one simple way to test these things is to write an interpreter for each pass (mostly because you get to enjoy the facilities of whatever host language you're writing in). Then you can start saying things like "for all inputs, interpreting the AST gives the same result as interpreting the type-checked-AST, gives the same results as interpreting the closured-AST, gives the same results as interpreting the list of IR instructions."
You mention "It ought to be easy because it is possible to only target the common subset of features these architectures support." <- That's your IR right there!
Once you have an IR that looks close enough to the target machine language, it shouldn't be too hard to translate the final step. Or just use LLVM.
I noticed in your code that you're using C, and really there's no need. Languages don't need to be stacked in a hierarchy (e.g. Clojure on top of the JVM which is C++ which compiles to asm). The compiler can be any language, because it only needs to be able to take in source code and spit out bytes.
abainbridge
> I think the viewpoint that your're missing is: how do I make sure the machine code means the same thing as the source code?
Ooo, no. I already have an AST. When writing the code gen for a node type in the AST, I normally start by typing a few lines of C into godbolt that exercises the same kind of thing represented by the node type. I try a few different compilers and optimization settings and look at what gets generated. I pick an approach that looks simple and good enough. Then I ask an AI to assemble the instructions I see the compilers using. I like to ask an AI to do this because it will explain what all the bits do in the instruction encoding and it is less error prone at reading the ISA docs than I am. The description from the AI might prompt me to ask things like, "what if the jump target doesn't fit in the 32-bit immediate" etc.
All I was claiming was that this is easier than generating code for a byte code of my invention, partly because I don't have to invent a byte code and partly because I can use existing tools to help, eg disassemblers/debuggers to check my output or compilers to give me ideas on how to convert C-like statements into machine code.
I don't have any IR at the moment. I'll have a think about what benefits that might bring.
The reason I posted my project under this top level thread is because I'm interested in Small Programs and Languages. My experiment is in what I can remove from a language implementation to make it simpler. Adding a dependency on LLVM is the opposite of what I had in mind :-)
There are many reasons I'm writing it in C but mainly because I like C.
ozgrakkurt
I would recommend reading a book about programing languages, most of those explain this imo.
What I understand from that is, byte code is portable while machine code isn't.
So you can write a byte code interpreter in C and you have fully cross platform toolchain.
It is also supposedly easier to generate bytecode compared to generating something like x86_64 machine code or assembly.
Imo what matters more is the execution and not the idea anyway so you shouldn't care about this:
> Any comments or suggestions, including, "that's a bad idea, you will fail because of XYZ", or, "save yourself the effort, here's one I wrote earlier..."?
abainbridge
> What I understand from that is, byte code is portable while machine code isn't.
This is an area I want to explore. It seems to me that it is less true than it used to be. x86_32 was the last significant architecture that made things hard. Now we can ignore that. All desktop or server class CPUs support 8, 16, 32 and 64-bit integers. And they all have at least 10 general purpose registers. They all have a sensible set of memory access modes. As a result, the same code generator works for them all. As it stands, my code generator calls functions like emit_indexed_load, emit_conditional_jump etc. There are currently 26 of those functions and they're all trivial.
So far I have only implemented them for x86_64 machine code output. But writing versions that output ARM64 or risvc doesn't seem hard. I expect I'll find small problems which will cause me to have to tweak the set of CPU features my code gen depends on.
As for generating bytecode being easier than x86_64 machine code, I disagree. There are lots of tools for validating x86_64 machine code (ie disassemblers). There aren't any for a bytecode I might invent. And I can ask an AI how to generate x86_64 machine code to do an indexed load. I immediately get the answer. I don't have to think about how to make an efficient bytecode encoding.
The hardest thing I've encountered so far is getting the ABI right so that my compiled code can call existing functions (eg libc). But I'd have to do that even if I was using an interpreter.
norir
It is straightforward to pick an isa and then design an ir that closely mirrors it. Codegen from the ir the original isa is dead simple. Other isas are also straightforward except that it may be necessary to introduce virtual registers and implement certain instructions as multiple instructions if there isn't a 1:1 correspondence.
I think the op is far too pessimistic about code size and performance. TCC for example produces terrible machine code but I rarely see 3x size or performance diffs compared to clang (at least for the kinds of programs I tend to write). It is also very easy to find edge cases where the clang optimizer makes heinously bad decisions. In one trivial example, I've written a program that has a helper function with no arguments that simply prints "Hello, world!" and a main function that calls the helper 1 million times. With optimizations, the version of clang on my computer inlined the helper call 1 million times, which made the binary I believe 4-6x bigger than -O0. With -O0, I believe compilation took 6 seconds compared to something like 15 minutes with -O2 (tcc took maybe 250ms and produced a binary that I think was about 2x the size of gcc -O0). All that is to say, I have less faith in the quality of optimizing compilers than most.
abainbridge
> I think the op is far too pessimistic about code size and performance
My code gen is definitely worse than TCC! But I think modern CPUs see all my redundant register-register moves and just treat them as a no-ops. Probably performance isn't much worse than TCC. But currently I can hardly compile a program complex enough for a meaningful comparison to be made.
raddan
You should do it. But I recommend a book or two on compiler design. There are useful techniques (like SSA) that simplify program analysis if you decide you want to dip your toes into adding optimizer passes. Building stuff yourself, the hard way, is definitely the best way to learn. I wish I had unbounded time to do it…
Edit: I like the Appel compiler book. One of my students enjoyed “Writing a C compiler” by Nora Sandler. There are also a number of classic compiler books that feel more relevant once you are deep in the weeds.
abainbridge
I didn't know about the Appel book. I'll take a look. Thanks.
I feel like the way we write about compiler design could be reduced in complexity too. I read the blog posts by Nora Sandler and they did a great job compared to "the Dragon book" (confusing now because her book has a dragon on the front too). But we still ought to replace phrases like "lexical analysis" with "character grouping" (credit to Sam H Smith for forcing that one into my brain).
rramadass
You may find the following useful for some necessary background and then leading to implementation;
For code generation, you can just walk the AST and either;
1) Emit the text of the assembly code for x86_64/ARM64/RISC-V and then leave the rest to the system assembler.
Or,
2) If you want to be even more professional, emit text of LLVM IR and then leverage its complete toolchain.
From your github i see you mention the "MicroC" subset of C language. Maybe follow the above but with the syntax/grammar of MicroC for your implementation.
fxj
"Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
Philip Greenspun (1993)
abainbridge
Hah. I won't pretend I'm not motivated by the same forces as many lost souls before me. But if my language turns out anything like Lisp, I'd be upset.
fxj
hehe! i didnt want to demotivate you in trying. I was in the same situation and I learned a lot doing it. Go for it.
lelanthran
I have used tcc as a scripting language in the past. I expect that if your shell script catches the compilation, that sort of approach will satisfy your requirements, even if tcc itself does not.
abainbridge
TCC is partly what motivated me to try. But I want to get closer to lower the Kolmogorov Complexity. I'm happy to sacrifice C compatibility. In fact I'm happy to sacrifice much of the power of C. And I'd be happier with code that was somewhat slower.
And the original TCC code is not easy to understand. It is a lot cleverer than I can cope with!
thelisu
Some high level features of the language might be more complicated to implement in assembly than in bytecode. The latter can have instructions more closely matching the language's features.
Similarly, it is quite rare to compile programs directly to assembly. In general, you have some intermediate representations... which can closely resemble some bytecode. The reason is the same: compiling to a higher-level IR is simpler than going directly to assembly.
longor1996
When it comes to writing small languages/interpreters, it is obligatory to mention "Crafting Interpreters" by Robert Nystrom, so here we go!
A language that was designed to make Kolmogorov complexity concrete is Binary Lambda Calculus, a self interpreter of which takes only 168 bits (21 bytes). Unlike the Lisp self interpreter in the article, it operates on a bitstream and thus has to include a parser.
Says more about the very real limitations of the human mind than anything else.
With an LLM, you can get a good-sized code base to converge on bug-free. The size of the code base your human mind can comprehend on its own is very small, so tiny pieces of code that do something interesting or useful seem beautiful and phenomenal to us. LLMs bust through that limitation and are capable of comprehending far more at one time than we are. Ultimately, human comprehensibility of code will no longer matter, and we will soon be guiding the evolution of vast towers of complexity that Just Work because they've been meticulously checked by machine at all but the highest levels of abstraction.
Where LLMs currently fall down is nuance, things like "business context" and what information resources users actually need.
The description of uxn and varvara are also small and might need only two pages (I did not write it).
I also remember reading in a book that someone made a game on Atari in 2 kilobytes, and described how they could make it fit (by making the map symmetric, etc), which was rejected because they had 4 kilobyte cartridges by then. (The article in this submission also links to a different game that (probably) someone else made in 2 kilobytes, but this time with JavaScript and HTML. Atari and uxn/varvara are much simpler systems than HTML/JavaScript, though.)
Of course, Hal was a genius.
The first time I saw it years back I was skeptical. As foremost a hardware guy I saw instructions in transistor count and gate delay, all that spaffed away on 16x16 multiply and you couldn't spare one flip flop for an overflow flag? Preposterous!
But the software already written was cool enough to convince me it was worth emulating, and once you've got an emulator you may as well write some software. A few short programs and I was in love. It's not about running code efficiently, it's about making it fun to write efficient code.
No sharp edges, no corner cases, generally minimal machine state. The cognitive load is so much smaller than any real world assembly I've used.
I didn't mean to write such a lot of meandering offtopic fluff, but damn, I just love that little guy ( ⊖-w-⊖)
Constructing Language Processors for Little Languages by Randy Kaplan - https://www.amazon.com/dp/0471597538?lv=shuf&channelId=500&p...
The other part for me is working within tight constraints. A couple of years back I made an Operating System that fits a bootloader (I was low-key hoping to find in the list :P) Not really golfing but surely a good exercise in playing within constraints.
If anybody wants to take a look https://github.com/shikaan/osle
"So how about something that is both small and simple and doesn't require a blood sacrifice?
I think the Lua programming language fits the bill."
For me, spitbol is smaller binary than lua/luajit and faster than lua when, e.g., printing 5001 strings containing incremented variable using a computer with below average specifications^1
1. For example, the blog author has been writing assembly on an ASUS eeePC 701: https://ratfactor.com/assembly-nights
luajit 2.1.1753364724 666.7K static binary (musl) amd64spitbol 4.0f 175.4K static binary (musl) amd64: 2.67x slower than luajit, 3.8x smaller than luajit
lua 5.5.0 362.6K static binary (musl) amd64: 2.38x slower than spitbol, 2.07x larger than spitbol
lua 5.3.6 255.0K static binary (musl) amd64: 2.63x slower than spitbol, 1.45x larger than spitbol
Also, JimTCL.
Thanks for sharing.
1: Design a bytecode. 2: Write a compiler. 3: Write an interpreter.
It seems like it would be simpler to not bother with 1 and 3 and instead use machine code as the bytecode. A side benefit is that programs will run faster.
I think it is easy to generate machine code for x86_64, ARM64 and risvc64, as long as you don't mind it being 3x larger and slower than an optimizing compiler would generate. It ought to be easy because it is possible to only target the common subset of features these architectures support.
I made a start, https://github.com/abainbridge/mortar, but haven't got much past being able to compile and run a Fibonacci sequence generator. I have no experience with language design or compiler implementation. I was somewhat gobsmacked when the fib generator ran 380x faster than an almost identical looking Python program.
Any comments or suggestions, including, "that's a bad idea, you will fail because of XYZ", or, "save yourself the effort, here's one I wrote earlier..."?
Trying to one-shot 'print "hello world";' into
is probably a non-starter, so compiler writers tend to attack the problem by breaking it down into lots of passes.Parsing into an AST is obviously the first, then you might opt into other passes, like type-checking, handling closures, simplifying into some kind of IR, and finally generating code. Each of those stages can be effectively unit-tested (except maybe the last). If you make a mistake in parsing (e.g. mistaking a statement for an expression), you don't want to have to catch that error by inspecting machine code. It's nice if each pass can be easily tested. And one simple way to test these things is to write an interpreter for each pass (mostly because you get to enjoy the facilities of whatever host language you're writing in). Then you can start saying things like "for all inputs, interpreting the AST gives the same result as interpreting the type-checked-AST, gives the same results as interpreting the closured-AST, gives the same results as interpreting the list of IR instructions."
You mention "It ought to be easy because it is possible to only target the common subset of features these architectures support." <- That's your IR right there!
Once you have an IR that looks close enough to the target machine language, it shouldn't be too hard to translate the final step. Or just use LLVM.
I noticed in your code that you're using C, and really there's no need. Languages don't need to be stacked in a hierarchy (e.g. Clojure on top of the JVM which is C++ which compiles to asm). The compiler can be any language, because it only needs to be able to take in source code and spit out bytes.
Ooo, no. I already have an AST. When writing the code gen for a node type in the AST, I normally start by typing a few lines of C into godbolt that exercises the same kind of thing represented by the node type. I try a few different compilers and optimization settings and look at what gets generated. I pick an approach that looks simple and good enough. Then I ask an AI to assemble the instructions I see the compilers using. I like to ask an AI to do this because it will explain what all the bits do in the instruction encoding and it is less error prone at reading the ISA docs than I am. The description from the AI might prompt me to ask things like, "what if the jump target doesn't fit in the 32-bit immediate" etc.
All I was claiming was that this is easier than generating code for a byte code of my invention, partly because I don't have to invent a byte code and partly because I can use existing tools to help, eg disassemblers/debuggers to check my output or compilers to give me ideas on how to convert C-like statements into machine code.
I don't have any IR at the moment. I'll have a think about what benefits that might bring.
The reason I posted my project under this top level thread is because I'm interested in Small Programs and Languages. My experiment is in what I can remove from a language implementation to make it simpler. Adding a dependency on LLVM is the opposite of what I had in mind :-)
There are many reasons I'm writing it in C but mainly because I like C.
What I understand from that is, byte code is portable while machine code isn't.
So you can write a byte code interpreter in C and you have fully cross platform toolchain.
It is also supposedly easier to generate bytecode compared to generating something like x86_64 machine code or assembly.
Imo what matters more is the execution and not the idea anyway so you shouldn't care about this:
> Any comments or suggestions, including, "that's a bad idea, you will fail because of XYZ", or, "save yourself the effort, here's one I wrote earlier..."?
This is an area I want to explore. It seems to me that it is less true than it used to be. x86_32 was the last significant architecture that made things hard. Now we can ignore that. All desktop or server class CPUs support 8, 16, 32 and 64-bit integers. And they all have at least 10 general purpose registers. They all have a sensible set of memory access modes. As a result, the same code generator works for them all. As it stands, my code generator calls functions like emit_indexed_load, emit_conditional_jump etc. There are currently 26 of those functions and they're all trivial.
So far I have only implemented them for x86_64 machine code output. But writing versions that output ARM64 or risvc doesn't seem hard. I expect I'll find small problems which will cause me to have to tweak the set of CPU features my code gen depends on.
As for generating bytecode being easier than x86_64 machine code, I disagree. There are lots of tools for validating x86_64 machine code (ie disassemblers). There aren't any for a bytecode I might invent. And I can ask an AI how to generate x86_64 machine code to do an indexed load. I immediately get the answer. I don't have to think about how to make an efficient bytecode encoding.
The hardest thing I've encountered so far is getting the ABI right so that my compiled code can call existing functions (eg libc). But I'd have to do that even if I was using an interpreter.
I think the op is far too pessimistic about code size and performance. TCC for example produces terrible machine code but I rarely see 3x size or performance diffs compared to clang (at least for the kinds of programs I tend to write). It is also very easy to find edge cases where the clang optimizer makes heinously bad decisions. In one trivial example, I've written a program that has a helper function with no arguments that simply prints "Hello, world!" and a main function that calls the helper 1 million times. With optimizations, the version of clang on my computer inlined the helper call 1 million times, which made the binary I believe 4-6x bigger than -O0. With -O0, I believe compilation took 6 seconds compared to something like 15 minutes with -O2 (tcc took maybe 250ms and produced a binary that I think was about 2x the size of gcc -O0). All that is to say, I have less faith in the quality of optimizing compilers than most.
My code gen is definitely worse than TCC! But I think modern CPUs see all my redundant register-register moves and just treat them as a no-ops. Probably performance isn't much worse than TCC. But currently I can hardly compile a program complex enough for a meaningful comparison to be made.
Edit: I like the Appel compiler book. One of my students enjoyed “Writing a C compiler” by Nora Sandler. There are also a number of classic compiler books that feel more relevant once you are deep in the weeds.
I feel like the way we write about compiler design could be reduced in complexity too. I read the blog posts by Nora Sandler and they did a great job compared to "the Dragon book" (confusing now because her book has a dragon on the front too). But we still ought to replace phrases like "lexical analysis" with "character grouping" (credit to Sam H Smith for forcing that one into my brain).
Implementing Programming Languages: An Introduction to Compilers and Interpreters by Aarne Ranta (<150 pages!) - https://www.grammaticalframework.org/ipl-book/
The above book uses the BNF Converter Tool - https://bnfc.digitalgrammars.com/
BNF Converter Tutorial - https://bnfc.digitalgrammars.com/tutorial/bnfc-tutorial.html
For code generation, you can just walk the AST and either;
1) Emit the text of the assembly code for x86_64/ARM64/RISC-V and then leave the rest to the system assembler.
Or,
2) If you want to be even more professional, emit text of LLVM IR and then leverage its complete toolchain.
From your github i see you mention the "MicroC" subset of C language. Maybe follow the above but with the syntax/grammar of MicroC for your implementation.
Philip Greenspun (1993)
And the original TCC code is not easy to understand. It is a lot cleverer than I can cope with!
Similarly, it is quite rare to compile programs directly to assembly. In general, you have some intermediate representations... which can closely resemble some bytecode. The reason is the same: compiling to a higher-level IR is simpler than going directly to assembly.
https://craftinginterpreters.com/
With an LLM, you can get a good-sized code base to converge on bug-free. The size of the code base your human mind can comprehend on its own is very small, so tiny pieces of code that do something interesting or useful seem beautiful and phenomenal to us. LLMs bust through that limitation and are capable of comprehending far more at one time than we are. Ultimately, human comprehensibility of code will no longer matter, and we will soon be guiding the evolution of vast towers of complexity that Just Work because they've been meticulously checked by machine at all but the highest levels of abstraction.
Where LLMs currently fall down is nuance, things like "business context" and what information resources users actually need.