You are viewing fare

eyes black and white

Interface-passing style

My local repository of XCVB is in a transient broken state in the beginning of a big refactoring. I've decided that it was easier to declare it broken, then take each file one by one in order, update it, add tests to it, and declare it fixed before I get to the next one.

But more interestingly, in my next rewrite of XCVB, I want to make wider use of a functional programming style and functional datastructures. However, I looked at the state of Common Lisp libraries, and could find precious little in terms of functional datastructures, except for FSet which comes with its own CL dialect which is more than I'm ready to deal with, yet without the level of control I desire.

And thus I rolled my own implementation of balanced binary trees, and published it as part of lisp-interface-library (formerly part of fare-utils). Actually, I'm so proud of the API I designed that I think it's worth a minor article at a Lisp conference, or at the very least a Lightning talk or two at the Boston Lisp Meeting.

  • The general idea is to systematically use composable first-class "interface" objects to drive the choice of algorithms.
  • These interface objects are typically used as first argument to any generic function in the API.
  • Interfaces can easily share common sub-algorithms with interface inheritance and interface mixins.
  • Interfaces can have slots that contain other interfaces to which they delegate some subproblems, and functions can build first-class interfaces by composing simpler interfaces into more elaborate ones, yielding parametric polymorphism.
  • Going from binary-trees to balanced binary-trees is literally one defmethod away, plus a trivial helper and two trivial defclasses. Very pleasant.
  • Algorithmic interfaces are decoupled from data structure constructors, and particularly from state management. Indeed, I'm mostly using constant algorithmic interfaces and pure functional datastructures. This is also very pleasant, unlike the horrors of standard OO style that conflate independent concerns of algorithm selection, data-structure and state encapsulation.
  • A very same datastructure can be viewed in different lights by being passed to the same function with different interfaces, and this makes it very easy to compose interfaces.
  • For instance, a pure hash table is a balanced tree of buckets, each bucket holding one (or at most a few) entries the hash values of which collide. This is trivially implemented by composing balanced trees and alists, so that the very same node can be viewed either as a hash-table of elements, or a tree of buckets.
  • Pure hash-table and alist interfaces are each parametrized by the interface that defines hash-function and equality on keys.
  • With this technique, you can have all the parametric polymorphism that Haskell type classes, ML functors, C++ templates, Java generic interfaces, PLT Scheme units, etc., provide, except without the aggravation or limitations of any of them, plus it fits nicely into the native Lisp style, and it takes advantage of CLOS expressiveness and optimizations.
  • While I was at it, I also implemented Big-Endian Patricia Trees aka "fast mergeable integer maps", with an additional obvious optimization for merging dense maps faster.
  • All my ventures with that interface passing style of programming were very pleasant. And I didn't feel like using a monad to pass interfaces around.

For instance, given an interface i that implements some kind of pure functional maps, you can lookup a key k in a map m with (lookup i m k) independently from that map being a function, tree, a hash-table, a trie, or whatever clever thing the user came up with. You can create interfaces from other interfaces, such as (<alist> eq:<equal>) which will create an interface for maps as association lists using equal as their equality predicate. Interfaces can take functions, numbers, etc., as parameters. You can implement order domains as parametrized by a string-lessp-like comparison predicate or by a strcmp-like function. You could have have n,m-Btrees, etc.

Note that "my" idea is not novel at all. Haskell typically implements type classes exactly this way: see for instance Implementing Type Classes (1993) by John Peterson and Mark Jones. Haskell has the advantage that it will automatically infer the type class for you and pass it around as an implicit argument. In a dynamic language like Common Lisp, you have to explicitly pass the interface around, which on the one hand is cumbersome, but on the other, gives you more control: you can express parametric polymorphism, existential quantification, dependent types, and multiple ways to view a very same data structure as being an instance of the same interface protocol, which is especially great when bootstrapping elaborate versions of a protocol from simpler versions of the same (as is done with hash-tables). Of course, using Haskell, you could also go from one point of view to the other by wrapping objects inside view-specific constructors; but then, if your algorithm switches point of view constantly as for a Necker Cube, you may waste a lot of space and possibly leak as you keep creating new wrapped objects; whereas with a first-class interface separate from the data, you can just switch interface without consing.

You could probably bootstrap a nice object system this way on a language that doesn't have objects, but using an existing object system to combine and compose interfaces actually helps a lot. Note that such interface objects are a great target for partial evaluation, hot spot optimization, etc. Happily, SBCL seems to be doing just that for you.

It's amazing the things you can do with proper use of a λ!

PS: see my ILC'2012 article LIL: CLOS reaches higher-order, sheds identity and has a transformative experience [source, HTML, PDF]

Comments

article

If you write an article about this, please announce it in your blog. I would be very interested in reading it.

(Anonymous)

Did you check http://github.com/ks/X.FDATATYPES ?

X.FDATATYPES

I didn't know about it. I suppose I didn't search the correct keywords.

I'm glad it exists, but I grew to really like Interface Passing Style, and may steal the code and reimplement it this way.

Also, the X.FDATATYPES author apparently doesn't know that github can create the .tar.gz from you without you checking it in. And he documents even less than I do! Congratulation though, it's nice that it should exist.

(Anonymous)

Re: X.FDATATYPES

I know about generating tarballs, but they have git's SHA attached to the name, which does not play well with cliki & asdf-install.
Do you know how to get tarball by making GET request on github URL with constant name?

Karol

X.FDATATYPES

If github won't do it, you can put you think on common-lisp.net's site, that can do tarballs with fixed names.

Or you can use github's download interface instead of checking things in there.

tarballs in git sucks. More work, more space wasted.
Worth a filtering rebasing of the whole project.

(Anonymous)

Re: X.FDATATYPES

http://github.com/ks/X.FDATATYPES/tarball/master
Sounds really interesting. I've always bemoaned OO style for it's separation of data and algorithms. This sounds like it could be a really good middle ground for an interface. I'd love to hear more about it.

(Anonymous)

er... um?

That sounds kinda interesting, but unfortunately I really don't get it! Could you please elaborate, maybe with a few simple examples that get the idea across (and are readable by non-lispers)?

(Anonymous)

Re: er... um?

Same here. I'm familiar with OO, but much less so with lisp and functional programming. A follow-up would be nice.

(Anonymous)

Sounds interesting but difficult to totally comprehend your idea (my bad). I would love to read a more elaborate (and err.. dummy's style, if I may) account on this style with simple examples. It would make it easier to use the fare-utils and also extend them, then.

-quasi
Interesting.

> These interface objects are typically used as first argument to any generic function in the API.

I've used an approach like this in a couple places. My favorite case is representing graphs, to decouple the objects comprising the graph's vertices from the graph itself, so that objects may be members of multiple graphs, each with their own rules governing how successors/predecessors are generated. Storing state in the first arg (making it more an ADT than an interface) makes it possible to define a graph type that computes the transitive closure of a directed graph and caches a table of direct predecessors, when the vertices themselves only know their direct successors (as in the possible case of a control-flow graph), without modifying the vertex objects themselves. You can also paper over whether edges are best represented explicitly (as objects) or implicitly (with successor/predecessor lists) using mutually recursive generic functions grounded by defining methods for whichever function fits the underlying objects.

I've toyed with a protocol for lattices along similar lines, parameterizing the functions on the type of lattice rather than the members themselves, for instance:
;;; A lattice of factors..
(defmethod join ((lattice (eql :factors)) a b) (lcm a b))
(defmethod meet ((lattice (eql :factors)) a b) (gcd a b))
...
;;; A lattice of bit strings as integers
(defmethod join ((lattice (eql :bitmask)) a b) (logior a b))
(defmethod meet ((lattice (eql :bitmask)) a b) (logand a b))
...
It probably makes sense to use classes rather than EQ-specializers, for instance to distinguish bounded versus general lattices.

It sounds like you're taking the idea much further. I'm hesitant to rely heavily on composition via mixins and inheritance because of the static nature of CLOS, though. I find the prospect of calling ensure-class at runtime to produce the arbitrary combinations distasteful; others may disagree.

(Anonymous)

At the end of your first bullet point...

I thought type classes, specifically because one needs to keep track of interfaces in CLOS to implement as generic functions members of the type class that are specialized on return type.

(Anonymous)

Hmm...

This is kind of like presentation methods in CLIM, where the presentation type is a separate parameter.

-- Rahul

"Interface Passing Style"

I've been using a similar dictionary passing mechanism to implement Haskell-like monad sugar in scheme. That said, I curry the function and pass it as an argument to the result rather than as the first argument. This lets me build macros for things like do sugar that can be used like:
(define (modify f) (do (x <- get) (put (f x)))


The result is polymorphic in the choice of monad that provides state because do returns a function from a dictionary to a monadic value, and the get and put combinators expect that dictionary to be passed to their results and dispatch to appropriate methods.

This also has the nice side effect that it can be done with hygienic macros.

Re: "Interface Passing Style"

For reference, edwardk adds on IRC this link: http://paste.lisp.org/display/86914
and this comment:
"each function returns a lambda that expects the dictionary, that lets me use variadic functions"

The Spirit of Lisp (some young kid&#8217;s impression)

User redline6561 referenced to your post from The Spirit of Lisp (some young kid’s impression) saying: [...] Passing Style” which simulates the parametric polymorphism of Haskell’s type classes [...]
eyes black and white

October 2014

S M T W T F S
   1234
567891011
12131415161718
19202122232425
262728293031 

Tags

Powered by LiveJournal.com