I've been thinking about embedded languages (domain-specific or otherwise), and in particular the approach where we define a datatype to represent terms of the embedded language, e.g. (in Haskell):
data Expr = Numeral Int
| Apply Expr Expr
| Lambda String Expr
| Var String
| ...
We then provide a library of functions which allow us to write programs, like plus 10 5
, but when "run" they don't actually produce the 'answer' (15
), they instead produce a representation of that program in the embedded language, like Apply (Apply (Var "plus") (Numeral 10)) (Numeral 5)
.
My question is: can we implement a general-purpose, high-level programming language, like Haskell, such that the "compiler" is actually a set of library functions, "compiling" is just interpreting our program, and the resulting value is machine code (or Javascript, or whatever our compilation target is).
Another way to think about this: in Lisp-like languages, we can create new language constructs using macros, which get "expanded" into other macro calls and eventually down to "special forms" implemented with an interpreter/compiler. From this perspective, my question would be: is it possible to make a Lisp where the only special forms are (representations of) machine code, and the whole "user-facing" language (function definition, calling, branching, etc.) is just a set of macros? In such a system, macro-expanding a program would result in a compiled binary. I'm willing to ignore the "dynamic"/reflection/etc. features found in "real" Lisps.
Another way to think about this: assembly languages get macro-expanded into machine code; are there any any assemblers which do/could provide "high-level" features, like higher-order functions, pattern-matching, garbage collection or linear types, etc.?
Is there some insurmountable difficulty with this (e.g. linking?)? Is it something that's been done? Things which seem related, but slightly different:
- Forth seems to 'bootstrap' itself in a similar way when executed, but doesn't (in my limited experience) seem to "compile down" to a 'self-contained binary'; rather, it either runs "dynamically" (i.e. the code we write gets executed 'as is'), or it gets compiled into a form with an embedded interpreter.
- The IO approach of Haskell, Idris, etc. is similar, in that Haskell can be seen as a macro language for constructing "IO programs", but it's not quite the same: our Haskell code isn't "fully expanded" by the compiler: we can write pure functions which only get executed at runtime, and even when things do get inlined/fused/etc. it's because of 'compiler magic' rather than the language's semantics.
- The Nix language is purely functional and turing complete, and its programs evaluate to give "derivations", containing an environment and build script for some 'package'. Derivations can, optionally, be sent to the
nix-build
tool for execution. Could we make a similar language which evaluates to give a "machine code" (or "unlinked assembly") value, which we can subsequently pass to an assembler/linker/etc.?
In such a system, our program would be instructions for the "compiler" (the interpreter we run to get the resulting binary), hence we could implement things like instrumentation, optimisation, cross-compiling, etc. as library functions, rather than having to update some separate, monolithic program like GHC.