caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* Re: [Caml-list] Rule based language [was: productivity improvement]
@ 2002-07-24 13:39 Arturo Borquez
  2002-07-24 20:03 ` Oleg
  0 siblings, 1 reply; 62+ messages in thread
From: Arturo Borquez @ 2002-07-24 13:39 UTC (permalink / raw)
  To: Oleg, Alessandro Baretta, Ocaml

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


^ permalink raw reply	[flat|nested] 62+ messages in thread
* Re: [Caml-list] Rule based language [was: productivity improvement]
@ 2002-07-24 22:31 sajuma
  2002-07-25  6:26 ` Oleg
  0 siblings, 1 reply; 62+ messages in thread
From: sajuma @ 2002-07-24 22:31 UTC (permalink / raw)
  To: Oleg; +Cc: caml-list

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


^ permalink raw reply	[flat|nested] 62+ messages in thread
end of thread, other threads:[~2002-10-21  8:57 UTC | newest]

Thread overview: 62+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <20020716172916.4903.qmail@web10702.mail.yahoo.com>
2002-07-18 23:14 ` [Caml-list] productivity improvement Oleg
2002-07-18 23:27   ` Brian Smith
2002-07-18 23:54   ` William Lovas
2002-07-19  3:59     ` Oleg
     [not found]       ` <20020719010318.B3631@boson.den.co.bbnow.net>
2002-07-19  8:22         ` Oleg
2002-07-19  8:57           ` Andreas Rossberg
2002-07-19 10:14             ` Alessandro Baretta
2002-07-19 18:15               ` John Max Skaller
2002-07-19 18:33                 ` Brian Smith
2002-07-20 17:30                   ` John Max Skaller
2002-07-19 19:06                 ` Alessandro Baretta
2002-07-20 17:49                   ` John Max Skaller
2002-07-19 10:34             ` Oleg
2002-07-19 17:25               ` Andreas Rossberg
2002-07-20 16:58                 ` John Max Skaller
2002-07-19 16:35     ` Brian Rogoff
2002-10-16 23:24       ` Eray Ozkural
2002-07-19  1:25   ` Alessandro Baretta
2002-07-19  4:04     ` Oleg
2002-07-19 15:46       ` [Caml-list] Rule based language [was: productivity improvement] Alessandro Baretta
2002-07-19 17:20         ` [Caml-list] compact.c Julie Farago
2002-10-15  9:31     ` [Caml-list] productivity improvement Eray Ozkural
2002-10-15 12:34       ` Oleg
2002-10-15 15:08         ` Eray Ozkural
2002-07-19  4:42   ` Emmanuel Renieris
2002-07-19  9:57     ` Oleg
2002-07-19 10:43       ` Alessandro Baretta
2002-07-19 10:52         ` Daniel de Rauglaudre
2002-07-19 11:36           ` Alessandro Baretta
2002-07-19 11:10       ` Xavier Leroy
2002-10-15  9:24         ` Eray Ozkural
2002-10-15 18:47           ` Pal-Kristian Engstad
2002-10-17  0:12             ` Eray Ozkural
2002-10-17  9:34               ` Diego Olivier Fernandez Pons
2002-10-17 15:55                 ` Jeffrey Palmer
2002-10-17 16:15                   ` brogoff
2002-10-17 18:21                   ` [Caml-list] Re: Camlp4 optimizations (was: productivity improvement) Christophe TROESTLER
2002-10-17 18:32                     ` Chris Hecker
2002-10-17 19:08                       ` Shivkumar Chandrasekaran
2002-10-17 20:01                         ` Chris Hecker
2002-10-17 19:36                       ` Daniel de Rauglaudre
2002-10-17 19:59                       ` Brian Hurt
2002-10-17 20:22                         ` Chris Hecker
2002-10-17 21:19                           ` Brian Hurt
2002-10-17 21:37                             ` Jeffrey Palmer
2002-10-17 23:55                               ` Alessandro Baretta
2002-10-18  0:57                                 ` Jeffrey Palmer
2002-10-18  4:21                                   ` Alessandro Baretta
2002-10-18  8:23                                     ` Remi VANICAT
2002-10-18  8:46                                       ` Sven Luther
2002-10-18  1:47                               ` Brian Hurt
2002-10-17 23:03                             ` Chris Hecker
2002-10-18 23:55                               ` brogoff
2002-10-18 10:43                   ` [Caml-list] productivity improvement Diego Olivier Fernandez Pons
2002-10-21  8:57                   ` Francois Pottier
     [not found] ` <200207200640.CAA11477@dewberry.cc.columbia.edu>
     [not found]   ` <3D391B41.50900@baretta.com>
     [not found]     ` <200207210059.UAA17003@dewberry.cc.columbia.edu>
2002-07-21 13:00       ` [Caml-list] Rule based language [was: productivity improvement] Alessandro Baretta
2002-07-23  9:53         ` Oleg
2002-07-24  8:07           ` Alessandro Baretta
2002-07-24 13:39 Arturo Borquez
2002-07-24 20:03 ` Oleg
2002-07-24 22:31 sajuma
2002-07-25  6:26 ` Oleg

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).