Compacting GC?

A neat trick is that directed acyclic graphs, the run-time structures egel programs manipulate, do allow for an efficient in-place compacting garbage collector. Which is what I am tempted to write at the moment.

Looks like sectorlisp uses that idea.

For future reference

cmake -DCMAKE_BUILD_TYPE=PROFILE ..




egel -e "import \"prelude.eg\";; using System;; using List;; foldl (+) 0 (from_to 0 1000000)"

/opt/homebrew/Cellar/llvm@12/12.0.1_1/bin/llvm-profdata merge -sparse default.profraw -o default.profdata

/opt/homebrew/Cellar/llvm@12/12.0.1_1/bin/llvm-profdata show -all-functions default.profraw

Testing 1.. 2.. 3..

// memory test

#include <memory>

#include <new>

#include <type_traits>

#include <utility>

// model values = atom int | array value*

static constexpr size_t roundup(size_t x, size_t m)

{

    return x % m == 0 ? x : (x + m) / m * m;

};

class Value;

typedef std::shared_ptr<Value> ValuePtr;

class Value {

public:

    Value() = default;

    virtual ~Value() {

    }

};

class Atom: public Value {

public:

    Atom(const int v): _value(v) {

    }

    virtual ~Atom() {

    }

    static ValuePtr create(const int v) {

        return std::shared_ptr<Atom>(new Atom(v));

    }

private:

    int _value;

};

struct ValueField {

    ValuePtr _value;

};

class Array: public Value {

public:

    Array() = default;

    virtual ~Array() {

        while (_size-- > 0)

            std::addressof(operator[](_size))->~ValueField();

    }

    ValueField &operator[](size_t i) {

        char *r0 = reinterpret_cast<char *>(this) + roundup(sizeof(*this), alignof(ValueField));

        ValueField *t0 = reinterpret_cast<ValueField *>(r0);

        return t0[i];

    }

    ValueField &at(size_t i) {

        if (i >= _size)

            throw std::out_of_range("duuude!");

        return operator[](i);

    }

    static ValuePtr create(size_t _sizes) {

        return std::shared_ptr<Array>(new(_sizes) Array(_sizes));

    }

    void *operator new(size_t count, size_t _sizes) {

        auto z = roundup(count, alignof(ValueField)) + sizeof(ValueField) * _sizes;

        return ::operator new(z);

    }

    void operator delete(void *x) {

        ::operator delete(x);

    }

    // not implemented for brevity reasons.

    // Also, it would have to handle (if only to throw an exception)

    // if someone attempted to move an Array(30) into an Array(20)

    /*

    Array(Array &&) = delete;

    void operator=(Array &&) = delete;

    */

private:

    Array(size_t n) {

        for (_size = 0; _size < n; ++_size)

            new(std::addressof(operator[](_size))) ValueField;

    }

    size_t _size = 0;

};

int main()

{

    Array fixed;

    auto flex = Array::create(20);

    // (*flex)[1]._value = 42;

}

Serialization

 I am more pondering than writing code at the moment. In order to get to mobile code, I need to be able to serialize, in order to serialize I need some representation independent of the runtime. Because when the serialized graph isn't independent it might corrupt the runtime when it is being loaded among other things.

It looks like I have little choice but to copy almost the complete runtime hierarchy into a serialization format.  Which sounds worse than it is, only four primitive types, arrays, then combinators. And then the combinators are the problem. Data is easy, bytecode can be (dis-)assembled, internal objects are always loaded, then the problem is externally defined C++ combinators. Or I do everything on a per-module basis, that's unclear at the moment.

Then there's the question of what goes into the graph. Say I have a bytecode combinator, do I only write the symbol or also the bytecode? No idea yet but I am tempted to have that separate from the graph.

The good part, serialization makes me think hard about how the interpreter is organized. The bad part, now I want to refactor again and get rid of some warts (macros), introduce namespaces, and employ c++20 modules. It's annoying to code against old code.

Also, pretty sure I am going to write the mobile code on top of grpc, which brings other problems since that's a client/server architecture and I want bidirectionality and more general a cloud of nodes which can talk to each other. But ah well, not everything is perfect. Maybe I'll just use it anyway.

Slides

 I felt like writing so I made some technical slides.

Hadoop

 While I work on the Python bridge code I am kind-of thinking I am getting a bit too distracted from the original goal of the Egel language, which was to facilitate data-center programming.

At the same time, it doesn't seem worthwhile to reinvent the wheel in this. Apache Hadoop has a ton of experience behind it so I'll need to look at whether I can lift that with Egel bindings after the Python bridge. Or maybe Kubernetes integration?

Futamura Projections

 I was discussing Futamura projections and made two observations.

1. Most of it remains true when you consider that partial evaluation doesn't have a lot to do with it all. Just take an interpreter and input program, combine them, and you already have a 'compiler.' The whole partial evaluation stuff is more the icing on the cake which makes you hope you can end up with an efficient solution.
2. Regarding the efficient solution, it's likely the case that partial evaluation in the extreme is an undecidable or NP problem. As an intuition, just take a sat solver as an interpreter. Then Futarama predicts that a sat solver plus a problem statement would give an efficient solver for that problem class,  and presto, your specializer proved P versus NP. Doesn't mean you cannot try this approach heuristically, but does imply that you have less than no guarantees at arriving at an efficient solution.

My $.02.