Sun Aug 30 11:50:31 CEST 2009

A fully linear concatenative VM needs interpretation

What I find really remarkable is that it is possible to make a pure
functional concatenative language fully linear.  You don't need _any_
graph structure, including its virtual machine!

However.  Full linearity of the machine requires some form of
interpretation (laziness).  When code is executed, name references
need to be expanded to their definitions.

This `lookup' cannot be performed in a separate compilation stage
(i.e. to eliminate its associated run-time cost) while maintaining
linearity of the VM.  Such a stage would directly link variable
references with variable definitions and require a non-linear (graph)
data structure:

   * Names can be used multiple times (i.e. procedure re-use) which
     requires a directed acyclic graph.

   * Name-based recursion can introduce loops in the representation.

In this light, the idea behind the PF machine is that you operate in
two regimes: one which remains linear, but keeps code and VM as
opaque, constant structures, and one which is nonlinear to implement
issues related to the VM (in the simplest case just code compilation).

The main idea is that: ``Names are part of the meta-language''[1].

[1] entry://../staapl-blog/20080813-125604