Lambda the Ultimate

maybe they don't make the state visible to the client.

While not quite on topic I'd like to answer the question "Are Applicative Languages Inefficient?". The answer is yes! At least it is true for pure call-by-value languages compared to their impure variants. This is a result by Nick Pippenger in his paper Pure versus impure Lisp. It is interesting to note thought that his result does not hold for a lazy language. In the paper More haste, less speed: lazy versus eager evaluation, Richard Bird, Geraint Jones and Oege de Moor shows that Pippengers's result is not applicable to lazy languages which makes them faster in some cases than strict languages. But that doesn't mean that every algorithm can be implemented optimally in a pure lazy language, just that the algorithm Pippenger used can.

Pippenger's paper states that, for the eager sequential declarative Lisp computation model, an on-line computation that takes n steps in the Lisp + mutable state model may take Omega (n log n) steps in the Lisp model.

This result is correct, but it is not a limiting factor for programmers wishing to write efficient declarative programs. You can always write a sequential declarative program that uses a single-threaded accumulator to simulate mutable state. Then, to get the same efficiency as a stateful program, it suffices to implement this accumulator using destructive assignment. (This corresponds to having a compiler recognize the single-threaded accumulator, which is easy to do. Note that Pippenger excludes such uses of the compiler in his paper!) The sequence of execution steps is the same for the original program and the mutable state program. So that *in practice*, declarative programming is not less efficient than stateful programming, despite Pippenger's result!

There is a general lesson to be learned here: theoretical limitations should not be taken too seriously, because they can very often be bypassed by somebody who wants to get the job done. This is because they are always based on a specific set of hypotheses, not all of which are relevant or important in practice. Changing the hypotheses slightly can completely change the theoretical result.

As an aside, another example of this "fragility" of theoretical results is Boebert's famous 1984 result on the limitations of capability machines for building secure systems: "unmodified capability machines cannot enforce the *-property". Since the *-property is important (lower clearance can communicate with higher clearance without leakage from high to low), this result convinced people that capability machines were not practical. This despite that a slightly more realistic capability model does not have this restriction at all! For a nice explanation, see the paper "Paradigm Regained: Abstraction Mechanisms for Access Control" by Mark Miller and Jonathan Shapiro, ASIAN 2003: 224-242.

As an OT-footnote to this OT-discussion ;-)



From the abstract of the Lisp thingy - something which just caught my eye:

"It is well known that cyclic list structures can be created by impure programs, but not by impure programs."

This seems dated, we now know how to tie a knot.

And by Peter:

What this means is that in practice, the use of state is a question of naturalness and not of efficiency.

So it boils down to "How natural is a pure program without state?" and "Is there a natural stateless equivalent for each program for which one has a natural stateful solution?" Who knows? I don't - but I know at this point I don't want to give up the freedom to just implement it in the way which feels natural to me without searching for the statefree natural solution [if that exists].
But yeah, there is no point discussing taste.



[ But in my heart I still want my "industrial/impure" Haskell - and I still think purity doesn't scale ;o) ]





btw: Oh yeah, Josef, my brain:

80% interpersonal, 100% visual, 40% verbal, and 180% mathematical.
Hmpf, figures...

Phew, just under 200% ;-)

(And the other scores were 61%, 52%, 38%, 86%)

"It is well known that cyclic list structures can be created by impure programs, but not by pure ones."

This seems dated, we now know how to tie a knot.

Does not tying the knot rely on lazy evaluation? Is not Lisp strict?

[Sorry Ehud, I hope you don't object to me answering this question]

Hmmm. I guess this is a "don't take scientific results too seriously answer".

Does not tying the knot rely on lazy evaluation?

No, I think not. It depends on: can I pass a reference of a term [to a function] before it [the term] is fully evaluated. Is that lazy evaluation or is it the fact that you can make use of graph rewriting semantics for some pure language?

I don't think he should have made that claim (at least not when discussing pure vs impure on the abstraction level of implementation languages/lisp).

Sure, why should I?

Oh, answering OT remark on OT posts on previously discussed papers. Whatever, ok.

Anywayz. Thanks for setting up the chairs, tables, and beer mugs that makes LtU.

Both these papers were discussed here before, as you can imagine. These are basic results I guess everyone should be familar with.