# The Cryn Programming Language

Cryn is a compiled systems programming language built on a very small and
unusual core: **cells, connections, focus, a working value, and a value
stack**. There are no symbolic operators, no braces, no semicolons, and no
indentation rules. Programs read like small English sentences describing
operations on a machine:

```text
define main
    set 10
    push
    set 20
    add
    output
    return
end
```

This compiles to a native executable through either of two backends:

```text
Cryn source -> lexer -> parser -> AST -> semantic analysis -> Cryn IR
           -> optimizer -> C backend    -> host C compiler -> executable
                       -> native backend -> ELF (x86-64)  -> executable
```

The C backend emits a self-contained C11 translation unit and hands it to
the host C compiler (the portable reference path). The native backend
lowers the IR directly to x86-64 machine code and writes an ELF executable
itself. No C compiler, linker, or CRT objects are involved at program
build time; the host C library is linked dynamically as the system-call
interface.

The bootstrap compiler (`cryn`) is written in portable ISO C11 and has no
dependencies beyond a C compiler, pthreads, and libm (`fmod`, used by
float `remainder`).

---

## Design philosophy

> C-level power through a radically small set of composable primitives.

* **38 commands total.** No `if`, `while`, `for`, `switch`, `array`,
  `struct`, `class`, or `pointer` keywords. Control flow is explicit
  jumps; arrays are indexed connections; structures are blocks of memory;
  pointers are address values.
* **Whitespace has no meaning.** Every program can be written on one line.
  Blocks end with `end`.
* **One comment syntax:** `[# ... #]`, possibly spanning lines.
* **English words instead of symbols:** `add`, `compare`, `jump ... when
  less`, `move`, `write`.
* **The graph model is the semantics; the compiler lowers it.** Cells and
  connections are what the language means; the compiler compiles them into
  ordinary locals, arrays, and pointer arithmetic, so Cryn code runs at
  native speed with no graph overhead.
* **Static typing with defined behavior.** Fixed-width integer and float
  types, defined overflow (wrap), defined division by zero (diagnostic
  abort), saturating float-to-int conversion, bounds-checked indexing.
* **No hidden runtime.** The runtime support layer is a few hundred lines:
  allocation headers, context structs, a per-context file-handle table,
  thread spawn/join, atomic access helpers, and output formatting. Every
  dependency is documented in this README.

See the [project wiki](https://vextoly.lgbt.sh/cryn/wiki/) for
the formal language reference
([Language Reference](https://vextoly.lgbt.sh/cryn/wiki/language-reference.php)),
a course from first principles
([Learning Cryn](https://vextoly.lgbt.sh/cryn/wiki/learning-cryn.php)),
and the compiler internals
([Architecture](https://vextoly.lgbt.sh/cryn/wiki/architecture.php)).
The `wiki/` folder holds the sources of those pages.

## Repository layout

```text
src/
    main.c       CLI entry point (build / run / check / emit-c / emit-ir)
    util.[ch]    buffers, lists, file I/O
    diag.[ch]    diagnostics (file:line:col reporting)
    lex.[ch]     lexer: keywords, literals, comments, locations
    ast.h        AST node definitions
    parse.[ch]   recursive-descent parser (formatting independent)
    types.[ch]   interned type objects, sizes, classifications
    check.[ch]   semantic analysis: abstract machine interpretation,
                 produces fully typed IR (src/check.c is the semantic heart)
    ir.h         Cryn IR instruction definitions
    opt.[ch]     IR cleanup: unreachable code and dead label removal
    be_c.[ch]    C backend: emits a self-contained C11 translation unit
    be_x64.[ch]  native x86-64 backend: lowers the IR to machine code and
                 writes an ELF executable directly (host libc via a
                 hand-built GOT; musl and glibc `_start` conventions)
    rt/
        cryn_rt.h    minimal runtime interface (embedded into output)
        cryn_rt.c    runtime implementation
    rt_src.h     generated: runtime sources as strings (tools/embed)
tools/
    embed.c      turns runtime sources into string headers
wiki/            sources of the published wiki pages: Home, Learning-Cryn
                 (TUTORIAL.md), Language-Reference (LANGUAGE.md),
                 Architecture (ARCHITECTURE.md)
tests/
    *.cryn       test programs
    expected/    expected outputs
    input/       stdin fixtures
    errors/      programs that must fail to compile
    run.sh       test runner
examples/        hello, fib, fizzbuzz, sorting, wordcount, linkedlist,
                 allocator
```

The frontend (lexer/parser/AST), the semantic layer (types/check), the IR,
and the backend (be_c) are cleanly separated. A native code backend can be
added by translating `src/ir.h` instructions directly; nothing in the
semantic layer is tied to C generation.

## Building

```sh
make              # builds ./cryn
make test         # runs the test suite (C backend)
make test-release # runs the test suite in release mode (no bounds checks)
make test-native  # runs the test suite through the native x86-64 backend
make clean
```

Requirements: any ISO C11 compiler and POSIX `make`. pthreads is required
for `spawn` / `wait` support.

## Using the compiler

```sh
cryn hello.cryn              # compile to executable "hello"
cryn build hello.cryn -o out # compile to executable "out"
cryn run hello.cryn          # compile and execute
cryn check hello.cryn        # type check only
cryn emit-c hello.cryn -o out.c   # write the generated C
cryn emit-ir hello.cryn      # print the Cryn IR
cryn help
cryn version
```

Both `build` and `run` accept `--release` (no runtime bounds checks;
statically provable checks are always eliminated at compile time) and
`--native` (emit an x86-64 ELF executable directly instead of generated C;
Linux, System V ABI, dynamic host libc).

`cryn` invokes the host C compiler (`$CC`, default `cc`) with
`-O2 -std=c11 -pthread` to turn generated C into an executable. Generated
programs are normal executables and need no Cryn runtime at runtime; the
runtime is compiled into every generated translation unit. With `--native`
no host C compiler is needed at all.

## How the compiler works

1. **Lexing** (`lex.c`): comments are stripped as `[# ... #]`; whitespace
   (including newlines) is skipped everywhere; line/column tracked for
   diagnostics.
2. **Parsing** (`parse.c`): recursive descent over the token stream.
   Transformation parameters are `{ type name }` pairs terminated by the
   first non-type token, which keeps parsing unambiguous without any
   punctuation.
3. **Semantic analysis** (`check.c`): an abstract interpreter over the
   Cryn machine. It tracks the static type of the working value, the
   abstract focus stack, the value stack shape, and comparison state, and
   merges these states at every label. All merges must agree exactly
   (integer literals widen to the type they fit). It also infers result
   types, resolves all names, checks argument counts/types, and emits the
   fully typed IR in one pass. Recursive transformations with unclear
   results must declare `result <type>`.
4. **IR** (`ir.h`): 50 typed instructions (navigation, value ops, memory
   access, comparisons, calls, external operations, atomics).
5. **Optimizer** (`opt.c`): removes unreachable code and unreferenced
   labels. (Deliberately small; the C compiler performs the heavy lifting
   on the readable C we emit.)
6. **C backend** (`be_c.c`): each transformation becomes a C function;
   frame cells become C locals; `move` becomes pointer assignment; value
   stack and focus history live in a per-thread context struct. The
   runtime sources are embedded and emitted into every translation unit,
   making the output a single self-contained `.c` file.
7. **Native backend** (`be_x64.c`): the same IR lowered straight to
   x86-64. Each transformation gets a frame of callee-saved machine state
   (`r12` comparison, `r13` focus, `r14` context, `r15` working value);
   the runtime helpers (value stack, focus, blocks with headers, streams,
   threads, float formatting) are emitted as machine code, and the writer
   produces a static ELF with a hand-built GOT and SysV hash table that
   links against the host C library for syscalls (stdio, malloc, pthreads,
   `fmod`, and `snprintf`/`strtod` so float output is byte-identical to
   the C backend). File handles, contexts, and block headers match the C
   runtime's semantics.

## Runtime dependencies (complete list)

The runtime (`src/rt/cryn_rt.*`) provides only:

| Facility        | Used by                          | Notes                          |
|-----------------|----------------------------------|--------------------------------|
| `malloc`/`free` | `make <size> of`, anonymous `make`, `free` | 16-byte header for sizes plus a mutex-protected registry of live blocks; validation of stale addresses is defined, never undefined reads |
| value stack     | `push`, `pop`, `swap`, `call`    | growable array, per thread     |
| focus history   | `move` (relative), `back`, `home`| fixed 1024 entries per context (shared across active frames) |
| FILE* streams   | `input`, `output`, `open`, `use`, `close`, `flush`, `seek`| stdin/stdout by default; `use` routes the context's streams through a handle; `seek` positions handle streams at a byte offset |
| `system()`      | `system`                         | shell escape                   |
| pthreads        | `spawn`, `wait`                  | join is an ordering guarantee  |
| formatting      | `output`                         | shortest round-trip float printing |
| relaxed atomics | all scalar loads/stores          | races yield unspecified values and never tear ([Language Reference](https://vextoly.lgbt.sh/cryn/wiki/language-reference.php)) |
| acq_rel atomics | `exchange`                       | indivisible swap of working value and focused cell; the only ordering primitive besides `wait` |

There is no garbage collector, no interpreter, and no mandatory runtime
library beyond the above.

## Testing

```sh
make test           # C backend
make test-release   # release mode: bounds checks removed
make test-native    # native x86-64 backend
```

48 checks each: arithmetic (including overflow wrap and division edge
cases), unsigned arithmetic, floats (including `remainder`/fmod and
NaN), all six comparison conditions, branches, loops, nested loops,
functions, recursion, mutual recursion, the value stack, cells and focus
navigation, arrays (sieve of Eratosthenes), strings, manual memory,
pointer arithmetic, linked lists, callbacks through transform references,
file I/O with first-class handles (two files interleaved, append mode,
flush), `seek` repositioning an `open both` stream (interleaved reads and
writes on one file), threads (`spawn`/`wait`), a spinlock built from
`exchange`, compare-and-swap built from `exchange` and `wait` (the
evaluation that closed further atomic primitives), a word counter, bubble
sort, a free-list allocator, a limits stress test (301 cells, 300 labels,
302-deep focus, 1100-deep value stack), and sixteen programs that must
fail to compile. Every run test passes under all three modes.

## Current limitations

These are honest boundaries of the first implementation, not pretenses:

* **Two backends.** The C backend is the portable reference and needs a
  host C compiler at build time. The native backend emits x86-64 ELF
  directly (Linux, System V ABI, musl or glibc host libc; the interpreter
  path and the libc SONAME are detected at compile time, override with
  `CRYN_INTERP`). Other targets stay on the C backend.
* **Concurrency is minimal.** `spawn` starts a thread running a
  zero-parameter transformation; `wait` joins all spawned contexts of the
  current one. Shared world cells may be accessed concurrently; a race
  on an aligned ≤ 8-byte cell yields an unspecified value of the cell's
  type and never tears (scalar access is lowered as relaxed atomics).
  The only ordering guarantees are `wait` (join) and `exchange`
  (an acquire-release atomic swap of the working value with the focused
  cell; enough to build locks). Communication of results happens
  through shared world cells.
* **File handles are plain integers scoped to one context.** `open`
  returns a handle (1 to 256 per context, -1 on failure; `read`, `write`,
  `both`, and `append` modes). `use` routes the context's streams
  through a handle: the readable side to input, the writable side to
  output; `use 0` returns to the standard streams. A spawned context
  cannot use its parent's handles, and closing a handle frees its
  number for reuse.
* **Indirect calls** (through `transform` references) are only allowed to
  zero-parameter transformations; checked at runtime when the reference is
  not statically known. The callee's result is discarded and the caller's
  working value (the reference) is preserved; results flow through world
  cells or addresses.
* **Bounds checks abort** with a diagnostic in the default mode. Release
  mode (`--release`) removes them; statically provable checks (literal
  indices into static arrays, and literal indices provably within a
  block's size) are eliminated at compile time in every mode.
* **Fixed limits:** 1024 focus history entries, 4096 labels, 4096 cells
  per transformation, 4096 provable value stack depth, 256 concurrent
  spawns per context, 256 open files per context. A single
  `make <size> of` allocation is capped at 16 TiB (the cap is
  overflow-safe in bytes, not elements); the type table is bounded only
  by memory.
* **No separate compilation** yet: one `.cryn` file per program.
* **The compiler itself is not yet written in Cryn.** Self-hosting is the
  remaining long-term goal; the architecture (small passes, plain data
  structures, no frameworks) was chosen for it.

## Contributing

* Keep the command count at or below 40. Before adding anything, prove it
  cannot be expressed with the existing primitives.
* Keep the compiler portable ISO C11; isolate platform specifics in
  `src/rt/`.
* Every language change needs: a test in `tests/`, updated wiki sources
  (`wiki/LANGUAGE.md`, published as
  [Language-Reference](https://vextoly.lgbt.sh/cryn/wiki/language-reference.php),
  and `wiki/TUTORIAL.md`, published as
  [Learning-Cryn](https://vextoly.lgbt.sh/cryn/wiki/learning-cryn.php)),
  and a note in this README if it affects the runtime surface.
* Run `make test`, `make test-release`, and `make test-native` before
  committing.

## Future work

1. Self-hosting: rewrite the compiler in Cryn (the C backend bootstraps
   the port; the native backend then keeps the toolchain C-free).
2. Extend the native backend beyond Linux/x86-64 (static PIE, more
   libc targets) as demand appears; the C backend covers everything
   else.

Done from the original list: the native x86-64 backend (`--native`),
release mode with compile-time elimination of statically provable bounds
checks (`--release`), file positioning (`seek`) for `open both` streams,
and the atomic-primitives evaluation: compare-and-swap and atomic
arithmetic build from `exchange` and `wait` alone
([tests/32_cas.cryn](tests/32_cas.cryn) is the proof), so no new
primitive was added.