Lambda the Ultimate

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.

I just came accross this interesting paper: Pure bigraphs: structure and dynamics. From the abstract:

"...it is shown that behavioural
analysis for Petri nets, pi-calculus and mobile ambients can all
be recovered in the uniform framework of bigraphs."

An interesting thing from my point of view is that an attempt is made to provide a descriptive explanation of the material, obviously along with math proofs.


There are also three, very basic, audio lectures(!) on pi-calculus at the following site: http://courses.cs.vt.edu/~cs5204/fall03/DayByDay.html.

Some of you might be interested in the following Conference during the first weekend in June at UBC in Vancouver, Canada:

Conference: Foundational Methods in Computer Science (FMCS05)

Local organizer: John MacDonald
Location: All sessions are held in WMAX 110 - 1933 West Mall
Dates: June 3-5, 2005

Friday, June 3, 2005

9:00-10:30a.m. Ernie Manes, UMass Amherst, USA
From locally-Boolean rings to sum-ordered categories

11:00-12:30p.m. Vaughan Pratt, Stanford University, USA
Recent developments in Chu spaces

2:30-4:00p.m. Steve Bloom, Stevens Institute of Technology, USA
Regular words

4:30-6:00p.m. Robin Cockett, University of Calgary
Restriction Categories and Ehresmann's Theorem

Saturday, June 4, 2005

9:00-9:50a.m. Paul Taylor, Manchester, UK
Extension of ASD (from locally compact locales) to and
beyond general locales

9:50-10:30a.m. Cyrus Nourani, USA
Functorial Model Computations

11:00-11:30a.m TBA

11:30-12:15p.m. Art Stone, Vancouver, Canada
2-Dimensional Adjunctions

2:00-2:30p.m. Varmo Vene, University of Tartu, Estonia
Signals and Comonads

2:30-3:00p.m. Bob Rosebrugh, Mt. Allison University
TBA

3:00-3:30p.m. Chris Dutchyn, University of British Columbia
Aspects are Dual to Objects

4:00-5:00p.m. Philip Mulry, Colgate University, USA
Monad Compositions on Recursive Data Types

Sunday, June 5, 2005

9:00- 9:30a.m. Brian Redmond, University of Ottawa,
Categorical Models for Soft Linear Logic

9:30-10:00a.m. X. Guo, University of Calgary,
Range Restriction Categories

10:00-10:30a.m. Dana Harrington, University of Calgary
TBA

10:30-11:00a.m. Break

11:00-11:30a.m. David Oury, McGill University,
TBA

11:30-12:00 Pieter Hofstra, University of Ottawa,
TBA

12:00-12:30p.m. TBA

Last updated: 5/27/05

For further information see the conference website:
http://www.pims.math.ca/science/2005/05fmcs

A Judy tree is generally faster than and uses less memory than contemporary forms of trees such as binary (AVL) trees, b-trees, and skip-lists. When used in the "Judy Scalable Hashing" configuration, Judy is generally faster then a hashing method at all populations.

Some of the reasons Judy outperforms binary trees, b-trees, and skip-lists:

• Judy rarely compromises speed/space performance for simplicity (Judy will never be called simple except at the API).
• Judy is designed to avoid cache-line fills wherever possible.
• A b-tree requires a search of each node (branch), resulting in more cache-line fills.
• A binary-tree has many more levels (about 8X), resulting in more cache-line fills.
• A skip-list is roughly equivalent to a degree-4 (4-ary) tree, resulting in more cache-line fills.
• An "expanse"-based digital tree (of which Judy is a variation) never needs balancing as it grows.
• A portion (8 bits) of the key is used to subdivide an expanse into sub-trees. Only the remainder of the key need exist in the sub-trees, if at all, resulting in key compression.

The Achilles heel of a simple digital tree is very poor memory utilization, especially when the N in N-ary (the degree or fanout of each branch) increases. The Judy tree design was able to solve this problem. In fact a Judy tree is more memory-efficient than almost any other competitive structure (including a simple linked list). A highly populated linear array[] is the notable exception.

Worth a look, considering the open-source LGPL license and range of applications. HP released this library in 2004. From the PDF manual,

Judy arrays are remarkably fast, space-efficient, and simple to use. No initialization, configuration, or tuning is required or even possible, yet Judy works well over a wide dynamic range from zero to billions of indexes, over a wide variety of types of data sets -- sequential, clustered, periodic, random.