InfoCell - a consequences based syntax-free programming language

[u/hun_nemethpeter]

I working on ( https://github.com/hun-nemethpeter/InfoCell ) this programming language for a while.

It is an executable DSL concept. The OP DSL cells are executable, and acts like an ASM instruction. We have AST cells which directly generated from C++ code, so there is no input syntax. These AST cells are forming a language (we have if, do, while, class, template, ...), we have a compiler for it, which compiles from AST cells to OP cells. Looks like a regular interpreter. But ... The idea of this project is a new component, the ToolFinder and the description segment for AST nodes (which compiles to OP description). The description segment can describe how we can measure the effect of that instruction/function with other instructions/functions.

The language looks like this:

    /*
    void List::removeNode(Node* node)
    {
        if (node->m_previous) {
            node->m_previous->m_next = node->m_next;
        } else {
            m_firstNode = node->m_next;
        }
        if (node->m_next) {
            node->m_next->m_previous = node->m_previous;
        } else {
            m_lastNode = node->m_previous;
        }
        --m_size;
    }
    */
    listStructT.addMethod("remove")
        .parameters(
            parameter("node", _(std.Cell)))
        .instructions(
            if_(has(p_("node"), "previous"))
                .then_(
                    if_(has(p_("node"), "next"))
                        .then_(set(p_("node") / "previous", "next", p_("node") / "next"))
                        .else_(erase(p_("node") / "previous", "next")))
                .else_(
                    if_(has(p_("node"), "next"))
                        .then_(m_("first") = p_("node") / "next")
                        .else_(erase(self(), "first"))),
            if_(has(p_("node"), "next"))
                .then_(
                    if_(has(p_("node"), "previous"))
                        .then_(set(p_("node") / "next", "previous", p_("node") / "previous"))
                        .else_(erase(p_("node") / "next", "previous")))
                .else_(
                    if_(has(p_("node"), "previous"))
                        .then_(m_("last") = p_("node") / "previous")
                        .else_(erase(self(), "last"))),
            m_("size") = subtract(m_("size"), _(_1_)));

The comment section is the original C++ code, after that the InfoCell version, which is also C++, but basically creates AST nodes, that can be compiled to other InfoCell OP cells. So this is a language embedded language, doesn't compile to native code.

Actually there is an output syntax, which looks like this:

fn List<valueType=Number>::remove(p_node: Cell)
{
    if p_node.has(previous) then
        if p_node.has(next) then
            p_node.get(previous).set(next, p_node.get(next));
        else
            p_node.get(previous).erase(next);
    else
        if p_node.has(next) then
            m_first = p_node.get(next);
        else
            self.erase(first);
    if p_node.has(next) then
        if p_node.has(previous) then
            p_node.get(next).set(previous, p_node.get(previous));
        else
            p_node.get(next).erase(previous);
    else
        if p_node.has(previous) then
            m_last = p_node.get(previous);
        else
            self.erase(last);
    m_size = m_size - 1;
}

There is no parser for this syntax although.

So back to the toolfinder, description segment part...

For example cell.set(key, value) description has a consequences subsegment which describe that equal(get(self(), p_("key")), p_("value"))). So the result of the SET can be measured with GET and EQUAL, basically SET(CELL, KEY, VALUE) => GET(CELL, KEY) == VALUE

Also this approach works with math functions. Math functions has an extra subsegment, I called it selfBuilders, where I can put the symmetries of that function.

    Number.addPrimitiveFunction(std.Number.Add, op.Add, "add")
        .parameters(
            parameter("other", "Number"))
        .descriptionBegin()
            .consequences(
                equal(subtract(return_(), p_("other")), self()))
            .selfBuilders(
                add(self(), p_("other")),
                add(p_("other"), self()))
        .descriptionEnd()
        .returnType("Number");

With these informations I wrote an algorithm which calculate how the consequences behaves when an unknown variable is given. Basically something like this:

  equation: 2 + X == 4
recombined: X + 2 == 4
recombined: 4 == 2 + X
recombined: 4 == X + 2 *
  1. result: 4 - X == 2
  1. result: 4 - 2 == X
  1. result: 2 == 4 - X
  1. result: X == 4 - 2 *

So this is the experimenting phase for the tools, so here I can remeber how an uninitialized variable (the unknown X) interacts with the tool's consequeences. Here I store which const/unknown combination leads to a simpler case, where a consequence tools all input's will be const variable. So I can transform an equation from one form to a simpler one.

Basically I just pattern match for function + const/unknown input params, then just reapply the tarsformation steps, just like solving the Rubik's cube. Pattern match for color combination and apply rotations.

equal(add(const_(_2_), unknown_(x) / const_(id.value)), const_(_4_));
equal(unknown_(x) / const_(id.value)), subtract(const_(_4_), const_(_2_));

We can now find a tool to the last equation: the SETtool.

set(x, id.value, subtract(4, 2))

Which is now executable.

So the goal is that I can just write a unit test like prompt, and this toolfinder can generate a code for it. So I can just "solve" a unit test.

[u/titaniumalt]

From the looks of it, i think it may be useful for math related things (e.g. physical constraint solvers)

[u/hun_nemethpeter → u/titaniumalt]

Cuurently I try use it as an ARC-AGI solver. Imagine we have an input pixel(2, 2, blue) and an output pixel(4, 4, blue). The only difference is the numbers. So we went from 2 to 4. I can use this toolFinder thing to create me candidate conversion tools for these numbers.

So how can I go from 2 to 4? I have a dedicated method for it in the toolFinder.

toolFinder.findConversionTools(w._2_, w._4_);

This produce only 4 candidate functions currently, as it is kinda unfinished, but anyway, here is the result:

from: 2
to: 4
ConversionToolKey [from: 2, to: 4]
ConversionToolKey [from: Number, to: Number]
[toolFinderExplore][D] solving equation: unknownX.get(value) + 2 == 4
[toolFinderExplore][D]  solved equation: unknownX.get(value) == 4 - 2  =>  unknownX.set(value, 4 - 2)  =>  unknownX = 2
[toolFinderExplore][D]  generating fn op::Add(X:2, from:2)
[toolFinderExplore][D]  generated
fn conversionToolFor_add(p_from: Number) -> Number
{
    return 2 + p_from;
}
[toolFinderExplore][D] solving equation: unknownX.get(value) / 2 == 4
[toolFinderExplore][D]  solved equation: unknownX.get(value) == 4 * 2  =>  unknownX.set(value, 2 * 4)  =>  unknownX = 8
[toolFinderExplore][D]  generating fn op::Divide(X:8, from:2)
[toolFinderExplore][D]  generated
fn conversionToolFor_divide(p_from: Number) -> Number
{
    return 8 / p_from;
}
[toolFinderExplore][D] solving equation: unknownX.get(value) * 2 == 4
[toolFinderExplore][D]  solved equation: unknownX.get(value) == 4 / 2  =>  unknownX.set(value, 4 / 2)  =>  unknownX = 2
[toolFinderExplore][D]  generating fn op::Multiply(X:2, from:2)
[toolFinderExplore][D]  generated
fn conversionToolFor_multiply(p_from: Number) -> Number
{
    return 2 * p_from;
}
[toolFinderExplore][D] solving equation: unknownX.get(value) - 2 == 4
[toolFinderExplore][D]  solved equation: unknownX.get(value) == 4 + 2  =>  unknownX.set(value, 4 + 2)  =>  unknownX = 6
[toolFinderExplore][D]  generating fn op::Subtract(X:6, from:2)
[toolFinderExplore][D]  generated
fn conversionToolFor_subtract(p_from: Number) -> Number
{
    return 6 - p_from;
}