Lambda the Ultimate

Noop.nl has posted its Top 200 blogs for developers, and LtU did pretty well. ;-)

Let's say that you have a logic database (or a relational database, or a constraint store, etc.) and the user issues a query that returns no results. It would be nice to be able to explain to the user why the query failed, perhaps identifying some subset of clauses that are mutually unsatisfiable or suggesting modified constraints. It looks to me like most of the work in this area takes the same approach as this paper by Parke Godfrey, finding maximal subqueries that succeed and minimal ones that fail and proceeding from there. (Judging from the citations to Godfrey's paper, this has been a hot topic in recommendation systems lately; I am surprised that it hasn't, as far as I can tell, caught on more generally in the constraint or logic programming communities -- although there may be some related work using different names for the same concepts.)

The capacity to explain failures and guide the user to a successful query seems awfully useful. I'm wondering if anyone is aware of (1) any other approaches for suggesting modifications to failing queries, or (2) any general-purpose constraint solving toolkits or logic programming systems that offer this functionality.

in an attempt to make up for the bad "subjective aside" that happened in a parallel universe and which will now go unmentioned, i'm interested in learning more about deterministic concurrency after reading Peter Van Roy's educational chapter. speaking for my self, i enjoy having constraints which can help me avoid bad code; the linked paper uses model checking as well as deterministic concurrency.

We believe the way forward is to provide more constrained par-
allel programming models that avoid some of these challenges by
construction. While restrictions mean that certain kinds of algo-
rithms are ruled out (or at least very awkward to code), this seems
a reasonable price to pay for correct programs.

the subjective thing is that i feel like most industrial developers are not willing to take on some constraints in order to be more safe. i find that frustrating, and wonder if/when/what could contribute to changing the mind set from "i'll do anything i darned well please, thank you very much" to more one of "hey, i'm going to be a responsible driver"?

also, since the paper targets the Cell processor, i wonder if the fact that people complain about how hard the PS3 is to develop for could lead some industry folks to become more interested in systems like that of the paper; systems which (to my mind) have chocolate+peanutbutter: a development system that makes using big parallelism safer and easier.

lastly, the results aren't the be-all, end-all. even though the system is helping us be safer and in some tests do better, there is still plenty of work to figure out how to really take advantage of all the possible power. which gets into the good/bad points of relying on a sufficiently smart compiler, another subjective area. i hope that things like GC, as imperfect as it is in many situations, help us work our way towards 'sufficiently smart' systems that really do work well overall.

I couldn't find this video anywhere on LtU, although it is a little old, and I'm not up-to-date with what Adobe is working on as of late. In any case, this happens to be a favorite video of mine. It is a clear demonstration of how Computer Science can be put to efffective use with the right understanding. These guys really know what they're doing with this, and happen to be close to many of my thoughts, ideas, beleifs about software development. Consider it food for thought.

A Possible Future of Software Development

I was curious if there was any sort of consensus for what the most powerful semantics known so far that are still guaranteed to only allow one to write programs that terminate? Phrased another way, languages that are "as close as possible to being Turing complete without actually being Turing complete." Most powerful in this context meaning something like, "the language for which their exists a function mapping all possible programs written in it to equivalent programs in the domain of all-possible-programs-that-could-be-written-in-a-Turing-complete-language with the largest image compared to all other such functions for other languages".

One thought is obsessing my programming language design thinking at the moment...

Bjarne Stroustrup's maxim that you should only consider creating a class if you have a class invariant to protect.

Does there exist a language,
where the internal state of an object instance can be so fully encapsulated,
that there is no way for anything other than an method of that instance,
to modify that state,
so the instance's invariant was violated?

And if not, what would such a language look like?

C++ is clearly not such a language as pointers and casts and references to internal state abound.

I expect it to be a Linear Logic language, as two objects of different class sharing the some of same internal state could trivially violate this rule.

If SSA and CPS (and ANF?) are provably equivalent, why does SSA seem much more popular than CPS in current language compiler implementation?

Any info, history, background, pointers to other discussions, etc. greatly appreciated.

Also, what is the current "state of the art" for CPS conversion? I think my resources - "Compiling with Continuations" and a 90's edition of EOPL - are quite dated. Moreover, I'd *love* to study a good treatment of CPS conversion and optimization that handles assignment.

Many thanks.

Here's the paper submitted to the 2009 Symposium on Parallelism in Algorithms and Architectures:

Reducers and Other Cilk++ Hyperobjects

Roy, Peter van (2009). Programming Paradigms for Dummies: What Every Programmer Should Know. In G. Assayag and A. Gerzso (eds.) New Computational Paradigms for Computer Music, IRCAM/Delatour, France.

This chapter gives an introduction to all the main programming paradigms, their underlying concepts, and the relationships between them. We give a broad view to help programmers choose the right concepts they need to solve the problems at hand. We give a taxonomy of almost 30 useful programming paradigms and how they are related. Most of them differ only in one or a few concepts, but this can make a world of difference in programming. We explain briefly how programming paradigms influence language design, and we show two sweet spots: dual-paradigm languages and a definitive language. We introduce the main concepts of programming languages: records, closures, independence (concurrency), and named state. We explain the main principles of data abstraction and how it lets us organize large programs. Finally, we conclude by focusing on concurrency, which is widely considered the hardest concept to program with. We present four little-known but important paradigms that greatly simplify concurrent programming with respect to mainstream languages: declarative concurrency (both eager and lazy), functional reactive programming, discrete synchronous programming, and constraint programming. These paradigms have no race conditions and can be used in cases where no other paradigm works. We explain why for multi-core processors and we give several examples from computer music, which often uses these paradigms.

I have not found this paper in the LTU archives, but I though it is likely of interest to this community. Of course, the author is well know here (e.g., his book Concepts, Techniques, and Models of Computer Programming). I like the bird's eye view of this paper.

I was wondering what people would consider Perlis languages, i.e. languages worth knowing because they should change how you think about programming. Obviously there is a lot of overlap between languages so what I'm looking for is a minimal set of established languages (by that I mean 10 years or older) that still provides a reasonably complete overview of different approaches to programming. My first try at a list would look something like:

Ada, C, Haskell, Java, Lisp, Smalltalk, Perl