Re: [Chicken-users] optimizing mutually recursive loops

[Alaric Snell-Pym]

[cunning optimisation stunts]

Some would say that the matrix multiply should just be written in C
and FFIed.

Some would say that Chicken should be improved until you can write
natural Scheme code without a thought for performance, and Chicken
should general optimal C as good as any human could handcode (although
they may get a bit vague and hand-wavey as to how this might be
accomplished).

But finding middle grounds is interesting; Alex has found one by
bending Chicken to his will cunningly. I wonder, though, how this can
be generalised a bit, since I have an instinctive distaste for
specific hacks: a let-machine is, in a way, a little subset of Scheme
that can be implemented particularly efficiently by Chicken.

Now I, in my own work, have sometimes had to implement low-level
operations involving binary data, and I've hankered for a way to do
them more efficiently in Scheme so I don't have to go into C so often.
What I've been thinking of is somewhat similar in execution, but first
a history lesson...

One of my inspirations in programming language technology (other than
Lisp) is Concurrent Clean, a Haskell-like purely functional language
that, unlike Haskell, implements mutating operations (non-copying
array ops, I/O, that sort of thing) using uniqueness typing.
Basically, if an object like an array passed into an array-set! style
function can be shown by the type system to be the only reference to
that object in the system, then array-set! can modify it in-place and
return the 'same' array with a new value, while still being a pure
function. If you pass it in a non-unique reference, then it has to
make a copy of the array to mutate and return.

As well as implementing efficient updates on large arrays, this is
also used for I/O; a top-level Clean program is a function of type
Unique World -> Unique World. And the system provides a number of
operations on type World, each of which require a unique reference to
the World and return a unique reference to a World. Eg, there's a
function that takes a World and a string, and returns a new World in
which that string has been displayed on a display device somewhere;
and a function that takes a World and returns a string and a World in
which some time has passed and somebody has typed that string in and
pressed enter... in effect, the entire universe is encapsulated in a
logical object so the program can 'mutate' it using the same trick.
But because the functions that accept Worlds all require them to be
unique, the type system forces the program to only ever have a single
World; if you try and keep a reference to a particular state of the
World then it stops being unique, so your program gives a compile-time
type error when you try and use that World or return it from 'main'.

Anyway, you can write imperative-style code in Clean, but it looks a
bit ugly. I can't remember the exact syntax, but in spirit, you end up
with:

SayHello :: !World -> !World
SayHello World =
  let World2 = printString (World, "Please enter your name") in
  let World3, Name = inputString (World2) in
  printString (World3, "Hello, " + Name)

This has benefits over monads - for a start, you can compose them in
parallel; your program might have regions that mutate some array, and
regions that mutate the world, and those two bits can be interleaved;
while in Haskell you can only do this by bunging everything into a
single IO monad, which ends up enforcing more sequentiality than is
needed (subject only to actual data-flow requirements between the two
"threads", the Clean compiler has more scope to rearrange or
parallelise stuff).

And it's really neat in that unique values don't need garbage
collection. A function that takes an object and doesn't return it (in
any form), if it's given a unique value, knows it never needs it
again. Functions that require unique arguments can just hardcode
deallocation; functions that might take a unique argument can, if they
destroy their reference to it, do an "if unique then deallocate"
operation reminiscent of a reference count decrement. Only shared
values are prone to garbage collection, and if the compiler can
correctly deduce the uniqueness of lots of data, that's lots of gc
overhead removed.

Anyway. Having noticed that the recursive-lets-with-new-names syntax
sucked, I followed a chain of thought as to how I'd improve it.

1) I don't know why the examples I saw used a new name for the World
each time - surely the nesting lexical scopes of the lets would let
you write:

let World = printString (World, "Please enter your name") in
 ...

and keep things neater?

2) Isn't a mutually-recursive set of functions passing unique values
between themselves just a state machine in register transfer language,
and thus really trivial to implement efficiently?

Now, I have a theory that state machines are a really good syntax for
imperative stuff. Structured programming has put goto out of fashion,
but used properly it was a good thing; the problem was that people
used goto for large-scale program structure, which was too large a
scope for a human to keep track of what's what, leading to the fabled
spaghetti code. But the baby was thrown out with the bath water.

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. "Oh, in this case, we need to go and restart from this
point up here". At which point, you need to rearrange the whole thing
in order to fit the new structure. This is particularly obvious in
exception handling; C programmers often have to resort to a "cleanup:"
label at the end of a function that they can goto, which exceptions
are to some extent syntactic sugar for.

But written as a state machine, such extra control flow arcs are easy
to add.

So, these two threads have been bubbling around in my head, and 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. Obviously, I was just going to make
them generate letrecs, since I was interested in designing a structure
that I knew *could* be implemented efficiently if made a special form,
rather than actually trying to get Chicken to be efficient, but that's
by the by; if I came up with a syntax that was elegant, we could look
at an efficient implementation later - perhaps even one that the
chicken core knows about (or, more likely, that compiles to a low-
level special form that just handles generating a set of goto-able
labels and gotos between them).

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