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.)
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.
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..."?
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..."?
> 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. Nowadays all desktop or server class CPUs support 8, 16, 32 and 64-bit integers. And they all have at least 10 general purpose registers. 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.
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.
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.
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.
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!
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.
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.)
Hal Finney wrote a BASIC interpreter for the Mattel Intellivision in about 2K of ROM.
Of course, Hal was a genius.
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.
If anybody wants to take a look https://github.com/shikaan/osle
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..."?
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..."?
> 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. Nowadays all desktop or server class CPUs support 8, 16, 32 and 64-bit integers. And they all have at least 10 general purpose registers. 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.
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.
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.
"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)
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.
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.
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.
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!
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.
I recommend parent's ioccc gem https://www.ioccc.org/2012/tromp/
This was such an enjoyable read. I’ve been a bit meh on software development recently and this really re-piqued some old interests.
Little Languages by Jon Bentley - https://news.ycombinator.com/item?id=40989069
Constructing Language Processors for Little Languages by Randy Kaplan - https://www.amazon.com/dp/0471597538?lv=shuf&channelId=500&p...
https://t3x.org
Also, JimTCL.
That's a very interesting website with a lot of info.
Thanks for sharing.