marius a. eriksen

Implementing python style generators with delimited continuations

2010-09-12T00:00:00-07:00

Jake’s article on implementing LWT-compatible fibers with Oleg’s delimited continuation library got me thinking about one of my favorite Python features: generators.

Delimited continuations

Delimited continuations have a very simple API (note: I’m going to consider only the high level API provided by delimcc here consistent with the abstract view of delimited continuations. Jake describes the low-level API in his article). The core API is:

val new_prompt   : unit -> 'a prompt
val push_prompt  : 'a prompt -> (unit -> 'a) -> 'a
val shift0       : 'a prompt -> (('b -> 'a) -> 'a) -> 'b

new_prompt simply creates the “handle”, push_prompt (traditionally called reset) sets the limit of the continuation (how far up the stack we will go), shift0 captures the continuation and gives it to the passed function. Crucially, the continuation captured by shift0 is delimited by the outer push_prompt. The “region” of the continuation delimited by push_prompt and shift0 consists of the stack frames between the two (this also means you cannot call shift0 anywhere outside the scope of push_prompt).

An example should clarify. Let’s first do something illegal.

# open Delimcc;;
# let p = new_prompt ();;
value p : Delimcc.prompt '_a = <abstr>
# push_prompt p identity;;
- : unit = ()
# shift0 p (fun k -> k ());;
Exception: Failure "No prompt was set".

Here, we tried to shift0 outside of the push_prompt. Nope, can’t do that.

# push_prompt p (fun () -> shift0 p (fun k -> k 123));;
- : int = 123

Here, the inner function (passed to shift0) was given the captured continuation k (as delimited by push_prompt), calling it with the argument 123 which was subsequently returned.

The neat thing about delimited continuations is that they capture the state entire delimited stack. That is, calling k ARG from within shift0 is equivalent to replacing the shift0 statement with ARG, returning the result of push_prompt. Furthermore, it’s a first class continuation, so we may use it multiple times. To wit:

# push_prompt p (fun () -> 10 * shift0 p (fun k -> k 1 + k 3));;
- : int = 40

Here, k is equivalent to the function ( * ) 10. The argument & return types needn’t be uniform:

# push_prompt p (fun () -> string_of_int (shift0 p (fun k ->  "hey " ^ k 123)));;
- : string = "hey 123"

Leaking continuations

What makes delimited continuations yet more interesting is that the continuations themselves can escape the scope of shift0, and be restarted from outside.

Because of the type signatures of shift0, we need to unify the types, so let’s first define an ADT to do so:

# type t = Done | More of (unit -> t);;

Note that we can’t just use option here, it seems, because we need a recursive type.

# let count = ref 0;;
# let More k = push_prompt p (fun () -> 
  while true do 
    count := !count + 1; 
    shift0 p (fun k -> More k)
  done; 
  Done);;

Here we are using our unified type trick to return the continuation itself (note how push_prompt and shift have the same return type). Let’s play!

# !count;;
- : int = 1
# k ();;
- : t = More <fun>
# k ();;
- : t = More <fun>
# !count;;
- : int = 3

Generators

We now have a pretty good idea of what’s needed to implement generators with an API similar to:

let producer () =
  let state = ... in
  gen begin fun yield ->
    yield state; ...; yield state; ...; yield state
  end

So we need a function gen that takes a “yielder” (in Python terminology) that needs to capture the continuation, communicate the value and resume execution when the next value is asked for by the consumer:

let consumer () = 
  let g = producer () in
  let v0 = g () in
  ...
  let vN = g ()

It turns out that this is a very natural fit, and we can implement full duplex generators in just a few lines, using the ideas developed above. Here is the full source code:

type ('a, 'b) t = Done | More of 'a * ('b -> ('a, 'b) t)

let gen f =
  (*
   * Note: the first value to yield gets thrown away as the generator
   * has not yet started.
   *)
  let start _ =
    let p = Delimcc.new_prompt () in
    Delimcc.push_prompt p begin fun () ->
      f (fun x -> Delimcc.shift0 p (fun k -> More (x, k))); Done
    end in
  let next = ref start in

  fun rv ->
    match !next rv with
      | More (x, k) -> next := k; Some x
      | Done        -> None

And sample use:

let rec take_all t count =
  match t count with
    | Some i -> printf "took: %d\n" i; take_all t (count + 1)
    | None   -> ()

let () =
  let take = gen begin fun yield ->
    for i = 0 to 10 do
      let rv = yield i in
      printf "got: %d\n" rv
    done
  end in
  take_all take 100

The only additional work we have to do is to type it for bi-directional communication, and to store the next continuation in a ref cell for the next invocation. Given that the generators developed here are full duplex, we can implement co-routines as outlined in PEP 342.

You can also get it as a gist here. I also highly recommend Jake’s article which explores delimcc from a lower level of abstraction.

Self-contained emacs

2010-02-21T00:00:00-08:00

One annoying thing about using emacs on remote systems is the absence of your own initialization & configuration code. It’s of course possible to push your own, but often it’s annoying. Configuration often gets rather involved: my own .emacs.d directory contains many packages and libraries that are not shipped with standard emacs distributions. Another common scenario is that you use shared accounts, making editor configurations rather intrusive.

So, I sought to simplify the situation.

make-emacs creates for you a simple, self-contained and relocatable script that allows you to invoke emacs with your own configuration anywhere. For example:

    $ make-emacs ~/.emacs.d /tmp/e
    $ scp /tmp/e remoteserver:
    $ ssh remoteserver
    $ ./e MYFILE
    extracting emacs.d..
    <emacs bliss>

It uses shar to create a self-extracting archive and wraps that extraction code to invoke emacs properly. It also caches the extracted configuration files, so that it only has to perform a potentially costly shar extraction once.

Get it on GitHub here.

Emacs as a tiling window manager

2010-01-26T00:00:00-08:00

I’ve been using emacs in in full-screen mode lately. It provides a nice, distraction-free environment. If you’re using carbon emacs it’s quite easy:

(defun mac-toggle-max-window ()
  (interactive)
  (set-frame-parameter nil 'fullscreen
                       (if (frame-parameter nil 'fullscreen)
                           nil
                         'fullboth)))
(global-set-key (kbd "<C-M-return>") 'mac-toggle-max-window)

I also really enjoy the efficacy of navigation provided by tiling window managers such as xmonad. So, why not make emacs behave like it?

emacsd-tile.el is a really tiny configuration snippet to provide just this.

It provides xmonad-inspired keyboard shortcuts:

`M-{j,k,h,l}`	→	move to window (down, up, left, right)
`M-S-{j,k,h,l}`	→	enlarge/shrink horizontally/vertically
`M-C-{j,k,h,l}`	→	swap with (down, up, left, right)

This mostly uses just stuff that was already in emacs! The only part I had to implement myself was window swapping.

Another really handy feature of emacs is the ability to save window configuration in registers. With this, you can “stash” away an entire window configuration and recall it later.

Here’s a screenshot, though it’s not really descriptive because it doesn’t show the keybindings in action, but it may convince you that emacs can at least look like a tiling window manager :-)

Any other improvements or suggestions?

Beautiful fixed-width fonts for OSX

2010-01-10T00:00:00-08:00

(Or, “an ode to 9x15”)

I’ve always had great appreciation for the fixed-width fonts distributed with X11 (”misc-fixed-*”): 6x13, 7x14, and especially 9x15 (my all-time favorite).

I never really found any type so satisfying. It is extremely crisp and legible, is not dull, and doesn’t go all fuzzy in its bold variant. Its glyphs are extraordinarily well-suited to the kinds of strange things we tend to do with the ASCII character set in code.

Charlie Cheever previously converted 9x15 to an OSX dfont, so I followed suit to fill in with the rest of the sizes using FontForge.

http://monkey.org/~marius/x11-misc-fixed.tar.gz

Included are 6x13, 7x14, 9x15 and 10x20. Make sure to use them only with their respective sizes (ie. 13pt for 6x13, 15pt for 9x15 and so on) and without anti aliasing turned on (bolds won’t render correctly).

Enjoy!

Regarding the case against Christopher Thompson

2009-11-17T00:00:00-08:00

This is a letter sent to the District Attorney in L.A. More information here.

Greetings,

I am an avid bicyclist and I think that it is imperative that Christopher Thompson is brought to justice with a penalty fitting the crime he has been convicted of.

Bicyclists are inherently disadvantaged by size and available protection while riding on public roads. It is dangerous enough while drivers are following the rules. With malicious intent however, the driver is undoubtedly in possession of a very deadly weapon indeed. I believe it is vital for motorists to understand this. By deviating from rule or protocol, the driver has at his hands the capacity to kill. With the addition of malicious intent, the driver almost certainly will.

The life of the cyclist is at the hands of the motorists around her. Please set the proper precedent by ensuring that Christopher Thompson is penalized to the fullest extent. This is only in proportion to his wildly irresponsible behavior.

Marius Eriksen of San Francisco, CA.

Haskell is beautiful in practice

2009-11-05T00:00:00-08:00

I’ve been writing a bit of Haskell lately (see my GitHub page), and it’s an absolutely beautiful experience. And I mean that in every way: The language itself of course, but also the community, the documentation, the package system and the Haskell platform ultimately help make the practice of writing Haskell more pleasing than any other I’ve had any experience with.

I find that Haskell lets me translate so many ideas and abstractions naturally and without the fuzz of too much indirection. My hope is to give you a small taste of what I’m talking about. Please note that this is going to contain some deliberate (but mostly inconsequential) inaccuracies and I will also leave out details here and there. A lot of the code is also “paraphrased” to highlight the ideas behind it.

I recently wrote an implementation of BERT in Haskell (github). I had the need for an RPC mechanism, and it seemed to fit my requirements rather well. “BERTs” are a subset of Erlang terms, which are composable and have a straightforward external representation (albeit not as space efficient as something like Google’s protocol buffers). So I figured this might be a good starting point for demonstrating some of the substantial ways in which Haskell provides facilities to create programs that are not only succinct but also readable and robust. At the same time, I hope to convince you that Haskell provides the kind of abstraction & encapsulation that is often much more natural than other approaches.

Types

We need to be able to represent BERT terms in Haskell. Thus we introduce an algebraic type representing a Term (github).

-- | A single BERT term.
data Term
  -- Simple (erlang) terms:
  = IntTerm        Int
  | FloatTerm      Float
  | AtomTerm       String
  | TupleTerm      [Term]
  | BytelistTerm   ByteString
  | ListTerm       [Term]
  | BinaryTerm     ByteString
  | BigintTerm     Integer
  | BigbigintTerm  Integer

This is pretty straightforward to read: a Term can be either an IntTerm, a FloatTerm and so forth. The right column specifies the data for the type. The IntTerm carries an integer, etc. An important detail here is that these are not different types: they are all type constructors for the type Term. That is, these are different ways to create a Term type. Algebraic types may also be recursively defined. The ListTerm constructor represents a list of other Terms. Already with this simple declaration, we’ve expressed most of the semantics of BERT terms. We can now express composite BERT terms. For example BERT defines dictionaries to be represented as {bert, dict, [{key, value}]. In Haskell:

TupleTerm [ AtomTerm "bert", AtomTerm "dict"
          , ListTerm [TupleTerm [AtomTerm "key", AtomTerm "value"]]]

Typeclasses

Terms encapsulate the BERT type representation, and we will write code that can encode Term values to a binary representation (as per the BERT spec). However, these values are not the most convenient to work with in other Haskell code. Furthermore, many Terms have a natural “more primitive” Haskell type (eg. IntTerm vs. Int, ListTerm vs. []).

We would like to introduce Terms from these types and vice-versa. The most primitive way to do this is via pattern matching (this is ubiquitous in Haskell and other functional programming languages. Also see my poor attempt at implementing pattern matching in Python).

listify (ListTerm l)      = listify' l
listify' []               = []
listify' ((IntTerm x):xs) = x:listify' xs

This code introduces a list of integers ([Int]) from a ListTerm containing IntTerms. Clearly going around creating little unpackers like this for everything is going to be quite cumbersome. Haskell provides a very nice solution. Typeclasses let you declare common traits to a set of types. For example, I can define a typeclass that declares the ability to translate a value of that a given type into or out of a Term (github).

class BERT a where
  -- | Introduce a 'Term' from a Haskell value.
  showBERT :: a -> Term
  -- | Introduce a Haskell value from a 'Term'.
  readBERT :: Term -> a

This introduces two new functions. One to create a term from a Haskell value, and one to do the inverse. So what kinds of types can introduce Haskell values from BERT or vice-versa? A few are quite simple. The most trivial is for Term itself.

instance BERT Term where
  showBERT = id
  readBERT = id

To convert a Term to a Term is just the identity function. We need to cover a few more primitive Haskell types. The BERT definition for lists is:

instance (BERT a) => BERT [a] where
  showBERT xs            = ListTerm (map showBERT xs)
  readBERT (ListTerm xs) = map readBERT xs
  readBERT _             = error "Invalid list type"

Unlike Haskell lists, BERT lists can be heterogeneous: they are lists of Terms which, being an algebraic type, may eventually contain different types of data. Thus, to introduce a BERT list, we return a ListTerm that applies showBERT to every element in the list. This also explains the typeclass restriction on a: we require that the list we are encoding contains a type that also has a typeclass instance of BERT. Similarly, to decode a list, we call readBERT on each element, introducing a list with the decoded Haskell types. But what about the other way? Certainly we couldn’t introduce a Haskell list from a heterogeneous BERT list. The code above looks deceiving in this way, but type inference is going on in the background here. The type of readBERT is Term -> [a]. This inference is propagated when we pass readBERT to map as well; it’s equivalent to the following code:

  readBERT :: Term -> [a]
  readBERT (ListTerm xs) = map (readBERT :: Term -> a) xs

Note that you can also create your own typeclass instances that suits your needs. For example if your application keeps some internal representation of some well defined value, you could create a typeclass instance to convert this representation to and from Terms.

Lazyness

The RPC specification for BERT provides a rather opaque notion of a transport. The transport, in essence, is a channel through which you can send and receive BERT terms. The terms are wrapped in a 4-byte header specifying its length.

Haskell has a Handle type that is an opaque representation of a file-like object. Sockets can also be fronted by handles. A popular module, Data.ByteString provides a lazy bytestring type that can be backed by a handle. It’s a type that looks like a bytestring, smells like a bytestring, and acts like a bytestring, except that when it needs more data, it requests it from the handle it’s been constructed with. Similarly, our binary term decoder reads from such bytestrings, so it does not take much imagination to produce a list that represents the infinite stream of packets coming from the BERT peer (github).

packets :: ByteString -> [Packet]
packets b
  | null b = []
  | otherwise = p:packets b' 
  where (p, b') = parsePacket b

(In Haskell, : is the list constructor: it prepends an item to a list, eg. 1:[2,3] == [1,2,3].) packets reads like a declaration: if our bytestring, b is null, it is the empty list, otherwise, it is the first parsed packet from b, plus the list of packets represented by the remainder of the string. This works in Haskell because everything is evaluated lazily. This in effect means that, unless you specify otherwise, values are not computed (code is not evaluated) until needed. In practice, the Haskell runtime leaves a “promise” of a computation when the value is not needed immediately. The list constructor : is no different: its arguments are not evaluated until needed. In our example this means that the list defined by packets is lazily generated. So if we create such a value with packet b, not until we examine the resulting list do we even begin parsing (or generating the list, or reading from the socket). This is an example by which we use lazyness to provide an abstraction. It allows us to operate on the familiar list type while not being terribly concerned about how the list is being constructed. It also relieves us of having to create any further abstraction: we can translate our model of a transport almost perfectly into a primitive Haskell concept without having to go about creating unfamiliar interfaces.

Monadic parsing

We created an algebraic type to represent terms, but their construction (if you need to work with the term type) can be a little cumbersome. Our representation

TupleTerm [ AtomTerm "bert", AtomTerm "dict"
          , ListTerm [TupleTerm [AtomTerm "key", AtomTerm "value"]]]

would be represented more succinctly in the erlang grammar as:

{bert, dict, [(key, value)]}

If just writing code, you probably don’t care too much about the difference: you typically don’t make big static constructs, but rather create types programmatically anyway. However, with the BERT implementation I wanted to have a command line tool that allowed for testing & inspection of results. For example:

$ bert call localhost:8181 mod proc "{1, test, [5,6,7]}"

Luckily, Haskell provides an excellent facility for parsing: Parsec. Parsec uses monadic actions to simultaneously lex & parse its input. I won’t go into monads here, but for our purposes here it is essentially a means by which you can run code in a certain context, and manipulate that context. It can provide a pure functional construct with which you can achieve the appearance of imperative programming. In the context of Parsec, its monad maintains the parser state (eg. where in the input are we, which rules have failed, which rules are yet to be tried, what is the output, etc.), and provides a set of functions that can operate within the context of the monad it provides. Here’s our parser for a term.

p_term :: Parser Term
p_term = t <* spaces    
  where 
    t =     IntTerm               <$> p_num (readSigned readDec)
        <|> FloatTerm             <$> p_num (readSigned readFloat)
        <|> AtomTerm              <$> p_atom
        <|> TupleTerm             <$> p_tuple
        <|> BytelistTerm . C.pack <$> p_string
        <|> ListTerm              <$> p_list
        <|> BinaryTerm   . B.pack <$> p_binary

Again, reading very naturally: a term is t possibly followed by some whitespace. (a <* b means roughly “run a, then b, but the value of the expression is the value of a”). t in turn can be either a p_num wrapped with an IntTerm, and so forth. (In this context, <|> can very roughly be thought of as “otherwise, try..” and <$> as “wrap the results of the argument to the right with the thing on the left”.)

The various p_*s are other parsers. For example the one for tuples is

p_tuple =
  between (char '{' >> spaces) (spaces >> char '}') $
    p_term `sepBy` (spaces >> char ',' >> spaces)

between is one of the Parsec functions that means: between the parses of the following arguments, try to parse the third. The third argument states: “try and parse a p_term that is separated by maybe some whitespace, a comma and maybe some more whitespace.”

…

This is really just the tip of the ice berg. Most of my descriptions, especially those regarding the use of monads belie the rigor and generality of these constructs. If you’d like to explore further, the Real World Haskell book is a great start point. The Haskell community is simply fantastic. Much conversation happens on IRC, where there is typically an armada of people just waiting to discuss the finer points of this wonderful language with you.

Pattern matching in Python

2009-05-11T00:00:00-07:00

One of my favorite things about various functional programming languages is pattern matching. It often allows for very succinct and elegant declarative expressions, and in the dynamic variants it allows for easy in-line lightweight type checking.

So, naturally I wanted the same in Python, the programming language we use at work.

Pattern matching is most powerful when it enjoys first-class support in a language. In addition to succinct syntax, this affords you the ability to integrate pattern matchers with control constructs, allowing conditional execution of code based on various patterns. It also may give you a degree of composability not possible otherwise. For example, Erlang has not only a case statement, but allows for clauses in functions, so that pattern matching is done on the arguments of functions with the same name and arity. For instance in Erlang, you could implement a simple REST-style HTTP request handlers like so:

%% handle(Path, Method)
handle("/", _) ->
  not_a_resource;
handle(Path, 'PUT') ->
  create_new_resource(Path);
handle(Path, 'POST') ->
  update_resource(Path);
handle(Path, 'GET') ->
  retrieve_resource(Path);
handle(_, _) ->
  invalid_request.

Now I can simply call handle(Path, Method) to deal with my request. Notice also how powerful ordering is here: I exclude the resource "/" entirely by matching on it first. Note also that some arguments here are binding, while others are not. For example in the first clause, nothing is bound, in the second, we bind Path if the method matches 'PUT'.

How do we graft something like this onto a language like Python? It’s especially tricky because we’d like to maintain the ever elusive “Pythonics.” While I’m quite sure Guido would never even touch this stuff, we can at least maintain the spirit! Start off by importing the match primitives:

>>> from match import M, A, A_

M creates a destructuring match expression (a “matcher”), A is the a binding argument, and A_ is the “any” argument. Any A arguments need to have a positional specifier. This is achieved with the division operator. So A/0 names the first value in the returned destructured tuple. With the help of a few operators, we compose a match expression:

>>> M((1, (A_, 3), A/1, A/0))
<match.M object at 0x726f0>

So, these expressions are entirely useless until they are bound. The == operator takes care of that:

>>> M((1, (A_, 3), A/1, A/0)) == (1, (2, 3), 1, 2)
(2, 1)

If you precede the match-expression with the ~ operator, the expression becomes a “pure” matching expression, and does not destructure the second operand, it just returns True or False depending on whether it matched successfully.

>>> ~M((1, (A_, 3), A/1, A/0)) == (1, (2, 3), 1, 2)
True

Now, to make things more interesting, match-expressions can be or-ed together, resulting in the first successful match. For example M([A/0]) | M(A/0) doesn’t care whether the value is a list of length 1 or a literal.

>>> M([A/0]) | M(A/0) == [5]
5
>>> M([A/0]) | M(A/0) == 5
5

Finally, matchers can specify “default” values to be returned they match successfully. This is to help deal with polymorphic return values. For example, the following expression:

>>> M([A/0]) | M([], d=False) == arr[:1]

picks the first element if arr is nonempty, otherwise it returns False.

I’ve put the code up on GitHub. I’m not super happy with the aesthetics of it but it’s interesting to experiment with. Among other things, it definitely needs list and dictionary destructuring.