Re: [Chicken-users] optimizing mutually recursive loops

[Alaric Snell-Pym]

On 16 Feb 2009, at 5:09 pm, Tobia Conforto wrote:

> Alaric Snell-Pym wrote:
> > Some would say that the matrix multiply should just be written in C
> > and FFIed.
>
> In fact, most would just (use blas) or such.  But I understand it
> was just an example.

Well, yeah ;-)

> > Concurrent Clean, a Haskell-like purely functional language that,
> > unlike Haskell, implements mutating operations using uniqueness
> > typing.
>
> I'm wondering whether we could apply a similar idea to Chicken.  Do
> you think there is any space for improvement, where we could somehow
> reduce GC by declaring stuff as unique?  I know I'm just hand-waving
> at this point, I need to think more about it.

Quite possibly. In fact, Henry Baker (who wrote the paper on the
Cheney MTA algorithm Chicken uses) has papers on the topic of Linear
Lisp - see the references at 
http://en.wikipedia.org/wiki/Uniqueness_typing#Discussions_of_uniqueness_typing_in_programming_languages

> > Any complex imperative algorithm involves a certain number of
> > nested control structures, and before long, you need to add a
> > single extra arc to that.
>
> This is quite true and I've found Scheme's named let an excellent
> syntax for this kind of algorithm. You can just write the loops in
> the natural order of variable declaration, and then jump back and
> forth as you need: "Oh, I'll just restart with the 2nd outer loop
> here: (loop-row x (+ y 1))."
>
> In fact, I've been writing "named loops" in other languages too,
> where the language lets me do it... which means, if it has a syntax
> for lambdas. But they never come out as nicely as in Scheme.

Yeah! I've made delightful use of escape continuations in the command
line interface for Ugarit. My core command line function presents a
prompt and processes what the user inputs; if this is a "cd" then it
recurses to work in the subdirectory, while "cd .." returns; other
commands just tail-call the CLI function again, but "quit" escapes the
whole lot by just calling a continuation established by a top-level
let/cc. This made for a very natural structure; similar code in C I've
written always seems to involve a boolean flag that requires sometimes
complex handling...

> > But written as a state machine, such extra control flow arcs are
> > easy to add. I've been meaning for some time to experiment with
> > writing Scheme macros that implement a state machine language
> > designed for ease of use, and experimenting with using them.
>
> Nice! Do you have any prototype we could play with, or ideas we
> could discuss?

No prototype, but lots of ideas:

1) Each state should be parameterised. This is a trick to convert a
system of "state machine plus mutable memory" to just "state machine"
- basically, you describe potentially infinite families of states in a
single rule by giving the rule parameters. Rather than having mutable
variables, you just pass parameters to states, and to "modify" them
they just pass new values on to the next state (or to themselves, if
looping). This reduces the state machine to a set of mutually
recursive pure functions, and the uniqueness just removes the need for
GC and opens up implementation as a set of registers.

2) Yet it'd also be nice to automate some of this by establishing a
group of states as a form of "lexical scope", declaring some state
variables for that scope, and having the states within that scope,
when they call each other, automatically passing any variables they
don't explicitly pass.

An example might make that clear. Say your state machine, from time to
time, has to do something a hundred times. So you might have a
parameterised state that does something N times. Say this thing has
several steps - the steps would have to pass N around between
themselves so the last state can jump back to the original state,
passing in N-1. But that might get tiresome - it'd be nice to write:

(let (N)
  step1:
    ...
    ...
    ...
    (goto step2)

  step2:
    ...
    ...
    ...
    (goto step3)

  step3:
    ...
    ...
    ...
    (if (zero? N)
       (goto ...exit...)
       (goto step1 N: (- N 1)))

Eg, N is being automatically passed along when step2 calls step3 (the
initial entry to step1, being from outside the 'scope', must pass it
in explicitly, of course); but step3 explicitly gives a value for N,
which is then used.

I don't know if this is a good idea or not - hidden state can be bad,
and it requires keyword-style arguments to states, which may be more
pain than it's worth.

2) How about reuse of portions of state machines? They should allow
some kind of lexical scope, too. A complex set of states should be
packagable into a black box with a set of defined entry states, and
"dangling pointers" out to exit states that must be supplied when the
package is used, in effect providing enough exit continuations with
the correct signatures. It's not quite like a closure, since it might
have several entry states. But perhaps that's not important and it
should just be called a closure?

Really, I need to work on some examples and work on a syntax that's
flexible yet pleasant!

ABS

--
Alaric Snell-Pym
Work: http://www.snell-systems.co.uk/
Play: http://www.snell-pym.org.uk/alaric/
Blog: http://www.snell-pym.org.uk/?author=4