Design Pattern Quandry

March 20, 2008 2:30 PM

Programming/design pattern question. Being self-taught, I've discovered a number of times I've labored over the solution to a problem only to discover a more elegant, standard design pattern already addresses the problem. I'm sort of hoping this is the case here.

What I want to do is provide a way for users to arbitrarily combine given numbers to generate meaningful-to-them numbers and have the means of doing this combining persist. For example, the application I have in mind stores counting statistics in baseball by player and date. As a user of this application, I'd like to be able to combine these stats in various ways that are more or less arbitrary from the application's POV. Many common formulas can be pre-programmed, i.e. OBP = (Hits + Walks + HBP ) / (AB + Sac + Walks + HBP). However, many may not be so easily anticipated, i.e. Quality Start = if( GS && (IP >= 6) && (ER <= 3) ) then return 1.

Instead of having to create a new class (oh, I'm using Java here) every time a user develops a new stat they'd like generated/displayed/scored in fantasy baseball, I'd like to develop a way to generate these classes/objects via the ui and then re-use them in subsequent user sessions. I can see how to do this in the UI using drag/drop or drop-down menus, but I don't know how to model this on the back end.

My present model suggests a class StatLine that is essentially a Collection of an arbitrary number of objects that implement a Stat interface. This interface describes methods like set/get value, get title/label, and get/set formula in addition to some other bookkeeping kinds of things like how to sort for scoring (ascending vs. descending). How to represent, store, and retrieve arbitrary formulas is the part that has me spinning in circles. It would seem that this is an ideal situation to use some combination of a properties file and reflection but the means have not yet come to me.

Something along the lines of:
public class AVG implements Stat {

public AVG( Stat Hits, Stat AB ) {
...

}

.... all kinds of getters and setters....

public Double getValue() {
...read some property that represents the formula and feed that formula to some kind of engine that returns the computed value...
}

}

It could be that I should drop the idea of making unique classes that implement the Stats interface for each statistic generated. Instead one could monkey together an engine that turned a string in to a calculation that is stored as a field in a Stats object. It just doesn't feel right though.

If you have run in to a pattern like this how did you solve it? What, if any, name does this design pattern have? What, if any, resources would you recommend for asking this question to a more specific audience?

posted by Fezboy! to computers & internet (12 comments total)

Embed a lua interpreter & store the query strings for later execution?
posted by pharm at 3:03 PM on March 20, 2008

It seems to me you either need to embed a language which can modify its own code, or you need to basically write an expression interpreter yourself. You write an engine that can handle any equation expressed within some rules, and then you store the expressions for use later.

Writing an interpreter is not hard. Parse through a string, at each point, identify the token. Is the token a value or an operator? A unary operator takes one argument, so do the requested operation on the one argument to the left or right of the operator, however it works. A binary operator takes two arguments... etc. You need to probably have a concept of recursion here to handle complex statements.

It both is and isn't hard to do, depending on your point of view. Knowing my solutions to programming problems however, this is probably the longest and most complicated route to the answer. :-)
posted by zhivota at 3:11 PM on March 20, 2008

Welcome to Java, The Kingdom of Nouns.

Now its been some time since I've dealt with Java, so some of this may be old and therefore no longer true, and I don't anything approaching a handle on the syntax any more, so forgive the English language psuedo-code.

Basically I think we're looking at two problems here.

Number one is how to make a class that implements the Stat interface but uses a different (and user contributed, and thus arbitrary) way of calculating what to put in a value field each time.

Ideally (and abstractly) what we'd like to be able to do here is to pass an arbitrary formula (ne function) and all the requisite Stat objects it needs to an ArbitraryStat object, which would then have all the calculation and storage action built into it, since it would also implement Stat.

The problem is that this isn't easy to do in Java (though it is considerably easier than it is in C++) because Java believes only data should be passed to functions, not functions. What you need to do is create an object with a single method called a functor, and then pass that to ArbitraryStat's constructor.

Problem two then becomes how to translate between what the user inputs (invariably a string of some sort) and an actual machine-readably Java function, which can then get passed (as a functor) to ArbitraryStat, along with the objects that function needs to calculate based upon. Of course, once you create these things, you'll need to get at them, so some sort of user-provided name would be nice: asTemp = ArbitraryStat( f, Object[] n, "Good Start");

Personally, I can't see much way around this without implementing some sort of parser. Now you could simplify things for yourself immensely by doing the UI with pull-downs rather than a free-form text field, so that the parser had only a VERY limited set of character patterns to recognize.

So you'd have "Stat = [pull-down for data] [pull-down for operator] [pulldown for data] [button to add a new operator & data pull-down pair]." ersomethin.

Now all that said, and again off the top of my head, its entirely likely that you'll run into some fairly hairy recursion, here. First off, I'd build that parser recursively, for a number of reasons, most notably due to the fact that you may want to add parentheses, which would mean essentially turning your input string into a tree structure. Second, ArbitraryStat should be able to accept any other ArbitraryStat as a parameter.

Now, if you were to implement all this in a functional language like Lisp, you might find things would be easier. As to the "smart people MUST have done this before now," see Google's MapReduce, the algorithm that makes Ridiculously Massive Parallel Processing go. (sorta).
posted by ChasFile at 3:29 PM on March 20, 2008 [1 favorite has favorites]

Check out javacc, it's a java parser generator. It allows you to develop your own syntax using a regular expression-like language embedded in your class and then takes the syntax and lets you execute arbitrary java for each token. It's nifty, though the learning curve is a little steep.
posted by roue at 4:19 PM on March 20, 2008

I think that all this talk of parsers may be a red herring. I think what you really want is the result of a parser, what is often called an abstract syntax tree --- whether you obtain the abstract syntax tree by parsing a string or by building it up from user clicks in a gui or whatever is irrelevant.

But in any event, to answer your question directly: yes, there is a design pattern that's meant for just this purpose, called the Interpreter Pattern (see also).
posted by jacobm at 4:36 PM on March 20, 2008

A parser generator is the thing you want if you want to convert user generated strings into useful structure. Basically you give it a grammer of rules that describe how to generate any legal string in you language:

expression := NUMBER |
expression '+' expression |
expression '-' expression |
expression '/' expression |
expression '*' expression

for example describes how to build expressions that are either numbers or arithmatic compositions of smaller expressions.

You also feed the parser generator some code that it runs whenever a rule gets applied so that you can get back the structure of the expression. For your application, you probably want to end up with a tree of objects that represent the overall expression, so you'd have code that would tell it to make a new NumberExpression and set its value whenever it uses the number rule or make a new PlusExpression and attach the subexpressions as children.

Each node in the tree will represent either a terminal thing (Hits, Walks, etc...) and have no children or a operator (+, -, /, ...) that combines the value of its children. When a node needs to compute its value, it returns it immediatly if it's a terminal thing or asks its children to compute their values, combines them according to what kind of opperator it represents,and returns that value.
posted by Diz at 4:42 PM on March 20, 2008

Don't bother putting in an extension language. Your user have to learn to use it and it costs you effort. You could just plug an java spreadsheet component in. Users understand spreadsheets and it save you programming time. Here's one. I haven't used it but there are plenty more that you can find by googling.
posted by rdr at 7:47 PM on March 20, 2008

You want an interpreter or a simple DSL, both of which are very painful to write in Java. I recommend going with JRuby instead, or just plain Ruby if you don't mind losing the JVM. It would make this much easier, and you'd learn a superior language to boot.
posted by rsanheim at 8:13 PM on March 20, 2008

Hmmm. What you basically want is a simple calculator. All the math that you want to do is more-or-less simple algebra, right? Stuff that even a cheap graphing calculator would have.

I don't know much about the Java community, but perhaps there's some sort of 3rd party calculator library that you can leverage. I'm sure that enough people have needed something like this to where somebody's done it before. If nothing else, I'm sure you could find a good algorithm for it in a CS book. Once you've found the algorithm, implementing it would be fairly trivial.

So yeah - try to find something that can do the work for you, and then adapt it.
posted by Afroblanco at 9:32 PM on March 20, 2008

I think some people may be over complicating the lex/parse approach. It has been a long time since I used Javacc but I've had more recent experience with SableCC, which is (as far as I am concerned) pretty easy to get going. Your grammar would be tiny and simple, as well, so it would take all of 20 minutes to write. The other option is to write your own in place "parser" - just spin through the expression string recursively, building a syntax tree as you go. It would probably amount to a switch on operators and a resolve stat for the variables. If you find a variable that doesn't resolve or an operator that falls off your switch, you tell the user they constructed an illegal stat.

Once you have a valid stat expression, you could just add it to a store, a file, or whathaveyou.. just re-parse each time the program loads up. Give the user the ability to label it in some meaningful way so that selecting it later is easy and intuitive.

But to answer the specific question, jacobm has it with the Interpreter Pattern
posted by mbatch at 6:41 AM on March 21, 2008

A parser's not hard to use if you've used one before. They're kind of daunting the first time. Whichever one you may use, they're all based on BNF grammars...

Here's a link that explains BNF grammars and how parsers work. Knowing this will make using a parser (or implementing your own) much easier.

That said, in your case, I would look hard for some basic arithmetic DSL first, or embed an interpreted language (as per LUA, JRuby, and spreadsheet suggestions above.. there's also Jython)

Also see CUP for Java.
posted by qxntpqbbbqxl at 7:23 AM on March 21, 2008

I just want to say that the powers that be should also have a flag for marking good answers that fill in any gaps because they've all been useful in some way. There's a bit of reading and some serious thinking to do this weekend which is great. I've been sitting on a plateau for a while programming-wise but recently have been challenged in some interesting ways. On the one hand I think I missed a lot by not getting a formal CS degree but on the other I've had many more moments like these where a simple-ish question really throws some doors open. There's a thrill that comes with being handed a whole new set of toys out of the blue. And if you haven't read ChasFile'a first link you really should.

For the time being: I think the project remains pretty squarely Java-based because there's a whole lot of infrastructure already in place w/r/t GUI and inter-widget communication and I'm probably not at a point where I'm willing to entertain integrating a melange of modules written in different languages. A parser of some sort will be built/used. An especially simple parser no doubt. I'm not sure about the implementation of that yet, but I can see how all the pieces work together now which is miles ahead of where I was when I asked this question.

Thanks!

which is not to say that if you have anything to add I wouldn't appreciate it. I just wanted to throw out an acknowledgment for all the good stuff that's already come my way.
posted by Fezboy! at 12:09 PM on March 21, 2008