Key Moments
Advanced Topics in Programming Languages: Concurrency/message passing Newsqueak
Google TalksKey Moments
Newsqueak's message-passing concurrency model simplifies interactive application development by treating software as independent processes communicating via channels, a stark contrast to traditional lock-based approaches.
Key Insights
Concurrency, as modeled by Newsqueak, is distinct from parallelism and aims to make programmers more effective rather than solely focusing on making parallel computers faster.
Newsqueak utilizes channels for all communication, which are unbuffered, synchronous, and fully typed, serving as both communication and synchronization primitives.
The 'select' operator in Newsqueak allows a process to wait for and react to communication on multiple channels simultaneously, offering a non-deterministic choice when multiple are ready.
The 'become' keyword in Newsqueak provides a richer notion of execution than a simple return, allowing a computation to be replaced by another expression of the same type, potentially optimizing stack usage.
Newsqueak's approach to building interfaces, such as a windowing system, involves composing components via channels, leading to systems where complexity scales linearly with design additions.
The prime sieve and power series examples demonstrate Newsqueak's ability to express complex algorithms concisely, with the power series example implemented in just a few hundred lines of code.
Rethinking concurrency beyond parallelism
Rob Pike introduces Newsqueak, a concurrent programming language designed in the late 1980s to address the mismatch between our concurrent world and the sequential nature of traditional programming. He distinguishes concurrency from parallelism, arguing that the former is about making programmers more effective and programs cleaner, not just about exploiting multiple processors. The core idea is to view software as a collection of independently executing processes, each with its own program counter and stack, whose states can be aggregated. This contrasts with models that focus on threads, shared memory, locks, and semaphores, which Pike considers too low-level for many application programming tasks. The talk draws inspiration from Tony Hoare's 1978 paper on Communicating Sequential Processes (CSP), but emphasizes the crucial addition of channels for communication.
Processes and channels: The building blocks
Newsqueak models concurrency through independent processes. Communication between these processes occurs exclusively through channels, which are unbuffered, synchronous, and fully typed. A channel acts as a handle for communication, and its synchronous nature means that both sender and receiver must be ready for the data transfer to occur, thus providing implicit synchronization. Channels are first-class citizens, meaning they can be passed around, sent through other channels, and used to manage program flow. While Newsqueak's primitive is an unbuffered channel, buffered channels can be simulated. The language avoids explicit join operations; instead, communication via channels is used to signal completion or readiness. This model emphasizes passing data and signaling together, avoiding the need for separate synchronization primitives like locks. The language also features a 'select' operator, which allows a process to wait for communication on multiple channels and react to whichever becomes ready first, providing a non-deterministic choice.
Key language features: 'become' and 'probe'
Beyond its concurrency model, Newsqueak introduces specific language constructs. The 'become' keyword offers a richer alternative to a traditional 'return'. It allows a computation to be replaced by another expression of the same type, effectively substituting the current computation. This mechanism is particularly useful for optimizing recursive calls, as it can avoid growing the call stack, a critical feature for interactive applications involving mutual recursion between processes. Functions in Newsqueak are first-class values, referred to as 'probes' (short for lambda). These probes can be assigned, passed as arguments, and crucially, invoked as new processes using the 'begin' keyword, which starts the probe asynchronously without waiting for its completion. The result of a 'begin' invocation, if any, is discarded. This pattern of launching processes within lambdas is common in Newsqueak programming.
Illustrative programs: Prime sieve and power series
The talk showcases Newsqueak's expressive power through two main examples. The first is a prime sieve, where a stream of integers is processed by a pipeline of filter processes, each responsible for removing multiples of a specific prime. This elegantly demonstrates channel threading, where the output of one filter becomes the input of the next, creating a 'string of pearls' effect. The second, more complex example involves manipulating power series, inspired by Doug McIlroy's work. Here, power series are represented as channels of rational numbers (coefficients). Operations like summation, differentiation, and integration are implemented by composing channel-based processes. This example highlights how Newsqueak's model can lead to extremely concise code, with the power series arithmetic implementation being only a few hundred lines, managing complex mathematical operations with surprising simplicity.
Building interfaces and systems from channels
A key application of Newsqueak's model is in constructing interfaces and systems. An interface is defined as a set of channels that encapsulate the communication protocol for a component. This approach is contrasted with object-oriented interfaces, as Newsqueak interfaces are fundamentally collections of communication channels. The composition of these interfaces leads to systems where complexity scales linearly with design additions, a significant advantage over state-machine-based approaches. The talk uses a windowing system as a prime example: the system's environment (mouse, keyboard, graphics) is represented as channels. The window system itself can act as a client of itself, allowing for elegant self-referential designs and transparent interposition of services (like flipping mouse buttons for left-handed users). This framework facilitates building complex, concurrent systems with manageable complexity, where interleaving of execution falls out naturally.
The system model: Composing interfaces, not state machines
The overarching system model proposed by Newsqueak involves defining components as interfaces that capture their communication requirements via channels. This allows for diverse implementations of an interface as long as they adhere to the channel-based protocol. The power of this model lies in the composition of these interfaces, leading to systems where complexity is linear with design and expressiveness is super-linear. This is presented as a counterpoint to state machines, which often exhibit exponentially increasing complexity for composition with less expressive results. The model also naturally handles the interleaving of execution, essential for systems involving concurrency and potential parallelism, without the low-level concerns of locks and shared memory. This approach simplifies reasoning about system behavior, especially in contexts like networking or distributed systems, where channel-based interfaces can be more readily adapted than shared memory paradigms.
Debugging concurrency and future directions
Pike addresses the common concern of debugging concurrent programs, stating that deadlocks are simply bugs that can be debugged by examining process stack traces, similar to any other bug. He highlights that tools exist for preemptively discovering deadlocks by analyzing program models. Furthermore, he hypothesizes about creating 'shim' interfaces that could monitor and isolate problematic clients to prevent deadlocks from affecting the entire system. While Newsqueak itself is an interpreted language and not optimized for raw parallelism, Pike suggests that the concepts—especially the channel-based communication and interface composition—are powerful. He expresses a personal desire to resurrect Newsqueak to build systems like web servers, believing the model offers significant advantages in managing complexity and reasoning about concurrent interactions, even if the underlying execution is not strictly parallel.
Mentioned in This Episode
●Software & Apps
●Organizations
●Concepts
●People Referenced
Newsqueak Concurrency Model
Practical takeaways from this episode
Do This
Avoid This
Common Questions
Newsqueak is a programming language developed by Rob Pike at Bell Labs around 1988. It was primarily created to facilitate the writing of a window system, offering a higher-level approach to concurrency and message passing than existing low-level mechanisms.
Topics
Mentioned in this video
An operating system developed at Bell Labs, for which Rob Pike was a contributor. Its design principles influenced later systems.
A toy language from 1985 that used concurrency to express graphical interfaces concisely, inspiring Newsqueak.
A language with syntax similar to Newsqueak, but lacking its concurrency features.
A programming language co-created by Phil Winterbottom, Shaun Dora, and Rob Pike, similar to Newsqueak but JIT-compiled and still sold.
A programming language developed by Rob Pike at Bell Labs, focusing on concurrency and message passing, designed for writing a window system.
Operating system for which early bitmap systems were developed.
Developed a compiled version of Newsqueak used as a systems language at Bell Labs, and later co-created the Limbo language.
Host introducing Rob Pike and the talk.
Author of the 1978 paper on Communicating Sequential Processes (CSP), which laid the groundwork for concurrent programming concepts.
Speaker discussing his work on the Newsqueak programming language, including its concurrency and message-passing mechanisms. He is credited with contributions like UTF-8 and Plan 9.
Showed Rob Pike the prime sieve program that uses channels.
Colleague at Bell Labs who realized power series could be manipulated using the Newsqueak system, leading to an influential paper.
A control-flow construct mentioned as being similar to Newsqueak's 'select' statement, but with communication as the primitive.
Character encoding standard developed by Rob Pike and others.
A theoretical model for concurrent programming introduced by Tony Hoare, influencing subsequent work in the field, including channels.
A type of power series, used as an example to demonstrate channel-based manipulation of mathematical sequences.
More from GoogleTalksArchive
View all 88 summaries
58 minEverything is Miscellaneous
54 minStatistical Aspects of Data Mining (Stats 202) Day 7
45 minKey Phrase Indexing With Controlled Vocabularies
63 minMysteries of the Human Genome
Ask anything from this episode.
Save it, chat with it, and connect it to Claude or ChatGPT. Get cited answers from the actual content — and build your own knowledge base of every podcast and video you care about.
Get Started Free