Universal high-level intermediate representation
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: likeseqbut without orderingcall/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
25 comments · 88% upvoted · other discussions
So, on a practical level, there are many IRs. Programming in general, the structure of your input data affects your algorithms that process them.
The algorithms you want to apply will vary on what your language offers. So it's not really possible to have a universal IR here.
What I think you're describing is p-code or bytecode. Which is technically IR but is focused on the "portable" side than the processing side.
Kind regards, M ✌️
killerstorm [OP] 1 points · Aug 2021
My goal is to create an IR which can
This is different from low-level IRs, e.g. if you compile Haskell to LLVM IR all its haskellness is gone at that point.
Universality is not about replacing all other kinds of IRs, obviously, but about supporting different models of execution.
[deleted] 15 points · Aug 2021
From an IR I'd expect that (after optimisations) it'd compile the same regardless of which source language I am using. But I don't understand how this works with your IR.
C and Haskell have very different execution models. In particular how do you handle laziness?
killerstorm [OP] 1 points · Aug 2021
That's where it gets complex. :)
What I want to do is something which enables any-to-any conversion, i.e. allows to compile different languages to different compilation targets. Sort of like pandoc but for software.
Compilation targets might range from boring binaries for a particular OS to some locked down VM. Obviously, some of (source, target) combination simply make no sense. Other might require emulation.
In the post I described only the execution model of IR, but it should have other components as well, particularly, it should define what source requires from the target. So a compiler would know what target it is compatible with, what sort of emulation or compat layer it might need, etc.
Basically the strategy so far is to translate "C" model to "Haskell" model, and then execute the "Haskell" model. I.e. we have a lazy program in the end, so compiler has to know how to do lazyness.
There can be a problem when interfacing between the two, I think it can be solved by representing more information about the function in the type system and then only allow safe constructions to be compiled / linked.
crundar 3 points · Aug 2021
Do you intend for it to round-trip? That is, is
compile2 :: LangA->LangB->LangAan identity function?killerstorm [OP] 1 points · Aug 2021
There might be different compilers which use this IR. Some might try to enable lossless translation as you described above, other might not care about this at all and focus on e.g. making a binary for a particular platform.
Currently I have some pragmatic use for IR as my company develops some programming languages / platforms we might benefit from having a flexible IR. Any-to-any is more of a pipe dream tbh.