Following Mark Tarver's recent shootout challenge to implement a program to
evaluate Minim programs, Pascal Constanza wrote a Minim compiler as a Lisp
compiler macro that has been by far the fastest of the implementations,
several orders of magnitude faster than most other implementations.
The following is a complete OCaml macro that extends the syntax of the OCaml
language to include the Minim sublanguage and expands minim programs into
OCaml code that is then compiled interactively, the same as the Lisp. This
macro performs tail-call optimization on the Lisp code, to ensure that the
resulting use of continuation passing style is robust. Specifically, an if
statement where both branches are tail calls is itself translated into a
tail call.
The OCaml macro is a third the length of the Lisp (in LOC) and can also be
extended to remove the superfluous parentheses from the Minim language and
implement operator precedences and associativites with virtually no
overhead:
open Camlp4.PreCast;;
open Camlp4.PreCast.Syntax;;
let mmstatement = Gram.Entry.mk "mmstatement";;
let mmvalue = Gram.Entry.mk "mmvalue";;
let mmtest = Gram.Entry.mk "mmtest";;
let mmident = Gram.Entry.mk "mmident";;
let rec compile _loc tag e = function
| [] -> <:binding< $lid:tag$ = fun () -> $e$ >>
| `TL e'::`T tag'::t ->
let bs = compile _loc tag' <:expr< () >> t in
<:binding< $lid:tag$ = fun () -> $e$; $e'$ and $bs$ >>
| (`TL e' | `E e')::t -> compile _loc tag <:expr< $e$; $e'$ >> t
| `T tag'::t ->
let bs = compile _loc tag' <:expr< () >> t in
<:binding< $lid:tag$ = fun () -> $e$; $lid:tag'$() and $bs$ >>;;
let compile _loc ss = compile _loc "entry" <:expr< () >> ss;;
EXTEND Gram
str_item: LEVEL "top"
[ [ "MINIM"; "("; ss=LIST1 mmstatement; ")" ->
<:str_item< let rec $compile _loc ss$ >>
] ];
mmstatement:
[ [ "("; x=mmident; "is"; y=mmvalue; ")" -> `E <:expr< $lid:x$ := $y$ >>
| "("; "++"; x=mmident; ")" -> `E <:expr< incr $lid:x$ >>
| "("; "--"; x=mmident; ")" -> `E <:expr< decr $lid:x$ >>
| "("; "if"; p=mmtest; "then"; t=mmstatement; "else";
f=mmstatement; ")" ->
(match t, f with
| `TL t, `TL f -> `TL <:expr< if $p$ then $t$ else $f$ >>
| (`TL t | `E t), (`TL f | `E f) ->
`E <:expr< if $p$ then $t$ else $f$ >>
| _ -> invalid_arg "Tag in 'if' expression")
| "("; "goto"; t=mmident; ")" -> `TL <:expr< $lid:t$() >>
| "("; "print"; s=STRING; ")" ->
let s = String.escaped s in
`E <:expr< print_string $str:s$ >>
| "("; "print"; x=mmvalue; ")" -> `E <:expr< print_int $x$ >>
| "nl" -> `E <:expr< print_newline() >>
| "("; "input"; x=mmident; ")" ->
`E <:expr< $lid:x$ := int_of_string(input_line stdin) >>
| tag=mmident -> `T tag ] ];
mmvalue:
[ [ x=mmident -> <:expr< ! $lid:x$ >>
| n=INT -> <:expr< $int:n$ >> ] ];
mmtest:
[ [ "("; f=mmvalue; "<"; g=mmvalue; ")" -> <:expr< $f$ < $g$ >>
| "("; f=mmvalue; "="; g=mmvalue; ")" -> <:expr< $f$ = $g$ >>
| "("; f=mmvalue; ">"; g=mmvalue; ")" -> <:expr< $f$ > $g$ >>
| "("; f=mmtest; "and"; g=mmtest; ")" -> <:expr< $f$ && $g$ >>
| "("; f=mmtest; "or"; g=mmtest; ")" -> <:expr< $f$ || $g$ >>
| "("; "not"; f=mmtest; ")" -> <:expr< not $f$ >> ] ];
mmident:
[ [ x=LIDENT -> "_"^x
| x=UIDENT -> "_"^x
| "end" -> "_end" ] ];
END;;
This macro may be invoked as follows:
let _x, _y = ref 0, ref 0;;
MINIM(
(print "Add x and y (what a feat!)")
nl
(print "Input x: ")
(input x)
nl
(print "Input y: ")
(input y)
main
(if (x = 0) then (goto end) else (goto sub1x))
sub1x
(-- x)
(++ y)
(goto main)
end
nl
(print "The total of x and y is ")
(print y)
nl
);;
The code generated by the expansion of the macro is:
let rec entry () =
(();
print_string "Add x and y (what a feat!)";
print_newline ();
print_string "Input x: ";
_x := int_of_string (input_line stdin);
print_newline ();
print_string "Input y: ";
_y := int_of_string (input_line stdin);
_main ())
and _main () = ((); if !_x = 0 then _end () else _sub1x ())
and _sub1x () = ((); decr _x; incr _y; _main ())
and _end () =
(();
print_newline ();
print_string "The total of x and y is ";
print_int !_y;
print_newline ());;
The new definitions are invoked by calling entry(). Performance from a
native-code ocamlnat top-level is:
# time entry ();;
Add x and y (what a feat!)
Input x: 10000000
Input y: 10000000
The total of x and y is 20000000
Took 0.094985s
- : unit = ()
Note that this is still 3.3x slower than Pascal's Lisp:
* (time (test-minim))
Add x and y
Input x: 10000000
Input y: 10000000
The total of x and y is 20000000
Evaluation took:
0.032 seconds of real time
0.030996 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
8,160 bytes consed.
NIL
Using batch compilation at the cost of non-interactivity makes the OCaml as
fast as the Lisp. However, the Lisp is interactive...
On a related note, I've been writing programs to evaluate Brainf*ck
programs. My MetaOCaml implementations that used staged native code
compilation at run-time are no faster than a naive interpreter. I believe
the reason is simply that MetaOCaml is not good at dealing with target
languages that use gotos because OCaml does not compile CPS as efficiently
as ordinary calls.
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
On Aug 17, 10:31 am, Jon Harrop <····@ffconsultancy.com> wrote:
> Following Mark Tarver's recent shootout challenge to implement a program to
> evaluate Minim programs, Pascal Constanza wrote a Minim compiler as a Lisp
> compiler macro that has been by far the fastest of the implementations,
> several orders of magnitude faster than most other implementations.
>
> The following is a complete OCaml macro that extends the syntax of the OCaml
> language to include the Minim sublanguage and expands minim programs into
> OCaml code that is then compiled interactively, the same as the Lisp. This
> macro performs tail-call optimization on the Lisp code, to ensure that the
> resulting use of continuation passing style is robust. Specifically, an if
> statement where both branches are tail calls is itself translated into a
> tail call.
>
> The OCaml macro is a third the length of the Lisp (in LOC) and can also be
> extended to remove the superfluous parentheses from the Minim language and
> implement operator precedences and associativites with virtually no
> overhead:
>
> open Camlp4.PreCast;;
> open Camlp4.PreCast.Syntax;;
>
> let mmstatement = Gram.Entry.mk "mmstatement";;
> let mmvalue = Gram.Entry.mk "mmvalue";;
> let mmtest = Gram.Entry.mk "mmtest";;
> let mmident = Gram.Entry.mk "mmident";;
>
> let rec compile _loc tag e = function
> | [] -> <:binding< $lid:tag$ = fun () -> $e$ >>
> | `TL e'::`T tag'::t ->
> let bs = compile _loc tag' <:expr< () >> t in
> <:binding< $lid:tag$ = fun () -> $e$; $e'$ and $bs$ >>
> | (`TL e' | `E e')::t -> compile _loc tag <:expr< $e$; $e'$ >> t
> | `T tag'::t ->
> let bs = compile _loc tag' <:expr< () >> t in
> <:binding< $lid:tag$ = fun () -> $e$; $lid:tag'$() and $bs$ >>;;
>
> let compile _loc ss = compile _loc "entry" <:expr< () >> ss;;
>
> EXTEND Gram
> str_item: LEVEL "top"
> [ [ "MINIM"; "("; ss=LIST1 mmstatement; ")" ->
> <:str_item< let rec $compile _loc ss$ >>
> ] ];
> mmstatement:
> [ [ "("; x=mmident; "is"; y=mmvalue; ")" -> `E <:expr< $lid:x$ := $y$ >>
> | "("; "++"; x=mmident; ")" -> `E <:expr< incr $lid:x$ >>
> | "("; "--"; x=mmident; ")" -> `E <:expr< decr $lid:x$ >>
> | "("; "if"; p=mmtest; "then"; t=mmstatement; "else";
> f=mmstatement; ")" ->
> (match t, f with
> | `TL t, `TL f -> `TL <:expr< if $p$ then $t$ else $f$ >>
> | (`TL t | `E t), (`TL f | `E f) ->
> `E <:expr< if $p$ then $t$ else $f$ >>
> | _ -> invalid_arg "Tag in 'if' expression")
> | "("; "goto"; t=mmident; ")" -> `TL <:expr< $lid:t$() >>
> | "("; "print"; s=STRING; ")" ->
> let s = String.escaped s in
> `E <:expr< print_string $str:s$ >>
> | "("; "print"; x=mmvalue; ")" -> `E <:expr< print_int $x$ >>
> | "nl" -> `E <:expr< print_newline() >>
> | "("; "input"; x=mmident; ")" ->
> `E <:expr< $lid:x$ := int_of_string(input_line stdin) >>
> | tag=mmident -> `T tag ] ];
> mmvalue:
> [ [ x=mmident -> <:expr< ! $lid:x$ >>
> | n=INT -> <:expr< $int:n$ >> ] ];
> mmtest:
> [ [ "("; f=mmvalue; "<"; g=mmvalue; ")" -> <:expr< $f$ < $g$ >>
> | "("; f=mmvalue; "="; g=mmvalue; ")" -> <:expr< $f$ = $g$ >>
> | "("; f=mmvalue; ">"; g=mmvalue; ")" -> <:expr< $f$ > $g$ >>
> | "("; f=mmtest; "and"; g=mmtest; ")" -> <:expr< $f$ && $g$ >>
> | "("; f=mmtest; "or"; g=mmtest; ")" -> <:expr< $f$ || $g$ >>
> | "("; "not"; f=mmtest; ")" -> <:expr< not $f$ >> ] ];
> mmident:
> [ [ x=LIDENT -> "_"^x
> | x=UIDENT -> "_"^x
> | "end" -> "_end" ] ];
> END;;
>
> This macro may be invoked as follows:
>
> let _x, _y = ref 0, ref 0;;
>
> MINIM(
> (print "Add x and y (what a feat!)")
> nl
> (print "Input x: ")
> (input x)
> nl
> (print "Input y: ")
> (input y)
> main
> (if (x = 0) then (goto end) else (goto sub1x))
>
> sub1x
> (-- x)
> (++ y)
> (goto main)
>
> end
> nl
> (print "The total of x and y is ")
> (print y)
> nl
> );;
>
> The code generated by the expansion of the macro is:
>
> let rec entry () =
> (();
> print_string "Add x and y (what a feat!)";
> print_newline ();
> print_string "Input x: ";
> _x := int_of_string (input_line stdin);
> print_newline ();
> print_string "Input y: ";
> _y := int_of_string (input_line stdin);
> _main ())
> and _main () = ((); if !_x = 0 then _end () else _sub1x ())
> and _sub1x () = ((); decr _x; incr _y; _main ())
> and _end () =
> (();
> print_newline ();
> print_string "The total of x and y is ";
> print_int !_y;
> print_newline ());;
>
> The new definitions are invoked by calling entry(). Performance from a
> native-code ocamlnat top-level is:
>
> # time entry ();;
> Add x and y (what a feat!)
> Input x: 10000000
> Input y: 10000000
> The total of x and y is 20000000
> Took 0.094985s
> - : unit = ()
>
> Note that this is still 3.3x slower than Pascal's Lisp:
>
> * (time (test-minim))
> Add x and y
> Input x: 10000000
> Input y: 10000000
>
> The total of x and y is 20000000
> Evaluation took:
> 0.032 seconds of real time
> 0.030996 seconds of user run time
> 0.0 seconds of system run time
> 0 calls to %EVAL
> 0 page faults and
> 8,160 bytes consed.
> NIL
>
> Using batch compilation at the cost of non-interactivity makes the OCaml as
> fast as the Lisp. However, the Lisp is interactive...
>
> On a related note, I've been writing programs to evaluate Brainf*ck
> programs. My MetaOCaml implementations that used staged native code
> compilation at run-time are no faster than a naive interpreter. I believe
> the reason is simply that MetaOCaml is not good at dealing with target
> languages that use gotos because OCaml does not compile CPS as efficiently
> as ordinary calls.
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy
> OCaml for Scientistshttp://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
what a horrible unreadable mess... !
thank god for lisp parens so that macros don't look like this.
Jon Harrop wrote:
> Following Mark Tarver's recent shootout challenge to implement a program to
> evaluate Minim programs, Pascal Constanza wrote a Minim compiler as a Lisp
> compiler macro that has been by far the fastest of the implementations,
> several orders of magnitude faster than most other implementations.
...and here is the kicker: I couldn't care less...
> Using batch compilation at the cost of non-interactivity makes the OCaml as
> fast as the Lisp. However, the Lisp is interactive...
...because that's more important, among other things.
The result is no surprise: It is well known in the Lisp community that
you can make Lisp code run as fast as required, provided you are willing
to invest the time to do so. The Minim interpreter was especially
straightforward to optimize because the Minim language consists mainly
of constructs that have direct counterparts in Common Lisp. It mostly
serves as an illustration that high efficiency is indeed possible to
achieve in Common Lisp. However, it is still a toy example and doesn't
say a lot about more complex and involved programs.
Lisp and Scheme give you a lot of advantages when you are interested in
dynamic and interactive features, and want to consider programs as
"living" systems that you can interact with, not as text files that need
to be translated and that you cannot touch anymore after such
translation. In Lisp, only if and when you detect serious bottlenecks,
you invest the time to detect the hot spots and then optimize them. At
least, that's the typical approach.
Lisp buys you flexibility by default, but you have to work for
efficiency. (That's in general true for other dynamic languages as well,
like Smalltalk, Prolog, etc.) In static languages, it's the other way
around: They buy you (low-level) efficiency by default, but you have to
work for flexibility. This gives you a pretty good rule of thumb when to
use what kind of languages.
Toy examples and toy benchmarks don't give you any useful rules of
thumbs. Knowing that a simple ray tracer is more efficient in OCaml and
that a simple assembly-style language is more efficient in Common Lisp
is pretty uninteresting. They are not realistic enough to be
representative of real-world software.
Pascal
P.S.: It's "Costanza", not "Constanza".
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
In article <<·························@news.sunsite.dk>>,
Alex Mizrahi <········@users.sourceforge.net> wrote:
>
> JH> let rec compile _loc tag e = function
> JH> | [] -> <:binding< $lid:tag$ = fun () -> $e$ >>
> JH> | `TL e'::`T tag'::t ->
>
> Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn
>
> JH> let bs = compile _loc tag' <:expr< () >> t in
> JH> <:binding< $lid:tag$ = fun () -> $e$; $e'$ and $bs$ >>
This isn't particularly complicated code.
<:blah< stuff $e$ >>
is quasiquotation -- it's equivalent to Lisp's `(stuff ,e).
The reason there's a "blah" there is that unlike Lisp, camlp4 also
makes the quotation system user-extensible, so the blah tells the
compiler which quotation processor to use.
The rest of what you quoted is just a recursive function that
processes a list with pattern matching.
--
Neel R. Krishnaswami
·····@cs.cmu.edu
On Fri, 17 Aug 2007 18:07:48 +0300, "Alex Mizrahi"
<········@users.sourceforge.net> wrote:
>Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn
He's awake and posting to c.l.l. What's the spell to send him back?
George
--
for email reply remove "/" from address
On Fri, 17 Aug 2007 09:31:09 +0100, Jon Harrop wrote:
> Following Mark Tarver's recent shootout challenge to implement a program to
> evaluate Minim programs, Pascal Constanza [sic] wrote a Minim compiler
> as a Lisp compiler macro that has been by far the fastest of the
> implementations
Since that was a cross posted flame war of a thread, it would be polite to
at least post a link to Pascal's posts.
These are the most relevant ones i found:
http://groups.google.com/group/comp.lang.lisp/msg/f6f6c4e0e7dd11fd
http://groups.google.com/group/comp.lang.lisp/msg/7b348db0212b746f
--
"You do not really understand something unless you
can explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> On Fri, 17 Aug 2007 09:31:09 +0100, Jon Harrop wrote:
>> Following Mark Tarver's recent shootout challenge to implement a program
>> to evaluate Minim programs, Pascal Constanza [sic] wrote a Minim compiler
>> as a Lisp compiler macro that has been by far the fastest of the
>> implementations
>
> Since that was a cross posted flame war of a thread, it would be polite to
> at least post a link to Pascal's posts.
>
> These are the most relevant ones i found:
>
> http://groups.google.com/group/comp.lang.lisp/msg/f6f6c4e0e7dd11fd
> http://groups.google.com/group/comp.lang.lisp/msg/7b348db0212b746f
Thank you. I did actually search for it but its like a needle in a hay
stack. :-)
Still, I think that was an enlightening challenge. Thank you, Mark.
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
On 17 Aug, 09:31, Jon Harrop <····@ffconsultancy.com> wrote:
> On a related note, I've been writing programs to evaluate Brainf*ck
> programs. My MetaOCaml implementations that used staged native code
> compilation at run-time are no faster than a naive interpreter. I believe
> the reason is simply that MetaOCaml is not good at dealing with target
> languages that use gotos because OCaml does not compile CPS as efficiently
> as ordinary calls.
I found the bounds checking of arrays to be the major bottleneck in
implementing a brainfuck complier in lisp. Make sure you turn this off
or at least merge statements so that +++++ is mapped to the ocaml
equivalent of (incf (aref x 10) 5) rather than:
(incf (aref x 10))
(incf (aref x 10))
(incf (aref x 10))
(incf (aref x 10))
(incf (aref x 10))
before you start blaming gotos.
If you still have problems, you can rewrite the while loop using HOFs
and see if function calls really are faster...