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.
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.
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.