Skip to content

mitranim/astil_forth

BranchesTags

Repository files navigation

TOC

Overview

Astil Forth is a native-code Forth system designed for self-bootstrapping and self-assembling. Uses a custom assembler in both C and Forth code. Currently supports only Arm64.

Goals:

  • Explore combined JIT & AOT compilation.
  • Explore viability of single-pass assembly.
  • Easy self-assembly in user/lib code.
  • Implement most of the language in user/lib code outside the compiler.
  • Be usable for scripting.
  • Support native register-based call ABI.
  • Avoid a VM or complex IR.
  • Keep the code clear and educational for other compiler amateurs.
  • Rewrite in Forth to self-host.

Non-goals:

  • Following other compiler designs.
  • Portability to multiple ISAs.

Everything was written by me. This is not slopbot-generated.

I gave talks about Astil Forth in SVFIG meetings (Silicon Valley Forth Interest Group). Currently, that's the closest substitute for documentation, in addition to this readme and ./examples.

Unlike other compiler writers, I focused on keeping the system clear and educational as much as I could. Compilers don't have to be full of impenetrable garbage. They can consist of obvious stuff you'd expect, and can learn from.

Show me the code!

IO and conditionals:

import' std:lang.af

: main
  " hello world!" log lf

  10
  if
    " branch 0" log lf
  else 20 elif
    " branch 1" log lf
  else
    " branch 2" log lf
  end

  12 0 +for: ind
    " current number: %zd" ind logf lf
  end
;

main

Easy self-assembly (Arm64):

\ add Xd, Xn, Xm
: asm_add_reg { Xd Xn Xm -- instr }
  Xd Xn Xm asm_pattern_arith_reg
  0b1_0_0_01011_00_0_00000_000000_00000_00000 or
;

\ add x0, x0, x1
: + { i0 i1 -- i2 } [
  0                 comp_clobber
  0 0 1 asm_add_reg comp_instr
  1                 comp_args_set
] ;

\ brk 666
: abort [
  0b110_101_00_001_0000001010011010_000_00 comp_instr
] ;

Easy AOT compilation; can be used from inside a program, or via CLI flags:

: main { -- exit }
  " hello world!" log lf
  0
;

xt' main           \ Reference to the entry point.
" out.exe"         \ Where to put the executable.
compile_executable

\ Run `./out.exe` in your shell to print the message.

Why

Always extensible

Most languages ship with a smart, powerful, all-knowing compiler with intrinsic knowledge of the entire language. I feel this approach is too inflexible. It makes the compiler a closed system. Modifying and improving the language requires changing the compiler's source code, which is usually over-complicated.

On top of that, most languages isolate you from the CPU, or even from the OS, from the get-go. Instead of giving you access to the foundations, and providing a convenient pre-built ramp to the high clouds, all you get is high clouds.

Astil Forth explores the opposite direction. The interpreter / compiler provides only the bare minimum of intrinsics for controlling its behavior, and leaves it to the program to define the rest of the language.

This is possible because of direct access to compilation. Outside the Forth world, this is nearly unheard of. In the Forth world, this is common and extremely powerful. For an elegant and enlightening read, look at Frugal Forth, which implements if/then/else conditionals in 3 lines of user/lib code, with very little compiler support. (Astil Forth also implements conditionals without compiler support, and makes them much nicer to use, but uses more code.)

Unlike Frugal and mature systems such as Gforth, Astil Forth goes straight for machine code. It does not have a VM, bytecode of any kind, or even an IR. I enjoy the simplicity of that, despite the non-portability.

The system comes in two variants which use different call conventions: register-based and stack-based. For code simplicity reasons, they compile separately, from differently selected C files. The stack-CC version is legacy and has fewer features.

The outer interpreter / compiler, written in C, doesn't actually implement Forth. It provides just enough intrinsics for self-compilation. The Forth code implements the language, on the fly, bootstrapping via inline assembly.

Always fast

Most languages lock into one execution model: either interpretation/JIT, or AOT compilation. This causes friction. Interpreted languages are nicer for scripting, prototyping, iterating. Compiled languages produce faster code and make deployment easier (just a binary), but compilation slows down development. How many projects were rewritten in C++ after starting in Python? And Java is the worst joke; wait for "compilation", only to find out you need an interpreter for the resulting image.

Astil Forth proves that combining interpretation/JIT and AOT compilation in one language is easy, practical, and useful. We could end the "language split".

In development, Astil is a scripting language with instant startup and feedback. For "production", it builds a standalone executable, deployable as-is, and without any interpreter inside.

Some other scripting languages offer "compilation", but it's almost never the real deal. Some examples:

  • Gforth builds a VM image file, which requires the interpreter.
  • Deno and Bun bundle an interpreter when building an executable.

Some recent AOT languages offer comptime execution, which is a nice step towards bridging the gap. Examples include Nim and Zig. Unfortunately, to the best of my knowledge, they do this with interpretation, not compilation, limiting the usefulness. Bun's sources (Zig) have comments like "this used to be calculated at comptime, but too slow, so we moved this to runtime". Astil Forth avoids this problem: "comptime" execution uses assembled code, not an interpreter.

Fun note. AOT compilation in Astil Forth might be the "fastest" of any language, because it simply dumps the already JIT-compiled code of your program (plus data and dyld symbols) into an executable file. At the time of writing, it takes about a millisecond for simple programs.

Easy C interop

It's trivial to declare and call external procedures, such as dynamically linked libc stuff. Examples can be found in the core files ./forth/lang.af and ./forth/lang_s.af.

The reg-CC version of Astil Forth, the default one, uses the native calling convention of the target platform, matching C. Its words can be passed to C by raw instruction addresses, and just work. In addition, it lets you define structs which match the C ABI. This allows perfect interop. See ./examples.

\ The numbers describe input and output parameters.
1 0 extern: puts
2 1 extern: strcmp

: main
  " hello world!" puts
  " one" " two" strcmp .
;
main

Exceptions done right: ABI compatibility

When using the register-based calling convention, you can opt out of exceptions inside any procedure. This reveals all error values, transforming them from exceptions. It's an implicit "catch" with procedure-level granularity.

: word [ true catches ]
  word0 {           err }
  word1 { val0      err }
  word2 { val1 val2 err }
;

Under the hood, an exception is a Go-style error value, implicitly appended to the success outputs. By default it's invisible and treated as an exception. When you "catch", the compiler reveals the error value, and skips the instructions it would normally insert to handle the error. A call becomes Go-style, as shown above. The caller has to check the error.

The resulting system is an exact inverse of Go (and Rust). By default, errors are exceptions and don't clutter the code. When you want explicit errors, it's for real, without hidden panics. There is no separate panic mechanism, no stack unwinder. At the ABI level, caller code always has local control.

The best part is cross-language ABI compatibility. Having exceptions without a runtime or unwinder means that other languages can seamlessly call our functions and handle returned errors. We can pass callbacks to libc and guarantee no surprises, such as a panic handler unwinding the C stack.

CLI

With global installation:

make install

# Get some instructions:
astil --help

# Register-based calling convention:
astil std:lang.af -  # REPL mode.
astil some_file.af   # One-shot run.
astil some_file.af - # Run file, then REPL.

# Stack-based calling convention:
astil_s std:lang_s.af - # REPL mode.
astil_s some_file.af    # One-shot run.
astil_s some_file.af -  # Run file, then REPL.

Don't forget to import' std:lang.af (or lang_s.af for stack-CC) inside your program, or on the command line. Without it, the language does not exist.

The REPL is barebones. For a better experience, using rlwrap is recommended:

rlwrap astil std:lang.af -

# Or use this shortcut from repo root:
make repl

Compile executables via --build:

astil my_program.af --build=out.exe
./out.exe

Local-only usage inside this repo:

make
./astil.exe
./astil_s.exe

Rebuild continuously while hacking:

make clean build_w

When debugging weird crashes, the following can be useful:

make debug_run '<file>'
make debug_run '<file>' DEBUG=true
make debug_run '<file>' TRACE=true
make debug_run '<file>' RECOVERY=false

Structure

  • ./forth:
    • lang.af — language core.
    • testing.af — simple testing utils.
    • Other files — optional small libraries; mostly interfaces to libc IO.
  • ./examples — how to use libc for IO, networking, threading.
  • ./comp — outer interpreter / compiler in C. Mostly library-style code with a small "main" entry point.
  • ./talks — presentation "slides" for the talks I gave in SVFIG about Astil Forth.
    • For now, this is the substitute for documentation, especially the February talk.
  • ./sublime — editor support for Sublime Text.

Sublime Text

Due to divergence from the standard, this dialect prefers its own syntactic support. This repository includes a syntax implementation for Sublime Text. To enable, symlink the directory ./sublime into ST's Packages. Example for MacOS:

ln -sfn "$(pwd)/sublime" "$HOME/Library/Application Support/Sublime Text/Packages/astil_forth"

Note that for standard-adjacent Forths, you should use the sublime-forth package, which is available on Package Control.

Library

Should be usable as a library in another C/C++ program. The "main" file is only a tiny adapter over the top-level library API. See comp/main.c.

In this codebase, all C files directly include each other by relative paths, with #pragma once. It should be possible to simply clone the repo into a submodule and include comp/interp.c which provides the top-level API and includes all other files it needs.

Many procedure names are "namespaced", but many other symbols are not; you may need to create a separate translation unit to avoid pollution. Almost every procedure is declared as static.

Tricks and optimizations

I consider this a "mildly optimizing" compiler. It maintains the convenience of single-pass self-assembly while employing several tricks compatible with it. Some are detailed in a "slide" for the February SVFIG presentation.

In both reg-CC and stack-CC:

  • Avoid emitting unnecessary prologue and epilogue.
  • Inline small leaf procedures.
  • Delay undecidable instructions, patch them in a fixup pass.
    • Used for prologue, ret try throw recur, and more.

In reg-CC:

  • Place inputs and outputs in registers, matching the native call ABI.
  • Prefer to keep locals in registers.
  • Relocate locals lazily and only when necessary.
  • Elide relocations of parameter locals when possible.
  • Associate locals with param regs, reuse when possible.
  • Keep track of clobbers, preserve caller-saved registers when possible.
  • ...Other small tricks. Some are word-specific.

Performance

See ./bench. In the few available microbenchmarks, the reg-CC version of Astil Forth vaguely approximates Clang C with -O2, while leaving Gforth in the dust. Needless to say, this shouldn't be over-generalized. The compiler is simple, stupid.

Limitations

Simplicity vs optimization

A core premise of this system is forward-only single-pass compilation. This keeps it simple, while still allowing a degree of low-hanging optimizations, such as basic register allocation and inlining. Some instructions are reserved in the first pass, and patched in a fixup post-pass.

This approach is at odds with most advanced compiler optimizations, which rely on building and analyzing intermediary representations before assembling. Complex compilers end up with multiple IR levels, and multiple passes. Complexity interferes with self-assembly; simply vomiting instructions into the procedure body no longer suffices; the code must now emit the first-pass IR instead of regular instructions.

I had a go, and bounced off the complexity. How to keep an optimizing compiler simple?

Other limitations

  • Currently only Apple Silicon (MacOS + Arm64).
  • Vocabulary / stdlib is somewhat limited.
  • Exceptions print only C traces, not Forth traces. (Opt-in via --trace.)

Non-standard

For the sake of my sanity and ergonomics, Astil Forth does not follow the ANS Forth standard. It improves upon it.

Words are case-sensitive.

Numeric literals are unambiguous: anything that begins with [+-]?\d must be a valid number followed by whitespace or EOF.

Non-decimal numeric literals are denoted with 0b 0o 0x. Radix prefixes are case-sensitive. Numbers may contain cosmetic _ separators. There is no hex mode. There is no support for & # % $ prefixes.

Many unclear words are replaced with clear ones.

More ergonomic control flow structures:

  • All conditionals and loops are terminated with end. No need to remember other terminators. (until is also available.)
  • elif / elifn is supported.
  • Any amount of else elif is terminated with a single end.
  • Any amount of leave or while is terminated with the same end as the loop.

Because the system uses native procedure calls, there is no return stack; see below.

There is no state or does>. Instead, the system uses two wordlists:

  • "exec" — execution-time words; not immediate.
  • "comp" — compile-time words; immediate.

Each word can be defined twice: an "exec" variant and a "comp" variant. In compilation mode, the "comp" variant is used first. In interpretation mode, the "exec" variant is used first. When finding a word by name, the caller must choose the wordlist, and thus the variant.

Exceptions are strings (error messages) rather than numeric codes.

Booleans are 0 1 rather than 0 -1.

Modifier words like catches and comp_only can only be used inside colon definitions.

Special semantic roles get special syntactic roles:

  • Word-parsing words which declare end with :.
  • Word-parsing words which don't declare end with '.
  • Unusual control-related words begin with # or use the T{ }T naming style.

Examples:

  • Words which declare: : :: let: var: to: and more.
    • Syntax highlighters are encouraged to scope the next word like a declaration.
  • Parsing words: xt' postpone' compile'.
    • Syntax highlighters are encouraged to scope the next word like a string.
  • Unusual control words: vargs{ }vargs.
  • Well-known control words don't use special characters: if else end ret and several more. Syntax highlighters should hardcode them.

Special syntax highlighting is also recommended for ( ) [ ] { } inside word names. These are commonly used as delimiters, like T{ }T.

No return stack

Because Astil Forth targets Arm64 and assumes an OS, the role of the return stack is fulfilled by registers and the system stack.

Reg-CC emphasizes named local variables. Locals are kept in registers when possible, and spilled to the system stack otherwise. The compiler figures out the locations.

Stack-CC always spills locals to the system stack.

Both conventions make use of temp registers for scratch space.

Why so much C code

Because I was learning and experimenting. Some of the code is generalized library stuff, checks and error messages (safety and UX), debug logging, code which is relevant but currently unused, and the code-split of supporting two calling conventions.

Lessons

  • Partial self-bootstrap is possible.
  • Partial self-assembly is possible.
  • Single-pass assembly is possible (with fixups 😔).
  • Single-pass assembly is compatible with basic optimizations, such as simple register allocation and limited inlining.
  • Single-pass assembly is incompatible with advanced optimizations.
  • Single-pass assembly with fixups scales to a point.

When the system is simple, single-pass compilation (with fixups) seems to be a simpler choice. After a certain level of complexity, an IR-based multi-pass approach starts to look simpler. I feel like this system is just before that threshold.

What is JIT

The term "JIT" is used here only for convenience. This doesn't assemble "just" in time; it assembles immediately. Saying "JIT" is just the most compact way to indicate on-the-fly assembly as opposed to interpretation. In the Forth world this is common, usually without buzzwords.

What is compilation

"Compilation" and especially "JIT compilation" are muddy terms. Many interpreters convert text to VM code, which may qualify as JIT compilation, even if the result remains interpreted. In the Java world, generating VM code files is considered "compilation".

Especially murky in the Forth world. Docs will often mention compilation, and sometimes decompilation, usually without saying what it compiles to and decompiles from: VM code or machine code. Some Forth systems use both; some stop at VM code; Astil Forth uses only machine code. Yet all these systems qualify as "compilers".

Sometimes it's useful to describe a non-assembler as a "JIT compiler". For example, one of my Go libraries implements JIT-construction of data structures which, when subsequently interpreted, allow efficient deep traversal of complex Go data structures; it delegates setup to "compilation time" and eliminates many costs at "runtime", although both steps occur when the program runs, and the result is interpreted.

Perhaps we should differentiate "JIT compilers" and "JIT assemblers". But at the end of the day, everything is interpreted, one way or another.

Name

The name Astil references a sentient magic grimoire from one anime I watched. A book of magic words. Fitting for a Forth, don't you think?

License

https://unlicense.org

About

A Forth JIT & AOT compiler designed for self-assembling and self-bootstrapping.

Topics

compiler jit aot forth abi self-assembly self-bootstrapping

Resources

Readme

License

Unlicense license
Activity

Stars

11 stars

Watchers

1 watching

Forks

1 fork
Report repository

Contributors 1

Languages