Implementing a letrec alike in Ioke

Published 2011-08-20

So, some time ago I tried to demonstrate the Parser Combinator approach to parsing to a friend, with a simple JSON parser in Ioke. This parser would be built in two layers; a generic Parser object, with some basic combinators, and a JSONParser object with additional parsers for JSON. The simple parser was easy enough; lit, alt, seq, star, many1, wrapped etc were easy to define. Things became interesting when, for the JSON parser, I had definitions for list and dict which were mutually recursive. Theoretically, the with construct should enable this; as it turns out, it seems to only work when all of the mutually recursive functions do not depend on anything further up the chain of mimics, and even then not reliably. So, I let it rest.

Half a year later I took a short holiday, and as often happens decided that a spot of yak shaving was called for. What I wanted was something similar to letrec in Scheme; this was complicated by potential activateability, and the idea that a value might be a result of the activation of its definition; for example, many of the parsers are defined by combinators taking parsers as arguments, returning new parsers. The parsers must act as inactivateable to be easily passed as arguments, but the initial definition of the parser may depend upon activateability to produce the actual parser value. The methods in the literature did not seem to handle this; they either seem to need function definitions to be totally declarative and references to cells to be completely late bound, or for simple lambda wrapping to work. So, after assuring myself that I wasn't ignoring the literature, I proceeded to write some code. In Ioke it is acceptable to make use of gratuitous mutation; so I took a decidedly kludgy approach and had the values wrap themselves in a macro which, when activated, queried the environment to see whether they should be inactivateable, and either fake inactivateability if so, or else proceed to replace the contents of their cell with the result of the invocation of the evaluation of their stashed quoted definition, and then activate themselves. The result, after many iterations, was basically like the various lambda wrapping methods, with an added heuristic to deal with activateability and an implementation of quote-invoke-replace-invoke I haven't seen anywhere else¹. There are still several ways that this fails to give true simultaneous assignment; notably while the created object will respond to the appropriate message invocation to return/activate cells, the cells will both look different to introspection and not show up in some parts of the MOP (ie cellNames, cells) until they have been activated for the first time at the top level; also, anything that requires strictness due to side effects or dependence on transitory external state during the definition will obviously not work as intended without extra work wrapping the dependent state and forcing the computation.

Anyhow, here is the code I came up with:

DefaultBehavior FlowControl letrec = macro(
  newObject = @mimic 
  call arguments each(arg, 
    if(arg keyword?,
        Reflector other:cell(self, arg name asText [0..-2]) = (''(method(+a, +:b,
          ; Make inactivateable for the moment
          if(a empty? && b empty?, return @@)
          Reflector other:cell(self, "#{`(arg name asText [0..-2])}") = ''(`(arg next)) evaluateOn(self)
          Reflector other:send(self, "#{`(arg name asText [0..-2])}", * a, * b))) evaluateOn(self)), 
        Reflector other:send(newObject, arg)))
  newObject)

I would be interested to hear if there is a more idiomatic or less problematic way to do this in Ioke.

Home | Blog | Code