Functional - shootout: implementing an interpreter for a simple procedural language Minim

Author

shootout: implementing an interpreter for a simple procedural language Minim

Mark Tarver

2007-07-17, 10:04 pm

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

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

2007-07-18, 4:13 am

Mark Tarver <dr.mtarver@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.

Jon Harrop

2007-07-18, 4:13 am

Mark Tarver wrote:
> 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

. :-)

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Jon Harrop

2007-07-18, 4:13 am

Paul Rubin wrote:
> 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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Paul Rubin

2007-07-18, 4:13 am

Jon Harrop <jon@ffconsultancy.com> writes:
>
> 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.

Jon Harrop

2007-07-18, 4:13 am

Paul Rubin wrote:
> 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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Paul Rubin

2007-07-18, 4:13 am

Jon Harrop <jon@ffconsultancy.com> writes:
> 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

2007-07-18, 4:13 am

Jon Harrop wrote:
> ...

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>"

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Jon Harrop

2007-07-18, 4:13 am

Paul Rubin wrote:
> Jon Harrop <jon@ffconsultancy.com> writes:
>
> 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.

Fine by me but the overhead of full-blown compilation will be significant.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Paul Rubin

2007-07-18, 4:13 am

Jon Harrop <jon@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,
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/lightni...g.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

2007-07-18, 4:13 am

Paul Rubin wrote:
> Jon Harrop <jon@ffconsultancy.com> writes:
>
> 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/lightni...g.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?

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Andras Simon

2007-07-18, 8:05 am

Jon Harrop <jon@ffconsultancy.com> writes:

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

2007-07-18, 7:11 pm

Jon Harrop <jon@ffconsultancy.com> writes:
> Doesn't support amd64, which rules it out for me.

I thought that was added recently.

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

2007-07-18, 7:11 pm

!!
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()
}

Mark Tarver

2007-07-19, 8:06 am

On 18 Jul, 06:41, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> Mark Tarver <dr.mtar...@ukonline.co.uk> writes:
>
> 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.

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

2007-07-19, 8:06 am

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.

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

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Mark Tarver

2007-07-19, 7:08 pm

OK; I'm reading this group on one news reader which works but does not
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

over my data structures - e.g. trying to find the value of a
constant.

Mark

Mark Tarver

2007-07-19, 7:08 pm

QUOTE
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

2007-07-19, 7:08 pm

Mark Tarver wrote:
> 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. :-)

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Raffael Cavallaro

2007-07-19, 7:08 pm

On 2007-07-19 10:22:46 -0400, Mark Tarver <dr.mtarver@ukonline.co.uk> said:

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

Ole Nielsby

2007-07-19, 7:08 pm

Jon Harrop <jon@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.

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

2007-07-19, 7:08 pm

Ole Nielsby wrote:
> Jon Harrop <jon@ffconsultancy.com> wrote:
>
> 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.

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

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Mark Tarver

2007-07-19, 7:08 pm

> 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?

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

Jon Harrop

2007-07-20, 4:17 am

Mark Tarver wrote:
> 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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Mark Tarver

2007-07-20, 4:17 am

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

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

2007-07-20, 4:17 am

Mark Tarver wrote:
> 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.)?

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

MetaProgrammer

2007-07-20, 8:05 am

On Jul 18, 1:24 am, Mark Tarver <dr.mtar...@ukonline.co.uk> wrote:
> \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

2007-07-20, 7:10 pm

P.S.: in order to build standalone Minim executables,
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.

Mark Tarver

2007-07-20, 7:10 pm

On 19 Jul, 20:47, Joachim Durchholz <j...@durchholz.org> wrote:
> Mark Tarver schrieb:
>
>
> 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

\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

2007-07-21, 4:15 am

Mark Tarver wrote:
>
> 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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Jon Harrop

2007-07-21, 8:05 am

Mark Tarver wrote:
> 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...

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Mark Tarver

2007-07-21, 8:05 am

> you're talking about - what? Lisp being useful as a target language?
>
> (Maybe I misunderstood your original statement.)

Exactly - that is what I as talking about.

Mark

Jon Harrop

2007-07-22, 8:05 am

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!

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Jon Harrop

2007-07-22, 7:09 pm

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?

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

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Tamas Papp

2007-07-23, 4:11 am

Joachim Durchholz <jo@durchholz.org> writes:

> (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

2007-07-23, 8:04 am

Hi,

> 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

2007-07-23, 8:04 am

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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Jon Harrop

2007-07-23, 8:04 am

Matthias Benkard wrote:
> 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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

David Golden

2007-07-23, 8:04 am

Jon Harrop wrote:

> Have a look at OCaml.

Turns out that has got some seriously fugly syntax.

Jon Harrop

2007-07-23, 8:04 am

Joachim Durchholz wrote:
> 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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

David Golden

2007-07-23, 7:07 pm

Jon Harrop wrote:

> Lisp's verbosity stems primarily from its use of whitespace and
> parentheses as well as a lack of pattern matching.

Of course, if a lisp coder really wants pattern matching, they just
load a pattern matcher / unifier.

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. One can write Qi or Lisp with single-character
identifiers. It's just not considered particularly good style.

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.

Jon Harrop

2007-07-23, 7:07 pm

David Golden wrote:
> Jon Harrop wrote:
>
> Of course, if a lisp coder really wants pattern matching, they just
> 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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Phil Armstrong

2007-07-23, 7:07 pm

David Golden <david.golden@oceanfree.net> wrote:
> 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.

It's been pointed out before I'm sure, but perhaps a better way to
compare syntactic program complexity is to measure the number of lexer
tokens. (Assuming the lexer spits out a single token for things like
identifiers of course).

There is of course no obviously correct way to do this in any case.

Phil

--
http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt

David Golden

2007-07-23, 7:07 pm

Jon Harrop wrote:

>
> Greenspun.

Yeah, just like it's greenspunning yacc how you used the parser module
for ocaml. Very, very lame, Jonnie boy.

> As you can see, the compressed OCaml is significantly shorter than the
> compressed Qi.

That rather missed the point of the example (which was stylistic
contrast, illustrating that indeed, using short identifiers makes code
look shorter).

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

Tony Finch

2007-07-23, 7:07 pm

Jon Harrop <jon@ffconsultancy.com> wrote:
>
>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 <dot@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.

Jon Harrop

2007-07-23, 7:07 pm

Phil Armstrong wrote:
> David Golden <david.golden@oceanfree.net> wrote:
>
> It's been pointed out before I'm sure, but perhaps a better way to
> compare syntactic program complexity is to measure the number of lexer
> tokens. (Assuming the lexer spits out a single token for things like
> identifiers of course).
>
> There is of course no obviously correct way to do this in any case.

Although that works well for Lisp or Scheme, lexical tokens have no
correspondence to perceived verbosity when the grammar is complicated
though. For example, I couldn't tell you what the tokens are here:

# let foo ?(t=[]) h = h::t;;
val foo : ?t:'a list -> 'a -> 'a list = <fun>

Is [] a single token, or is it two? Is [] twice as verbose as NIL?

multiple-value-bind

is five times more verbose in OCaml than Lisp:

multiple - value - bind

etc.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Ulf Wiger

2007-07-23, 7:07 pm

>>>>> "Jon" == Jon Harrop <jon@ffconsultancy.com> writes:

Jon> Joachim Durchholz wrote:[color=darkred]

Jon> Even if there is four times as much code?
[color=darkred]

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

2007-07-23, 7:07 pm

David Golden wrote:
> 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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...entists/?usenet

Stefan Ram

2007-07-23, 7:07 pm

Mark Tarver <dr.mtarver@ukonline.co.uk> writes:
>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.

Here is a Java implementation. It does not follow the formal
type semantics precisely and just runs the example program -
not the rest of the language. Both could be added keeping the
global structure of the code.

It uses the library "ram.jar"

http://www.purl.org/stefan_ram/pub/ram-jar

to read the program to a kind of S-expression. Because "=" has
a special meaning for this kind of S-expression, "=" was
renamed to "eq". The source also was slightly reformatted to
use other delimiters for lists and strings.

A preprocessor converts texts in single quotes as used below
to Java identifiers.

The main parts of the program:

method main iterate through the program
method execute execute a statement
method value evaluate an expression
object of class Input the input from the user
object of class State the state of the interpreter
objects of class Symbol a statement or an expression
.of(kw) does it have keyword kw?
.operand(i) operand #i of the keyword
.string(i) operand #i as a string
.room(i) operand #i as a list

import de.dclj.ram.notation.unotal.RoomSource;
import static de.dclj.ram.notation.unotal.RoomFromModule.roomFrom;
import static java.lang.System.out;

public class Main
{ public static void main( final java.lang.String[] args )
{ final Input input = new Input();
final State state = new State( input );
boolean running = true; while( running )
{ final java.lang.Object 'source entry' = state.'current entry'();
if( 'source entry' instanceof RoomSource )
{ final Symbol statement = new Symbol( 'source entry' );
running = running && execute( statement, state ); }
++state.'source pos';
if( state.empty() )running = false; }}

static boolean execute( final Symbol statement, final State state )
{ boolean running = true; if( statement.of( "end" ))
{ running = false; }
else if( statement.of( "print" ))
{ java.lang.System.out.println
( state.value.containsKey( statement.string( 0 ))?
value( statement.string( 0 ), state ) : statement.string( 0 )); }
else if( statement.of( "input" ))
{ state.value.put
( statement.string( 0 ), state.input.data.get( state.'input pos'++ )); }
else if( statement.of( "if" ))
{ execute
( new Symbol
( statement.room( value( statement.room( 0 ), state ) == 0 ? 4 : 2 )),
state ); }
else if( statement.of( "goto" ))
{ state.'go to'( statement.string( 0 )); }
else if( statement.of( "--" ))
{ state.value.put
( statement.string( 0 ),
java.lang.String.valueOf
( value( statement.string( 0 ), state ) - 1 )); }
else if( statement.of( "++" ))
{ state.value.put
( statement.string( 0 ),
java.lang.String.valueOf
( value( statement.string( 0 ), state ) + 1 )); }
return running; }

static int value( final java.lang.Object object, final State state )
{ int result = java.lang.Integer.MIN_VALUE;
if( object instanceof java.lang.String )
{ final java.lang.String string =( java.lang.String )object;
if( string.matches( "[0-9]+" ))
{ result = java.lang.Integer.valueOf( string ); }
else
{ result = java.lang.Integer.valueOf
(( java.lang.String )state.value.get( string )); }}
else
{ final Symbol expression = new Symbol( object );
if( expression.of( "eq" ))
{ final int l = value( expression.operand( 0 ), state );
final int r = value( expression.operand( 1 ), state );
result = l == r ? -1 : 0; }}
return result; }}

class Input
{ final RoomSource source = roomFrom
( " " +
" " +
" " +
" < < print [Add x and y] > " +
" " +
" < print [Input x: ] > " +
" < input x > " +
" " +
" < print [Input y: ] > " +
" < input y > " +
" " +
" main " +
" < if< x eq 0 >then< goto end >else< goto sub1x >> " +
" " +
" sub1x " +
" < -- x > " +
" < ++ y > " +
" < goto main > " +
" " +
" end " +
" < print [The total of x and y is ] > " +
" < print y > " +
" " +
" > " +
" " +
" " +
" " );
final RoomSource data = roomFrom
( "< 10 20 >" ); }

class State
{ public final Input input;
public State( final Input input )
{ this.input = input; }
public final java.util.Map<java.lang.String,java.lang.Object> value =
new java.util.HashMap<java.lang.String,java.lang.Object>();
int 'source pos' = 0;
int 'input pos' = 0;
public void 'go to'( final java.lang.String label )
{ for( int i = 0; i < input.source.length(); ++i )
if( label.equals( this.input.source.get( i )))this.'source pos' = i; }
public java.lang.Object 'current entry'()
{ return this.input.source.get( this.'source pos' ); }
public boolean empty()
{ return this.'source pos' >= this.input.source.length(); }}

class Symbol
{ java.lang.String keyword = null;
int 'keyword pos' = -1;
RoomSource source = null;
public Symbol( final java.lang.Object entry )
{ source =( RoomSource )entry;
keywordPos = 0;
keyword =( java.lang.String )source.get( 0 );
if( source.length() > 1 &&
source.get( 1 )instanceof java.lang.String )
{ final java.lang.String cadr =( java.lang.String )source.get( 1 );
if( "and".equals( cadr ) || "or".equals( cadr ) || "is".equals( cadr ) ||
"<".equals( cadr ) || ">".equals( cadr ) || "eq".equals( cadr ))
{ 'keyword pos' = 1; keyword = cadr; }}}
public final java.lang.String keyword(){ return this.keyword; }
public final boolean of( final java.lang.String string )
{ return string.equals( this.keyword() ); }
public final java.lang.Object operand( int pos )
{ if( pos >= 'keyword pos' )++pos;
return this.source.get( pos ); }
public final java.lang.String string( final int pos )
{ return( java.lang.String )this.operand( pos ); }
public final RoomSource room( final int pos )
{ return( RoomSource )this.operand( pos ); }
public final java.lang.String toString()
{ return this.source.toString(); }}

/*

Add x and y
Input x:
Input y:
The total of x and y is
30

*/

David Golden

2007-07-23, 7:07 pm

Jonnie wrote:
> Sounds like another triumph of hope over reality

I don't think anyone's gonna buy that, Jonnie boy.
The Qi and ML programs as a whole may have similar
effects, but hey, I could drive or skate to
the shops too.

Stefan Ram

2007-07-23, 10:05 pm

ram@zedat.fu-berlin.de (Stefan Ram) writes:
>/*
>
>Add x and y
>Input x:
>Input y:
>The total of x and y is
>30
>
>*/

So, this is supposed to be a benchmark for the execution time?

The programm initially took about 15 or 25 seconds for 100000
iterations.

I did not write it with performance in mind. So I tried to do
some microoptimizations for the name-value-lookup, integer
variable storage and the label-offset-lookup and eventuelly it
took just below 10 s:

Add x and y
Input x:
Input y:
The total of x and y is
200000

9,639743

But this is running on historic hardware that was at the
low end even when it was built about 10 years ago. It should
run in about 1 s on a consumer class computer bought today.

I believe that I now could write a faster interpreter by
first translating the S-expression to an object model.

Paul Rubin

2007-07-23, 10:05 pm

Matthias Benkard <mulkiatsch@gmail.com> writes:
> 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

2007-07-23, 10:05 pm

Ulf Wiger <etxuwig@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.

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.