[ANN] C3 linearization
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: [ANN] C3 linearization
- From: Alban Linard <alban.linard@...>
- Date: 2015年9月29日 15:14:17 +0200
I am pleased to announce the first stable release of `c3`, an
implementation in pure Lua of the C3 linearization algorithm.
https://github.com/saucisson/lua-c3
This implementation extracts super classes with a user-defined function,
and handles cycles.
Install
-------
This module is available as a Lua rock:
````sh
luarocks install c3
````
Example
-------
First, require this module and create an instance of the algorithm
using your own `superclass` function.
Here, we simply use the identity function for `superclass`: the
superclasses are stored within the class, from `1` (the lowest priority)
to `n` (the highest priority).
````lua
C3 = require "c3"
c3 = C3.new {
superclass = function (x) return x end,
}
````
Then, build the class hierarchy. Here, we follow the example given in
[Wikipedia](http://en.wikipedia.org/wiki/C3_linearization). We check
that linearization works as expected:
````lua
local o = {}
local a = { o, }
local b = { o, }
local c = { o, }
local d = { o, }
local e = { o, }
local k1 = { c, b, a, }
local k2 = { e, b, d, }
local k3 = { d, a, }
local z = { k3, k2, k1, }
local assert = require "luassert"
assert.are.same (c3 (o ), { o, })
assert.are.same (c3 (a ), { o, a, })
assert.are.same (c3 (b ), { o, b, })
assert.are.same (c3 (c ), { o, c, })
assert.are.same (c3 (d ), { o, d, })
assert.are.same (c3 (e ), { o, e, })
assert.are.same (c3 (k1), { o, c, b, a, k1, })
assert.are.same (c3 (k2), { o, e, b, d, k2, })
assert.are.same (c3 (k3), { o, a, d, k3, })
assert.are.same (c3 (z ), { o, e, c, b, a, d, k3, k2, k1, z, })
````
Notice that the `superclass` function takes as input a class, and
returns its direct superclasses, from the lowest to the highest priority.
The C3 function returns a linearization of the classes, also from
the lowest to the highest priority. These orders differ from the one
used in the [Wikipedia](http://en.wikipedia.org/wiki/C3_linearization)
article, but they allow an efficient implementation.