Tech projects, hobby programming, and geeky thoughts of Paolo Amoroso

Braincons, a Brainfuck implementation in Interlisp

After Stringscope I've been working on Braincons, an Interlisp implementation of the esoteric programming language Brainfuck. The project goals are to further learn the Medley Interlisp environment I'm developing Braincons with, as well as experiment with the compilation and implementation of a very simple language.

Braincons data structures inspected in Medley Interlisp.

Status

Braincons is in an early stage of development and largely incomplete, so I don't have much to show yet.

There's no program, output window, or Executive command to run. But preliminary versions of some of the main functions and data structures are in place, which can be called and inspected from Lisp.

So far the system can only parse Brainfuck program sources, check for errors, and produce an intermediate representation a virtual machine will eventually execute.

Installation

To try out Braincons download the file BRAINCONS from the project repo, copy it to a file system your Medley Interlisp installation has access to, and evaluate the following expression from the Lisp Executive:

(FILESLOAD BRAINCONS)

Usage

At this point you can call the parser function BRC.PARSE and pass it a Brainfuck source string:

(SETQ PARSED.PROGRAM (BRC.PARSE "<>[.,]+-"))

BRC.PARSE returns the intermidiate representation of the source, then assigned to the variable PARSED.PROGRAM which you can inspect as a BRC.PROGRAM record:

(INSPECT PARSED.PROGRAM)

The inspected record and its fields should look similar to the above screenshot. This is all I have for now.

Design

I initially focused on designing the main data structures and functions upon which to build the rest of Braincons.

First, I assigned descriptive mnemonics to the Brainfuck commands as in this table:

Command Mnemonic
> NEXT
< PREV
+ INC
- DEC
. OUT
, IN
[ JZ
] JNZ

Braincons represents the source of a Brainfuck program as a string. Two data structures implemented as Interlisp records hold the intermediate representation the parser produces.

The record BRC.PROGRAM consists of an array of instructions, the index of the last instruction in the array, a list of any branch instructions in the source, and a list of any errors encountered while parsing the program. Each array entry holds a Lisp symbol of the mnemonic of the corresponding instruction, except for the branch instructions JZ (jump if zero) and JNZ (jump if not zero).

Branches are records with fields for the mnemonic, the source address in the instruction array, the destination address, and the index of the branch command in the source string.

So far Braincons has only one entry point, function BRC.PARSE, which takes a Brainfuck source string as the only argument and returns the parsed intermediate representation record BRC.PROGRAM. BRC.PARSE calls directly or indirectly some helper functions to parse individual instructions, create branch records, and check for errors.

Sharing

Along with ASCII characters, Interlisp source files contain special characters such as and control codes that encode font changes. Visualizing these files in editors and tools that expect ASCII thus shows spurious characters.

To work around this I didn't directly share the raw code of Stringscope. Instead I stripped the control and formatting codes from the source exported from Medley Interlisp, replaced the special characters with more readable versions, and published it to a GitHub gist. The code in the gist is nicely formatted for reading but Medley Interlisp can't load it as is, so I have to provide the raw source separately.

Since Interlisp programmers are used to the formatting, and cleaning it up involves additional steps, I decided to store the raw source of Braincons in a GitHub repo. This also provides the additional flexibility of a full repo.

Further development

I'm actively changing and enhancing the code of the only working feature, the parser. Although the basic design of the main data structures is stabilizing, everything else will likely need a lot of refactoring and cleanup.

Next, I'll implement the virtual machine that processes and executes the parsed program.

In the long term I'd like to build a minimal Brainfuck development environment on top of the parsing and program execution functionality. The environment will comprise a source editor based on TEdit and an interactive visualization with controls for loading and starting programs, showing the state of the virtual machine and the executing program, reading user input, and displaying the output.

#braincons #Interlisp #Lisp

Discuss...
Email | Reply @amoroso@fosstodon.org