Re: Existence Based Polymorphism

"Decision tables aren't tables of function pointers ever. If you mean switch statements, then you're missing out on what a decision table means; it's more about providing zero or more reactions to an incoming data stream. They don't work on incoming streams of data then shunting off into other code, they merely provide a mechanism by which you can process what should be done given an incoming stream of state information."


Decision tables can be (and quite often are) of function pointers (or in some cases just a label address) to drive program logic based on a stream of data. This method is used for pattern matching (as seen in functional languages like Haskell/F#), handling network protocols and is also often used in interpreter implementations. In fact, the generalization of virtual functions to multiple dispatch is often implemented with decision tables. 

Looking at the wikipedia link you provided below, they even provide an example of the case where a decision table is used to drive program logic like this.

"This does in turn lead to good possibilities for state transition engines, which is why I say it's stronger than virtual function oriented polymorphism, but the technique never actually hits logic as the arguments for the decision tables to work on are produced by processing the potential set, and the outputs are used to built a processing set. What the processing is on either side of a decision table processing stage is arbitrary."

Don't get me wrong, decision tables are great for state transition systems and enumerating complex logic in an easy to understand way. They can also make for a great data driven system/DSL (which would work well for designers).  

"I've come up with a solution to the problem of large tables that literally just involves using a tri state bool for the argument comparison. It's very hard to make that table big enough to not fit in cache."

Can this method easily support condition alternatives that aren't booleans? It's quite common to use an enumeration as the input for a condition alternative (where instead of just having Y/N, you have 0 1 2 3 or other discrete values) and in the case of parsers/regex, a whole character!   

"there's hardly any code to run on a decision table, all you're doing is converting arguments to decisions."

Well, as I said earlier, I thought because you would be converting them to decisions that happened to point to code, which is what a lot of people use them for.  
 
"I think we can still maintain that OO virtual function driven development is good for very high level development where abstraction is paramount."

Very much agreed. I don't think they're always bad at low levels either, they just have to be used very judiciously. 

"I have a feeling our definitions of decision tables aren't quite in alignment, I only learnt about the term a few months ago, so I may be using it wrong, but here's how I understand it:


http://www.methodsandtools.com/archive/archive.php?id=39
http://en.wikipedia.org/wiki/Decision_table

worthy of  note is that in most cases, output from a decision table is not limited to 1 decision, it can be anywhere from zero upwards."

Okay, the other important thing to remember is that the condition alternatives and the actions can essentially be of any type (and it's not even uncommon to see "fuzzy" condition alternatives). All a decision table is, is a mapping of a compound key of possible input conditions to a set of output actions (however you wish to describe an action). The boolean representations (where you map a simple set of "yes"/"no" conditions in all permutations to another set of "yes"/"no" telling you what actions you wish to perform are the simplest form.   

The typical implementation for a decision table is a compound binary key with all the conditional alternatives encoded into a single integer, which is then used to lookup the table. The table can obviously then be whatever you're encoding your resulting action as (a function pointer representing the action to take, an array of function pointers representing multiple actions to take, an integer bitflag for a set of actions, a set of parameters for another function). 

Lex and Yacc use decision tables based on characters and symbols (respectively) for the deterministic FSAs they use for parsing (although Yacc uses a stack as well). In the case of lexers, part of the action for the previous character is used as part of the condition for the next decision and this is how sequenced rules are matched.

Cheers,
Conor

_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com