MultiLisp

From Wikipedia, the free encyclopedia

MultiLisp is a functional programming language and dialect of the Lisp dialect Scheme, extended with constructs for parallel execution and shared memory; MultiLisp is implemented in Interlisp. These extensions involve side effects, rendering MultiLisp non-deterministic. In addition to its parallel-programming extensions, MultiLisp also had some unusual garbage collection and task scheduling algorithms. Like Scheme, MultiLisp is oriented toward symbolic computation. Unlike some parallel programming languages, MultiLisp incorporates constructs for causing side effects and for explicitly introducing parallelism. It was designed by Robert H. Halstead in the early 1980s for use on the 32-processor Concert multiprocessor being developed at MIT. It has influenced the development of the Scheme dialect Gambit [1], and Interlisp-VAX

[edit] PCALL

MultiLisp achieves parallelism with the PCALL macro, where

(PCALL Fun A B C ...)

is equivalent to

(Fun A B C ...)

except that the arguments A, B, C, etc are explicitly allowed to be evaluated in parallel; this circumvents the usual order of evaluation, which is sequential and left to right. It also makes use of a parallel programming construct called futures, (which resembles forking, combined with Lazy evaluation) to allow PCALLs to be made for basic operations such as:

(PCALL cons (A) (B))

[edit] See also

Speculative evaluation

[edit] References

R. H. Halstead, "MultiLisp: A Language for Concurrent Symbolic Computation", TOPLAS, October 1985
Koomen, J.A.G.M., "The Interlisp Virtual Machine: A Study of its Design and its Implementation as Multilisp", Master's thesis, University of British Columbia, 1980
Raymond L. Bates, David Dyer, Johannes A. G. M. Koomen "Implementation of Interlisp on the VAX" pp81-87 in ACM Proceedings of the 1982 ACM Conference on LISP and Functional Programming, Pittsburgh, Pennsylvania, United States
Halstead, R.H.jr. The MULTILISP Language: LISP for a Multiprocessor. Conf. on 5th Generation Computers, Tokyo, 1984
Halstead, Robert H. Jr., "MULTILISP: a language for concurrent symbolic computation" in TOPLAS 7(4) October 1985
W.S. Martins "Parallel Implementations of Functional Languages" In Proceedings of the 4th Int. Workshop on the Parallel Implementation of Functional Languages, 92
Skillicorn, David B. and Talia, Domenico "Models and languages for parallel computation" pp123-169 in ACM ACM Computing Surveys (CSUR) 30(2) June 1998