PietCC

PietCC is a Rust interpreter and compiler for the Piet esoteric language using inkwell and LLVM as a backend / IR generator. To read more about the compiler, visit this writeup.

Organization

1. piet_core: core language types
2. interpreter: core interpreter logic
3. compiler: core compiler logic, handles CFG generation and subsequent optimizations
4. parser: core image parsing logic, handles image loading and pixel/codel operations
5. src: main CLI, allows users to run either the interpreter or compiler with a variety of flags
6. tests: integration tests for compiler and interpreter

Dependencies

• Rust 1.89+ (Stable, Beta, or Nightly), for inkwell
• LLVM libraries, including clang and llc, for generating IR / lowering to assembly.

Features

• Supports treating unknown colors as white / black.
• Supports white block tracing and elimination
• Supports nontermination detection for certain classes of programs
• Supports running LLVM module optimization passes via inkwell
• Supports static evaluation / constant folding optimizations at the CFG level

TODO

Compiler

• Develop more Piet-specific optimizations and respective optimization passes

Installation

Clone this repository via

git clone https://github.com/pwang00/pietcc
cd pietcc

Building PietCC

To build PietCC, first make sure you have supported versions of rustc and LLVM on your system. You may need to modify inkwell's cargo feature flags in the Cargo.tomls of the project root and compiler. This project sets them at LLVM 18.1:

inkwell = { version = "0.7.0", features = ["llvm18-1"] }

However, other versions are supported as well per the inkwell docs:

| LLVM Version | Cargo Feature Flag | | :----------: | :-----------: | | 4.0.x | llvm4-0 | | 5.0.x | llvm5-0 | | 6.0.x | llvm6-0 | | 7.0.x | llvm7-0 | | 8.0.x | llvm8-0 | | 9.0.x | llvm9-0 | | 10.0.x | llvm10-0 | | 11.0.x | llvm11-0 | | 12.0.x | llvm12-0 | | 13.0.x | llvm13-0 | | 14.0.x | llvm14-0 | | 15.0.x | llvm15-0 | | 16.0.x | llvm16-0 | | 17.0.x | llvm17-0 | | 18.1.x | llvm18-1 |

so replace features = ["llvm18-1"] with the desired cargo feature flag.

Once you have verified that the LLVM version is correct, run

cargo build --release
mv target/release/pietcc .

Alternatively, it is possible to combine the build / run workflow via

cargo run --release <image> <flags>, but this attempts to check for changes to the PietCC source on every run, so is not recommended.

Testing

PietCC includes comprehensive unit and integration tests.

Prerequisites

Integration tests require npiet to be installed:

Ubuntu/Debian:

sudo apt install libgd-dev groff
git clone https://github.com/gleitz/npiet.git && cd npiet
./configure
make
sudo make install

macOS: npiet is not currently supported on macOS due to giflib API incompatibilities. Unit tests will still work.

Running Tests

# Run all tests
./scripts/run_tests.sh

# Or use cargo directly
cargo test

For detailed information about the test infrastructure, writing tests, and CI/CD, see TESTING.md.

Interpreting Piet programs

PietCC provides several options for interpreting programs, as shown below.

USAGE:
    pietcc [OPTIONS] <input>

ARGS:
    <input>    Piet source file to interpret

OPTIONS:
...
    -i, --interpret                Interpret the given program
    -o, --output <out>             Output an executable into <file> [default: program.out]
    -s, --size <codel_size>        Interpret or compile with a supplied codel size (must divide
                                   program height and width)
    -v, --verbosity <verbosity>    Sets the interpreter's verbosity
    --ub                           Treats unknown pixels as black (default: error)
    --uw                           Treats unknown pixels as white (default: error)

PietCC will by default try to infer the codel width of the program. The heuristic used computes the gcd of all the block widths and heights with each other and the program width / height, and will produce a correct estimate of the codel width with high probability. However, to correctly interpret some programs, supplying the size flag with a corresponding value for the codel width is necessary.

The images/ directory contains a list of sample programs.

Here's an example run with fizzbuzz.png:

<img src="https://github.com/pwang00/pietcc/blob/main/images/fizzbuzz.png" alt="Piet FizzBuzz" width="256"/>

./pietcc images/fizzbuzz.png -i -v 2

Running with codel width of 1 (size of 1)

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16

Doing cargo run --release images/fizzbuzz.png -i -v 2 will also work.

Compiling Piet programs

PietCC supports emitting executables, LLVM IR, and LLVM bitcode. The latter two options can be useful for targeting other architectures other than x86_64. The relevant flags are shown below.

Piet compiler and interpreter

USAGE:
    pietcc [OPTIONS] <input>

ARGS:
    <input>    Piet source file to interpret

OPTIONS:
    -d, --default <use_default>    Interpret or compile with a codel size of 1
        --emit-llvm                Emit LLVM IR for a given Piet program
        --emit-llvm-bitcode        Emit LLVM bitcode for a given Piet program
    -h, --help                     Print help information
    -i, --interpret                Interpret the given program
    -o, --output <out>             Output an executable into <file> [default: program.out]
        --o1                       Sets the compiler optimization level to 1 (LLVM default<O1>, attempts
                                   Piet constant folding)
        --o2                       Sets the compiler optimization level to 2 (LLVM default<O2>, attempts
                                   Piet constant folding)
        --o3                       Sets the compiler optimization level to 3 (LLVM default<O3>,
                                   attempts Piet compile-time evaluation to fold constant programs)
    -s, --size <codel_size>        Interpret or compile with a supplied codel size (must divide
                                   program height and width)
        --ub                       Treats unknown pixels as black (default: error)
        --uw                       Treats unknown pixels as white (default: error)
    -v, --verbosity <verbosity>    Sets the interpreter or compiler's verbosity
    -w, --warn-nt                  Attempts to detect nontermination behavior in a Piet program
                                   during compilation

To compile a Piet program to an ELF executable, LLVM IR, and LLVM bitcode respectively, do

• ./pietcc <image> -o <output>
• ./pietcc <image> -o <output> --emit-llvm
• ./pietcc <image> -o <output> --emit-llvm-bitcode

To specify an optimization level while compiling, do

./pietcc <image> --o[1|2|3] -o <output>

To specify behavior when encountering unknown pixels, do

./pietcc <image> --[ub|uw] -o <output>

and to specify warning about nontermination, do

./pietcc <image> -w -o <output>

Terminating Piet programs

Here are some example terminating Piet program images with compilation logs:

Piet Pi Approximation

<img src="https://github.com/pwang00/pietcc/blob/main/images/piet_pi_big.png" alt="Piet Pi"/>

$ ./pietcc images/piet_pi.png -o piet_pi
$ ./piet_pi 
31405


Stack empty

Hello World 1

<img src="https://github.com/pwang00/pietcc/blob/main/images/hw1-11.gif" alt="Hello World with Codel Size 11"/>

$ ./pietcc images/hw1-11.gif -o hw1-11
$ ./hw1-11 
Hello, world!
Stack empty

Piet Brainfuck Interpreter

<img src="https://github.com/pwang00/pietcc/blob/main/images/piet_bfi.gif" alt="Piet Brainfuck interpreter" width="300"/>

Per the relevant section under piet samples

"The Piet program takes a Brainfuck program, and its input (seperated by |), from STDIN and prints the output of the Brainfuck program to STDOUT. E.g. the input ",+>,+>,+>,+.<.<.<.|sdhO" would generate the output 'Piet'"

$ ./pietcc images/piet_bfi.gif -o piet_bfi
$ ./piet_bfi 
Enter char: ,+>,+>,+>,+.<.<.<.|sdhO
Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Enter char: Piet
Stack (size 29): 18 0 7 18 80 0 105 0 101 0 116 44 43 62 44 43 62 44 43 62 44 43 46 60 46 60 46 60 46 

[Piet