arlo: generic combinators for python [12/20/2008 23:23:54]
python that looks like haskell:
from arlo import declare, _
exec declare('sig let Ord a where y xs x ')
qsort = [
sig. qsort == Ord.a >> [a] >> [a] ,
let. qsort ( [] ) == [] ,
let. qsort ( _[x:xs] ) == ( _.qsort.lesser + [x] + _.qsort.greater ,
where (
_.lesser == [ y | y << xs , y < x ],
_.greater == [ y | y << xs , y >= x ])) ]
The first line imports a function (declare) and an object (_). from the module arlo.
The second line calls declare to convert a string of identifiers into a string of python variable declarations, and then runs the generated code.
The remaining lines create a list of three objects, and assign it to a new variable called qsort.
The point of this program isn't to emulate haskell in python, or even to implement quicksort, but rather to demonstrate how arlo lets you hack the python syntax to express interesting ways.
expressions that look like statements:
from arlo import declare, _
exec declare("CLASS YIELD RETURN SET DEF SELF INIT")
print repr(
CLASS. MyClass ( _.object ) [
DEF. INIT (SELF, _.name ) [
SET. SELF.name == _.name ],
DEF. hello (SELF, _.name) [
YIELD. _("hello %s") % SELF.name ]])
The first two lines are the same as before, except for the names being declared.
The rest of the program builds up a single object and then prints out a string representation of that object. It looks like this (except scrunched together on one long line):
_.CLASS.MyClass(_.object)['_.DEF.INIT(_.SELF,_.name)
['(_.SET.SELF.name == _.name)'],_.DEF.hello(_.SELF,
_.name)["(_.YIELD._(_('hello %s')) % _.SELF.name)"]']
What's interesting is that if you loaded that output into a python string, evaluated it with python's eval() function, and then printed the resulting representation, you'd get that same output
again.
the reification rule:
# for any arlo.Expr object s:
assert repr(eval(s)) == s
In other words, arlo lets you create
python expressions that model the syntax used to create them.
Why would you want to do this? Well, as you can see from the examples above, by stripping the meaning from the various python operators, you can create your own mini-languages on the fly, without needing to write your own parser.
arlo at the prompt:
You can also combine these expression objects directly at the python prompt, and switch back and forth between the expression language and pure python. For example, notice how python immediately evaluates 2 + 3 in the fourth line below, whereas the other addition operations get quoted into the expression object.
>>> x = _.x
>>> x
_.x
>>> x + 1
(_.x + _(1))
>>> x * ( 2 + 3 ) + 2
((_.x * _(5)) + _(2))
>>> x.y() + _.z
(_.x.y() + _.z)
Another way of saying this is that arlo
is a generic combinator library for building expressions.
Combinator libraries are common in functional
languages like haskell, but they're not exactly
new to python. For example, pyparsing uses the approach to build parsers, while Stan overrides method invocation (x(y)) and subscripting (x[y]) to provide a pure-python syntax for building XML documents,
and the SQLAlchemy expression language uses the combinator concept for building SQL queries.
What is new (at least as far as I know) is the idea of creating a generic combinator library for expressions.
We've already seen that calling repr() on
these objects produces the python syntax necessary to recreate them. But if you call str(), you get the equivalent python expression, which you can then pass to eval():
Sort of like a lambda:
>>> y = _.m * _.x + _.b
>>> y # repr()
((_.m * _.x) + _.b)
>>> print y # str()
((m * x) + b)
>>> m, x, b = 1, 2, 3
>>> eval(str(y))
5
>>> x = 4
>>> eval(str(y))
7
As you can see, you can use arlo and eval() as an alternative to defining named functions or using lambda.
About two years ago, I wrote a post called "what python looks like naked" that demonstrated how you could remove all of python's control structures from a program and replace them with functions and delaying every expression by wrapping it in a lambda.
If you can replace python's control structures, that
means you can create your own control structures. For example, you could use the technique to add a prolog-style inference engine to python. Then, in addition to simple propositional logic (if/elif/else and the boolean operators), your program could make choices based on logical deduction from a set of facts and rules.
Of course you can implement these things in python
already, or call foreign libraries, but it would be nice
to have these things as first-order objects in the language, and that's what a reification technique like wrapping everything in lambda gives you.
The only problem is, lambdafied python is an ugly, ugly mess.
The combinator appproach goes a long way to solving the syntax problem, and with arlo, python developers can now use a generic syntax for building combinator libraries.
Anyway, this is an idea I've been kicking around for a long time, and now that it's working, I'd love to hear what other folks have to say about it.
try it out!
(it's open source under a python-style license)
You can browse or download the code from the Trac links below:
You might also want to look at wherewolf, a simple language
for building expressions for matching against tables of data. Thee expressions can either be evaluated directly in python for querying against data in memory, or compiled down to SQL WHERE clauses (like a very tiny version of SQLAlchemy).