Home » forums » LtU Forum

Short examples of complex use of state?

Hi, I'm looking for some short algorithms that use state in tricky ways, where by "tricky" I mean:

1. State is used nonlinearly. That is, there should be multiple pointers to some of the state in the program.

2. The state should be "visible" to clients. Something like memoizing or caching is stateful and nonlinear, but it has no visible side-effects.

3. The state should have an indefinite lifetime -- that is, stack allocation isn't a sufficient memory management strategy.

4. Ideally, the state should be higher-order -- I'd like to see references of function (or object) types, so that there's a pointer to code. This is less critical than the others, but still nice.

Any ideas? I've thought of union-find, and I would guess there are graph algorithms that have these properties, but I'm relatively ignorant about them.

By neelk at 2005-05-27 15:55 | LtU Forum | previous forum topic | next forum topic | other blogs | 10590 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

My thoughts

In reading through your requirements, union-find came to my mind as well, before I read that you had thought of it. For graph algorithms, maybe consider minimum spanning tree or finding strongly connected components. Something else to consider is SAT solvers like zchaff.

By Jeffery Walker at Fri, 2005-05-27 16:15 | login or register to post comments

Possibly DaCapo benchmarks?

The Computer Language Shootout recently added a healthcare test that seems to require a large tree of mutable state. That benchmark comes from the Olden benchmark. More description in the paper, Software Caching and Computation Migration in Olden (1995). Maybe finding interesting parallel benchmarks is a good heuristic for your search?

--Shae Erisson - ScannedInAvian.com

By shapr at Sat, 2005-05-28 14:31 | login or register to post comments

how about

splay trees?

By Dave Herman at Sat, 2005-05-28 19:00 | login or register to post comments

oh, wait...

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

By Dave Herman at Sat, 2005-05-28 19:00 | login or register to post comments

BDDs

What about Binary Decision Diagrams? They are stateful alright. And pointers pointing all over the place. (A BDD is really a DAG if you're familiar with the concept.) Though I'm not quite sure I understand your second point so I don't know if BDDs qualify. Could you elaborate a bit perhaps.

Finally I can recommend reading up on graph algorithms. They're great fun.

By Josef Svenningsson at Sun, 2005-05-29 10:15 | login or register to post comments

Declarative algorithms and state

Here are some pointers that are not a direct answer to your question, but maybe they are relevant.

Check out the article "Are Applicative Languages Inefficient?" by Carl Ponder, Patrick McGeer, and Antony Ng, SIGPLAN Notices 23(6): 135-139 (1988). It's available at the ACM Portal, but you need a subscription. The article reviews seven problems for which the authors have not been able to find efficient applicative algorithms.

Another good place to look is Chris Okasaki's book "Purely Functional Data Structures", Cambridge University Press, 1998. This book goes in the other direction: it shows how to design efficient functional implementations of data abstractions for which you might naively think they need state (such as constant-time queues). The main idea is to use lazy evaluation in a clever way. The intuition is that using lazy evaluation is like spreading butter on bread: if you design the algorithm cleverly, the lazy evaluations can be spread out uniformly instead of being bunched up at one spot.

I also recommend that you read section 4.8 of CTM, "Limitations and extensions of declarative programming". Basically, the answer is that declarative programming is as efficient as stateful programming if one is allowed to rewrite the program to be less natural. What this means is that in practice, the use of state is a question of naturalness and not of efficiency.

By Peter Van Roy at Mon, 2005-05-30 09:54 | login or register to post comments

Applicative Languages ARE inefficient.

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.

By Josef Svenningsson at Mon, 2005-05-30 10:41 | login or register to post comments

Are applicative languages efficient?

The answer to this question depends on what your goals are. Are you exploring the theoretical limits of computation models? Or are you interested in writing efficient programs? The answer to the question is not the same in these two cases.

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.

By Peter Van Roy at Mon, 2005-05-30 11:27 | login or register to post comments

Pure vs Impure Lisp

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%)

By marco at Mon, 2005-05-30 14:50 | login or register to post comments

Tying the knot

"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?

By Jim Apple at Mon, 2005-05-30 16:10 | login or register to post comments

Ouch again

[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).

By marco at Tue, 2005-05-31 08:49 | login or register to post comments

Huh?

I hope you don't object to me answering this question

Sure, why should I?

By Ehud Lamm at Tue, 2005-05-31 18:23 | login or register to post comments

Ah, Ok

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.

By marco at Wed, 2005-06-01 19:44 | login or register to post comments

Pure/Impure classic results

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

By Ehud Lamm at Mon, 2005-05-30 18:16 | login or register to post comments

On interpreting theoretical results.

Peter. Thanks for adding some nuance to my perhaps overly rigid previous post. I agree with everything you wrote, especially this:

theoretical limitations should not be taken too seriously.

By Josef Svenningsson at Mon, 2005-05-30 13:10 | login or register to post comments

named regexps

named regexps seem to meet everything but the last requirement. since they are really graph algorithms perhaps that is what other people have suggested too (i didn't understand all the comments).

by "named", i mean that you can name and refer to matches within the regular expression, and can access named matches afterwards. so, for example, if two different parts of the regexp have the same name, then they must be identical.

By andrew cooke at Mon, 2005-05-30 16:42 | login or register to post comments