Here are two Python modules that use techniques similar to the Blitz++
"expression templates" techniques to build a parse tree from a Python
arithmetic expression (including actual parameters), then compile it
into machine code on the fly. You might want to do this, for example,
if you have a complicated arithmetic expression that you want to
evaluate many times. Dave Long inspired this technique by
implementing a Forth interpreter this way.
I mostly did this this afternoon as I waited in the emergency room
waiting room.
In its current form, this program suffers from two big flaws that
probably keep it from having any real use:
1. The generated C files #include <Python.h>, which includes a lot of
the system header files --- about 16 500 lines' worth on my system.
gcc can compile a small C source code into a shared library in tens of
milliseconds, but parsing all these header files takes it more than a
second on my 300MHz Pentium. You have to do a lot of arithmetic in
Python bytecode to chew up a second of evaluation. Worse, the
regression tests take 17 seconds!
2. The generated C files handle only integers.
It also has a third, more minor flaw:
3. It will recompute common subexpressions needlessly, even when it
already knows enough to store their results into the same variable.
These flaws don't disturb me too much; I built this program with an
eye to techniques for efficient implementations of the "mvfs" I
described in a kragen-tol post earlier this month. I think psyco
probably does a better job of accelerating Python arithmetic
evaluation than this program does, and in a more useful way, although
I haven't tried it.
Below I include the two source code files, followed by a tarball
including it (for ease of extraction).
Here's pygencode.py; pygencode.function_from_c_body turns a chunk of C
code into a Python-callable function.
#!/usr/bin/python
# Given C code, compile it at run-time into a Python-callable function.
# Works well enough at present, but takes 1+ seconds on my 300MHz processor
# even for these trivial examples. I suspect that's because Python.h
# includes nearly all the system header files.
import os, sys
class modname_generator:
def __init__(self):
self.counter = 0
def __call__(self):
self.counter += 1
return "tmpmod%s" % self.counter
gen_modname = modname_generator()
dyncode_dir = ".tmp_dynpycode"
def gen_c_filename(modname):
return "%s/%smodule.c" % (dyncode_dir, modname)
def write_file(filename, modname, funcbody):
if not os.path.exists(os.path.dirname(filename)):
os.makedirs(dyncode_dir)
outfile = open(filename, "w")
outfile.write("""
#include <Python.h>
static PyObject *
call(PyObject *self, PyObject *args)
{%(body)s
}
static PyMethodDef methods[] = {
{"call", call, METH_VARARGS},
{NULL, NULL},
};
void init%(modname)s()
{
Py_InitModule("%(modname)s", methods);
}
""" % { 'modname': modname, 'body': funcbody })
outfile.close()
def write_simple_file(filename, modname):
write_file(filename, modname, """
if (!PyArg_ParseTuple(args, "")) return NULL;
return Py_BuildValue("i", 3);""")
def so_file_name(modname):
return '%s/%smodule.so' % (dyncode_dir, modname)
def compile_c_file(filename, modname):
compiler = '/usr/bin/gcc'
rv = os.spawnv(os.P_WAIT, compiler,
[compiler, '-O', '-shared', '-I/usr/include/python2.1',
filename, '-o', so_file_name(modname)])
if rv:
raise "Compile failure"
def import_c_file(filename, modname):
compile_c_file(filename, modname)
sys.path.insert(0, os.path.dirname(filename))
try:
return __import__(modname)
finally:
sys.path.pop(0)
def remove_if_possible(pathname):
try: os.remove(pathname)
except: pass
def function_from_c_body(funcbody):
modname = gen_modname()
filename = gen_c_filename(modname)
try:
write_file(filename, modname, funcbody)
module = import_c_file(filename, modname)
return module.call
finally:
remove_if_possible(filename)
remove_if_possible(so_file_name(modname))
def test():
if os.path.isdir(dyncode_dir):
for filename in os.listdir(dyncode_dir):
remove_if_possible("%s/%s" % (dyncode_dir, filename))
modname = gen_modname()
filename = gen_c_filename(modname)
assert filename == "%s/%smodule.c" % (dyncode_dir, modname)
write_simple_file(filename, modname)
file_contents = open(filename).read()
assert file_contents.endswith("""
#include <Python.h>
static PyObject *
call(PyObject *self, PyObject *args)
{
if (!PyArg_ParseTuple(args, "")) return NULL;
return Py_BuildValue("i", 3);
}
static PyMethodDef methods[] = {
{"call", call, METH_VARARGS},
{NULL, NULL},
};
void init%(modname)s()
{
Py_InitModule("%(modname)s", methods);
}
""" % { 'modname': modname })
orig_sys_path = sys.path[:]
module = import_c_file(filename, modname)
assert module
assert module.call() == 3
os.remove(filename)
os.remove(so_file_name(modname))
func2 = function_from_c_body("""
if (!PyArg_ParseTuple(args, "")) return NULL;
return Py_BuildValue("i", 4);""")
assert func2
assert func2() == 4
assert sys.path == orig_sys_path
assert os.listdir(dyncode_dir) == []
test()
And here's compilemath.py, which uses the above pygencode.
#!/usr/bin/python
# portably compile arithmetic expressions into machine code on the fly
import pygencode
class MismatchedArgCount(Exception): pass
class gensymmer:
def __init__(self):
self.counter = 0
def __call__(self):
self.counter += 1
return "_gensym%s" % self.counter
gensym = gensymmer()
def make_term(obj):
if hasattr(obj, 'as_compilable_term'):
return obj.as_compilable_term()
elif type(obj) is type(0):
return constant_term(obj)
class term:
def as_compilable_term(self): return self
def __add__(self, other):
return sumterm(self, other)
def __sub__(self, other):
return diffterm(self, other)
def __mul__(self, other):
return prodterm(self, other)
def __div__(self, other):
return ratioterm(self, other)
def __call__(self, *args):
self.__call__ = self.compile()
return self(*args)
def compile(self):
return pygencode.function_from_c_body("\n" +
self.declarations() +
self.arg_parsing_code() +
self.evaluation_code() +
self.return_code()
)
def declaration(self):
if not hasattr(self, 'varname'): self.varname = gensym()
return " int %s;\n" % self.varname
def c_expr(self):
return self.varname
def arg_parsing_code(self):
argcount = self.argcount()
if argcount is None: argcount = 0 # only constants (kinda dumb)
argnames = ["arg%d" % ii for ii in range(argcount)]
comma = ', '
return '\n'.join([" int %s;" % name for name in argnames] +
[' if (!PyArg_ParseTuple(args, "%s"%s))\n'
' return NULL;\n'
% ('i' * argcount, comma.join([''] +
["&%s" % x for x in
argnames]))])
def return_code(self):
return ' Py_BuildValue("i", %s);\n' % self.c_expr()
class binary_term(term):
def __init__(self, operand1, operand2):
self.operands = map(make_term, [operand1, operand2])
def argcount(self):
argcounts = [count for count in [x.argcount() for x in self.operands]
if count is not None]
if argcounts == []: return None
elif len(argcounts) == 1: return argcounts[0]
else:
if argcounts[0] != argcounts[1]:
raise MismatchedArgCount, argcounts
return argcounts[0]
def declarations(self):
return (self.operands[0].declarations() +
self.operands[1].declarations() +
self.declaration())
def evaluate_operands_code(self):
return (self.operands[0].evaluation_code() +
self.operands[1].evaluation_code())
def evaluation_code(self):
return (self.evaluate_operands_code()+
" %s = %s;\n" % (self.varname,
self.evaluation_expr(*[x.c_expr()
for x in
self.operands])))
class sumterm(binary_term):
def evaluation_expr(self, var1, var2):
return "%s + %s" % (var1, var2)
class diffterm(binary_term):
def evaluation_expr(self, var1, var2):
return "%s - %s" % (var1, var2)
class prodterm(binary_term):
def evaluation_expr(self, var1, var2):
return "%s * %s" % (var1, var2)
class ratioterm(binary_term):
def evaluation_code(self):
dividend, divisor = self.operands
return (self.evaluate_operands_code() +
' if (%s == 0) {\n'
' PyErr_SetString(PyExc_ZeroDivisionError, \n'
' "compiled integer division");\n'
' return NULL;\n'
' }\n'
' %s = %s / %s;\n' % (divisor.c_expr(),
self.varname,
dividend.c_expr(),
divisor.c_expr()))
class arith_arg(term):
def __init__(self, ordinal, total_args):
self.ordinal = ordinal
self.total_args = total_args
def argcount(self):
return self.total_args
def declaration(self):
self.varname = "arg%s" % self.ordinal
return ""
def declarations(self):
self.declaration()
return ""
def evaluation_code(self):
return ""
def arith_args(nn):
return [arith_arg(ii, nn) for ii in range(nn)]
class constant_term(term):
def __init__(self, value):
self.value = value
def argcount(self):
return None
def declarations(self): return ""
def evaluation_code(self): return ""
def c_expr(self):
return str(self.value)
def test():
x, y = arith_args(2)
func = x + y
assert func(3, 4) == 7
assert (x + y + y)(1, 2) == 5
a, b, c = arith_args(3)
assert (a + b + c)(1, 2, 4) == 7
try:
f2 = a + x
f2(1, 2)
except MismatchedArgCount:
pass
else:
assert 0, "No exception raised"
f3 = x - y
assert f3(5, 1) == 4
f4 = x * x + y
assert f4(5, 1) == 26
f5 = a * b / c
assert f5(10, 5, 2) == 25
try:
f5(10, 5, 0)
except ZeroDivisionError:
pass
else:
assert 0, "No exception raised for zero division"
func = x + y + 5
assert func(1, 2) == 8
(z,) = arith_args(1)
assert (z * z + 1)(5) == 26
assert (make_term(1) + 1)() == 2
test()
begin 644 compilemath-0.tar.gz
M'XL(`&>M3#X``^T::V_;.+*?_2M8%3Y+J>+XF1S2ZP&];K%;8-L-MKU=X+*&
M($MTS%:6!%%.XP;][S=#4A1ER8_NIK=8G`9P;(G#F>&\229(5BF+Z,K/EZ>#
MLT??!`:#R>AB.H7OP?!B.C"_"W@TN#@?C8>C\^D$\(;CP7CZB$R_C3A56//<
MSPAY]#'S;VB\&^_0^%\4@HK]C:=^NGDH'H/A8+#;_F#LZ:2P_^1B?`[XTXOA
MZ!$9/)0`^^#_W/Y/'I^M>78V9_%9NLF72=QY0M(DR_UYM"'*'8B?L7RYHCD+
M"+U+,\HY2V).6)PG9.4'2Q93P`TI26*2+RE91)M.AZV0#DDWH#8<['2"R.><
MO&$<_"M8TO!%=O,R6<>Y_>HNH&D.-)U+D@).@0HS^6:UHMEEAP"$=$$\C\4L
M]SR;TVCAR/<(^-@/D!K-R',R,"8$?A0=F/#T.1GJD8SFZRPFEB?9=[E%NA7T
MCAP`-EI`V^ETD-O*_T@]0%G9R?R#XL869.ES/\\S?.F2GL\]J5E0LL3N&8(I
M]H#:KR,"'\2A$1#--RD5;`CC\F%0)Q.`H7(_SDNA"N7BBU*O#:RDP@I"^&0H
MU0]#I5.7)&#SK,Z:KU>:3H%D4.#K^2$*(5LL]I%8K:-#)-(L"?>1"-GM(1*9
M#ZZYCX;A8"XY\;,;ONUG!0ZXC'(D$5C*FJ;.8-26)#2#`GG+@8L%%O'57ZSC
M`(/(6V3)R@N\>1)N;.NWV")/]20M44C!"\3*8FX[Y"FIHX`47NIGG,4W'C)`
MM#H6O?6CM:"S!TG*JA#T<+E$0YKM98*CQTFN(T@JN7?K9[&_HA`WDH%ZUB%9
MUZPEB,4YZ?)GJ)-N96*I;`\SW`Y=-\ZHJ6EK+HR+O%'8OG@V1&2+$@MB^6T2
MTTMSWH"0)Y!;14:6X<R)_9'%H4_"]6KNF+Q0-@YSKBUXZ(:X4,;((LGPBZ$W
MQS?4+H@[,ST7W&SEP\0>J'=[X;W?XE[_0\)B^]K4(Q(7:D?RX@<P*&28;3E"
M!:Y[:MWVXZL-U`'O"C1(WZ_32,C&76)!WNURQP'.N\F0WI:@;__]XX_/]D_I
M$KO'>N1$*]B52U?KZ_7V"GX`KJV_R7IQ)W1R!PKYW;1*33K.K(P5,Y::W50H
MY6KC_6O-HO`7"$]J6\QRP6(.ZD97,^GJNB!`#^!G&YG[\8^SH^I"!DPIN%$X
MU+]&VPE/O4='7/FIK<NB2Z[KDXW%Z>#8$43"LV58H'Y5R,3D^LZ(*ZWZJBRS
M9DNP!=&1AYD&HV_6%)K`&YC/=$5$1(TG*G)$8QU9W$'TH<;6[Z\',V,6IY>=
M+6E,3/+XN?$\G%W6UI#YC-.&ILHMYU7F[!)G*PWS';YE5U0*DVN5I"9A=<;P
MV!EF37!*#U'UAGH%Q7V14)?V4+EJ%+@VJ2:.'MHGQP[1G;H$(LEVT=EUM;+-
MXN,>E52VZ[,(]Q,(%1WYQU#9`7\\O6TI&K*<HS)1T3D:&<E(1MLKDCD)-#,4
M?T=U]4,A@0Y')F;;0"PRG^XS'Y+AZ1Z&NBM]2(8G>QB6/>Q!CDUN#%TR"VD<
MNN(73[*BF2F,]W4.WQ!SNA_HBC0[<,A]4QG7]?YJ\RK+O'<T?Y=GT'G9\'P7
M>/^A6?(=2@@+@?$D<\E>*MM@J5X[Q`Z'WL#.,%34+*>QK3BZ_Q"(7W:.J%@G
M9S+@L4;;2M4Z6H\+>@%?GRL$%&;^/2RWI76T[XG3`P\*SJ&N(@O!-R.7Y$GN
M1U[3/DJA@*[4K^IP.1$PRH>#W879WC=,V[,[V=I\B)Z[/"_8%K((5NNHBENO
M@GL('5>'8$)'*D*9A-MQK-`4RG5I+L9<`L.US0.\FQ7&K9XO[#<PBDCKRH.7
MH#KQ?:RE=.NU0X='*Z@!<?\.4&U!I=CJT">G'+I.B7OGD@UY;BIX),V&NW,8
MN(-"M!$O0'LTR\5[>^R2B>@7+\PA6R#CQ[$AH8\$QE1BN&0.^Y8JI[%3F>W#
MS#E\`CF[RB+/-N7B%B,D!*AWQBO)4AXWB?.YAB:S)"&.[01NI:55L@Q@/_<V
M473`!+)K#:72%V.AE],MO8SMJ4N&0N2)Q)L(O),&'4Y*W-&Y1)Z*)9V`!LY(
M4$&>VD.09UHH=#1M4(C&&50T4*LO?U`!(K0^`]&RSM2<!3[3FL-H=_B[&+(_
MNT[5%X957_@,FO@,E(:./3755(R7YY9#1Z))+('4D0[>^;//JEMX>*C>_Y2'
MB0]W^R/O?\XGDUWW?^?G>.>C[O_&DPN\_QE?M/<__Q-HNO_YGMW2F+P45SJN
MO@1B.?%SDJWCTYR)D[X\@01[)2:=XO$VWAR0XA"Z#W1^3;*/G'RB441HG*QO
MED@`KX\H'D_,USG)(>UP,GP*K0`T$B''"Z35AHP'@S<_?,9=4D`Y-)5`BZ)(
MF"WS)<R';`WY$AI!>N>OTHCR/B&O8=O(4QH`U:6?]SB9T\!?`ZX4L;\$*BP.
MHG4(+&/J9]&&@-3BPHIO>$Y79$G]$'K^!4.*^@8KX2XB%!W/*@FQV\/;(=C4
MY,F?<SF5KU(0I.%N"B^G/"4CGKYM2RMNJC8BR+V0H3A6'XAY\"[=X%O5(B*9
MP$-5X'Q;T:GVBK#K/.MR&%I'M!^(O:=!VBV8JS;I$U0G*BC:!5F-X@K'P1N+
M\M(,#^,2WD_Q,IK>,9YSNW@$ZD*J@HYCZ`YPL)H!"C>ED?4P6><X!S<0*8T-
M.:Q/5@6C+Z2U+6@,GRBO(?\H/.F?'4@:>!MZM?EI_@%=[J2#AK3+9]GQEL_R
M2N>^:XLU\LZ7DL0;"E3#[_#V4/SBUS.0[UY(<V\A70NB$+Y<\N;5^Q^\7U[\
M_.+G[]]]D9NS>]QRNF+C"6^^/.O<)@RWKRSO:J-Q,+JD=[7Q7L/0&V$RVS)0
M@(=B[SP#Z6#A8,Y[TE,(O<O25#U<`[PH3$:^5%471`FG=L7JG&&8[C"^,MY^
M_[!4B[[WSL!RG,I.W'36A@/QL?,,R"I!>2)X>[O=O6>Z.T]Z!_Q=)4X513N7
MK=`P$GLZ%]\$@3PIR&[15WF?I_ZG^!8#X,K[]<7K]SHO9XU[]&L]2GJG/^&5
MSBE?^AD-Q<_7@H]R:Y7W1_UAKWF[7PK>.TU@?J.BU!D^6">[-79-XG#:>JE*
MR,)GT3HK,HQ,KT>J9S>:P(+\+#,#B[&AM:'?WITKZOV^,C#D;RF39U>H+W`7
M'QGXFEV:I/9`V3NCJ^26>FSAI0GG#*JAC3C&6I`GRB4QRU%CBU'\`P02;+S0
MW<J39:8W\KY=B"U7K`8;LGE=$T<F:8TOHP$X'++FMJZ+J@&*;=9Q@SJU"?<A
M-;IGPTX=7+5P$<;!22K%PM@*)EFI2!;CG`AJT>X).\22M;)>([?<\@'L6>P3
M-?;SXPMUZ0+[,[:6QX.^+:?R8JY24AWP<C^T:R+I"7T*#=\GV+`^>)']%G7B
M+URP=7G.V(T'F<M#G\<#?)7$KB]GA>M]12@KD\I)]3<BL.4APEARUVFO&L7E
M^QV!*SP-\@Z>437_B\LWZ`PFJC,PG1=EJ+VPC0,J];[0*PY4=&XB[4@C\HJY
MTYZXM-!""RVTT$(++;300@LMM-!""RVTT$(++;300@LMM-!""RVTT$(++;30
-0@N'X;\1I"YF`%``````
`
end
--
<[EMAIL PROTECTED]> Kragen Sitaker <http://www.pobox.com/~kragen/>
Edsger Wybe Dijkstra died in August of 2002. The world has lost a great
man. See http://advogato.org/person/raph/diary.html?start=252 and
http://www.kode-fu.com/geek/2002_08_04_archive.shtml for details.
