Wikilon Dictionary Applications

A repeating cycle of simplification and refinement has fine-tuned Wikilon since I introduced it over a year ago. One area where Wikilon has changed significantly is its application model, that is: how I expect to host server-side applications and debugging. The idea now is to use AO dictionary applications for everything, including edit sessions and issue trackers.

Dictionary Applications

An ‘AO dictionary application’ is any application whose state is represented within a healthy AO dictionary. An AO dictionary is a simple association of words to definitions. A ‘healthy’ AO dictionary is acyclic, fully defined, and well typed. AO is a purely functional subset of Awelon Bytecode (ABC) that uses of `{%word}` tokens to link definitions of other words. Linking a word is trivially equivalent to inlining its definition.

Humans usually don’t mess directly with AO bytecode. Instead, they leverage editable views such as Claw, a Forth-like command language, or a more structured variant.

Dictionary applications take this ‘editable views’ idea to a further extreme. Application views may freely involve multiple words and definitions from the dictionary, including evaluation of functions. One very useful pattern for dictionary applications that leverages evaluation is the command pattern. Represented in an AO dictionary, the command pattern looks a lot like:

@foo.v0 (creates initial foo)
@foo.v1 {%foo.v0}(command to update foo)
@foo.v2 {%foo.v1}(another command)
@foo.v3 {%foo.v2}(yet another command)
@foo {%foo.v3}

Here, the word `foo` represents an application object, perhaps a database or a canvas or a collection of communicating processes. With each new command, we add a new definition (e.g. `foo.v4`) then update `foo` to point to the new ‘head’. To obtain the current state of `foo`, we naively would evaluate `foo` from scratch in a provided context. Fortunately, the command pattern is cache-friendly: if we have already computed `foo.v2` in the same context, we can reuse this and evaluate just the last two commands. While command pattern would conventionally be used to present only the ‘current’ state of an object, some applications like REPLs (or a variant with constructive graphics, perhaps inspired from iPython-notebooks) might present each command together with some computed output.

Between hosting state in source, and the command pattern, dictionary applications have many nice features:

  • applications are persistent, portable, versioned like source
  • live coding and continuous testing become implicit
  • abstraction, compression, indexing of state and commands
  • excellent fit with HTTP and REST architectural styles
  • cache-friendly patterns for common updates
  • unlimited undo of commands and dictionary manipulations
  • back-in-time debugging via command or dictionary histories
  • trivial forking, cloning, snapshots of applications

Dictionary applications aren’t limited to explicit ‘refresh’. Trivially, an application could naively poll the dictionary to maintain a current view. But real-time feedback is feasible with Comet technologies like AJAX long-polling or subscription. Real-time views offer a convenient basis for both live coding and communication between agents that share the dictionary.

A dictionary is effectively a filesystem with a rich, computational semantics. Unlike conventional filesystems, a dictionary requires no special consideration for redirects, ad-hoc composition of content, or dictionary compression and procedural generation.

Note: Dictionary applications subsume and simplify a lot of my older ideas, including Wikilon filesystem, abstract virtual machines, extensible syntax via Claw-like views, and embedded literal objects via command patterns.

Real World Effects

Dictionary applications, in their natural environment, are implicitly multi-agent systems.

If our only agent is a human, we can model calculators, REPLs, interactive fictions, and other applications that remain ‘paused’ while waiting on the next human action. If we assume multiple humans, we can suddenly model more interesting applications like forums, shared chatrooms, chess, multi-user dungeons. Communication between humans becomes an implicit effect: humans observe updates caused by other humans. With software agents, or ‘bots’, we can support ad-hoc effects. For example, a human might add a request to a shared chatroom that requires querying an external database. A bot sharing the same chatroom then queries the database and injects the result back into the dictionary to fulfill the request. With software agents, we can model command shells, or time-dependent systems that we iteratively ‘step’ forward until a stable state is reached.

For software agents, effective control becomes important. This is achievable with attributes, i.e. annotations that have no runtime semantics. In the Claw view, I express attributes with parentheses around a list of words, e.g. `(license:BSD3 author:dmbarbour category:math)`. This desugars to a dropped block of annotations `[{&license:BSD3}{&author:dmbarbour}{&category:math}]%`. We can use attributes for all sorts of things: deprecations, todos, indexing, authorship or licensing where it matters, etc.. For bots in particular, we can use opt-in attributes like (allow:myChatBot) or opt-out attributes like `(noindex)`. I generally favor opt-in attributes in cases where a bot will modify the dictionary.

Concurrent Applications

Evaluation within a dictionary is deterministic. Despite this, it is frequently to our advantage to explicitly model concurrent systems, e.g. communicating processes or actors systems. A ‘concurrent system’ is reified as a dictionary object that we can ‘run’ a few steps at a time or interfere with in simple ways (e.g. injecting messages or twiddling state). Our applications are then modeled within these concurrent systems. This pattern buys us several features:

  • ability to iteratively ‘run’ the system a few steps at a time
  • implicit step-based debugging below granularity of ‘commands’
  • ability to interrupt or interfere with applications after any step
  • ability to extend applications by injecting new computations
  • animate, graph, or scrub rendered views of application state
  • easy integration of multiple agents with active application

Debugging concurrent applications hosted in a dictionary is much less unpleasant than doing the same for applications hosted on hardware. For example, there is no risk of heisenbugs. We’re free to step back in time via the command pattern. We can explore multiple valid progressions of non-deterministic concurrent applications (e.g. by using different PRNG seeds to shuffle messages).

The main feature we lose is hardware races for evaluation. We cannot rely on timeouts as a basis for hand-wavy soft real-time behavior. If we need well-timed applications, we’ll need to use explicitly timed programming models (that allow us to express how much time a computation should take, e.g. in terms of seconds or musical beats).

Managed Dictionaries

Preserving a long history for command pattern objects isn’t necessarily a problem. In cases where ‘commands’ are due to discrete and infrequent human actions, such as mailing lists and forums, it is entirely feasible to keep a complete history. Terabytes of storage are quite affordable these days. However, in the general case we might want something like garbage collection for our application histories. Besides GC, I also imagine wanting to automatically refactor, compress, and optimize code in our dictionaries.

As with real-world effects, automatic management of our dictionaries is feasible if we leverage software agents guided by attributes. In particular, I envision tagging words with three attributes to guide automatic management:

  • hidden – avoiding external references; may delete this word if unused
  • opaque – only care about behavior of this definition, not structure
  • frozen – committed to this definition; may inline into opaque definition

Opaque words allow for automatic refactoring, inlining, etc.. Frozen words may be inlined. Hidden words may be GC’d. We can model words with all three attributes, easily enough. Additional attributes might be leveraged to implement ‘gradual’ decay models (e.g. exponential decay). For example, an attribute could represent an expiration condition managed by an independent software agent.

Regarding ‘Big Data’ Applications

It is feasible for application objects to contain multi-gigabyte databases, FTP services, and the like. In conventional programming systems, we’d be forced to shove data out to an external database or filesystem to prevent memory overload. However, Wikilon is designed to address this problem without external dependencies. Instead, we annotate large values for external storage via `{&stow}`. Stowed values are serialized to cold storage but will implicitly be loaded and cached in main memory when necessary. My current implementation uses VCache, which uses a LMDB.

By stowing nodes in a large trie, we can easily model filesystems and databases without loading them into memory all at once. Using finger-trees, we can model larger-than-memory logs and queues. These large values are held by the cache. If we update something far upstream of our cached values we may need to recompute our application states. However, the common case would involve incremental updates and viewing only ‘final’ states.

Parallelism also helps with scalability because it can help quickly recompute a large application state in cases where our updates do not align nicely with our incremental models or existing cache. AO code can easily leverage Haskell’s par/seq parallelism with a few annotations. Long term, it is also feasible to optimize specialized subprograms akin to Haskell’s accelerate package.

Extracting Applications

As Wikilon is a development platform, we’ll sometimes want something closer to the ‘conventional’ edit-compile-test style. For example, we might want to provide a binary for use on an Android phone. This is achieved through an extraction process. The extracted binary is essentially a view on the dictionary, though not a particularly editable one. Conveniently, extraction could be presented to users as a simple GET on an HTTP link, or via a form that constructs an appropriate link (with various compilation flags).

Our extractor must know how to compile a popular ‘type’ of applications for an appropriate back-end. This is easiest for applications modeled as objects with the command pattern, and especially those modeling a concurrent system. Command pattern objects are easy to separate from the dictionary because their ‘state’ doesn’t involve parsing bytecode, and they clearly have ‘updates’. A self-describing object would be even better, i.e. one that can be queried for available commands. Concurrent systems enable us to have some commands take time while permitting interruption or interference, and thus are a good fit for many target systems.

The ability to extract applications in medias res is valuable. This allows us to easily ‘create’ new applications through incremental interactions with existing applications, like working with a spreadsheet or preparing a form so it is mostly filled. So, I think dictionary applications will help a lot even in these cases where we plan to extract a separate binary.

Posted in Language Design, Live Programming, Modularity, State, User Interface | Leave a comment

Command Language for Awelon

Claw (command language for awelon) is an editable view and syntactic sugar for AO (awelon object). AO is a subset of Awelon Bytecode (ABC) that limits tokens and texts. Tokens of the form {%foo} link definitions of other words in a dictionary. Dependencies within the dictionary form a directed acyclic graph. (Recursion is anonymous, via Z-combinator.)

Claw provides a Forth-like experience, suitable for simple REPLs and command shells, albeit with better support for higher order programming and weaker support for ad-hoc side-effects. AO is purely functional, but we can model effects monadically.

Claw is interesting because it’s extremely simple while remaining very effective.

Claw Semantics

Claw semantics is a trivial multi-step expansion, ultimately into bytecode. For example:

Code Expansion
2/3 2 3 ratio
4/10 4 10 ratio
3.141 3141 3 decimal
-1.20 -120 2 decimal
6.02e23 6.02 23 exp10
42 \#42 integer
-7 \#7- integer
[inc mul] \[inc mul] block
\[1,2,3] \[1] \[2] \[3] bseq bseq
inc mul \{%NSinc} \{%NSmul}
“foo” \”foo
~ literal

The lowest level of expansions are the escaped forms, indicated by prefix `\`.

  • bytecode escape, e.g. `\vrwlc`
  • token escape, e.g. `\{foo}`
  • text escape, e.g. `\”foo…\n~`
  • block escape, e.g. `\[inc mul]`

These expand almost directly into bytecode, excepting blocks which must be recursively expanded. Escaped forms shouldn’t see much use at a command line. Users should be encouraged to define words rather than issue commands at this level.

The claw expansion has two important properties.

First, the expansion is context-free. That is, the expansion of a number, text, block is completely independent of its surrounding context. Context free expansion has valuable locality properties, and guarantees that claw code preserves the same tacit concatenative composition and refactoring properties as the bytecode.

Second, this expansion is reversible. Bytecode may be ‘parsed’ back into the forms that generate them, e.g. starting with escaped forms at the bottom level, reducing some tokens back to words, and reducing sequences such as `2 3 ratio` to `2/3`. This reversibility property allows us to understand and treat claw code as a lens or editable view of the underlying bytecode.

Claw code (command histories, etc.) should always be stored in the canonical, fully expanded bytecode format. The burden of providing an editable claw ‘view’ then shifts to either the editor or an intermediate layer (e.g. a FUSE-based filesystem view, or a web server). Doing this improves claw’s portability and extensibility. Bytecode can easily be stored and processed by backends that know nothing of claw syntax. We could keep command sessions in an AO dictionary for regression testing and refactoring purposes. If an editor didn’t know about rationals it could still preserve meaning and present `2 3 ratio` to a user.

Command Sequences

Command sequences are an important feature of claw. They enable concise expression of data and flexible expression of monadic DSLs.

Claw allows blocks to be broken into segments by a simple command separator: the comma. For example, [1,2,3,4,5] breaks into five separate blocks. These segments are then recombined, right-to-left, by word `bseq`. Depending on how we define bseq and interpret the resulting block, we can readily stream data, compute in continuation passing style, or model monadic effects.

Claw Namespaces

In practice, we will develop alternative command environments (shells, REPLs, etc.) for different use cases. I imagine these developments will share metaphors and structures with existing environments, so we’ll need overlap in the command words used, albeit often with a slightly different implementation. Namespaces provide a simple means to reuse words in different contexts.

Claw has exactly one namespace for any given region of code.

The namespace is added as a prefix in the expansion of every word, including words integer, decimal, block, etc. used in code expansions. For example, word `integer` will expand to \{%bar:integer}` if we are in namespace `bar:`. Namespaces are the exception to claw’s context-free expansion constraint. The singular namespace is simple enough to avoid compromising locality and composition, though a little care is needed to preserve namespace information if refactoring at the claw code layer.

A namespace annotation may appear at any point in a Claw command stream. A namespace annotation has the form `#bar:`, meaning `switch to namespace `bar:`. Claw reserves the `#` prefix for this purpose. To guarantee reversibility, a namespace annotation expands into the annotation `{&ns:bar}` at the bytecode layer.

A change in namespace lasts until we either reach the end of the current block or we again change namespaces. Blocks become implicit regional delimiters for namespaces, e.g. for `[#bar: 42 foo]` the `#bar:` annotation only applies within the block. This supports a common use case where we apply a block to a different context than where we constructed it.

Given the restriction to a single namespace, there is never any ambiguity about which foo you’re invoking. There is no need to consult a dictionary (e.g. to search for a defined word) to determine how words link to each other. There are no boiler-plate import lists. This restriction contributes wonderfully to claw’s simplicity and concision.

OTOH, every namespace must define its own version of every common word. If performed by hand, this would be a huge investment of a developer’s time and energy just to catch up and keep up. This cost might be mitigated by developing a few tools or software agents to automate the process.

Claw Extensions

Claw is extremely extensible.

While my immediate focus is on simple numbers and small texts (the original ‘AO’ feature set), it is feasible to support matrices, tables, and other structured data. Structured programming is also viable, e.g. conventional loops and if-then-else expressions converting to use of blocks and keywords (e.g. expansion `\[cond] \[body] while_do_` could correspond to a conventional while loop). Similarly, sugar for monadic expression could simplify integration of ad-hoc sequential effects models.

Any extensions must preserve the properties that expansion is context free (hence local) and reversible. But those are not difficult constraints to work with.

Of course, there are limits on what we can effectively support in context of line-oriented command text. Some syntax extensions, such as matrices or structured programming, would require a page-oriented programming environment. Something akin to iPython-notebook environments, wikis, or structure editors, might be appropriate. With structure editors, an interesting possibility is interactive extensions – e.g. checkboxes, sliders, color pickers, canvases.

Aside: This claw-structured bytecode (based on parsing bytecode into a structured editable view) is independent of the AO structured definitions (based on evaluating bytecode into a manipulable value structure). I hope these orthogonal kinds of structure will augment each other, or at least address different niches. But, with extensions, there is some overlap in potential utility. I’ll need to see how this works in practice.

Command Shells and Effects Models

A command environment, e.g. a REPL or command line, has a state value. Each claw ‘command’ will be a pure function from `state → state`, and is applied to atomically update the state value. The state value may be arbitrarily sophisticated, e.g. including a stack, a filesystem model, a turtle-graphics canvas. Our editor may have some expectations about the shape of this state. For a simple Forth-like REPL, we might simply render the top few elements on the stack after each action. If we want turtle graphics, we might choose to render a canvas after each step. Command environments don’t need to be purely textual.

To integrate real world effects, we’ll assume that some external environment or agent has access to the state, perhaps indirectly or only a fragment of it. As a simplistic example, our state might contain an inbox and outbox at a predictable location. The background agent feeds the inbox and empties the outbox between user commands. A more sophisticated effects model might allow the user to automate how each incoming message is processed. The exact details are left to each command environment.

Effects modeled this way are inherently asynchronous.

They’re also a good fit for many of Awelon project’s UI design principles:

  • all long-running behaviors are represented in human meaningful and modifiable state
  • users may assign their own, private meanings to the structure of their environment
  • human actions and gestures are modeled as a stream of code that manipulates state
  • failures are coarse grained and simple to deal with (e.g. due to atomic commands)

Assigning private meanings to state requires a command environment that explicitly hides private structure behind a public interface. For example, if our state were an AVM triple (i.e. state, behavior, signal) then users would have a private state model while the behavior function and signal values provide a public interface.

For many use cases, synchronous APIs are concise and convenient. To preserve benefits of synchronous APIs while working with inherently asynchronous effects is feasible with futures or promises, i.e. such that tokens serve as placeholders for future results and actions can suspend. Modeling futures does require some careful attention because Claw doesn’t directly support mutable state, so it must be modeled indirectly, e.g. with a map from tokens to waiting clients or content.


In the short term, claw can almost immediately provide a simple Forth-like REPL or turtle graphics environment, and it won’t take much effort to provide at least a basic environment for real world interaction. Anything that fits a basic shared state or message passing paradigm should be easily adapted. Long term, claw has potential to provide an excellent user experience for real world activities relative to command line shells and perhaps even some graphical environments. But this won’t happen easily. A lot of development is necessary to even begin catching up, and a lot of tuning would be necessary.

Claw is extremely simple, transparent, composeable, and adaptable. These are excellent properties for my long term goals.

Posted in Grammars, Language Design, User Interface | 1 Comment

Purely Functional Performance

An argument I’ve encountered umpteen times, most recently on LtU, is: imperative programming performs better than functional programming because it has O(1) updates, while updating functional structures is typically O(lg(N)). I’m now weary of repeating the counterpoints so, like a good programmer, I’ve decided to refactor into a blog for future linking. Here goes:

In any physical system, memory is laid out in a 3-dimensional physical space. Consequently, speed-of-light delays between memory and any centralized processing unit increase by at least a factor of N^(1/3). Further, there is a lg(N) factor if we give every location in the space a unique address. Thus, if we account for known physical constraints, the very best we can theoretically do for centralized processing of a data structure is O(lg(N) * N^(1/3)). (Or maybe that `*` should be a `+`.) In practice, memory tends to be laid out in two dimensions (surface of a board, surface of the Earth) so the factor is actually N^(1/2).

Usually, we ignore these physical factors. However, they’re more difficult to ignore today than they were historically. Today, we have three levels of cache, NUMA, distributed shared memory models, using memory itself as cache for the disk, and so on.

If we do account for these physical factors, then functional data structures have the same asymptotic properties as imperative ones.

Conversely, functional structures can easily model physical memory – e.g. use a trie where every key is a 64-bit number. In this case, we can guarantee that the access and update is O(1) in the same asymptotic sense as is the case for physical RAM. Any update to the trie requires creating at most 64 new nodes.

So, no matter which perspective you take – physical or logical – functional code isn’t asymptotically worse than imperative code.

However, FP does tend to be less efficient in every relevant absolute sense. Allocating 64 nodes is a lot more expensive than in-place mutation of RAM in a 64-bit address space. So, I do acknowledge that performance is a concern.

Performance can be divided into a few different concerns, such as efficiency, utilization, scalability. Efficiency: do we use our resources well? Utilization: do we use all of our resources? Scalability: can we easily throw more resources at the problem? (or gracefully take some away?)

While FP isn’t doing so well with absolute efficiency, it can utilize resources and perhaps has greater potential for scalability (due to ease of parallelization, and location-independence of computations).

Further, due to structure sharing, FP performance tends to be more stable under external scenarios that might benefit from acquiring atomic snapshots of machine state: orthogonal persistence, time travel debugging, state visualization, live programming, rollbacks for exception-safe consistency, parallel reads and mirrored servers, etc..

So, while performance certainly is a concern, I believe FP fares very well – both asymptotically and absolutely – after we step back and look at the big picture.

Posted in Language Design | Leave a comment

Abstract Awelon Virtual Machines

I’m still working towards Wikilon, a wiki-based development environment and initial software platform for the Awelon project. The design is still fluid, and has taken me in some interesting and unconventional directions on the ‘development environment’ side.

On the ‘software platform’ side, I was contemplating a filesystem model, for long-lived data and applications. But I was concerned: how do developers disentangle their app from the filesystem? So I shifted to Wikilon hosting abstract virtual machines (AVMs) that host applications. AVMs provide boundaries for entanglement, forcing developers to address latency, concurrency, and disruption. This week, I decided I don’t want the heavy weight of a filesystem in every AVM. AVM state is now just a value, and a trie value is a decent model of a filesystem if developers want to use one. The development of VCache makes it entirely feasible to model filesystem-sized values containing gigabytes of data.

I selected message passing as a basis for communication between AVMs. I’m not fond of message passing, but ease of implementation and integration with existing systems sold it to me anyway.

Some interesting differences between AVMs and other message passing systems:

  • AVMs cleanly separate state from behavior. The behavior of an AVM is a pure function of the form `(InMessage, State) → (OutMessages, State)`. All messages travel through this function. This separation makes live programming easy: bind behavior to a Wikilon dictionary, such that edits affect behaviors in real-time. Similarly, we can apply a structure editor to browse and directly manipulate state.
  • Every message carries a capability-secure context: every InMessage is a (Context, Content) pair while every OutMessage is a (Capability, Content) pair, where the capability is an ADT that keeps context opaque to the sender. An AVM is (usually) given a pure function `self :: Context → Capability` so that it can construct capabilities needed for query-response and other feedback patterns. An AVM constructs ad-hoc, fine-grained capabilities on the fly.
  • AVMs cannot create/spawn/fork/etc. new AVMs as a primitive. However, AVMs may host other AVMs hierarchically, using context to route messages. AVMs tend to centralize a lot of state under just a few objects, which has many advantages for debugging. That said, spawning can be modeled in terms of a capability to ask another machine to host an AVM.
  • A friendly scheduler is specified. Messages between AVMs are implicitly grouped into batches. Output messages resulting from a batch are sorted into a new batch for each target AVM. Batches are processed atomically, and messages within each batch preserve order. Batches between machines also preserve order, using timestamps. Thus, developers don’t need to think about worst cases for non-determinism.
  • A ‘common capabilities’ concept is also supported. For example, if access to UTC time is provided by a capability, and we send this capability to a remote host, said host may recognize this capability as a common one and provide a local implementation. This is discretionary; the host may instead send the message across the network to get UTC time at the origin. This mechanism is highly extensible: time, random numbers, high performance matrix multiplication, HTTP access, multi-homing, etc. can be modeled this way.
  • I’ll make a reasonable effort at timely, reliable delivery of messages, but I won’t guarantee delivery. If a message cannot be delivered easily, I’ll drop it. If a message has a much larger latency than physically expected, I’ll drop it. Dropping messages allows a simple and scalable implementation in the face of varying connectivity, congestion, migration, administration that might take a machine offline, etc.. AVMs can react intelligently to network conditions via special capabilities that can report delivery status or provide alternate behaviors. Developers are encouraged to explicitly model mailboxes and tuple spaces and other robust offline delivery mechanisms where needed.
  • In addition to state and behavior, every AVM has a ‘signal :: Context’ value. This value is used by the hosting environment to get an AVM running (an ‘init’ signal) or support graceful shutdown (a ‘stop’ signal) or indicate other concerns (e.g. low power) or to inject information about the environment or the Self function. Basically, it’s an initial capability. It provides an extensible set of generic AVM methods.
  • At the toplevel, AVMs will be given global names – a secure hash of a public key – with routing based on a distributed hashtable. This makes it easy to create tons of fine-grained AVMs, to move them across physical systems, and to secure them against man-in-the-middle attacks without relying on a central naming service. If developers want common names, e.g. similar to domain names, these might be supported via NameCoin and similar protocols. (I’d rather avoid depending on ICANN or CAs.)

As with other message-passing systems, effects are modeled in terms of sending messages to resources masquerading as machines. Access to Redis, S3, AMQP, XMLHttpRequest, sockets, user interfaces, etc. could be modeled this way. Though I’ll initially focusing on just whatever I need for web services and web sockets.

Addendum: to emphasize a few points

I really love the simple, pure, non-monadic nature of the step function.

This sort of straight-line code is easy to express in a first-order manner. It is abundantly clear to developers that nothing happens – no output, no new input, no progress – unless the function terminates. It is clear that developers cannot wait on a message in response to a send unless they model waiting in a higher layer abstraction. The loop itself is clearly separated from state, which simplifies both live programming and visualization or direct manipulation of machine state.

I believe AVMs will prove highly scalable, and this is greatly aided by their purely functional nature and clear simplicity. Read-only messages are easy to parallelize. If we notice (by comparing before and after states) that many messages are read-only, we can heuristically switch to parallel modes and use compare-and-swap or other rework models to resolve read-write conflicts. Developers can leverage this by dividing AVMs for read-mostly loads or arranging for a single writer to avoid read-write conflicts. This sort of parallelism is highly scalable, e.g. can be implemented through replicating the entire abstract machine. Read-write messages are more difficult to parallelize. But if we have expensive computations distributed across small partitions of state, we can use pure parallelism to be processing many updates at one time. Normal sharding techniques also apply.

The real challenge will be to make these AVMs competitively efficient, i.e. by developing an effective compilers or JIT for Awelon Bytecode, leveraging annotations for memoization, etc..

Posted in Concurrency, Modularity, Open Systems Programming, Security, State | 10 Comments

Structure Editors for Wikilon

I have a new design that vastly improves upon my older extensible syntax and embedded literal objects approaches, and brings Wikilon many steps closer to my long term HCI goals for Awelon project. And it’s surprisingly simple!

Every word in the Wikilon dictionary is now defined by a pair: a compiler function, and a structured value, such that compiling the value returns a block – a first-class function – which is accepted as the meaning of the word. Both elements of this pair are encoded in Awelon Bytecode (ABC), albeit with access to the dictionary via unforgeable `{%foo}` tokens.

Structured values in ABC are constructed of only a few basic primitives:

  • numbers – rational, precise (unless weakened)
  • products (a*b) – pairs of values
  • sums (a+b) – ~ Haskell Either type
  • unit (1) and void (0) – structured identities
  • blocks [a→b] – first class functions
  • discretionary sealers {:fooType} – ~ Haskell newtype

These are the basic types. Floating point numbers might be requested via annotations, e.g. {&float}. Strong, cryptographically sealed values may be accessible via side-effects. But we don’t really need to consider anything beyond the basics for our dictionary and compilers.

The simplest possible compiler function is the identity function, which works when the structured value for the definition is just a block of code.

:swap [rwrwzwlwl]
:dup [r^zlwl]
:swapd [rw {%swap} wl]
:rot [{%swapd} {%swap}]
:dupd [rw {%dup} wl]
:over [{%dupd} {%swap}]

Conveniently, this trivial ‘identity function’ compiler corresponds closely to the (now deprecated) Awelon Object (AO) code. Compare AO code as it exists today:

@swap %rwrwzwlwl
@dup %r^zlwl
@swapd %rw swap %wl
@rot swapd swap
@dupd %rw dup %wl
@over dupd swap

To directly read and write this raw ABC in place of AO code is doable. Indeed, I’ll probably do some of that when getting started in this new model. However, the growing noise from `{%foo}` wrappers and inconvenient number encodings (e.g. `#1234#1000/*l` is the ABC equivalent to `1.234` in AO) would grow wearisome. Fortunately, in context of a structure editor, I think we could present blocks as an AO variant to the user, even rendering `1.234` as appropriate, and perhaps fading out raw data plumbing code. And hyperlinking words, of course. :)

But we aren’t limited to the trivial compiler. We can use arbitrary, ad-hoc structures to represent our word definitions… and we can render the definitions appropriately, i.e. using lists and dictionaries and so on.

The `{:fooType}` discretionary value sealers provide a convenient mechanism to denote that a sealed substructure might benefit from a special rendering and editing widget. This can be very ad-hoc, driven by convention and reflection. E.g. if we want markdown text to use special syntax highlighting and editing tools, we could model this as a text literal followed by `{:md}`, and allow our editors to know what is expected in this case or reflect back into the dictionary searching for words named something like `edit:md`. This should achieve most of the advantages of embedded literal objects, while avoiding most of the weaknesses.

This new approach has many other important advantages:

First, the use of `{%foo}` tokens to access words makes trivial a global renaming of words. Simple renaming is actually what led me to this design. My earlier approach to extensible syntax left word-recognition to a user-defined parser function, which made it too difficult to recognize, refactor, or replace words in a more generic sense.

Second, definitions modeled this way are very scalable – i.e. because it’s easy to use generic mechanisms for compression, linking, automatic refactoring, structure sharing.

Third, it’s easy to save arbitrary data structures into the dictionary to simplify the flow of application-generated data (or even whole application-snapshots) back into reusable code.

Fourth, it’s easy to reuse compiler functions, or even embed them (e.g. constructing a pair of a foo value and the foo compiler), when modeling higher level languages. Thus, languages are readily compositional.

Fifth, with respect to my long term HCI goals, it’s easy to model user input as streaming code, functions that operate on the structured value. There is no need to repeatedly parse and pretty-print. We can abstract a stream into new user macros and editing tools, or as ad-hoc reusable functions.

This technique is, in a broad sense, similar to storing an AST in the database. But it also differs in ways that I consider interesting: opacity of block structures to the compiler function, easy support for user-macros to construct and manipulate the structured values, absence of predefined structure, and easy structured reuse of languages. I believe this new approach to extensible syntax and structured editing will prove a good long-term fit for Awelon project.

Addendum 20150302: We can use metadata to associate a compiler function with each word; however, metadata is relatively inaccessible. An interesting alternative is to push the compiler function into the structure generated by each word, e.g. such that definitions have type `type Def a b = ∃v.∀e. e → ([v→[a→b]] * (v * e))` and an example might appear as `:fooExample mkFooStruct [{%fooLang}]`. This technique is simple, universal, and offers developers much ability to directly manipulate and refactor language (how a structure is interpreted) in addition to the structure. The simplest compiler function is still identity, e.g. `:dup [r^zlwl] []`.

Posted in Language Design | 5 Comments

Haskell VCache 0.1

The first version of Haskell VCache is now available on Hackage. Before installing VCache, you may need to `sudo apt-get install lmdb-dev` on your Linux system, or install LMDB and its header files by some other means.

At this point, the primary features of VCache seem solid. PVars and VRefs are each first-class. The reference counting garbage collection is very simple. Structure sharing for values works. The concurrent aspects are kept simple, albeit bottlenecked at the moment by a single MVar. The batching mechanisms work very well. It seems easy to use, at least in ghci. But testing isn’t very rigorous.

There are performance improvements to be had, especially with respect to cache management.

But if you’re interested in an alternative to acid-state that can support very large values and fine-grained, first-class mutable variables, then give VCache a try. Also, let me know where the documentation can be improved.

Posted in Language Design | 3 Comments

Extensible Syntax for Awelon Project

I’ve been exploring extensible language for almost as long as I’ve been interested in PL. A few years ago, I posted some constraints for user-defined syntax that I had developed c.2007. More recently, I’ve described a alternative to DSLs based on embedding applet-like objects as literals in source code. The latter is especially interesting because it might enable ad-hoc graphical languages for problems like building game worlds, music, graph literals.

Despite my interest, it remains unclear to me whether this is a “good idea”. Extensible syntax presents significant challenges for tooling (e.g. reporting errors, syntax highlighting), and can result in a steep learning curve for programmers. So, when I started Awelon project, I chose to table efforts on this subject.

With the ongoing development of Wikilon, I feel it’s time to explore extensible syntax more seriously. And I’m also interested in the possibility of unifying user-defined syntax with embedded literal objects.

Summary of constraints for extensible syntax:

  • limit syntax to boundaries of one module
  • use one short word to indicate syntax
  • avoid modifying syntax within a module
  • syntax should be modular, composable
  • syntax should be a library, not external tool
  • trace errors to whatever the programmer sees

The motivation for these constraints is primarily to minimize boiler-plate, support “small” modules, simplify incremental compilation, support tooling.

I plan to base Wikilon on Awelon Object (AO) code. Each AO word is a function, a module, and a page in the wiki. AO has a simplistic Forth-like syntax. A typical module is between five and fifteen words and literals. Many modules are just one line. A wiki with very small pages is viable if we allow the browser to open multiple pages on a single canvas, e.g. similar to CodeBubbles.

With DSLs, data modules, etc. some of these pages would become much larger than the typical AO word. But we should favor a low overhead so we can still use small modules even with alternative syntax. Using just one word per module to indicate language seems a nice target. If a language needs additional parameters, it may always parse them.

Module text would then be processed by the language.  The exact nature of this processing is still an open question: we might translate the input to AO code, or to an AST, or leverage a monadic API to build some object representing the code’s meaning. I favor targeting an API because it better fits the ‘code as material’ metaphor and readily supports staged computation (i.e. use behaviors defined by other words) and may be readily extensible and composable if we choose a good general model for languages (e.g. machines rather than parser combinators).

A concrete import/export format like the following might work well enough:

:benchmark 0 [4 +] 1000 1000 * repeat
:repeat assertNatural .rw [step.repeat] bind fixpoint .wl swap inline
:step.repeat rot dup 0 gt [drop3] [action.repeat] if_
:action.repeat dec unrot dip2 inline
:fixpoint .prebind_l .fixfirst
:.prebind_l %r [%l] %rol
:.fixfirst %r' [%^'ow^'zowvr$c] %r^owol
 MoO moO MoO mOo MOO OOM MMM moO moO
 MMM mOo mOo moO MMM mOo MMM moO moO
 MOO MOo mOo MoO moO moo mOo mOo moo

I favor flat, streamable formats like this because they’re good not just for import and export, but also for continuous updates and synchronization. This format could be easily extended with new toplevel operations, e.g. to add temporal information or author metadata, or to support diffs. I’m assuming that newlines in content are escaped by trivially following them with a space.

The above seems a good start, though I might favor plain English ‘define’ and ‘using’ instead of ‘:’ and ‘#’.

But can we also support nice graphical languages?

I’ve had some difficulty adapting ‘embedded literal objects‘ to Wikilon. One of the big problems was identity: when objects are embedded at arbitrary locations in source code, it becomes difficult to name those objects, i.e. you’re stuck saying something like “the third embedded literal in function foo” and that name might not be very stable.

Naming objects is convenient for many reasons. For example, it simplifies recording ‘view’ information, e.g. such that clients might render multiple views of the same 3D scenegraph, each with a different rotation or camera position. Naming also simplifies streaming updates. For example, the browser might stream “I performed update XYZZY with parameters 1,2,3,4” updates to the named object, and the Wikilon server might stream rendering updates back to multiple views of that object. The ability to stream updates is valuable because embedded literal objects may grow large, and we’d rather avoid the costs of shuttling them between client and server or repeatedly recompiling them.

To support names, I must abandon the ‘literal’ aspect of embedded literal objects.

Instead, I would align each object with an AO word. This word becomes a simple, stable identity for the object. AO words serve yet another role: module, function, Wikilon page, and now interactive object or applet. The Wikilon page for each of these objects might present itself as an interactive web application with web sockets to maintain updates. However, unlike general purpose web apps, these objects would be self-contained, purely functional, highly modular. It would generally be easy to peek under the hood to see the code, or to ‘clone’ an object by creating a new word with the same initial code. Stable (bookmarkable) views of the object might be represented with a few query parameters in a URL (enabling some server-side rendering), or a little information in the anchor.

We need logic to render these objects, to receive updates, to generate AO code, to trace errors.

The language word seems a fine place to specify this additional logic. Rather than a function that simply compiles text, the language function must accepts multiple methods, or alternatively constructs an object (based on an initial text) that can handle various update methods and pretty-print an updated version of the source in the end. (The latter could be a lot more efficient when processing lots of updates.)

I’m a bit wary because It’s difficult to structurally guarantee or prove useful properties for languages like: “pretty printing then reconstructing is observationally equivalent to the identity function”. Fortunately, Wikilon does make it feasible to test properties like this against historical definitions and updates, and various dynamic tests can be applied systematically (e.g. does `parse print parse print` result in the same printed content and AO behavior each time?). I believe we can achieve a reasonable degree of confidence in our DSLs and embedded objects.

There are still many details to hammer out, such as what is a good type for the language function. But I think extensible syntax will be worth pursuing, especially if I can support graphical languages and flexible editors.

Posted in Language Design | 4 Comments

VCache, an Acid-State Killer

Haskell has a convenient package called acid-state, which enables a Haskell value to be utilized as a database, essentially via the command pattern: updates are logged, and programmers can perform the occasional checkpoint; on restart, the checkpoint is loaded and updates are applied. In Haskell, treating the database as a value is convenient because it allows developers to build the domain model and operations upon it from pure functions, which are easy to reason about.

However, acid-state doesn’t scale nicely. Large checkpoints take a long time to load at startup. Large values in memory create a large burden for the Haskell garbage collector, which must occasionally perform a full sweep. Also, acid-state doesn’t compose very nicely. If you have two acid-state resources, there is no way to update both of them atomically. If you have some volatile storage for the particular process, you cannot easily keep it consistent with the acid-state resource.

Haskell has plenty of support for other databases, of course. So we can scale by switching to one of those. But this means accepting a lot of incidental complexity and semantic noise, giving up much simplicity from acid-state.

I want the simplicity of acid-state AND scalability. Oh, and composition would be nice, too.

To that end, I am currently developing VCache. The primary innovation of VCache is to support a clean separation of value references of kind VRef vs. persistent variables of kind PVar.

A VRef is a handle to an immutable value that is primarily represented in an auxiliary address space. Importantly:

  1. VRef’d values may contain VRefs, supporting tree structures and DAGs.
  2. Construction of a VRef and dereferencing values are pure computations.
  3. Dereferenced values are usually cached to reduce serialization overheads.
  4. VRefs are tracked via weak refs, and aren’t GC’d from the auxiliary space.

VRefs can represent very large domain models without overly burdening system memory. Note that these models don’t need to be persistent. Use of VRefs to create very large, volatile models may be useful for some applications, e.g. for the same reasons you might want a temporary filesystem. Volatile values arise naturally with lazy evaluation, optimistic concurrency, constraint solving search, and so on.

A PVar is a variable named by bytestring, and may be loaded from one execution to another. The content of a PVar is the same class of values as a VRef, and thus PVars can contain very large domain models – much larger than system memory – assuming developers structure them appropriately.

PVars are implemented as thin wrappers around STM TVars, and may be updated transactionally with other PVars and TVars (arbitrary STM operations may be lifted into a PVar transaction). The resulting transactions are atomic, consistent, isolated, and optionally durable. (Durability simply involves waiting for a synchronization after running the transaction.)

Supporting STM transactions together with persistent variables is very convenient for ensuring the volatile elements of the application are consistent with the persistent elements. The transactions also support composition and extension – i.e. it’s easy to add new persistent features without trying to modify a global datatype. Optimistic concurrency does come with a few weaknesses of its own, of course. Large transactions may ‘starve’ if small, fast transactions repeatedly manipulate variables used by the larger transaction. But I believe this concern is easy to address at the application layer, e.g. by constructing queues and cooperation patterns around the more contentious resources.

The VCache auxiliary address space is backed by LMDB. LMDB is a a read-optimized embedded key-value store that utilizes MVCC to ensure readers never wait on writers. LMDB is limited to one writer at a time… but, within that limit, it at least writes efficiently. Usefully, VCache mitigates LMDB’s few weaknesses. The Haskell STM layer easily supports concurrent read-write transactions. The VCache will amortize synchronization costs by combining transactions that occur around the same time. Lazy construction of VRefs may avoid some writes entirely.

The VCache garbage collector uses reference counting at the LMDB layer, and operates incrementally and concurrently in a background thread. As our LMDB file scales to gigabytes or terabytes or larger, we never need to sweep the whole thing. When the application is restarted, the garbage collector can eliminate values that were held only by volatile VRefs on the previous run. Usefully, LMDB covers the whole compaction issue as part of maintaining the underlying B-trees.

With regards to value caching, programmers will have some heuristic control over cache behavior on a per value basis, and the ability to roughly indicate roughly how much memory to use (albeit, based roughly on LMDB encoding rather than actual Haskell memory consumption). Values are also organized in VCache such that, at least for smaller values, structures allocated at around the same time will typically be on the same pages in LMDB. This allows effective use of smaller values.

VCache performs structure sharing at the VRef layer. This is useful because it saves space, because it may save some writes to disk, because it simplifies some forms of reasoning (e.g. about space costs for idempotent updates to a historical database), and because it allows comparisons of VRefs without loading the underlying values – e.g. such that we can efficiently perform a ‘diff’ on large trees that are mostly the same. When not used, the performance and space overhead should be is minor. I feel that structure sharing is one of those features that’s easiest to leverage when it’s pervasive.

My plan is to use VCache to support my Wikilon project.

Wikilon has an unusual ‘file’ system: files consist of bytecode and represent purely functional objects. That bytecode may contain values. But, for very large values – e.g. a tree map with a thousand elements – I’d rather avoid loading and parsing the bytecode to construct that value in memory. Instead, I’ll include a simple escape in the bytecode to access the value as a VRef. This allows me to preserve the O(lg(N)) updates or queries on the map, as opposed to the O(N) serialization costs for the full map. Further, that map could easily be part of a query response or function input. VCache will make it possible to treat persistent objects in a first-class manner.

VCache is not ready for use. And it won’t see much work over the next couple weeks (I’m on vacation). But I’ve hammered out most of the details, I’ve written the Haskell bindings to LMDB, and I’ve started implementation. I’m excited about this. I think, if you’re a Haskell developer or are interested in creating very large Haskell apps, that maybe you should be excited about it, too.

Posted in Concurrency, Modularity, State | 5 Comments

Wikilon Filesystem

Wikilon isn’t just an online dictionary for AO code. It will offer a simple filesystem-like abstraction, allowing use as a software platform for creating interesting applications and services. Simple isn’t easy. I’ve spent a great many hours designing, refining, and backtracking on the subject over the last ten days.

A few of the design points I find interesting:

  • Stateful files are replaced by purely functional objects, i.e. closures with fixpoint behavior. An unsophisticated purely functional object is `µO.[arg→(O*result)]`. I plan to use the same model as for embedded literal objects, which cleanly separates queries from updates. For example
  • Basic authorities aren’t just “read” and “write”, but also “update” and “query”. Read and write are still available, but operate at source level (reflection, direct manipulation), whereas update and query authorities use message passing and thus allow the object in question to protect its own invariants. This should simplify collaboration between software agents.
  • Usefully, state resources for RDP can essentially use the same model as state resources for imperative code, albeit with a small tweak: the update method takes a set of demands rather than a singular update message, and I must compute to a fixpoint.
  • Scripts can also be transparently used as resources, allowing ad-hoc adaptability and attenuation of the resource model. By ‘script’, I mean bytecode that is run when a query or update hits that resource, with the possibility of querying or updating other objects.
  • Updates are typically transactional (for imperative) or logically timed (for RDP) so this filesystem is a great deal easier to reason about than conventional filesystems, even with high levels of concurrency.
  • I’m making extensive use of logarithmic history. Users will be able to step back in time and briefly interact with historical snapshots. Even better, this will support retroactive testing, i.e. applying new tests on all available past states, and rather flexible debug modes where you can operate on past states.
  • Directory structure, relative to convention, is inverted. Every user has their own ‘root’, at least so far as they can tell. Public or shared directories might be mounted as subdirectories into each user’s workspace.
  • Directories have both internal ‘pet’ names, e.g. a file or directory named “bob”, and stable, opaque, external names based on, e.g. `HMAC(serverSecret,parent++"bob")`.
  • Capability secure. Capability strings provide authority to directories or objects, and may be attenuated and shared. In addition to an opaque GUID, each capability includes an authority code and an HMAC to guard the capability against forgery.
  • Simple tactic to mitigate supercalifragilisticexpialidociousID problem. See below.

The capabilities aspect has received much of my attention recently. I’ve determined that I can’t use ABC’s `[{tokens}]` because it creates aliasing problems for imperative code (resulting in race-conditions), and because it also muddles up cross-model queries between imperative transactions and RDP behaviors. Instead of tokens, I’m using strings together with a few annotations and sealers.

The capability strings look like `Mbdfghjkmnpqstxyz…` where `M` is an authority code, and the mess that follows is a bunch of base16 including GUID, HMAC, and potentially some path information. My goal is that this string should look exactly the same in your browser URL as within Wikilon.

Instead of permission flags, which allow invalid combinations, I’ll just use a short enumeration of valid codes: M: query+update, P: update, Q: query, R: read, S: read+update, T: read+write. (I’ve rejected write-only option as unwise, though it could be modeled indirectly via script. In most cases, what you’d really want is update-only.)

Unfortunately, a conventional representation of GUID+HMAC gets to be pretty bulky.

I’ve found a simple tactic to mitigate this: GUID and HMAC can overlap a fair amount so long as I expose enough of the GUID (e.g. 32 bits) to filter down candidates. I can then XOR the candidate GUID with the string to recover the HMAC, then test the HMAC. Thus, a 192 bit GUID plus a 160 bit HMAC could share a space. (I wouldn’t be surprised if other people have been using this idea since before I was born. But it’s the first time I’ve thought of it.)

A simple annotation like {&rsc} could greatly improve performance and ability to locate dead links in scripts or objects.

I’m still hammering out many details.

In addition to GUID and HMAC, I’m thinking I might want to keep some path information in some manner so as to support transitive revocations. One candidate mechanism is to list the first sixteen bits in each GUID in a path from root to the target GUID. If any of the elements on the path (most likely symbolic links) are disabled or now point elsewhere, we could disable the capability. Again, path information could partially overlap the GUID, and perhaps even a little with itself, while still supporting an efficient search. But it couldn’t overlap with the HMAC.

I’m also starting to think that acid-state isn’t going to scale (not with long logarithmic histories and goals like game development), and its interface doesn’t fit right for my use case. I’m now checking out TX, TCache, and Perdure. I’m hoping I won’t need to write my own.

Addendum: I speak more about the resource model on the captalk mailing list.

Posted in Language Design, Security, Stability | 4 Comments

Logarithmic History v3

Exponential decay, resulting in log-scale lists, an excellent way to work with an unbounded amount of history in a bounded amount of space. I’ve described this in two previous articles [1][2]. In my first article, I modeled logarithmic decay via a sequence of ring buffers: each ring would lose (or merge) one of its items rather than passing it forward. In my second article, I expressed a concern that ring buffers might lose information that occurs at a regular frequency, and modeled the decay probabilistically instead. The latter ‘improved’ form of exponential decay is certainly easier to implement, and could be generalized in interesting ways (such as time-based collapse). But original design had a nice property too. For example, it was extremely predictable.

In this article, I describe an even simpler model:

  1. Choose a maximum number of entries for your history buffer.
  2. Whenever you reach the maximum, decimate your history.
  3. To decimate: Take groups of ten entries. From each group, kill one.

Trivial, eh?

The word ‘decimate’ means to kill one man in every ten to punish or subdue a group. This results in a 90% survival rate. Repeatedly decimating our history will give us exponential decay. Operating on groups of ten keeps the operation simple, and ensures the decay process is relatively uniform and predictable. Of course, the particular choice of tenths is arbitrary and could be adjusted without loss of generality.

The decision, then, is how to choose one element from each group to destroy.

The probabilistic approach is to roll a ‘die!’.

The probabilistic approach can be deterministic in a simple way: use a hash function on each group of entries to roll a die for that group. This sort of technique would be convenient when working with replicated histories, distributed databases, and so on.

A non-probabilistic model might heuristically select one entry to erase based on estimated loss of information. For example, if we’re erasing camera frames, we might favor deleting a frame that looks most similar to another frame in the group. Or if our history consists of a path of a robot, we might favor deleting entries where the robot was basically sitting still or moving in a straight line.

Of course, merging is also a fine idea. We could choose two items to merge, ideally in an associative manner such that merge(a,merge(b,c)) = merge(merge(a,b),c); this can be done with weighted averages, keeping counts and sums and sums-of-squares, and generally developing a monoidal type for history entries.

I developed this particular approach to logarithmic history to support Wikilon. Logarithmic history offers a happy medium between keeping a complete history and keeping the most recent version of each page/word. It does have a few disadvantages. For example you can’t get a “permanent link” to a historical version of a word. But you can at least browse historical versions of the wiki/dictionary, get a story for how a system evolved, access old versions of ideas. And the long-term space requirements are very predictable.

Posted in Language Design | 2 Comments