Contact: iaindunning at gmail, @iaindunning, github/IainNZ
In this post I present my new programming language, IPLANG, where the program is described (encoded?) as the solution to a binary optimization problem, and there are a large number of possible encodings for even the most simple program - the art is in making the relationship between the optimization problem and the program as interesting as possible.
After learning how to program in a couple of languages, a fairly natural thing to want to do is to create your own. Some people set out to create “serious” languages, believing that their new language is the solution to a/the world’s software development problem(s), but the reality seems to be that there are only so many programming languages that the world can handle at any one time, and most of these efforts die out. Some walk a different path and create languages not as “real” development tools but more as an exploration of the space possible ways to tell a computer what we want it to do. These more quirky languages are sometimes called esolangs, and there have been many interesting ones over the years. Some examples include:
PLEASE
, PLEASE DO NOT
and so on do not appear enough in the program, it will not run.
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
As you can tell from the listings on Esolang.org, there have been many esolangs made over the years. A large number seem to be based on Brainfuck, either in that they extend/reduce it slightly or can be trivially transliterated to Brainfuck. I am fond of Ook!, where the 8 instructions are matched to different combinations of “Ook” and punctuation, e.g. “increment” is Ook. Ook.
and “decrement” is Ook! Ook!
. Instead of ooks and punctuation though, we could be dull and simply use a binary encoding, e.g.
000
- Move pointer right
001
- Move pointer left
010
- Increment memory cell under pointer
011
- Decrement memory cell under pointer
100
- Output character for memory cell under pointer
101
- Input character and store in memory cell under pointer
110
- Jump past matching 111 if cell under pointer is 0
111
- Jump back to matching 110 if cell under pointer isn't 0
I’ll return to this in a moment. For now, let us take a detour into mathematics.
Linear programming (LP) is one of the core tools in the numerical optimization toolbox. In LP we are interested in the following problem:
In words, find the (real) values of \( x_{j} \) that maximize the value of a linear expression (the objective function) subject to a set of linear constraints. Note that we can also use equality or greater-than-or-equal-to constraints, and change between these different forms with simple transformations. This problem has some fantastic structure that allows us to solve it efficiently, and despite (or because of?) everything being linear it has found a wide variety of uses. Note that “programming” is used in a different sense to the modern “programming language”, although they both share a common origin from the days when “computers” were people. To avoid confusion, some now use “linear optimization” instead.
A natural variation of this problem is to restrict all or some of the \( x_{j} \) to the set of integers, or even just the values 0 and 1. This is often called “integer programming” (IP) and although it is a much tougher problem, large (\( n \) can be on the order of \( 10^6 \) ) integer programs can be solved (usually as a sequence of linear program relaxations).
In real-world problems the constraint “data” \( A_{ij} \) is very sparse - most of the values are 0, and most constraints involve very few of the variables. As a result, constructing the \( A \) matrix manually is painful, inefficient, and hard to maintain. Instead, people use algebraic modeling languages which can be thought of as mathematical domain-specific languages, sometimes embedded in other languages. One such language is JuMP, which is embedded in the Julia programming language. For an example of how a modeling language is used, and why you might want to use one, check out my Sudoku-as-a-Service post.
Given that Brainfuck only has eight instructions, we can use 3 bits per instruction, and can encode an \( n \)-instruction-long Brainfuck program as a sequence of \( 3n \) bits. We can thus, for any Brainfuck program, create an integer optimization problem with \( 3n \) decision variables where the optimal solution is that program.
Thus, IPLANG is born. An IPLANG program is written as integer programming problem, and is run by
The interest comes from the multitude of ways to encode a problem. Consider the following very simple program which emits an exclamation mark then terminates:
++++++++[>++++<-]>+.
This program is 20 instructions long, or 60 bits, so we will need a 60 variable optimization problem. There are two simple problems that will always work that are also completely boring. In the first, define a vector \( \mathbf{c} \in \mathbb{R}^n \) such that \( c_j \) is positive if \( x_j \) should be 1, and negative if it should be 0. Then our optimization problem is simply
which is horribly dull. In the second, we don’t even define an objective - instead we express the program as a vector \( \mathbf{b} \in \left\{0,1\right\}^n \) and define a constraint for each decision variable, i.e.
which is also really dull.
The above extremes suggest some ways we can make using IPLANG more interesting, or at least challenging to create programs in. I propose the following metrics and bonuses:
Connectivity. Here we turn the constraint matrix into a undirected graph, where the nodes are the n decision variables. We say an edge exists between nodes i and j if and only if the corresponding variables appear together with non-zero coefficients in a constraint The goal is then to minimize the number of connected components in this graph, with 1 being the best you can do and n the worst (e.g. the second example above). We’ll say that “no constraints” is equivalent to n components.
Importance of the objective. This is a have-it-or-don’t kind of thing. In the first example above, the objective was critical - any change would change the solution. In the second, we didn’t even have an objective - even if we did, it wouldn’t change the solution. The first is more interesting, so we’ll say that you get a bonus if the objective matters - that is, changing the objective changes the solution.
Fractionality, or effort to solve. This is a bit more subtle. Most integer programming solvers work by relaxing the binary restriction to \( 0 \leq x_j \leq 1 \) and solving the resulting linear program. They then check for any fractional values in the solution, and select one variable to “branch” on - they create two new linear programs, one where one of those fractional variables is fixed to 0, and in the other is fixed to 1. Eventually you’ll solve a relaxation and everything will be integer - this is a feasible solution, but not necessarily optimal. In the worst case you are looking at an exponential number of relaxations, but by using bounding and some geometric tricks you can usually do much better. This suggests two similar metrics: the number of linear program relaxations required to find an optimal solution (the higher the better), or the percentage of variables that have a fractional value at the initial relaxation (the higher the better). You could definitely argue that lower is better for both of those though.
Aesthetics. If we were to turn the constraint matrix \( A \) for the second example into a black-and-white image, where 0 is white and 1 is black, we would get a diagonal strip. Points could be awarded for how good the sparsity pattern looks. Another such subject quality could be how practical the integer programming problem looks - the more practical/realistic it looks, the more surprising it is that the solution is actually a computer program.
There isn’t really an IPLANG implementation right now, but its fairly easy to play with in Julia. First, add the required packages, e.g.
julia> Pkg.add("JuMP") # Modeling language
julia> Pkg.add("Cbc") # Integer programming solver
julia> Pkg.clone("https://github.com/johnmyleswhite/Brainfuck.jl") # Brainfuck interpreter
then you can write your IPLANG program using JuMP (manual)
N = 20 # Number of instructions
using JuMP
m = Model()
@defVar(m, x[1:3*N], Bin) # 60 binary variables
@setObjective(m, Max, 5x[1] + 2x[3] ) # ... and so on
@addConstraint(m, x[1] + x[5] <= 1)
# ...
solve(m) # Solve the problem
x_val = getValue(x) # Values will be Float64s - not necessarily exactly 0 and 1
and run it with John Myles White’s Brainfuck.jl (thanks John!):
import Brainfuck
function iplang_to_bf(x)
x = map(int, x)
N = length(x)/3
ops = Int[]
for i = 0:N-1
bits = (x[3i+1], x[3i+2], x[3i+3])
bits == (0,0,0) && push!(ops, Brainfuck.OP1) # > right
bits == (0,0,1) && push!(ops, Brainfuck.OP2) # < left
bits == (0,1,0) && push!(ops, Brainfuck.OP3) # + inc
bits == (0,1,1) && push!(ops, Brainfuck.OP4) # - dec
# Note JMW's order is swapped for next two from IRD's
bits == (1,0,1) && push!(ops, Brainfuck.OP5) # , read
bits == (1,0,0) && push!(ops, Brainfuck.OP6) # . print
bits == (1,1,0) && push!(ops, Brainfuck.OP7) # [ begin
bits == (1,1,1) && push!(ops, Brainfuck.OP8) # ] end
end
Brainfuck.interpret(ops)
end
iplang_to_bf(x_val)
Minimum vertex cover is a classic graph problem. We try to select a minimal subset of the nodes in a graph so that for every edge at least one of the nodes that define it are in the subset. We can model this problem an integer program. The particular graph I constructed has two connected components thus, so does my constraint matrix - so thats a 2 on the connectivity score. The objective is the vector of ones, and changing it by anything than a positive scaling is quite likely to change the solution, so it meets that goal. Finally, I claim this does fairly well on the aesthetic measure, because we are solving a problem on realistic graph but the solution is a program - a non-obvious transformation. Minimal vertex cover is NP-Hard and the LP relaxation is fractional.
The following graph has an optimal vertex cover which produces the same exclamation point program we were been looking at above:
Here is the code, which I created iteratively - which suggests the process could be automated - you could even write an optimization problem to create IPLANG programs!
m = Model()
@defVar(m, x[1:60], Bin)
@setObjective(m, Min, sum(x))
edges = [( 1, 2), ( 2, 3), ( 4, 5), ( 5, 6),
( 7, 8), ( 8, 9), (10,11), (11,12),
(13,14), (14,15), (16,17), (17,18),
(19,20), (20,21), (22,23), (23,24),
(25, 1), (25, 3), (25, 4), (26,35),
(26,27), (26,28), (26,57), (29,26),
(32,30), (32,31), (34,35), (35,36),
(37,38), (38,39), (40,41), (41,42),
(44,45), (45,46), (56,38), (32,51),
(47, 6), (47, 7), (47, 9), (35,32),
(48,10), (48,12), (48,13), (41,56),
(49,15), (49,16), (49,18), (45,46),
(50,19), (50,21), (50,22), (50,43),
(51,52), (51,53), (51,33), (50,58),
(56,54), (56,55), (56,23), (51,45),
(58,59), (58,60), (58,33), (35,11)]
for edge in edges
@addConstraint(m, x[edge[1]] + x[edge[2]] >= 1)
end
solve(m)
iplang_to_bf(getValue(x)) # Defined above
The next steps are to write a tool to take Brainfuck programs and generate IPLANG programs, possibly by making a basic IPLANG program and mutating it. Another approach is pick an IP-solvable problem like the traveling salesman problem or max-cut and creating the graph that will encode the program. Trying to make even the simple program above manually took quite a while!
Finally, let me know if you create an IPLANG program of your own - I’ll add it here.