Tue May 4 12:45:05 EDT 2010
Implementing DFN as a State monad.
1. Lifting functions to channels.
Objective: Channels implement the Num class. This can be done in
two steps: implement Functor and Applicative, then use `mapf' and
Note that a Channel is a MonadState, so `mapf' and `liftA2' are
2. Implement "connect".
The two sides of a channel:
- Construction (through the lifting operations) creates a
computation that takes a context and produces a value and a
- Consumption queries the context, and either reuse a value if
it is already computed, or triggers computation.
The whole representation is still functional (outputs are
"created" by the invocation of a function). To connect this view
to explicit output descriptions, a "sink" type is probably
Making the output explicit requires an "arrow lift". (a -> b) ->
(DFN in out)
So, let's separate the two ideas:
1. Abstraction of memoization as a state monad.
2. The arrow lift: making outputs explicit such that "connect"
The latter probably requires a level of indirection to connect
intermediate nodes (a consequence of SSA form) to output nodes. It
seems that this small sacrifice (the presence of explicit "sink" nodes
like indexed arrays as lvalues in C) yields a structure that can be
completely embedded in a lexical language.
It seems that the lesson to learn is that a DFN is not symmetric
wrt. input/output. Turning the arrows around still means it is a
directed acyclic graph, but there is a little bit more structure to
capture. Lexical structure (one binding, multiple uses) neatly
reflects this structure.
Building the memostructure as a state monad seems straightfoward. I
have examples. Just need to get used to Haskellisms. The arrow
lifting seems more involved. I'm missing the "two ends of the arrow"
Write down "connect" first.
connect o i =
o1 = mapf f i1
o2 = mapf f i2
(connect o1 i2)
What does "connect" do? It "reduces" a network, i.e. eliminates one
_input_ while leaving all outputs available.
So, start from this:
* "connect" eliminates an input from a network.
* outputs need to be "exported" explicitly, since each intermediate
output node could be made public.