Felix has inline functions, which are always inlined unless
(a) they’re recursive
(b) closures are formed (Felix is really bad at closure elimination)
“val" rariables can be inlined too depending on a heuristic.
In any case, the premise of the system appears to be that the heap
is eliminated. This is provably impossible for an open program.
For a closed program (i.e. one with no inputs) monomorphisation and
dependent typing can, for example, convert lists into arrays.
To solve this problem, we use a partial evaluator to close an open
program. We do this by reading the input, and generating code
for that input; that is, forming a closed program, and then compile
it, thereby eliminating the heap at the expensive of runtime code
generation and compilation.
Jay’s FISh that I worked on did this for arrays. Instead of dynamic
length arrays, the input arrays were actually program constants
which the partially compiled program compiled. FISh actually
generated FORTRAN or C, compiled it, and ran it dynamically.
FISh had no heap either.
Thats the theory: the heap (dynamic data structures) are replaced
by dynamic code generation with static data structures whose
size and shape is calculated, then fast code generated.
The cost of course is run time generation, compilation,
and execution of that part of the program dependent
on the inputs: in performance terms this is radically slower
than dynamic arrays since array processing in general
gains nothing from replacing a few indexing variables
with constants .. the constants are going to be loaded
into machine registers anyhow. The big win is when you
can replace lists with arrays, or more generally, trees.
=====
I might point out C++ has superior first class inlinables.
Its called constexpr. So C++ itself also has two types of
staged evaluation now: template monomorphisation
and also, separately, constexpr reduction. I wouldn’t be
suprised if C++ compiles now have to do partial evaluation
since almost any function can now be constexpr, forcing
the compiler to evaluate it at compile time. I guess Clang
must do this by compiling it to LLVM bytecode and interpreting it,
but it could even compile that bytecode to binary and execute it.
====
The BIG problem in FISh, C++, and Felix, with partial evaluation
is knowing when something is evaluated. On the other hand, with
explicitly staged compilation, its just as bad, even though the staging
is forced, the annotation required to control that makes the program
hard to understand, because the annotations are optimisation
controls and not semantic information.
—
John Skaller
ska...@internode.on.net