8 ms·
StoneKnifeForth (With a Metacircular Compiler)
- rwmj 6y agoIs it Forth week on HN :-? I like this but only allowing single letter identifiers is an unfortunate choice - although I'm sure it made parsing much simpler.
- agumonkey 6y agoYeah I wonder what propped this flood of Forth threads. Not that I'm against it.. just a bit odd.
- guerrilla 6y agoToo much? I've been posting things I think other people might find interesting while researching implementing a Forth compiler after having just done a Scheme.
- kragen 6y agoWell, not all the hackers have yet been driven from "Hacker News" yet, I guess. Where there are hackers, there will be FORTH — as Devine Lu Linvega said, "Lisp is a slippery slope that leads inevitably to FORTH." DSSP was an independent Soviet invention (on a balanced-ternary machine!) but its differences from ANS FORTH are smaller than the differences between Moore's early text interpreters and polyForth or ANS FORTH. FORTH's a bit of an occupational hazard of hacking, you might say. Like suicide, or being burned at the stake. (It's been two days since the anniversary of Giordano Bruno being burned at the stake for being a hacker, though he was too early to write a FORTH himself.)
- agumonkey 6y agoAre you still stuck in a basement ?
- kragen 6y agoNo! I remodeled the basement, picked the lock, hopped a freight train, and married into the gentry years ago. Since then, I've founded a company, been betrayed by my closest friends, written a book (which turned out to be unreadable), set myself on fire repeatedly, violently subdued villainous bandits, fallen in love with beautiful women, broken their hearts, had my heart broken by them, and digitized the Oxford English Dictionary. I've read through ancient, forgotten books in faraway lands; I've learned strange tongues and seen fortunes won and lost; I've comforted the grieving, and I've restrained deadly robots as they wriggled to escape my grasp. I've comforted the suicidal, and I've broken the trust of those who placed their hopes in me. After midnight, I danced in the moonlight with a beautiful Brazilian as we stood guard outside her now-demolished ecovillage; she told me she'd thought she'd lost the ability to fall in love. We didn't need any music. I've studied at the knee of wise elders, meditated in monasteries, translated poetry, and embraced madmen who predicted my demise in their psychotic ravings. I've made foolish mistakes whose consequences maimed those I loved, and I've averted catastrophe innumerable times. And most of that is even true. Thanks for asking! I hope you're doing well too :)
- vidarh 6y agoThese things tend to happen on HN - someone discovers something new or new to them and posts something and triggers others to read up on the subject and/or reminds people of related projects, and suddenly you have a slew of submissions about similar things.
- mindcrime 6y agoSpeaking as somebody who submitted a couple of Forth links (but not this one) - I saw there were two Forth related links on the front-page at one point yesterday, was reminded of the famous "Erlang Day" incident in HN history and thought "wouldn't it be cool if HN were flooded with Forth links for a little while?" and submitted a couple. Can't speak for anybody else, but I'm guessing other people had a similar reaction.
- todd8 6y agoHow strange, I just picked up a book from my bookshelf, my old copy of Starting Forth by Leo Brodie. I was trying to remember if Forth was created by Charles Moore or Calvin Moores. Charles Moore invented Forth. I really enjoyed reading Starting Forth when it came out. I've used Starting Forth together with Threaded Interpretive Languages: Their Design and Implementation by R. G. Loeliger to create my own Forth system. This second book is not about "threads" as we know them today; threading is a way to very efficiently dispatch the execution of Forth primitives. Calvin Moores is a language inventor too. I've also implemented a version of his language TRAC. TRAC is mentioned prominently in a book that I really enjoyed while in grad school in the 70's, Computer Lib by Ted Nelson. Described by Wikipedia as the first book on personal computers. The appeal of Forth, and even more so of TRAC, is that they are very simple languages to implement. It is completely possible to implement either language in assembly language, but C would be a bit easier. As a project to learn Perl, back when it was new, I wrote a TRAC interpreter over a couple of days. TRAC, like the roughly contemporaneous language GPM invented by Christopher Strachey, is a macro processor. GPM and TRAC are "Turing complete" macro processors. So they can be used to write arbitrary programs and are in fact designed for this purpose. Some links/references: Leo Brodie, Starting FORTH : an introduction to the FORTH language and operating system for beginners and professionals, Prentice-Hall, 1987. https://www.forth.com/starting-forth/ https://www.forth.com/starting-forth/ Martin Campbell-Kelly, Christopher Strachey, 1916-1975: A Biographical Note, IEEE Annals of the History of Computing, 1985, https://www.computer.org/csdl/magazine/an/1985/01/man1985010019/13rRUy3gmZc https://www.computer.org/csdl/magazine/an/1985/01/man1985010... R. G. Loeliger, Threaded Interpretive Languages: Their Design and Implementation, BYTE Books, 1979, https://www.abebooks.com/servlet/BookDetailsPL?bi=22536154738&cm_ven=sws&cm_cat=sws&cm_pla=sws&cm_ite=22536154738&clickid=1rPxe9yy8xyLRH4wUx0Mo3b5UkETmTzEEzAf0A0&cm_mmc=aff-_-ir-_-353196-_-77798&ref=imprad353196&afn_sr=impact https://www.abebooks.com/servlet/BookDetailsPL?bi=2253615473... Calvin Moores, TRAC, A Procedure-Describing Language for the Reactive Typewriter, CACM Vol 9, Num 3, March 1966, https://dl.acm.org/doi/10.1145/365230.365270 https://dl.acm.org/doi/10.1145/365230.365270 Ted Nelson, Computer Lib/Dream Machines, self-published, 1974, https://en.wikipedia.org/wiki/Computer_Lib/Dream_Machines https://en.wikipedia.org/wiki/Computer_Lib/Dream_Machines
- rwmj 6y ago
- kragen 6y agoHey, I'm glad you like it! I liked Jonesforth a lot, and SKF's predecessor tokthr was derived from Jonesforth: https://github.com/kragen/tokthr/blob/master/tokthr.S https://github.com/kragen/tokthr/blob/master/tokthr.S IIRC the reason I only allowed single-byte identifiers was to simplify the symbol table, which is implemented by these four lines of code: : Type Four* header 6144 + + ; ( Table of definition Types: 1=code, 2=data ) : Addr Type 1024 + ; ( table of definition Addresses ) ( register a colon definition ) : Colon %flush dup Type 1 xchg ! HERE @ xchg Addr ! ; ( register a variable definition ) : Var %flush dup Type 2 xchg ! HERE @ xchg Addr ! ; Abbreviating this as follows would clearly be highly immoral, so I would never do that: : T F h 6144 + + ; : A T 1024 + ; : C % d T 1 x ! H @ x A ! ; : V % d T 2 x ! H @ A ! ; "Parsing" is kind of the same as it would be if more bytes in the name were significant, because the other bytes in the name are still there in the source and the compiler still has to skip them: : word getchar dup Isdigit [ ; ] dup '' = [ ; ] dup 0 1 - = [ ; ] { Getchar dup ' = [ pop ; ] dup 10 = [ pop ; ] 0 1 - = [ ; ] 1 } What's simpler is that it doesn't have to store them anywhere, or implement any kind of string compare operation, and consequently doesn't use C@, and consequently doesn't have to implement C@ either. It implements @ and ! and C! (which it calls "store"; I should have called it "c!" since capital "C" was already taken for "colon"). It needs C! ("store") for emitting sub-word-length instructions and at any rate for backpatching jumps. It's definitely a questionable choice, though! I think it might be worth using two significant letters instead of one for a "tiny boot FORTH". Traditional FORTHs, you probably recall, used a fixed-size four-byte "name" in their dictionaries: a length byte and the first three letters of the name. Chuck Moore received some criticism for this choice, in response to which he wrote a letter to a popular FORTH magazine arguing, effectively, that thr-- let---- was ade----- to tel- wor-- apa--; col------- bet---- wor-- wer- suf--------- rar- wit- the fir-- thr-- let---- bei-- sig--------, and of cou--- it was mor- eff------. FTP and SMTP commands are all four letters long for the same reason.
- transfire 6y agoI very much enjoyed this, in explaining StoneKnifeForth it is a nice article on minimalism in computer language design.
- kragen 6y agoI'm glad to hear it!
- orthoxerox 6y agoI love that it produces actual runnable binaries instead of emitting assembly or C, like so many tiny compilers do. I know it's technically the job of the assembler and the linker, but without these parts it kinda feels like cheating.
- carapace 6y agoFor this sort of thing I bounce back and forth between targeting C vs ASM. C is so universal and there are so many tools you can use to harden it. On the other hand, you're still using a big ol' abstraction layer between C and the machine. On the gripping hand, CPUs are doing so many things under the hood now that ASM can be considered an abstraction layer obscuring the actual machine, so you kind of need a modern compiler to have a hope of taking advantage of all that without doing a ton of research. Over on the "αcτµαlly pδrταblε εxεcµταblε" page ( https://justine.lol/ape.html https://justine.lol/ape.html ) there's a subsection called "x86-64 Linux ABI Makes a Pretty Good Lingua Franca" it seems to me to be a reasonable suggestion (although I've never like x86 myself.) You can bundle an x86 emulator with your code to run on other architectures. I like the Project Oberon 32-bit RISC developed by Prof. Wirth as a target. It's really simple for educational purposes. (Meaning you can more easily teach more people Oberon RISC than, say, RISC-V. ALthough see the "Selfie" project: https://selfie.cs.uni-salzburg.at/ https://selfie.cs.uni-salzburg.at/ "An educational software system of a tiny self-compiling C compiler, a tiny self-executing RISC-V emulator, and a tiny self-hosting RISC-V hypervisor.") There are many emulators for Oberon RISC already, including one in Javascript, so you can run the old Oberon OS in your browser! Launch an emulator with a disk image from here: https://schierlm.github.io/OberonEmulator/ https://schierlm.github.io/OberonEmulator/
- astrobe_ 6y agoI have done something along the lines of TFA a long time ago, a system that could boot from a floppy and recompile itself from source (never did anything useful with it), but today I daily use a Forth dialect written in C that is designed to play nice with C and the OS. C is a sure bet. Interpreters that rely too much on JIT are simply not available on processors where the JIT is not available (duh), which was often the case for ARM before it became really popular. Same thing with relying on an emulator (also, you are running a VM in another kind of VM; it's usually bad for performance). As far as speed is concerned, if your Forth implementation makes it really easy to extend, you can always get something fast enough by re-coding the critical parts in C. That's why I stopped worrying about which implementation technique is the fastest and chose the one that made it the most trivial to extend the interpreter.
- pmiller2 6y agoSomeone needs to write a library / framework for this thing and call it "bear skin." https://wiki.c2.com/?BearSkinsAndStoneKnives https://wiki.c2.com/?BearSkinsAndStoneKnives
- aarchi 6y agoI built an AOT compiler for Whitespace with its own SSA-form intermediate representation that lowers to LLVM IR. Whitespace is very similar to a minimal Forth, except, well, syntax. Since StoneKnifeForth has no filesystem access, only stdin and stdout, the principles could be easily adapted for Whitespace. https://github.com/andrewarchi/nebula https://github.com/andrewarchi/nebula
- notriskfree 6y agoVery nice. Building a new FORTH using FORTH might have been easier; FORTH is traditionally very good at rebuilding itself. e.g. WimpForth on a PI400 recompiles its own kernel to an absolute image (executable) in 00:00:007. FORTH week on HN is great. The main trouble with FORTH is remembering to stop playing with FORTH and actually write the App.
- anta40 6y ago"actually write the App." I assume FORTH is mostly used for embedded development these days? And perhaps umm... instrumentation? What about mobile apps? Or REST API?
- kragen 6y agoThose I write in JS: http://canonical.org/~kragen/sw/81hacks/progeome http://canonical.org/~kragen/sw/81hacks/progeome
- kragen 6y agoYeah, it probably would have been easier to metacompile from an existing FORTH, but the whole point was to not have a lot of dependencies on existing code.
- deleted 6y ago[deleted]
- mcguire 6y ago"But if you try to implement a Lisp interpreter in a low-level language by translating that metacircular interpreter into it (as I did later that year) you run into a problem. The metacircular interpreter glosses over a large number of things that turn out to be nontrivial to implement — indeed, about half of the code is devoted to things outside of the scope of the metacircular interpreter. Here’s a list of issues that the Lisp 1.5 metacircular interpreter neglects, some semantic and some merely implementational:..." Amen! Those metacircular interpreters are neat, and very useful from a learning-programming-languages standpoint, but they gloss over about 90% of the details and pain of language implementation. I was really looking forward to Paul Wilson's An Introduction to Scheme and its Implementation (http://www.aboulsaadat.com/wael/teaching/324/exdocs/schintro_paul_wilson.pdf http://www.aboulsaadat.com/wael/teaching/324/exdocs/schintro...), but at the time it was really incomplete. Looks like there's more now, but still no garbage collection as far as I can see.
- nils-m-holm 6y agoHere is a minimal LISP compiler in 400 lines of LISP that does not gloss over anything: http://t3x.org/lfn/liscmp.lisp.html http://t3x.org/lfn/liscmp.lisp.html It only depends on about 350 lines of LISP code for standard functions like CADR, APPEND, READ, etc, plus avout 400 lines of C for low-level stuff (variable binding and garbage collection). The 350 lines of LISP standard function even contain low-level things like interning of symbols: http://t3x.org/lfn/lisp.lisp.html http://t3x.org/lfn/lisp.lisp.html Even the garbage collector could be written in LISP http://t3x.org/lfn/gc.lisp.html http://t3x.org/lfn/gc.lisp.html but there are a few issues that are not addressed in the code. For a full explanation of the compiler and some bits of historical trivia, see http://t3x.org/lfn/index.html http://t3x.org/lfn/index.html
- kragen 6y agoThis is very interesting, thank you! At first glance, it does perhaps gloss over a few things still: instruction encoding, jump-target backpatching (or its moral equivalent), the system call interface, the fetch-execute cycle, and a debugger; but not, for example, function entry and exit, or, as you point out, garbage collection or the reader. Also, on p. 16, there's an error seemingly due to the author not knowing about the Y-combinator: The LABEL special form, as implemented by EVAL, was a clever construct for defining anonymous recursive functions. Anonymous functions ("lambda functions") cannot usually recurse (apply themselves), just because they are anonymous, so there is no name that can be used to invoke them.
- tekknolagi 6y agoI have a C++ fork of this project in case Python isn't an option: https://github.com/tekknolagi/stoneknifecpp https://github.com/tekknolagi/stoneknifecpp
- kragen 6y agoYes, this is awesome!
- Klwohu 6y ago>If you want to counter Ken Thompson’s “Trusting Trust” attack, you would want to start with a minimal compiler on a minimal chip; StoneKnifeForth might be a good approach. Some people have been working on fairly good Forths for different, minimal hardware including the Parallax boards. https://github.com/prof-braino/PropForth5.5 https://github.com/prof-braino/PropForth5.5 There's also Chuck Moore's GreenArrays GA144 if you want a high performance Forth machine which includes a proto area on the board.
- aidenn0 6y agoThe ga144 seems more like a replacement for a cpld+mcu so I wouldn't call it "high performance" in the sense that a mid ranged arm board will out perform it on terms of raw throughput for most tasks.
- kragen 6y agoWell, I think an FPGA might be a closer equivalent. The GA144 can do something like 100 billion 18-bit integer additions per second, or two billion 17×17-bit integer multiplications (my rough notes on http://www.greenarraychips.com/home/documents/greg/WP003-100617-msp430.pdf http://www.greenarraychips.com/home/documents/greg/WP003-100... are where I'm getting that). With a CPLD like the US$1.00 Altera 5M40ZE64C5N you might be able to get 100 million 16-bit integer adds per second, three orders of magnitude slower — and CPLDs don't usually have multipliers on them, so multiplication will be slower by the same amount. What do you mean by "a mid ranged arm board"? This Blue Pill is a US$2 ARM board, and a MacBook Pro is a US$2048 ARM board, so maybe something like the geometric mean, US$64? Maybe like https://www.digikey.com/en/products/detail/stmicroelectronics/STM32F7508-DK/10209874 https://www.digikey.com/en/products/detail/stmicroelectronic... a US$54 STM32F750N8† eval board? Well, that has 64 KB of Flash and 340 KB of RAM (an order of magnitude more than the 9216 18-bit words on the GA144), and a screen, and a lot of I/Os and integrated peripherals, and the MCU has a bunch of fixed-function blocks like AES and SHA-2. But "in terms of raw throughput for most tasks" I don't think it's anywhere close: it's just a 216-MHz Cortex-M7, which is a 32-bit 2.1DMIPS/MHz dual-issue core with a 6-stage pipeline, "DSP instructions", and floating point. The "DSP instructions" turn out to be multiply-accumulate and integer SIMD, so you can do four 16-bit multiply-accumulates per cycle instead of one, if the pipeline doesn't stall. Or eight 8-bit multiply-accumulates. That adds up to about 0.9 billion 16-bit multiplies per second, which is indeed in the same league as the GA144. But it's also only 0.9 billion 16-bit adds per second, or 1.8 billion 8-bit adds, which is short of the GA144's 100 billion adds per second by about a factor of 64! While using an order of magnitude more power (thus "GreenArrays", I suppose.) And it's a very inflexible 0.9 billion multiplies — it's hard to not stall the pipeline and to ensure that you're not accidentally serializing on a single functional unit. The GA144 cores don't have pipelines — but you'll probably build pipelines when you floorplan your app on it. I mean, I imagine the AES core on the STM32 is actually faster than AES on the GA144, which takes 38 μs per 128-bit block using 17 of the 144 processors.※ That's 420 kilobytes per second, or 3.3 megabytes per second if you replicate it 8 times. I don't know how slow the STM32's AES hardware is but I bet it takes less than 70 clock cycles per byte. That's a bit faster than (one core of) this laptop's CPU, an i7-3840QM at 2.8 GHz, with no AES-NI, which gets 2.1 megabytes per second. But it's not very flexible. You can switch those 17 cores to run a different application in about a microsecond; the AES hardware is forever AES hardware. With floating-point math I think the comparison might be arguable. The GA144 has to implement floating point in software, like we did on our 486es, which usually imposes a speed penalty on the order of 32×. The ARM core has single- and double-precision floating-point hardware. The GA144's throughput is around 128× as many instructions per second as the ARM's, but it has to multiply a single multiplier bit at a time, so it might end up being slower in this case. Believe me, I love me some "mid ranged arm boards" for "raw throughput" (see http://canonical.org/~kragen/sa-beowulf/ http://canonical.org/~kragen/sa-beowulf/ for some context) but I think an FPGA is a closer analogy. A small FPGA, like a US$6 ICE40UP5K, which has eight 16-bit multipliers running, I think, up to about 100 MHz, so it can do nearly one billion multiplies per second. But when it comes to addition, or state machines, or square roots, or FFTs, the GA144 hopelessly outclasses it. You need to move up to a much larger FPGA to get into the same order of magnitude. So why would anyone use a CPLD or an FPGA or an MCU when they could use a GA144? Because you can program the MCU in C or Python, and you can program the CPLD or FPGA in Verilog, but if you want to use the GA144 you have to program it in Forth. Worse, until recently you had to program the GA144 in a dialect of colorForth. With an FPGA nextpnr does the floorplanning for you; with arrayForth you have to do the floorplanning. There are efforts to improve this situation, like Chlorophyll‡ ("Compared to MSP430, GA144 is 19 times more energy efficient and 23 times faster when running this [accelerometer-based hand-gesture recognition] application"), but they're still research projects, and they still require you to learn new languages. C was a research project in 1972, Verilog was a research project in 1986, and yosys was a research project in 2014 (and still is if you want to use the 5M40ZE64C5N), but now they're battle-tested tools that lots of people know how to use. The GreenArrays tools to allow you to program at a higher level are not there yet, because Chuck Moore doesn't think that's the way to do things. Disclaimer: I haven't used any of the chips mentioned above except the i7, so probably some of the things I said above are wrong. Corrections would be greatly appreciated. _______ † https://www.st.com/resource/en/datasheet/stm32f750v8.pdf https://www.st.com/resource/en/datasheet/stm32f750v8.pdf ‡ https://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-134.pdf https://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-... ※ https://www.cosic.esat.kuleuven.be/ecrypt/AESday/slides/AES-DAY-Gueneysu.pdf https://www.cosic.esat.kuleuven.be/ecrypt/AESday/slides/AES-...
- kragen 6y agoOh hey, I'm glad people are enjoying SKF. Last week I was thinking that it might be interesting to port it to RISC-V, which involves maybe a certain amount of perverse instruction encoding pain, but is otherwise very much simpler than i386.