Parallel/Distributed

Termite: a Lisp for Distributed Computing

(via Patrick)

In short: take Scheme, remove mutations, add isolated processes with mailboxes, add message sending and receiving operations and an addressing mechanism.

Termite is a Lisp for distributed computing (PDF paper and PDF presentation), providing an Erlang like model on top of Scheme.

As the presentation says, the powerful abstraction facilities provided by Scheme made impelementing Termite rather easy and the implementation doesn't require much code.

[Edit: here's a working link for the PDF paper]

A Theory of Distributed Objects

A Theory of Distributed Objects - Asynchrony - Mobility - Groups -Components. Denis Caromel and Ludovic Henrio.

Distributed and communicating objects are becoming ubiquitous. In Grid and Peer-to-Peer environments, extensive use is made of objects. This book provides a general theory for distributed objects interacting asynchronously, for the sake of efficiency and scalability. Further, it copes with advanced issues such as mobility, groups, and components.

Pi-Calculus, Join-Calculus and more...

Check out the sample chapter to get a feeling of the writing style.

Revisiting coroutines

Revisiting coroutines

This paper defends the revival of coroutines as a general control abstraction. After proposing a new classification of coroutines, we introduce the concept of full asymmetric coroutines and provide a precise definition for it through an operational semantics. We then demonstrate that full coroutines have an expressive power equivalent to one-shot continuations and one-shot partial continuations. We also show that full asymmetric coroutines and one-shot partial continuations have many similarities, and therefore present comparable benefits. Nevertheless, coroutines are easier implemented and understood, specially in the realm of procedural languages. Finally, we provide a collection of programming examples that illustrate the use of full asymmetric coroutines to support direct and concise implementation of several useful control behaviors, including cooperative multitasking.

Taking into account real or imaginary interest to control operators on LtU, I believe this paper makes nice reading. See also Coroutines in Lua.

Crystal Scheme: A Language for Massively Parallel Machines

Crystal Scheme: A Language for Massively Parallel Machines
Massively parallel computers are built out of thousands conventional but powerful processors with independent memories. Very simple topologies mainly based on physical neighbourhood link these processors. The paper discusses extensions to the Scheme language in order to master such machines. Allowing arguments of functions to be concurrently evaluated introduces parallelism. Migration across the different processors is achieved through a remote evaluation mechanism. First-class continuations offering some semantical problems with respect to concurrency, we propose a neat semantics for them and then show how to build, in the language itself, advanced concurrent constructs such as futures. Eventually we comment some simulations, with various topologies and migration policies, which enables to appreciate our previous linguistical choices and confirms the viability of the model.
Note the year of publication -1991. The bibliography goes back to 1980. My question might be naive, but what are major inventions in the area of hardware parallelism since then? What ideas comprising, e.g., Cell architecture were not known at 1991? Is Cell just an engineering achievement (assuming it is an achievement) or a scientific as well?

And, returning to PLT, can Crystal Scheme be useful for Cell?

Tim Bray: On Threads

A report on Sun's "Chip Multi-Threading" summit.

Not much that is new here, but the trend towards concurrency is one we discussed a few times, and which seemed to attract interest.

Bray's comments regarding erlang and other languages are sure to annoy LtU readers. Let's not start a flamefest. Let me just remark that even if you want shared data structures, Java isn't your only option. You should at least check out Ada... (and you can compile Ada to the JVM, if that's what you want to do. let's not confuse language and implementation).

Bidirectional fold and scan

Bidirectional fold and scan, O'Donnell ,J.T. In Functional Programming, Glasgow 1993, Springer Workshops in Computing.

Bidirectional fold generalises foldl and foldr to allow simultaneous communication in both directions across a list. Bidirectional scan calculates the list of partial results of a bidirectional fold, just as scanl and scanr calculate the partial results of a foldl or foldr. Mapping scans combine a map with a scan, and often simplify programs using scans. This family of functions is significant because it expresses important patterns of computation that arise repeatedly in circuit design and data parallel programming.

The biderctional fold is a bit surprising at first, but the real reason I am posting this is to encourage discussion on the connection between functional and data prallel programming.

Lisp or Erlang

Some here will find this discussion on language choice for building an industrial strength poker server to be of interest.

Parallel Programming with Matrix Distributed Processing

Matrix Distributed Processing (MDP) is a C++ library for fast development of efficient parallel algorithms. MDP enables programmers to focus on algorithms, while parallelization is dealt with automatically and transparently. Here we present a brief overview of MDP and examples of applications in Computer Science (Cellular Automata), Engineering (PDE Solver) and Physics (Ising Model).

A short tutorial on MDP.

MDP provides a distributed programming model. On top of that, it is interesting to see that the library adds what looks like a language constructs (e.g., forallsites).

Design Philosophy of Distributed Programming in Mozart

From the abstract of Per Brand's Ph.D. thesis,
The Design Philosophy of Distributed Programming Systems: the Mozart Experience, which has just appeared (dated June 2005):

Distributed programming is usually considered both difficult and inherently different from concurrent centralized programming. It is thought that the distributed programming systems that we ultimately deploy, in the future, when we've worked out all the details, will require a very different programming model and will even need to be evaluated by new criteria.



The Mozart Programming System, described in this thesis, demonstrates that this need not be the case. It is shown that, with a good system design, distributed programming can be seen as an extended form of concurrent programming. This is from the programmer's point-of-view; under the hood the design and implementation will necessarily be more complex. We relate the Mozart system with the classical transparencies of distributed systems. We show that some of these are inherently on the application level, while as Mozart demonstrates, others can and should be dealt with on the language/system level.

[...]

The full range of the design and implementation issues behind Mozart are presented. This includes a description of the consistency protocols that make transparency possible for the full language, including distributed objects and distributed data-flow variables.

A type discipline for authorization policies

A type discipline for authorization policies. Cedric Fournet; Andrew D. Gordon; Sergio Maffeis

Distributed systems and applications are often expected to enforce high-level authorization policies. To this end, the code for these systems relies on lower-level security mechanisms such as, for instance, digital signatures, local ACLs, and encrypted communications. In principle, authorization specifications can be separated from code and carefully audited. Logic programs, in particular, can express policies in a simple, abstract manner. For a given authorization policy, we consider the problem of checking whether a cryptographic implementation complies with the policy. We formalize authorization policies by embedding logical predicates and queries within a spi-calculus. This embedding is new, simple, and general; it allows us to treat logic programs as specifications of code using secure channels, cryptography, or a combination. Moreover, we propose a new dependent type system for verifying such implementations against their policies. Using Datalog as an authorization logic, we show how to type several examples using policies and present a general schema for compiling policies.

I guess it's dependent types day around here...

XML feed