Just an idea I have, comments welcome. This post assumes that reader has some knowledge of Lisp and Haskell, otherwise it's probably incomprehensible.

Goal

Make a universal high-level intermediate representation which is suitable for many kinds of execution models such as:

• imperative mutable / pure functional
• low-level / manual memory management / automatic memory management

Expression tree

I assume that expression tree is perhaps the simplest way to build it, in form of a LISP or AST of a minimal language.

But a downside of that it might be too opinionated, particularly, regarding value bindings. How can we do it differently?

DAG

Another way to do it is to represent an expression DAG as a list. Each element of a list consists of an operator and a list of references to DAG nodes from the list before this nodes or surrounding lists.

For this example, I will use s-expression notation. Comments are after ;. The example just shows an idea and isn't meant to be complete, particularly, it says nothing about types, etc.

  (link ; link directive binds global entities to local module environment
        plus) ; reference to function plus, gets index 0 in local module environment

  (define-function add5 ( x ) ; names do not affect semantics
        (int-constant 5) ; load 5 into function environment slot 0
        ; 2D notation is used to reference DAG nodes, where first index is 
        ; index of environment (this list, arg list, module list) and second is index 
        ; of a slot in that environment
        (call (2 . 0) ; module-local environment has index 2, slot 0 is function plus
               (0 . 0) ; reference slot 0 of this environment, which is integer 5
               (1 . 0))) ; reference slot 0 of function arg list, which is x

An expression tree (i.e. Lisp) analog of this is (defun add5 (x) (plus 5 x)) which is kind of shorter, but...

What are possible advantages of this approach over expression trees?

• name bindings are unrolled into a DAG, thus languages compiling to this IR can implement their own binding semantics
• lexical environment with its complexities is just not a thing in this model
• it strongly discourages special operators which make use of "lexical environments", since they are not a thing

What operators (types of nodes) do we need? I believe for pure functional IR we fundamentally only need call and lambda, but if and int-constant can be handy for efficiency reasons too.

Here's example of a function which uses lambda to run a loop. I will first show the function implemented Common Lisp:

  (defun product-via-summation (x y)
      (let ((inner (lambda (left sum) 
                          (if (zerop left)
                              sum
                              (funcall inner (- left 1) (+ sum y))))))
         (funcall inner x 0))

(It won't actually work in CL because of lexical visibility rules. We need to use LABELS to be able to call local function recursively.) Now same using IR, for simplicity I refer to globals by their name but in reality it might be compiled down to index:

  (define-function product-via-summation (x y) ; silly function which implements * using +
        (lambda (left sum)
              (call zerop (1 . 0)) ; check if `left` is zero
              (call plus (1 . 1) (3 . 1)) ;   sum + y
              (call decrement (1 . 0)) ; left - 1
              (call (2 . 0) (0 . 2) (0 . 1)) ; recursive call to itself
              (if (0 . 0) (1 . 1) (0 . 3))) ; if zero return sum, otherwise return result of recursive call
        (call (0 . 0)  (1 . 0) zero))

Imperative programming / IO

Lazy pure functional programming, is, of course, easy mode. The real question is how imperative programming fits into this model. To handle imperative programming we add following operators:

• seq: make sure that all referenced nodes are evaluated in order, return the last one.
• par: like seq but without ordering
• call/seq: sugar for a call followed by seq.

Let's try doing the function above while also printing intermediate results:

   (define-io-function product-via-summation (x y) 
        (lambda (left sum)
              (call zerop (1 . 0)) ; 0: check if `left` is zero
              (call plus (1 . 1) (3 . 1)) ; 1:  sum + y
              (call decrement (1 . 0)) ; 2: left - 1
              (call (2 . 0) (0 . 2) (0 . 1)) ; 3: recursive call to itself
              (call print (1 . 1)) ; 4: print sum so we start with printing 0
              (if (0 . 0) (1 . 1) (0 . 3)) ; 5: if zero return sum, otherwise return result of recursive call
              (seq (0 . 4) (0 . 5))) ; make sure we always print before returning
        (call (0 . 0)  (1 . 0) zero))

How do we implement mutable variables and explicit memory management?

Just consider them as IO. The function above can be written as:

   (define-io-function product-via-summation (x y) 
        (mkvar (1 . 0)) ; 0: left
        (mkvar zero) ; 1 : sum
        (lambda ()
              (call readvar (2 . 0)) ; 0: read left
              (call readvar (2 . 1)) ; 1: read sum
              (call zerop (0 . 0)) ; 2: check if `left` is zero
              (call plus (0 . 1) (3 . 1)) ; 3:  sum + y
              (call decrement (0 . 0)) ; 4: left - 1
              (call print (0 . 1)) ; 5: print sum
              (call writevar (2 . 0) (0 . 4)) ; 6: write left
              (call writevar (2 . 1) (0 . 3)) ; 7: write sum
              (call (2 . 2)) ; 8: recursive call to itself
              (seq (0 . 6) (0 . 7) (0 . 8)) ; 9: imperative sequence for going to next iteration: write variables then call itself
              (if (0 . 2) (0 . 1) (0 . 9)) ; 10: if zero return sum, otherwise return result of recursive call
              (seq (0 . 5) (0 . 10))) ; make sure we always print before returning
        (call (0 . 2)))

This looks quite a bit like assembly (so I'm fairly certain it can represent low-level operation like assembly), but call sequence is determined by how dependencies and calls to seq and call are ordered, not by order of operations. So e.g. " (call writevar (2 . 0) (0 . 4))" does not happen unless it is required by the returned value.

Did you just reinvent Haskell?..

This is, obviously, influenced by how pure functional languages approach IO, but:

• evidently, it is not driven by types, although types can certainly prevent non-sensical programs to be compiled
• IR can in principle let programmer to write imperative using a language similar to Python or C which then gets compiled to this IR