Modules, Multimethods (Kinda), and More for Arc

I’ve been doing things here or there in Arc without really having a specific plan in mind for sharing them. Most notably, I had the fundamentals of an untested Arc multimethod system laying around, which were made in an effort to collect my thoughts about Blade, a potential idea for an everything-is-a-multimethod language. And that’s what I expect a large part of my projects to be: Approximations of a language I’d rather program in. So finally, last week I started up a GitHub repo, Lathe, where I could submit miscellaneous utilities that smoothed out non-Blade languages according to my own aesthetic.

That Arc multimethod system is one of those utilities, but first…

Modules

I’m not very bold when it comes to polluting the global namespace, and that’s discouraged me from releasing any Arc code. Even if I pick names no one else does, I’m still limiting my own ability to give those same names different meanings in the future. If I use any specific global names, then multiple versions of my code will not be able to coexist in the same application, and that bugs me.

So that I could avoid this trouble, the first thing I contributed to Lathe was a module system. I have a few basic goals in mind for this system, which I’ve so far achieved:

  • Hiding code is okay but not Arclike. An Arc module system should free code from accidental naming conflicts, not protect it from intentional ones.
  • One library should be able to declare a dependency on another library without specifying how to satisfy that dependency. For example, two libraries should be able to depend on a third library without that third library being loaded (or downloaded, compiled, etc.) twice.
  • Even if it isn’t possible to treat existing Arc libraries as modules, code written for the module system should be easy to rewrite in a more traditional way. I’m sharing Arc hacks, not committing people to a framework.
  • Some Arc code may rely on modifications to the Arc implementation, but the module system itself should not. For instance, none of my code currently drops to Scheme; in fact, it works just as well on Rainbow as it does on Arc and Anarki.

Another basic property I’d like to fulfill in this module system is the ability for multiple libraries to depend on each other, which can be useful when a big project needs to be split up into more manageable chunks. I have a plan in mind for this, but I’m going to put off this plan until I work a bit more on multimethods, especially since multimethods and module systems might influence each other in subtle ways.

Here’s an example of the module system in action (which may also give you a bit of insight into the multimethod system):

; multirule.arc

(packed:using-rels-as mt "multival.arc"
                      oc "order-contribs.arc"
                      ru "../rules.arc"

; A basic-rulebook-reducer multival takes contributions that are rules
; (which are extracted here from the 'val entries of contribution
; detail tables), it sorts those contributions using order-contribs,
; and it ultimately becomes a function that calls those sorted rules
; as a basic rulebook.
(def my.basic-rulebook-reducer (contribs)
  (let rulebook (map !val (apply join oc.order-contribs.contribs))
    (obj val (fn args
               (apply ru.call-basic-rulebook rulebook args))
         cares `(,oc!order-contribs))))

(mac my.rule (name parms . body)
  (zap expand name)
  (let (label . actualbody) body
    (zap expand label)
    (unless (and actualbody anormalsym.label)
      (= actualbody (cons label actualbody) label (uniq)))
    `(do (,mt!defmultifn-stub ,name)
         (,mt!contribute ',name ',label ,my!basic-rulebook-reducer
           (,ru!ru ,parms ,@actualbody)))))

)

All the definitions are surrounded by a (packed ...) form, which does a couple of things: It defines the “my” namespace anaphorically, it executes its body at the top level, and it returns a package value that exposes that namespace.

The using-rels-as form here resolves the three dependencies '(rel "mutlival.arc"), '(rel "order-contribs.arc"), and '(rel "../rules.arc"), gets the package values for them, and binds 'mt, 'ot, and 'ru to those packages’ namespaces for the rest of the form, which it executes at the top level.

A dependency of the form '(rel "relative/path/to/code.arc") uses relative addressing. There’s a little bit of bookkeeping done behind the scenes to make this work. (Currently, this is actually the only form of dependency supported. It’s possible to extend the system to support things like installing libraries from the Web, requiring certain Arc implementations to be in use, requiring certain implementation patches to have been applied, or doing version number comparison, but I don’t yet have a plan in mind for those things.)

I’ve mentioned that 'my, 'mt, 'oc, and 'ru are bound to namespaces here. A namespace is just a macro that associates symbols to gensyms.

  • If you pass it a symbol (“my.foo“), it expands into a gensym (“gs1234-foo“). This means you can use my.foo in most places you can use a variable name, except that it has to be a place where macros are expanded.
  • If you pass it a quoted symbol (“my!foo“), it expands into a quoted gensym (“'gs1234-foo“). This is useful for code generation, as you can see in multirule.arc above.
  • Finally, if you pass it a form other than a 'quote form (“(my:foo a b c)“), if the car of that form is a symbol, then it expands into the same form except with a gensym at the car (“(gs1234-foo a b c)“). This is useful if my.foo is a macro; if instead you just say (my.foo a b c), the Arc compiler will expand the my.foo ssyntax, then determine that (my foo) is not a symbol globally bound to a macro (since it’s a list), then macro-expand (my foo), and you’ll end up getting a runtime error when the macro is invoked as a procedure.

In order to facilitate the use of namespaces, the module system redefines 'def, 'mac, and 'safeset so that they expand the names given to them, and Lathe code continues with this policy everywhere it makes sense to do so. You can see this effect in multirule.arc above, where 'rule explicitly expands both its name and its label.

Multivals, a generalization of multimethods

For the time being, Lathe’s multimethod API is relatively abstract. In fact, the term “multimethod” itself indicates a method that dispatches based on the types of multiple parameters, and since Arc has no obvious and extensible type system to dispatch on, I haven’t attempted multimethods in this proper sense. But inasmuch as a multimethod is a method defined in multiple pieces, it’s a special case of what I’ll call a multival.

Conceptually, a multival is anything which can be defined in multiple pieces (its contributions). When a multival is needed, the accumulated contributions are sent to a single reducer associated with the multival, and the reducer’s result is used.

When something is defined in multiple places, it’s tough to say in general which of those definitions should have precedence or what order they should be combined in, especially when the definitions are far apart or in separate libraries (when code order becomes obscure or vague). This is a problem many multiple-definition systems like CSS and Inform 7 solve with complicated orders of precedence (like a notion of how specific a definition is) alongside patched-on ways to escape those conventions (like CSS’s !important and Inform 7’s procedural rules). For the purposes of solving this problem, Lathe’s multival system provides a single multival, 'order-contribs, whose purpose is to sort multival contributions.

That’s right, 'order-contribs is a multival. True to its intent to sort the contributions of every multival, it sorts its own contributions. It does this the hard way, by brute-forcing every permutation of its contributions (with quite a bit of pruning) until it finds an order that’s consistent with itself. If this order can’t be found, 'order-contribs signals an error. This should cleanly model the behavior desired by Andrew Plotkin for a rule-based rule precedence system. And hey, if you can find a smarter way to do this order-finding, you can write that function and contribute it to 'order-contribs as the only contribution. The built-in brute-force search won’t hurt you, since the factorial of one is one.

Finally, for those who really don’t care about 'order-contribs, it’s opt-in. Most multival reducers Lathe defines will call 'order-contribs right away, but there’s nothing preventing someone from defining a reducer that does no such thing. One reason for doing this is when you need to use a strange library that contributes things to 'order-contribs that mess it up for everybody else. (When a rogue rule asserts its own precedence over all other rules, in principle it’s impossible to overcome that with another rule unless you get clever/lucky regarding the order in which the permutations are checked.)

Multivals in practice

I could go into the internals of defining your own reducers and contributions in Lathe, but there’s nothing particularly clever about it. There’s just a global store of multimethod contributions and reducers, along with an API for contributing to that store. And then there’s 'order-contribs, which has similar idiosyncracies if you want to use it directly. So instead I’ll show you how this infrastructure looks on the surface, using some contrived examples:

; multirule-demo.arc

(prn "starting multirule-demo")

(using-rels-as mr "../multival/multirule.arc"
               oc "../multival/order-contribs.arc"

wipe.fail

(mr:rule factorial (n)
  (unless (< 0 n) (fail "The parameter isn't positive."))
  (* n (factorial:- n 1)))

(mr:rule factorial (n)
  (unless (is n 0) (fail "The parameter isn't zero."))
  1)

(mr:rule expbysquare (base exp) one
  (unless (is exp 1) (fail "The exponent isn't one."))
  (list base 0))

(mr:rule expbysquare (base exp)
  (unless even.exp (fail "The exponent isn't even."))
  (let (prevresult mults) (expbysquare base (/ exp 2))
    (list (* prevresult prevresult) (+ mults 1))))

(mr:rule expbysquare (base exp)
  ; This condition subsumes the condition for the 'one contribution on
  ; purpose, so that we can test 'prec. Since this contribution comes
  ; later in the code, it ends up farther toward the beginning of the
  ; contribution stack, and ultimately this rule would be tried before
  ; the 'one rule (catastrophically) if not for the presence of
  ; [iso (map _ '(name label)) '(expbysquare one)] in the 'prec line
  ; below.
  (unless odd.exp (fail "The exponent isn't odd."))
  (let (prevresult mults) (expbysquare base (- exp 1))
    (list (* base prevresult) (+ mults 1))))

(mr:rule expbysquare (base exp) diabolical
  (err:+ "Somehow the 'diabolical contribution to 'expbysquare was "
         "used."))

(oc.prec [iso (map _ '(name label)) '(expbysquare one)]
         [~iso (map _ '(name label)) '(expbysquare diabolical)])

(for i 0 10
  (prn "The factorial of " i " is " factorial.i "."))

(for i 1 10
  (let (result mults) (expbysquare 2 i)
    (prn "Two to the " i " gives " result " after "
         (plural mults "multiplication") ".")))

(prn "finishing multirule-demo")

nil

)

First, note that this file is not set up a module, and it doesn’t hesitate to pollute the global namespace. But although it isn’t careful about what comes out of it, it is careful about what goes in; the “wipe.fail” line toward the beginning makes sure that 'fail is not a macro and therefore doesn’t get macro-expanded in the following code.

There are only three new operators this code uses: 'rule, 'fail, and 'prec.

The implementation of the 'rule macro was shown further above. Essentially, it works like a normal function definition, except that multiple such definitions can coexist.

In order to make sure the appropriate rule is used for the given situation, any rule that doesn’t apply should call 'fail right away. The 'fail function is defined anaphorically within the context of a rule, and it exits the rule immediately, making its use very similar to that of 'err. However, 'fail and 'err have different meanings; 'fail signifies that this rule doesn’t apply but some other rule might, and 'err signifies that something is positively wrong.

Another feature 'rule provides is to label a particular rule with a given symbol, by writing that symbol unquoted after the argument list. As you can see, this is optional; the 'factorial rules have no labels, but two of the 'expbysquare rules do. Labeled rules have two advantages: One, they’re easier to refer to specifically from elsewhere in the code, and two, if you define multiple rules with the same name and the same label, the older ones are overwritten. The overwriting feature is especially useful at a REPL, and it was inspired by an early version of Andrew Wilcox’s 'extend macro.

Finally, there’s 'prec, a function that takes any number of tests and institutes a precedence order on contributions so that those which satisfy the tests come first. When there are multiple tests given, the earlier tests in the argument list have more powerful influence than the later ones.

A 'prec call just works by registering a contribution to 'order-contribs. It’s possible for this contribution to be given a label too, using the 'label-prec macro like so:

(oc:label-prec expbysquare-precedence
  [iso (map _ '(name label)) '(expbysquare one)]
  [~iso (map _ '(name label)) '(expbysquare diabolical)])

If you label your precedence contributions like this, you can define precedences over precedences.

Furthermore, with the right setup, you should be able to store arbitrary metadata about rules at the same time as you define them (by associating the name and label of the rule to a metadata container via a global table or something) and then have much more expressive precedence rules based on that medatada, making it less necessary to write special-case precedence rules like these. This is the path I’m going to take, ’cause there’s no point in having multiple definitions of something if the definitions are going to be manipulated individually.

And much, much more (but not that much)

Even if the module system and multival system are too monolithic or too specific for your needs, Lathe still has quite a few bite-size hacks worth looking at. Here are a few of them:

The 'global function, defined in Lathe’s arc/modules/modulemisc.arc, takes a symbol and returns the value of that symbol in the global environment, or nil if the symbol is unbound. That’s nothing exciting; (global x) is just (bound&eval x) with some error checking. What’s exciting is that 'global has a 'setforms entry, allowing deeply nested code to modify arbitrary global bindings. This is slightly harder than it sounds; to do it without using 'global requires code similar to (eval `(= ,x ,something)), but that 'something can’t refer to any part of the lexical context, since it’s being evaluated in the global one, so a single temporary global variable is needed to ferry the value over. The 'global 'setforms entry takes care of all of that.

The 'parse-magic-withlike function, which is also defined in modulemisc.arc, is a utility for macros to use. It takes the body of a form that’s similar to Arc’s 'with, and it extracts all bindings from the beginning of it and pairs them up in a list. If the first element of the body is a list, it behaves just like Arc’s 'with and treats that list as a list of places and values to bind. However, the parentheses around those bindings can be omitted if all the places being bound are non-ssyntax symbols. Since a non-ssyntax symbol doesn’t make a lot of sense at the beginning of a 'do body (unless it’s the only expression in that body), it shouldn’t be misinterpreted as a place to be bound. And the macro can still support destructuring or setforms for bindings, since the user can always wrap the bindings in a list the old-fashioned way when that feature is needed.

Somewhat randomly, I wrote an independent implementation of Andrew Wilcox’s 'extend macro, which I put in Lathe’s arc/extend.arc. In addition to the 'extend macro itself, this also provides 'label-extend, which does the same thing but associates a unique label with the extension so that another extension with the same label will overwrite it. There was an interesting hurdle to overcome in this implementation to handle corner cases in the way Andrew Wilcox’s 'extend binds 'it in the body to the value of the test; I end up having to store the body as a function that takes 'it and returns a function that takes the regular parameters, since 'it is bound this way in the parameter list too. I haven’t needed this at all, but it was a nice exercise.

These snippets are great candidates for committing to Anarki. However, I don’t know where I should draw the line, I’m not bold enough to stomp into a community project carrying a module system, and because of its Rainbow support, Lathe needs a home apart from Anarki anyway. If my hacks do find their way into other projects, that’s fine, but I think their first stop will continue to be Lathe.

And all in all, With the comfortable structure the Lathe repo gives me, I’m hoping to have a outlet for my language design pursuits while at the same time making the results more available to the rest of the world.

Advertisements

2 thoughts on “Modules, Multimethods (Kinda), and More for Arc

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