Re: [Maxima-discuss] Lisp error in the evaluator (Lisp function objects as operators)

[Henry B. <hb...@pi...>]

Hi Richard, et al:

The discrepancies between "interpreted" and "compiled" code has plagued Lisp and Lisp-like (incl. Maxima) languages ever since McCarthy's Lisp group wrote their first Lisp compiler.

 From a theoretical perspective, the problem *cannot* be solved, since the only way to ensure 100% compatibility is through so-called "lazy evaluation", which is not the standard semantics of Common Lisp.  (Lazy evaluation is the mechanism that ensures the *unique* result of lambda calculus evaluation -- assuming that a result is ever obtained at all.)

The second best approach is that of SBCL, which (at least in the version installed on my machine) *compiles every expression* prior to execution -- e.g., even simple expressions like "(+ 2 3)" that are typed in at "top level".

Modern Javascript implementations use so-called "incremental compilation", whereby sub-expressions are compiled and the compiled code is cached; if for any reason the compiled code is suspected of being stale, that compiled code is flushed from the cache.  Probably the earliest incremental compilers were implemented for APL back in the 1970's; APL expressions cannot be "compiled" in the usual sense, since these expressions cannot even be unambiguously *parsed* without interpreting them!

As Richard has correctly observed, code involving heavily generic arithmetic operations are unlikely to benefit substantially from compilation -- e.g., bfloat arithmetic or bignum arithmetic implemented by means of the Gnu MP library (gmplib.org).  Every such operation involves at least one function call, which eliminates most of the opportunities for speed optimization.

Maxima has (at least) two choices: fix the Maxima translator to output code which respects dynamic binding, or (for the much longer term) changing Maxima to rely a lot less on dynamic binding, and lexically signal dynamic binding the way that Common Lisp (mostly) does.

The PDP10 Maclisp compiler was the epitome of dynamic binding compilation quality -- which quality will never again be achieved.  So Maxima's current reliance on dynamic binding puts it on the wrong side of history.  I'm not a big fan of the Javascript language, but do applaud their choice of lexical scoping -- even for so-called "closures" (aka Maclisp "FUNARG"s).

At 08:11 AM 7/22/2016, Richard Fateman wrote:
>First, some history.
>
>The motivation for compiling a Macsyma function F was to speed up the
>evaluation of numerical functions (those that return machine floating-point numbers)
>that are used by plotting F or numerical quadrature: integration of F between
>limits. Such uses typically call F many times.  Typically F does not use symbolic
>aspects of computing.
>
>Unfortunately, IMHO the undergraduate who took on this task was overly ambitious,
>very keen on showing off, and entirely lacking in taste.
>
>Hence a remarkably elaborate program was produced,
>displaying peculiar behavior and unique "style" . And buggy.
>The code is spread over 13 files, for example. See the comments in transl.lisp.
>
>The code for translating lambdas is probably in trans3.lisp, whose comments
>demonstrate the ambitions and style of the original author, who has tried to
>implement ideas that were not, and never have been in Macsyma.
>
>For example, I think he tried to do lexical scope.
>Thus foo(x):=lambda([y],x+y);
>allows foo(3)(4) to return 7.
>It doesn't, untranslated it returns x+4.
>translated it returns (on sbcl) the bogus result "symbol".
>
>Second,
>
>The simple solution to this particular "bug" is for the translation code to
>NOT TRANSLATE or compile code like lambda([], ....) but to 
>essentially leave it alone.  It's not going to make it faster if it
>mimics in its entirety the binding mechanism used in Maxima.
>It can just return something like a call to meval or mfuncall.
>
>This has the positive result that the computed return value from running the
>translated/compiled code is exactly the same as running the uncompiled code.
>
>While I do not recommend a further retreat, one could find a vast
>simplification of the process here by doing what (some version of ...) Mathematica
>did, which is to compile only arithmetic expressions. No loops, gotos, 
>symbolic stuff, etc. This worked some of the time, as long as complex numbers
>were not used in the intermediate calculations. This may have been extended, though
>in later Mathematicas.
>
>For Maxima, my suggested solution is to go into transl or trans3, and disable the code that tries to
>translate a returned lambda expression. I expect that the change would be 
>a line or two of code at most, and maybe would even shorten the code.
>
>Finding the right spot might take some study, since lambda expressions that
>are properly called seem to use the same code.  Indeed, properly returning a
>correct lambda expression (an "upward funarg") is tricky. The phrase that comes to
>mind with respect to the code in trans3 is that it is attempting to pick up a turd by the clean end.
>
>Philosophically,
>
>While it may be possible to put "anything" through the translation/compilation
>route, many constructions will likely take up more memory but run at the same speed.
>
>A major use of the compiler in the commercial Macsyma may 
>have been for code obfuscation and (possibly?) for faster loading.
>
>Finally,
>
>The very very simplest solution is to ignore this problem.
>
>Taxing every use of "meval1" to repair this (on the grounds that it can hardly
>take much time) is unappealing to me.
>
>Making something less efficient on the grounds that it is only
>a little less efficient is a bad reason.
>
>RJF
>
>On 7/21/2016 7:34 PM, Stavros Macrakis wrote:
>
>>PS why do you call (( <opaque compiled function object) ... ) a well-formed (Maxima) expression?  There are lots of perfectly good Lisp objects which Maxima doesn't (currently) allow in Maxima expressions.
>>
>>On Jul 21, 2016 22:27, =?UTF-8?B?U3RhdnJvcyBNYWNyYWtpcw==?= =?UTF-8?B?ICjOo8+EzrHhv6bPgc6/z4IgzpzOsc66z4HOrM66zrfPgik=?= <mac...@al...> wrote:
>>
>>Lisp compiled function objects are *not* first-class citizens in Maxima today: they don't have a clean output representation and we've found two cases where they're not handled properly so far.  Lisp symbols with function values are what Maxima expects to work with, hence my suggestion of gensyms.
>>
>>The translator should work with the system as it is, not as it would like it to be.
>>
>>Of course that doesn't preclude modifying the system and then the translator.
>>
>> -s
>>
>>PS written on my phone without testing additional card....
>>
>>On Jul 21, 2016 21:31, "Kris Katterjohn" <kat...@gm...> wrote:
>>On Thu, Jul 21, 2016 at 04:22:10PM -0400, Stavros Macrakis (Σταῦρος Μακράκης) wrote:
>>> I would say that that *is* a bug in the translator. The translator should
>>> be returning an object of a type recognized by Maxima, maybe a gensym with
>>> that function property.
>>
>>Well, it's translating a (Maxima) lambda expression into a lisp
>>function, and lisp functions are recognized by Maxima. I'm not saying
>>that the translator couldn't be improved, but it seems like it's doing
>>what I asked for in a reasonable way.
>>
>>I'm not sure how much sense it makes to return a gensym. Currently after
>>
>>(%i1) foo () := lambda ([], 1)$
>>(%i2) translate (foo)$
>>(%i3) f : foo ()$
>>
>>f's value is a lisp function. This is what I would expect (am I wrong
>>to expect this?). Based on the definition of foo, I don't understand
>>why f's value should be a symbol. The translator doesn't know what (if
>>anything) I'll be doing with foo's return value later on.
>>
>>It still seems to me that there is a bug in MEVAL1. It's handed a
>>well-formed expression, but instead of evaluating it in the way that I'd
>>expect, it constructs a bogus expression which it then tries to
>>evaluate, which causes it to throw a lisp error. If this is not a bug,
>>then at the very least it's not optimal (as RJF would say).
>>
>>> meval1 is not the only place affected. Consider
>>>
>>> f():=lambda([],1)$
>>> funmake(f(),[]) => OK
>>> translate('f)$
>>> funmake(f(),[])) => error
>>
>>Fair enough, but at least here it's a Maxima error instead of a lisp error.
>>
>>Cheers,
>>Kris Katterjohn