Assemble an XOISC program
Tags: code-golf, parentheses, parsing
Recently I solved this challenge, for which I created XOISC - a very low-level functional language. To compile a program (written in the absurdly high-level lambda calculus programming language) it must first be translated into an expression consisting only of X combinators and from there it can be translated to the "machine language".
There's an initially empty stack and the program only consists of a stream of integers. For each integer the following happens:
Pop N elements f1,...,fN and push X (f1 (..(fN-1 fN)..)) - ie. it right-folds function application and applies this to another X.
Eventually we'll end up with a stack of functions which gets left-folded with function application. That's it.
How does it work?
When parsing such an expression, one thing to keep in mind is that function application is left-associative - meaning that X (X X) X is read as (X (X X)) X rather than X ((X X) X).
If we have an expression f g with sub-expressions f and g (in the code below
App f g - eg. X (X X) X would be f = X (X X) and g = X), there's a simple recursive algorithm to assemble it:
-- Base case: We simply need to pop the accumulated functions
asm' n X = [n]
-- Recurse: First build the left function, then the right one.
-- Incrementing n ensures that we leave (f g) on stack
asm' n (App f g) = asm' 0 f ++ asm' (n+1) g
-- Now we start with 0 functions on the stack:
asm expr = asm' 0 expr
For those unfamiliar with Haskell:
- this algorithm assumes an already parsed expression in the form of of a binary tree (the definition of the data structure would be
data Exp = X | App Exp Exp where
X would be a leaf and
App f g would be a node with children
g that are
Exps as well)*
asm' n exp does a case distinction by matching a pattern on
- if the expression is X (ie.
exp = X) it's the base case and just returns a singleton list containing
n (an integer)
- else it's of the form f g (with f,g some sub-expressions) which is expressed as
App f g, so it will recursively build the list for f and append the list of g
- to assemble an expression
exp we begin initialize the recursive algorithm with
n = 0 (
asm' 0 exp)
Note: Since a lot of people here know Python, you can find a horrible but very well documented Python reference implementation here which does the parsing as well as the assembling!
| means that an
Exp type can be constructed of either the left constructor (
X) or of the right one (
App Exp Exp where the two
Exp two sub-expressions).
For example the expression X (X X) X would be expressed as
App (App X (App X X)) X.
Having an expression X (X X) X, it helps to think of the implicit parentheses: (X (X X)) X
Translating this with the above algorithm:
- Assemble (X (X X)):
- Assemble X:
- Now Assemble X X, making sure it gets applied to the previous one (+1)
- The first X gives us a
- The second one gives us
0 + 1 + 1 = 2 (apply to X and previous one)
- So the left (X (X X)) gave us
[0,0,2], assembling the right X:
- This gives us
0 + 1 (apply to the previous one)
And we end up with the program
Note: While this algorithm ensures that there's a program for every expression, there can be other solutions too. For example
[0,0,1,0] would be a valid one for X (X X) X as well.
Given an expression consisting of X combinators, translate it to the XOISC machine language:
- Input will be a string encoding such an expression
- The input will be a valid expression and non-empty
- You may choose to require an input string that contains no spaces
- You may choose the characters encoding parentheses and the combinator itself (as long as it's consistent, eg. using
x instead of
- You're guaranteed that there are no unnecessary parentheses (eg.
(X X) X would result in undefined behaviour)
- Output can be a list of integers, a string separated by new-lines or whitespaces
These testcases assume that the input contains whitespaces and choose
X to encode the combinator.
Note that there may be multiple valid outputs, you're free to choose one* - I'll only show the solution resulting from the above algorithm:
X -> 
X X X -> [0,1,1]
X (X X) -> [0,0,2]
X (X X) X -> [0,0,2,1]
X (X (X (X X X))) -> [0,0,0,0,1,4]
X (X X) (X X) (X X) -> [0,0,2,0,2,0,2]
X (X X X (X X)) -> [0,0,1,1,0,3]
X (X (X X) (X X)) -> [0,0,0,2,0,3]
X X (X X (X (X (X (X (X X X)))) X) X) -> [0,1,0,1,0,0,0,0,0,1,5,2,2]
X (X (X X) X (X X X)) X (X (X (X X) X)) -> [0,0,0,2,1,0,1,3,1,0,0,0,2,3]
X (X (X (X (X X) X X) X X X) X X X X) X X X X X -> [0,0,0,0,0,2,1,2,1,1,2,1,1,1,2,1,1,1,1,1]
X (X (X X (X X) (X X) (X X) X) X (X X) X) X (X X X) X -> [0,0,0,1,0,2,0,2,0,2,2,1,0,2,2,1,0,1,2,1]
* Here's a program to validate alternative solutions
- I already posted this to main, but apparently I did a bad job of explaining it.. It's hard to tell what's missing, I'd be happy for feedback (feel free to edit this)!