String Processing Challenge
Date: 4 Feb 2007 23:06:06 -0800
Message-ID: <1170659166.412183.318960_at_h3g2000cwc.googlegroups.com>
In the recent thread "Objects and relations" Marshall and I had an interesting discussion about whether RM/RA is suitable for string processing. I feel that the examples we used for comparison were overly simple. For my own part I'm still left wondering how RM can be easily applied in more complex problems.
I have chosen a practical example of string processing that allows for reasonably concise solutions in OO, FP and LP styles. The existence of concise FP and LP solutions show that the problem is well described declaratively or logically. ie it is not specifically suitable for procedural solutions.
Problem specification: Given a string that is an infix expression using the binary operators *,/,+,-, unary operators +,- and literal integers in base 10, calculate the result as an integer following BIMDAS / PEMDAS (or whatever you call it). Assume "/" designates integer division. For simplicity assume that the expression is well formed, there is no exponentiation, there is no division by zero and ignore overflow when using a native integer type.
The following EBNF grammar is assumed
Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
LiteralInteger =
Digit |
LiteralInteger Digit;
Expr = AdditiveExpr;
AdditiveExpr = MultiplicativeExpr { ("+" | "-") MultiplicativeExpr };
MultiplicativeExpr = PrimExpr { ("*" | "/") PrimExpr };
PrimExpr =
LiteralInteger |
("+" | "-") PrimExpr |
"(" Expr ")";
If anyone is happy to take the challenge I'm happy to develop and post a C++ solution that can be compared to some relational solution. It would also be interesting to see solutions in other languages.
I suggest that the comparison be based primarily on simplicity, expressiveness and clarity, and not on performance given the lack of a mature language and compiler for an RM based approach. Also the relational solution is free to introduce its own language constructs, perhaps making use of FP,LP or even some OO given that RA is not Turing complete. In other words a hybrid solution is allowable. Received on Mon Feb 05 2007 - 08:06:06 CET