The Miser Project  

Collaborative articulation of how abstraction and language is employed in the computational manifestation of numbers -- including analysis of the role of syntax, semantics, and meaning in the specification and use of software interfaces.

Click for Blog Feed
Blog Feed

Recent Items
Computer Science Classics: Your Picks?
Cybersmith: How Many Functions Am I Holding Up?
More Annotated Turing
Different (Universal) Computation Models
2007-11-14: SeaFunc Meet-Up
Miser Project: Repaving Kick-Off
Hark! Is That an Idiom That I See Before Me?
Whither Peano?
Miser Hacks II: A Hole to Bind Them
Petzold Annotates Turing!

This page is powered by Blogger. Isn't yours?

visits to Miser Project pages

The nfoCentrale Blog Conclave
Millennia Antica: The Kiln Sitter's Diary
nfoWorks: Pursuing Harmony
Numbering Peano
Orcmid's Lair
Orcmid's Live Hideout
Prof. von Clueless in the Blunder Dome
Spanner Wingnut's Muddleware Lab (experimental)

nfoCentrale Associated Sites
DMA: The Document Management Alliance
DMware: Document Management Interoperability Exchange
Millennia Antica Pottery
The Miser Project
nfoCentrale: the Anchor Site
nfoWare: Information Processing Technology
nfoWorks: Tools for Document Interoperability
NuovoDoc: Design for Document System Interoperability
ODMA Interoperability Exchange
Orcmid's Lair
TROST: Open-System Trustworthiness



Miser: The Immutability of Obs

In the Miser formulation of a functional/applicative computing machine, the fundamental data structures, the obs, are immutable.  There is no operation that can change an ob.   Obs behave very much as mathematical objects (as opposed to the object-oriented programming sort), and mathematical reasoning is applicable to obs and the operations defined on obs.   This is a very strict condition.   It is intended that the computer manifestation of obs be as indistinguishable from the mathematical as possible given the realities of computational speed and memory-capacity limitations.

There is no way to alter an ob.  It is as if obs are neither created nor destroyed, they are merely found.  It takes some work to maintain such an illusion, especially in a computation distributed across multiple computers, but it is critical to the formulation of Miser that it be made so.

This immutability also prevents the appearance of cyclic ob structures except for the special cases of singletons and only singletons being immutably self-cyclic [2].   Immutability also allows a single, well-defined equality relation, signified in the usual way by "=".

Immutability First, Mutability Another Way

The purpose has been to start with a "pure" system in this way.  When mutability is finally entertained, it will be in ways that are strictly-confined and that do not alter the immutability of obs in any way whatsoever.

This can be done with Miser simply by breaking its connection with those functional-programming systems, especially Lisp and Scheme, that have allowed relatively unrestricted mutability of their fundamental data structure from the beginning.  I don't know if it was a mistake to have done that, although I long thought so.  I do know that it would be a mistake for that to be done with Miser.  Although later functional-programming systems have been more generous with immutability, I want to take a fresh look that begins with immutability as a given.

Snatching from the Jaws of Mutability

Meanwhile, serious, practical interest has arisen in having immutable data structures where that was not the natural state of affairs before. 

Really un-mutable Scheme.  It was amusing to see that version 4.0 of PLT Scheme is going to have the fundamental pairing operation for list structures (the Lisp cons[x; y]) involve immutable structures [1].  This is part of a shift from mutability as the default to mutability as the exception.  There will be mutable forms of the data structures, but new operations are required for using them.  In a comment, it is revealed that the opportunity to rely on a single "=" is not being taken just yet.

There is also interest in operating with immutable structures in object-oriented systems.  Eric Lippert provides a key element to the basis for such interest [3]:

"Objects which are truly madly deeply immutable have a lot of great properties. They are 100% thread safe, for example, since obviously there will be no conflicts between readers and (non-existent) writers. They are easier to reason about than objects which can change. But their strict requirements may be more than we need, or more than is practical to achieve."

Lippert is exploring ways to have deeply immutable objects when they are really useful, but not having that be fundamental or always be required.  His programming examples that are used to tease out deep immutability for practical situations are very challenging and useful to explore.   A systematic approach and further examples can be found in the work of Chris Okasaki [4, 6].

Although thread safety is an important benefit, there are others:

  • Immutable data structures are inherently distributable, whether completely or partially, and they can be replicated without concern for synchronization since they never change.
  • Partitioning of a problem and introduction of parallel processing can sometimes be extremely efficient with  quasi-immutable data structures [5]. 

Interest in immutability seems to be arriving hand-in-hand with awakening interest in functional programming as well.

The inherent distributability and thread safety, as well as the amenability to mathematical treatment, are the motivations for persisting in immutability-first for Miser.

[1] Matthew Flatt: Getting rid of set-car! and set-cdr!  PLT Scheme (web log), 2007-11-12.
[2] Dennis E. Hamilton: Miser Hacks II: A Hole to Bind Them.  Numbering Peano (web log), 2007-11-04.
[3] Eric Lippert: Immutability in C# Part 10: A double-ended queue.  Fabulous Adventures in Coding (web log),, 2008-01-22.The ongoing series is under the immutability category.  The initial posting provides a nice classification of immutability du jour, and an earlier series develops some interesting data structures for an A* search algorithm.
[4] Chris Okasaki: Purely Functional Data Structures.  Cambridge University Press (Cambridge: 1998), ISBN 0-521-66350-4 pbk.
An earlier version of the material, with some differences in coverage, can be found in Okasaki's 1996 thesis.
[5] Jeffrey Dean and Sanjay Ghemawat: MapReduce: Simplified Data Processing on Large ClustersComm. ACM 51, 1 (January 2008), 107-113. 
The original 2004 Google Research publication is available on-line.
[6] Chris Okasaki: Ten Years of Purely Functional Data StructuresTeaching, Playing, and Programming (web log), 2008-02-08 (via Lambda the Ultimate).
A wonderful retrospective on functional data structures, the anguish of immutability, and how it is overcome.  It will be interesting to see how some of the remedies fail or survive under distribution of the data structures.

[update 2008-02-08T12:13 -0800: I was bowled over to see that Chris Okasaki is blogging and now his reflections on Purely Functional Data Structures have been posted in a wonderfully literate essay.  That is reflected in the update here.  I finally remembered that the C.ACM version of [5] is available on-line and I now link to it here.  I finally realized that my use of relative links to fragments in these posts is problematic on the front pages of my blogs.  I am not going to do anything about that.  It's a great example of failing to consider the overall system, though.]

Construction Structure (Hard Hat Area) You are navigating The Miser Project.

template created 2004-05-31-22:34 -0700 (pdt) by orcmid
$$Author: Orcmid $
$$Date: 10-04-30 21:00 $
$$Revision: 22 $