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.
The nfoCentrale Blog Conclave
nfoCentrale Associated Sites
Technorati Tags: PLT Scheme, immutable objects, models of computation, distributed computation, manifest mathematical objects, Miser, oMiser
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 . 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 . 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 :
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:
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.
[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  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.]
|You are navigating The Miser Project.|