Iain Dunning

Contact: iaindunning at gmail, @iaindunning, github/IainNZ

› IPLANG - an optimization-based esolang

First posted: May 28, 2014

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.

Solve integer progam to find the minimal vertex cover of this graph = compile an IPLANG program.

Solve integer progam to find the minimal vertex cover of this graph = compile an IPLANG program.

Introduction to Esoteric Programming Languages

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:

  • INTERCAL requires the user to be polite - if PLEASE, PLEASE DO NOT and so on do not appear enough in the program, it will not run.
  • Spleenmap uses only 5 instructions, and is written as a two dimensional block of text, resulting in something like “ASCII art”.
  • Brainfuck is probably the most famous (and copied). It uses 8 instructions, and strikes a fairly interesting sweet-spot between minimalism and complexity. Here is a program in Brainfuck that prints out Hello World!:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

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.

Introduction to Integer (Linear) Programming

Linear programming (LP) is one of the core tools in the numerical optimization toolbox. In LP we are interested in the following problem:

$$ \begin{alignat*}{1} \text{maximize} \quad & \sum_{j=1}^{n} c_j x_j \\ \text{subject to} \quad & \sum_{j=1}^{n} A_{i,j} x_j \leq b_i \qquad \forall i \in \{1,\dots,m\}\\ \end{alignat*} $$

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.

IPLANG

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

  1. Solving the integer optimization problem (e.g. using Cbc or another solver from the JuliaOpt collection).
  2. Treat the solution as a bit string and transpile it to Brainfuck.
  3. Run the Brainfuck program.

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

$$ \begin{alignat*}{1} \text{maximize} \quad & \sum_{j=1}^{n} c_j x_j \\ \text{subject to} \quad & x_j \in \left\{0,1\right\} \quad \forall j \in \{1,\dots,n\}\\ \end{alignat*} $$

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.

$$ \begin{alignat*}{1} \text{maximize} \quad & 0 \\ \text{subject to} \quad & x_j = b_j \quad \forall j \in \{1,\dots,n\}\\ & x_j \in \left\{0,1\right\} \quad \forall j \in \{1,\dots,n\}\\ \end{alignat*} $$

which is also really dull.

Scoring an IPLANG program

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.

Trying it out

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)

Example IPLANG program: minimum vertex cover

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:

Graph whose optimal vertex cover is a Brainfuck program

Graph whose optimal vertex cover is a Brainfuck program

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

Next steps

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.

HackerNews discussion.


© Iain Dunning, 2015. Base theme/CSS by Skeleton.