MultiLisp is a functional

Functional programming

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...

 programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

 and dialect of the Lisp

Lisp programming language

Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...

 dialect Scheme, extended with constructs for parallel execution and shared memory; MultiLisp is implemented in Interlisp

Interlisp

Interlisp was a programming environment built around a version of the Lisp programming language. Interlisp development began in 1967 at Bolt, Beranek and Newman in Cambridge, Massachusetts as BBN LISP, which ran on PDP-10 machines running the TENEX operating system...

. These extensions involve side effects, rendering MultiLisp non-deterministic. In addition to its parallel-programming extensions, MultiLisp also had some unusual garbage collection

Garbage collection (computer science)

In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...

 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

Massachusetts Institute of Technology

The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...

. It has influenced the development of the Scheme dialect Gambit

Gambit (Scheme implementation)

Gambit, also called Gambit-C, is a free software Scheme implementation, consisting of a Scheme interpreter, and a compiler which compiles Scheme to C. Its documentation claims conformance to the R4RS, R5RS, and IEEE standards, as well as several SRFIs...

 http://www.iro.umontreal.ca/~gambit/, and Interlisp-VAX

Interlisp

Interlisp was a programming environment built around a version of the Lisp programming language. Interlisp development began in 1967 at Bolt, Beranek and Newman in Cambridge, Massachusetts as BBN LISP, which ran on PDP-10 machines running the TENEX operating system...

.

PCALL and FUTURE

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

Future (programming)

In computer science, future, promise, and delay refer to constructs used for synchronization in some concurrent programming languages. They describe an object that acts as a proxy for a result that is initially not known, usually because the computation of its value has not yet completed.The term...

, which resembles forking

Fork (operating system)

In computing, when a process forks, it creates a copy of itself. More generally, a fork in a multithreading environment means that a thread of execution is duplicated, creating a child thread from the parent thread....

, combined with Lazy evaluation

Lazy evaluation

In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...

. Using this construct, an expression such as

(cons

Cons

In computer programming, cons is a fundamental function in most dialects of the Lisp programming language. cons constructs memory objects which hold two values or pointers to values. These objects are referred to as cells, conses, non-atomic s-expressions , or pairs...

 (FUTURE A) (FUTURE B))

can be written, which will overlap the evaluation of the expressions A and B, not only with each other, but with computations that use the result of the cons

Cons

In computer programming, cons is a fundamental function in most dialects of the Lisp programming language. cons constructs memory objects which hold two values or pointers to values. These objects are referred to as cells, conses, non-atomic s-expressions , or pairs...

call, until an operation is performed that requires actual information about the value of A or B.