How do I make this functional DSL written in an imperative language more efficient?

Question

Suppose I create a simple functional Domain-specific language (DSL) using an imperative language, in this case C++. Here is a simple implementation of a DSL that can has the notion of a simple value and operator (in this case the addition operator):

// some operator
template <typename LHS, typename RHS>
struct OpImpl
{
    Op(LHS lhs, RHS rhs) : mLhs(lhs), mRhs(rhs) {}
    auto operator()() const
    {
      return mLhs() + mRhs(); // let's say it's a non-trivial operation, and can't be optimised away but also has no side effects.
    }
    LHS mLhs;
    RHS mRhs;
};

template <typename LHS, typename RHS>
auto Op(LHS&& lhs, RHS&& rhs) { return Op<LHS, RHS>(lhs, rhs); }

struct Value
{
    Value(int value) : mValue(value) {}
    auto operator()() const
    {
        return mValue;
    }
    const int mValue;
};

Disregarding other problems with this, if I try to create a nested expression using this "language" I will very quickly end up with redundant leaf nodes:

int main()
{
    auto Res0 = Op(Value(1), Value(2)); // 1 + 2
    auto Res1 = Op(Res0, Res0); // (1 + 2) + (1 + 2)
    auto Res2 = Op(Res1, Res1); // ((1 + 2) + (1 + 2) + (1 + 2) + (1 + 2))
    auto Res3 = Op(Res2, Res2); // etc.
    auto Res4 = Op(Res3, Res3);
    auto Res5 = Op(Res4, Res4);
    auto Res6 = Op(Res5, Res5);
    auto Res7 = Op(Res6, Res6);
    auto Res8 = Op(Res7, Res7);
    auto Res9 = Op(Res8, Res8);
    auto Res10 = Op(Res9, Res9);
    auto Res11 = Op(Res10, Res10);
    auto Res12 = Op(Res11, Res11);
    auto Res13 = Op(Res12, Res12);
    auto Res14 = Op(Res13, Res13);
    auto Res15 = Op(Res14, Res14);
    auto Res16 = Op(Res15, Res15);
    auto Res17 = Op(Res16, Res16);
    auto Res18 = Op(Res17, Res17);
    auto Res19 = Op(Res18, Res18);
    auto Res20 = Op(Res19, Res19);
}

The above code in any normal language will have linear complexity on the number of "Res" depths (in this case 21), and presumably functional language implementations do as well.

However, in the above example, my program will call the () operator on the Value class 2^21 times. If Value is not trivial to calculate, this could make my program tremendously inefficient!

I can reduce the number of calls to Value by introducing a cache:

template <
struct OpImpl
{
    Op(LHS lhs, RHS rhs) : mLhs(lhs), mRhs(rhs) {}   
    auto operator()() const
    {
        // some unique identifier
        auto cacheIndex = findMyIndex(this) // this could be a typeid, etc.

        if (!cache.count(cacheIndex))
            cache[cacheIndex] = mLhs() + mRhs();
        return cache[cacheIndex];
    }

    LHS mLhs;
    RHS mRhs;
};

The above reduces the number of calls to the parenthesis operator of Value to 2 and the number of calls to OpImpl to 21. With some tweaking (figuring out the cache position at construction, using an efficient lookup, memory pools, etc.) we can probably make these lookups quite cheap, but we're still doing 21 lookups / pointer indirection for a series of operations that would be much more efficient in bespoke c++ or with a real functional language.

So, to get to my question; how do functional languages solve this problem, and, more importantly, how do I apply such a solution to the simple DSL example given above, such that the code exhibits a reasonable amount of efficiency?

Note that I am not asking about making the above algorithm perform more quickly, I want to find a better algorithm.

Answer 1

You seems to want to make some optimization (e.g. common subexpression extraction, as commented by rwong) in your interpreter.

Notice also that a language (even a domain-specific language) is never defined by some internal representation, but a computer language is defined by its syntax and its semantics (so you'll better define them first, at least on paper, before any implementation effort).

^{The syntax defines what are the valid sentences or phrases of your language, and the semantics defines what are their behavior or meaning.}

Actually, interpreters vs compilers does not mean much, and there is a continuum between them.

The most inefficient interpreters are like the BASIC interpreters on original PC in the 1980: they are rescanning and reparsing and interpreting the source code of every statement every time they need to interpret it. So when interpreting a loop they are repeatedly reparsing the text of each statement.

Then you have interpreters which are parsing into some abstract syntax trees (AST) and later evaluating (recursively) the ASTs.

It is usually more efficient to have the interpreter transforming (usually once) the AST into some lower form, often some bytecode interpreted by a virtual machine and doing some optimizations on it (many efficient interpreters are doing that, e.g. Ocaml, Lua, etc...). You could consider translating your DSL into some existing bytecode VM like Parrot. Actually efficient compilers and interpreters are transforming the AST into bytecode (or object code, or C code) using several passes (FYI the GCC compiler has several hundreds of passes).

Finally, you can transform the AST or the bytecode (or some other internal representation) into machine code using e.g. Just-In-Time translation techniques (e.g. with JIT libraries like libjit, libgccjit, LLVM, ...)

At last, ordinary ahead-of-time compilers exist. BTW, you could compile to e.g. C code (see this) and dynamically load (e.g. with dlopen on POSIX systems) and execute it. I'm doing that in MELT (and it is actually compatible with an interactive REPL loop).

At least if you know a tiny bit of Lisp or Scheme, you should read Queinnec's Lisp In Small Pieces book, which covers most of the spectrum outlined above.

Compilers and interpreters have a lot of things in common, and there is a continuum between them. So you should dive into a good compiler book.

BTW, why don't you reuse some existing embeddable language implementation like GUILE?

Notice that your example is very artificial in practice. People usually don't have a very deep arithmetic expressions like you are showing. I guess that if you do something equivalent with the C preprocessor or with C++ templates the C or C++ compiler would need a lot of CPU time to compile it (so in my opinion you are wrong in believing that "any normal language will have linear complexity").

In your example, your AST is not a tree but a DAG, which is somehow unusual. Unless your DSL is homoiconic and/or have sophisticated macro-programming or metaprogramming (e.g. multi-staged programming) facilities, your DSL script source text won't get parsed into a DAG, but into a tree (and your issue won't happen at all).

BTW, a possible solution might be to have let like expression binding a local variable (see what let is in Ocaml or Scheme) in your DSL, e.g. something like (using Ocaml syntax):

let x1 = 1 in
 let x2 = x1 + x1 in
  let x3 = x2 + x2 in
   let x4 = x3 + x3 in
    x4 + x4

Notice that you might spend several months or even years to implement your efficient DSL. Are you sure that it is worth the effort? Can't you embed some existing interpreter?

Reading some books comparing several programming languages (and knowing several of thems), e.g. Scott's Programming Language Pragmatics, will certainly improve your thinking about your DSL design (before any implementation effort).

Answer 2

My understanding is that a lazy evaluated language actually holds everything in a wrapper like this:

class LogicalValue {
    ActualValue *value;
    ActualValue operator()() {
       if (value == null) {
           value = computeValue();
       }
       return value;
    }
}

This is like your caching example, except that it doesn't attempt to reuse values from other copies of LogicalValue. If I apply the same function to the same operations a second time, it'll get recomputed. The fact is, attempting to memoize everything all the time is a massive performance loss. There is typically only a small set of cases where it is useful, and its explicitly enabled there.

Now, that is theoretically what happens. An actual optimizing functional language compiler will do a lot of optimizations on-top of this structure to get rid of the overhead. For example, if you use a value repeatedly, there's no point in repeatedly checking if it has been evaluated already. On the other hand, if you just created a LogicalValue, there is no point in checking to see if it has been evaluated.

As far your actual case: If we ignore conditionals, it is actually pretty trivial. We always have to compute everything. Just use a depth first traversal of the of graph, adding items to a to-calculate list if they aren't already added. Once you have the list, all you need to do is traverse the list in order evaluating each option. You know that all pre-requisites have been precomputed, because they were added to the list first.

Conditionals make things more complicated because some portions of the DAG won't need to be evaluated. Depending on the complexity of your operations, it might be acceptable to evaluate them anyways. If not, you'll have to come up with a more sophisticated handling.