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; 8+ 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] 8+ messages in thread

* Re: [Caml-list] Rule based language [was: productivity improvement]
  2002-07-24 13:39 [Caml-list] Rule based language [was: productivity improvement] Arturo Borquez
@ 2002-07-24 20:03 ` Oleg
  0 siblings, 0 replies; 8+ messages in thread
From: Oleg @ 2002-07-24 20:03 UTC (permalink / raw)
  To: Arturo Borquez, Alessandro Baretta, caml-list

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


^ permalink raw reply	[flat|nested] 8+ 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, 0 replies; 8+ messages in thread
From: Oleg @ 2002-07-25  6:26 UTC (permalink / raw)
  To: sajuma; +Cc: caml-list

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


^ permalink raw reply	[flat|nested] 8+ 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; 8+ 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] 8+ messages in thread

* Re: [Caml-list] Rule based language [was: productivity improvement]
  2002-07-23  9:53         ` Oleg
@ 2002-07-24  8:07           ` Alessandro Baretta
  0 siblings, 0 replies; 8+ messages in thread
From: Alessandro Baretta @ 2002-07-24  8:07 UTC (permalink / raw)
  To: Oleg, Ocaml



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


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [Caml-list] Rule based language [was: productivity improvement]
  2002-07-21 13:00       ` Alessandro Baretta
@ 2002-07-23  9:53         ` Oleg
  2002-07-24  8:07           ` Alessandro Baretta
  0 siblings, 1 reply; 8+ messages in thread
From: Oleg @ 2002-07-23  9:53 UTC (permalink / raw)
  To: Alessandro Baretta, Ocaml

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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [Caml-list] Rule based language [was: productivity improvement]
       [not found]     ` <200207210059.UAA17003@dewberry.cc.columbia.edu>
@ 2002-07-21 13:00       ` Alessandro Baretta
  2002-07-23  9:53         ` Oleg
  0 siblings, 1 reply; 8+ messages in thread
From: Alessandro Baretta @ 2002-07-21 13:00 UTC (permalink / raw)
  To: Oleg, Ocaml



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


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [Caml-list] Rule based language [was: productivity improvement]
  2002-07-19  4:04     ` Oleg
@ 2002-07-19 15:46       ` Alessandro Baretta
  0 siblings, 0 replies; 8+ messages in thread
From: Alessandro Baretta @ 2002-07-19 15:46 UTC (permalink / raw)
  To: Oleg, Ocaml

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


^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2002-07-25  6:26 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2002-07-24 13:39 [Caml-list] Rule based language [was: productivity improvement] Arturo Borquez
2002-07-24 20:03 ` Oleg
  -- strict thread matches above, loose matches on Subject: below --
2002-07-24 22:31 sajuma
2002-07-25  6:26 ` Oleg
     [not found] <20020716172916.4903.qmail@web10702.mail.yahoo.com>
2002-07-18 23:14 ` [Caml-list] productivity improvement Oleg
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
     [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       ` Alessandro Baretta
2002-07-23  9:53         ` Oleg
2002-07-24  8:07           ` Alessandro Baretta

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