Smart dispatch

Introduction

At the heart of performant code execution in PeTTa lies the ability to map efficiently written MeTTa code to efficient Prolog code.

Let's consider the following tail-recursive fibonacci:

(= (fib $n) (fib $n 0 1))
(= (fib $n $a $b)
   (if (== $n 0)
       $a
       (fib (- $n 1) $b (+ $a $b))))

which gets translated to

fib(A, B) :- fib(A, 0, 1, B).
fib(A, B, C, D) :-
    (   ==(A, 0, true)
    ->  D=B
    ;   -(A, 1, E),
        +(B, C, F),
        fib(E, C, F, D)
    ).

From the generated code we see that the fib predicate is invoked at the end of the body of the fib(A, B, C, D) definition, leading to an efficient tail-recursive call that gets optimized. The direct mapping to a predicate call is possible because when translator gets to translate the recursive call, fib is already known to be a function from previously processing the function header. Hence with this version !(fib 100000) takes about 170ms on M4 processor.

However what if the compiler would not yet know that fib is a function when the call is made. Three options arise from this:

1. Just always assume it to be a function call (call), generating a predicate invocation. This won't work as we want to build lists too, e.g. (justdata 42) should evaluate to itself in MeTTa rather than generating an error.

2. Always assume it to be data/list (quote). Nope, we want to be able to call functions.

3. Evaluate MeTTa code at runtime (eval): For each expression invoke translator and execute the generated Prolog goals. This would essentially turn PeTTa into a code interpreter, which is significantly slower than when translating the code first to Prolog, then asserting it (leading to bytecode compilation).

4. Dynamic dispatch (reduce): Always Generate a dynamic dispatch which checks whether the first argument is a function, if yes call it, if not leave it as a list. Then, in case the fib function gets added later, the code will automatically switch to function call when invoked rather than leaving-it-as-list. However, then every predicate call performs a dynamic dispatch, which is slow (at least by a factor of 2-4 in examples like https://github.com/patham9/PeTTa/blob/main/examples/fib.metta ) yet still significantly faster than an interpreter.

5. Dynamic dispatch unless function: If it is known to be a function, generate a predicate invocation, else generate a dynamic dispatch. This covers making function calling fast if they are added in the dependency order. However, it means all list construction still uses dynamic dispatch, which can still be slow. For instance structure-heavy examples like https://github.com/patham9/PeTTa/blob/main/examples/tilepuzzle.metta are 100 times slower when dynamic dispatch is invoked for list building.

6. Smart dispatch: When an expression is already known to denote a function, generate a direct predicate invocation; otherwise, treat it as data. This is further improved by having two-stage compilation so definition order does not matter anymore. A retranslate!(name) facility allows explicit retranslations if adding functions in dependency order or using forward declarations such as (= (myfunc) (empty)) is not feasible. Mechanisms also exist to manually enforce call, eval, quote, or reduce, though this is rarely required and unused even in advanced projects such as NARS, PLN, or Nil’s backward chainer. PeTTa adopts this Smart Dispatch approach, achieving MeTTa execution speeds comparable to idiomatic Prolog. One residual case of dynamic dispatch remains: when a caller itself evaluates to a function as in ((f) 42), since f may return a function that must then receive the argument 42. This last instance could be further reduced for the "(just data)" case by inspecting type declarations to verify whether a function’s output is not a function. Additionally, future iterations of Smart Dispatch could automate retranslate! by tracking which atoms appear in caller position and triggering retranslations when corresponding function definitions are added. Smart dispatch for HOL functions: Here if it is known to lead to a function call, generate a direct predicate invocation. Since that is not always knowable for HOL functions, dynamic dispatch is the backup decision in this case. Overall, smart dispatch is more complex but serves as the key mechanism that eliminates dynamic dispatch in nearly all cases, providing substantial speedups without requiring user awareness. In addition to the direct translations to Prolog clauses Translator offers, Smart Dispatch is the secret sauce that allows PeTTa to execute MeTTa code as fast as if it had been written in Prolog, thereby combining the best of both worlds: the speed of modern Prolog engines with the elegancy of MeTTa.

Case study with timings

Now we will investigate timing characteristics by forcing the compiler to generate Call/Reduce/Eval respectively:

Call / Smart dispatch

(= (fib $n $a $b)
   (if (== $n 0)
       $a
       (fib (- $n 1) $b (+ $a $b))))

translates to the same code as enforcing call:

(= (fib $n $a $b)
   (if (== $n 0)
       $a
       (call (fib (- $n 1) $b (+ $a $b)))))

and executes (fib 500000) in 1.5s.

Reduce / Dynamic Dispatch

(= (fib $n $a $b)
   (if (== $n 0)
       $a
       (reduce (fib (- $n 1) $b (+ $a $b)))))

takes 2.9s due to enforcing dynamic dispatch on each call.

Eval / Interpretation after translation

(= (fib $n $a $b)
   (if (== $n 0)
       $a
       (eval (fib (- $n 1) $b (+ $a $b)))))

takes 3.8s, still not bad considering in each recursive call we translate the MeTTa expression (fib (- $n 1) $b (+ $a $b)))) (with the variables instantiated) to Prolog goals (essentially 500K translator invocations on that expression), and directly call the Prolog goals without compilation to bytecode.

---

However, the benefit of Smart Dispatch is clear even in linear recursions / iterative code like that. In other examples the difference can be even more pronounced, e.g. naive fibonacci !(fib 33):

Call/Smart Dispatch: 1.8s

Reduce/Dynamic Dispatch: 4.0s

Eval/Interpretation after translation: 18s