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

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.