Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!apple!brutus.cs.uiuc.edu!wuarchive!wugate!uunet!yale!leichter
From: leichter@CS.YALE.EDU (Jerry Leichter)
Newsgroups: comp.lang.misc
Subject: Re: multi-dimensional switch statements
Message-ID: <67623@yale-celray.yale.UUCP>
Date: 26 Jul 89 14:00:06 GMT
Sender: root@yale.UUCP
Organization: Yale Computer Science Department, New Haven, Connecticut, USA
Lines: 58
X-from: leichter@CS.YALE.EDU (Jerry Leichter (LEICHTER-JERRY@CS.YALE.EDU))

A number of languages with a features of this general sort have been proposed
over the years.  The construct is usually called a decision table.  Two
references I know of - quite old, but you should be able to find more recent
stuff now that you know the term used - are:

	Lew, A and Tamaraha, D.  Decision Table Programming and Reliability.
		In Proceedings, 2nd International Conference on Software
		Engineering, 1976.

	Pollack, SL, Hicks,HT Jr. and Harrison, WJ.  Decision Tables:
		Theory and Practice.  Wiley-Interscience, 1977

While similar in flavor to a "multi-dimensional switch", a basic decision
table is actually more like a 2-d chain of if's.  A table has two segments,
a condition segment and an action segment.  For example:

Conditions |	R1	R2	R3
X > 5		Y	Y	N
Y > 2		N	-	N
X + Y odd	Y	N	Y

Actions
Z = Z + 1	-	X	X
X = X + 1	X	X	-

Each condition consists of a Boolean and n "when" markers.  Each "when" marker
is one of Y, N or -.  An action consists of executable code and n triggers,
either X or -.

Rules, here labeled R1-R3, are organized vertically.  A Y when marker is
satisfied when a condition is true, a N when its condition is false, a -
always.  Thus R1 represents (X > 5 and X+Y is even).

Once all the rules have been evaluated, any actions with an X trigger in a
column with a satisfied rule is executed.  Thus, if X = 1 and Y = 2, the
effect of this decision table is to satisfy R3, hence execute Z=Z+1.

Many elaborations are possible; an obvious one is to have a decision table
which will keep repeating until it reaches a state in which no rules are
satisfied.  That makes "decision table programs" universal.  It's possible
to define decision table subroutines quite naturally (e.g., have conditions
which are in some way the result of evaluating some other decision table).

Decision tables have never caught on in a big way, although there have always
been pockets of interest.  If you look through the theory and compiler liter-
ature, you can find papers here and there discussing algorithms for compiling
decision tables into efficient code.  It turns out that one can do a rather
good job.  Decision tables can provide a compact and very understandable rep-
resentation of complex decision procedures that would in most languages be
written as incomprehensible pages of nested if's.  Try writing out even the
very simple decision table I've shown above and you'll see what I mean.  (You
can, of course, simulate the decision table by using a Boolean variable for
each row.  Try making sense of that in a much larger decision table though.)

There are some obvious connections to other work, especially rule-based sys-
tems, though these tend to lose the elegant decision table notation.

							-- Jerry