Namespaces, revisited.

I conservatively extended namespaces, but that took an internal overhaul of how scopes are treated. Shorthands are syntactic sugar for full-blown expressions.

using System

The above is sugar for:

using System (c0, c1, c2, ...)

Where c0, c1, c2, ... are all combinators in the System workspace. And that is sugar for:

using ε = System (c0, c1, c2, ...)

Which is again sugar for a number of renames.

using ε = System (c0 = c0, c1 = c1, c2 = c2, ...)

The renames all introduce bound names into the current scope. E.g.,

using Sys = System (p = print)

This will bind 'Sys::p' to 'System::print'.

Docstrings

I added docstrings to the Egel language some time ago. You can add documentation to either a file or a combinator.

@"""A multiline docstring for a file"""

def f =
    @"this is the fabulous 'f' combinator"
    [X -> 42]

Given docstrings, you can now ask for that interactively in the REPL.

>> help 'f'
{"this is the fabulous 'f' combinator"}

'Help' will do a best-match against all combinator definitions.

Thread local Stopgap

I made the stopgap solution thread local. It's still expensive.

   ~VMObjectArray() {
#ifdef GC_STOPGAP
        if (deferring) {
            for (int i = 0; i < _size; i++) {
                defer.push(_array[i]);
            }
            delete[] _array;
        } else {
            deferring = true;
            for (int i = 0; i < _size; i++) {
                defer.push(_array[i]);
            }
            delete[] _array;
            while (!defer.empty()) {
                defer.pop();
            }
            deferring = false;
        }
#else
        delete[] _array;
#endif
    }

Stopgap solution to Cascading Free

 Egel runtime objects are instances of C++'s std::shared_ptr. Because egel objects can be deeply nested, it is not uncommon for large structures to go out of scope and result in cascading frees that blow up the C stack.

I.e., the following short egel program would core dump:

# rewrite a list of a million numbers to none

from_to 0 1000000 |> [_ -> none]   

I implemented a costly stopgap solution. First, we need a collector for trash. It has an in queue and an out queue, and its sole intention is to retain objects for a while such that they don't go out of scope recursively and blow up the C stack.

class GC {

public:
    GC() {
    }

    void push(const VMObjectPtr &o) {
        std::lock_guard<std::mutex> lock(mtx_in);
        _in.push(o);
    }

    void copy() {
        std::scoped_lock lock(mtx_in, mtx_out);
        while (!_in.empty()) {
            _out.push(_in.top());
            _in.pop();
        }
    }

    bool done() {
        std::scoped_lock lock(mtx_in, mtx_out);
        return _in.empty() && _out.empty();
    }

    void empty() {
        std::lock_guard<std::mutex> lock(mtx_out);
        while (!_out.empty()) _out.pop();
    }

    void clear() {
        while (!done()) {
            copy();
            empty();
        }
    }

private:
    mutable std::mutex mtx_in;
    mutable std::mutex mtx_out;
    std::stack<vmobjectptr> _in;
    std::stack<vmobjectptr> _out;
};

inline GC garbage_collector;

Now when an array goes out of scope, we place its members in the collector.

    ~VMObjectArray() {
        for (int i = 0; i < _size; i++) {
            garbage_collector.push(_array[i]);
        }
        delete[] _array;
    }

And during rewrites we then empty the queues.

    while ((trampoline != nullptr) && (*run != HALTED)) {
        if (*run == RUNNING) {
            trampoline = f->reduce(trampoline);
            garbage_collector.clear();
        } else if (*run == SLEEPING) {
            std::this_thread::sleep_for(std::chrono::milliseconds(100));
        } else {  // *run == HALTED
        }
    }

I am not happy with this solution. First, I consider it a std::shared_ptr bug that it can blow up the C stack, and second, the performance cost is way too steep for my taste.

I'ld rather convince C++ developers that this is their bug; for all I know cascading frees are a normal thing in reference counted garbage collection and their implementation should be able to handle that.

Temporal Logic Synthesis

 I wanted to show that Egel can be used to create small tools, and decided upon a temporal logic synthesizer. After reading a bit I trimmed that down to: do something useful with LTL and Z3. The first because LTL is relatively small, the latter since I want Z3 bindings for Advent of Code anyway.

Synthesis is a bit of a hopeless subject since the best you can hope for is to derive small automata with maybe five states. Moreover, it already exploded on translating LTL to negation normal form, the first ostensibly minor step in the whole process.

But I remain committed for now.

E-Graphs trivially in PSPACE

Some people pointed me at E-graphs, a manner for representing and then heuristically minimizing terms. Of course, Boolean circuits are terms too and minimizing circuits is PSPACE. Very much so, even.

So, it's unclear how much minimization you can actually achieve with E-graphs.

Control Flow Revisited

Two forms (b?f:g)(x) and f(b?x:y), should be enough for all (functional) control flow analysis. In a very abstract sense, application and choice are all you need.

After I commented that contification just equals hoisting on a small example someone on the interwebs made a smart comment that 'f' cannot be hoisted in the following example but can be contified.

let f = fun arg -> body in 

match thingy with 

| A -> f x 

| B -> f y 

| C -> g foo

Of course, you just need a rewrite to a term that uses b0? f(b1?x:y) : g foo to see that 'f' is still hoisted. But it won't be pretty so that's an issue.