Wednesday, September 19, 2012

Saturday, September 8, 2012

Having both fexprs and macros

Lexically-scoped fexprs and first-class environments make it simple to do hygienic metaprogramming, using less machinery than hygienic macro systems, and they also require less concepts in the language: there is no need to specify a preprocessing phase.

The downside is that fexprs always incur an interpretative overhead with current technology. Many are convinced that those fexprs that do similar things to what macros do can be partially evaluated: "my research in static analysis leads me to believe that we will be able to erase that overhead for the common case--where first-class macros are used to do the job of compile-time macros" writes Matt Might, for example.

In my new language, Wat, I've implemented both fexprs and macros. Macros are expanded at runtime, when they are first encountered, and their result is memoized in the syntax tree, a technique described in two interesting articles (1, 2) related to the SCM Scheme implementation.

In Wat, MACRO is a special form that can be wrapped around a combiner, and causes calls to that combiner to be memoized in the source tree. An example, LET:

(def let
  (macro (vau (bindings . body) #ign
           (cons (list* lambda (map car bindings) body)
                 (map cadr bindings)))))

With a bit of sugar, one can write macros that look almost like in Common Lisp:

(define-macro (until test . body)
  (list* while (list not test) body))

Macros complicate the language quite a bit; but used in moderation, especially for forms like LET that are basically never changed nor used in a higher-order fashion, they should be unproblematic, and offer a nice speed boost. Fexprs should be used for more complex tasks that require special attention to hygiene, or need to do things that macros can't do, whereas macros could be used for simple transformation and processing tasks, such as UNTIL, above.

Oh, and it should also be noted that these macros enjoy a nice level of hygiene already, by virtue of first-class environments and first-class combiners. For example, UNTIL above doesn't insert the symbols WHILE or NOT into the generated code - it inserts the actual values, therefore being protected from variable shadowing by calling code.

Thursday, September 6, 2012

Mixing first-order and higher-order control

It's desirable for a language to support exceptions (preferably restartable ones), unwind protectiondynamic binding, and delimited continuations. [Adding Delimited and Composable Control to a Production Programming Environment, Delimited Dynamic Binding]

I've found a tractable way to implement these features in the language I'm currently working on, Wat.

My approach is to totally separate first-order control from higher-order control.

There is a set of Common Lisp-like first-order forms:
These forms are implemented natively using JS try/catch and finally.

Restartable exceptions are implemented in terms of these first-order forms and dynamically-bound variables, which are also provided natively.

In addition there's a completely separate set of higher-order control forms from A Monadic Framework for Delimited Continuations.

Delimited continuations are implemented using a technique similar to Exceptional Continuations: ordinary code paths run on the normal JS stack; when a continuation is captured, the stack is unwound frame by frame up to the prompt, and at each frame, a resumption is added to the continuation that is built up during the unwinding. This technique is ten times faster than a naive scheme with heap-allocated stack frames, but currently doesn't support TCO.

First-order control is used for quotidian control flow, whereas higher-order control is used for heavy control flow lifting, such as making a REPL written in direct style work in the browser's asynchronous environment.

This is a quite intuitive model: in the small, one has the usual Common Lisp control flow, including restartable exceptions, whereas in the large, behind the scenes, control flow may be arbitrarily abstracted and composed with the higher-order control forms.

Wednesday, September 5, 2012

Reactive Demand Programming

David Barbour has created a very promising and exciting paradigm for writing interactive, networked applications: Reactive Demand Programming (RDP).

RDP is very sophisticated and I can't really do it justice here, but its salient points are:
  • An RDP application is a dynamically-changing set of semi-permanent, bidirectional data exchanges, called behaviors. What pipes are to Unix, behaviors are to RDP.
  • A signal is a monodirectional channel carrying a value, and varies discretely over time.
  • A behavior is made up of one or more input signals, called demands, and a single output signal.
  • RDP builds in the notion of anticipation - every signal update comes with the expected duration the new value is valid. This allows low latency through smart scheduling.
  • [Update: See David's corrections in the comments.]
An example for a behavior would be a camera receiving move and zoom commands (or rather demands) with discrete time intervals (e.g. as long as a user moves the camera joystick) from one or more users on input signals, interpolating these commands using some deterministic decision procedure (such as averaging all commands), and outputting camera frames on the output signal, with the anticipation measure telling clients something about the rate at which the camera refreshes, allowing them to smartly perform display reprocessing.

The best way to get started is the README of David's RDP implementation. David has also just posted a progress report on his blog, which contains many articles on RDP.

I think RDP is one of the most exciting developments in interactive application development and is worth checking out.