shootout: implementing an interpreter for a simple procedural language Minim
Mark Tarver
programs in different functional languages for comparison. He
suggested interpreters for procedural languages like Basic.
QUOTE
There seems to be a great deal of interest from the functional
programming community in benchmarking. ..... I would also like to see
regexps, program evaluators (rewriters, interpreters and compilers)
and other benchmarks
UNQUOTE
Ok; here's a response - let's see if people want to try.
***********************************************************
The task is to implement an interpreter for a language Minim and run a
stock Minim program that adds two numbers x and y together where x =
100000 (10^5) and y = 100000 (10^5) and give the times.
***********************************************************
Minim is a very basic language - fairly close to assembly. Minim can
1. assign number constants to variables
2. assign the value of a variable to a variable
3. decrement or increment a variable
4. compare two values (numbers or variables) by >, < or =.
5. perform if then else tests
6. jump to a tag
7. print a string
8. print a value (i.e. a number or the value of a variable)
9. input a number value from a user into a variable
10. print a new line
11. do AND, NOT and OR boolean tests
Here's Minim Syntax in BNF with comments
<program> := <statement>
| <statement> <program>;
<statement> := <assignment>
| <conditional>
| <goto>
| <tag>;
| <print>
| <input>
<assignment> := (<var> is <val>) { assign a value to a variable }
| (++ <var>) { increment a variable }
| (-- <var>); { decrement a variable }
<val> := <constant> | <var>;
<var> := any symbol;
<constant> := any number
<conditional> := (if <test> then <statement> else <statement>);
<test> := (<val> <comp> <val>)
| (<test> and <test>); { boolean AND}
| (<test> or <test>) {boolean OR}
| (not <test>); {boolean NOT}
<comp> := > | < | =;
<goto> := (goto <tag>); {go to}
<tag> := any symbol
<print> := (print <string>) | (print <val>); nl; {nl is new line}
<input> := (input <var>); {input the users response to
var}
<string> := any string;
Here's the stock program to add two numbers together in Minim -
designed to here run under Qi. You should be able to follow it.
[ [print "Add x and y"]
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]
A Qi Solution
_____________
Here's a type secure implementation of an interpreter for Minim in Qi.
The type theory encapsulates the BNF and is 54 lines of sequent
calculus.\
(synonyms program [statement]
env [(symbol * number)])
(datatype statement
Var : symbol; Val : val;
=========================
[Var is Val] : statement;
if (element? Op [++ --])
Var : symbol;
=====================
[Op Var] : statement;
Test : test; DoThis : statement; DoThat : statement;
====================================================
[if Test then DoThis else DoThat] : statement;
Tag : symbol;
======================
[goto Tag] : statement;
Message : string-or-val;
============================
[print Message] : statement;
Message : string;
_________________
Message : string-or-val;
Message : val;
_________________
Message : string-or-val;
Var : symbol;
=========================
[input Var] : statement;
Tag : symbol;
_____________
Tag : statement;)
(datatype test
if (element? Comp [= > <])
Val1 : val; Val2: val;
======================
[Val1 Comp Val2] : test;
if (element? LogOp [and or])
Test1 : test;
Test2 : test;
=============
[Test1 LogOp Test2] : test;
Test : test;
==================
[not Test] : test;)
(datatype val
______________________________________
(number? N) : verified >> N : number;
_______________________________________
(symbol? S) : verified >> S : symbol;
Val : symbol;
_______________
Val : val;
Val : number;
_____________
Val : val;)
\The program that runs Minim programs is 56 lines of Qi and is given
here.\
(define run
{program --> env}
Program -> (run-loop Program Program []))
(define run-loop
{program --> program --> env --> env}
[] _ Env -> Env
[nl | Ss] Program Env -> (do (output "~%") (run-loop Ss Program
Env))
[Tag | Ss] Program Env -> (run-loop Ss Program Env) where (symbol?
Tag)
[[goto Tag] | _] Program Env -> (run-loop (go Tag Program) Program
Env)
[[Var is Val] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (compute-val Val Env)
Env))
[[++ Var] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (+ 1 (look-up Var Env))
Env))
[[-- Var] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (- (look-up Var Env) 1)
Env))
[[if Test then DoThis else DoThat] | Ss] Program Env
-> (if (perform-test? Test Env)
(run-loop [DoThis | Ss] Program Env)
(run-loop [DoThat | Ss] Program Env))
[[print M] | Ss] Program Env -> (do (output "~A" (look-up M Env))
(run-loop Ss Program Env))
where (symbol? M)
[[print M] | Ss] Program Env -> (do (output "~A" M)
(run-loop Ss Program Env))
[[input Var] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (input+ : number)
Env)))
(define compute-val
{val --> env --> number}
N _ -> N where (number? N)
Var Env -> (look-up Var Env) where (symbol? Var))
(define go
{symbol --> program --> program}
Tag [Tag | Program] -> Program
Tag [_ | Program] -> (go Tag Program)
Tag _ -> (error "cannot go to tag ~A~%" Tag))
(define perform-test?
{test --> env --> boolean}
[Test1 and Test2] Env -> (and (perform-test? Test1 Env)
(perform-test? Test2 Env))
[Test1 or Test2] Env -> (or (perform-test? Test1 Env)
(perform-test? Test2 Env))
[not Test] Env -> (not (perform-test? Test Env))
[V1 = V2] Env -> (= (compute-val V1 Env) (compute-val V2 Env))
[V1 > V2] Env -> (> (compute-val V1 Env) (compute-val V2 Env))
[V1 < V2] Env -> (< (compute-val V1 Env) (compute-val V2 Env)))
(define change-env
{symbol --> number --> env --> env}
Var Val [] -> [(@p Var Val)]
Var Val [(@p Var _) | Env] -> [(@p Var Val) | Env]
Var Val [Binding | Env] -> [Binding | (change-env Var Val Env)])
(define look-up
{symbol --> env --> number}
Var [] -> (error "~A is unbound.~%" Var)
Var [(@p Var Val) | _] -> Val
Var [_ | Env] -> (look-up Var Env))
\Here is a trial run -
NB: This is run under CLisp which is *much* slower than SBCL. My
version of SBCL (1.0) for Windows is rather neurotic and I've had to
choose the slower but more stable CLisp. This means I've probably
lost out by a factor of 4 (at a guess).
Qi 2007, Copyright (C) 2001-2007 Mark Tarver
www.lambdassociates.org
version 9.0 (Turbo-E)
(0-) (tc +)
true
(1+) (turbo +)
true : boolean
(2+) (load "minim.txt")
compiled : unit
statement : unit
test : unit
val : unit
run : ((list statement) --> (list (symbol * number)))
run-loop :
((list statement) -->
((list statement) -->
((list (symbol * number)) --> (list (symbol * number)))))
compute-val : (val --> ((list (symbol * number)) --> number))
go : (symbol --> ((list statement) --> (list statement)))
perform-test? : (test --> ((list (symbol * number)) --> boolean))
change-env :
(symbol -->
(number --> ((list (symbol * number)) --> (list (symbol * number)))))
look-up : (symbol --> ((list (symbol * number)) --> number))
typechecked in 22217 inferences.
Real time: 0.875 sec.
Run time: 0.859375 sec.
Space: 11044772 Bytes
GC: 21, GC time: 0.140625 sec.
loaded : symbol
(3+) (time (run [
[print "Add x and y"]
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]))
Add x and y
Input x: 100000
Input y: 100000
The total of x and y is 200000
Real time: 12.15625 sec.
Run time: 2.125 sec.
Space: 7210116 Bytes
GC: 14, GC time: 0.03125 sec.
[(@p x 0) (@p y 200000)] : (list (symbol * number))
(4+)
This whole post is a commented Qi program so you can load it into Qi.
Mark \
Paul Rubin
> The task is to implement an interpreter for a language Minim and run a
> stock Minim program that adds two numbers x and y together where x =
> 100000 (10^5) and y = 100000 (10^5) and give the times.
This is too easy to game. Think of the obvious Lisp approach of
translating the Minim program into an S-expression and evaluating it.
Now think of an evaluator that automatically invokes an optimizing
compiler and memoizes the resulting machine code. You see where this
leads.
Jon Harrop
> Minim is a very basic language - fairly close to assembly.
This is ok but I think minim is a little too simple.
> Here's the stock program to add two numbers together in Minim -
> designed to here run under Qi. You should be able to follow it.
>
> [ [print "Add x and y"]
> 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]
Can you write a parser so the program can be loaded from a text file written
in the syntax you described? Unfair to hard code it...
Here's my expr.ml:
type 'var value =
| Int of int
| Var of 'var
type 'var test =
| Less of 'var value * 'var value
| Equal of 'var value * 'var value
| Greater of 'var value * 'var value
| And of 'var test * 'var test
| Or of 'var test * 'var test
| Not of 'var test
type ('var, 'tag) statement =
| Assign of 'var * 'var value
| Incr of 'var
| Decr of 'var
| If of 'var test * ('var, 'tag) statement * ('var, 'tag) statement
| Goto of 'tag
| Tag of 'tag
| PrintString of string
| Print of 'var
| Input of 'var
type program = (string, string) statement list
> A Qi Solution
> _____________
>
> Here's a type secure implementation of an interpreter for Minim in Qi.
> The type theory encapsulates the BNF and is 54 lines of sequent
> calculus.
Can you give an example of errors that your static type system catches?
Here's my lexer.mll:
{
open Parser
open Expr
let start = ref 1 and line = ref 1
let newline lexbuf =
start := lexbuf.Lexing.lex_curr_p.Lexing.pos_cnum;
incr line
let ident = function
| "is" -> IS
| "if" -> IF
| "then" -> THEN
| "else" -> ELSE
| "goto" -> GOTO
| "print" -> PRINT
| "nl" -> NL
| "input" -> INPUT
| "and" -> AND
| "or" -> OR
| "not" -> NOT
| s -> IDENT s
}
let digit = ['0'-'9']
let alpha = ['a'-'z' 'A'-'Z']+
let ident = alpha+ (alpha | digit)*
rule token = parse
| '\n' { newline lexbuf; token lexbuf }
| [' ' '\t' '\r'] { token lexbuf }
| '=' { EQUAL }
| "++" { INC }
| "--" { DEC }
| '<' { LESS }
| '=' { EQUAL }
| '>' { GREATER }
| digit+ as s { INT (int_of_string s) }
| ident as s { ident s }
| '"' (("\\\"" | [^ '"'])* as s) '"' { STRING s }
| eof { EOF }
Here's my parser.mly:
%{
open Expr
%}
%token <string> STRING IDENT
%token <int> INT
%token IS IF THEN ELSE GOTO PRINT NL INPUT AND OR NOT EOF INC DEC LESS EQUAL
GREATER
%start program
%type <Expr.program> program
%%
program:
| statement program { $1 :: $2 }
| statement EOF { [$1] };
statement:
| IDENT IS value { Assign($1, $3) }
| INC IDENT { Incr $2 }
| DEC IDENT { Decr $2 }
| IF test THEN statement ELSE statement { If($2, $4, $6) }
| GOTO IDENT { Goto $2 }
| IDENT { Tag $1 }
| PRINT STRING { PrintString $2 }
| PRINT IDENT { Print $2 }
| NL { PrintString "\n" }
| INPUT IDENT { Input $2 };
value:
| INT { Int $1 }
| IDENT { Var $1 };
test:
| value LESS value { Less($1, $3) }
| value EQUAL value { Equal($1, $3) }
| value GREATER value { Greater($1, $3) }
| test AND test { And($1, $3) }
| test OR test { Or($1, $3) }
| NOT test { Not $2 };
> \The program that runs Minim programs is 56 lines of Qi and is given
> here.\
Here's my 43-line eval.ml:
open Expr
open Printf
module Bindings = Map.Make(String)
let set m x y = Bindings.add x y m
let get m x = Bindings.find x m
let tags_of program =
let aux (pc, tags) = function
| Tag t -> pc+1, Bindings.add t pc tags
| _ -> pc+1, tags in
let _, tags = Array.fold_left aux (0, Bindings.empty) program in
tags
let eval vars = function
| Int n -> n
| Var v -> get vars v
let rec test vars = function
| Less(f, g) -> eval vars f < eval vars g
| Equal(f, g) -> eval vars f = eval vars g
| Greater(f, g) -> eval vars f > eval vars g
| And(f, g) -> test vars f && test vars g
| Or(f, g) -> test vars f || test vars g
| Not f -> not(test vars f)
let rec statement tags vars pc = function
| Assign(x, y) -> set vars x (eval vars y), pc + 1
| Incr x -> set vars x (get vars x + 1), pc + 1
| Decr x -> set vars x (get vars x - 1), pc + 1
| If(p, t, f) -> statement tags vars pc (if test vars p then t else f)
| Goto tag -> vars, Bindings.find tag tags
| Tag _ -> vars, pc + 1
| PrintString s -> print_string s; vars, pc + 1
| Print x -> print_int(get vars x); vars, pc + 1
| Input x -> set vars x (int_of_string(input_line stdin)), pc + 1
let rec run program tags (vars, pc) =
run program tags (statement tags vars pc program.(pc))
let () =
match Sys.argv with
| [|_; file|] ->
let ch = open_in file in
let program = Parser.program Lexer.token (Lexing.from_channel ch) in
close_in ch;
let program = Array.of_list program in
(try run program (tags_of program) (Bindings.empty, 0) with _ -> ())
| _ -> invalid_arg "Usage: ./minim <file>"
> NB: This is run under CLisp which is *much* slower than SBCL. My
> version of SBCL (1.0) for Windows is rather neurotic and I've had to
> choose the slower but more stable CLisp. This means I've probably
> lost out by a factor of 4 (at a guess).
> ...
> The total of x and y is 200000
>
> Real time: 12.15625 sec.
> Run time: 2.125 sec.
I get roughly the same performance from OCaml's interpreted bytecode:
$ ocamlbuild eval.byte
+ /usr/bin/ocamlyacc parser.mly
6 shift/reduce conflicts.
Finished, 13 targets (0 cached) in 00:00:03.
$ time ./eval.byte test.minim <args.txt
Add x and y
Input x:
Input y:
The total of x and y is 200000
real 0m0.583s
user 0m0.569s
sys 0m0.005s
However, native-code is over an order of magnitude faster:
$ ocamlbuild eval.native
Finished, 16 targets (11 cached) in 00:00:03.
$ time ./eval.native test.minim <args.txt
Add x and y
Input x:
Input y:
The total of x and y is 200000
real 0m0.050s
user 0m0.048s
sys 0m0.001s
To optimize this, I would precompute branch targets and variable space,
substituting the gotos and variable references with integers instead of
strings. I deliberately parameterized the expr type over the types of
variables and tags to make this easy.
> This whole post is a commented Qi program so you can load it into Qi.
Now that is cool. :-)
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
Jon Harrop
> This is too easy to game. Think of the obvious Lisp approach of
> translating the Minim program into an S-expression and evaluating it.
> Now think of an evaluator that automatically invokes an optimizing
> compiler and memoizes the resulting machine code. You see where this
> leads.
I think that's exactly what makes this benchmark interesting.
Paul Rubin
> > Now think of an evaluator that automatically invokes an optimizing
> > compiler and memoizes the resulting machine code. You see where this
> > leads.
>
> I think that's exactly what makes this benchmark interesting.
Are you kidding? Think of Kyoto Common Lisp for example. It compiles
Lisp functions into C code, invokes cc, and loads the resulting object
file. The benchmark becomes a test of the external C compiler.
Joachim Durchholz
Well, the external C compiler is a part of the compiler, then, so this
is actually OK.
I agree with Jon that having a benchmark that tests the compiler's
ability to pre-evaluate stuff isn't a bad idea.
I also agree with Paul that this benchmark tests a rather narrow
spectrum of cases (and probably not the case that Mark had in mind).
I think the benchmark should be split into variants: one that evaluates
a constant expression (tests compile-time evaluation), one that accepts
parameters for a fixed Minim program (tests partial compile-time
evaluation), and one that takes a Minim program as a parameter (tests
symbolic evaluation).
Regards,
Jo
Jon Harrop
> Are you kidding? Think of Kyoto Common Lisp for example. It compiles
> Lisp functions into C code, invokes cc, and loads the resulting object
> file. The benchmark becomes a test of the external C compiler.
Then that feature of Kyoto CL gives it an advantage over OCaml, which has no
built-in evaluator. That's something I'd like to measure. I'd also like to
compare with MetaOCaml's built-in evaluator that compiles using ocamlopt.
Paul Rubin
> Then that feature of Kyoto CL gives it an advantage over OCaml,
> which has no built-in evaluator. That's something I'd like to
> measure. I'd also like to compare with MetaOCaml's built-in
> evaluator that compiles using ocamlopt.
I wonder if it fits the shootout specification to just compile the
Minim program into machine code and then either invoke it externally
or load it into Ocaml through an FFI and run it.
Jon Harrop
> ...
I've added preprocessors that convert the string representations of variable
and tag names in the abstract syntax tree into int refs and int program
counters, respectively. The code that does this is really beautiful,
totalling only 26 more lines of code. The core new higher-order
function "subst" has the inferred type:
val subst :
('a -> 'b) ->
('c -> 'd) -> ('c, 'a) Expr.statement -> ('d, 'b) Expr.statement
Also, the program ran correctly the first time it passed type checking.
This makes the whole interpreter ~6x faster with the given benchmark now
taking only 0.008s:
open Expr
open Printf
let tags_of program =
let aux (pc, tags) = function
| Tag t -> pc, (t, pc)::tags
| _ -> pc+1, tags in
snd(List.fold_left aux (0, []) program)
let vars_of program =
let aux (n, tags) = function
| Assign(x, _) | Input x -> n+1, (x, ref 0)::tags
| _ -> n+1, tags in
snd(List.fold_left aux (0, []) program)
let subst_val vars = function
| Int n -> Int n
| Var x -> Var(vars x)
let rec subst_test vars = function
| Less(x, y) -> Less(subst_val vars x, subst_val vars y)
| Equal(x, y) -> Equal(subst_val vars x, subst_val vars y)
| Greater(x, y) -> Greater(subst_val vars x, subst_val vars y)
| And(x, y) -> And(subst_test vars x, subst_test vars y)
| Or(x, y) -> Or(subst_test vars x, subst_test vars y)
| Not x -> Not(subst_test vars x)
let rec subst tags vars = function
| Assign(x, y) -> Assign(vars x, subst_val vars y)
| Incr x -> Incr(vars x)
| Decr x -> Decr(vars x)
| If(p, t, f) -> If(subst_test vars p, subst tags vars t, subst tags vars
f)
| Goto tag -> Goto(tags tag)
| Tag _ -> invalid_arg "Unexpected tag"
| PrintString s -> PrintString s
| Print x -> Print(vars x)
| Input x -> Input(vars x)
let not_tag = function Tag _ -> false | _ -> true
let eval = function
| Int n -> n
| Var v -> !v
let rec test = function
| Less(f, g) -> eval f < eval g
| Equal(f, g) -> eval f = eval g
| Greater(f, g) -> eval f > eval g
| And(f, g) -> test f && test g
| Or(f, g) -> test f || test g
| Not f -> not(test f)
let rec statement pc = function
| Assign(x, y) -> x := eval y; pc + 1
| Incr x -> incr x; pc + 1
| Decr x -> decr x; pc + 1
| If(p, t, f) -> statement pc (if test p then t else f)
| Goto tag -> tag
| Tag _ -> pc + 1
| PrintString s -> print_string s; pc + 1
| Print x -> print_int !x; pc + 1
| Input x -> x := int_of_string(input_line stdin); pc + 1
let rec run program pc =
run program (statement pc program.(pc))
let () =
match Sys.argv with
| [|_; file|] ->
let ch = open_in file in
let program = Parser.program Lexer.token (Lexing.from_channel ch) in
close_in ch;
let tags = (fun m k -> List.assoc k m) (tags_of program) in
let vars = (fun m k -> List.assoc k m) (vars_of program) in
let program = List.filter not_tag program in
let program = List.map (subst tags vars) program in
let program = Array.of_list program in
(try run program 0 with _ -> ())
| _ -> invalid_arg "Usage: ./minim <file>"
--
Jon Harrop
Fine by me but the overhead of full-blown compilation will be significant.
Paul Rubin
> Fine by me but the overhead of full-blown compilation will be significant.
Nah. I mean invoking a heavyweight compiler like gcc would be slow,
but once you have a parse tree, you can spew straightforward machine
code that might be lousy by serious compiler standards, but should
still be much faster than any interpreter. You can even do that
sort of portably:
http://www.gnu.org/software/lightning/manual/lightning.html#Overview
There have also been Lisps that had embedded compilers and evalled by
generating machine code directly rather than invoking cc like KCL did.
Yale's T system (a Scheme dialect) did that. I don't remember its
read-eval-print loop pausing noticably even on the comparatively slow
machines of the 1990's (I think I used it on a Sun 3).
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> writes:
>> Fine by me but the overhead of full-blown compilation will be
>> significant.
>
> Nah. I mean invoking a heavyweight compiler like gcc would be slow,
Yes.
> but once you have a parse tree, you can spew straightforward machine
> code that might be lousy by serious compiler standards, but should
> still be much faster than any interpreter.
True. That could be a lot of work though.
> You can even do that sort of portably:
>
> http://www.gnu.org/software/lightning/manual/lightning.html#Overview
Doesn't support amd64, which rules it out for me.
> There have also been Lisps that had embedded compilers and evalled by
> generating machine code directly rather than invoking cc like KCL did.
> Yale's T system (a Scheme dialect) did that. I don't remember its
> read-eval-print loop pausing noticably even on the comparatively slow
> machines of the 1990's (I think I used it on a Sun 3).
I was under the impression that most Lisp compilers did this. What does SBCL
do?
Andras Simon
>
> > There have also been Lisps that had embedded compilers and evalled by
> > generating machine code directly rather than invoking cc like KCL did.
> > Yale's T system (a Scheme dialect) did that. I don't remember its
> > read-eval-print loop pausing noticably even on the comparatively slow
> > machines of the 1990's (I think I used it on a Sun 3).
>
> I was under the impression that most Lisp compilers did this. What does SBCL
> do?
Most of them do (SBCL doesn't even have an interpreter AFAIK).
Andras
Paul Rubin
> > http://www.gnu.org/software/lightning/manual/lightning.html#Overview
> Doesn't support amd64, which rules it out for me.
I thought that was added recently.
> > There have also been Lisps that had embedded compilers and evalled by
> > generating machine code directly rather than invoking cc like KCL did.
>
> I was under the impression that most Lisp compilers did this. What does SBCL
> do?
I thought it was more conventional to have both a compiler and an
interpreter, but I haven't used many full-scale CL implementations.
Ole Nielsby
This post is a commented PILS program.
It compiles the minix stock program to a set of PILS rules and executes
it by repeatingly applying the ruleset to a state node that holds the
variables.
The style is what I call narrative programming - I start with
the mimix program in a text literal, then describe what to do with it.
Parsing is done with a cheat - using 9 code lines.
The compiler as such approx. 45 code lines. I tried to cover all minix.
The "minix runtime" is 30-odd lines, mostly because PILS doesn't have
a console interface - the text input/output is done via wxWidgets dialogs.
Execution time for 100000 + 100000 is approx. 1.7 seconds on a
2GHz dual core2, using the VC2005 release build of the PILS system.
(Actually, I tested with 1000000 + 1000000 and got 17 seconds.)
I made the compiler as simple as possible - a few simple optimisations
would make it somewhat faster.
!!
{.test
|:ok
!!
Here goes the minix stock program.
String delimiters are doubled, by PILS convention
!!
"
(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
"
!!
To parse it using the PILS constant syntax,
replace () with [list: ] outside strings.
!!
split """"
split 2
each
( { a, b |:ok process (a), b }
{ a, | :ok process (a) }
where
{ process: string | :ok string replace ["(" "[list: " ")" "]"] } )
splice splice """"
!!
enclose in [] and readt, using the PILS parser
!!
call {s|:ok ?:? read ("[" (s) "]") }
!!
compile to tagged actions
!!
listwise counting
{ number := statement
| list [actions] :=
?tag number
.action
?next (' ?state) head (tag: number + 1);
statement try
{ / tag | :ok list [actions] := (?tag .action next); next }
{ .nl | :ok ::- ' print ""/; next }
{ list: [print], / v | :ok ::- (: print (: ' state . v)); next }
{ list: [print], $ string | :ok ::- (: print (string)); next }
{ list: [input], / v | :ok v := ' input }
{ list: [goto], / v | :ok ' (?state) head: tag: v }
{ list: [++], / v | :ok v := : val (v) + 1 }
{ list: [--], / v | :ok v := : val (v) - 1 }
{ list: / a, [is], b | :ok a := val (b) }
{ list: [if], if, [then], then, [else], else
| :self :ok
::if . try
{ list: a, [=], b | :ok : val (a) = val (b) }
{ list: a, [<], b | :ok : val (a) < val (b) }
{ list: a, [>], b | :ok : val (a) > val (b) }
{ list: a, [and], b | :self :ok ::if a try (self); b try (self) }
{ list: a, [or], b | :self :ok ::if a try (self); 1 .else b try
(self) }
{ list: [not], a | :self :ok : a <> 1 }
; then try (self)
.else . try (self)
}
where
! This rule implements assignment by constructing a new state
{ / v := e
| :where :ok
next merge: ?state
: (' state) merge: (node [?] (where . v) := e) node [?]
}
! Constant vals are as-is, variables must be fetched from the state
{ .val (= e) | :ok e }
{ .val (/ v) | :ok : ' state . v }
}
list [actions]
! tag/action pairs are wrapped
every
{?tag .action
| :ok ?match (' ?state) head (tag: tag) .action (::ok action)
}
first [?]
fold {rules := ?match .action|:ok ::match .action ; rules}
call {rules | :ok ::ruleset rules}
!!
This produces the following PILS rules:
{[tag: 1]: .state|:ok :- print "Add x and y (what a feat!)"; [tag: 2]:
.state}
{[tag: 2]: .state|:ok :- print ""/; [tag: 3]: .state}
{[tag: 3]: .state|:ok :- print "Input x: "; [tag: 4]: .state}
{[tag: 4]: .state|:ok [tag: 5]: .state . merge (?x input)}
{[tag: 5]: .state|:ok :- print ""/; [tag: 6]: .state}
{[tag: 6]: .state|:ok :- print "Input y: "; [tag: 7]: .state}
{[tag: 7]: .state|:ok [tag: 8]: .state . merge (?y input)}
{[tag: main]: .state|:ok [tag: 9]: .state}
{[tag: 8]: .state|:ok [tag: 9]: .state}
{[tag: 9]: .state|:ok :else ([tag: sub1x]: .state) .if state v = 0; [tag:
end]: .state}
{[tag: sub1x]: .state|:ok [tag: 11]: .state}
{[tag: 10]: .state|:ok [tag: 11]: .state}
{[tag: 11]: .state|:ok [tag: 12]: .state . merge (?x state v - 1)}
{[tag: 12]: .state|:ok [tag: 13]: .state . merge (?y state v + 1)}
{[tag: 13]: .state|:ok [tag: main]: .state}
{[tag: end]: .state|:ok [tag: 15]: .state}
{[tag: 14]: .state|:ok [tag: 15]: .state}
{[tag: 15]: .state|:ok :- print ""/; [tag: 16]: .state}
{[tag: 16]: .state|:ok :- print "The total of x and y is "; [tag: 17]:
.state}
{[tag: 17]: .state|:ok :- print (state v); [tag: 18]: .state}
{[tag: 18]: .state|:ok :- print ""/; [tag: 19]: .state}
Now run it, using the PILS editor window as base for dialogs
(wxWidgets PILS doesn't alow orphan dialogs, they mess up the event
handling)
!!
call
{ minix-rules
| :rule [runner];
?window [channel: editor] window;
( node [ps] print := "";
?endstate
([tag: 1]: .state ?:) repeat
( minix-rules ---
{ :nonsense | :what rule [runner] :ok what }
{ .print ($ string) | :ok node [ps] print := node [ps] print .
string }
{ .print ""/
| :ok
:if node [ps] print => +$ message;
:- window wx:MessageBox (message);
node [ps] print := ""
}
{ .print (% n)|:self :try self print (?:? write (n)) }
{ .input
| :if
window wx:GetTextFromUser (node [ps] print, "minix-input") => +$
text,
?:? read (text) => % text
;
node [ps] print := "";
:ok text
}
! for debugging, a rule can be inserted here.
! but {state|state bug (?:?)}
)
;
:ok endstate
)
node [ps]
}
}
!!
This should be a builtin, haven't implemented it yet.
list split 2 splits a list in pairs, etc.
!!
where
{ & list split (+ splitsize)
| :ok
list count repeat
{ + count | :ok list() := list <+# count ++# splitsize; count -
splitsize }
list()
}
Jon Harrop
> This whole post is a commented Qi program so you can load it into Qi.
How do I get a working Qi environment? I can't find a Debian package. Is
there a Lisp equivalent of CPAN or GODI that makes it easy to fetch and
install such things?
Mark Tarver
Ah, but thats a compiler Paul, not an interpreter.
Actually, thats easy in Lisp because Lisp includes many 'impure'
procedural constructions. I doubt it would be so easy to do in a pure
functional language.
Mark
Jon Harrop
> Parsing is done with a cheat - using 9 code lines.
> The compiler as such approx. 45 code lines.
The short interpreter is 63 LOC in OCaml or 133 LOC including the full lexer
and yacc-based parser.
> Execution time for 100000 + 100000 is approx. 1.7 seconds on a
> 2GHz dual core2, using the VC2005 release build of the PILS system.
Not meaning to be rude, but why are the Qi and PILS implementations so slow?
This is just looping and incrementing 100,000 times and you guys are getting
times ~1s? That means you're doing O(10,000) machine operations per loop of
the minim code, which is just crazy.
Mathematica is the slowest language that I have access to and even it only
takes 0.27s to complete this problem:
$ ledit MathKernel
Mathematica 5.1 for Linux x86 (64 bit)
Copyright 1988-2004 Wolfram Research, Inc.
-- Motif graphics initialized --
In[1]:= x=100000; y=100000;
In[2]:= Timing[While[x>0, --x; ++y]; y]
Out[2]= {0.26896 Second, 200000}
> (Actually, I tested with 1000000 + 1000000 and got 17 seconds.)
That is ~200x slower than the OCaml, which takes only 0.08s:
$ time ./eval.native test.minim <args.txt
Add x and y
Input x: 1000000
Input y: 1000000
The total of x and y is 2000000
real 0m0.080s
user 0m0.078s
sys 0m0.002s
Rewriting the test Minim program in OCaml:
let x = ref 1000000
let y = ref 1000000
let () =
while !x>0 do
decr x;
incr y;
done;
Printf.printf "y=%d\n%!" !y
and running it using OCaml's bytecode interpreter takes only 0.004s so it is
20x faster than my naive term-level interpreter, which sounds about right.
I can't imagine what you're doing to make it run another 200 times slower
though...
Mark Tarver
let me post and replying on Google which lets me reply (sometimes) but
does not let me read my own post. Rather weird - like watching a film
in which the action is out of sync with the sound. I'm going to
suppose that this ends up where it should.
> This is ok but I think minim is a little too simple.
Well its a post, so I wanted it not to be too long.
> Can you write a parser so the program can be loaded from a text file written
> in the syntax you described? Unfair to hard code it...
Not needed - just place (time (run ....)) into a text file and load it
with type checking enabled.
The type checker will parse the input to ensure it conforms to the
requirements.
> Can you give an example of errors that your static type system catches?
Any syntax error in a Minim program; for example missing a 'then' in
an if-statement.
Any error in my interpreter that comes from getting Minim syntax wrong
or getting
confused over my data structures - e.g. trying to find the value of a
constant.
Mark
Mark Tarver
Not meaning to be rude, but why are the Qi and PILS implementations so
slow?
This is just looping and incrementing 100,000 times and you guys are
getting
times ~1s? That means you're doing O(10,000) machine operations per
loop of
the minim code, which is just crazy.
Mathematica is the slowest language that I have access to and even it
only
takes 0.27s to complete this problem:
let x = ref 1000000
let y = ref 1000000
let () =
while !x>0 do
decr x;
incr y;
done;
Printf.printf "y=%d\n%!" !y
and running it using OCaml's bytecode interpreter takes only 0.004s so
it is
20x faster than my naive term-level interpreter, which sounds about
right.
I can't imagine what you're doing to make it run another 200 times
slower
though...
UNQUOTE
Come on Jon; that's trying it on :). Of course if you take my Minim
program
and hand compile it into another language - even a slow one like
Mathematica
- it will run faster than my interpreter. I can hand compile it into
procedural
Lisp and I guarantee it will be blazingly quick. You can't make
meaningful comparisons
like that.
But you want a faster interpreter than the one I wrote - OK see my
next post.
(You'll undoubtedly see it before I do thanks to Google).
Nice try, but no cigar and early bedtime with no tea.
Mark
PS This has appeared in the right thread but not in exactly the right
place because
Google still thinks its yesterday and therefore Jon has not made any
such post as the
one to which I am replying which according to Google I will not reply
to until tomorrow.
Confused? Don't worry about it.
Jon Harrop
> Come on Jon; that's trying it on :). Of course if you take my Minim
> program and hand compile it into another language - even a slow one like
> Mathematica - it will run faster than my interpreter.
I don't understand why you would think that.
> I can hand compile it into procedural Lisp and I guarantee it will be
> blazingly quick. You can't make meaningful comparisons like that.
These results are all for interpreters (no hand compiling, except the
hard-coded Minim program in your Qi):
Mark's Qi: 2s
Ole's PILS: 2s
Mathematica: 0.3s
Jon's OCaml: 0.08s
How do you explain the differences?
> But you want a faster interpreter than the one I wrote - OK see my
> next post.
> (You'll undoubtedly see it before I do thanks to Google).
>
> Nice try, but no cigar and early bedtime with no tea.
I'm waiting. :-)
Raffael Cavallaro
> Of course if you take my Minim
> program
> and hand compile it into another language - even a slow one like
> Mathematica
> - it will run faster than my interpreter. I can hand compile it into
> procedural
> Lisp and I guarantee it will be blazingly quick. You can't make
> meaningful comparisons
> like that.
You seem to have mistaken Jon for a legitimate, fair minded,
correspondent to this newsgroup. He is a spammer trying to sell his
ocaml and f# consulting services. He will never post anything unless it
shows these two languages, from which he earns his living, in a
favorable light, whether the comparison is fair or not.
Joachim Durchholz
> Actually, thats easy in Lisp because Lisp includes many 'impure'
> procedural constructions. I doubt it would be so easy to do in a pure
> functional language.
Quite to the contrary.
They don't have to do aliasing or dataflow analysis to do that kind of
optimization. I'd expect that kind of optimization to happen far more
early in the development cycle of a compiler, and that it will stay more
aggressive throughout the compiler's lifetime.
Regards,
Jo
Ole Nielsby
> Ole Nielsby wrote:
>> Parsing is done with a cheat - using 9 code lines.
>> The compiler as such approx. 45 code lines.
>
> The short interpreter is 63 LOC in OCaml or 133 LOC including the full
> lexer
> and yacc-based parser.
The Kvernbitr parser generator (written in PILS) can parse yacc-unfriendly
languages like VB6 and SQL, using a BNF-like syntax. I haven't yet ported
it to the new PILS dialect which I am going to publish soon.
>> Execution time for 100000 + 100000 is approx. 1.7 seconds on a
>> 2GHz dual core2, using the VC2005 release build of the PILS system.
>
> Not meaning to be rude, but why are the Qi and PILS implementations so
> slow?
> Mathematica is the slowest language that I have access to and even it only
> takes 0.27s to complete this problem
Whereas PILS takes 0.35s using a direct approach (comparable to the
Mathematica snippet you posted):
(?x 100000 .y 100000)
repeat {: ?x . [+] .y|:ok ?x . - 1 .y . + 1}
y
So it's about the same speed as Mathematica - assumig similar CPUs.
The slowness is mostly due to boxing and unifying of numbers. This
makes PILS unfit for serious number crunching, whereas processing of
texts and node trees is quite fast. So the speed depends on what you
use it for. The unified number boxing may be bad for numeric calculations
but it is part of a strategy that makes pattern matching very fast. So it's
a tradeoff by design.
There is still room for improvement though. There are things I could
do to the PILS interpreter to bypass boxing in cases like this - it's just
not a priority now, the language was never meant for number crunching.
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> wrote:
>> Ole Nielsby wrote:
>> The short interpreter is 63 LOC in OCaml or 133 LOC including the full
>> lexer
>> and yacc-based parser.
>
> The Kvernbitr parser generator (written in PILS) can parse yacc-unfriendly
> languages like VB6 and SQL, using a BNF-like syntax. I haven't yet ported
> it to the new PILS dialect which I am going to publish soon.
Yes. I tried writing the parser in camlp4 and using streams first but never
got them to work. I'm going to have another hack at a stream-based parser
as it will be much shorter.
>>> Execution time for 100000 + 100000 is approx. 1.7 seconds on a
>>> 2GHz dual core2, using the VC2005 release build of the PILS system.
>>
>> Not meaning to be rude, but why are the Qi and PILS implementations so
>> slow?
>> Mathematica is the slowest language that I have access to and even it
>> only takes 0.27s to complete this problem
>
> Whereas PILS takes 0.35s using a direct approach (comparable to the
> Mathematica snippet you posted):
>
> (?x 100000 .y 100000)
> repeat {: ?x . [+] .y|:ok ?x . - 1 .y . + 1}
> y
>
> So it's about the same speed as Mathematica - assumig similar CPUs.
Argh, I see. You were both running interpreters in interpreted languages. I
should compile the OCaml to interpreted bytecode rather than native code
for a fairer comparison then. In which case I get (neglecting machine
differences):
CLisp: 0.86s
PILS: 0.35s
OCaml: 0.11s
That's much more inline with what I'd expect.
Mark Tarver
When Qi first came out it ran only under Windows CLisp and so I used
to
distribute executables. Since then Qi has been ported to Allegro,
SBCL and
CMUCL and runs under Xnix and Windows. So I stopped issuing
executables
because the combinations of platforms and OS were too many. The
download from
Lambda Associates assumes that you've already got one of these Lisps
and
takes it from there.
J. T. Gleason runs a Google open source repository for Qi and he has
written
an installation package for Qi - see http://code.google.com/p/qilang/
The fastest platform is (I think) CMUCL though I haven't timed it
against
my beta release Windows SBCL.
Mark
Mark Tarver
> hard-coded Minim program in your Qi):
>
> Mark's Qi: 2s
> Ole's PILS: 2s
> Mathematica: 0.3s
> Jon's OCaml: 0.08s
>
> How do you explain the differences?
Ok; not majorly important but the 2s is only for Qi under CLisp.Here
is Qi on an experimental SBCL.
This is experimental prerelease support for the Windows platform: use
at your own risk. "Your Kitten of Death awaits!"
............................................
(3+) (time (run [
[print "Add x and y"]
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]))
Add x and y
Input x: 10000
Input y: 10000
The total of x and y is 20000
Evaluation took:
6.75 seconds of real time
0.03125 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
655,344 bytes consed.
[(@p x 0) (@p y 20000)] : (list (symbol * number))
Sadly the kitten of death gets me after this, because I suppose, its
an experimental port. At the cost of much pain I could run this
under CMUCL, but I loathe using Linux and its a drag installing 9.0
under my Ubuntu. But project the above timing by x10 and you're
looking at a ball park figure of 0.3-0.4s under a well-configured
Lisp; that is at least 5 times faster than my 2.0s under CLisp.
But thats not the main issue. The main thing is that you are
comparing hand-compiled equivalents to my Minim program, written in
native Mathematica and OCaml, to Qi *interpreting* a Minim program.
Not commensurable at all.
Now regarding my Minim program being 'hard-coded'. I really don't
know what that means here. Your Mathematica program is certainly hard-
coded. The Minim program corresponds exactly to the BNF laid down -
its not tweaked at all.
Mark
David Golden
> Sadly the kitten of death gets me after this, because I suppose, its
> an experimental port.
Maybe. Turns out that having (tc +) on in qi 7.3 will crash under sbcl
1.0.7 on linux on load of the source of your minim implementation on my
machine, with a joyful and rather unusual "Unhandled memory fault at
#x0."
> At the cost of much pain I could run this
> under CMUCL, but I loathe using Linux
Well, hey, I loathe using Windows. Strange though. Are you
sure you loathe using Linux? Maybe you just loathe a
particular desktop environment for Linux like GNOME? If you have
ubuntu, try "apt-get install kubuntu-desktop" (or use the package
management GUI), and select a KDE session instead of a GNOME one upon
next login.
> Now regarding my Minim program being 'hard-coded'. I really
> don't know what that means here.
Well, obviously you're not compiling the input expression into the
program which is what "hard coding" would usually suggest to me (like
jon hard coded the input expression into his ml program rather than
reading it at run time in the previous "simplify" example). He may
have some issue with you supplying the minim program at runtime to the
interpreter as lists though. That's not what I'd call "hard coding". It
is skipping lexing, or at least reusing the lisp reader's
[sorta-]lexing instead of writing your own, though. There are of
course lexer packages for use in lisp around, though I haven't used
them much myself, e.g. Michael Parker's
http://www.geocities.com/mparker762/clawk.html
Jon Harrop
> But thats not the main issue. The main thing is that you are
> comparing hand-compiled equivalents to my Minim program, written in
> native Mathematica and OCaml, to Qi *interpreting* a Minim program.
> Not commensurable at all.
No, I'm comparing your interpreter to my interpreter (the one I posted).
> Now regarding my Minim program being 'hard-coded'. I really don't
> know what that means here. Your Mathematica program is certainly hard-
> coded.
Yes.
> The Minim program corresponds exactly to the BNF laid down - its not
> tweaked at all.
You gave a BNF:
<program> := <statement>
| <statement> <program>;
<statement> := <assignment>
| <conditional>
| <goto>
...
But it appears that your program does not include a lexer and parser,
instead having the Minim program hard-coded in the Qi source code:
(3+) (time (run [
[print "Add x and y"]
nl
[print "Input x: "]
...
My interpreter loads its input program from the specified text file. I think
that is an important difference in terms of functionality. Perhaps I have
misunderstood.
Mark Tarver
> 1.0.7 on linux on load of the source of your minim implementation on my
> machine, with a joyful and rather unusual "Unhandled memory fault at
> #x0."
Can't comment on this - CLisp compiles and runs it fine.
My 1.0.6 SBCL crashes worse than 1.0 with a different error message.
1.0 sometimes crashes while loading this program and sometimes it
loads it. I think on balance of probability there is a problem in
SBCL somewhere. This is why I generally use the slower but more
stable CLisp. Try it.
>
> > At the cost of much pain I could run this
> > under CMUCL, but I loathe using Linux
>
> Are you> sure you loathe using Linux?
OK; let me check .... hmmm, yes, yes I do.
> He may
> have some issue with you supplying the minim program at runtime to the
> interpreter as lists though. That's not what I'd call "hard coding".
Agreed.
> It
> is skipping lexing, or at least reusing the lisp reader's
> [sorta-]lexing instead of writing your own, though.
OK; that's a different point. Actually Qi has its own lexer and all
the input is going through that. I was not assuming that people needed
to implement a lexer, but that might be needed for certain languages
which be limited to string entry etc. But my entry corresponds to the
BNF for Minim.
Mark
Mark Tarver
> instead having the Minim program hard-coded in the Qi source code:
>
> (3+) (time (run [
> [print "Add x and y"]
> nl
> [print "Input x: "]
> ...
>
> My interpreter loads its input program from the specified text file. I think
> that is an important difference in terms of functionality. Perhaps I have
> misunderstood.
See remark above, just put my line entry into a file and load it. The
parsing is done by the Qi type checker based on the spec in my
interpreter program.
If you want to seperate out the reading from the execution then define
(define run-minim
{string --> symbol}
File -> (time (load File)))
and put (run <put your Minim program here> into the file.
(6+) (run-minim "minim add.txt")
Add x and y
Input x: ... etc.
Hack my Minim program and put in an error (missing then)
[if [x = 0] [goto end] else [goto sub1x]]
(7+) (run-minim "minim add.txt")
error: type error
Mark
Jon Harrop
> Hack my Minim program and put in an error (missing then)
>
> [if [x = 0] [goto end] else [goto sub1x]]
>
> (7+) (run-minim "minim add.txt")
> error: type error
Perhaps I am mistaken, but this is not the grammar that you described
because the text file you're loading must be translated into Qi notation by
hand (by adding [ ] etc.)?
Mark Tarver
If you prefer round brackets, then load it through Lisp.
(run '(etc etc....))
or if you hate the (run '( bit just type in Qi
(1-) (run (read-file "minim program.txt"))
with this in the file
(print "Add x and y")
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
I probably need to add a typed version of read-file; would be useful.
But that works.
The problem here I think is the OCaml technology. A Minim program is
just a list of a particular structure. But languages like ML and its
relatives do not operate kindly with free form lists as does Lisp. In
this event ML expects you to define constructor functions and if the
original source is not in that form then you need to lex and parse it
into your internal representation.
Qi does not need to do that with Minim because the Qi approach to
typing is designed to be consistent with the Lisp approach to
programming. No Qi/Lisp programmer will write a Minim lexer that is
effectively nothing more than an identity function w.r.t. the input,
and parsing is not needed in Qi because if the syntax is wrong the Qi
type checker will tell him.
Your adopted religion requires you to operate in this way; like having
to eat cold boiled spinach on Sunday. But I have no appetite for
eating cold spinach; this is why I left languages like ML, OCaml and
Haskell behind a long time ago.
Mark
MetaProgrammer
> \Jon suggested that it would be good to implement some significant
> programs in different functional languages for comparison. He
> suggested interpreters for procedural languages like Basic.
Hi there!
Here is our solution, using the .NET framework and MBase
(see http://www.meta-alternative.net/techpreview.html)
The compiled code works even faster than corresponding C# code,
compilation time is reasonably small.
-------
;;; Language abstract syntax tree
(def:ast minim ()
(*TOP* <program>) ;; entry point, used internally
(program <*statement:sts>)
(statement
(| (Ass <ident:var> <val:val>)
(++ <ident:var>)
(-- <ident:var>)
(Cnd <test:tst> <statement:tr> <statement:fl>)
(Gto <ident:tag>)
(Tag <ident:tag>)
(PrntStr <string:val>)
(PrntVal <val:val>)
(PrntNl)
(Input <ident:v>)
))
(test
(| (Comp cmp <val:left> <val:right>)
(And <test:left> <test:right>)
(Or <test:left> <test:right>)
(Not <test:t>)
))
(val (| (V <ident:v>) (C num)))
)
;;; Some .NET stuff
(define _print_mtd (r_mtd "System.Console" "Write" object))
(define _readline_mtd (r_mtd "System.Console" "ReadLine"))
(define _parse_mtd (r_mtd "System.Int32" "Parse" string))
;;; Compiler: compiling minim program into .NET IL
(function minim->cli ( expr )
(<> expr
(ast:visit minim program
(program DEEP ;; flatten the compiled statements list
(foldl append '() sts))
(statement DEEP ( ;; compile the statement, deeper ones first
(Ass
`((local ,var ,t_Int32)
,@val
(Stloc (var ,var))))
(++ `((Ldloc (var ,var))
,(_ldc_i4 1)
(Add)
(Stloc (var ,var))))
(-- `((Ldloc (var ,var))
,(_ldc_i4 1)
(Sub)
(Stloc (var ,var))))
(Cnd
(with-syms (lend lfl)
`(,@tst
(Brfalse (label ,lfl))
,@tr
(Br (label ,lend))
(label ,lfl)
,@fl
(label ,lend)
)))
(Gto `((Br (label ,tag))))
(Tag `((label ,tag)))
(PrntStr
`((Ldstr ,val) (Call ,_print_mtd)))
(PrntVal
`(,@val (Box ,t_Int32)
(Call ,_print_mtd)))
(PrntNl
`((Ldstr "\n") (Call ,_print_mtd)))
(Input
`((local ,v ,t_Int32)
(Call ,_readline_mtd)
(Call ,_parse_mtd)
(Stloc (var ,v))))))
(val DEEP ( ;; compile the value lookup
(V `((Ldloc (var ,v))))
(C `(,(_ldc_i4 num)))))
(test DEEP ( ;; compile the test statement
(Comp
`(,@left ,@right
,(case cmp ((>) '(Cgt)) ((<) '(Clt)) ((=) '(Ceq)))))
(And `(,@left ,@right (And)))
(Or `(,@left ,@right (Or)))
(Not `(,t (Not)))))
)))
;;; Being fair: won't reuse s-expressions parser,
;;; implementing a real one, with an advantage of
;;; readable error messages.
;; Simple lexer: splits the stream into tokens
(make-simple-lexer minim-lexer
(ident-or-keyword
(p.alpha ((p.alpha | p.digit) *))
ident)
(keywords input print nl goto if then else and or not is)
(simple-tokens
"[" LB "]" RB
"(" LB ")" RB
">" > "<" < "=" = "++" ++ "--" --)
(regexp-tokens
(("\"" (((#\\ #\") | (! #\")) *) "\"") ->
(M@ list->string cuttail cdr)) string
(("\'" (((#\\ #\') | (! #\')) *) "\'") ->
(M@ list->string cuttail cdr)) string
p.integer.p number)
(ignore p.whitespace))
;; Simple LL(1) parser
(bnf-parser ((programg parse-minim))
(programg
((LB program RB) $1) ;; not quite conforming to formal spec,
;; but required to run the test prog.
)
(program
((statement program) (cons $0 $1))
((statement) (list $0)))
(statement
((LB ident:va is val:vl RB) `(Ass ,va ,vl))
((LB ++ ident:va RB) `(++ ,va))
((LB -- ident:va RB) `(-- ,va))
((LB goto ident:tag RB) `(Gto ,tag))
((LB if test:tst then statement:s1 else statement:s2 RB)
`(Cnd ,tst ,s1 ,s2))
((LB print string:str RB)
`(PrntStr ,str))
((LB print val:v RB)
`(PrntVal ,v))
((nl)
`(PrntNl))
((LB input ident:va RB)
`(Input ,va))
((ident)
`(Tag ,$0)))
(val
((ident) `(V ,$0))
((number) `(C ,$0)))
(test
((LB val:v1 comp:c val:v2 RB) `(Comp ,c ,v1 ,v2))
((LB test:l and test:r RB) `(And ,l ,r))
((LB test:l or test:r RB) `(Or ,l ,r))
((LB not test:t RB) `(Not ,t)))
(comp
((<) '<)
((>) '>)
((=) '=))
)
;; Compiler frontend: macro which embedds the compiled IL assebmly
;; into the Lisp function and calls that function immediately.
;; In case of an error it prints the message, doing nothing.
(macro include-minim (fname)
(try
(let* ((ll (lex-and-parse minim-lexer parse-minim
(read-file-list fname)))
(lp (minim->cli ll))
(nm (gensym)))
`(begin
(function ,nm ()
(n.asm ()
,@lp
(Ldnull)
))
(,nm)
))
t_MBaseException
(fun (e)
(writeline `(Exception in minim loader: ,(mbaseerror e)))
'nil)))
;; Now: test it.
(include-minim "test1.min")
MetaProgrammer
change the last macro into the following:
;; Compiler frontend: macro which embedds the compiled IL assebmly
;; into the Lisp function and calls that function immediately.
;; In case of an error it prints the message, doing nothing.
(macro include-minim-f (nm fname)
(try
(let* ((ll (lex-and-parse minim-lexer parse-minim
(read-file-list fname)))
(lp (minim->cli ll)))
`(function ,nm ()
(n.asm ()
,@lp
(Ldnull)
)
))
t_MBaseException
(fun (e)
(writeline `(Exception in minim loader: ,(mbaseerror e)))
'nil)))
(macro include-minim ( fname )
(with-syms ( nm )
`(top-begin
(include-minim-f ,nm ,fname)
(,nm))))
----
And compile now the following file (using mbase /compiledll
<filename>):
(n.module mcomp exe)
(include "./minim.al")
;;; MINIM language compiler frontend for standalone executables.
(function main ( )
(let ((fnm (car (a->l *CMDLINE*))))
(read-int-eval '(n.module minim exe))
(read-compile-eval
`(include-minim-f main ,fnm))
(read-int-eval '(save-module))
))
----
After that, just do "mcomp ./test1.min", and "minim.exe" to run the
resulting program.
Matthias Blume
> Qi does not need to do that with Minim because the Qi approach to
> typing is designed to be consistent with the Lisp approach to
> programming. No Qi/Lisp programmer will write a Minim lexer that is
> effectively nothing more than an identity function w.r.t. the input,
> and parsing is not needed in Qi because if the syntax is wrong the Qi
> type checker will tell him.
I think you are being unfair here. Clearly, you designed the language
specifically so that it can be parsed trivially using Lisp.
(Well, at least as long as you allow an extra pair of parentheses
around your program -- something that the original grammar you posted
did not.)
And, strangely, you don't even stick to that syntax but use a
different one in your Qi implementation...
> Your adopted religion requires you to operate in this way; like having
> to eat cold boiled spinach on Sunday. But I have no appetite for
> eating cold spinach; this is why I left languages like ML, OCaml and
> Haskell behind a long time ago.
Well, Jon may come across as a bit nutty at times, but at least he
restricts his spinach-eating to Sundays.
IMNSHO, to be on level playing ground, the syntax of the language to
be interpreted should not blatantly favor one of the contestants.
Or would you agree to a syntax that happens to match, say, Haskell
data syntax? Haskell programmers would have a huge advantage, since
they would just declare the data types for the abstract syntax, add
"deriving Read", and be done with the parser...
Cheers,
Matthias
Jon Harrop
> The problem here I think is the OCaml technology...
Allow me to cripple the OCaml, making it as featureless as the Lisp:
module Bindings = Map.Make(String)
let set m x y = Bindings.add x y m
let get m x = Bindings.find x m
let tags_of program =
let aux (pc, tags) = function
| `Tag t -> pc+1, Bindings.add t pc tags
| _ -> pc+1, tags in
let _, tags = Array.fold_left aux (0, Bindings.empty) program in
tags
let eval vars = function
| `Lit n -> n
| `Var v -> get vars v
let rec test vars = function
| `Less(f, g) -> eval vars f < eval vars g
| `Equal(f, g) -> eval vars f = eval vars g
| `Greater(f, g) -> eval vars f > eval vars g
| `And(f, g) -> test vars f && test vars g
| `Or(f, g) -> test vars f || test vars g
| `Not f -> not(test vars f)
let rec statement tags vars pc = function
| `Assign(x, y) -> set vars x (eval vars y), pc + 1
| `Incr x -> set vars x (get vars x + 1), pc + 1
| `Decr x -> set vars x (get vars x - 1), pc + 1
| `If(p, t, f) -> statement tags vars pc (if test vars p then t else f)
| `Goto tag -> vars, Bindings.find tag tags
| `Tag _ -> vars, pc + 1
| `PrintString s -> print_string s; vars, pc + 1
| `Print x -> print_int(get vars x); vars, pc + 1
| `Input x -> set vars x (int_of_string(input_line stdin)), pc + 1
let rec run program tags (vars, pc) =
run program tags (statement tags vars pc program.(pc))
let () =
run
[|PrintString "Add x and y"; PrintString "\n"; PrintString "Input x: ";
Input "x"; PrintString "\n"; PrintString "Input y: "; Input "y";
Tag "main"; If (Equal (Var "x", Lit 0), Goto "end", Goto "sub1x");
Tag "sub1x"; Decr "x"; Incr "y"; Goto "main"; Tag "end";
PrintString "\n"; PrintString "The total of x and y is "; Print "y";
PrintString "\n"|]
(tags_of program) (Bindings.empty, 0)
> Your adopted religion requires you to operate in this way...
As you can see, the OCaml operates perfectly well both ways. The Lisp,
however, does not.
Jon Harrop
> Mark Tarver <dr.mt...@ukonline.co.uk> writes:
>> Qi does not need to do that with Minim because the Qi approach to
>> typing is designed to be consistent with the Lisp approach to
>> programming. No Qi/Lisp programmer will write a Minim lexer that is
>> effectively nothing more than an identity function w.r.t. the input,
>> and parsing is not needed in Qi because if the syntax is wrong the Qi
>> type checker will tell him.
>
It would be unfair to compare the similar-sized Lisp and OCaml
implementations when only the OCaml implements a lexer and parser. Provided
you strip the lexer and parser from the OCaml, I think it is fair. The
OCaml remains several times faster and is now several times shorter as
well.
I think it is a shame that Mark backtracked from a description of the
grammar only to hard-code the interpreted program in the interpreter. I
would have liked to see a lexer and parser written in Lisp. Now I can only
assume that it is prohibitively difficult to implement such trivial
functionality correctly in Lisp.
Andy Freeman
> Now I can only
> assume that it is prohibitively difficult to implement such trivial
> functionality correctly in Lisp.
Great!
Now go tell other people how OCaml/F# are superior to lisp and leave
those of us who noticed that the above is nothing more than a claim
about your limitations in peace.
-andy
Mark Tarver
Ah, that's quite legitimate, but not the point Jon is making. Jon is
saying 'Where's your lexer?' and I'm saying 'Actually Qi doesn't need
one here for this example' - the lexer is the identity function.
Properly
then we can level the field by taking out his lexer
from LOC and the timings and that would be fine by me.
More sensible than requiring me to write a lexer that does nothing -
that's very dull :(. And the parsing is done by the Qi type checker.
The rest of his complaint about needing []s and run is easily solved
(see my reply to him).
Mark
Mark Tarver
Actually it is a doddle in this case. I didn't attach vast importance
to this issue. OK
(define load-and-run-minim
File -> (time (run (read-file File)))
will do the trick. This runs the following program in a file.
(print "Add x and y")
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
This runs in untyped mode - I could get a version to run in typed mode
with little effort.
> I would have liked to see a lexer and parser written in Lisp.
I've said before, and I'll repeat it again, that the Qi type checker
is doing the parsing here. A Lisper might volunteer to write you a
parser, but again I have no motivation or need to do so. I've even
less motivation to write a lexer that acts as the identity function.
> I can only
> assume that it is prohibitively difficult to implement such trivial
> functionality correctly in Lisp.
You assume wrong, and you assume that people in comp.lang.lisp will
rush to disabuse you. Read CLTL on reader macros.
> The OCaml remains several times faster and is now several times
> shorter as well.
Um, well you need to get rid of those timings of Minim-written-in-
OCaml/Mathematica which are about as relevant here as the contents of
the Great Pyramid.
I think you had these readings
QUOTE
I get roughly the same performance from OCaml's interpreted bytecode:
..........
real 0m0.583s
user 0m0.569s
sys 0m0.005s
UNQUOTE
Thats about the same as I'd expect from an SBCL that didn't blow up in
my face - maybe a little slower. But in the ball park.
QUOTE
However, native-code is over an order of magnitude faster:
................
real 0m0.050s
user 0m0.048s
sys 0m0.001s
UNQUOTE
Obviously the OCaml compiler is very efficient. But you know perhaps
that the Qi program can be made faster (and shorter to boot)?
Mark
Mark Tarver
\I don't reckon so; Lisp is a very easy target for *compiling* Minim.
Here's the code which runs under the Qi environment. It takes a Minim
program in one file and outputs the corresponding Lisp to be LOADed
into Qi.\
(define compile-minim-to-lisp
In Out -> (write-to-file Out
[TIME [BLOCK [] [TAGBODY | (map compile-statement (read-
file In))]]]))
(define compile-statement
[++ V] -> [INCF V]
[-- V] -> [DECF V]
[goto Tag] -> [GO Tag]
[if X then Y else Z] -> [if (compile-test X)
(compile-statement Y)
(compile-statement Z)]
[input V] -> [SETQ V [READ]]
[print Message] -> [FORMAT T "~A" Message]
[Var is Val] -> [SETQ Var Val]
nl -> [TERPRI]
Tag -> Tag)
(define compile-test
[X > Y] -> [> X Y]
[X = Y] -> [= X Y]
[X < Y] -> [< X Y]
[P and Q] -> [and (compile-test P) (compile-test Q)]
[P or Q] -> [or (compile-test P) (compile-test Q)]
[not P] -> [not (compile-test P)]
P -> P)
\The compiled output of this program uses Qi booleans but can be
LOADED into Qi just like any other Lisp program.
(14-) (compile-minim-to-lisp "f.txt" "g.txt")
"g.txt"
(15-) (COMPILE-FILE "g.txt")
P"C:Documents and Settings/User/My Documents/Qi 9.0/g.fas"
(16-) (LOAD "g")
Add x and y
Input x: 100000
Input y: 100000
The total of x and y is 200000
Real time: 12.140625 sec.
Run time: 0.046875 sec.
About 50X faster than my interpreter - even under CLisp.
It is easy for precisely the reason I gave; because Lisp includes
these impure procedural features as part of the language spec.
This is too trivial as a challenge problem and too biased to Lisp,
hence I didn't set it.
Mark\
Jon Harrop
> Actually it is a doddle in this case. I didn't attach vast importance
> to this issue. OK
>
> (define load-and-run-minim
> File -> (time (run (read-file File)))
>
> will do the trick. This runs the following program in a file.
>
> (print "Add x and y")
> nl
>
> I've said before, and I'll repeat it again, that the Qi type checker
> is doing the parsing here.
This is the input program according to the task that you set and the grammar
that you provided:
print "Add x and y"
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
My program handles it, yours requires the user to lex and parse it by hand
into s-exprs themselves.
> Obviously the OCaml compiler is very efficient. But you know perhaps
> that the Qi program can be made faster (and shorter to boot)?
Wonderful. Please post some code so that we can all test it objectively and
quantitatively.
Are we now removing the grammar, lexer and parser from this benchmark?
Matthias Blume
Did you actually try to compile this code? It does not look right.
(Unbound variable "program").
Mark Tarver
> This is the input program according to the task that you set and the grammar
> that you provided:
>
> print "Add x and y"
> nl
> print "Input x: "
> input x
> nl
> print "Input y: "
> input y
> main
> if x = 0 then goto end else goto sub1x
> sub1x
> -- x
Actually it isn't you know.
> Wonderful. Please post some code so that we can all test it objectively and
> quantitatively.
The easiest way to speed the program is to transfer it from CLisp to a
fast Lisp like CMUCL. A point of optimisation is to change the line.
[[++ Var] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (+ 1 (look-up Var Env)) Env))
to
[[++ Var] | Ss] Program Env
-> (run-loop Ss Program (fast-change-env Var inc Env))
where fast-change-env traverses the environment once instead of
traversing twice as in the old version.
(define fast-change-env
{symbol --> symbol --> env --> env}
Var Cmd [(@p Var Val) | Env] -> [(@p Var (if (= Cmd inc)
(+ 1 Val)
(- Val 1))) | Env]
Var Cmd [Binding | Env] -> [Binding | (fast-change-env Var Cmd Env)])
Running this under CMUCL gives about 0.25s to run the Minim program.
Much faster than CLisp's 2.1s. As I said, CLisp is slow.
For me there is no lexer, but you can count parsing into the time
which is here done by the Qi typechecker. It takes 2689 inferences to
read and typecheck (= parse) the Minim program into Qi and CLisp reads
and typechecks it from file at about 100-150K inferences/sec.
Real time: 4.828125 sec.
Run time: 0.03125 sec.
Space: 289524 Bytes
GC: 1, GC time: 0.0 sec.
loaded : symbol
600 KLIPS under CMU is about right according to my benchmarks, so the
time for this process is really quite small.
You can optimise it further and reduce the processing time to 0.17s
under CMU by dispensing with using an association list as an
environment and using the Lisp/Qi inbuilt assignment. The result
cannot be typechecked w.r.t. the type theory I supplied.
Actually this is not uncommon - often you can find shortcuts in a
program that work but are not demonstrably w.r.t. the type checker
type secure. There is a difference between what we can see to be true
and what can be formally demonstrated to be true within a given
framework (as Godel proved 80 years ago in another context). The
existence of this disparity is one reason why some programmers prefer
to work outside type secure languages because they see them as
preventing possible good solutions.
If you actually compile Minim into Lisp then the figures given have to
be divided by 50 or thereabouts. The compiler is also very small. As
I said above, you cannot meaningfully compare an OCaml version of the
Minim program to a Qi interpreter.
But staying within the bounds of type security you have this
Execution time under CMU: 0.25s
Read and typecheck (parse): 0.01s
This is twice as fast as OCaml interpreted bytecode, but 5X slower
than OCaml native code according to your benchmarks.
Mark
Jon Harrop
> Did you actually try to compile this code? It does not look right.
> (Unbound variable "program").
No, I was gedankencoding. :-)
Try this:
let () =
let program =
[|PrintString "Add x and y"; PrintString "\n"; PrintString "Input x: ";
Input "x"; PrintString "\n"; PrintString "Input y: "; Input "y";
Tag "main"; If (Equal (Var "x", Lit 0), Goto "end", Goto "sub1x");
Tag "sub1x"; Decr "x"; Incr "y"; Goto "main"; Tag "end";
PrintString "\n"; PrintString "The total of x and y is "; Print "y";
PrintString "\n"|] in
run program (tags_of program) (Bindings.empty, 0)
Jon Harrop
> ...
> Actually it isn't you know.
How so?
> This is twice as fast as OCaml interpreted bytecode, but 5X slower
> than OCaml native code according to your benchmarks.
I should probably detail the optimization phases that I've done as it sounds
like you're not doing them. They made it 6x faster.
1. Strip tags and replace the tags in gotos with program counters.
2. Replace each variable name with a reference to an integer.
These (particularly the latter) avoid all association list lookups during
interpreting.
Jon Harrop
> > Can you give an example of errors that your static type system catches?
>
> Any syntax error in a Minim program; for example missing a 'then' in
> an if-statement.
With the program hard-coded, such errors will be caught by OCaml's static
type system. When the program is lexed and parsed properly, the parser
would have caught that error.
Joachim Durchholz
>>> Lisp because Lisp includes many 'impure' procedural
>>> constructions. I doubt it would be so easy to do in a pure
>>> functional language.
>>
>> Quite to the contrary.
>> They don't have to do aliasing or dataflow analysis to do that kind of
>> optimization. I'd expect that kind of optimization to happen far more
>> early in the development cycle of a compiler, and that it will stay more
>> aggressive throughout the compiler's lifetime.
>
Now that's another topic.
I was specifically responding to the "preevaluate at compile time" bit,
now you're talking about - what? Lisp being useful as a target language?
(Maybe I misunderstood your original statement.)
Regards,
Jo
Jon Harrop
> Run time: 0.046875 sec.
>
> About 50X faster than my interpreter - even under CLisp.
Then its performance is comparable to my OCaml interpreter (0.043s). Note
that this isn't surprising because this benchmark only tests a part of
CLisp that is about the size of my interpreter (scaled by the relative
verbosity of Lisp, of course).
> It is easy for precisely the reason I gave; because Lisp includes
> these impure procedural features as part of the language spec.
So you're saying Lisp might beat Haskell? That's great but don't forget: its
the taking part that counts.
> This is too trivial as a challenge problem and too biased to Lisp,
> hence I didn't set it.
I'm not sure that this is biased towards Lisp. I'd write a Minim -> C
compiler in OCaml...
Mark Tarver
>
> (Maybe I misunderstood your original statement.)
Exactly - that is what I as talking about.
Mark
David Golden
> Mark Tarver wrote:
>> ...
>> Actually it isn't you know.
>
> How so?
>
Well, the BNF had left and right round brackets embedded in it...
It says
<conditional> := (if <test> then <statement> else <statement>);
not
<conditional> := if <test> then <statement> else <statement>;
They're round rather than square brackets, of course, but hey.
Jon Harrop
I finally managed to get a version working using the new camlp4 system to
implement an in-line extensible parser. The result is a 68-line interpreter
that runs more quickly than all other implementations so far:
open Camlp4.Sig;;
open Camlp4.Struct;;
let tags = ref [] and vars = ref [];;
let rec get m k =
try List.assoc k !m with Not_found -> m := (k, ref 0) :: !m; get m k
let pc = ref 0;;
module Token = Token.Make(Loc);;
module Lexer = Lexer.Make(Token);;
module Gram = Grammar.Static.Make(Lexer);;
let program = Gram.Entry.mk "program";;
let program_aux = Gram.Entry.mk "program_aux";;
let statement = Gram.Entry.mk "statement";;
let value = Gram.Entry.mk "value";;
let test = Gram.Entry.mk "test";;
let comp = Gram.Entry.mk "comp";;
EXTEND Gram
program:
[ [ ss=LIST1 program_aux -> Array.of_list ss ] ];
program_aux:
[ [ s=statement -> incr pc; s ] ];
statement:
[ [ x=LIDENT; "is"; y=value -> `Assign(get vars x, y)
| "++"; x=LIDENT -> `Incr(get vars x)
| "--"; x=LIDENT -> `Decr(get vars x) ]
| [ "if"; p=test; "then"; t=statement; "else"; f=statement -> `If(p, t,
f) ]
| [ "goto"; t=LIDENT -> `Goto(get tags t) ]
| [ t=LIDENT; s=statement -> get tags t := !pc; s ]
| [ "print"; s=STRING -> `PrintString s
| "print"; v=value -> `Print v
| "nl" -> `PrintString "\n" ]
| [ "input"; x=LIDENT -> `Input(get vars x) ] ];
value:
[ [ x=LIDENT -> `Var(get vars x)
| n=INT -> `Int(int_of_string n) ] ];
test:
[ [ a=value; op=comp; b=value -> `Comp(op, a, b) ]
| [ a=test; "and"; b=test -> `And(a, b) ]
| [ a=test; "or"; b=test -> `Or(a, b) ]
| [ "not"; a=test -> `Not a ] ];
comp:
[ [ "<" -> `Less | "=" -> `Equal | ">" -> `Greater ] ];
END;;
let eval = function `Int n -> (n : int) | `Var v -> !v
let rec test = function
| `Comp(`Less, f, g) -> eval f < eval g
| `Comp(`Equal, f, g) -> eval f = eval g
| `Comp(`Greater, f, g) -> eval f > eval g
| `And(f, g) -> test f && test g
| `Or(f, g) -> test f || test g
| `Not f -> not(test f)
let rec statement pc = function
| `Assign(x, y) -> x := eval y; pc + 1
| `Incr x -> incr x; pc + 1
| `Decr x -> decr x; pc + 1
| `If(p, t, f) -> statement pc (if test p then t else f)
| `Goto tag -> !tag
| `PrintString s -> print_string s; pc + 1
| `Print x -> print_int(eval x); pc + 1
| `Input x -> x := int_of_string(input_line stdin); pc + 1
let rec run program pc = run program (statement pc program.(pc))
let () =
match Sys.argv with
| [|_; file|] ->
let ch = open_in file in
let program = Gram.parse program Loc.ghost (Stream.of_channel ch) in
close_in ch;
(try run program 0 with _ -> ())
| _ -> invalid_arg "Usage: ./minim <file>"
I think it is particularly interesting to note that the parser is shorter,
faster and more extensible than the Qi implementation even though the
target grammar is an s-expr!
Pascal Costanza
> On 18 Jul, 06:41, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>> Mark Tarver <dr.mtar...@ukonline.co.uk> writes:
>>> stock Minim program that adds two numbers x and y together where x =
>>> 100000 (10^5) and y = 100000 (10^5) and give the times.
>> This is too easy to game. Think of the obvious Lisp approach of
>> translating the Minim program into an S-expression and evaluating it.
>> Now think of an evaluator that automatically invokes an optimizing
>> compiler and memoizes the resulting machine code. You see where this
>> leads.
>
> Ah, but thats a compiler Paul, not an interpreter.
...and why would that matter?!?
[The following should be quite fast - but I haven't performed any test
runs. I am interested in your results, though. It should be possible to
squeeze out more by adding declarations...]
(defvar *tag-table* '())
(defvar *var-table* '())
(defun eval-statements (statement more-statements)
(flet ((cont ()
(when more-statements
(eval-statements
(car more-statements)
(cdr more-statements)))))
(etypecase statement
(symbol (if (eq statement 'nl)
(terpri)
(setf (getf *tag-table* statement)
(cons statement more-statements)))
(cont))
(cons (case (car statement)
(if (destructuring-bind
(<if> test <then> then <else> else) statement
(declare (ignore <if>))
(assert (and (eq <then> 'then) (eq <else> 'else)))
(if (eval-test test)
(eval-statements then more-statements)
(eval-statements else more-statements))))
(goto (destructuring-bind
(<goto> tag) statement
(declare (ignore <goto>))
(let ((continuation
(or (getf *tag-table* tag)
(member tag more-statements))))
(eval-statements
(car continuation) (cdr continuation)))))
(print (destructuring-bind
(<print> value) statement
(declare (ignore <print>))
(princ (eval-value value))
(finish-output)
(cont)))
(input (destructuring-bind
(<input> var) statement
(declare (ignore <input>))
(assert (symbolp var))
(setf (getf *var-table* var) (read))
(cont)))
(++ (destructuring-bind
(<++> var) statement
(declare (ignore <++>))
(assert (symbolp var))
(incf (getf *var-table* var))
(cont)))
(-- (destructuring-bind
(<--> var) statement
(declare (ignore <-->))
(assert (symbolp var))
(decf (getf *var-table* var))
(cont)))
(otherwise (destructuring-bind
(var1 <is> var2) statement
(assert (and (symbolp var1)
(eq <is> 'is)
(symbolp var2)))
(setf (getf *var-table* var1)
(getf *var-table* var2))
(cont))))))))
(defun eval-value (value)
(typecase value
(symbol (getf *var-table* value))
(otherwise (assert (atom value)) value)))
(defun eval-test (test)
(if (eq (car test) 'not)
(destructuring-bind (<not> test) test
(declare (ignore <not>))
(not (eval-test test)))
(destructuring-bind (arg1 op arg2) test
(ecase op
(> (> (eval-value arg1) (eval-value arg2)))
(< (< (eval-value arg1) (eval-value arg2)))
(= (= (eval-value arg1) (eval-value arg2)))
(and (and (eval-test arg1) (eval-test arg2)))
(or (or (eval-test arg1) (eval-test arg2)))))))
(defun eval-minim (statements)
(eval-statements (car statements) (cdr statements)))
(define-compiler-macro eval-minim (&whole whole statements)
(unless (and (consp statements) (eq (car statements) 'quote))
(return-from eval-minim whole))
(let ((variables '()))
(labels ((translate-statement (statement)
(etypecase statement
(symbol (if (eq statement 'nl) '(terpri) statement))
(cons (case (car statement)
(if (destructuring-bind
(<if> test <then> then <else> else)
statement
(declare (ignore <if>))
(assert (and (eq <then> 'then)
(eq <else> 'else)))
`(if ,(translate-test test)
,(translate-statement then)
,(translate-statement else))))
(goto (destructuring-bind
(<goto> tag) statement
(declare (ignore <goto>))
`(go ,tag)))
(print (destructuring-bind
(<print> value) statement
(declare (ignore <print>))
`(progn
(princ ,(translate-value value))
(finish-output))))
(input (destructuring-bind
(<input> var) statement
(declare (ignore <input>))
(assert (symbolp var))
(pushnew var variables)
`(setq ,var (read))))
(++ (destructuring-bind
(<++> var) statement
(declare (ignore <++>))
(assert (symbolp var))
(pushnew var variables)
`(incf ,var)))
(-- (destructuring-bind
(<--> var) statement
(declare (ignore <-->))
(assert (symbolp var))
(pushnew var variables)
`(decf ,var)))
(otherwise (destructuring-bind
(var1 <is> var2) statement
(assert (and (symbolp var1)
(eq <is> 'is)
(symbolp var2)))
(pushnew var1 variables)
(pushnew var2 variables)
`(setq ,var1 ,var2)))))))
(translate-test (test)
(if (eq (car test) 'not)
(destructuring-bind (<not> test) test
(declare (ignore <not>))
`(not ,(translate-test test)))
(destructuring-bind (arg1 op arg2) test
(ecase op
((> < =) `(,op ,(translate-value arg1)
,(translate-value arg2)))
((and or) `(,op ,(translate-test arg1)
,(translate-test arg2)))))))
(translate-value (value)
(when (symbolp value) (pushnew value variables))
(assert (atom value)) value))
(let ((new-statements
(mapcar #'translate-statement (cadr statements))))
`(prog ,variables ,@new-statements)))))
(defun test-minim ()
(eval-minim
'((print "Add x and y")
nl
(print "Input x: ")
(input x)
nl
(print "Input y: ")
(input y)
nl
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)))
;-)
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza
> Mark Tarver wrote:
>> On 18 Jul, 06:41, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>>> Mark Tarver <dr.mtar...@ukonline.co.uk> writes:
>>>> The task is to implement an interpreter for a language Minim and run a
>>>> stock Minim program that adds two numbers x and y together where x =
>>>> 100000 (10^5) and y = 100000 (10^5) and give the times.
>>> This is too easy to game. Think of the obvious Lisp approach of
>>> translating the Minim program into an S-expression and evaluating it.
>>> Now think of an evaluator that automatically invokes an optimizing
>>> compiler and memoizes the resulting machine code. You see where this
>>> leads.
>>
>> Ah, but thats a compiler Paul, not an interpreter.
>
> ...and why would that matter?!?
>
> [The following should be quite fast - but I haven't performed any test
> runs. I am interested in your results, though. It should be possible to
> squeeze out more by adding declarations...]
...squeeze out more efficiency, I mean...
> (defvar *tag-table* '())
I just noticed that there is a bug in the handling of the *tag-table*,
but that should be easy to fix...
Jon Harrop
> ...and why would that matter?!?
Indeed.
> [The following should be quite fast - but I haven't performed any test
> runs. I am interested in your results, though. It should be possible to
> squeeze out more by adding declarations...]
By my measurements, this is 2-3x longer and twice as fast as the fastest
OCaml interpreter. By the looks of the code it is using a macro to
translate to Lisp and then compiling, in which case I am surprised the
performance is not better. I assume it is doing a very simple translation
to rather inefficient Lisp?
I'll code up an OCaml equivalent. Should be a good test of the new camlp4
although I'm not sure how to translate the gotos into OCaml...
Pascal Costanza
> Pascal Costanza wrote:
>> ...and why would that matter?!?
>
> Indeed.
>
>> [The following should be quite fast - but I haven't performed any test
>> runs. I am interested in your results, though. It should be possible to
>> squeeze out more by adding declarations...]
>
> By my measurements, this is 2-3x longer and twice as fast as the fastest
> OCaml interpreter. By the looks of the code it is using a macro to
> translate to Lisp and then compiling, in which case I am surprised the
> performance is not better. I assume it is doing a very simple translation
> to rather inefficient Lisp?
Yes. As I said, there are no type declarations in the generated code. It
should be straightforward to declare all variables as integers, but then
all incoming values from (input var) forms have to be type checked. If
you insist, I can make the necessary changes.
What is neat about this solution here is that the interpreter is still
available, so you can call eval-minim on computed values as well. The
translation to Lisp code only occurs at compile time when the compiler
macro sees a constant value for the program passed to eval-minim, so you
get the advantages of both an interpreter and a compiler. This is a
standard practice for optimizing code in Common Lisp, BTW. (To put it
differently, compiler macros allow you to define ad hoc partial
evaluations that can take advantage of domain-specific knowledge.)
It is possible to perform the translation to Lisp code on the fly, by
performing manual dynamic compilation. Then the translation could also
be done on computed values (but the runtime would be increased by the
compilation time itself, so a real gain in overall efficiency is much
harder to achieve this way). This would require a lot more code, though.
> I'll code up an OCaml equivalent. Should be a good test of the new camlp4
> although I'm not sure how to translate the gotos into OCaml...
A standard way to express gotos in functional languages is to turn each
tag into a function which ends in a call to the immediately following
tag. If your language is tail recursive, there is no real difference to
a goto in that case.
André Thieme
> I finally managed to get a version working using the new camlp4 system to
> implement an in-line extensible parser. The result is a 68-line interpreter
> that runs more quickly than all other implementations so far:
>
> faster and more extensible than the Qi implementation even though the
> target grammar is an s-expr!
The question is what you mean with "shorter".
In principle you can express a problem exactly the same in Lisp as you
could in OCaml (or Haskell).
These languages offer two interesting features: syntactic sugar for a
small set of lambdas (currying) and patter matching. Haskell also offers
lazyness which reduces the need for some macros (and can result in worse
performance).
On top of that there is not really much more that one can find in for
example OCaml. Currying and PM are also available in Lisp. In Lisp there
also is a dynamic environment and macros. These macros can also access
the Lisp environment at run time (well, any Lisp programming always
happens at runtime).
So, from that we know that in principle Lisp programs should be the same
(or shorter), complexity wise.
Counting lines makes not much sense for Lisp. Although it supports all
these programming paradigms it has a very unique style which will blow
up the LOC count in several cases. But from this it doesn't follow, that
coding takes longer.
This one liner: (defun make-accumulator (n) (lambda (i) (incf n i)))
gets usually written in three visible lines:
(defun make-accumulator (n)
(lambda (i)
(incf n i)))
OCaml has a lot of syntax which allows generally to express algorithms
with a smaller number of lines/chars (compared to Lisp).
Or see this Haskell function:
powerset = foldr (\x ys -> ys ++ (map (x:) ys)) [[]]
In Lisp we can do exactly the same one liner. Here it is (also in one
line, in some sense):
(defun powerset (set)
(reduce (lambda (x ys)
(append ys (mapcar (lambda (y)
(cons x y))
ys)))
set
:initial-value '(())
:from-end t))
Lisp does not offer a separate foldr and foldl. Reduce is doing both.
But in the case of a foldr we need to add :from-ent t
Here is the same Haskell code, indented with Lisp style:
powerset set =
foldr (\x ys ->
++ ys (map (\y
x:y)
ys))
[[]]
set
If Haskell also would use one function for foldr and foldl we also had
to add this line.
So, these two functions do exactly the same. Haskell uses more syntatic
sugar which cuts down the byte count.
When we take this in mind then the Lisp code that was presented took up
much less lines. Maybe around your OCaml solution. But it is very hard
to compare.
But it seems that your OCaml programs execute the task much faster.
Conceptually the Lisp programs don't have to be more complicated.
From that perspective I think your statement that your implementation
is shorter is not correct.
André
--
Joachim Durchholz
> Counting lines makes not much sense for Lisp. Although it supports all
> these programming paradigms it has a very unique style which will blow
> up the LOC count in several cases. But from this it doesn't follow, that
> coding takes longer.
>
> This one liner: (defun make-accumulator (n) (lambda (i) (incf n i)))
> gets usually written in three visible lines:
> (defun make-accumulator (n)
> (lambda (i)
> (incf n i)))
There are two answers to that:
1. Coding doesn't take longer, but you can't place the same amount of
code on a screenful, so debugging and maintenance will take longer.
Note that your typical generic FPL not only fits on a line, it even
takes less of a line; the syntactic Haskell equivalent of the above
example would look like this:
make-accumulator N = incf N
(No, Haskell isn't cheating, it simply doesn't have or need macros and
quoting, so it can encode the same code with far less symbols.)
Now that's 27 instead of 52 characters, which means I can put nearly
double the code on a single line without cramming it.
(I'd expect OCaml to be slightly more verbose. Jon?)
2. You can always count nodes in the AST instead of lines of code. For
the above example, you'd end up at roughly the same figures for Lisp and
your generic FPL, but as soon as you declare macros in Lisp, the FPL
needs less nodes.
(There may be other effects. Jon?)
Regards,
Jo
Tamas Papp
> (No, Haskell isn't cheating, it simply doesn't have or need macros and
> quoting, so it can encode the same code with far less symbols.)
Doesn't have? Yes. Doesn't need? People who started Liskell or
Template Haskell would probably disagree.
Tamas
Matthias Benkard
> the syntactic Haskell equivalent of the above
> example would look like this:
> make-accumulator N = incf N
Not really.
First of all, INCF is a macro. How do you curry a macro? That
doesn't make much sense to me.
Second, INCF takes a place as its first argument, not a value.
Third, INCF takes a variable number of arguments. How is the compiler
supposed to know wheter MAKE-ACCUMULATOR is of type Number a => a -> a
or of type Number a => a?
So yes, claiming that the above pieces of code are syntactically
equivalent _is_ cheating (macros are part of the syntax, after all).
You may argue about the utility of macros, but that's beside the
point, for the fact is, Common Lisp _does_ have macros (and places,
and variable number argument lists, both of which I find extremely
useful), and they're not going away anytime soon.
Haskell has its advantages over Common Lisp, of course, but it's
certainly not a "better Lisp", and its syntax is not "better S-
expressions but without macros", as macros are part of the _point_ of
S-expressions.
Do you want to be able to express common idioms more concisely, or do
you want to have the power to create your own idioms in a straight-
forward way? It's a trade-off. I have yet to see a syntax that is
both as flexible as and more concise than that of Common Lisp.
Mata ne,
Matthias
Jon Harrop
> Doesn't have? Yes. Doesn't need? People who started Liskell or
> Template Haskell would probably disagree.
Sure, but the vast majority of OCaml and Haskell coders who could use their
excellent macro systems choose not to.
I do not doubt that Lisp's macros are extremely useful for Lisp programmers
but I would contest any generalization that macros are necessary for
programming or that all languages should have macro systems, which is an
opinion often put forward on c.l.l.
Jon Harrop
> Do you want to be able to express common idioms more concisely, or do
> you want to have the power to create your own idioms in a straight-
> forward way? It's a trade-off. I have yet to see a syntax that is
> both as flexible as and more concise than that of Common Lisp.
Have a look at OCaml.
Slobodan Blazeski
This turned into a pissing contest, why doesn't this discussion going
solely on comp.lang.functional without crossposting so it will be seen
only by those people who care if language x *better* than language y
because it has a biggest , I mean smallest line count.
David Golden
> Have a look at OCaml.
Turns out that has got some seriously fugly syntax.
Jon Harrop
> There are two answers to that:
>
> 1. Coding doesn't take longer,
Even if there is four times as much code?
> but you can't place the same amount of
> code on a screenful, so debugging and maintenance will take longer.
Yes. I would expect that to result in superlinear degredation of development
speed with respect to LOC.
> Note that your typical generic FPL not only fits on a line, it even
> takes less of a line; the syntactic Haskell equivalent of the above
> example would look like this:
> make-accumulator N = incf N
A literal translation:
# (fun (+) n i -> n := !n + i);;
- : ('a -> 'b -> 'a) -> 'a ref -> 'b -> unit = <fun>
A useful translation to count the number of elements in a list:
# let length list = List.fold_left (fun n _ -> n+1) 0 list;;
val length : 'a list -> int = <fun>
To count the number of elements in any container:
# let length fold seq = fold (fun n _ -> n+1) 0 seq;;
val length : ((int -> 'a -> int) -> int -> 'b -> 'c) -> 'b -> 'c = <fun>
To sum the int elements in any container:
# let sum fold seq = fold (+) 0 seq;;
val sum : ((int -> int -> int) -> int -> 'a -> 'b) -> 'a -> 'b = <fun>
To sum elements of any type in any container:
# let sum add zero fold seq = fold add zero seq;;
val sum : 'a -> 'b -> ('a -> 'b -> 'c -> 'd) -> 'c -> 'd = <fun>
and so on. In practice, this code would never see the light of day because
real accumulators have too little in common to make such factoring useful.
For example, if you want to sum the elements of a floating point vector you
would take their magnitude into account to avoid unnecessary numerical
errors. If you want to "accumulate" strings (i.e. a StringBuilder) you
would amortize appends to reduce complexity from quadratic to linear.
> 2. You can always count nodes in the AST instead of lines of code.
Lisp's verbosity stems primarily from its use of whitespace and parentheses
as well as a lack of pattern matching. You can see this in almost any
comparable programs written in the two languages (or any languages with the
similar features, e.g. Haskell vs Scheme). Look at the intersect routines
from my ray tracer. First the Lisp:
(defun intersect (orig dir scene)
(labels ((aux (lam normal scene)
(let* ((center (sphere-center scene))
(lamt (ray-sphere orig
dir
center
(sphere-radius scene))))
(if (>= lamt lam)
(values lam normal)
(etypecase scene
(group
(dolist (kid (group-children scene))
(setf (values lam normal)
(aux lam normal kid)))
(values lam normal))
(sphere
(values lamt (unitise
(-v (+v orig (*v lamt dir)) center)))))))))
(aux infinity zero scene)))
Then the OCaml:
let rec intersect o d (l, _ as hit) (c, r, s) =
let l' = ray_sphere o d c s in
if l' >= l then hit else match s with
[] -> l', unitise (o +| l' *| d -| c)
| ss -> List.fold_left (intersect o d) hit ss
Look at the core interpreters in this Minim shootout. First the OCaml:
let rec test = function
| `Comp(c, x, y) -> c !x !y
| `And(f, g) -> test f && test g
| `Or(f, g) -> test f || test g
| `Not f -> not(test f)
let rec statement pc = function
| `Assign(x, y) -> x := !y; pc + 1
| `Incr x -> incr x; pc + 1
| `Decr x -> decr x; pc + 1
| `If(p, t, f) -> statement pc (if test p then t else f)
| `Goto tag -> !tag
| `PrintString s -> print_string s; pc + 1
| `Print x -> print_int(!x); pc + 1
| `Input x -> x := int_of_string(input_line stdin); pc + 1
let rec run program pc = run program (statement pc program.(pc))
Then the Qi:
(define run
{program --> env}
Program -> (run-loop Program Program []))
(define run-loop
{program --> program --> env --> env}
[] _ Env -> Env
[nl | Ss] Program Env -> (do (output "~%") (run-loop Ss Program
Env))
[Tag | Ss] Program Env -> (run-loop Ss Program Env) where (symbol?
Tag)
[[goto Tag] | _] Program Env -> (run-loop (go Tag Program) Program
Env)
[[Var is Val] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (compute-val Val Env)
Env))
[[++ Var] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (+ 1 (look-up Var Env))
Env))
[[-- Var] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (- (look-up Var Env) 1)
Env))
[[if Test then DoThis else DoThat] | Ss] Program Env
-> (if (perform-test? Test Env)
(run-loop [DoThis | Ss] Program Env)
(run-loop [DoThat | Ss] Program Env))
[[print M] | Ss] Program Env -> (do (output "~A" (look-up M Env))
(run-loop Ss Program Env))
where (symbol? M)
[[print M] | Ss] Program Env -> (do (output "~A" M)
(run-loop Ss Program Env))
[[input Var] | Ss] Program Env
-> (run-loop Ss Program (change-env Var (input+ : number)
Env)))
(define compute-val
{val --> env --> number}
N _ -> N where (number? N)
Var Env -> (look-up Var Env) where (symbol? Var))
(define go
{symbol --> program --> program}
Tag [Tag | Program] -> Program
Tag [_ | Program] -> (go Tag Program)
Tag _ -> (error "cannot go to tag ~A~%" Tag))
(define perform-test?
{test --> env --> boolean}
[Test1 and Test2] Env -> (and (perform-test? Test1 Env)
(perform-test? Test2 Env))
[Test1 or Test2] Env -> (or (perform-test? Test1 Env)
(perform-test? Test2 Env))
[not Test] Env -> (not (perform-test? Test Env))
[V1 = V2] Env -> (= (compute-val V1 Env) (compute-val V2 Env))
[V1 > V2] Env -> (> (compute-val V1 Env) (compute-val V2 Env))
[V1 < V2] Env -> (< (compute-val V1 Env) (compute-val V2 Env)))
(define change-env
{symbol --> number --> env --> env}
Var Val [] -> [(@p Var Val)]
Var Val [(@p Var _) | Env] -> [(@p Var Val) | Env]
Var Val [Binding | Env] -> [Binding | (change-env Var Val Env)])
(define look-up
{symbol --> env --> number}
Var [] -> (error "~A is unbound.~%" Var)
Var [(@p Var Val) | _] -> Val
Var [_ | Env] -> (look-up Var Env))
> For
> the above example, you'd end up at roughly the same figures for Lisp and
> your generic FPL, but as soon as you declare macros in Lisp, the FPL
> needs less nodes.
Are you saying that macros reduce code size?
> (There may be other effects. Jon?)
Pattern matching is the single biggest advantage and is the main reason why
OCaml, SML, Haskell and F# are all much more concise than Common Lisp. Look
at the amount of code doing destructing in the above examples.
Pascal Costanza
> Jon Harrop wrote:
>> Pascal Costanza wrote:
>>> ...and why would that matter?!?
>>
>> Indeed.
>>
>>> [The following should be quite fast - but I haven't performed any test
>>> runs. I am interested in your results, though. It should be possible to
>>> squeeze out more by adding declarations...]
>>
>> By my measurements, this is 2-3x longer and twice as fast as the fastest
>> OCaml interpreter. By the looks of the code it is using a macro to
>> translate to Lisp and then compiling, in which case I am surprised the
>> performance is not better. I assume it is doing a very simple translation
>> to rather inefficient Lisp?
>
> Yes. As I said, there are no type declarations in the generated code. It
> should be straightforward to declare all variables as integers, but then
> all incoming values from (input var) forms have to be type checked.
Here is a new version to try out. Note that I declared the variables as
fixnum, which means that they wrap around beyond a certain threshold.
That number is implementation-dependent and is stored in the constant
MOST-POSITIVE-FIXNUM. For example, in SBCL it's 536870911. If that's too
small for your tests, change the *variable-type* parameter to 'integer
and recompile. (In Common Lisp, integer is unlimited for correctness.)
It's also fun to call (disassemble 'test-minim) after compilation (with
any type).
I have also fixed the bug in the interpreter which I reported on before.
As an additional note: The code is roughly 2x longer than necessary
because of the optimization added via the compiler macro. In a more
realistic scenario, you would use the interpreter only, and only
optimize the code as soon as you notice that there is a performance
bottleneck here. In an even more realistic scenario, you would probably
use a pure macro version from the start, but Mark wanted an interpreter,
so there you go.
Cheers,
Pascal
(defvar *tag-table* '())
(defvar *var-table* '())
(defvar *program*)
;;
;; change this parameter for different variable types
;;
(eval-when (:compile-toplevel :load-toplevel :execute)
(defparameter *variable-type* 'fixnum))
(defun eval-statements (statement more-statements)
(flet ((cont () (when more-statements
(eval-statements
(car more-statements)
(cdr more-statements)))))
(etypecase statement
(symbol (if (eq statement 'nl)
(terpri)
(setf (getf *tag-table* statement)
(cons statement more-statements)))
(cont))
(cons (case (car statement)
(if (destructuring-bind
(<if> test <then> then <else> else) statement
(declare (ignore <if>))
(assert (and (eq <then> 'then) (eq <else> 'else)))
(if (eval-test test)
(eval-statements then more-statements)
(eval-statements else more-statements))))
(goto (destructuring-bind
(<goto> tag) statement
(declare (ignore <goto>))
(let ((continuation (or (getf *tag-table* tag)
(member tag *program*))))
(defun eval-minim (statements)
(let ((*program* statements))
(eval-statements (car statements) (cdr statements))))
(let ((input (gensym)))
`(let ((,input (read)))
(check-type
,input ,*variable-type*)
(setq ,var ,input)))))
`(prog ,(loop for var in variables collect `(,var 0))
(declare (optimize (speed 3) (safety 0) (debug 0)
(compilation-speed 0))
(,*variable-type* ,@variables))
,@new-statements)))))
(defun test-minim ()
(eval-minim
'((print "Add x and y")
nl
(print "Input x: ")
(input x)
nl
(print "Input y: ")
(input y)
nl
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)))
--
Jon Harrop
> Jon Harrop wrote:
>> Lisp's verbosity stems primarily from its use of whitespace and
>> parentheses as well as a lack of pattern matching.
>
> load a pattern matcher / unifier.
Greenspun. If you put a couple of years into it you'll be where Mark is now
with Qi. If you work really hard for another 30 years you might get to
where OCaml, Haskell or F# are now.
> Actually, much of the shortening is coming from simply using
> shorter or single-character identifiers in your ML code where Lisp (or
> apparently Qi) authors would use more meaningful ones - hardly a
> sensible comparison.
On the contrary, when trying to compare brevity I see no merit in ignoring
verbosity.
> One can write Qi or Lisp with single-character
> identifiers. It's just not considered particularly good style.
It also makes little difference (see below).
> I can rewrite a pattern match from Mark's Qi into something a little
> more like your ML in style:
>
> [[if Test then DoThis else DoThat] | Ss] Program Env
> -> (if (perform-test? Test Env)
> (run-loop [DoThis | Ss] Program Env)
> (run-loop [DoThat | Ss] Program Env))
>
> ===>
>
> [[if X then A else B] | Ss] P E ->
> (if (pt X E) (rl [A | Ss] P E) (rl [B | Ss] P E))
>
> Oh look, I've "halved" the length (if you're measuring LOC, which is a
> ridiculous measure anyway for most languages, not just lisp or ML). Of
> course it's also got less readable, like your (but not all) ML.
To be fair, I am sure you will want to take the OCaml:
`If(p, t, f) -> statement pc (if test p then t else f)
and perform equivalent compression:
`If(p, f, g) -> s n (if t p then f else g)
As you can see, the compressed OCaml is significantly shorter than the
compressed Qi. The only useful conclusion we can draw from this is that the
length of identifiers was not, in fact, relevant.
Tony Finch
>
>Lisp's verbosity stems primarily from its use of whitespace and parentheses
>as well as a lack of pattern matching. You can see this in almost any
>comparable programs written in the two languages (or any languages with the
>similar features, e.g. Haskell vs Scheme). Look at the intersect routines
>from my ray tracer.
I think the comparison would be fairer if you used the same variable names
in each language. You've used words in the Lisp and single letters in the
O'Caml, which undermines your argument. You have also wasted vertical
space in the Lisp, and maximized vertical compression in the O'Caml,
in both cases more than I would say is normal.
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
PORTLAND PLYMOUTH: NORTHWESTERLY BACKING SOUTHWESTERLY 4 OR 5, INCREASING 6 OR
7 FOR A TIME. SLIGHT OR MODERATE, OCCASIONALLY ROUGH. RAIN OR THUNDERY
SHOWERS. MODERATE OR GOOD.
Markus E Leypold
> I do not doubt that Lisp's macros are extremely useful for Lisp programmers
> but I would contest any generalization that macros are necessary for
> programming or that all languages should have macro systems, which is an
> opinion often put forward on c.l.l.
ACK.
Regards -- Markus
Pascal Costanza
> Tamas Papp wrote:
>> Doesn't have? Yes. Doesn't need? People who started Liskell or
>> Template Haskell would probably disagree.
>
> Sure, but the vast majority of OCaml and Haskell coders who could use their
> excellent macro systems choose not to.
>
> I do not doubt that Lisp's macros are extremely useful for Lisp programmers
> but I would contest any generalization that macros are necessary for
> programming or that all languages should have macro systems, which is an
> opinion often put forward on c.l.l.
...or you just misunderstand them.
Pascal
Ulf Wiger
Jon> Joachim Durchholz wrote:
>> There are two answers to that:
>>
>> 1. Coding doesn't take longer,
Jon> Even if there is four times as much code?
>> but you can't place the same amount of code on a screenful, so
>> debugging and maintenance will take longer.
Jon> Yes. I would expect that to result in superlinear degredation
Jon> of development speed with respect to LOC.
I've been quoted as stating that development speed in terms
of lines of code per man-hour* seems to be the same regardless
of language, and that LOC reduction should result in roughly
linear improvement in development speed. We've noted that the
same seems to be true for fault density**, with corresponding
effects on product quality. This would seem to support your
assumption about a superlinear difference overall
* Development + testing up until product release
** Faults found in the field, measured in faults/KLOC
I think a long-term effect of relieving the programmer
of concern for low-level memory management, locking,
etc. will eventually allow programmers to adjust their
frame of mind and ways of working (e.g. smaller projects,
less bureaucracy, perhaps fewer and better programmers***),
will give additional factors of productivity improvement,
but this is mainly speculation, which BTW would seem to
invalidate my initial assumption, but support yours. ;-)
*** While one should really have top-notch programmers to
get away with C++ programming in the large, the need
for large projects tends to drive away the best
programmers.
BR,
Ulf W
--
Ulf Wiger, Senior Specialist,
/ / / Architecture & Design of Carrier-Class Software
/ / / Team Leader, Software Characteristics
/ / / Ericsson AB, IMS Gateways
Jon Harrop
> You conflate another issue: your ML "if" match line is not doing the
> same thing as Mark's Qi "if" match line (hint: when/if you work out why
> it's not, you'll also work out why it's both unsurprising and
> uninteresting your ML was faster than Mark's Qi interpreter).
Sounds like another triumph of hope over reality.
Dan Bensen
> Jon Harrop escreveu:
>> Pattern matching is the single biggest advantage and is the main
>> reason why OCaml, SML, Haskell and F# are all much more concise
>> than Common Lisp.
> libraries for pattern matching in Lisp. Why?
Because it sells books.
--
Dan
www.prairienet.org/~dsb/
André Thieme
> André Thieme schrieb:
>> Counting lines makes not much sense for Lisp. Although it supports all
>> these programming paradigms it has a very unique style which will blow
>> up the LOC count in several cases. But from this it doesn't follow, that
>> coding takes longer.
>>
>> This one liner: (defun make-accumulator (n) (lambda (i) (incf n i)))
>> gets usually written in three visible lines:
>> (defun make-accumulator (n)
>> (lambda (i)
>> (incf n i)))
>
> There are two answers to that:
>
> 1. Coding doesn't take longer, but you can't place the same amount of
> code on a screenful, so debugging and maintenance will take longer.
This might be true for several cases.
I also see the scenario in mind where longer names for variables or
functions bring in advantages for readability.
However, if you wanted then you could compress code in Lisp as well.
For example with my DEF:
(def make-accumulator (n) [incf n])
> Note that your typical generic FPL not only fits on a line, it even
> takes less of a line; the syntactic Haskell equivalent of the above
> example would look like this:
Well, for some situations you are right, for others you are not.
It depends on what you want to do.
I gave the example about calculating the powerset.
One other Haskell solution is for example this one:
powerset = filterM (const [True, False])
To do the same in Lisp you first need to write like 40 LOC preparation
code.
In other situations Lisp can be the better option.
Joel Raymond wrote about Erlangs advantages over Haskell:
http://wagerlabs.com/2006/1/1/haskell-vs-erlang-reloaded/
For example point 3.2 was talking about static typing and the extra
code it needed.
> make-accumulator N = incf N
Hmm, does Haskell have infc?
Is that some monad that can do the destructive manipulation on N?
What is the minus (between "make" and "accumulator") doing when it is
placed on the right side of a "="?
> (No, Haskell isn't cheating, it simply doesn't have or need macros and
> quoting, so it can encode the same code with far less symbols.)
It is true that the need for Macros in Haskell is reduced. This comes
from implicit currying but mainly from lazyness.
In Lisp you could do the same. You could teach Lisp implicit currying
and also implicit lazyness (altough I think that it would feel really
bad).
So yes, several things that are expressed in Lisp with Macros would be
expressed without them in Haskell. However, I am not sure if that comes
without performance hits.
> Now that's 27 instead of 52 characters, which means I can put nearly
> double the code on a single line without cramming it.
With short code examples it will probably often happen.
> 2. You can always count nodes in the AST instead of lines of code. For
> the above example, you'd end up at roughly the same figures for Lisp and
> your generic FPL, but as soon as you declare macros in Lisp, the FPL
> needs less nodes.
This might be a little misunderstanding.
Usually after introducing macros the count of nodes is reduced.
André
--
Cesar Rabak
Paul Rubin
> First of all, INCF is a macro. How do you curry a macro? That
> doesn't make much sense to me.
incf is a macro because macros are the only way to make Lisp forms
that don't evaluate their args. Haskell uses lazy evaluation and
therefore all kinds of things that Lisp uses macros for, are done in
Haskell as ordinary functions. Of course incf mutates its argument,
which normally isn't done in Haskell. So you'd only code something
like incf as a monad action.
>
> Third, INCF takes a variable number of arguments. How is the compiler
> supposed to know wheter MAKE-ACCUMULATOR is of type Number a => a -> a
> or of type Number a => a?
Type inference.
Paul Rubin
> I've been quoted as stating that development speed in terms
> of lines of code per man-hour* seems to be the same regardless
> of language, and that LOC reduction should result in roughly
> linear improvement in development speed.
I wonder about this. My hat off to anyone who can code in Haskell as
fast in LOC/hour as they can code in Java. Of course the Java LOC
only do 1/10th as much, so coding 2x slower still leaves one ahead by
a factor of 5.
Ulf Wiger
Paul> Ulf Wiger <etx...@cbe.ericsson.se> writes:
>> I've been quoted as stating that development speed in terms of
>> lines of code per man-hour* seems to be the same regardless of
>> language, and that LOC reduction should result in roughly linear
>> improvement in development speed.
Paul> I wonder about this. My hat off to anyone who can code in
Paul> Haskell as fast in LOC/hour as they can code in Java. Of
Paul> course the Java LOC only do 1/10th as much, so coding 2x
Paul> slower still leaves one ahead by a factor of 5.
I believe this is basically the point. For a sufficiently
difficult problem, understanding how to build the program
takes much longer than writing it down. The speed of actually
writing the code will depend on the ratio of trivial vs tricky
code. When trying to understand what you wrote, the code that is
secondary to solving the actual problem will get in your way and
slow you down.
Our frame of reference was very large projects, where the actual
writing of code is a fairly small part of the overall project
time. And it's just a superficial observation, from comparing
actual metrics from several projects using different technologies.
It's only a little bit more solid than "a watched pot never boils."
The observation itself is not particularly novel. Brooks reported
someone as drawing the same conclusion in The Mythical Man-Month
(I don't have a copy of the book, so I can't check the reference).
We checked the numbers for a few of our projects and observed that
they seemed to corroborate Brooks' old rule of thumb, QED. (:
Ulf Wiger
Andre> In other situations Lisp can be the better option. Joel
Andre> Raymond wrote about Erlangs advantages over Haskell:
Andre> http://wagerlabs.com/2006/1/1/haskell-vs-erlang-reloaded/ For
Andre> example point 3.2 was talking about static typing and the
Andre> extra code it needed.
A paper at the upcoming ICFP conference will present a more
systematic comparison between C++, Erlang and Haskell.
It shows some interesting stuff, but also warns against too
far-reaching conclusions.
Evaluating High-Level Distributed Language Constructs
by Jan Nystrom, Phil Trinder, David King
Jon Harrop
> In other situations Lisp can be the better option.
> Joel Raymond wrote about Erlangs advantages over Haskell:
> http://wagerlabs.com/2006/1/1/haskell-vs-erlang-reloaded/
> For example point 3.2 was talking about static typing and the extra
> code it needed.
Look at the vector record and zero vector definition from my ray tracer. In
Lisp:
(defstruct (vec (:conc-name nil)
(:constructor vec (x y z))
(:type (vector double-float)))
x y z)
(defvar zero (vec 0d0 0d0 0d0))
In OCaml:
type vec = {x:float; y:float; z:float}
let zero = {x=0.; y=0.; z=0.}
>> (No, Haskell isn't cheating, it simply doesn't have or need macros and
>> quoting, so it can encode the same code with far less symbols.)
>
> It is true that the need for Macros in Haskell is reduced. This comes
> from implicit currying but mainly from lazyness.
> In Lisp you could do the same. You could teach Lisp implicit currying
> and also implicit lazyness (altough I think that it would feel really
> bad).
Greenspun.
Jon Harrop
> Jonnie wrote:
>> Sounds like another triumph of hope over reality
>
> The Qi and ML programs as a whole may have similar
> effects, but hey, I could drive or skate to
> the shops too.
So you're saying that the comparison is grossly unfair in some unspecified
way. I don't suppose you could be more specific?
Paul Rubin
> In Lisp you could do the same. You could teach Lisp implicit currying
> and also implicit lazyness (altough I think that it would feel really bad).
You can't do anything of the sort. Consider that Haskell has no
language support for exceptions or continuations, because they're
implemented straightforwardly as library modules, using a combination
of lazy evaluation and currying. They can't be implemented that way
in Lisp, so exceptions are built into the language and continuations
(in CL) can't be done at all without nonstandard extensions.
Jon Harrop
> So, this is supposed to be a benchmark for the execution time?
Yes. I get a lot of errors when I try to compile it:
$ javac stefanram.java
stefanram.java:10: unclosed character literal
{ final java.lang.Object 'source entry' = state.'current entry'();
^
stefanram.java:10: unclosed character literal
{ final java.lang.Object 'source entry' = state.'current entry'();
Any ideas what these mean?
> I believe that I now could write a faster interpreter by
> first translating the S-expression to an object model.
Java has lex and yacc tools (JavaCC combines these, IIRC) so you could use
them for parsing.
Define an abstract syntax tree (AST) as a class hierarchy with an abstract
base class representing the AST type. This will be more verbose than the
Lisp or OCaml because you have to write the classes down by hand in Java.
Get the parser to generate an AST.
When it comes to evaluation, you can use the built-in virtual function
dispatch (e.g. a "run" member function) to avoid the nested ifs and string
compares that you're currently doing.
Finally, you can avoid name lookups on variables and tags in gotos by
replacing these with ints.
I might have a go at doing this in Java...
Jon Harrop
> Jon Harrop escreveu:
>> why OCaml, SML, Haskell and F# are all much more concise than Common
>> Lisp. Look at the amount of code doing destructing in the above examples.
>
> libraries for pattern matching in Lisp. Why?
Pattern matching in Lisp was in no way prohibited or even discouraged in any
of these examples. The vast majority of Lisp programmers never reach for
more sophisticated functionality, opting instead to hand code everything in
a hopelessly unmaintainable way. See Andre Thieme or Nathan Froyd's
implementations:
http://www.lambdassociates.org/studies/study10.htm
Some people did try to use pattern matching from Lisp but it remained
uncompetitive:
Dan Bensen Greenspunned by lashing up an ad-hoc bug-ridden
informally-specified implementation of half of an ML pattern matcher for
his symbolic simplifier. His implementation remains longer and slower than
the OCaml.
Mark Tarver went the extra mile and put years of effort into making the most
sophisticated replica of modern functional programming languages for Lisp.
As you can see from these results, the Qi implementations remains slower
and longer than the OCaml.
Joachim Durchholz
>> the syntactic Haskell equivalent of the above
>> example would look like this:
>
>
> First of all, INCF is a macro.
That's why I wrote "syntactic equivalent".
I was all talking about the overhead of having parentheses.
> How do you curry a macro? That doesn't make much sense to me.
I don't see any problems applying currying to macros that wouldn't apply
to functions, or vice versa.
You can explain currying as a purely syntactic device. You can "explain
it away" for functions by resorting to HOFs (and that's a useful
perspective for some questions around currying), but you don't have to.
> Second, INCF takes a place as its first argument, not a value.
Seems like a macro thing to me.
> Third, INCF takes a variable number of arguments. How is the compiler
> supposed to know wheter MAKE-ACCUMULATOR is of type Number a => a -> a
> or of type Number a => a?
There's no difference. In Haskell, make-accumulator would be exactly
equivalent to incf.
> So yes, claiming that the above pieces of code are syntactically
> equivalent _is_ cheating (macros are part of the syntax, after all).
> You may argue about the utility of macros, but that's beside the
> point, for the fact is, Common Lisp _does_ have macros (and places,
> and variable number argument lists, both of which I find extremely
> useful), and they're not going away anytime soon.
There is no difference between a macro and a function in Haskell.
In Haskell, there is no semantic difference between compile-time and
run-time evaluation, so any macro would be a function and vice versa.
(That's a general property of pure languages, and not due to Haskell's
nonstrict evaluation strategy.)
You *can* have macros in Haskell (just plop in a preprocessor), but they
aren't nearly as pressingly needed as in an impure language. (That may
be the reason why preprocessors are more en vogue for OCaml than for
Haskell.)
> I have yet to see a syntax that is
> both as flexible as and more concise than that of Common Lisp.
Drop the superfluous parentheses, for example. A minimum amount of
operator precedence and layout rules eliminates 99% of them.
That's "just lexical conciseness", you'll say, and you'd be correct.
However, when I look at the sheer percentage of screen estate these
parentheses are taking up, it's getting too much.
Regards,
Jo
Cesar Rabak
> André Thieme wrote:
>> In other situations Lisp can be the better option.
>> Joel Raymond wrote about Erlangs advantages over Haskell:
>> http://wagerlabs.com/2006/1/1/haskell-vs-erlang-reloaded/
>> For example point 3.2 was talking about static typing and the extra
>> code it needed.
>
> Look at the vector record and zero vector definition from my ray tracer. In
> Lisp:
>
> (defstruct (vec (:conc-name nil)
> (:constructor vec (x y z))
> (:type (vector double-float)))
> x y z)
>
> (defvar zero (vec 0d0 0d0 0d0))
>
> In OCaml:
>
> type vec = {x:float; y:float; z:float}
> let zero = {x=0.; y=0.; z=0.}
>
2 logical lines.
Joachim Durchholz
> Joachim Durchholz wrote:
>> There are two answers to that:
>>
>> 1. Coding doesn't take longer,
>
> Even if there is four times as much code?
Not enough of a difference to get above the noise level.
I spend 90% of my programming time designing things. (The other 90% are
debugging and maintenance, of course *g*)
I also happen to be a rather adept blind typist, so I wouldn't even
*think* about the parentheses.
>> 2. You can always count nodes in the AST instead of lines of code.
>
> Lisp's verbosity stems primarily from its use of whitespace and parentheses
> as well as a lack of pattern matching.
Ah, right, lack of pattern matching tends to bloat any code.
I didn't notice this since the example code given didn't have any case
distinctions.
I'm still surprised it isn't already in widespread use in any new
language. I've been seriously missing that in any language that I've
been using since I got to know the concept (and even before).
I think the Lisp would look better if it weren'd indented so much.
It might even get slightly shorter because some stuff could be written
inline.
(I can't say whether the above Lisp could be written more concisely though.)
>> For
>> the above example, you'd end up at roughly the same figures for Lisp and
>> your generic FPL, but as soon as you declare macros in Lisp, the FPL
>> needs less nodes.
>
> Are you saying that macros reduce code size?
First, I'm (wrongly) assuming that Lisp's relative verboseness comes
from parentheses (and additional whitespace needed because those
parentheses force you into more line wraps).
Seconds, I'm saying that needing macros means that you often writen the
same semantics twice, once as a function and once (for those cases where
it's a useful optimization) as a macro.
So a language that works well without macros is shorter.
(I assume that macros are more a library thing, not something that gets
written routinely or redundantly, so I don't think the effect is large.)
So, no, I'm saying that needing macros tends to increase code size,
though I can't say it would be much and suspect it isn't much indeed.
Regards,
Jo
Joachim Durchholz
> I think the comparison would be fairer if you used the same variable names
> in each language. You've used words in the Lisp and single letters in the
> O'Caml, which undermines your argument.
Only partly.
In shorter code, fully descriptive names aren't as relevant since you
have fewer lines to check for cross-referencing code.
I see these name terseness elsewhere in functional code, including code
from people who are generally considered as "writing good style". (Take
a look at the Haskell Prelude, for example.)
Regards,
Jo
Joachim Durchholz
> Humm... I still find your comparison loaded: you rule out the use of
> libraries for pattern matching in Lisp. Why?
My answer would be:
Using a pattern matching library adds yet another dependency to your
code. Unless you know that the library is well-maintained, you don't
want this kind of dependency.
In other words, I suspect it would find lots of use it if became part of
the CLOS standard.
Regards,
Jo
David Golden
> Drop the superfluous parentheses, for example. A minimum amount of
> operator precedence and layout rules eliminates 99% of them.
And makes the code massively more annoying to read. In fact,
the baroque syntax is the main reason I dislike Haskell (Liskell borders
on interesting though, there might be a reasonable language buried
underneath the syntax afflicting Haskell). I find Lisp, Forth and APL
pleasant to read largely due to their simple syntax without complicated
precedence. You may be different, but not everyone's preferences are
the same.
Pascal Bourguignon
>> I have yet to see a syntax that is
>> both as flexible as and more concise than that of Common Lisp.
>
> Drop the superfluous parentheses, for example. A minimum amount of
> operator precedence and layout rules eliminates 99% of them.
Oops! Now you'll have to teach this minimum amount of operator
precedence and layout rules to the billions of macros out there.
And each macro will become much bigger and more complex...
--
__Pascal Bourguignon__ http://www.informatimago.com/
Wanna go outside.
Oh, no! Help! I got outside!
Let me back inside!
Don Dwoske
> A paper at the upcoming ICFP conference will present a more
> systematic comparison between C++, Erlang and Haskell.
> It shows some interesting stuff, but also warns against too
> far-reaching conclusions.
>
> Evaluating High-Level Distributed Language Constructs
> by Jan Nystrom, Phil Trinder, David King
Brief discussion and a link to that paper can be found here:
http://lambda-the-ultimate.org/node/2287
Just the paper:
http://www.macs.hw.ac.uk/~trinder/papers/ICFP2007.pdf
Neelakantan Krishnaswami
Paul Rubin <> wrote:
>
> You can't do anything of the sort. Consider that Haskell has no
> language support for exceptions or continuations, because they're
> implemented straightforwardly as library modules, using a
> combination of lazy evaluation and currying. They can't be
> implemented that way in Lisp, so exceptions are built into the
> language and continuations (in CL) can't be done at all without
> nonstandard extensions.
Continuations can definitely be implemented in Lisp to the same extent
that they are in Haskell. What Haskell's continuation module provides
is a nice, strongly-typed interface to code in continuation passing
style. It does *not* let you capture arbitrary continuations, the way
you can in Scheme.
Being able to conveniently program in CPS is a good thing, IMO, but a)
I certainly wouldn't call it full support for continuations, and b)
you can program in CPS in any Lisp with tail call optimization.
--
Neel R. Krishnaswami
ne...@cs.cmu.edu
Alexander Schmolck
>> (defstruct (vec (:conc-name nil)
>> (:constructor vec (x y z))
>> (:type (vector double-float)))
>> x y z)
>>
>> (defvar zero (vec 0d0 0d0 0d0))
>>
>> In OCaml:
>>
>> type vec = {x:float; y:float; z:float}
>> let zero = {x=0.; y=0.; z=0.}
>>
> For a LOC counting perpective, both snippets above have the same count: 2
> logical lines.
You should write a paper introducing this brilliant new code metric of
"logical lines" (my I suggest "PROGN the ultimate 1-liner" for a title?).
'as
Jon Harrop
> Jon Harrop wrote:
>> So you're saying that the comparison is grossly unfair in some
>> unspecified way.
>
> trying to change the subject - you (invalidly) tried to compare
> the length of your if match line and mark's, when it is clear
> that they are not doing the same thing.
What exactly do you believe they are doing differently?