A programming system with selective encapsulation and a metaprogramming focus.
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
buildlib
demos Updated references to rocketnia now that we've migrated the Era proje… Mar 8, 2017
notes In algebraic-subtyping.txt, modeled a type hierarchy: Each type unive… Apr 11, 2017
src Fixed several bugs in era-avl.js. Aug 29, 2016
test Gave Staccato mini a working def-macro. Woo! It doesn't have meticulo… Feb 26, 2016
.gitignore In Penknife, compiled the demo using Node.js. Apr 6, 2014
.travis.yml Travis: Polished deploy.sh. Specifically, removed the `touch .`, move… Dec 21, 2015
LICENSE.txt
README.asc Updated references to rocketnia now that we've migrated the Era proje… Mar 8, 2017
build-era.js Updated references to rocketnia now that we've migrated the Era proje… Mar 8, 2017
deploy.sh Updated references to rocketnia now that we've migrated the Era proje… Mar 8, 2017
gh-pages.gitignore Travis: Stopped ignoring the /fin/ directory on the gh-pages branch. Dec 21, 2015
package.json Updated references to rocketnia now that we've migrated the Era proje… Mar 8, 2017

README.asc

Era

Build Status

Programming is an activity of last resort. Like a programming language, Era is a program that facilitates programming where it’s necessary. Era tries to reduce the burden that comes with programming, including the burden of maintaining Era itself:

  • It must be easy to reimplement Era from its documented semantics.

  • If a useful goal can be accomplished by reimplementing Era in a way that breaks Era’s documented semantics, there must be another way to achieve that goal that is consistent with Era’s semantics.

  • Era must facilitate programming. For Era’s purposes, programming is when a person nurtures a serializable artifact in one time or place with the intention to make it applicable in another.

To put a limit on the scope of this project, although Era may make it easy to stay out of messes, Era will not necessarily make it difficult to get into them. After all, someone could easily get themselves into a mess just by choosing not to use Era.

Because of our broad view of programming, it even encompasses word processing, art asset production, playlist maintenance, and other creative tasks, so Era is eventually going to be an OS. However, the OS design is still far off.

Wherever it makes sense to do so, Era will help people share artifacts in the form of a monotonic knowledge representation. If any two people have collections of their favorite serializable artifacts, they can combine these collections without fear that some of the artifacts will conflict with each other. If this works, it should minimize the need to do extra programming just to negotiate conflicts. Conflict negotiation makes the maintenance cost grow superlinearly with the number of modules involved, and that kind of cost growth should be minimized so that it doesn’t put unnecessary friction in the way of knowledge sharing.

To facilitate programming, Era should also facilitate the creation of additional tools to help with programming. With quasiquotation, Era’s syntaxes will make it easy to maintain programs that generate Era’s syntaxes.

The Era project contains a few sub-projects, and their implementations may blend in with each other a bit. The one under most active development recently is Staccato.

In this document, links like this one will take you to live demos:

Most of the demos aren’t very interesting to view, but some are interactive.

The Staccato language

The popular present-day programming languages have several superficial things in common: Most of them have interpreters, compilers, and/or servers you can run from the command line, which process a file tree full of plain text files. Most of them have some IDE support. Most of them have ways to install packages from the Web. Staccato is going to be a programming language in that sense.

Staccato’s run time semantics

The design of Staccato starts with a simple model for run time semantics: Semantically, every first-class value is a tagged record, and the stack is a simple list of values that will be called. Function definitions can be attached to tags, but the behavior of a single function must always take constant time. That way, a Staccato program can always be suspended in a well-defined state.

That well-defined state isn’t always going to be useful, and it usually impedes optimizations and concurrency. Most of the time, the actual implementation details of a Staccato system will differ from this representation. However, it acts as a semantic structure against which Staccato step debuggers, profilers, JITs, reflective towers, etc. can be specified and understood.

Additionally, by considering every single first-class value to be a tagged record, Staccato is a good starting point for language features where selective encapsulation is needed: Function code is not encapsulated to everybody, but it is encapsulated to everybody who doesn’t statically "know" the tag name, and this lack of knowledge can be enforced with sandbox abstractions, common Web service data security practices, or code signing.

Staccato’s textual syntax

Staccato’s syntax is designed to get out of the way when dirty programming tricks are needed. The textual syntax is based on Lisp, but the simple addition of (a b /c d) syntax as an alternative to (a b (c d)) means it’s easy to write code in a way that avoids avoids heavy nesting:

(defn bag-minus a b
  (cast a bag a-avl-tree
    err.\;qq[Expected an a value of type bag]
  /cast b bag b-avl-tree
    err.\;qq[Expected a b value of type bag]
  /bag/bag-fold-asc a-avl-tree b /fn state elem
    (avl-minus-entry state elem)))

This has the crucial benefit that code written in continuation-passing style or monadic style can be formatted in a flat way, very much like imperative code:

(defn compile-def-type mode definition-ns name projection-list
  (bind-effects
    (procure-put-defined
      (ns-get-string str.projection-list
      /ns-get-name (constructor-name mode definition-ns name)
      /ns-get-name str.constructors definition-ns)
      projection-list)
  /fn -
  /bind-effects
    (procure-put-defined
      (ns-get-string str.function
      /ns-get-name (macro-name mode definition-ns name)
      /ns-get-name str.macros definition-ns)
      constructor-macro.projection-list)
  /fn -
  /no-effects/compile-ret-tuple mode definition-ns str.nil /nil))

Staccato’s string literals are written \;qq[...] or \;qq(...). Since this starts with a backslash and uses brackets, it’s possible to write code that generates textual code that generates textual code, at any level of nesting, without needing to scatter escape sequences all over the code.

(fn -
  str.\;qq[
    (fn -
      str.\;qq[
        (fn -
          str.\;qq[Hello, world!])])])

The forward slash can even be used with string delimiters, facilitating a string-based continuation-passing style that would be nightmarish in other languages:

(fn - str.\;qq/
\/fn - str.\;qq/
\/fn - str.\;qq/
Hello, world!)

It’s not recommended to write code in this style. However, this style is a natural consequence of using compilers that expect plain text as input. Since Staccato provides just such a compiler, it would be hypocritical not to support this kind of coding.

By default, the string syntax normalizes whitespace, so the above two examples are precisely equivalent. This is convenient for embedding natural language texts into the code, such as error messages. If necessary, individual whitespace characters can be specified explicitly using escape sequences, or whitespace normalization can be suppressed for a string altogether.

Staccato’s side effects

In usual practice, Staccato is a functional language with referential transparency. If an effect can be performed in a referentially transparent way—​that is, if the only way to observe the effect is to observe the result value—​and if it is semi-deterministic—​that is, it has only one possible result value for a given input, but it may sometimes encounter an error and fail to produce it—​then it can be performed in a direct way. All other effects are performed using a commutative monad.

If an effect is not naturally commutative with the other effects in the system, then it must be expressed as an effect that sets up a callback to be called to produce a future bundle of commutative effects. After all, "setting up a callback" is usually commutative. Unless they’re used in a completely sequential way, these callbacks will tend to fan out and lose track of each other. When this happens, they can be synchronized again using promises.

This is a general approach to all kinds of side effects, and Staccato will have at least two disjoint effect systems designed this way: Services and macros. These are described below.

Staccato’s live services

Microservice architectures are becoming prominent for good reason: Humans and computer hardware happen to be interactive systems that maintain their identity over time. Software services can be peers in that respect, replacing and abstracting over hardware APIs.

For this reason, Staccato’s error handling is based on the idea that there’s a hardware service where the Staccato code is running, and this hardware service can be interacted with like any other service. In practice, instead of real hardware, this can be any kind of implementation of the Staccato language.

Live services live through continuous time; they don’t inherently need a notion of discrete events. David Barbour’s reactive demand programming (RDP) has explored a kind of stateless computation model with glitch tolerance. The idea of glitch tolerance is that if execution is somehow incorrect for a split second, it usually doesn’t have large, lasting effects. To achieve this, at one point RDP had no notion of discrete events. All computation was in the form of continuous reactivity. Another feature that contributes to RDP’s glitch tolerance is the use of static delays, which effectively means a program cannot live longer than a duration specified in its source code.

Staccato live services will be similar to RDP. They’ll use continuous reactive semantics, and they’ll pass around explicit licenses that authorize the use of persistent state for a limited time.

Staccato’s macros and namespaces

Because it must be easy to reimplement Era, it must be easy to reimplement Staccato. Staccato will support a macro system so people can easily bootstrap their slight extensions and modifications without reimplementing the whole language.

As far as modularity and encapsulation are concerned, Staccato macros are not a good alternative to writing functions; they are a good alternative to writing compilers. Nevertheless, if Staccato macros are written with a certain discipline, they can play well with other Staccato code; Common Lisp and Racket are examples of languages where this kind of discipline has paid off.

In particular, Staccato has a macro hygiene discipline. Macros pass around hierarchical namespaces, and the programmer should make sure to pass mutually exclusive namespaces to any two subcomputations that shouldn’t be able to see each other’s work. The global definition namespace is another parameter to the macro, and it’s usually shared by all subcomputations, but it can be replaced with another namespace to achieve sandboxing.

Staccato’s top-level declarations will act concurrently. A macro defined in any declaration in a codebase will be accessible anywhere else as long as there are no cyclic dependencies. Macro implementation code will see actually see this as an explicit form of concurrency. From the perspective of macro implementation code, installing a definition is a commutative side effect, and looking one up is a referentially transparent side effect.

To support incremental compilation, the macro system passes around a value representing the current "time," which in this case means the current compilation. That way, a definition lookup may have a result that varies over multiple source code edits, while still being a deterministic computation.

The Era module system

Although it hasn’t been expanded upon in a while, the Era project started with the intention to program to a module system that doubled as a monotonic knowledge representation. That is, the meaning of a module cannot change when other modules are installed, although it can become better understood.

The module system design will support selective encapsulation. If someone has a module installed, they know its source code, and they’ll be able to use the fact that they know it. For instance, this will be useful for proving additional properties about code that has already been published. If a module can prove that it’s by a particular author (e.g. using code signing), that’ll be even better; it will be able to query all that author’s code and private definitions. The notion of "private" isn’t even needed; every definition can be published by one author and published for another. With this kind of system, there will be no need to have more than one declaration per module.

The Era module system will have a certain approach to the Expression Problem. The Expression Problem is usually understood as a problem of how to make a system extensible by more variants of objects and extensible by more operations over those objects at the same time. First, this simplifies if we look at "more operations" as "more variants of operations"; now we’re just adding a variant to the system in both cases. Next, we can safely extend the system with a new type if we can prove that, for all possible sets of other people’s extensions to the system, our extended implementation continues to behave the same way as the old implementation as long as the inputs do not include our new variants.

Era’s module system probably isn’t expressive enough to do that kind of proof in any interesting cases, so it’s not ready yet. Michael Arntzenius’s language Datafun, which supports monotonic function types as a built-in concept, will probably reveal a much simpler way to design a monotonic knowledge representation like this one.

The Penknife language

The Era repository also houses the current version of Penknife. Penknife shares Staccato’s syntax, and it was the original testing bed that the syntax and quasiquotation approach were developed for.

Penknife has a novel system whereby, if a variable is used more or fewer than one time in its lexical scope, a dynamic behavior is called. This dynamic behavior is user-defined, but it can do resource cleanup, throw errors (for values that should not usually be aliased), or even create multiple completely different values to use for each of the variable usage sites. This experiment was specifically intended for the purpose of easily constructing graphs that resembled the data flow of a variable. The design worked. However, these graphs were of limited use without a corresponding way to track control flow.

Penknife also has a way to enforce purity of subcomputations, effectively by making all side effects depend on a global state that can be temporarily replaced to forbid effects. Like Haskell’s ST monad, there’s a corresponding way for a pure Penknife computation to create a world of mutable boxes that it can temporarily take advantage of to employ impure programming techniques. Once the world expires, its boxes can no longer be modified.

Penknife’s implementation is in continuation-passing style—​actually, a sort of world-passing and continuation-passing style—​and since it was so frustrating to write this in JavaScript, it motivated the creation of Staccato as a way to generate it automatically. Ironically, this was also a contributing step toward Staccato’s side effect style, which has world-passing and continuation-passing aspects to it as well.

Various notes

The notes/ subdirectory contains a collection of unsorted words about topics in and around Era. The file src/era-tacit.js is mostly useful for its unsorted notes as well.

I’ve frequently revisited the topic of combining the calculus of structures (deep inference) with the calculus of constructions (dependent types). The calculus of structures is attractive to me because it indicates that a manipulation of a local structure can be valid regardless of what’s going on in the rest of the world. It could be a way for logical inference to act modularly. The Era approach to modules will already let programs be broken apart to one definition per module, and the calculus of structures could potentially let the expressions themselves be broken apart into an individual connective per module. But combining the calculus of structures with dependent typing has been quite a challenge.

About this project

Era is released under the MIT license. See LICENSE.txt.