Re: Design Patterns and Functional programming

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. 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;;

let rec loop() =
Printf.printf "> %!";
let x = Gram.parse expr Loc.ghost (Stream.of_string (input_line stdin)) in
Printf.printf "= %f\n%!" x;
loop();;

let () = loop()

BTW, in a real compiler you won't have them in the form you have
proposed.

Most compilers written in Standard ML, Haskell or OCaml use this form.
Indeed, this carries through to machine code generation as the machine
itself doesn't implement n-ary addition.

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

How do you add precedence to your design?

Precedence is implemented the same way in the functional and OO styles.
For programmatic construction, it is inherited from the use of infix
operators.

But your idea was to map that onto some [functional] language constructs,
which apparently do not take care of.

[...]

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

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?

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

--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?usenet
.