Lambda the Ultimate

The example is similar, though the point is very different. The obsession with "eliminating multiple passes" through tying-the-knot techniques and the credit-card transformation is often a red herring. The article's example certainly is; subtracting the average off of a list inherently requires two passes. Tying the knot builds a list of thunks, not floats... approximately speaking, it makes the second pass implicit.

import Data.List as List

--- Listing Two ---

diff     :: [Float] -> [Float]
diff xs  = map (\x -> x - (avg xs)) xs

avg    :: [Float] -> Float
avg xs   = sum xs / genericLength xs

diff2    :: [Float] -> [Float]
diff2 xs =
  let
    nil avg          =   (0.0, 0.0, [])
    cons x fs avg    =   let (s,l,ds) = fs avg
                         in (s+x,l+1.0,x-avg : ds)
    (sum,length,ds)  =   foldr cons nil xs (sum / length)
  in ds

diff3 :: [Float] -> [Float]
diff3 xs = map (\x -> x - (average xs)) xs

average :: [Float] -> Float
average xs = sum / length
  where
   f (tot,count) x = ((,) $! tot + x) $! count + 1
   (sum, length) = List.foldl' f (0.0, 0) xs   

test f xs = let xs' = f xs in xs' == xs' 
   
main = return ()

Compiled with "ghc -O" and loaded into ghci, "test diff [1 .. 100000]" takes roughly the same amount of time as "test diff2 [1 .. 100000]", which both take longer than "test diff3 [1 .. 100000]". Moreover, diff3 is the only one to return a correct answer when the size of the list is increased to 1,000,000... the others overflow the stack. Not to mention that diff2 breaks GHC's list deforestation... diff is not a good consumer, but it is a good producer, and that map is liable to get fused into the calling function.

So, in this case, fusing sum and length into one pass is worthwhile, tying the knot is not. A useful example of the latter is building an environment for a set of recursive bindings in an interpreter. Here, all you are doing is filling a hole in a symbolic data structure, not building thunks, thus there isn't an implicit second pass.

A follow-on thought occurs to me: the problem with the example is that it is attempting to do coinduction on a flat type. While this certainly has a sensible semantics, it's not where current implementations really shine.

Flat types are those without any partial values. Common examples are characters, machine integers and floats, ML's unit type, etc. The only values that inhabit these types are computational divergence and a fully formed values.

However, say your number type isn't flat. Say you are using or building a library for exact real arithmetic, and you want to implement a particularly efficient way of taking the average of a list of numbers. In this case, I would most certainly investigate algorithms similar in nature to diff2.

Moreover, I'm guessing that it's fairly straightforward to derive diff3, the best performing solution on flat types, directly from diff2, which might perform better on non-flat numbers. I'm not sure that the converse would be true, however.

I would venture a guess that diff2 or something rather similar can be turned into a very compelling example, in an appropriately modified context.

For those of us who have not previously seen the phrase "un-CAF your list", this page might help a little.

It seems like it might be a variant on traditional dataflow; instead of functions blocking until data is available, functions are moved to the head of the queue when data is available.

I'm guessing that the dataflow and control-flow analyses for such a scheme would often be too complicated to be done at compile time; it seems like this would necessitate run-time elements. I'm not real familiar with the implementation of dataflow languages though; in Oz you create multiple threads in order to express dataflow, and I doubt your variant would be any different.

The ivory towerist in me tells me it surely is an evaluation strategy for a graph rewrite system, at least that's the easiest way for me to understand it. That's where I'd look in literature.

Apart from the variable elimination technique from satsolving, another thought:

It occured to me that your idea might be problematic though. I guess, one restatement of your strategy is that in general all functions which refer to an argument get rewritten when the refcount of the argument decreases. Functions are also arguments of other functions, what happens when functions get rewritten?

The ivory towerist in me tells me it surely is an evaluation strategy for a graph rewrite system, at least that's the easiest way for me to understand it. That's where I'd look in literature.

Thanks for the tip, I'll start diving into that end of the pool.

It occured to me that your idea might be problematic though.

Yeah, I haven't thought it through very far. But before I started implementing it as a toy interpreter, I thought I'd check with LtU to see if it was a well-understood problem.

I think your original post and this post are both great idea's.

However, a small alternative view.

Haskell's memoization stems probably from two origins:

1. Graph rewrite semantics just imply sharing, [implicit memoization]
2. Need for speed, or performance. [explicit memoization]

I think 2. is probably a main reason. Probably the compiler would otherwise be significantly slower because it would need to re-evaluate a lot of basic terms each time (for instance, a computed string to match upon).

I think in the end, for a programmer, however, it is not worth it. I do believe memoization can be implemented without a substantial overhead. However, it makes the runtime substantially more complex, and it probably will always have "weird" (in the programmer's eyes) runtime characteristics.

In the end, I think performance optimization should always be a choice of the programmer.

So, unless you are writing a sufficiently high specific purpose language, say Matlab, I think these kind of optimizations should be avoided. Even if they are very convenient.

[Sharing is not memoization. The adding of tables to remember precomputed values is, and that is what I meant in 2.]