Re: String Processing Challenge

On Feb 5, 6:58 pm, "JOG" <j..._at_cs.nott.ac.uk> wrote:
> On Feb 5, 7:06 am, "David BL" <davi..._at_iinet.net.au> wrote:
>
> > 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.
>
> I am unclear at to the utility of the comparison that would be made
> here? Given the remit of relational theory is data storage, integrity
> and manipulation,

It is sometimes necessary for text to need to persist, have strong integrity constraints, and need manipulation. Source code is a fine example. Therefore on its face, your characterisation (of the remit of relational theory) encompasses string modelling and processing.

> the only part of the comparison which makes sense to
> me is encoding the original string expression as a null-terminated
> character array versus an indexed relation.

It wasn't suggested that there are advantages to physically storing a string as an indexed relation. Instead it was suggested there might be advantages to dealing with strings relationally at a logical level on the assumption that a compiler will be free to choose an efficient implementation.

> In which case I could
> write something like the boost::spirit library (highly recommended by
> the way to anyone doing any language parsing) to do the BNF
> interpretation - /whichever/ string representation I use
Received on Mon Feb 05 2007 - 12:57:29 CET