Skip to content

mitranim/astil_forth

BranchesTags

Repository files navigation

TOC

Overview

Astil Forth is an experimental system which uses Forth as a model for exploring self-bootstrapping, self-assembly, and a unified JIT & AOT execution model. Currently supports only Arm64 + MacOS.

Goals:

  • Explore combined JIT execution & AOT snapshotting.
  • Explore self-bootstrap: defining language on the fly in itself.
  • Explore self-assembly in user/library code.
  • Explore single-pass assembly (with fixups).
  • Be usable for scripting.
  • Support direct C interop.
  • Avoid a VM or complex IR.
  • Keep compiler clear for compiler amateurs.
  • Eventually rewrite in Forth to self-host.

Non-goals:

  • Following other compiler designs.
  • Portability to multiple ISAs.
  • ANS Forth compatibility.
  • Complex optimizations.
  • Complete stdlib.

No dependencies (other than libc). Uses custom assemblers in both C and Forth code.

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:

use' lang.af

fun: run
  " hello world!" .log .lf

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

  0 { ind }
  loop
    ind 12 < .while
    " current number: %zd" ind .logf .lf
    inc: ind
  end
end

.run

Easy self-assembly (Arm64):

\ add Xd, Xn, Xm
fun: 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
end

\ add x0, x0, x1
fun: + { i0 i1 -- i2 }
  [
    0                  .comp_realloc_reg
    0 0 1 .asm_add_reg .comp_instr
    1                  .comp_args_set
  ]
end

\ brk 666
fun: abort
  [
    0b110_101_00_001_0000001010011010_000_00 .comp_instr
  ]
end

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

fun: run { -- exit }
  " hello world!" .log .lf
  0
end

fun: main { -- exit } .with_main_ctx .run end end

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.

Traditional style : word ; is also availble, but fun: word end is preferred for stylistic reasons and consistency with control structures, which are also terminated with end.

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. See ./forth/lang.af.

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, in barely a page of code, and makes them much nicer to use than standard Forth.

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 functions, 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) uses the native calling convention of the target platform, matching C. Extern functions can be called directly, and just work.

AF words can be passed to C by raw instruction addresses, and in many cases, they just work. See Memory management for the edge cases involving ambient context.

AF also lets you define structs which match the C ABI. See ./examples using that.

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

fun: run
  " hello world!" .puts
  " one" " two" .strcmp .show
end
.run

Errors done right: simplicity with ergonomics

Astil Forth uses plain error outputs while making them as ergonomic as exceptions.

  • Errors are plain outputs.
  • Local shortcuts "try" and "throw" inside functions.
  • Opt-in auto-"try" inside functions.
  • No need for "catch".
  • Errors are part of regular call ABI.
  • Interoperable between languages.
  • No unwinder; all control is local.

By convention, errors are C-strings, but there's no type restriction:

" err_msg" { err } \ Error as message.
123        { err } \ Error as code.

Naming a trailing output exactly err or Err tells the compiler it's an error:

fun: always_fails { -- err } " err_msg" end

For ergonomics, compiler auto-zeroes the error output if you don't explicitly return it:

fun: always_succeeds { -- val err } 234 end \ implicit nil error

.throw returns an error; other outputs are undefined. Handy in multi-output functions. "Throw" is entirely local; it's just a variant of "return":

fun: some_word { -- out0 out1 err }
  if fail .then
    " err_msg" .throw \ x0 x1 x2 = junk junk err
  end
  123 234 \ x0 x1 x2 = 123 234 nil
end

When all outputs must be defined, just return instead:

fun: some_word { -- out0 out1 err }
  if fail .then
    nil nil " err_msg" .ret
  end
  123 234 \ implicit nil
end

Returned errors are visible by default:

fun: caller
  .always_fails { err }
  err .elogf .elf
end

Forwarding trailing errors just works:

fun: caller { -- Err } .always_fails end

.try consumes and tests errors, returning non-nils early:

\ Worse:
fun: some_word { -- out Err }
  .word0 { err }           if err .then nil err .ret end
  .word1 { val0 err }      if err .then nil err .ret end
  .word2 { val1 val2 err } if err .then nil err .ret end
  val0 val1 val2 + *
end

\ Better:
fun: some_word { -- out Err }
  .word0 .try
  .word1 .try { val0 }
  .word2 .try { val1 val2 }
  val0 val1 val2 + *
end

Naming trailing output exactly lowercase err enables local auto-try within current function, eliminating all visible error handling. The external behavior is identical to Err:

fun: some_word { -- out err }
  .word0
  .word1 { val0 }
  .word2 { val1 val2 }
  val0 val1 val2 + *
end
  • Callee decides whether to return an error via err|Err; this is external ABI.
  • Caller decides whether to auto-try internally via err; this is local convenience.
  • No "catch"; in error-sensitive code, simply don't auto-try.

Return states:

  • Success: return non-error outputs; nil err is implicit.
  • Partial failure: return non-error outputs and non-nil err.
  • Total failure: use .throw / .try; non-error outputs are undefined.

Callers, including C/FFI callers, must check errors before using regular outputs, unless callee documents partial-failure contract.

The resulting system is a hybrid between C/Go/Swift/exception styles:

  • Like C: control is always local; FFI-compatible ABI.
  • Like Go: multi-outputs; error is last; prefer strings with useful context.
  • Like Swift: implicit nil errors; try throw shortcuts.
  • Like exceptions: opt-in auto-try.

Special note on ABI. Astil Forth uses an FFI-compatible multi-output call ABI with defined error lifetimes. Error strings are allocated either statically, or in the current ambient memory context; see Memory management.

AF functions which don't depend on ambient memory context can be passed as callbacks to libc, and just work. qsort callbacks are a good example.

All of the above is reg-CC only, and doesn't quite apply to stack-CC, which always treats errors as exceptions and provides catch'.

CLI

With global installation:

# (Choose between perf and debug.)
make install PROD=true
make install

# Get some instructions:
astil --help

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

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

# One-off scripts via CLI arg or stdin pipe; example for reg-CC:
astil lang.af --eval='10 20 + .show'
printf '10 20 + .show\n' | astil lang.af -

Don't forget to import lang.af via use' lang.af (or use' lang_s.af for stack-CC) inside your program, or via CLI args.

Note on "use": absolute or explicitly-relative paths are resolved against the current file (PWD in REPL); unprefixed paths are "standard library" only.

Compile executables via --build:

astil <file> --build=out.exe
./out.exe

The file must define an AOT entry main; code which needs ambient context should use .with_main_ctx as shown in Memory management.

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

rlwrap astil lang.af -

# Or use this shortcut from repo root:
make repl

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

Memory management

Astil Forth doesn't have GC or memory-related compiler magic. Technically, memory is managed manually.

AF simplifies MM in two ways:

  • Caller-owned arenas.
  • Ambient memory context.

AF dedicates one register (x28) to the ambient context, available anywhere via the word context. See the type Ctx for the structure's definition.

The context acts as a bump-allocator over borrowed caller-owned memory. It's used by words like strf, which need thread-specific scratch memory.

The outer compiler automatically sets up the main arena. In JIT, it also sets up the main context. In AOT, the main arena is memory-mapped automatically, but the context requires extra setup. General AOT pattern:

fun: run { -- exit }
  " hello %s" " world" .strf .log .lf
  0
end

fun: main { -- exit }
  .with_main_ctx .run end
end

The main arena can't be freed, but may be rewound by saving ctx_top and restoring it via ctx_top_set. Other arenas are caller-owned; callees may allocate, or restore a prior top; caller frees the whole thing:

fun: callee { -- str } " code: %zd" 123 .strf end

fun: caller { -- Err }
  alloca' Stack { mem } \ Locally-owned scratch memory.

  CTX_CAP Ctx mem .stack_init_ctx .try { ctx }

  ctx .with_ctx         \ x28 = inner scratch context.
    .callee .log .lf    \ Use scratch memory before freeing.
  end                   \ x28 = outer context.

  mem .stack_deinit     \ Unmap scratch memory.
end

with_ctx is structural, not unwind-safe. Its body must reach end; don't use .ret, .try, .throw, or local auto-try inside it. Call an inner function and capture its outputs outside the scope when early return is possible.

Every context object begins with Ctx, and may contain arbitrary extra fields. In JIT mode, the default ambient context is Interp*, which begins with the default Ctx. User code may define its own context types.

The shortcut stack_init_ctx maps a guarded Stack, allocates an arbitrarily-sized context struct at its floor, initializes its Ctx header, and returns its address. The context struct is owned by its own backing memory and shares the same lifetime.

When passing AF callbacks to foreign code, mind the context:

For callbacks which don't need the context (like qsort comparator), no special action; they just work.

Callbacks which use context require additional setup:

  • Either receive memory from parent, or map/unmap it locally.
  • Run the inner callback inside with_ctx ... end.

Joinable child threads require parent-owned memory for their context. Our forth/pthread.af provides the shortcut thread_spawn_ctx for joinable threads, and shows the needed closure + trampoline pattern for thread context setup.

Thread memory use is exclusive: while a child is running, parent is not allowed to use or unmap its memory.

Detached child threads set up the context internally. Our examples/http_echo.af shows the needed pattern for internal context setup; see handle_conn.

We currently don't support thread-local storage. Ambient contexts provide a similar-enough solution, designed for parent-owned memory which outlives the child. The differences between our approach and TLS are mostly in the implementation; the current solution is simpler and requires less OS-specific machinery. We may bridge this gap in the future.

Structure

  • ./forth:
    • lang.af — language core.
    • 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 function names are "namespaced", but many other symbols are not; you may need to create a separate translation unit to avoid pollution. Almost every function 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 functions.
  • 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.
  • Fold comptime constants in most arithmetic words.
  • Some peephole instruction fusion.
  • ...Other small tricks. Some are word-specific.

Register allocation and greediness

In reg-CC, inside each word, the compiler uses volatile registers x0 … x15 as a stack. Example: 10 20 30 lands in x0 x1 x2.

This matches the platform call ABI (Arm64 only for now). Runtime calls are greedy: a 3-input call requires the current stack to be exactly x0 x1 x2, consumes it, and resets the stack to the callee's visible outputs, again starting at x0.

To keep values between runtime calls, stash them into locals:

.runtime_word_0 { one two three }
.runtime_word_1 one + two + three +

Comptime words operate at the top of the stack. That enables true concatenative compiled code; in 10 20 + 30 40 - *, + - * consume/replace top registers and fold constants when possible.

Register allocation for locals is trickier and smarter. They often need relocation, but final destinations are unknown until end of current word definition. The compiler reserves instructions, builds a list of pending relocations, and patches them in a fixup pass. This allows us to preserve the single-pass compilation strategy. The compiler employs several tricks to elide unnecessary relocations.

Performance

See ./bench. Summary: in these very limited microbenchmarks, the reg-CC version of Astil Forth trounces VM interpreters, approximates other JITs, and vaguely approximates Clang C with -O2. 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 function 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).
  • Top-level exceptions print only C traces, not Forth traces. (Opt-in via --trace.)

Call syntax

TLDR: nouns and verbs look distinct and the compiler enforces that.

Longer version:

Source code consists of whitespace-separated words. Aside from numeric literals, source words have two spelling classes:

  • Value-like spelling: [A-Za-z_][A-Za-z0-9_]*.
  • Call-like spelling: every other non-numeric word.

Locals and global values use value-like spelling:

123 let: SOME_GLOB

fun: some_fun
  SOME_GLOB { some_loc }
  some_loc { -- }
end

Calls use call-like spelling. Names such as +, !b, u/mod, fun:, and xt' are automatically call-like. Ident-like names become call-like via dot prefix: .logf calls logf. The dot is special and not part of actual names:

fun: log_num { val }
  " %zd" val .logf .lf
end

1 0 extern: exit
0 .exit

Control words which don't deal with runtime args stay plain. Control words which use or affect args use dot-call:

if 123 .then 234 else 345 end
loop predicate .while body again end
err .try
err .throw
val .ret
.recur

Examples of control-only words: if ifz elif elifz else loop leave again assert end. leave and again validate loop arity, but stay plain.

In file root, .ret simply quits the current file. Inside a compiled word, .ret returns current args as outputs. Even nullary .ret requires a dot.

The call syntax rules apply only to reg-CC (default/main language). Stack-CC doesn't have these nuances.

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 goes through the numeric parser and must be followed by whitespace or EOF. Only decimals may use -.

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.

Words are preferred over punctuation (except delimiters):

' -> xt'
: -> fun:
; -> end

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.
  • Conditionals take the form if .then else end, which reads much nicer.
  • elif is supported.
  • Any amount of conditional branches is terminated with a single end.
  • Any amount of leave or .while is terminated with the same end as the loop.

Reg-CC supports exactly one loop form: loop … end, with leave .while again auxiliaries. Other loop forms don't buy anything.

loop
  predicate .while
  body
  if done .then leave end
  if skip .then again end
end

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

  • "exec" — runtime words; not immediate.
  • "comp" — comptime 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.

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

Booleans are 0 1 rather than 0 -1.

Word-modifiers like .comp_only are used inside definitions, not outside.

Special semantic roles get special syntactic roles:

  • Words which declare: fun: let: var: to: and more.
    • Syntax highlighters are encouraged to scope the next word like a declaration.
  • Parsing words: use' xt' postpone' compile'.
    • Syntax highlighters are encouraged to scope the next word like a string.
  • Calls use call-like spelling; see call syntax.
    • Syntax highlighters are encouraged to scope calls differently from values.
  • Modifier-style comptime words may begin with #; like #debug_ctx.
  • Structural control words may stay plain; syntax highlighters may hardcode common names such as if ifz else elif elifz end loop leave again assert.

Special syntax highlighting is also recommended for ( ) [ ] { } inside word names.

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.

Bot policies

The system is human-envisioned, human-designed, and was not touched by any bots during initial months of development.

Later, bots got employed for reviews and many mechanical refactorings. I tried labeling all bot-generated parts, but it became too much work. Just know that I focus highly on unslop. They're useful tools.

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

16 stars

Watchers

1 watching

Forks

1 fork
Report repository

Contributors

Languages