Awelon Progress Report V

Performance remains a priority.

At the beginning of this month, I reported some success with compiling the AO dictionary to Haskell ahead-of-time. However, after just a few days of using aoExec, I was feeling very sick of large up-front compilation times after tweaking the AO dictionary. Further, I realized I need some equivalence between `aoExec` and `aoi`, especially with respect to their powerblock and available effects, if testing in one is to carry over to the other.

On April 9th, I decided to discard `aoExec` and try a dynamic compiler based on Haskell’s plugins. Besides offering a more dynamic development environment, this approach should be much better than `aoExec` for metaprogramming.

I only required a few changes, but I (foolishly) decided to reorganize and rewrite most of the ao libraries. On the bright side, the rewrite netted significant (and rather unexpected) performance gains for my interpreter. The `bench.repeat100k` microbenchmark that before took 2.4s to interpret (and 0.4s when compiled), now takes 0.56s to interpret. The `ao test` that before took 1.38s, now takes 0.155s to interpret (though, it before took 0.012s when compiled into `aoTest`).

Dynamic compilation is now supported.

In AO, developers can use the annotation `{&compile}` to compile a block. The Haskell plugin is a module generated from the raw ABC code, and uniquely named based on a cryptographic hash of said ABC code. The type passed across the module boundary is `newtype Resource = Resource (forall m . (Runtime m, Monad m) ⇒ V m → m (V m))`, leveraging GHC’s Rank2Types extension.

This works. As in: it compiles, it links, it executes and returns correct results. Simple `$c]` tail calls are working fine. But:

  • It takes 0.8s to compile the identity function, and 1.86s to compile `bench.repeat100k`
  • Upon execution, the compiled form (for this microbnenchmark) is approximately 65% the speed of the interpreted bytecode.
  • Object code is never garbage collected after load.

Still, I’m optimistic! I can’t do much for the latency, but I could compile in parallel and hot-swap a block used in a loop, and perhaps avoid rebuilding code if it already exists. Due to a bug in GHC, I can’t fix the garbage collection before GHC 7.8.1 (I currently use 7.6.3, which ships with Ubuntu). But, when the time comes, I might be able to leverage System.Memory.Weak ephemeron tables or foreign pointers to address garbage collection. Most importantly, I can improve the generated code.

The Haskell code I generate is currently extremely simplistic and naive. For example, the bytecode `vrwlc` expands into:

{-# LANGUAGE NoImplicitPrelude #-}
module Rynms52btpb4zpgpwot32aqx2mzgkkxe4serh3c4tht3rcieaj4pjjbywahbe
    (resource) where
import ABC.Imperative.Operations
import ABC.Imperative.Resource
import Control.Monad

resource :: Resource
resource = Resource (v>=>r>=>w>=>l>=>c)

I have a big list of ways to improve the generated code, e.g. by building a Haskell expression rather than directly composing operations I could reduce this to `resource = Resource $ \ (P a b) -> return (P b a)`. I suspect I can achieve an order of magnitude improvement for sophisticated programs. Additionally, with a little partial evaluation, I should be able to directly recognize fixpoint cycles and model loops in forms GHC can effectively work. If an ABC program is highly repetitive (large common subprograms) then it might also be useful to recognize these and reuse them to reduce memory footprint.

I’ll be giving these improvements a try over the next couple weeks.

Leaping to Awelon Project’s process model

I’ve spent a lot of time this month thinking about process models. In the last report, I mentioned, “I’ll need to develop the `aoExec` powerblock a fair bit to perform useful side-effects”. Initially, I was laboring under an assumption that I’d pursue a fully imperative approach to get started, then go about implementing Awelon project’s model (a toplevel ABC stream that manipulates a ‘live’ RDP program). However, imperative processes are an awkward fit for AO’s constraints (spatial idempotence, causal commutativity, progress, etc.). I can model imperative processes if I’m willing to sacrifice causal commutativity, or accept lockstep concurrency, or implement a time-warp system. But I’m not willing to do the first two, and the last is even more sophisticated than RDP.

My decision is to move forward with the Awelon project model, albeit tweaked slightly: we’ll still manipulate a representation of an RDP program, but the act of ‘installing’ the RDP behavior will be an explicit imperative action (albeit, an idempotent and commutative action). This risks one of my design principles: that “ALL long-running behaviors and policies should have corresponding state in the environment.” However, it also allows much greater precision for how we interpret the RDP program, how much we recompute, and eliminates risk of trying to interpret invalid intermediate states. Presumably, some environments might couple these update actions more tightly to avoid behaviors falling out of synch with their representations. But, for now, that will be left to discipline.

Ultimately, both `ao exec` and `aoi` can use this same model. They already receive the same toplevel stream of AO or ABC. I haven’t even started implementing the RDP interpretation of ABC, since I’m still focused on performance in the imperative layer. Fortunately, I don’t expect any special challenge: Sirea was already a prototype for this sort of development.

Overall, I think this change is moving my timeline in a nice direction: I won’t be detouring through imperative process models or development of associated words and idioms. I’ll get more practice implementing RDP for when I fully bootstrap.

Miscellaneous

  1. The `>` ABC operator is now monomorphic, operating only on numbers. This change was suggested to me because `>` was the only remaining polymorphic operator that requires type information in simplistic implementations of ABC.
  2. The list type from `µL.(1+(a*L))` to `µL.((a*L)+1)`, mostly because operator `V` makes it a lot easier to add elements on the left than on the right (fewer operators for ‘cons’). This change had a pretty small impact, only required tweaking a few list processing words.
  3. New utility `ao exec` offers a similar role to the now defunct `aoExec`. Though `ao exec` is more convenient because it receives an ad-hoc AO command.
  4. New utility `ao exec.s` can receive a stream of AO via standard input. It’s basically the non-interactive `aoi`.
  5. New utility `ao exec.abc` can receive raw ABC code as a command. And `ao exec.abc.s` can receive ABC via standard input.
  6. New utility `ao jit` outputs the Haskell code that will be generated for dynamic compilation of a given program.
  7. New utilities `ao list`, `ao defs`, `ao uses`, and `ao def` are useful for studying the AO dictionary without the text editor.
  8. The old `ao type` utility is currently disabled and needs rewritten. I have new ideas for it anyway.

(Aside: I’m thinking to implement some command-line refactoring utilities, e.g. to rename words or update definitions.)

It has been a productive month. I’ve spent most of it ‘in the flow’. However, there wasn’t much development of new AO code.

What’s Next?

Performance is the top priority for me. I don’t want AO to remain a ‘toy’ language for another six months. I’ll be spending the next couple weeks aiming to improve the generated Haskell code. I imagine I’ll be content, if not happy, to achieve an order of magnitude improvement for loopy programs.

Beyond that, I’m interested in developing a more sophisticated static type inference – i.e. to properly detect structural fixpoint (µ) types, and track correctness under multiple sets of assumptions, and perhaps determine a conservative set of ‘gatekeeper’ safety predicates upon entry to a subprogram. I also have some ideas on how to develop `type.` and `typeOf.` words in AO for automatic testing and documentation purposes. (It’d be nice to assert that certain arguments are polymorphic, or to develop something like QuickCheck based on type descriptors.)

And, of course, I need to develop the RDP interpretation of ABC.

I don’t have a solid timeline for all this, but my best guess would be: two more weeks on performance, two weeks on AO type inference, then get back to RDP integration in June (after which time I’ll be able to try some long-running applications). I’d like to also develop the dictionary some, but I don’t have much hope of getting back to it this month.

Time is flying! Hopefully, by October, I’ll be ready to implement real programs (e.g. video games, web servers) and use this technology in real practice.

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

2 Responses to Awelon Progress Report V

  1. rolyp says:

    When you wrote `µL.(1+(a*L))` to `µL.((a*L)+1)` the text which followed made me wonder whether you meant `µL.(1+(a*L))` to `µL.(1+(L*a))`. (I.e. `cons` to `snoc`.) But assuming you meant what you wrote, why is it more convenient to inject into the left component of a sum?

    On the subject of fixed points, are you planning to support data types too, or only anonymous recursive types? Or is that something you might implement on top of your core language?

    • dmbarbour says:

      It’s a consequence of bytecode minimalism: operator `V :: (a*e)→((a+0)*e)` puts values in the left. To put something in the right requires `VVRWLC` (where `VRWLC` encodes a ‘mirror’ operation `((a+b)*e)→((b+a)*e)`). Ultimately, the difference is minor, but I figure lists and streams will be common enough to deserve the low level attention.

      At the ABC (Awelon bytecode) layer, types are always structural and anonymous. AO is designed to be a shallow macro-language for ABC (a trivial ‘full abstraction’).

      However, use of value sealing can model abstract data types. AO does allow hard-coding of sealers and unsealers – e.g. `{:foo}` would seal a value with token `foo`, and `{.foo}` would unseal said value. Hard-coded sealers aren’t very secure, but they serve the job of newtype declarations quite well (preventing some type accidents). And they can be secured against foreign code at runtime (e.g. `{:$foo}` indicates it should be rewritten, e.g. using HMAC based on the connection receiving it).

      (If you meant to ask about ‘data types’ rather than their abstract variant, ABC does support rational numbers as its only interesting low-level data type, and inline text is shorthand for a list of integral numbers between 0 and 1114111.)

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s