FLOORPLAN

Inspiration

What's everyone's biggest problem with floor plans? Once you build the room, they're basically useless. Here we present an interpreter to give these building foundations a much needed second lease of life --- as programs.

As a group, we spent a while meditating on the theme of 'Building Foundations'. We wanted to do something interesting, unexpected, and hopefully kind of funny. Eventually, this resulted in the idea of taking the theme completely literally - and writing a programming language that parses & interprets building floorplans. We began the hackathon by brainstorming approaches to the programming language, eventually deciding on a functional style language that executes by "stepping" through rooms sequentially, performing operations based on the items within the room. It was great fun to throw around ideas of what could be in our building - we landed on a sort of Severance-core office theme for the items, reflecting the sometimes slightly odd and labirinthine floorplans necessary to represent programs.

What it does

FLOORPLAN (yes, inspired by FORTRAN) is a Turing-complete programming language that enables users to execute floorplans written in Unicode. For example, a basic "Hello World" program, is represented as follows (I promise, this works much better in an actual text editor!):

    ┌───◟───────────┐
    │               │
    │  HELLO WORLD  │
    │               │
    └───═══─────────┘

There is an entry point in the form of the door into the room, then a label for the room, and a window along the bottom edge. This tells the compiler to enter the room, and then output (through the window) the room label.

Of course, this is a very simple example! Our language can do much more than this. One program is a building, with multiple floor files within it, each with multiple rooms. Lifts and staircases direct control flow, allowing jumps to other functions and recursive calls back into the same floor. You can construct products and project from them, "photocopy" your value to fork a process, and perform arithmetic operations with "shredders" and "team building exercises". If-then-else is implemented with the "wastepaper basket" which checks if a value is the 'base case' of the type.

With these primitive building blocks, we were able to build complex functions for our standard library, such as multiplication, minus, and strictly less-than. These can be inserted as floors into existing buildings and then accessed with elevators to quickly and simply run more difficult operations.

With this library, we were able to write the 'factorial building', combining primitive floors with the standard library. While we didn't quite have time, we're fairly confident we could've even written RSA :)

For ease of understanding, programs can simply be thought of as a path that a person walks through the building (splitting themselves in two to go through two doors, of course.) This made paper debugging much easier, and when writing code in a text editor we could add windows to all the rooms to check what was going on inside of them!

While Unicode can be a little tricky for coding, we provide the 'useful-characters' file with all the Unicode characters needed to write programs in FLOORPLAN, as well as notation on what they represent. We use very few Unicode characters, but a creative programmer can use many more, decorating their building with any non-reserved character to create a lively scene.

How we built it

FLOORPLAN uses simple building blocks. It is written in Haskell, using only ghc and the Base library. We built everything from the ground up (ha!), writing both a parser and interpreter. Buildings can be run by simply providing the folder (of floor files) and command line argument taken in (through the "door to the outside"). The results of any rooms with windows are returned.

The parser alone was very complex, as we'd expected. While our syntax is well-defined, it is also not strict; ie, there are many ways to represent the same program that should be parsed to the same Abstract Syntax Tree. For example, rooms can be of any size so long as they are rectangular, and doors can be placed at any point on walls, so long as the left-right ordering is kept consistent. This meant having to first process where all the corners are in order to locate rooms in the file, understanding the entrances & exits (as well as staircases and lifts, which can be both entering and leaving the floor!), and then finally processing any items within the room. While when writing our own programs we rarely found a need to place more than one objects in the same room, an arbitrary number can be placed there and are processed sequentially.

The interpreter then had to take that AST and actually run it. Some especially difficult tasks were left to the interpreter, such as processing pairs, staircases & lifts, and if-then-else splits. A lot of information on the processing has to be inferred from the structure of the rooms as stored in the AST - for example, staircases are aligned by co-ordinate, and the interpreter must work out whether the staircases is going up or down.

To have a language, we also had to program in it, so we also spent time writing sample programs. This provided us great opportunities for debugging our parser & interpreter, as well as giving us an idea of what our language was capable of. Getting our heads around the language took a second, but once we got into the flow of it, it became easier. It was also fun to notice standard convention for approaching programming we started using, such as a liminal Floor (n+1) used to recurse on Floor n.

Challenges we ran into

The biggest challenge was that our requirements were ~~stupid~~ hard

If it looks like a floorplan, it should at least parse and try to run
- Added leniency means a compiler with less diagnostics and less to debug from
Turing completeness
Source programs should look good

There were definitely some significant challenges when building this project! Even from the very beginning, it was daunting to think about how we were going to translate something so disimilar to "normal" programming languages into an AST so we could actually run it. We were very lucky to kidnap a whiteboard, and spent a lot of time hashing out all sorts of problems, having to debug both our Haskell and FLOORPLAN code.

In terms of parsing, the biggest challenge was working out the boundaries of the rooms, and differentiating between room labels (which represent constants) and items in the room. Taking inspiration from real building floorplans, it was important to us to have both, so we were very happy to eventually get it working. A major issue with room boundaries was working out a) what was a room and what was just the empty void outside of the building and b) when floorplans were illegal (such as exits from the building, which are not allowed! This is Severance-core, after all.)

For interpreting, we faced a hurdle at the last minute when we thought everything was running well .... and then realised pairs weren't evaluating properly. This was a major setback, as pairs are vital in the "photocopying" modality, which allows functions to run with two instances of the variable on the right-hand side (such as f(n) = n * (n-1) for factorial). It was really important to be able to split pairs and then later rejoin them in order to perform functions such as multiplication, but ensuring the two "copies" of the person walking around the building met back up and then executed properly was very difficult!

Finally, writing programs in FLOORPLAN had its own issues too. One of the most infuriating problems was due to the fact that whitespace is important in our language in order to properly align cross-floor features such as staircases (after all, they must line up in real life!). This resulted in a lot of furious sending backwards-and-forwards of our floor files as we tried to determine why on earth they wouldn't parse properly, and why emacs and vim couldn't agree on how to display whitespace!

Accomplishments that we're proud of

FLOORPLAN is Turing complete (use it for your next work project)
- Primitive recursion
Factorial program was a ridiculous achievement to write an debug
- There are 5 floors

I think all of us were genuinely shocked by how much we managed to get done, and how effectively our very silly idea worked. The feeling when we first managed to run a program was incredible, even if it was just Hello World! Seeing all of the different parts we'd been working on come together into something that not only executed, but correctly was incredible, all the more so because it was at least 2am! Seeing the potential for the language has been really awesome too - we've already been thinking up new items that can be placed into the rooms to allow us to write even more programs, such as "mod" and maybe even "fizz buzz".

In the end, by far the most exciting moment was when we got our factorial building to work. We'd written it in the early hours of the hackathon as a goal to shoot for, and we ran into error after error getting it to run, exposing all sorts of issues across the code base. But when it finally ran, and we saw the right numbers output on a program built from a floorplan it was unparalleled. All of our work paying off in something that was actually functional was really an awesome feeling.

What we learned

While all of us on our team were brought together by our love for programming language theory and the more mathematical side to Computer Science, we had a lot to learn. Especially given most of us hadn't written any Haskell in a good while, it was a very steep learning curve. Do you know what a reverse Monadic bind does? I didn't either, at the start of this hackathon. A real highlight of the late evening was one of our teammates yelling you, "Wait! Room is a monoid!" which then led to a fascinating (and ultimately unproductive) discussion of whether Floor could be a group, and if so what an inverse Floor would be...

What's next for FLOORPLAN

As mentioned, we've got a lot of ideas for what could be added to FLOORPLAN next. These include both language features (such as an "incinerator", which allows the person to get rid of one of their values they're holding), and quality of life features for programming (it really is infuriating sometimes...). In an ideal world, this would include features such as automatic alignment of staircases to take out the whitespace headache. We have ideas to bring the floorplans closer into alignment with real life too, such as more complex parsing to allow for L-shaped rooms and corridors.