Re: Design Patterns and Functional programming

On Sun, 08 Jul 2007 20:55:13 +0100, Jon Harrop wrote:

Dmitry A. Kazakov wrote:
On Sun, 08 Jul 2007 18:35:51 +0100, Jon Harrop wrote:
Dmitry A. Kazakov wrote:
How do you add that to the object oriented design?

No problem actually. You first derive from abstract expression an
abstract infix operation (that is - two arguments one result) and then
specialize it to concrete operation.

Could you post working code for that design, please?

http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc

It contains a complete sample for building parsing trees of Ada 95 infix
expressions with all bells and whistles.

Note that my post that you were replying to was about a term rewriter rather
than a parser.

That should not change much.

Regardless, parsing is another interesting example. I
believe your 239-line Ada program is equivalent to the following 23-line
OCaml program:

open Camlp4.PreCast;;

let expr = Gram.Entry.mk "expr";;

EXTEND Gram
expr:
[ "sum" LEFTA
[ e1 = expr; "+"; e2 = expr -> e1 +. e2
| e1 = expr; "-"; e2 = expr -> e1 -. e2 ]
| "product" LEFTA
[ e1 = expr; "*"; e2 = expr -> e1 *. e2
| e1 = expr; "/"; e2 = expr -> e1 /. e2 ]
| "power" LEFTA
[ e1 = expr; "**"; e2 = expr -> e1 ** e2 ]
| "simple" NONA
[ n = INT -> float_of_string n
| x = FLOAT -> float_of_string x
| "("; e = expr; ")" -> e ] ];
END;;

The above is not the Ada's grammar, which is far more complex. See

http://www.cs.vu.nl/grammars/ada/#gdef:expression

The problem is in additional constraints, like a**-b (illegal). This is the
problem with grammars, which turn very verbose on real-life examples. You
cannot come away with just one "expr."

Further, diagnostics will be a mess, because in the above you have only
match or no match, while what is required is a lot of semi-match states
where you could hint the user what was wrong. This is where internal states
shine.

Yes, but you definitely wanted to fold constants in expressions like
1+a+2.

You might want to do that. If you do, just sort by commuting and the
existing reduction rules will take care of constant folding. Something like
this:

| Add(Add(f, g), h) when g>h -> f +: h +: g
| Add(f, g) when f>g -> g +: f

What about 1+b+a+2? What about 1-b+a-2? The approach does not scale. Which
is the point. There are many languages in which you can solve some simple
task in few lines. But this does not imply that you could get a quality
production code in any reasonable time. You certainly know the 80/20 law.
Software design is not about that 80%, it is about what to do with these
damned 20% of the rest.

[Please, don't consider this as a language flame, I have nothing against
"oh, calm" (:-)) et al. Just, code snippets prove nothing.]

If we're talking about parsers then the handling of precedence levels should
be clear from the above example.

Yep, you can trash them into the grammar, and in fact, people are doing
this all the time. But the result will most likely be an unreadable mess,
which is again the point.

What would the equivalent be in an object oriented design?

Follow the link I have provided. The focus of the design was to avoid
hard-coded grammar. Therefore decomposition goes along different lines. It
is operations, arguments, sources and parsers. The approach is
table-driven, that is - lexical elements, like infix operations, their
precedence are defined dynamically. Static are only the classes of, like
operator, bracket, comma, ligature. This gives you the operation and
argument stack objects in a fully generic way.

Does that design have any advantages over the functional solution above?

Yes, because of code reuse. It is modular, you don't need to rewrite (and
to test) all the code in order to parse, say C++. Other issues are
diagnostics, consider marking up the errors in the source. (BTW, what is a
functional equivalent to "marking in"? (:-)) Error recovery, what about
skipping to the end of the expression? You need two different grammars for
this and switching forth and back. To colorize the source there would be a
third grammar, and don't forget expansion of the methods when the cursor
hovers over... (Uhmm, "to hover" is it functional? (:-))

I would still be interested to see an object oriented equivalent to the term
rewriter. :-)

Rewriter is defined as a function, its OO equivalent would be again a
function. Don't expect me reinventing wheels. (:-))

But, what about sets of rewriters?

1. How would you describe a class of, with certain properties? How a user
of the class could design a program in terms of these properties?

2. How would you extend / modify a rewriter? When you have it as a
function, there is little you could do with it beyond construction of a
composition with some another function.

If you wanted to "programmatically" look into a rewriter, then it would
become interesting. You could decompose it functional, you could do it as a
state machine, you could use a stack automat.

OO does not limit you here in any way. Probably differently to some people
here, I don't see any opposition between FP and OO. You don't like stateful
objects? I don't either. But I see reasons when an object should better
have a state.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
.