Clojure's Approach to Identity and State

Clojure has been discussed here before. It fits in the Lisp family with S-expressions, macros, and functions as values. Like most Lisps, it's dynamically typed and impure. But its target focus is concurrency so symbols are defined immutably by default; its standard library's collection structures are immutable and persistent; and its various mutable concepts are threadsafe except, of course, for the back doors implied by I/O and JVM library interoperability. See vars, refs, and agents.

What I wanted to highlight is position paper of sorts that Rich Hickey has posted on Clojure's Approach to Identity and State. An excerpt:

While some programs are merely large functions, e.g. compilers or theorem provers, many others are not - they are more like working models, and as such need to support what I'll refer to in this discussion as identity. By identity I mean a stable logical entity associated with a series of different values over time. Models need identity for the same reasons humans need identity - to represent the world.
In Clojure's model, value calculation is purely functional. Values never change. New values are functions of old, not mutations. But logical identity is well supported, via atomic references to values (Refs and Agents). Changes to references are controlled/coordinated by the system - i.e. cooperation is not optional and not manual.

Hickey also addresses the choice to not follow Erlang's model.

There are other ways to model identity and state, one of the more popular of which is the message-passing actor model, best exemplified by the quite impressive Erlang. ... It is important to understand that the actor model was designed to address the problems of distributed programs. And the problems of distributed programs are much harder ... Clojure may eventually support the actor model for distributed programming, paying the price only when distribution is required, but I think it is quite cumbersome for same-process programming. YMMV of course.

The essay is worth a read on a couple of levels of interest to LtU. At an abstract level, it's a good example of a well-articulated design justification. Agree or not, it's clear that Hickey gave thought to his decisions. Too many language designers fall into the trap of blindly inheriting semantics from a favorite language and end up putting new lipstick on the same pig. Any language designer would do well to write an essay or two like this before jumping into their venture.

At the specific level, the core approach is certainly worthy of discussion and alternative designs. Is mutable state really the best way to deal with "working models"? Are there things that the pure functional camp can do to make "working models" more convenient, e.g. do Clean's uniqueness types fit the bill at least for sequential programming, or are they too restrictive? Are there things that can make Erlang style actors less cumbersome to use especially when distribution isn't necessary?

Simply efficient functional reactivity

Simply efficient functional reactivity. Conal Elliott.

Functional reactive programming (FRP) has simple and powerful semantics, but has resisted efficient implementation. In particular, most past implementations have used demand-driven sampling, which accommodates FRP's continuous time semantics and fits well with the nature of functional programming. Consequently, values are wastefully recomputed even when inputs don't change, and reaction latency can be as high as the sampling period.

This paper presents a way to implement FRP that combines data- and demand-driven evaluation, in which values are recomputed only when necessary, and reactions are nearly instantaneous. The implementation is rooted in a new simple formulation of FRP and its semantics and so is easy to understand and reason about.

On the road to efficiency and simplicity, we'll meet some old friends (monoids, functors, applicative functors, monads, morphisms, and improving values) and make some new friends (functional future values, reactive normal form, and concurrent “unambiguous choice”).

I'm not sure exactly where to classify this submission to ICFP 2008, but I think many here will be interested in it.

Sliced Bananas On Opaque Data

Sliced bananas on opaque data (The expression lemma). Ralf Lämmel and Ondrej Rypacek.

Algebraic data types and catamorphisms (folds) play a central role in functional programming as they allow programmers to define recursive data structures and operations on them uniformly by structural recursion. Likewise, in object-oriented (OO) programming, recursive hierarchies of object types with virtual methods play a central role for the same reason. There is a semantical correspondence between these two situations which we reveal and formalize categorically. To this end, we assume a coalgebraic model of OO programming with functional objects. In practical terms, the development prepares for refactorings that turn sufficiently disciplined functional folds into OO programs of a designated shape (and v.v.).

I haven't even glanced at the paper yet, but it looks extremely interesting, and it's directly related to some recent discussion. This blog post from Ondrej is also relevant.

VamOz: Visual Abstract Machine for Oz

VamOz: Visual Abstract Machine for Oz

VamOz is a visual abstract machine executing kernel language programs as defined in the book Concepts, Techniques and Models of Computer Programming by Peter Van Roy and Seif Haridi.

VamOz has been developed by Frej Drejhammar and Dragan Havelka with contributions from Christian Schulte. The idea is to give students a tool with which they can increase their understanding of how the abstract machine computes. VamOz has been used successfully in 2003 in the Datalogi II course taught by Christian Schulte at KTH.

Diagram showing all programming paradigms and their relationships

Here is a diagram showing all the main programming paradigms and their relationships. This is quite different from the usual diagram which just shows programming languages. This diagram condenses a lot of information in a compact way. If your favorite language is not mentioned here, make a convincing argument and I may add it. If you find any errors, please let me know. I will take all people's comments into account to improve the diagram. Note to Unix aficionados: the diagram was made using xfig running on Mac OS X.

Edit: here is the latest updated diagram.

No Ifs, Ands, or Buts

No Ifs, Ands, or Buts: Uncovering the Simplicity of Conditionals. Jonathan Edwards.

Schematic tables are a new representation for conditionals. Roughly a cross between decision tables and data flow graphs, they represent computation and decision-making orthogonally. They unify the full range of conditional constructs, from if statements through pattern matching to polymorphic predicate dispatch. Program logic is maintained in a declarative canonical form that enforces completeness and disjointness among choices. Schematic tables can be used either as a code specification/generation tool, or as a self-contained diagrammatic programming language. They give program logic the clarity of truth tables, and support high-level direct manipulation of that logic, avoiding much of the mental computation demanded by conventional conditionals.

Many of us are skeptical of "visual programming", but also intrigued by the impact that powerful development tools might have on language design. This represents an interesting compromise. It addresses a pervasive problem in a novel way, and this is a paper with many interesting and accessible ideas. I look forward to seeing an implementation.

Jonathan posted this on his blog, where there are already several comments.

[I'm not sure where to put this... Seems like plain-old "Paradigms" is the best fit...]

Future of software design?

It's been a while since I submitted a is some food for thought!

What will programming look like in 20 years? Maybe it will be based on a "definitive language" like the speculations of the article Convergence in language design: a case of lightning striking four times in the same place (FLOPS 2006). Such a language will have a layered structure and its handling of concurrency is important. (Whether it is dynamically or statically typed is of absolutely no importance, BTW.)

How will we program with such a language? Maybe we will program with feedback loops, as explained in Self management and the future of software design (FACS 06). This seems to be one way to handle complexity, the inevitability of software and hardware faults, and managing global behavior of a system. I am coordinating a new project, SELFMAN, that is looking at this.


Is "post OO" just over?

While studying the conference program of the upcoming OOPSLA 2006 I discovered under the category "essay" an author who has quite something critical to say about AOP:

Aspect-oriented programming is discussed as a promising new technology. Like object-oriented programming, it is beginning to pervade all areas of software engineering. With its growing popularity, practitioners and academics alike are beginning to wonder whether they should start looking into or it, or otherwise risk having missed an important development. The author of this essay finds that much of aspect-oriented programming's success seems to be based on the conception that it improves both modularity and the structure of code, while in fact, it actually works against the primary purposes of the two, namely independent development and understandability of programs. Not seeing any way of fixing this situation, he thinks the success of aspect-oriented programming to be paradoxical.

This is not just another internet rant about the latest PL hype but the author, Friedrich Steimann, had done interesting work about AOP before. In particular his latest paper about typed AOP:

AOP and the antinomy of the liar

but also his award winning former critical AOP review:

Domain models are aspect free

Pugs, Practicing the Theories.

A lot of language theory goes past here on Lambda the Ultimate, but we rarely see that theory directly impacting commercial programmers.

I'm a great fan of theoretical concepts like arrows, but at the same time I'm a self-employed programmer interested in solving my clients' problems.

Pugs is notable in that it profitably uses recent developments such as GADTs and Template Haskell for an implementation of Perl6.

I recently became a regular on the #perl6 irc channel and soon after joined the list of committers.

In just a few days I've seen a lot. I've seen enthusiastic members of the Perl community learning Haskell. I've seen myself learning Perl. I've also seen how daily Perl programmers work with abstractions like monad transformers. I've seen how some structures are easy to extend for programmers new to both the Pugs codebase and Haskell.

The Pugs project was started 64 days ago by Autrijus Tang, as an exercise while reading TaPL. Pugs already includes network and threading primitives. New tests and code are add at an amazing rate, as evidenced by the smoke tests.

I don't know if I'll end up using Perl after Pugs is written, but I am learning how to practice the theory of programming language design and implementation.

Interactive Programming

By way of Joe Marshall in comp.lang.lisp:

Here's an anecdote I heard once about Minsky.  He was showing a
student how to use ITS to write a program.  ITS was an unusual
operating system in that the `shell' was the DDT debugger.  You ran
programs by loading them into memory and jumping to the entry point.
But you can also just start writing assembly code directly into memory
from the DDT prompt.  Minsky started with the null program.
Obviously, it needs an entry point, so he defined a label for that.
He then told the debugger to jump to that label.  This immediately
raised an error of there being no code at the jump target.  So he
wrote a few lines of code and restarted the jump instruction.  This
time it succeeded and the first few instructions were executed.  When
the debugger again halted, he looked at the register contents and
wrote a few more lines.  Again proceeding from where he left off he
watched the program run the few more instructions.  He developed the
entire program by `debugging' the null program.
XML feed