Re: lexer, parser

[Markus Mottl <mottl@miss.wu-wien.ac.at>]

> > Execution of "semantics" is also much faster than versions that use
> > algebraic datatypes and pattern matching, because here we only have to
> > call methods (wrapped in the functions of the stream) on objects instead
> > of match abstract syntax trees or else.
> 
> Sorry to answer pinpoint, but I just want to avoid a confusion.
> 
> In caml pattern-matching is much more efficient than calling a method.
> Calling a method is a dynamic operation, involving looking-up a table
> and calling a possibly curried function, while pattern-matching is
> completely statically compiled.

Sorry for having caused confusion - my statement above was indeed
misleading. I thought that the original writer wanted to use objects
anyway, so instead of calling methods and matching patterns in the object,
calling the methods alone would be faster even if there is a curried
function inbetween. Matching patterns without using objects would be
faster, of course - but in my eyes much less flexible.

Here an example:

---------------------------------------------------------------------------
(* definitions for version with algebraic datatypes *)
type action = Inc | Dec

class c1 = object
  val mutable x = 0
  method x = x
  method interpret = function
    | Inc -> x <- x + 1
    | Dec -> x <- x - 1
end

let action1 () =
  match Random.int 2 with
  | 0 -> Inc
  | 1 -> Dec
  | _ -> failwith "impossible pattern"

(* definitions for version with functions encapsulating method calls *)
class c2 = object
  val mutable x = 0
  method x = x
  method inc = x <- x + 1
  method dec = x <- x - 1
end

let inc obj = obj#inc
let dec obj = obj#inc

let action2 () =
  match Random.int 2 with
  | 0 -> inc
  | 1 -> dec
  | _ -> failwith "impossible pattern"

(* generate the stream - this is the optimized version with
   linear time behaviour *)
let rec action_stream action =
  Stream.lcons action (Stream.slazy (fun _ -> action_stream action))

(* uncomment the appropriate part to test the specific version *)
let _ =
  let o = new c1
  and strm = action_stream action1 in
  for i = 1 to 5000000 do Stream.next strm done;
(*
  let o = new c2
  and strm = action_stream action2 in
  for i = 1 to 5000000 do (Stream.next strm) o done;
*)
  Printf.printf "o#x: %d\n" o#x
---------------------------------------------------------------------------

If we count away the time that is spent during traversal of the stream,
the (compiled) version using encapsulated method calls is (on my machine)
a bit more than 20% faster.

In my opinion the version without pattern matching is much more natural:
although we have to define the encapsulating functions once, it is never
necessary to explicitely match the action type - we could thus easily
redirect the stream to other objects that match the signature.

The OO-version is much easier to maintain, because the different actions
are really different methods, whereas in the other version the correct
"semantics" has to be chosen in one function (where the patterns are
matched). Thus, we can (by inheritence, parameterized objects, etc..)
easily use abstraction mechanism for generating new "semantics".

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl