5 ms·

Trying to get an overview of which languages allow for tiny implementations of their core features. Like, max. ~10KB binary size (but preferably a few KB's). Th

Trying to get an overview of which languages allow for tiny implementations of their core features. Like, max. ~10KB binary size (but preferably a few KB's). This is assuming basic IO is trivial, like reading/writing to some memory location to get/print a character on text console. Forth is an obvious one. Basic another. There's some tiny Lisps out there. And Tcl. Any other languages that go that small?

giraffe_lady 2y ago
One thing you quickly run into with this exercise is needing to establish the boundaries around "programming language" which can be kind of fraught. For example miniKanren is tiny and is used as a DSL, but is capable of expressing any computation so does that count? Some type systems are turing complete and a naive implementation could be tiny. Is conway's game of life a programming language. You could probably strip a bunch of useful stuff out of sqlite's sql parser and get it below 10k. etc.
- samatman 2y ago
  You have to draw a line somewhere, and it's necessarily somewhat arbitrary. Mine is the size of the runtime, usually. So the Forth is the size of Lua + the 40 line script, minKanren is the size of the .scm file + the Scheme implementation, and so on. This ignores the host environment, which I think is fair: generally these will be enormously larger than they would actually have to be to support the language. I do award subjective bonus points to languages which actually have a freestanding runtime, that is, I could actually compile them and run them on a bare chip. Even then, I don't count the microcode which implements the instruction set of that chip, or the Verilog/VHDL which is needed to tape it out. Usually! ColorForth on GreenArrays gets even more bonus points, because not only is the language exceedingly compact, and freestanding, but the VLSI tool used to create the chip is also tiny to an almost unbelievable degree. So it wins some kind of prize in the special "total system complexity" category.
  - RetroTechie 2y ago
    > I do award subjective bonus points to languages which actually have a freestanding runtime, that is, I could actually compile them and run them on a bare chip. That's what I was getting at with "trivial IO": when you ignore what's needed to get data in/out, and optional parts of a standard library (if included), how big is the remainder, the implementation of the language constructs? (Potentially) standalone, self-hosting & small is indeed the bonus points I'm looking for. A tiny Basic or Forth running bare metal on a uC could be it. A 'tiny' language implemented using a multi-MB VM is not.
    - samatman 2y ago
      It seems we're basically in agreement then. I do want to point out that the weight of the Lua 5.4 standalone binary on my machine is 70KiB. Yes, you read that correctly. Lua is truly amazing in terms of the amount of power you get for how little there really is. One of the reasons it's faster than most other VMs with no JIT functionality is because the entire VM fits in a typical L1 cache. My laptop's L1 is 192KiB, meaning it could fit 122KiB of program state in with the VM without breaking a sweat.
- RetroTechie 2y ago
  > One thing you quickly run into with this exercise is needing to establish the boundaries around "programming language" which can be kind of fraught. Well I was referring to what one could call a souped-up macro assembler: direct access to a machine's hardware, but with some (but important!) conveniences of higher-level languages. Eg. many Forth systems provide a read-eval-print loop (REPL), allowing users to re-define Forth words on the fly, poke some memory mapped IO, etc. But still do so in a relatively comfortable manner using Forth words rather than (only) through editing assembly code. The mapping (the "language", if you will) between Forth words, and assembly code that implements them, is fairly straightforward 1:1. And thus, allows for small implementations. Like, fit comfortably in a 16-bit address space. Many esoteric languages do not fit this description, since they often discard the convenience factor. C is on the fence here. It's got many of these aspects, but small-ish? Hmm.. And stripped down to a subset, is it still C?
tromp 2y ago
Binary Lambda Calculus is absolutely tiny [1], with a 29 byte self-interpreter (43 byte for the byte oriented version), and absolutely extensible, since it can transform into any other language. [1] https://www.ioccc.org/2012/tromp/hint.html https://www.ioccc.org/2012/tromp/hint.html
johnnyjeans 2y ago
There are a lot of languages that are actually pretty small if you just boil them down to their primitives. Prolog and most other rule engines, especially CLIPS, jump to mind. ANSI C and SML. SML in particular is cute if you use your tiny Prolog to implement the type system ;-)
- trealira 2y ago
  > SML in particular is cute if you use your tiny Prolog to implement the type system. That sounds pretty cool; do you know of an implementation of SML that fits into 10 KB of memory because it uses tiny Prolog?
  - johnnyjeans 2y ago
    I do not. As far as I'm aware, SML is much like C in that despite being a relatively simple language, there aren't many toy implementations floating around.
trealira 2y ago
Apparently, the B programming language from 1969 fit into 8 KB of memory: https://www.bell-labs.com/usr/dmr/www/chist.html https://www.bell-labs.com/usr/dmr/www/chist.html After a rapidly scuttled attempt at Fortran, he created instead a language of his own, which he called B. B can be thought of as C without types; more accurately, it is BCPL squeezed into 8K bytes of memory and filtered through Thompson's brain.

giraffe_lady 2y ago

One thing you quickly run into with this exercise is needing to establish the boundaries around "programming language" which can be kind of fraught. For example miniKanren is tiny and is used as a DSL, but is capable of expressing any computation so does that count? Some type systems are turing complete and a naive implementation could be tiny. Is conway's game of life a programming language. You could probably strip a bunch of useful stuff out of sqlite's sql parser and get it below 10k. etc.

samatman 2y ago
You have to draw a line somewhere, and it's necessarily somewhat arbitrary. Mine is the size of the runtime, usually. So the Forth is the size of Lua + the 40 line script, minKanren is the size of the .scm file + the Scheme implementation, and so on. This ignores the host environment, which I think is fair: generally these will be enormously larger than they would actually have to be to support the language. I do award subjective bonus points to languages which actually have a freestanding runtime, that is, I could actually compile them and run them on a bare chip. Even then, I don't count the microcode which implements the instruction set of that chip, or the Verilog/VHDL which is needed to tape it out. Usually! ColorForth on GreenArrays gets even more bonus points, because not only is the language exceedingly compact, and freestanding, but the VLSI tool used to create the chip is also tiny to an almost unbelievable degree. So it wins some kind of prize in the special "total system complexity" category.
- RetroTechie 2y ago
  > I do award subjective bonus points to languages which actually have a freestanding runtime, that is, I could actually compile them and run them on a bare chip. That's what I was getting at with "trivial IO": when you ignore what's needed to get data in/out, and optional parts of a standard library (if included), how big is the remainder, the implementation of the language constructs? (Potentially) standalone, self-hosting & small is indeed the bonus points I'm looking for. A tiny Basic or Forth running bare metal on a uC could be it. A 'tiny' language implemented using a multi-MB VM is not.
  - samatman 2y ago
    It seems we're basically in agreement then. I do want to point out that the weight of the Lua 5.4 standalone binary on my machine is 70KiB. Yes, you read that correctly. Lua is truly amazing in terms of the amount of power you get for how little there really is. One of the reasons it's faster than most other VMs with no JIT functionality is because the entire VM fits in a typical L1 cache. My laptop's L1 is 192KiB, meaning it could fit 122KiB of program state in with the VM without breaking a sweat.
RetroTechie 2y ago
> One thing you quickly run into with this exercise is needing to establish the boundaries around "programming language" which can be kind of fraught. Well I was referring to what one could call a souped-up macro assembler: direct access to a machine's hardware, but with some (but important!) conveniences of higher-level languages. Eg. many Forth systems provide a read-eval-print loop (REPL), allowing users to re-define Forth words on the fly, poke some memory mapped IO, etc. But still do so in a relatively comfortable manner using Forth words rather than (only) through editing assembly code. The mapping (the "language", if you will) between Forth words, and assembly code that implements them, is fairly straightforward 1:1. And thus, allows for small implementations. Like, fit comfortably in a 16-bit address space. Many esoteric languages do not fit this description, since they often discard the convenience factor. C is on the fence here. It's got many of these aspects, but small-ish? Hmm.. And stripped down to a subset, is it still C?

tromp 2y ago

Binary Lambda Calculus is absolutely tiny [1], with a 29 byte self-interpreter (43 byte for the byte oriented version), and absolutely extensible, since it can transform into any other language. [1] https://www.ioccc.org/2012/tromp/hint.html https://www.ioccc.org/2012/tromp/hint.html

johnnyjeans 2y ago

There are a lot of languages that are actually pretty small if you just boil them down to their primitives. Prolog and most other rule engines, especially CLIPS, jump to mind. ANSI C and SML. SML in particular is cute if you use your tiny Prolog to implement the type system ;-)

trealira 2y ago
> SML in particular is cute if you use your tiny Prolog to implement the type system. That sounds pretty cool; do you know of an implementation of SML that fits into 10 KB of memory because it uses tiny Prolog?
- johnnyjeans 2y ago
  I do not. As far as I'm aware, SML is much like C in that despite being a relatively simple language, there aren't many toy implementations floating around.

trealira 2y ago

Apparently, the B programming language from 1969 fit into 8 KB of memory: https://www.bell-labs.com/usr/dmr/www/chist.html https://www.bell-labs.com/usr/dmr/www/chist.html After a rapidly scuttled attempt at Fortran, he created instead a language of his own, which he called B. B can be thought of as C without types; more accurately, it is BCPL squeezed into 8K bytes of memory and filtered through Thompson's brain.