Stream vs. Stack

In a recent discussion on PiLuD, a question was asked regarding implications of stream processing relative to the stack-machine concept used by many languages today. I replicate my answer here:

Stream processing has low memory locality (touches a lot of code per element), and uses a lot of memory (many buffers). OTOH, it composes well (pipelines, merges), parallelizes well and in an understandable manner (early parts of a pipeline can run in parallel with later parts, and multiple pipelines can easily run parallel side-by-side), and has highly predictable performance characteristics (CPU, latency, memory costs).

Consequently, stream processing is a very effective basis for:

  • high-performance, scalable, parallel or distributed computing
  • real-time computing
  • embedded systems where predictable memory is important

Stream processing is used heavily for these purposes, both in languages (such as Lucid and Lustre – synchronous reactive programming) and architectures (OpenGL shader pipelines; flow-based programming; etc.).

A benefit of stream processing is that it’s `natural` to associate state with locations in a stream. Even in a semantically stateless stream-processing system, developers can easily annotate stateful optimization: caching, memoization, diff processing and compression, filtering equal updates, stability, choking, and so on. By comparison, there is no `natural` way to associate state with a behavior on a stack. Stack activities are naturally ephemeral. Developers can work around the issue by adding a `heap` or static state to their model, albeit at cost of complicating their computation model.

There is considerable variation among stream processing systems regarding what elements of the stream `mean`, and how side-effects and state are supported. Elements in a stream might represent events or a time-varying value. Effects might be triggered on events, continuous, or shifted entirely to system edges. State might be internal, i.e. accumulate history while computing the stream, or externalized to a database or tuple space. There are many design concerns to weigh here, such as events and internal state allow a lot of expressiveness, but using only external state can support the language designer in ensuring useful properties like resilience against disruption or consistent view among observers. (Note: one can get the benefits of both external and internal state by using linear types to exclusively bind external state to an internal location.)

Consider: Functional Reactive Programming (FRP) and Reactive Demand Programming (RDP) are both stream processing models. FRP traditionally supports both events and behaviors, allows internal state (causal behaviors, event accumulators) but forces developers to propagate values to the edge of the system to integrate effects. RDP restricts developers to time-varying values, and forbids internal state, but does allow a continuous effects in the middle (including access to external state).

Anyhow, there are many stream processing models, just as there are many stack-based programming models.

IMO, stack-based programming survives on path dependence. It was a moderately effective design for a singular central processing unit and batch-processing applications. But it’s a rather poor fit for modern computation and service architectures – whether you’re considering GPGPUs, OpenCL, or something larger like web-services. And it’s a terrible fit for interactive or reactive applications, such as GUIs, games, and robot control software. While I mention complications for representing long-lived state, there are many other complications in the stack architecture – e.g. composing concurrent behaviors. Even if you do pursue stack-basis, you’d be better off at least modeling it as continuation passing rather than a true stack!

A stack is a fine example of a `simplistic` model that causes complications everywhere else! Stack-based programming hurts its users again, and again, and again. But it’s hard for humans to recognize such abuse until they’ve escaped it.

There comes a time when every language designer must make a choice between what is simple and what seems easy…

Advertisements
This entry was posted in Concurrency, Language Design and tagged , . Bookmark the permalink.

12 Responses to Stream vs. Stack

  1. Re “Even if you do pursue stack-basis, you’d be better off at least modeling it as continuation passing rather than a true stack!”

    I’ve come to love the combination of segmented stacks (as seen in efficient call/cc and delimited continuation implementations [1, 2]) and continuation marks [3]. They’re a natural fit: continuation marks allow us to attach key/value pairs (marks) to (delimited) computation contexts (preserving tail-call elimination). The marks are used to store stuff like exception handlers and prompts, and have a lot of other uses (e.g. implement a stepper for a debugger entirely in userland [3]). Their combination with delimited control is intuitive: only the marks in the delimited contexts are stored with a delimited fragment and reinstated on composition. (Very similar to Oleg and Chung-chieh’s delimited dynamic binding.) And as [2] shows, such segmented cactus stacks may be implemented similarly efficiently as ordinary stacks.

    [1] http://www.cs.indiana.edu/~dyb/pubs/stack-abstract.html
    [2] http://www.cs.indiana.edu/l/www/ftp/techreports/TR615.pdf
    [3] http://www.brinckerhoff.org/clements/papers/dissertation.pdf

    Oh, and of course these delimited stack fragments a natural fit for all kinds of scheduling.

    • dmbarbour says:

      First-class continuations and segmented stacks do help solve problems whose cause is using stacks in the first place, yes. They’re a natural fit for a fabricated hole.

      • That’s the kind of response I’ve come to expect from you! 😉

        But surely you’re not advocating ditching stack-based programming in favor of stream processing as the general purpose framework?

      • dmbarbour says:

        I do advocate ditching stacks as a primary basis for programming. If you need stacks, model them as state maintained in a stream. You won’t often need stacks. The performance benefits stacks offered for central processing systems are now compromised severely by concurrency, distribution, and the relative priority of latency and scalability over efficiency.

        If your language design is stack based, your language is already antiquated.

  2. “Stack activities are naturally ephemeral.”

    Does this still hold, in your opinion, with delimited continuations? Don’t they make it possible to abstract control flow suitably?

    • dmbarbour says:

      Delimited continuations do make it possible to `abstract control flow suitably`, and with less accidental complexity than would be required with full continuations or stacks. However, one should not confuse the properties of the host abstraction with the properties of the system being abstracted. Each activation of a delimited continuation is still `naturally` ephemeral.

  3. “If your language design is stack based, your language is already antiquated.”

    I can’t imagine writing a whole computing system in a stream-based style? Does it only apply at the “application layer”, or would you also recommend it for implementing things like hardware drivers, schedulers, databases, file systems, …?

    • dmbarbour says:

      Hardware drivers are naturally stream-based: sensors are stream sources, actuators are stream sinks. One is typically maintaining time-varying values, whether those values describe wrench efforts, speaker voltages, or pixel buffers.

      Schedulers are not a natural abstraction, but they do solve a natural problem: resource contention, distribution of computations in space or time. I would not model schedulers as they exist today. I would solve the problems that schedulers solve by use of a different abstraction: a concept of code distribution and program fusion.

      Databases, filesystems, and memory are naturally modeled as time-varying values, and of course streams are useful to model both the updates and the result of time-varying queries. Stream fusion models concurrent activities.

      I can easily imagine stream-based programming all-the-way-down.

  4. As with all your posts, very inspiring and though-provoking stuff – but aren’t you dramatizing the issue?

    Is your concern the immediate improvement of personal computing? Then there are easier avenues than abolishing the dominant stack-based control regime.

    Take a language like Common Lisp, with the most simple stack-based first-order control. This language has served, in the 80s and 90s, as an application framework for dozens of human-computer interaction prototypes and applications, that are still improvements over their successors. OVAL is just one interesting example. http://ccs.mit.edu/papers/CCSWP181/

    These applications, ideas like naked objects http://en.wikipedia.org/wiki/Naked_objects , pliant systems http://video.google.com/videoplay?docid=-7521521683937268935 , Oleg’s A Dream of an Ultimate OS http://okmij.org/ftp/DreamOS.html , the Be File System http://www.nobius.org/~dbg/practical-file-system-design.pdf , and protocols like 9P seem to hint at a general truth: it’s about the data. Once applications provide users interesting and relevant means to structure and access their extensible (of course) data, a lot of other application concerns fall out for free. (Social networking is really just a shared database.)

    9P has a handful of commands. With content-centric networking, it boils down to one command (interest). These systems have been developed by some of our finest minds for the purpose of connecting programs that use first-order control, and they have interesting applications in the field, and their properties are easily understood. (Yeah, I know what you’ll say. :-))

    I think my point is that I’d like you to focus on RDP as a data-oriented protocol, not a language. (Because protocols are easier to deploy on a broad basis than languages.)

    • dmbarbour says:

      Think hard thoughts, speak hard words, though I may contradict myself tomorrow – Ralph Waldo Emerson.

      I have a grand vision for improvement of personal computing. The line between HCI and programming should be fuzzy or non-existent. Programming is performed by billions of people worldwide – albeit, at varying levels of detail, and not always obviously. Using the computer for day-to-day tasks becomes a subtle education in programming, starting at age two or so. There must not be any `discontinuity spikes`: the intuitions people gain from the HCI and user interfaces must be valid for programming at all higher and lower scales. This requires simplicity and elegance without compromising practicality and performance. Programs are not limited to the local device, may connect arbitrary services and systems – even remote ones. Communication within an application is decentralized – i.e. composing two remote services means creating direct connections between those services. Applications are highly declarative and continuous, i.e. linking objects together, adding statements to a database, introducing rules or constraints. Limits of authority are reflected in the HCI exactly as they are in the language – a powerful principle for secure interaction design. It is not `about the data`. It’s about extending human agency, human reach, human intelligence. It’s about automating our preferences and policies and contracts. It’s about orchestration.

      Focusing on RDP as `just a protocol` would never allow me to achieve my vision – there would be a painful discontinuity between local stack-based programming and distributed communication, and no easy way for regular users to bridge it. The gap becomes a barrier to casual programming. Further, without programming language, I would be unable to distribute code in order to model truly distributed applications. At scales of a billion programmers, issues such as concurrency, consistency, scalability, security, revocation, tolerance to error, orthogonal persistence, live programming, runtime upgrade, simple and predictable failure modes, disruption tolerance, resilience, security, modularity, extensibility, and system-level optimizations become very important. A wide range of compositional properties also serves as an effective foundation upon which users can establish useful intuitions – i.e. the very properties that make a language scalable also make it intuitive and simple and suitable for subtle user education. This is an example of convergent language design.

      I consider RDP a general purpose programming model – not a language, not a protocol. I do plan to develop an RDP based programming language (awelon), and an RDP based protocol (avon). But, in addition to those, there will be RDP based frameworks – e.g. in Haskell and JavaScript. And RDP based state models, and UI models and linker and compiler models.

      • I think our POVs are duals, then. 🙂 You want to model data as essentially a constant computation, whereas I’d like to model computations as dynamcially synthesized data (as in 9P servers).

  5. I remember John McCarthy (or one of his students/colleagues) saying that the stack was originally used by him to keep track of procedure calls for debugging – there was some hardware that made debugging tricky, and so the idea was to represent everything as a stack to make debugging more reliable. I remember a later research paper by Arvind arguing against the use of stacks in general to record the state of a computation, and suggesting other techniques for determining where in a long-running computation something went wrong.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s