Lambda the Ultimate

I've just finished my master's thesis on the parallel shift. It covers why threading, in most cases, isn't a suitable programming model for extracting parallel performance, how we still can extract performance out it and what desired parallel programming models need to consider.

I expect a lot of people in this forum are more knowledgeable in computer languages than I am. Therefore, I would very much like some comments on what I've written, especially the first part. Or better yet - a discussion :)

You can find the thesis at www.johantorp.com

Best Regards, Johan Torp

ABSTRACT
Part 1 - A bird's eye view of desktop parallelism,
Part 2 - Zooming in on C++0x's memory model

The first part of the thesis is an overview of the paradigmatic shift to parallelism that is currently taking place. It explains why processors need to become parallel, how they might function and which types of parallelism there are. Given that information, it explains why threads and locks is not a suitable programming model and how threading is being improved and used to extract parallel performance. It also covers the problems that await new parallel programming models and how they might work. The final chapter surveys the landscape of existing parallel software and hardware projects and relates them to the overview. The overview is intended for programmers and architects of desktop and embedded systems.

The second part explains how to use C++'s upcoming memory model and atomic API. It also relates the memory model to classical definitions of distributed computing in an attempt to bridge the gap in terminology between the research literature and C++. An implementation of hazard pointers and a lock-free stack and queue are given as example C++0x code. This part is aimed at expert C++ developers and the research community.

The machine learning community has started to realize the importance of expressive languages for specifying probabilistic models and also executing those models (i.e., performing "inference" by computing conditional distributions). A number of "probabilistic programming languages" have been proposed by machine learning/AI researches recently--Pfeffer's IBAL, and Goodman, Mansinghka, my, and Tenenbaum's CHURCH, and Winn's CSOFT.

Outside of the ML community, I know of a few languages, including Park, Pfenning, and Thrun's PTP, and Erwig and Kollmansberger's PFP/Haskell. In general, the work by ML researchers places more emphasis on the conditional execution of probabilistic programs (e.g., asking about the value of some variable given that the entire program takes on a particular value).

Of possible interest to the PL community are a number of interesting relationships between ideas in probability theory and programming languages (when used to specify so-called generative models). One of these is that purity/referential-transparency relaxes in the probabilistic setting to exchangeability (a property of a probability distribution being invariant to reordering). Other interesting theoretical connections relate to relaxed notions of halting (e.g., halting with probability one) and their effects on statistical inference (this is particularly relevant for so-called nonparametric distributions; e.g., see a recent workshop abstract of mine).

Along with my colleagues (Vikash Mansinghka (MIT), John Winn (MSR Cambridge), David McAllester (TTI-Chicago) and Joshua Tenenbaum (MIT)), we are organizing a workshop at the NIPS*2008 conference. While I've been reading LtU for some time, I've joined now to announce this workshop to the PL community because we definitely need the PL communities help in solving some open problems.

Probabilistic inference algorithms are very complicated beasts and writing universal inference algorithms that take as specifications "probabilistic programs" seems, at first blush, to implicate program analysis, compilation, partial evaluation and a host of other ideas from programming languages.

If these questions pique your interest, visit the workshop website:

http://probabilistic-programming.org

and also drop me an email (droy at mit edu). I hope to see some of you in Whistler this December.

On a method of expressing by signs the action of machinery, Charles Babbage, Philosophical Transactions of the Royal Society of London, 1826.

In the construction of an engine, on which I have now been for some time occupied, for the purpose of calculating tables and impressing the results on plates of copper, I experienced great delay and inconvenience from the difficulty of ascertaining from the drawings the state of motion or rest of any individual part at any given instant of time: and if it became necessary to enquire into the state of several parts at the same moment the labour was much encreased.

In the description of machinery by means of drawings, it is only possible to represent an engine in one particular state of its action. … The difficulty of retaining in the mind all the cotemporaneous and successive movements of a complicated machine, and the still greater difficulty of properly timing movements which had already been provided for, induced me to seek for some method by which I might at a glance of the eye select any particular part, and find at any given time its state of motion or rest, its relation to the motions of any other part of the machine, and if necessary trace back the sources of its movement through all its successive stages to the original moving power. I soon felt that the forms of ordinary language were far too diffuse to admit of any expectation of removing the difficulty…. It then became necessary to contrive a notation which ought if possible to be at once simple and expressive, easily understood at the commencement, and capable of being readily retained in the memory from the proper adaptation of the signs to the circumstances they were intended to represent.

I thought this was an interesting effort:

http://wiki.reia-lang.org/wiki/Reia_Programming_Language

Reia (pronounced RAY-uh) is a Python/Ruby-like scripting language for the Erlang virtual machine (BEAM). Reia aims to expose all the features and functionality of Erlang in a language more familiar to programmers of scripting languages, while improving string handling, regular expressions, linking with external libraries, and other tasks which are generally considered outside the scope of Erlang. Reia is distributed under the MIT License.

If it were just the syntax, that would be sort of interesting, but maybe nothing too special. However, they're also attempting to create an object system on top of Erlang, which if I'm not mistaken uses an Erlang process per object.

In Common Lisp, Dylan, and Python, all languages that provide multiple inheritance, there is a notion of inheritance order, specified by the order in which the direct superclasses of a class are given. All three languages determine the order in which methods are examined for relevance at method-call time by flattening the direct superclass orders into an order of all the superclasses. If no such flat order is possible, the class is rejected at compile time. (The flattening is done by different rules in each language, but that's not my present concern.)

In particular, suppose a class A and a class B which wlg inherit only from the topmost class. Then we may have a class AB which inherits first from A and then from B if A does not have a suitable method, and a class BA which inherits first from B and then from A. However, a class C that inherits from both AB and BA is not allowed, as its order would be locally inconsistent: we do not know whether to flatten it as C, AB, BA, A, B or as C, AB, BA, B, A.

My question is this: does having such classes as AB and BA ever actually make sense? Are there Real World examples where it is necessary in the same program to have two distinct classes that inherit from the same set of superclasses but in a different order?

I ask this question because I am implementing a language with MI, and it seems to me that there is a considerable advantage to my implementation if I can rule out such combinations of classes tout court, and simply require a globally unique order: if AB exists, then BA cannot, and vice versa. I have asked people from the Python and CL communities, and they tell me that such contrasts are normally considered poor style: that the only thing a method should count on is that methods from its subclasses are tried before it, and methods from its superclasses are tried after it. However, I would not want a win for me to become a loss for my users, so if anyone can point to realistic counterexamples, I suppose I will have to bite the bullet.

They are essentially translating haskell to CUDA code. The added semantics on the Haskell side is what is most interesting. Does anyone know of similar projects to add higher-level constructs to a language that gets compiled to CUDA. It's not clear to me from this presentation what the Lava semantics have to do with it.

Obsidian

Hello everyone,

I have been working on a language design which will requires builtin security checks of some sort ala what Java has or something like E. I have been looking recently at ML mixin modules which seem to be very closely related to classes. The question I have is are there known methods for handling security for systems like this where you cannot trust all the packages or load files in the system? To have a security system which is similar to an object based one I assume one would have to have any such security predicated not only on the modules(classes) but also the data. Is this sort of thing possible and is there any research in this area?

Thanks in advance,

Carter.

Assume a Haskell-like language. Say you have a value of an unknown (abstract) type, but you know it is either an integer, a string, or a tree node.

Are there (/have there been) extensions to Haskell that you can safely inspect and specialize the type of that given value?

Before I get going, as this is my first post here, I would just like to say hello and thank you all for your contributions to an always-interesting forum. :o) I will also point out that my background is in Mathematics, not computer science.

Graphs are extremely useful structures, and they are pretty much everywhere you look in computing whether explicitly or implicitly. Yet I have never met a mainstream language which included graph processing as an in-built facility. I am wondering - why not?

A quick Google search turned up a few research languages which make heavy use of graph rewriting rules (GP, Spider), and some interesting systems like NESL and SARTEX. The last of these sounds the most like what I am thinking of - a mainstream language (for the time) with built-in support for graphs. But the paper is from 1985, so it appears that the idea did not catch on. Was there a good reason for this?

For those interested, the review of the Phoenix library starts today. From the library description:

Phoenix enables Functional Programming (FP) in C++. The design and implementation of Phoenix is highly influenced by FC++ by Yannis Smaragdakis and Brian McNamara and the BLL (Boost Lambda Library) by Jaakko Jaarvi and Gary Powell. Phoenix is a blend of FC++ and BLL using the implementation techniques used in the Spirit inline parser.

Phoenix is meant to be an advanced replacement for boost.lambda.

If you are interested on the topic, want to comment on the design or simply want to support its inclusion into boost, write a review or at least make your voice be heard on the boost mailing list.

Here is a link to the documentation.