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