Paper Trail

Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

John McCarthy

In this foundational paper, McCarthy formalizes a system for defining and computing recursive functions on symbolic expressions and uses it to introduce the programming language LISP. He begins by defining a class of symbolic (S-) expressions and a corresponding set of basic functions and predicates, then shows how more complex functions can be built recursively using conditional expressions. The paper presents the notion of a universal function that can interpret symbolic expressions — conceptually similar to a universal Turing machine — and describes how these ideas were embodied in the LISP programming system developed for the IBM 704 to support symbolic manipulation and artificial intelligence research.

Promises: linguistic support for efficient asynchronous procedure calls in distributed systems

Barbara Liskov, Liuba Shrira

"Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems" introduces a new language construct called a promise to support efficient asynchronous remote procedure calls in distributed computing. The paper describes how promises act as placeholders for results that will be computed in the future, allowing a caller to initiate a remote call and continue executing without waiting for the reply. Promises decouple the invocation from the result, enabling parallelism and overlap of communication and computation.

A note on distributed computing

Jim Waldo, Geoff Wyant, Ann Wollrath, Sam Kendall

The authors argue that treating distributed objects the same as local objects — as if location and communication were mere implementation details — is fundamentally mistaken and leads to flawed system designs. They explain that distributed systems introduce intrinsic challenges not present in single address space computing, such as network latency, different memory access models, partial failures, and concurrency concerns, which cannot be abstracted away without sacrificing robustness and reliability.

A poor man's concurrency monad

Koen Claessen

Claessen shows how to add a simple form of concurrency to Haskell without extending the language with new primitives by defining a concurrency monad transformer. This construction allows developers to take any existing monad and lift its atomic actions into a concurrent context, providing operations like fork to initiate concurrent processes. The paper describes the design and implementation of the monad transformer, explains how concurrency can be modeled via interleaving and continuations.

Crash-Only Software

George Candea, Armando Fox

Candea and Fox propose a design philosophy for Internet systems in which programs are built so that the only way they stop is by crashing and the only way they start is by recovering. By eliminating separate "clean shutdown" and "exceptional failure recovery" paths, crash-only systems simplify software behavior, make failure handling more predictable, and enable fast, reliable recovery from inevitable faults.

A Concurrent Lambda Calculus with Futures

Joachim Niehren, Jan Schwinghammer, Gert Smolka

This paper introduces λ(fut), a concurrent extension of the lambda calculus designed to model the operational semantics of Alice ML, a concurrent, statically-typed extension of Standard ML that uses futures as its core synchronization mechanism. λ(fut) minimally extends the call-by-value lambda calculus with constructs for concurrent threads, futures, handles, and reference cells.

Revisiting coroutines

Ana Lúcia De Moura, Roberto Ierusalimschy

De Moura and Ierusalimschy argue for bringing coroutines back into prominence as a powerful and general control abstraction in programming languages. They propose a new classification of coroutine mechanisms, define what they call full asymmetric coroutines with precise operational semantics, and demonstrate that such coroutines have expressive power equivalent to one-shot continuations and one-shot delimited continuations.

Fault Tolerance via Idempotence

G. Ramalingam, Kapil Vaswani

Ramalingam and Vaswani explore how to build fault-tolerant distributed systems by leveraging idempotence, the property that repeated execution of an operation has the same effect as a single execution. They introduce a core language inspired by modern distributed platforms that models services, duplicate requests, process failures, and local atomic transactions, and then define a correctness criterion combining safety (idempotence) and progress (failure-freedom).