10 ms·
A bestiary of single-file implementations of programming languages
- dmitripopov 7y agoSomehow I still get those chills while reading source code of programming languages interpreters / compilers. I guess it's like getting to the origins of life, or something.
- downerending 7y agoIt is. As a kid, I kind of understood programs, but I could not even imagine how an interpreter (or compiler) could work. I partly got a CS degree just so I could learn the answer.
- glic3rinu 7y agoThen this talk from David Beazley will blow your mind https://www.youtube.com/watch?v=VUT386_GKI8 https://www.youtube.com/watch?v=VUT386_GKI8
- 7thaccount 7y agoFor those of us short on time, can you summarize in a sentence or two?
- ampdepolymerase 7y agoHe builds a WebAssembly interpreter from scratch in Python and compiles a Rust program to run on it.
- sigjuice 7y agoFrom https://www.dabeaz.com/talks.html https://www.dabeaz.com/talks.html Closing Keynote: A Talk Near the Future of Python October 13, 2019 PyCon India, Chennai A live-coded implementation of simple stack machine that's later turned into a WebAssembly interpreter capable of running a game written in Rust.
- deleted 7y ago[deleted]
- ngcc_hk 7y agoThe twist is a bit of a surprise. Totally like the change in the movie parasite. It just suddenly from text to ... Very good video.
- frabert 7y agoIncredibly similar to my story. I did not even know how to program, but the mere idea of something that took code in and spit executables out was completely magic to me. I absolutely had to know how they worked.
- dana321 7y ago(Abstract Syntax) Tree (Of Life)
- PaulHoule 7y agoThe small C compilers are great. I guess if you couldn't write a C compiler in a single small file (by modern standards) you wouldn't have been able to run a C compiler on an 8-bit machine.
- kick 7y agoActually, C compilers back then were still pretty large (also, as far as I'm aware, every machine that UNIX originated on was at least 16-bit, and the very first machine it ran on was 18-bit): https://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c https://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/... The language was quite a bit smaller, though, and much less complex. A C2X compiler will be drastically more tedious to make than this was.
- PaulHoule 7y agoThat is still not much code.
- john-radio 7y agoI laughed at the header in comment at the top of the Super Tiny Compiler here: https://github.com/jamiebuilds/the-super-tiny-compiler/blob/master/the-super-tiny-compiler.js https://github.com/jamiebuilds/the-super-tiny-compiler/blob/...
- ww520 7y agoNot surprisingly most are lisp.
- dr_j_ 7y agoWhy is that? What’s special about lisp?
- 7thaccount 7y agoI think relatively easy to implement and interesting to many.
- lallysingh 7y agoIt's got no grammar, so you don't have to parse it, just lex and recursively eval.
- dr_j_ 7y agoI guess one might say that the syntax is basically the parse tree, more or less?
- kazinator 7y agoIf you want to do a really poor, minimal job of implementing something that processes and executes programs, you will find that most of the complexity will rest in handling syntax. Any reductions in that complexity will have a big relative impact on trimming down the code and amount of work. Now you can duck out of implementing solid semantics, without changing what a language looks like. For instance, programs language with broken scope can look superficially like programs in a language with working lexical scope. Or, a language that works by interpreting a syntax tree using a few lines of code looks and works just as well as a compiled one, just slower. But if you don't negotiate about what a language looks like, there is only so much simplification you can do while still correctly handling the syntax which allows the language to look like that. Further reductions in complexity require simplifications in syntax (how the language looks), which leads toward one of several existing well-understood design families for minimal syntax: Lisp-like, Forth-like, APL-like.
- cellularmitosis 7y agoReaders of this thread might enjoy the collection of links I've started collecting: https://gist.github.com/cellularmitosis/1f55f9679f064bcff02905acb44ca510 https://gist.github.com/cellularmitosis/1f55f9679f064bcff029...
- dr_j_ 7y agoThese examples blow my attempt at an interpreted programming language (thousands of lines over multiple source files) out of the water.. so impressive.
- skybrian 7y agoIt would be nice to see more examples of how to do type checking. But there are some good examples in the Programming Languages Zoo. [1] [1] https://plzoo.andrej.com/ https://plzoo.andrej.com/
- userbinator 7y agoI think the ones which can self-compile are most interesting, because it passes a "it's not just a trivial example anymore" point. To do that in a single relatively small file also makes it convenient for studying. Mini-C is even more amazing if you look at its description: I set myself a challenge: write a self-hosting C compiler in 10 hours. Although the language it accepts, being untyped, is closer to B. Also nice to see my personal favourite, C4, in the list.
- onlyrealcuzzo 7y agoHe wrote a self hosted C compiler in 10 hours?! How?! That is straight up sorcery.
- progfix 7y agoIt's not that hard if you have experience in writing compilers.
- mras0 7y agoHadn't seen Mini-C before, that's quite the feat. Apart from the awesome C4, I also like 8cc (https://github.com/rui314/8cc https://github.com/rui314/8cc) in this category. Recently did this myself (https://github.com/mras0/scc/blob/master/scc.c https://github.com/mras0/scc/blob/master/scc.c) but it took waaaaay more than 10 hours and I had many previous failed attempts before that.
- mickduprez 7y agoForth is a great language, simple syntax, (relatively) simple to implement, has a repl, easily extendable and fast. Chuck Moore was/is really onto something.
- LessDmesg 7y agoThen how come no real software has been written in this wonderful language? Not even a decent text editor, let alone a browser or a game engine?
- RodgerTheGreat 7y agoMost of the software written in Forth runs on embedded systems, not user-facing ones. OpenFirmware is based on forth, and was used instead of BIOS for Sun workstations, some Powermacs, and the OLPC, among other devices. On the OLPC it offers a nice debugging interface and educational opportunity.[0] The Wikireader "wikipedia appliance" used forth for their testing harness during manufacturing, and it's possible to write your own applications for the device using it.[1] Forth has been used for control software for a variety of aerospace applications.[2] I have personally used Forth as an interactive testing environment for bringing up new hardware. In one case, I prototyped software for the power management chip in an embedded linux device. I've also written games and programming environments in Forth, both for fun and for use in educational after-school programs I helped organize. For example, a logo environment[3,4] and a rewrite of Yar's Revenge[5,6]. Is any of this software "real"? [0] http://wiki.laptop.org/go/Open_Firmware http://wiki.laptop.org/go/Open_Firmware [1] https://github.com/JohnEarnest/Wikireader-Adventures https://github.com/JohnEarnest/Wikireader-Adventures [2] https://www.forth.com/resources/space-applications/ https://www.forth.com/resources/space-applications/ [3] http://johnearnest.github.io/Mako.js/?rom=Loko http://johnearnest.github.io/Mako.js/?rom=Loko [4] https://github.com/JohnEarnest/Mako/tree/master/demos/Loko https://github.com/JohnEarnest/Mako/tree/master/demos/Loko [5] http://johnearnest.github.io/Mako.js/?rom=Yar http://johnearnest.github.io/Mako.js/?rom=Yar [6] https://github.com/JohnEarnest/Mako/blob/master/games/Yar/Yar.fs https://github.com/JohnEarnest/Mako/blob/master/games/Yar/Ya...
- 7y ago
- breuleux 7y agoWell, that's cool. Might as well plug the one I made a couple years ago. It's an interactive tutorial too, sort of: http://breuleux.net/blog/language-howto.html http://breuleux.net/blog/language-howto.html
- RodgerTheGreat 7y agomy k interpreter[0] is less than 1000 lines of JS. Big compared to many on this list, but still human-scale. Looking back on it I see many opportunities left to simplify. further back, I wrote a compiler for part of the language described in Dijkstra's A Discipline of Programming in a dialect of forth[1]. one of my colleagues, Stevan Apter, has a number of interesting toy interpreters on his site[2], particularly concatenative languages. [0] https://github.com/JohnEarnest/ok/blob/gh-pages/oK.js https://github.com/JohnEarnest/ok/blob/gh-pages/oK.js [1] https://github.com/JohnEarnest/Mako/blob/master/demos/FiDo.fs https://github.com/JohnEarnest/Mako/blob/master/demos/FiDo.f... [2] http://nsl.com http://nsl.com
- mamcx 7y agoThis great. I wish exist more information on the array family (and with less "condensed" syntax :)). I'm building a relational language and have tried to borrow some ideas, but apart from the very basics is not much info out (and most are about numerics). For example, how about crud operations.? Lazy evaluation?
- kick 7y agoThe condensed "syntax" (notation) is actually a feature! Read "Notation as a Tool of Thought" to learn more, it's actually one of the best parts of APL as a whole.
- mamcx 7y agoYeah, i have read it (is good!). But could be useful to de-compress it and see how is used "normally" then the step back, I think.
- Firadeoclus 7y agoIndeed, as someone who's learning a bit of APL on the side I'd love to have a tool that can "explain" a line of APL on demand, e.g. show the parse tree, name built-in functions and operators, expand trains, possibly name common idioms. I find the concepts in APL very simple. The difficulty for me is in becoming comfortable reading it. Such a tool would make it quick and easy to confirm one's initially very tentative guesses as to what a line means, and gradually you'd come to depend less on it as you get more confident that your initial understanding is right.
- remcob 7y agoThe LLVM Kaleidoscope tutorial [0] builds up to a single file implementation. It's a very good introduction. I'd also like to offer my winning Brainfuck compiler + direct threaded VM implemented in Ethereum assembly [1]. [0] https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index... [1] https://g.solidity.cc/submissions/wicketh.eth/9a5cb12b504b81db3ac1ad8e2cb8be1e869851554f385ec8b8f4412f48d420ce https://g.solidity.cc/submissions/wicketh.eth/9a5cb12b504b81...
- DagAgren 7y agoA bit disappointed that False is not on there, since it was both a compiler that fit in less than 1k of binary code, and also the origin of the whole esoteric language craze that is still going on. (Brainfuck was a direct response to it, trying to make a compiler that was significantly smaller - the original compiler was 240 bytes.)
- thr0w__4w4y 7y agoHa ha, no one brave enough to take on C++. Many years ago I worked on a C++ compiler, and this was during the C++03 days. The language and standard (now C++20) is // so much larger // than it was even 15-20 years ago. I will say, however, that when I'm brave enough to peek into the clang code (I work up the courage maybe a couple times a year), at least for someone who understands the language, it's very clean. But it's big. Very big.
- peter_d_sherman 7y agoPascal-S, Mini-C, 256LOL (x86 assembler)... Nice!