decision tables Re: Another stab at a "switch/case" construct (new proposal):
Bengt Richter
bokr at oz.net
Thu Apr 11 09:34:30 EDT 2002
On Sat, 30 Mar 2002 08:33:13 +0300 (MSK), Roman Suzi <rnd at onego.ru> wrote:
>On Fri, 29 Mar 2002, Chris Gonnerman wrote:
>
>>----- Original Message -----
>>From: "Cliff Wells" <logiplexsoftware at earthlink.net>
>>>
>>> Now which is cleaner? I think the perceived need for this type of
>>> construct is a holdover from thinking in other programming languages
>>versus
>>> thinking in Python.
>
>if-elif-else is a complete functional substitute for any kind
>of switch/case. I can't see why this topic is still discussed.
>Python has dictionaries, so many simple things could be
>made by them. More complex decision making pieces of code
>could be elegantly done with if's.
>
>*
>
>However, I'd liked to see a good paradigm for expressing
>decision tables like this one:
>
>F1 F2 F3 R
>0 0 * do1
>0 1 0 do2
>0 1 1 do3
>1 * * do4
>
>in Python. (With lazy evaluation, of course).
>
>Any ideas?
>
See if this does what you want (what did you want to do with it?)
The DT class constructor will read your decision table just as is above, and make
an instance that has a decision tree in it. The test prints out the table and tree
and runs all the combinations of inputs, but you don't have to do all that of course.
The test code for the following is (snipped from below):
# first test
if testno==1:
print '\n--< Test 1, with complete table and list of functions >--'
print dtable
dt = DT(dtable, dofuns(4), on_error=errf)
dt.ptree()
for i,j,k in [(i,j,k) for i in 0,1 for j in 0,1 for k in 0,1]:
print dt(i,j,k)('args:',i,j,k)
dtable is your table with triple quotes around it, otherwise verbatim. It ignores blank
lines before and after, and white space left and right, so you can lay it out prettily ;-)
dofuns(4) generates a list of four functors to use ad do1-do4, but
DT accepts keyword specification of functions overriding or in place of the function list.
The keys must match the right column in the dtable if used (e.g., do2=foo2) and an error function
is optional via keyword on_error=whatever.
The print statement shows how the parameters are passed to the decoder like dt(i,j,k) and
the arguments passed can be anything, since they are captured as *args, **kwds and passed
through to the selected function. ('args:',i,j,k) was just to print something recognizable
using returns from the test functions.
I assumed '*' meant "don't care" in the table. I think it will generate a tree if you
use other than trailing '*'s, but the tree won't be as efficient space wise. It should
be the same speed though. The latter (heck, all) is largely untested, so no doubt there
are bugs somewhere.
A test (#1) with a complete table makes this test result (only tested on NT4 Python 2.2):
[ 6:28] C:\pywk\dtable>python dtable.py 1
--< Test 1, with complete table and list of functions >--
F1 F2 F3 R
0 0 * do1
0 1 0 do2
0 1 1 do3
1 * * do4
[
[
<dofun instance do_1>,
[
<dofun instance do_2>,
<dofun instance do_3>,
],
],
<dofun instance do_4>,
]
<dofun instance do_1> was called with (('args:', 0, 0, 0),{})
<dofun instance do_1> was called with (('args:', 0, 0, 1),{})
<dofun instance do_2> was called with (('args:', 0, 1, 0),{})
<dofun instance do_3> was called with (('args:', 0, 1, 1),{})
<dofun instance do_4> was called with (('args:', 1, 0, 0),{})
<dofun instance do_4> was called with (('args:', 1, 0, 1),{})
<dofun instance do_4> was called with (('args:', 1, 1, 0),{})
<dofun instance do_4> was called with (('args:', 1, 1, 1),{})
===< dtable.py >===================================================================
#!/usr/bin/python
# dtable.py (C) 2002 by Bengt Richter. All rights reserved and transferred to PSF
# This is alpha code. NO WARRANTY OR GUARANTEE OF ANY KIND
# The DT class constructor takes a decision table and a set of functions and defines
# an instance with a call method for decoding per the table and returning the
# appropriate function. The instance contains a decision tree generated from the
# decision table. This file can be run from the command line to execute one of
# four tests (1-4) thus: python dtable testno
# see test code at end for usage patterns. Sorry about doc shortage. More possible
# if any interest. You can reach me at bokr at oz.net.
#
class DT(object):
def tree_upd(subtree, conds, fun):
# subtree can be:
# [] empty, which can receive a terminal [fun] or a choice [x,y] or
# a don't-care-but-do-care-further-on where x and y are both []
#
# [fun] -- already a terminal, anything more is multiple definition
#
# [x,y] -- a '*' should update both x and y subtrees
condc = conds and conds[0] or '<error if used>'
if conds.count('*') == len(conds):
if subtree == []: subtree.append(fun)
else: raise ValueError, '*-tail conflicts for %s: %s' % (fun.__name__,conds)
elif condc == '*':
# current is don't care, but do care later
# split current node if not already split
if subtree == []: subtree.extend([[],[]]) #operate destructively, don't rebind!
if not isinstance(subtree[0], list) or not isinstance(subtree[1], list):
raise ValueError,'Conflicting "*" in tail "%s" for %s' % (cond, fun.__name__)
DT.tree_upd(subtree[0],conds[1:],fun)
DT.tree_upd(subtree[1],conds[1:],fun)
elif condc == '0':
if subtree == []: subtree.extend([[],[]]) # make sure it's split
if not isinstance(subtree[0], list):
raise ValueError,'Conflicting condition tail "%s" for %s' % (cond, fun.__name__)
DT.tree_upd(subtree[0],conds[1:],fun) # update subtree
elif condc == '1':
if subtree == []: subtree.extend([[],[]]) # make sure it's split
if not isinstance(subtree[1], list):
raise ValueError,'Conflicting condition tail "%s" for %s' % (cond, fun.__name__)
DT.tree_upd(subtree[1],conds[1:],fun) # update subtree
else:
raise ValueError,'Bad condition code "%s" for %s' % (condc, fun.__name__)
tree_upd = staticmethod(tree_upd)
def tree_clean(t):
if not isinstance(t, list): return t
for i in xrange(len(t)):
t[i] = DT.tree_clean(t[i])
if len(t)==1 and not isinstance(t[0], list): return t[0]
return t
tree_clean = staticmethod(tree_clean)
def _ptree(t,ind):
sind = ' '*4*ind
if isinstance(t, list):
print '%s[' % sind
for st in t:
DT._ptree(st,ind+1)
print '%s]%s' % (sind, ind and ',' or '')
else:
print '%s%s,' % (sind,t)
_ptree = staticmethod(_ptree)
def defaultErrf(*args, **kwds):
return 'defaultErrf: no function specified for:', args, kwds
defaultErrf = staticmethod(defaultErrf)
def __init__(self, dt, *flist,**fdir):
if flist and isinstance(flist[0], list):
flist = flist[0] # flist tuple contains a single list of args instead of arg list
# allow pretty table formatting by stripping leading/trailing blank lines and spaces
dtlines = [ s.strip() for s in dt.split('\n') if s and not s.isspace()]
self.kwk = dtlines[0].split()[:-1] # for kw=>arg list translation overriding flist
self.dtree = [] # dtree[0] is the root
# * * * foo => dtree == [foo]
# 1 * * bar => dtree == [[],bar]
# tree is cleaned up after building is completed
nlines = len(dtlines)
for fx in xrange(1,nlines): # walk table by lines
line = dtlines[fx]
ls = line.split()
ls, fname = ls[:-1], ls[-1] # cond list, function name
#print '-----------------\nfname:',fname,fdir,flist,locals(),globals()
fun = fdir and fdir.get(fname) or flist and flist[fx-1] or DT.defaultErrf
# add to tree as necessary for new choices
# call recursively descending tree update
DT.tree_upd(self.dtree, ls, fun)
# set optional on_error function to call with (args,kwargs) like others
self.on_error = (
fdir and fdir.get('on_error') or
flist and len(flist)>nlines and flist[nlines]
) # optional on_error function
self.dtree = DT.tree_clean(self.dtree) # change [fun] to fun at leaves
# define dispatch based on decision tree and input, returning selected function
def __call__(self, *args, **kw):
if kw:
args = [kw.get(k,0) for k in self.kwk] # default 0
else:
args = list(args)
t = self.dtree
while len(args)<3: args.append(0)
for fx in args:
# choose between t[1] and t[2] per fx
# print 't => ',t
try:
if not isinstance(t, list): return t
t = t[fx]
if t == []: raise IndexError
except IndexError:
if self.on_error: return self.on_error
raise ValueError,'Decision table does not define %s' % args
return t
def ptree(self):
DT._ptree(self.dtree, 0)
print
##########################
## tests ##
##########################
def test(testno=0):
# test example
dtable="""
F1 F2 F3 R
0 0 * do1
0 1 0 do2
0 1 1 do3
1 * * do4
"""
# the above dtable should lead to this decision tree
"""
tree =
[ # * * *
[ # 0 * *
<dofun instance do_1>, # 0 0 *
[ # 0 1 *
<dofun instance do_2>, # 0 1 0
<dofun instance do_3>, # 0 1 1
],
],
<dofun instance do_4>, # 1 * *
]
# it is traversed with args list [F1,F2,F2] of integer 0's & 1's
t = tree
for fx in args:
... etc., see __call__ method above
"""
# test functions
def foo1(*args): return 'foo1', args
def foo2(*args): return 'foo2', args
def foo3(*args): return 'foo3', args
def foo4(*args): return 'foo4', args
def errf(*args): return 'errf', args
# test functions as functors in list
def dofuns(n):
class dox:
def __init__(self,v): self.v = v
def __repr__(self): return '<dofun instance %s>' % self.v
def __call__(self,*args,**kw):
return '<dofun instance %s> was called with (%s,%s)' % (self.v, args, kw)
return [dox('do_%d' % (i+1,)) for i in xrange(n)]
# first test
if testno==1:
print '\n--< Test 1, with complete table and list of functions >--'
print dtable
dt = DT(dtable, dofuns(4), on_error=errf)
dt.ptree()
for i,j,k in [(i,j,k) for i in 0,1 for j in 0,1 for k in 0,1]:
print dt(i,j,k)('args:',i,j,k)
else:
# second etc tests with 0 1 0 undefined
dtable2 = """
F1 F2 F3 R
0 0 * do1
0 1 1 do3
1 * * do4
"""
if testno==2:
print '\n--< Test 2, table missing 0 1 0 do2, functions in list >--'
print '\n',dtable2
dt = DT(dtable2, dofuns(4), on_error=errf)
dt.ptree()
for i,j,k in [(i,j,k) for i in 0,1 for j in 0,1 for k in 0,1]:
print dt(i,j,k)('args:',i,j,k)
# third test, with 0 1 0 undefined
elif testno==3:
print '\n--< Test 3, table missing 0 1 0 do2, functions kw specified >--'
print '\n',dtable2
dt = DT(dtable2, do1=foo1,do3=foo3,do4=foo4,on_error=errf) # get functions named as in table (do1,do3,do4) per kwds
dt.ptree()
for i,j,k in [(i,j,k) for i in 0,1 for j in 0,1 for k in 0,1]:
print dt(i,j,k)('args:',i,j,k)
# fourth test, with 0 1 0 undefined and do1 function missing
elif testno==4:
print '\n--< Test 4, table missing 0 1 0 do2, functions kw specified except do1 >--'
print '\n',dtable2
dt = DT(dtable2, do3=foo3,do4=foo4,on_error=errf) # get functions named as in table (do1,do3,do4) per kwds
dt.ptree()
for i,j,k in [(i,j,k) for i in 0,1 for j in 0,1 for k in 0,1]:
print dt(i,j,k)('args:',i,j,k)
else:
print 'Undefined test number: %d' % testno
if __name__ == '__main__':
import sys
try:
n = int(sys.argv[1])
test(n) # do it/them
except:
print "Usage: python dtable.py testno\n where testno can be 1,2,3,4"
================================================================================
Anyway, this sat as a saved reply with nothing in it for a long time. I finally
thought to get it out, in case you or someone was interested. I just cut and pasted
to make a few different tests, as can be seen ;-)
Regards,
Bengt Richter
More information about the Python-list
mailing list