Re: Very poor Lisp performance / about Mathematica

Joe Marshall wrote:
> Jon Harrop <usenet@xxxxxxxxxxxxxx> writes:
>> You cannot predict what such an OCaml program will do.
>
> I can predict that OCaml will correctly evaluate programs that have no
> side effects.

IIRC, there was some interesting work at Oxford recently that demonstrated
how the side-effect-free (and without laziness) subset of ML is strictly
less powerful.

> This is a pretty strong prediction. When this
> predicition is not adequate (that is, when I wish to use side
> effects), the language provides sequencing constructs for this
> purpose. Not using them is considered an abuse of the language.

Yes.

>> From experience, none of these have ever caused me a problem.
>
> You've never used the Update function?

Nope. Indeed, I had never even heard of the Update function.

>>> There are BIG differences between mathematical functions and rewrite
>>> rules. Even a rewrite rule that defines a function may not be the
>>> function you think it is or expect. Lisp hackers, computer language
>>> theorists, and especially computer language and computer algebra
>>> theorists know that function definition is one of the trickiest parts
>>> of semantics.
>>
>> Can you be more specific?
>
> Sure. In Lisp, you can write higher-order functions --- functions
> that take functions as arguments and return functions as values.
> Let's consider the set of functions. Some of these map from the set
> of functions to the set of functions. But given a discrete domain and
> range, the number of functions that can be defined over that domain
> and range is
> domain
> range
>
> So the set of functions has a cardinality equal to that cardinality
> raised to itself. Only the empty set has this property.
>
> Once you get past that difficulty, you'll find that what you are
> defining is likely a series of approximations to a computable partial
> function.

I wouldn't apply any of that theory to Mathematica directly. In Mathematica,
you only have replacement rules that locate ASTs matching given patterns
and substitute them with ASTs. So there are no functions that map integers
to functions in Mathematica, for example.

> But then again, you might not be defining a function at all.
> The fibonacci function can be mathematically defined with this
> recurrance relationship:
>
> F(n) = F(n+1) - F(n-1)
>
> but that definition won't work in a computer.

No. Firstly, your definition is both wrong and incomplete (it needs base
cases before it will work, even in maths), it should be:

F(n) = F(n-1) + F(n-2)
F(1) = F(2) = 1

Secondly, you can type this into Mathematica and compute Fibonacci numbers
"in a computer":

In[2]:= F[n_] := F[n-1] + F[n-2]

In[3]:= F[1] = F[2] = 1

Out[3]= 1

In[4]:= F[10]

Out[4]= 55

You can get a better idea of how Mathematica's fixed point based evaluation
is working by looking at the equivalent OCaml function, written using
pattern matching:

# let rec f n = match n with
| 1 | 2 -> 1
| n -> f(n-1) + f(n-2);;
val f : int -> int = <fun>
# f 10;;
- : int = 55

You have to do little more than decorate with polymorphic variant type
constructors and add substitution until fixed point to get a
mini-Mathematica interpreter written in OCaml:

# let rec eval t =
let t' = match t with
| `Seq (`Plus, [i; j]) -> begin match eval i, eval j with
| `Int i, `Int j -> `Int (i + j)
| i, j -> `Seq (`Plus, [i; j])
end
| `Seq (`F, [`Int (1 | 2)]) -> `Int 1
| `Seq (`F, [n]) ->
let n = eval n in
let e1 = eval (`Seq (`Plus, [n; `Int (-1)])) in
let e2 = eval (`Seq (`Plus, [n; `Int (-2)])) in
eval (`Seq (`Plus, [`Seq (`F, [e1]); `Seq (`F, [e2])]))
| ast -> ast in
if t = t' then t else eval t';;
val eval : ([> `Int of int | `Seq of [> `F |`Plus ] * 'a list ] as 'a)
-> 'a = <fun>

For example, this can evaluate "1+2":

# eval (`Seq (`Plus, [`Int 1; `Int 2]));;
- : [> `Int of int | `Seq of [> `F | `Plus ] * 'a list ] as 'a = `Int 3

As the rules for the Fibonacci recurrence relation are built in, it can also
compute Fibonacci numbers:

# eval (`Seq (`F, [`Int 10]));;
- : [> `Int of int | `Seq of [> `F | `Plus ] * 'a list ] as 'a = `Int 55

You can probably write that interpreter more succinctly in Lisp thanks to
quote. However, it is nice that the OCaml compiler infers the type of the
(polymorphic variant) AST and statically type checks its use.

>>> In Mathematica, however, this would not work. The value of a HOLD
>>> expression cannot be the object that is held because *that* object
>>> might be an expression (and thus get fed back into the Mathematica
>>> evaluator). Instead, the value of a HOLD expression is the HOLD
>>> expression itself.
>>
>> I don't understand. What do you mean by "object" in the context of
>> Mathematica?
>
> I may be using a bad terminology. In Lisp there are data structures
> that can be used to represent Lisp expressions. The data structures
> *aren't* expressions --- they are just data structures:
>
> (defvar *my-ds* nil)
>
> (push '4 *my-ds*)
> (push '3 *my-ds*)
> (push '+ *my-ds*)
> *my-ds*
> => (+ 3 4)
>
> Note that this does *not* evaluate to 7. It's a list that happens to
> look like an expression. If I continue to push elements:
> (push '2 *my-ds*)
> (push '* *my-ds*)
> (push '5 *my-ds*)
> *my-ds*
> => (5 * 2 + 3 4)
>
> I now have a list that happens to look a lot like an infix
> expression. It *isn't* an expression, but it looks like one.

Yes. It is an abstract syntax tree (AST). In Mathematica, you only have
ASTs.

> Presumably, Mathematica has some sort of data structure that can be
> used in a similar way.

Yes, in Mathematica you use an AST that looks like a list. It is written:

{1, 2, 3}

but it is actually stored as the AST (seen in "FullForm"):

List[1, 2, 3]

There are functions like Part that allow you to extract "elements" (ASTs)
from these "lists" (ASTs). These functions can be implemented as
replacement rules (also ASTs). For example, a replacement rule to extract
the first element (the head) of a list may be written:

{h_, ___} -> h

But this is just syntactic sugar for another AST:

Rule[List[Pattern[h, Blank[]], BlankNullSequence[]], h]

Mathematica's evaluation strategy (replace repeatedly, to fixed point) is
equivalent to the recursion of a term-level Lisp interpreter (or any other
language). If Mathematica is fed rules that never reach fixed point then it
hangs. If a term-level Lisp interpreter is fed a program that recurses
indefinitely then it also hangs.

> Yes, you have to apply Release manually and that `turns on'
> evaluation, but how do you `turn it off' again?

You can apply Hold again. As a shortcut, if just you want to evaluate what
is inside a Hold[...] AST, is to use Hold[Evaluate[...]] which evaluates
the inner expression. For example:

In[5]:= Hold[Evaluate[1 + 2 + Hold[3 + 4]]]

Out[5]= Hold[3 + Hold[3 + 4]]

>>> (In Lisp, QUOTE and EVAL respectively take you one step up and down
>>> the syntactic reflect/reify tower. At each meta-level, additional
>>> quotes take you further up, and additional EVALs take you further
>>> down. In Mathematica, HOLD takes you a step up, but RELEASE takes you
>>> *all the way down* to the bottom level.)
>>
>> No. Release only removes 1 level of Hold:
>>
>> Release[Hold[Hold[x]]]
>> Hold[x]
>
> That's not what I meant. I meant that once Released, the substitution
> rules are iteratively applied until the form is fully reduced. You
> cannot do a `one-step' Release.

That is like saying that you do not want the result of a recursive function
call but, rather, you want to inline the body of the function having
substituted the arguments.

In Mathematica, you cannot apply all of the built-in rules once only (AFAIK)
but you can apply specified rules once only. For example, this gives the
body of the "recursive call" F[10] with its argument substituted:

In[8]:= F[10] /. {F[n_] -> F[n - 1] + F[n - 2], F[1] -> 1, F[2] -> 1}

Out[8]= F[8] + F[9]

>>> This is an example of being ignorant about language design principles.
>>> If you have reflection in a language, you should make sure that each
>>> reflective operator has a corresponding reification operator that
>>> *exactly* undoes that reflection. If you don't, it will be either
>>> painful or impossible to *use* the reflection in non-trivial ways.
>>> Mathematica chose to ignore this principle, and guess what happens.
>>
>> Are you sure you haven't misunderstood Release?
>
> No, I'm not sure, but that's what I infer from Fateman's paper and
> what you have been saying.

Ok. I think you're on the right track and hopefully what I just said will
clarify things. Mathematica's evaluation strategy is not like those of
other languages but it does work very well, especially for symbolic maths.

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

Relevant Pages

  • What does the simplified sexp-based syntax for C# looks like?
    ... language", parse it, and produce the parse tree from it, then you ... don't have to write functions such as this OCaml example. ... correct by comparing the C# AST I produce against one that I expect. ...
    (comp.lang.lisp)
  • Re: parser
    ... all I could see was an example for a trivial language. ... Did I mention that Ocaml is fast? ... reason is that Mathematica has an unusually rich syntax. ... concise that the equivalent C++. ...
    (comp.programming)
  • Re: Computer Algebra Algorithms lisp vs. C.
    ... > in a non-standard language like maple language might not work ... I just tried exactly this: running some Mathematica and some ... > Of course Lisp, Ocaml, etc. are certainly appropriate languages too, ...
    (sci.math.symbolic)
  • Re: SBCL is now faster than Java, as fast as Ocaml, and getting better
    ... amount to learn from Mathematica because it addressed so many of Lisp's ... What do you think Mathematica can learn from Lisp? ... are overestimating the "language merits" of Mathematica as far as its ... go beyond our discussion of Lisp, MLish and pattern matching. ...
    (comp.lang.lisp)
  • Re: A question on Newtons Method
    ... bug reports per day. ... there are arbitrary-precision integers and rationals (Num in OCaml, ... native format in Mathematica, and a major hassle in Fortran). ...
    (sci.math.num-analysis)