Re: Computer Algebra Algorithms lisp vs. C.

parisse@xxxxxxxxxxxxxx wrote:
>> Modern FPLs are vastly better suited to CAS development than C++. The
>> resulting programs will be smaller, simpler, faster, more robust and
>> efficient than a C++ program written in the same amount of time.
>
> Can you show us some code that support your claim?

I sold the code to WRI and developed it under NDA, of course. However, I can
give you some information about it.

My original interpreter was 994 lines of (commented) OCaml code, including
the lexer, parser, interpreter and top level. My JIT compiler was 2,238
lines of code in total.

The size alone is a good reason to use an FPL. The development time is
probably the main reason though. Starting from scratch, with only
superficial knowledge of Mathematica itself (as a user) it took me four
days to write the first working interpreter which implements most of
Mathematica's core language in OCaml. This was only 6 months after I
started learning OCaml!

In terms of the code itself, here are some snippets from the originally open
source version (which is no longer available in full).

>From the 59-line lexer:

....
rule comment = parse
"*)" { token lexbuf }
| _ { comment lexbuf }
and token = parse
"(*" { comment lexbuf }
| [' ' '\t'] { token lexbuf }
| '[' { OPEN }
| ']' { CLOSE }
| '(' { BOPEN }
| ')' { BCLOSE }
| '{' { LOPEN }
| '}' { LCLOSE }
| '\n' { line := 1 + !line; CR }
....

>From the 89-line parser (some of the token definitions, operator
associativies and precedences and then the rules of the grammar):

....
%token <int> INTEGER
%token <string> SYMBOL
%token <string> PATTERNTYPE
%token CR NULLTYPE BOOLTYPE INTTYPE WITH FUN RETURN FUNC
....
%left SEMICOLON COMMA
%left FUNC
%left REPLACEALL REPLACEREPEATED
%right SET
%nonassoc SETDELAYED UPSET
....
expr:
SYMBOL { Sym $1 }
| INTEGER { Integer $1 }
| MINUS INTEGER { Integer (-$2) }
| pattern { $1 }
| expr REPLACEALL expr { Seq (Sym "ReplaceAll", [$1; $3]) }
....

>From the 816-line interpreter (entire definition of the type representing
the abstract syntax tree (a Mathematica expression) and then part of the
interpreter):

....
type ast =
Real of float
| Integer of int
| Sym of string
| Seq of ast * ast list
....
let eval state = function
Seq (Sym "Plus", [t]) -> eval state t
| Seq (Sym "Times", [t]) -> eval state t
| Seq (Sym "Plus", Integer n :: Integer m :: tl) ->
state, Seq (Sym "Plus", Integer (n+m) :: tl)
| Seq (Sym "Times", Integer n :: Integer m :: tl) ->
state, Seq (Sym "Times", Integer (n*m) :: tl)
....

Notice:

1. types do not need to be declared (type inference) and
2. are completely validated at compile-time (static type checking),
including tokens emitted by the lexer, abstract syntax tree reduced by the
parser and substitutions performed by the interpreter (eval)
3. the use of pattern matching in the interpreter to implement the core
substitutions provided by the language.
4. the brevity of the type declaration representing an abstract syntax tree
(5 lines of code!)
5. performance: the unoptimised first working version of the interpreter was
only 3-7x slower than Mathematica itself.

I found that the Mathematica pattern matcher was the most conceptually
difficult part to implement. It took me a whole day to implement just a
useful subset, resulting in some decidedly imperfect (but working!) code.
Mathematica's pattern matching capabilities far exceed those of any other
language I have come across, BTW.

Although my implementations were only prototypes, not ready for shipping,
they will be very useful for trying out different ideas without having to
change hundreds of thousands of lines of C (literally). I'm confident that
my work will help to widen the gap between Mathematica and other CASs. ;-)

I don't think I need to go into the reasons why this shouldn't be attempted
in C++...

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
.

Relevant Pages

  • Re: Why does everyone do it?
    ... reaction from Han. ... mathematical definition in 'Principia Mathematica' by Russell and ... definition we are in NO TROUBLE whatsoever. ... mentioning those tokens but using them to refer to the number 1. ...
    (sci.math)
  • Re: the necessity of Lisps Objects?
    ... because the interpreter is just providing the glue. ... kind of use that Mathematica was designed for. ... the compiler must be able to deal with anything that the programmer ... programmers, in which case Mathematica sucks for them, of course - but ...
    (comp.lang.lisp)
  • Re: Programming Language Productivity: The Stupidity of Programmers
    ... Tak To wrote: ... an interpreter comprises of a compiler ... while others would process several tokens all at once at various ...
    (comp.object)
  • Re: Programming Language Productivity: The Stupidity of Programmers
    ... Tak To wrote: ... an interpreter comprises of a compiler ... while others would process several tokens all at once at various ...
    (comp.programming)
  • Re: Where comes the myth that Lisp is interpreted?!
    ... less the first time my collegues encounter FP (through Mathematica). ... After pointing out during a lecture that Mathematica was very much like ... Lisp, I asked if it may be programmed in any Lisp dialect. ... Once Jon Harrop wrote an interpreter that performed the important core ...
    (comp.lang.lisp)
Loading