Re: Design Patterns and Functional programming

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?

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.

Think about optimizations made later during code generation. You would
really wish to factorize infix commutative operators like a+b+c+d out into
Sum(a,b,c,d). The number of arguments becomes variable.

If you wanted to do that then it is easy enough. Replace the binary Add
constructor with:

| Sum of expr * expr list

I don't think there is any point though.

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.
For parsing, use yacc and specify the operator precedences.

Association order?

Add clauses to rotate the abstract syntax tree as it is constructed:

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

| Mul(f, Mul(g, h)) -> f *: g *: h

Association checks? [this is when x and y or z is illegal without
brackets]

That is a check in the parser. Nothing to do with functional vs OO designs.

What about types and types matching?

Type constructors handle run-time types. The pattern matches handle
deconstruction of boxes values (type matching). If you want static typing
then you must design and implement a static type checker in OCaml/SML/F#.
In Haskell, you can embed the static type system of a domain specific
language in Haskell's own type system and get it to do the static type
checking for you (Google for "GADTs"). The same can be done in C++ using
template metaprogramming. This is not related to functional vs OO style.

Reasonable error diagnostic and recovery?

This is mostly automated by the "scrap your boilerplate" techniques in
Haskell and OCaml. This is not related to functional vs OO style.

Array aggregates?

Add a constructor to the expr type:

# type expr =
| Int of int
| Array of expr array
| Add of expr * expr
| Mul of expr * expr;;

Literals?

Add a rule to the grammar with an action that uses the Array constructor.

Function calls?

See the complete interpreter in this post for a working example.

Keyed parameter association? Defaulted parameters?

Implementation dependent: what semantics would you like them to support?

Do you honestly believe that a syntax + semantic analyzer can be 100 lines
long?

I've attached a 49-line interpreter for a dynamically-typed purely
functional programming language.

If not, then what about readability, maintainability, reuse etc?

In this context, all much better with a functional style. This family of
languages were designed for compiler writing...

Object-oriented only means that the tree and its nodes are considered
objects of some types.

Yes. An object oriented approach can be quite devastating to readability and
maintainability, as I'm sure you'll agree if you try implementing this
simple functionality in an entirely OO style.

The following is a complete term-level interpreter for a dynamically-typed
functional programming language that supports higher-order functions and
currying:

open Camlp4.PreCast;;

let expr = Gram.Entry.mk "expr";;
EXTEND Gram
expr:
[ "prog" NONA
[ "if"; p = expr; "then"; t = expr; "else"; f = expr -> `If(p, t, f)
| "let"; "rec"; f = LIDENT; x = LIDENT; "="; body = expr; "in"; rest =
expr ->
`LetRec(f, x, body, rest) ]
| "equal" LEFTA
[ e1 = expr; "="; e2 = expr -> `Equal(e1, e2) ]
| "sum" LEFTA
[ e1 = expr; "+"; e2 = expr -> `Add(e1, e2)
| e1 = expr; "-"; e2 = expr -> `Add(e1, `Mul(`Int(-1), e2)) ]
| "product" LEFTA
[ e1 = expr; "*"; e2 = expr -> `Mul(e1, e2) ]
| "apply" LEFTA
[ e1 = expr; e2 = expr -> `Apply(e1, e2) ]
| "simple" NONA
[ v = LIDENT -> `Var(v)
| n = INT -> `Int(int_of_string n)
| "("; e = expr; ")" -> e ] ];
END;;

(* Evaluator *)
let int = function `Int n -> n | _ -> invalid_arg "int";;
let bool = function `Bool b -> b | _ -> invalid_arg "bool";;

let rec eval vars = function
| `Apply(func, arg) -> apply (eval vars func) (eval vars arg)
| `Add(e1, e2) -> `Int (int(eval vars e1) + int(eval vars e2))
| `Mul(e1, e2) -> `Int (int(eval vars e1) * int(eval vars e2))
| `Equal(e1, e2) -> `Bool (eval vars e1 = eval vars e2)
| `If(p, t, f) -> eval vars (if bool (eval vars p) then t else f)
| `Int i -> `Int i
| `LetRec(var, arg, body, rest) ->
let rec vars' = (var, `Closure(arg, vars', body)) :: vars in
eval vars' rest
| `Var s -> List.assoc s vars
and apply func arg = match func with
| `Closure(var, vars, body) -> eval ((var, arg) :: vars) body
| _ -> invalid_arg "Attempt to apply a non-function value";;

(* Top level *)
let string_of_value = function
| `Int n -> string_of_int n
| `Bool true -> "true"
| `Bool false -> "false"
| `Closure _ -> "<fun>";;

let () =
let program = Gram.parse expr Loc.ghost (Stream.of_channel stdin) in
let vars = ["true", `Bool true; "false", `Bool false] in
print_endline(string_of_value(eval vars program));;

This can interpret the following program, for example:

let rec fib n =
if n=0 then 0 else
if n=1 then 1 else
fib(n - 1) + fib(n - 2) in
fib 35

What would the equivalent be in an object oriented design?

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