I have swapped the Swap instruction for the BitwiseNand instruction.

Add mutability checks so that immutable data can't be written to.

Add a test case to run all the examples and check against expected outputs.

LIR is cool, demonstrate some!

The LIR examples use several inlined-assembly procedures to access comparison, logical, and bitwise operators. Add the missing operators and swap out the new ones in the LIR examples.

I want to add parameterized types to the lower intermediate representation. I expect the architecture to look something like this.

// src/lir/types.rs

enum Param {
    Type(Type),
    Const(ConstExpr),
}

// ...

enum Type {
    // ...
    
    LetParam(Vec<(String, Vec<(String, Option<Type>)>, Box<Type>>)>, Box<Self>),
    Param(Box<Type>, Vec<Param>)
}

This way, the LetParam will be simplified in terms of the Let variant of the Type type.

let StackVec<T, N: Int> = unit StackVec = [T; N],
    List<T> = struct {
        data: T,
        next: &List<T>
    } in ...

Parameterized types can be substituted directly to an equivalent Let expression of types by converting them like so:

let List<T> = struct {
        data: T,
        next: &List<T>
    } in
        let x: List<Int> = ...

// becomes

let x: (let T = Int, MANGLED_LIST_T_NAME = struct { data: T, next: &MANGLED_LIST_T_NAME } in MANGLED_LIST_T_NAME) in ...

Whenever a parameterized type is instantiated, it checks if that specific instance of the type has already been instantiated. This prevents creating several copies of the type and possibly recursing infinitely.

If not, we drop in the type definition. This will create an in-line type definition with a mangled, unique name for that specific combination of type / const arguments.

Add instructions like Spawn which creates another tape head with its own independent state elsewhere on the tape which runs concurrently asynchronously.

LALRPOP has been a pain. Use Pest instead. Right now the frontend uses Pest, and the stages of IR use LALRPOP.

See tile

I changed the Inc and Dec operators to two new operators:

1. Index
2. Swap

Index looks at the tape, reads the value, and uses that as an index for a pointer stored in the register. The address of the cell at that index is stored in the register. For implementations that use tape indexes as pointers, like the interpreter, this operation is simply addition. For implementations where pointers do not increment by 1 (an implementation with real pointers), this is addition with a constant multiplier.

Swap simply swaps the value at the tape with the value in the register.

... or, maybe I'm the only person interested in computer programming languages who doesn't know what FFI stands for. In which case, just close this issue, I guess. I actually suspect that might be true, and didn't even look to see if anyone had opened an equivalent issue, because I thought it very unlikely. The trouble with "just [search] it" is that it's work, even if not very much.

I want to be able to see the turing tape in operation with a tape head using a neat graphic. Something like https://adam-mcdaniel.net/harbor

A Unit type traditionally means the None type in common nomenclature.

Currently, the Unit type in Sage is a type that enforces structural equality and nominal equality. A Unit(Meter, Int) is not equal to an Int, or a Unit(Kilometer, Int); it is only equal to another Unit(Meter, Int), where the inner types are structurally equal. An Int can be cast to a Unit(Meter, Int) and vice versa. This adds functionality to the type system to typecheck against using a "Meter" where a "Kilometer" is required, even though the data used to represent both the types is the same. It forces the user to perform the unit conversion at the type system level.

I'm thinking a name like Unique, or Nominal could be used instead.

Right now, the compiler will generate code with nested function definitions. This is fine by the virtual machine specification, but it makes it harder to compile the output code. Right now, neither the interpreter or C target call functions properly. In both implementations, functions are only defined when their definition is executed.

To fix this, we simply need to flatten the functions like so:

fn f0() {
    fn f1() {
        fn f2() {

        }
        fn f3() {
            fn f4() {
            }
        }
    }
}
// Becomes:
fn f0() {}
fn f1() {}
fn f2() {}
fn f3() {}
fn f4() {}

This can be done in the VM code, it doesn't have to be done in the frontend. This should just be a simple pass before we compile the code to a specific target.

Add LLVM backend as a target. Make it available through an optional feature flag like llvm-support or something; LLVM is an utterly massive dependency that I don't want to rely on. If performance isn't good enough, we can directly lower the psuedo-assembly-language to LLVM; this should achieve performance on par with other languages like C.

Fix all the dumb clippy warnings for src/target/c.rs!

Hi!

I test Profile-Guided Optimization (PGO) on different kinds of software - the current results are available here (with a lot of other PGO-related information). Since PGO helps with achieving better performance with many compilers (like Rustc, GCC, Clang, etc.) I think trying to optimize Sage with PGO can be a good idea. I did some benchmarks and want to share my results.

Test environment

• Fedora 39
• Linux kernel 6.6.9
• AMD Ryzen 9 5900x
• 48 Gib RAM
• SSD Samsung 980 Pro 2 Tib
• Compiler - Rustc 1.75
• Sage version: the latest for now from the main branch on commit 72b536f61ebb6332c57cf57fab9fe53b1e878c1d
• Disabled Turbo boost (for more stable results across runs)

Benchmarks

As a benchmark, I use built-in benchmarks with cargo bench command. For the PGO optimization phase, I use cargo-pgo with cargo pgo optimize bench. For the PGO training phase, I use the same benchmark with cargo pgo bench.

Results

I got the following results:

• Release: https://gist.github.com/zamazan4ik/09666344f7cb0ee92a69d4a14a8b50e6
• PGO-optimized compared to Release: https://gist.github.com/zamazan4ik/2adb489319886015c98e393cac5e2e57
• (just for reference) PGO-instrumented compared to Release: https://gist.github.com/zamazan4ik/ae10d0fa65fb4be599876735b7ef15a6

According to the tests, PGO makes things faster in Sage.

I need to note that enabling Link-Time Optimization (LTO) is generally a good idea too - this optimization works well together with PGO. I even performed some benchmarks where I compared LTO to Release: https://gist.github.com/zamazan4ik/6be63330d2c97b510fdfc6b7aa7988c5 . However, in some cases, there are performance regressions - that need to be investigated. LTO was enabled with codegen-units = 1 and lto = "fat" for the corresponding profiles in Cargo.toml file.

Further steps

I can suggest the following action points:

• Perform more PGO benchmarks on Sage. If it shows improvements - add a note to the documentation about possible improvements in Sage performance with PGO.
• Providing an easier way (e.g. a build option) to build scripts with PGO can be helpful for the end-users and maintainers since they will be able to optimize Sage according to their workloads.

Testing Post-Link Optimization techniques (like LLVM BOLT) would be interesting too (Clang and Rustc already use BOLT as an addition to PGO) but I recommend starting from the usual PGO.

Here are some examples of how PGO optimization is integrated into other projects:

• Rustc: a CI script for the multi-stage build
• GCC:
  • Official docs, section "Building with profile feedback" (even AutoFDO build is supported)
  • A part in a "wonderful" configure script
• Clang: Docs
• Python:
  • CPython: README
  • Pyston: README
• Go: Bash script
• V8: Bazel flag
• ChakraCore: Scripts
• Chromium: Script
• Firefox: Docs
  • Thunderbird has PGO support too
• PHP - Makefile command and old Centminmod scripts
• MySQL: CMake script
• YugabyteDB: GitHub commit
• FoundationDB: Script
• Zstd: Makefile
• Foot: Scripts
• Windows Terminal: GitHub PR
• Pydantic-core: GitHub PR
• file.d: GitHub PR
• OceanBase: CMake flag

Please treat the issue just as a benchmark report - it's not an actual error, crash, or something like that. I don't know how much you care about performance in Sage so I don't know how important these improvements are for the project. I hope we can use these benchmarks at least as an additional data point about PGO efficiency for compilers.

Add a CLI so I can compile and run from the terminal instead of messing with main.rs.

It would be nice to insert more comments in the generated assembly at the LIR level. This is straightforward.

It would also be nice to have debugging symbols in the assembly (and possibly VM code as well) to allow a program to step through the compiled code and reference against the source code.