Thu Nov 18 08:26:15 EST 2010

Again: concatenative languages

Fresh morning, not too much coffee, not too grumpy.  Let's try again..

Where I got yesterday: there are 3 parts to a concatenative language:

1) a meaning function   I :: m -> (t -> t)

2) a concatenation/composition function   f m -> (t -> t)
   where f is a Foldable type

3) an empty program t0

Is it a good approach to use a Monad instead of a Foldable?  

Hmm.. I don't really know where I'm going apart from the very weak
intuition that I'm going to find something.  This is probably for
later.  Maybe I should just ask on the Haskell IRC channel?

First I got to know, what is my question?

This is a primitive machine language:

  prim :: c   -> (s -> s)
  comp :: [c] -> (s -> s)
  nop  :: s
  prim nop = \s -> s

An opcode c has a meaning (s -> s) transforming a machine state s.

A sequence [c] has a meaning (s -> s) obtained by running the
primitive opcodes in sequence.

The `nop' is an empty program, and interpreted it leaves the machine
state intact.

I have one missing element: the compositon container of the target
language!  What I have is really this:

  prim :: c   -> ([s] -> [s]),  prim [] = \ss -> ss
  comp :: [c] -> ([s] -> [s])
I.e. there are both source and target containers (composition,
concatenation) and primitives.  Here we use lists and stacks-as-lists.

So what about picking monads for the code and state composition:

  prim :: c    -> (ms s -> ms s)
  comp :: mc c -> (ms s -> ms s)

What if these are the same?

  prim :: c   -> (m s -> m s)
  comp :: m c -> (m s -> m s)

So far this is still meaningless.  I also do not have a goal yet apart
from finding something "really obvious".

Let's try to formulate again:

Given a function I :: m -> (t -> t) representing the meaning of a
collection of Staapl macros (t -> t), is there a way to characterize
the [m] -> t transformation which compiles a macro program [m] into a
target program t?

Enough.. This isn't going anywhere.

A bit more thought: the real point is that each s->s in a composition
has the _possibility_ to change the _whole_ state, but will probably
not do so.  What you want is several small _local_ changes to state.

But really enough now.