Static Resource Programming Language

I am interested in static allocation. Beyond benefits for resource control, hardware description, or embedded systems, static allocation is convenient from a UX perspective. In contrast to a stack or heap, variables from a static allocation have a static existence, amenable to stable layout on a screen or virtual environment. Direct manipulation is also feasible insofar as it fits within the language’s effects-model.

I am also interested in static processing guarantees. Beyond benefits for real-time systems, static processing is convenient from a UX perspective. Compared to loops that wait indefinitely for input, or process indefinite input streams, a guaranteed termination provides a clean semantic opportunity for user interaction: administrative interrupts, user events, direct manipulation of state, or live coding of process behavior.

Why?

I envision a future where the boundary between program and user-interface is blurry, a matter of projectional editing and live coding: A projected view may hide some elements of a program, highlight others. We can render state graphically where appropriate, and support state manipulation through projections. Modifications to the program should have immediate, observable impact. The underlying motive is that users should have effective control over their software environments, including easy inspection, decomposition, modification, and sharing thereof.

If you’ve followed my blog, you might be aware that I’ve been pursuing term rewriting because it’s also a very good fit for my vision. However, I’ve been feeling frustrated with the *performance* side of rewriting. It isn’t difficult to implement a naive interpreter, but obtaining great performance from is too difficult. Also, I have some interest in developing a computational wiki where pages and graphs can easily be computed and kept up-to-date from tables or logs. But with user-defined computations on a server, resource consumption becomes a significant concern. Enabling quotas for computations is certainly feasible, but I consider use of quotas to be very awkward and arbitrary.

Thus, I’ve been contemplating alternatives. A functional language that defaults to static resource consumption (in space and time) seems a very promising alternative. We may still have an opportunity to model allocation as an effect.

Regarding prior work, I’m only aware of Statically Allocated Functional Language (SAFL) by Alan Mycroft and Richard Sharp. TLDR: To achieve static allocation, SAFL restricts use of recursion and function dependencies. Mutually tail-call recursive function groups are permitted. The paper briefly sketches support for function parameters.

It is worth noting that static allocation implicitly admits static garbage collection. We can decide statically which regions of memory to reuse. In practice, this may result in a stack-like implementation, where the same stack space is reused for diverse computations. However, the exact allocation decision will also be based on parallelism, stream fusion, and other features. Beyond the requirement for static allocation, SAFL makes a guarantee that memory is directly proportional to program size, but I don’t need or care about that restriction.

Aside: I’m aware of many hardware description languages, which also have characteristics very similar to what I want. However, HDLs tend to embed state within a process, which is problematic for my vision, such as support for live coding or easy caching and memoization. I intend to cleanly separate state from behavior.

Glas Language

I propose a new language, which I’ll name Glas unless later inspired by a better name. In addition to static allocation, Glas will guarantee a static maximum compute effort and static linking. Some Glas programs might work around these limitations using effects, but use of dynamic structure is under programmer control.

To achieve static compute efforts, Glas will not support while loops, nor tail recursive loops where termination behavior is difficult to analyze. To make up for this weakness, I believe that Glas will require excellent standard support for collections processing and data-oriented programming, where loops are generally applied to arrays or matrices or streams of statically bounded size.

By ‘static linking’ I mean that the location for parameters to functions, such as the address of an argument, return value, or function, will be known statically.

I’m still exploring how this restriction will affect Glas. For example, we cannot have an array of existentially typed runtime values, because we wouldn’t statically know which function we’re invoking. But we could return an arbitrary function value from a ‘static’ computation. There is a potential explosion of implementations, where each function is duplicated and specialized with constant-propagation per call site. But a compiler could optimize for space, and use dynamic function and data pointers where appropriate.

Remaining Design Work

I still need to develop a type system. I assume it should include well proven conveniences such as GADTs and type abstractions. It might focus on bit-level representations.

For the effects model, to avoid interference with parallelism, I’m inclined to favor a linearity-based approach: effectful functions operating on abstract linear values, and references to those abstract linear values, may be provided as an argument to ‘main’. It supports object capability security, but because of the static linking constraint it’s no more expressive than algebraic effects. But we’ll need support for both linear types and a good environment model to either bundle parameters or make them implicit.

A viable process model is to simply repeat the effectful ‘main’ function in an indefinite loop. We can design an asynchronous effects API to limit internal waits within the loop. This would be similar to many game loops. With some care, it’s feasible to simulate cooperative multi-threading and channels if desired. A distrusted application could easily be wrapped to restrict or intercept access to some capabilities.

Glas should not be a technically difficult language. It will be a smaller language than most because there is no need for a heap or stack or functions as data. And static linking greatly simplifies analysis. However, the programmer will need good defaults and libraries and perhaps a decent effects API to avoid being stifled by those restrictions on expressiveness. So, Glas mostly becomes a UX and utility challenge.

This entry was posted in Language Design. Bookmark the permalink.

5 Responses to Static Resource Programming Language

  1. Asger Palm says:

    I have been thinking along similar lines, and we are working on a slightly different approach, but with very much the same goal.
    Our setup defines a set of language dialects in the form of abstract data types. These are basically ASTs for various languages. That can include GUI languages, i.e. think HTML, but also other kinds, such as LaTeX, SVG, or whatever can be represented as an AST.
    On top of this set of dialects, we allow them to extend each other. We can add a Circle element to HTML to form HTML’. To render that, we define a lowering function, which will convert the Circle element from HTML’ down to HTML (maybe using SVG). There is a mechanism to do that recursively, so any recursive element of HTML will now have a version that allows HTML’, thus allowing us to extend languages “locally” and still keep expressive power.
    This lowering is written in a simple functional language similar to what you outline, and what SAFL talks abouit. I.e. no first-order functions, no closures, no globals, no references, no mutation, only tail recursion allowed. The goal is to have stack allocation discipline.

    So to summarize, at this point we have a family of functions which convert from AST to AST. I.e. lowerings. These are written so that they will convert one given value in a dialect down to whatever dialect is required for rendering.
    Together, they define a graph of conversions between all these language dialects, so we can automatically stitch a given pipeline of conversion together.
    At this point, we thus have a way to render a given value of a given dialect using some other dialect as the backend. There is no mutation, it just works as a converter function for static languages.

    The next step is to lift this to a mutable world.

    The way we do that is to “lift” each lowering function to work not with static values, but with Functional Reactive values, i.e. behaviours.

    So basically, we have a compiler which will convert the restricted functional language up into the same program in a FRP formulation. The restrictions help us manage lifetime, without having to resort to any GC discipline, but can rely on “stack” allocation to handle lifetime even when there is mutation.

    So automatically, we achieve a situation where we can allow dynamic editing of values in a high-level dialect, and automatically the engine will figure out what parts of the AST to recompute using FRP principles.

    To help ensure performance is adequate, we have arrays in the language. Common operations, such as map & fold are then specialized, and can exploit common array operations, such as inserts/deletes/updates without having to “relower” the entire array of values.

    So in comparison with your proposal, we avoid effects completely in the language, since we add that by a systematic “lifting” to a FRP formulation of the static program.

    The benefit is that the static program can be implemented and tested using a normal functional compiler, and once you need the dynamic version, you compile the lifted version, and are good to go.

    • dmbarbour says:

      This seems interesting, and I do see some similarities to what I’m proposing. Since you’re approved now, feel free to provide a link.

      I’m still contemplating how to approach ‘effects’ in Glas. I’m not entirely happy with the approach described in the article above. Another viable approach involves ‘typed’ interactions, perhaps based on session types. Effect models are essentially interaction models.

  2. Asger Palm says:

    There is no link yet, sorry. For effects, be sure to check out http://www.eff-lang.org/.

    • dmbarbour says:

      Algebraic effects and handlers were among the first approaches I considered, and I do mention them above. They are a very nice alternative to monads. However, it seems a bit difficult to preserve the parallelism implicit to pure FP under that design, so I’m still researching alternatives. I do have one interesting idea, which I’ll blog about later.

  3. Pingback: Partial Evaluation Process Networks | Awelon Blue

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s