Sun Mar 14 23:00:40 CET 2010

Functional representation of stages

I've identified the language levels[1] in Staapl.  I was wondering how
to represent these as higher order functions, and whether it is

I see 2 ways to do this:

A. Directly relating functions in the 3 levels:

> type Mem a   = [a]                 -- Machine state, parameterized by representation
> type Asm a   = (Mem a) -> (Mem a)  -- Machine code, represents state transitions
> type Macro a = (Asm a) -> (Asm a)  -- Macro language = machine code transformers

The problem is that this does not include pattern matching rules
(intensional analysis).  Code is an opaque type.

Pattern matching seems to be an essential component to encode the
actual work.

B. So, what about including the interpretation steps, i.e. have a mix
   of code and data intermediate?

See figure in [1] which looks like

          int      |
     stx ====> fun |
      :            |
 comp :            V
      :          data'

where the morphism called "interpretation" is included explicitly.

> -- Machine state, parameterized by representation
> type Mem a = [a]
> -- Semantics of AsmStx and MacroStx
> type AsmFun a   = (Mem a) -> (Mem a)
> type MacroFun a = (AsmStx a) -> (AsmStx a)
> -- Machine and forth syntax: concrete (structured) data.
> data MacroStx a = ...
> data AsmStx a = ...
> iAsm   :: AsmStx a -> AsmFun a
> iMacro :: MacroStx a -> MacroFun a

So is interpretation a practical issue (in Haskell, OCaml, Scheme,
... you need the syntax representation to be able to manipulate it) or
is this of deeper significance?

Ultimately this should be related to mathematical logic, where formal
statements and and formal rewrite rules are manipulated on the

[1] entry://../staapl-blog/20100314-192109