mwm@mica.berkeley.edu (Mike (I'll think of something yet) Meyer) (07/22/89)
Last night, I ran into the need for a construct that I've not seen in
any language. I've seen this same need more than once, so thought I'd
ask if any existing language has such a construct.
There's a second half to this question: I don't know what the
construct should look like. I know what features I want it to have; I
just don't know how to get it to fit into a language.
The basic idea is to be able to code a state table as is, so that the
table is obvious. A two-dimensional switch statement is the analogy
that comes to mind. A typical example might look like:
switch (row:bumpx, col: bumpy) {
case 0: case 3: case 5: case 7:
case 2: z = x++ + y; z = 2 * x + y; z = 3 * x++ + y; z = x;
case 4: z = x + y; z = x + y++; z = 3 * x + y++; z = y;
case 7: z = x++ + y++; z = x + 2 * y; z = 8 * x++ + y++; z = x * y;
}
I have no idea how to make a compiler swallow something like the
above. I don't know that that's the right form for the thing.
Features that must be there: the labels on each axis should have to be
mentioned only once, and should definitely be computed only once. It
should be able to handle large blocks of code in each element. The
compilers should be free to create the most efficient code for this
case: jump tables, spares matrixes, search trees, or else-if chains
(i.e. - the features doesn't force an implemenation technic on the
compiler writers). Most importantly, the table should have to be
mentioned only once.
I'd like to hear any thoughts from people who've actually done some
language design & implementation work, on how they'd try and get such
a feature into a language, and what they'd make it look like.
I also look forward from hearing from those who think current language
design is wrong. After all, their "everything to all people" language
would allow me to do this. If it won't let me express my ideas in a
form I find comfortable, what good is it?
Thanx,
<mike
--
Cats will be cats and cats will be cool Mike Meyer
Cats can be callous and cats can be cruel mwm@berkeley.edu
Cats will be cats, remember this words! ucbvax!mwm
Cats will be cats and cats eat birds. mwm@ucbjade.BITNETjozwiak@uicsrd.csrd.uiuc.edu (07/24/89)
The language ISetL, for Interactive Set Language, allows _maps_
as first class objects, and as such allows one to build n-dimensional
switch statements:
{ [0, {[1,"cat"],
[2,"dog"]
}
],
[1, {[1,"panther"],
[2,"wolf" ]
}
]
}(0)(2);
"dog";
Similarly, since functions are first-class objects, as are sets (and
maps as a special case thereof), one may write:
cat := func(); printf "cat"; end;
dog := func(); printf "dog"; end;
switch:= { [0, {[1,cat],
[2,dog]
}
],
[1, {[1,func(); printf "panther"; end],
[2,func(); printf "wolf"; end]
}
]
};
switch(0)(1);
!FUNC(5cf98/5e700)!;
switch(0)(1)();
catOM;
There the system printed the word "cat", after which, as the system does,
printed the return value of the application, which was here the ISETL
object OM (the undefined object).
I hope this is an example of the sort for which you looked,
john jozwiak
jozwiak@uicsrd.csrd.uiuc.eduijd@otter.hpl.hp.com (Ian Dickinson) (07/25/89)
> /otter:comp.lang.misc / mwm@mica.berkeley.edu (Mike Meyer) / > The basic idea is to be able to code a state table as is, so that the > table is obvious. A two-dimensional switch statement is the analogy > that comes to mind. A typical example might look like: > > > switch (row:bumpx, col: bumpy) { > > case 0: case 3: case 5: case 7: > > case 2: z = x++ + y; z = 2 * x + y; z = 3 * x++ + y; z = x; > case 4: z = x + y; z = x + y++; z = 3 * x + y++; z = y; > case 7: z = x++ + y++; z = x + 2 * y; z = 8 * x++ + y++; z = x; > > } From your example, it looks as though you don't need anything more than pattern matching on the left-hand side of an equation: Eg, Prolog state_machine( 0, 2, Z ) :- Z is <expression> state_machine( 0, 4, Z ) :- Z is <expression> state_machine( 0, 7, Z ) :- Z is <expression> state_machine( 3, 2, Z ) :- Z is <expression> ... etc or, SML fun stateMachine 0 2 = <expression> | stateMachine 0 4 = <expression> | stateMachine 0 7 = <expression> | stateMachine 3 2 = <expression> ... etc Compiler technology for both languages is maturing, so they could each do a pretty good job of optimising the tests. I have left out the details of the <expressions> since good programming practice in each language avoids scungy imperative operators like ++. Adding the extra parameters to do it properly would obscure the point. Once upon a different life, I would have preferred to use Prolog. However, having been writing SML code for some time now, I like the mental hygiene of keeping the expressions type-correct, and having the compiler enforce that for me. In the above example, you wouldn't have to keep to integers for the case labels, but each parameter (effectively, every column in the above) would have to be the same type. In return, the compiler will warn when you have incomplete coverage of that type. If I missed the point of the question, please explain further. Cheers, Ian. | Ian Dickinson, HP Labs, Information Systems Centre, Bristol, England | | net: ijd%otter@hplabs.hp.com | | | or: ijd@hplb.uucp | ?- mind(X), body(X), spirit(X). | | These opinions are all my own work. | |
mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer) (07/26/89)
In article <2400025@otter.hpl.hp.com> ijd@otter.hpl.hp.com (Ian Dickinson) writes:
<> /otter:comp.lang.misc / mwm@mica.berkeley.edu (Mike Meyer) /
<> The basic idea is to be able to code a state table as is, so that the
<> table is obvious. A two-dimensional switch statement is the analogy
<
<From your example, it looks as though you don't need anything more than
<pattern matching on the left-hand side of an equation:
<
<If I missed the point of the question, please explain further.
I would like to thank those who answered, either here or by e-mail.
The original problem was poorly stated - mostly because I wasn't clear,
myself, on what the problem _was_. I now have a solution. I expect
theres a better one, but this one works.
Problem: Given two variables a, b that each have some finite set of A
& B, to be able to specify code to execute for each element of the AxB
set of possible values the two variables could have.
Goals: The user need not mention the possible values A and B more than
once, and that the must not be evaluated more than once.
The problem is, at heart, a notational problem: is there a notation
that fits the current 1-d array of characters that programming
languages are being forced into that would allow the obvious
"tableness" to show through, and still meet the goals above.
A variety of people pointed out that vectors (in various flavors) can
be used to solve this problem. These suffer from the user having to
specify translations from A & B to the indices of the vectors. Others
suggested variations on associative arrays, which avoids that problem.
However, these require the mention or evaluation of the elements of A
& B multiple times.
The solution appears to be to provide a template for the code
fragments in the switch. Staying with C, this would work in a manner
similar to array initialization. The first "dimension" of the switch
has unknown length, and labels specified by case's as they occur. The
other dimensions have labes/lengths specefied by a template at the
start of the switch, and each case statement marks the beginning of an
N-1d slice through the Nd table.
It's still not pretty, but it hands the whole mess to the compiler to
choose a good implementation for that example.
Thanx,
<mike
--
Il brilgue: les toves lubricilleux Mike Meyer
Se gyrent en vrillant dans le guave, mwm@berkeley.edu
Enmimes sont les gougebosqueux, ucbvax!mwm
Et le momerade horsgrave. mwm@ucbjade.BITNETleichter@CS.YALE.EDU (Jerry Leichter) (07/26/89)
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