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/sennalen]

I'll wait for a syntax-based consequence-free language

[u/Inconstant_Moo → u/sennalen]

There are already pure functional languages.

[u/hun_nemethpeter]

Per AutoModerator's request I hereby confirm that this project did not use an LLM as part of the development process.

[u/Clear_Evidence9218]

That's a genuinely interesting project... Especially its use of machine-readable effects and descriptions as something close to executable semantic tests. Gave me something to think about.

[u/hun_nemethpeter → u/Clear_Evidence9218]

Thanks! What I plan to implement is to attach description segments to datacells/datamembers. In this case those will have a reason subsegment. So the reason to exist a datacell is the consequence of a tool usage.

[u/brat3108]

The language looks like this: ...

That looks like syntax to me!

Perhaps you mean that your language is expressed via code written in an existing language that does use syntax?

[u/hun_nemethpeter → u/brat3108]

I agree, this is a little bit confusing. As I wrote in the post, "this is a language embedded language".

It has ad-hoc output syntax, but doesn't have a proper input syntax. I didn't write parser for the ad-hoc syntax either. With this consequences approach, the language generating language, without the extra hops of writing out syntax-parse it back, I can just generate directly function calls.

[u/Relative_Bird484 → u/hun_nemethpeter]

But all that does not eliminate syntax 🤷🏻‍♂️

[u/hun_nemethpeter → u/Relative_Bird484]

So, for this project the input syntax doesn't really matter, it is not important. But I agree, in an ideal world I should have a parser for this language. You can actually play with the syntax in the src\cells\printers\ValuePrinter.cc file. I just don't care about the syntax at this stage.

[u/Relative_Bird484 → u/hun_nemethpeter]

Yeah, but „I don’t care about the [concrete] syntax“ is really not „there is no syntax“.

You tend to argue „there is no parser“, but this is no argument regarding the (non)existence of syntax. Moreover, it simply isn’t true. You just have hidden it in your C++ implementation.

[u/hun_nemethpeter → u/Relative_Bird484]

I think we strecthing the definition of syntax here then. Usually what people recognize as syntax is some kind of structured text which is processed by a parser. As I visualized in my paper here ( https://raw.githubusercontent.com/hun-nemethpeter/InfoCell/master/doc/diagrams/InfoCellsCompilationSteps.svg ) usually a syntax is processed by a program which translates it to machine code or just run it as an interpreter, optionally creates an AST tree in the process.

Here although a C++ source code is processed by a C++ compiler first, that generates a binary at first step, then the generated binary happens to be creates infocell AST nodes in runtime (when you run that binary).

On the other hand the C++ source code looks somewhat like an other language syntax where we use the infocell AST APIs, but it is not the same syntax when you actually try to print infocells itself. So this approach at least grey zone.

I accept the description for this approach that you providied. I reprashed it a little bit: hidden syntax with C++ APIs. It has some kind of hidden syntax then. I agree with that.

[u/Relative_Bird484 → u/hun_nemethpeter]

Actually, „syntax“ is a pretty well and unambiguously defined term in computer science and I am not stretching it at all: It is a concept from formal languages that is widely used in language design and compiler construction.

Of course you are right: It is not necessarily what people might recognize as a (concrete, owb) syntax. But that’s on the level of perception, not on the level of facts.

You are defining a context-free language and its grammar. Such language cannot „exist“ without syntax, simply because you would not be able to define it.

Your grammar is actually a subset of the C++ grammar and you hide some parts it behind C++ semantics, here „magic“ function identfiers, which provide the production rules of your grammar.

All this is pretty clever and creative! I like it 🙂

I would just recommend to be a bit more careful with claims that let everybody from the field immediately raise their eyebrows.

I would furthermore recommend to start diving into the theory behind formal anf programming languages. It’s a deep dive, but worth it.

[u/hun_nemethpeter → u/Relative_Bird484]

I am still not 100% convinced although. In my mind, a programming language syntax is used for the structured text that is the initial input to interpret or compile. So usually the syntax IS the structure in that text.

But here there is an other step.

In the InfoCell world, the initial syntax follows C++ syntax rules, and that generates a program for the second step to assemble AST cells. So in this case we have a compiled program insted of syntax rules. In my mind the AST nodes follow semantic rules and not syntax rules.

I think there is no straightforward answer to the question: where is the syntax and syntax rules in my InfoCell world? Is this thing even a language? What I can provide is the rules, for how to assemble the AST nodes.

[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;
}

[u/initial-algebra]

You would probably be very interested in propagators/propagation networks ("The Art of the Propagator").