Re: [Caml-list] Rule based language [was: productivity improvement]

Re: [Caml-list] Rule based language [was: productivity improvement]

[sajuma]

[-- Attachment #1: Type: text/plain, Size: 3387 bytes --]

> > > This looks pretty simple. What makes you think the program is a
> > > compelling evidence of O'Caml superior productivity?

> > 197 lines of code, including whitespace and commments. I
> > think it is a pretty clear example of how you can write cool
> > software in O'Caml in a very short time. If you had not been
> > "lazy", as you said, and had tried implementing the same
> > language in C++, I strongly doubt you could have written a
> > more compact source.

> 109 LOC in C++ counting blank lines and lines containing a single
> '}'. See atttached files.
 
> A few notes about the differences between your O'Caml program and
> my C++ 
> program: 

> 1) I'm not using Yacc or Lex for parsing, because I'm not familiar
> with these 
> tools, so ugly parsing takes up most of those 109 LOC (Parsing
> things is 
> peripheral to my professional interests right now. I don't write
> compilers)

I think that the difference of parsing code
illustrates the difference between imperative and functional programming:
C++ code has no clear structure and it's parts do not have simple meanings.
In O'Caml code, the parser is combined from smaller parts and every parser
has a simple meaning. Same kind of code could be written in C++ too, but
C++ doesn't support functional style good enough to make this normal.

> 2) I decided not to implement the "simple" keyword, because I did
> not understand what it was supposed to mean (a depth limit on
> deduction, I'm guessing, but what for?)

I think you misunderstood the specification of the language.
(It was not very clear). The meaning of "a and b" should not
be "a is reachable and b is reachable" (additive and), but
"a and b are true at the same time" (multiplicative and).
Of course I could be mistaken too, but the multiplicative case
is more interesting.

> 4) The algorithms are different I think, resulting in, for example,
> about 200x speed improvement for the attached test.input file on my
> P3-800MHz (g++-3.0 vs ocamlopt) (The output is identical).  The O'Caml
> program convergence seems to be quite unstable. Sometimes it is as
> fast or even faster than the C++ program. 

The examples are too simple to show the difference. I have made a new
example that can detect the difference, and also has a big enough
search space.

> I can see how the same algorithm can be implemented in ~100 LOC of
> O'Caml too. However, IMO as this and the previous examples show, reports
> about extreme LOC ratios are premature.

The previous example shows that converting simple pattern
matching to C++ makes it twice as long, unreadable, and
still doesn't implement all the functionality.

Anyway, problems in memory management and modularity
only appear when the programs become big. Usually big
programs are not written in two languages, so comparison
is hard. But the example of Horus vs. Ensemble shows that
there is very large improvement. Ensemble and other big O'Caml
programs could probably be converted to C without making them much
bigger, but they would become unreadable and unmaintainable.

Here is a question: in C you can hack in all the object
oriented features, so why are you using C++? Many claim that
OOP in C is better than in C++, so what would you say to these
people? Perhaps we could then tell you why you should use O'Caml.
All I can say now is that O'Caml has been a massive productivity
improvement for me.

[-- Attachment #2: rules.ml --]
[-- Type: application/octet-stream, Size: 3445 bytes --]


open Genlex

let rec cond2 = parser
 | [< 'Ident "and"; 'Ident x; xs = cond2 >] -> x::xs
 | [< >] -> []

let cond = parser [< 'Ident x; xs = cond2 >] -> x::xs | [< >] -> []

let token = parser [< 'Ident i >] -> i | [< 'Int i >] -> string_of_int i

let goal = parser
 | [< 'Ident "simple"; gn = token; 'Ident "is"; l = cond; 'Kwd ";" >] ->
   (true,gn,l)
 | [< gn = token; 'Ident "is"; l = cond; 'Kwd ";" >] -> (false,gn,l)

let rec goals = parser
 | [< g = goal; gs = goals >] -> g::gs
 | [< _ = Stream.empty >] -> []

let rec dataset = parser
 | [< 'Ident "goals"; 'Kwd ":" >] -> []
 | [< 'Ident d; 'Kwd ";"; ds = dataset >] -> d::ds

let rule = parser
 | [< rn = token; 'Ident "is"; pre=cond; 'Kwd "=>"; post=cond; 'Kwd ";" >] ->
   (rn,pre,post)

let rec rules = parser
 | [< 'Ident "dataset"; 'Kwd ":" >] -> []
 | [< r = rule; rs = rules >] -> r::rs

let ruleset = parser [< 'Ident "ruleset"; 'Kwd ":"; lst = rules >] -> lst

let program = parser
 | [< rs = ruleset; ds = dataset; gs = goals >] -> (rs, ds, gs)

type rule = { name : string; dlist : int array; alist : int array }

let set_bit x i = i lor (1 lsl x)

let add_list list x = list.(x / 31) <- set_bit (x mod 31) list.(x / 31)

let add x y = Array.mapi (fun i x -> x lor y.(i)) x
let minus x y = Array.mapi (fun i x -> x land (lnot y.(i))) x

let includes x y =
  let res = ref true in
  for i = 0 to Array.length x - 1 do
    if (lnot x.(i)) land y.(i) <> 0 then res := false
  done;
  !res

let states = Hashtbl.create 1000

let apply_rule state {dlist=dlist;alist=alist} =
  if includes state dlist then Some (add (minus state dlist) alist) else None

let rec search goal state rules =
  if includes state goal then Some [] else
  if Hashtbl.mem states state then None else
  let _ = Hashtbl.add states state () in
  let rec try_rules = function
   | [] -> None
   | r::rs when includes state r.dlist ->
     ( match search goal (add (minus state r.dlist) r.alist) rules with
     | None -> try_rules rs
     | Some p -> Some (r.name::p) )
   | _::rs -> try_rules rs in
  try_rules rules

let rec simple state rules =
  let (changed,state) = List.fold_left (fun (ch,state) r ->
    match apply_rule state r with
     | None -> (ch,state)
     | Some nstate -> (true,nstate)) (false,state) rules in
  if changed then simple state rules else state

let test_simple state goal rules =
  if includes (simple state rules) goal then "found" else "not found"

let test_normal state goal rules =
  Hashtbl.clear states;
  match search goal state rules with
  | None -> "not found"
  | Some plan -> String.concat "; " plan

let table = Hashtbl.create 100 and uniq = ref 0

let new_id name =
  if not (Hashtbl.mem table name) then (Hashtbl.add table name !uniq; incr uniq)

let make_list names =
  let arr = Array.make (!uniq/31 + 1) 0 in
  List.iter (fun n -> add_list arr (Hashtbl.find table n)) names; arr

let compile rs state =
  List.iter (fun (_,a,b) -> List.iter new_id (a@b)) rs; List.iter new_id state;
  List.map (fun (n,a,b) -> {name=n; dlist=make_list a; alist=make_list b}) rs,
  make_list state

let _ =
  let st = Stream.of_channel stdin in
  let (rs,ds,goals) = program (make_lexer [";"; ":"; "=>"] st) in
  let rules, state = compile rs ds in
  let test_goal (s,gn,g) =
    let goal = make_list g in
    print_string ("Goal " ^ gn ^ ": " ^
      (if s then test_simple state goal rules
       else test_normal state goal rules) ^ "\n") in
  List.iter test_goal goals


[-- Attachment #3: pigeons.prog --]
[-- Type: application/octet-stream, Size: 3567 bytes --]

ruleset:

to_1_1 is p_1 and h_1 => i_1_1;
from_1_1 is i_1_1 => p_1 and h_1;
to_1_2 is p_1 and h_2 => i_1_2;
from_1_2 is i_1_2 => p_1 and h_2;
to_1_3 is p_1 and h_3 => i_1_3;
from_1_3 is i_1_3 => p_1 and h_3;
to_1_4 is p_1 and h_4 => i_1_4;
from_1_4 is i_1_4 => p_1 and h_4;
to_1_5 is p_1 and h_5 => i_1_5;
from_1_5 is i_1_5 => p_1 and h_5;
to_1_6 is p_1 and h_6 => i_1_6;
from_1_6 is i_1_6 => p_1 and h_6;
to_1_7 is p_1 and h_7 => i_1_7;
from_1_7 is i_1_7 => p_1 and h_7;

to_2_1 is p_2 and h_1 => i_2_1;
from_2_1 is i_2_1 => p_2 and h_1;
to_2_2 is p_2 and h_2 => i_2_2;
from_2_2 is i_2_2 => p_2 and h_2;
to_2_3 is p_2 and h_3 => i_2_3;
from_2_3 is i_2_3 => p_2 and h_3;
to_2_4 is p_2 and h_4 => i_2_4;
from_2_4 is i_2_4 => p_2 and h_4;
to_2_5 is p_2 and h_5 => i_2_5;
from_2_5 is i_2_5 => p_2 and h_5;
to_2_6 is p_2 and h_6 => i_2_6;
from_2_6 is i_2_6 => p_2 and h_6;
to_2_7 is p_2 and h_7 => i_2_7;
from_2_7 is i_2_7 => p_2 and h_7;

to_3_1 is p_3 and h_1 => i_3_1;
from_3_1 is i_3_1 => p_3 and h_1;
to_3_2 is p_3 and h_2 => i_3_2;
from_3_2 is i_3_2 => p_3 and h_2;
to_3_3 is p_3 and h_3 => i_3_3;
from_3_3 is i_3_3 => p_3 and h_3;
to_3_4 is p_3 and h_4 => i_3_4;
from_3_4 is i_3_4 => p_3 and h_4;
to_3_5 is p_3 and h_5 => i_3_5;
from_3_5 is i_3_5 => p_3 and h_5;
to_3_6 is p_3 and h_6 => i_3_6;
from_3_6 is i_3_6 => p_3 and h_6;
to_3_7 is p_3 and h_7 => i_3_7;
from_3_7 is i_3_7 => p_3 and h_7;

to_4_1 is p_4 and h_1 => i_4_1;
from_4_1 is i_4_1 => p_4 and h_1;
to_4_2 is p_4 and h_2 => i_4_2;
from_4_2 is i_4_2 => p_4 and h_2;
to_4_3 is p_4 and h_3 => i_4_3;
from_4_3 is i_4_3 => p_4 and h_3;
to_4_4 is p_4 and h_4 => i_4_4;
from_4_4 is i_4_4 => p_4 and h_4;
to_4_5 is p_4 and h_5 => i_4_5;
from_4_5 is i_4_5 => p_4 and h_5;
to_4_6 is p_4 and h_6 => i_4_6;
from_4_6 is i_4_6 => p_4 and h_6;
to_4_7 is p_4 and h_7 => i_4_7;
from_4_7 is i_4_7 => p_4 and h_7;

to_5_1 is p_5 and h_1 => i_5_1;
from_5_1 is i_5_1 => p_5 and h_1;
to_5_2 is p_5 and h_2 => i_5_2;
from_5_2 is i_5_2 => p_5 and h_2;
to_5_3 is p_5 and h_3 => i_5_3;
from_5_3 is i_5_3 => p_5 and h_3;
to_5_4 is p_5 and h_4 => i_5_4;
from_5_4 is i_5_4 => p_5 and h_4;
to_5_5 is p_5 and h_5 => i_5_5;
from_5_5 is i_5_5 => p_5 and h_5;
to_5_6 is p_5 and h_6 => i_5_6;
from_5_6 is i_5_6 => p_5 and h_6;
to_5_7 is p_5 and h_7 => i_5_7;
from_5_7 is i_5_7 => p_5 and h_7;

to_6_1 is p_6 and h_1 => i_6_1;
from_6_1 is i_6_1 => p_6 and h_1;
to_6_2 is p_6 and h_2 => i_6_2;
from_6_2 is i_6_2 => p_6 and h_2;
to_6_3 is p_6 and h_3 => i_6_3;
from_6_3 is i_6_3 => p_6 and h_3;
to_6_4 is p_6 and h_4 => i_6_4;
from_6_4 is i_6_4 => p_6 and h_4;
to_6_5 is p_6 and h_5 => i_6_5;
from_6_5 is i_6_5 => p_6 and h_5;
to_6_6 is p_6 and h_6 => i_6_6;
from_6_6 is i_6_6 => p_6 and h_6;
to_6_7 is p_6 and h_7 => i_6_7;
from_6_7 is i_6_7 => p_6 and h_7;

to_7_1 is p_7 and h_1 => i_7_1;
from_7_1 is i_7_1 => p_7 and h_1;
to_7_2 is p_7 and h_2 => i_7_2;
from_7_2 is i_7_2 => p_7 and h_2;
to_7_3 is p_7 and h_3 => i_7_3;
from_7_3 is i_7_3 => p_7 and h_3;
to_7_4 is p_7 and h_4 => i_7_4;
from_7_4 is i_7_4 => p_7 and h_4;
to_7_5 is p_7 and h_5 => i_7_5;
from_7_5 is i_7_5 => p_7 and h_5;
to_7_6 is p_7 and h_6 => i_7_6;
from_7_6 is i_7_6 => p_7 and h_6;
to_7_7 is p_7 and h_7 => i_7_7;
from_7_7 is i_7_7 => p_7 and h_7;

dataset:

p_0;
p_1;
p_2;
p_3;
p_4;
p_5;
p_6;
p_7;
h_0;
h_1;
h_2;
h_3;
h_4;
h_5;
h_6;
h_7;

goals:

x is i_1_1 and i_2_2 and i_3_3 and i_4_4 and i_5_5 and i_6_6 and i_7_7;
y is i_1_1 and i_2_2 and i_3_3 and i_4_4 and i_5_5 and i_6_6 and i_7_6;
z is i_1_1 and i_1_2 and i_3_3 and i_4_4 and i_5_5 and i_6_6 and i_7_7;

Re: [Caml-list] Rule based language [was: productivity improvement]

[Oleg]

On Wednesday 24 July 2002 06:31 pm, sajuma@utu.fi wrote:
> I think you misunderstood the specification of the language.
> (It was not very clear). The meaning of "a and b" should not
> be "a is reachable and b is reachable" (additive and), but
> "a and b are true at the same time" (multiplicative and).
> Of course I could be mistaken too, but the multiplicative case
> is more interesting.

I did not misunderstand. I use multiplicative AND. All three programs give 
equivalent output when they all finish for all cases I looked at. 

However, your and Alex's programs, for examle, fail to finish processing this 
file containing 9000 rules with preconditions of lengths 1 to 10, 10 goals 
and 10 dataset points. (My patience ran out after 72 and 45 minutes of 
waiting for your and Alex's programs, respectively):

http://www.columbia.edu/~ot14/rules_test_long.input.gz (152 kB), 

while mine takes only 4 seconds. Something to think about [1]

> Here is a question: in C you can hack in all the object
> oriented features, so why are you using C++? Many claim that
> OOP in C is better than in C++, so what would you say to these
> people?

I'd ask them if they were on any special medication.

Cheers,
Oleg

[1] As I said, I certainly do not blame O'Caml for this. Just poor choice of 
algorithm.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Rule based language

[sajuma]

> I did not misunderstand. I use multiplicative AND. All three
> programs give equivalent output when they all finish for all
> cases I looked at. 

If you only looked cases like your "test.input",
they are not very reliable, because all the
satisfiable goals are in the dataset at the beginning,
and other goals are not reachable at all.
I guess none of the other goals is actually on the right side
of the rules.

OTOH my pigeons example shows the difference:

./rules < pigeons.prog
Goal x: found
Goal y: found
Goal z: found

./rules.opt < pigeons.prog
Goal x: (big plan found by dfs)
Goal y: not found
Goal z: not found

For some reason you missed my attachment or
you have changed your program after sending
it to the list.

Here is a more simple example that shows the difference:

------------------------------
ruleset: 1 is a => b;
dataset: a;
goals: g is a and b;
------------------------------

The meaning of Rule 1 is that if "a" is in the dataset, then
it is removed from the dataset, and "b" is added to the
dataset.

The meaning of goal "g" is that both "a" and "b" are
in the dataset after some sequence of rule activations.
In this case, additive and multiplicate readings are
different, because it is possible to reach both "a" and "b",
but they cannot coexists.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Rule based language

[Oleg]

On Thursday 25 July 2002 09:30 am, sajuma@utu.fi wrote:
> ruleset: 1 is a => b;
> dataset: a;
> goals: g is a and b;
> ------------------------------
>
> The meaning of Rule 1 is that if "a" is in the dataset, then
> it is removed from the dataset, and "b" is added to the
> dataset.
>
> The meaning of goal "g" is that both "a" and "b" are
> in the dataset after some sequence of rule activations.
> In this case, additive and multiplicate readings are
> different, because it is possible to reach both "a" and "b",
> but they cannot coexists.

I'm glad we straightened this out. In my program 

"a", "b", etc. are logical variables
"and" is logical AND (aka "multiplication")
"=>" is logical inference

Cheers,
Oleg
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] Rule based language

[Francois Rouaix]

Could you guys take your challenge discussions of the
Caml list ? At this point it doesn't really have to do
with Caml. Maybe when you're done competing and
comparing...
Thanks,

François Rouaix
(310) 316 9529
http://www.rouaix.org/fmr/ 

> -----Original Message-----
> From: owner-caml-list@pauillac.inria.fr 
> [mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of Oleg
> Sent: Thursday, July 25, 2002 11:16 AM
> To: sajuma@utu.fi
> Cc: caml-list@inria.fr
> Subject: Re: [Caml-list] Rule based language
> 
> 
> On Thursday 25 July 2002 09:30 am, sajuma@utu.fi wrote:
> > ruleset: 1 is a => b;
> > dataset: a;
> > goals: g is a and b;
> > ------------------------------
> >
> > The meaning of Rule 1 is that if "a" is in the dataset, then
> > it is removed from the dataset, and "b" is added to the
> > dataset.
> >
> > The meaning of goal "g" is that both "a" and "b" are
> > in the dataset after some sequence of rule activations.
> > In this case, additive and multiplicate readings are
> > different, because it is possible to reach both "a" and "b",
> > but they cannot coexists.
> 
> I'm glad we straightened this out. In my program 
> 
> "a", "b", etc. are logical variables
> "and" is logical AND (aka "multiplication")
> "=>" is logical inference
> 
> Cheers,
> Oleg
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: 
> http://caml.inria.fr
> Bug reports: 
> http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> 
> 
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] productivity improvement (was: Rule based language)

[Oleg]

On Wednesday 24 July 2002 06:31 pm, sajuma@utu.fi wrote:

> Anyway, problems in memory management and modularity
> only appear when the programs become big. Usually big
> programs are not written in two languages, so comparison
> is hard. But the example of Horus vs. Ensemble shows that
> there is very large improvement. 

Do you have links/references? (Although the fact that ML is more productive 
than C is quite believable to me) I found Horus/Ensemble web site. It looks 
like it has not been updated in 5 years[1] 

> [...] why are you using C++? 

It's very easy to give simple examples of when C++ is much more productive 
than C in programs defined by their I/O (If anyone needs such examples: a) 
reverse a file, b) reverse lines in a file c) /usr/bin/sort ). The situation 
seems to be different with O'Caml vs C++.

Regards,
Oleg

[1] Maybe the complexity has cought up with them eventually :)
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Rule based language [was: productivity improvement]

[Arturo Borquez]

Oleg <oleg_inconnu@myrealbox.com> wrote:

>On Sunday 21 July 2002 09:00 am, Alessandro Baretta wrote:
>> Oleg wrote:
>> > Alex,
>> >
>> > This looks pretty simple. What makes you think the program is a
>> > compelling evidence of O'Caml superior productivity?
>>
>> 197 lines of code, including whitespace and commments. I
>> think it is a pretty clear example of how you can write cool
>> software in O'Caml in a very short time. If you had not been
>> "lazy", as you said, and had tried implementing the same
>> language in C++, I strongly doubt you could have written a
>> more compact source.
>
>
>109 LOC in C++ counting blank lines and lines containing a single '}'. See 
>atttached files.
>
>A few notes about the differences between your O'Caml program and my C++ 
>program: 
>
>1) I'm not using Yacc or Lex for parsing, because I'm not familiar with these 
>tools, so ugly parsing takes up most of those 109 LOC (Parsing things is 
>peripheral to my professional interests right now. I don't write compilers)
>
>2) I decided not to implement the "simple" keyword, because I did not 
>understand what it was supposed to mean (a depth limit on deduction, I'm 
>guessing, but what for?)
>
>3) Your program fails to imlement multi-token post-conditions in rules and 
>mutli-token goals (as described in your formal language specification)
>
>4) The algorithms are different I think, resulting in, for example, about 
>200x speed improvement for the attached test.input file on my P3-800MHz 
>(g++-3.0 vs ocamlopt) (The output is identical).  The O'Caml program 
>convergence seems to be quite unstable.  Sometimes it is as fast or even 
>faster than the C++ program. 
>
>I can see how the same algorithm can be implemented in ~100 LOC of O'Caml 
>too. However, IMO as this and the previous examples show, reports about 
>extreme LOC ratios are premature.
>
>Cheers,
>Oleg
>

Nice Oleg!.

Can I participate in this challenge?

I have yet build your parser in 25 lines of OCaml
and seems to run as fast as yours. Perhaps in a
couple of days I'll post my solution as I have
very few spare time.

-- 
Arturo Borquez



__________________________________________________________________
Your favorite stores, helpful shopping tools and great gift ideas. Experience the convenience of buying online with Shop@Netscape! http://shopnow.netscape.com/

Get your own FREE, personal Netscape Mail account today at http://webmail.netscape.com/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Rule based language [was: productivity improvement]

[Oleg]

On Wednesday 24 July 2002 09:39 am, Arturo Borquez wrote:
> Can I participate in this challenge?

Sure

> I have yet build your parser in 25 lines of OCaml
> and seems to run as fast as yours. 

I'd actually expect the same algorithm in O'Caml to be a bit faster, since I 
use std::list (doubly-linked) while only a singly-linked list is necessary. 
For non-trivial input parsing time is negligible.

> Perhaps in a
> couple of days I'll post my solution as I have
> very few spare time.

We'll wait

Cheers
Oleg
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] productivity improvement

[Oleg]

On Tuesday 16 July 2002 01:29 pm, Shannon --jj Behrens wrote:

> Wow, that's an impressive piece of C++!!!  C++ never
> seems to stop surprising me!  Nonetheless, I feel the
> OCAML version is infinitely more readable.
>
> Best Regards,
> -jj
[...]

I'd say, to a person equally familiar with O'Caml and C++, the readability 
ratio is less than 2 [1] The readability of compiler messages is a whole 
different story: G++ gives horrible messages when templates, or, god forbid, 
STL errors are present [2]

However, the C++ version looks more "extensible" to me: Suppose that in a 
while, you decide that you want your "node" to be not only Leaf or Unop or 
Binop, but also Triop:

type 'a node = Leaf of 'a | Unop of ('a->'a) * 'a node | Binop of ('a * 'a -> 
'a) * 'a node * 'a node | Triop of ('a * 'a * 'a -> 'a) * 'a node * 'a node * 
'a node;;

You will need to modify the original node type and function "eval" by adding 
an extra pattern to "match" statement, and then recompile everying that 
depends on it. At the same time, with C++ the type of node remains the same. 
You just need to derive a new class  from it:

template<class T>
struct triop : public node<T> {
      T (*fun)(T, T, T);
      node<T> &n1;
      node<T> &n2;
      node<T> &n3
      T eval() { return fun(n1.eval(), n2.eval(), n3.eval); }
      triop (T (*f)(T, T, T), node<T>& N1, node<T>& N2, node<T>& N3) : 
fun(f), n1(N1),  n2(N2), n3(N3) {}  
};

Recompiling isn't necessary. In fact, "old code" may call "new code" if you 
happen to pass it a node that happens to be a triop.

Oleg

P.S. Having read the CalTech tutorial and chapters 1-4 & 14 of the O'Reilly 
book, and having gotten some experience with O'Caml, I'm running low on 
motivation right now. Please give me examples of what's 
hard/awkward/impossible in C++, but relatively easy in O'Caml, if any (I have 
only finite time, so 50 KLOC Coq is not a good example :)

P.P.S. My primary interest is statistical AI (artificial neural networks). I 
haven't found any relevant libraries or applications in SML or O'Caml. That 
is a bit discouraging.

[1] And the example was hand-picked!
[2] If one doesn't want "ad hoc" genericity, templates aren't necessary, of 
course.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] productivity improvement

[Alessandro Baretta]

Oleg wrote:

> P.S. Having read the CalTech tutorial and chapters 1-4 & 14 of the O'Reilly 
> book, and having gotten some experience with O'Caml, I'm running low on 
> motivation right now. Please give me examples of what's 
> hard/awkward/impossible in C++, but relatively easy in O'Caml, if any (I have 
> only finite time, so 50 KLOC Coq is not a good example :)

I am in the process of finishing up a simple XML stylesheet 
processor which formats ascii data for a line printer. Very 
simple. About 1000 odd lines of code in O'Caml. Would a 
project of this kind and size suit your interest? You might 
try to code a processor for the same dtd, so that we can 
measure di difference in "semantic density" of O'Caml and 
C++, within the limits of our respective abilities with the 
two languages (I'm not an O'Caml guru--yet...)

> P.P.S. My primary interest is statistical AI (artificial neural networks). I 
> haven't found any relevant libraries or applications in SML or O'Caml. That 
> is a bit discouraging.

I have a feeling that O'Caml was born out INRIA's need for a 
language to use in symbolic AI projects. The two worlds seem 
to be very difficult to reconcile.

> [1] And the example was hand-picked!
> [2] If one doesn't want "ad hoc" genericity, templates aren't necessary, of 
> course.

Ah! Wait a minute. I have another toy project I could 
propose to you: an interpreter for rule based language, à la 
CLIPS. 197 lines of code in ocaml, including comments. This 
is probably the kind of compelling example you are looking 
for. I coded it in 24 h, including time for sleep, nutrition 
and general self care.

Let me know if you are interested.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] productivity improvement

[Oleg]

On Thursday 18 July 2002 09:25 pm, Alessandro Baretta wrote:

[...]

> Ah! Wait a minute. I have another toy project I could
> propose to you: an interpreter for rule based language, à la
> CLIPS. 197 lines of code in ocaml, including comments. This
> is probably the kind of compelling example you are looking
> for. I coded it in 24 h, including time for sleep, nutrition
> and general self care.
>
> Let me know if you are interested.

Sure, if it's really compelling, and if I won't have to guess the language 
specifications.

Thanks
Oleg
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Rule based language [was: productivity improvement]

[Alessandro Baretta]

Oleg wrote:
> On Thursday 18 July 2002 09:25 pm, Alessandro Baretta wrote:
> 
> [...]
> 
> 
>>Ah! Wait a minute. I have another toy project I could
>>propose to you: an interpreter for rule based language, à la
>>CLIPS. 197 lines of code in ocaml, including comments. This
>>is probably the kind of compelling example you are looking
>>for. I coded it in 24 h, including time for sleep, nutrition
>>and general self care.
>>
>>Let me know if you are interested.
> 
> 
> Sure, if it's really compelling, and if I won't have to guess the language 
> specifications.
> 
> Thanks
> Oleg
> 

Here is the specification of the language:

<program> -> <ruleset> <dataset> <goals>

<ruleset> -> ruleset: <rules>
<rules>   -> <rule> <rules> | <epsilon>
<rule>    -> <rule_name> is <preconditions> =>
                  <postconditions>;
<rule_name> -> <token>
<preconditions> -> <conditions>
<postconditions> -> <conditions>
<conditions>    -> <datum> | <datum> and <conditions>
<datum>   -> <token>

<dataset> -> data_set: <data_list>
<data_list> -> <datum>; <data_list> | <epsilon>

<goals>  -> goals: <goal_list>
<goal_list> -> <goal> <goal_list> | <epsilon>
<goal>   -> <simple>? <goal_name> is <conditions>;
<simple> -> simple
<epsilon> ->

I hope this grammar is complete. I cannot find the original 
specifications for this language.

The interpreter takes a program written in the language 
specified above and for each goal it attempts to find a 
sequence of rule activations that lead to the conditions of 
goal being present contemporarily in the dataset. Since 
preconditions are removed from the dataset upon rule 
activation, the logic determined by this language is non 
monotonous, and backtracking is required to solve the 
problem. Goals marked simple are tested with out 
backtracking: the first rule whose preconditions are 
verified is activated at each step.

Goals are all verified from the initial dataset--that is, 
execution order or goals does not matter.

Here's a thirty second test case I cooked up. We'll want 
something more complete and complex for verification and 
benchmarking.
<rules.program>
--------------------------------------------------------
ruleset:

1 is x => y;
2 is x and pippo => z;

dataset:

foo
x;

goals:

foo is x;
simple x is foo;
simple sz is z;

--------------------------------------------------------
The following is the output the interpreter is supposed to 
generate.

[alex@athlon ocaml]$ ./rules < rules.program
Goal pippo: found
Goal x: found
Goal sz: not found
Goal z: found


Code on and have fun!

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Rule based language [was: productivity improvement]

[Alessandro Baretta]

Oleg wrote:
> Alex,
> 
> This looks pretty simple. What makes you think the program is a compelling 
> evidence of O'Caml superior productivity?

197 lines of code, including whitespace and commments. I 
think it is a pretty clear example of how you can write cool 
software in O'Caml in a very short time. If you had not been 
"lazy", as you said, and had tried implementing the same 
language in C++, I strongly doubt you could have written a 
more compact source.

> Is the idea to make a maximally efficient program? In that case, what kind of
> a) number of different tokens
> b) dataset size
> c) ruleset size
> d) rules size
> are we looking at?
>
> Regards
> Oleg

 From the standpoint of benchmarking, we'll need to write 
several test cases to see how the execution times scale with 
  program size. We might actually want to write an automatic 
testcase generator. I do no expect a C++ compiler to be able 
to beat ocamlopt by a significant amount, unless you use an 
optimized algorithm, different form the one I implemented. 
Anyhow, we shall take up the quest for benchmarking after 
your C++ clone of my "rules" program will be available.

BTW, if you wish to extend the language with other 
constructs, such as pattern matching rules, I'm willing to 
do this. Such constructs would probably increase the 
"lines-of-code" ratio of the C++ vs. O'Caml versions.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Rule based language [was: productivity improvement]

[Oleg]

[-- Attachment #1: Type: text/plain, Size: 1790 bytes --]

On Sunday 21 July 2002 09:00 am, Alessandro Baretta wrote:
> Oleg wrote:
> > Alex,
> >
> > This looks pretty simple. What makes you think the program is a
> > compelling evidence of O'Caml superior productivity?
>
> 197 lines of code, including whitespace and commments. I
> think it is a pretty clear example of how you can write cool
> software in O'Caml in a very short time. If you had not been
> "lazy", as you said, and had tried implementing the same
> language in C++, I strongly doubt you could have written a
> more compact source.


109 LOC in C++ counting blank lines and lines containing a single '}'. See 
atttached files.

A few notes about the differences between your O'Caml program and my C++ 
program: 

1) I'm not using Yacc or Lex for parsing, because I'm not familiar with these 
tools, so ugly parsing takes up most of those 109 LOC (Parsing things is 
peripheral to my professional interests right now. I don't write compilers)

2) I decided not to implement the "simple" keyword, because I did not 
understand what it was supposed to mean (a depth limit on deduction, I'm 
guessing, but what for?)

3) Your program fails to imlement multi-token post-conditions in rules and 
mutli-token goals (as described in your formal language specification)

4) The algorithms are different I think, resulting in, for example, about 
200x speed improvement for the attached test.input file on my P3-800MHz 
(g++-3.0 vs ocamlopt) (The output is identical).  The O'Caml program 
convergence seems to be quite unstable.  Sometimes it is as fast or even 
faster than the C++ program. 

I can see how the same algorithm can be implemented in ~100 LOC of O'Caml 
too. However, IMO as this and the previous examples show, reports about 
extreme LOC ratios are premature.

Cheers,
Oleg

[-- Attachment #2: test.input.gz --]
[-- Type: application/x-gzip, Size: 13749 bytes --]

[-- Attachment #3: rules.cpp.gz --]
[-- Type: application/x-gzip, Size: 1098 bytes --]

Re: [Caml-list] Rule based language [was: productivity improvement]

[Alessandro Baretta]

Oleg wrote:
>>197 lines of code, including whitespace and commments. I
>>think it is a pretty clear example of how you can write cool
>>software in O'Caml in a very short time. If you had not been
>>"lazy", as you said, and had tried implementing the same
>>language in C++, I strongly doubt you could have written a
>>more compact source.
>
 >
> 
> 109 LOC in C++ counting blank lines and lines containing a single '}'. See 
> atttached files.

Cool job Oleg! Hats off to you.

> A few notes about the differences between your O'Caml program and my C++ 
> program: 
> 
> 1) I'm not using Yacc or Lex for parsing, because I'm not familiar with these 
> tools, so ugly parsing takes up most of those 109 LOC (Parsing things is 
> peripheral to my professional interests right now. I don't write compilers)

I expected it to be so.

> 2) I decided not to implement the "simple" keyword, because I did not 
> understand what it was supposed to mean (a depth limit on deduction, I'm 
> guessing, but what for?)

Not a big deal.

> 3) Your program fails to imlement multi-token post-conditions in rules and 
> mutli-token goals (as described in your formal language specification)

I don't remember. I lost the original specs and I finished 
working on that program more than a year ago. I look at it 
again today if I have time. Otherwise I'll, think intensely 
about parsing and backtracking, under the Salentinian sun, 
on the white sand of the beaches of Alimini.

> 4) The algorithms are different I think, resulting in, for example, about 
> 200x speed improvement for the attached test.input file on my P3-800MHz 
> (g++-3.0 vs ocamlopt) (The output is identical).  The O'Caml program 
> convergence seems to be quite unstable.  Sometimes it is as fast or even 
> faster than the C++ program. 

I take this to mean you are challenging me, huh? You are, 
huh? Ok... Ok, you'll see... ;-)

> I can see how the same algorithm can be implemented in ~100 LOC of O'Caml 
> too. However, IMO as this and the previous examples show, reports about 
> extreme LOC ratios are premature.
> 
> Cheers,
> Oleg

I had only a modest O'Caml experience 14 months ago, when I 
wrote the code you have seen. On the other hand, you are an 
expert C++ programmer now, at the time of the "challenge". 
I'll pick up your challenge and try to cook up something by 
tonight. After that, we'll have to pick up our challenge 
again in late august.

Have a lot of fun!
Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners