legit

Git commits as an esoteric programming language
2019-05-01 / blinry / CC BY-SA 4.0 / software, esolang, fav

Ever since I gave my first talk about esoteric programming languages, I wanted to create my own one. Well, some years later, at the Recurse Center, I wanted to learn how to build compilers with LLVM, so that seemed like a good opportunity to try that! Presenting:

Programs written in legit are defined entirely by the graph of commits in a Git repository. The content of the repository is ignored.

legit is designed so that all relevant information is visible when running git log --graph --oneline. For example, here is “hello world”:

Thanks to rohieb for the original idea! Influences for the design of this language include Folders, Befunge, Brainfuck, and Elymas.

A fun consequence of programs defined by a Git history is that you can’t properly track versions, because they already are Git repositories. All you can do is force-push a new version to GitHub.

You can find implementations of legit, as well as some example programs, on GitHub: https://github.com/blinry/legit. The entry in the Esolang wiki is at https://esolangs.org/wiki/Legit.

Here’s how the language works:

Memory

In each legit program, two data structures are available: A stack, and a brainfuck-like endless tape, with a head moving on it. Both hold signed integers.

Control flow

Execution starts at the commit pointed to by the master branch. Commit messages can contain a series of instructions, seperated with spaces, which are executed one by one. Only the first line is considered, so lines after that can be used for comments.

Instructions

For all instructions, popping from the empty stack will return a value of 0.

Control flow:

I/O:

Stack operations:

Tape operations:

Examples

I’ll be honest with you: I got tired of writing Git commands by hand to create legit programs. One consequence of the execution going top-down is that you have to write your programs backwards, and each time I’d make a typo, I’d have to start all over, because the commits above that would be invalidated. So… I started to write shell scripts, which would then generate my legit programs. You can generate the examples like this:

make -C examples

Alternatively, you can also clone them directly from GitHub:

hello, a simple hello world program:

rot13, a ROT13 implementation:

brainfuck, a fully-functioning Brainfuck interpreter, conveniently proving that legit is Turing complete!

Implementations

The repository provides both an interpreter (better suited for development and debugging purposes) and a compiler (which produces highly efficient binaries).

For both, you’ll need Ruby, and the “rugged” Gem:

gem install rugged

Running the interpreter

To execute a program, run

ruby interpreter.rb examples/hello/

Running the compiler

The compiler compiles a legit program to LLVM IR. You can then use LLVM tools to build binaries for all plaforms where you have a C standard library available (legit will be linked with exit, getchar and putchar).

First, run the compiler to create a .ll file:

ruby compiler.rb examples/hello/

And then, run a tool like clang to optimize it and produce a binary:

clang -O3 hello.ll -o hello

As an alternative to the second step, you can use the provided Makefile and simply run make hello.

The final challenge

So, after I had written that Brainfuck interpreter, I thought would be the final milestone for my language. But then, Kate-Laurel sat down next to me and asked: “Could you write a quine?”

So this is the challenge I now give to you, dear reader: Write a legit program that prints the Git commands required to create itself! Good luck.

Aftermath

Turns out at least two people were up to the challenge, and actually wrote a quine! I can’t believe it!

One is by remuladgryta, you can find a script to generate the legit program here! Daniel Temkin published a neat article about legit and remuladgryta’s quine on esoteric.codes!

Another one is by LegionMammal978, you can find the legit program here!


Comments?

Send a message to @blinry@chaos.social or drop me a mail at mail@blinry.org. Also, you can support me on Patreon or subscribe to my newsletter!