Re: Sorting times

[Vladimir Nesterovsky <vnestr@netvision.net.il>]

Reini --

On Wed, 26 May 1999 15:15:40 +0000, you wrote:

>Vladimir Nesterovsky wrote:
>> have you had a chance to look into the data
>
>right now we switched from BNC ethernet to twisted pair, the whole
>weekend crawling on the floor... :)

...noticed _that_. :)

>anyway, i have more problems with the "famous funarg problem", not having lexical
>binding. every stdlib function accepting functions as arguments has inherent problems
>shadowing bindings of internaly used vars. same with my "destructive" functions.
>for now i marked all better-to-be-lexical vars with a "_" and "_$" prefix.
>either i can establish a common obscure prefix for such problematic vars, such as
>"_$", but when these functions are called recursively we are lost.
>with vill/vlisp i don't have such problems, all functions accepting functions are
>vlisp internal, which is lexical.
>
>or i'll try to make (FUNCTION) a closure, establish a lexical binding of the used
>vars. that will be the best. callbacks should be definable with FUNCTION then as
>well, instead of DEFUN. for named closures i thought of DEFCLOSURE in contrary to
>DEFUN. hmm, what do you think?

What I'm doing with this problem, is first -- to always put prefix on
all function's arguments, like fun::arg, which eliminates most of the
problems with data vars. Now for functions -- I call them always by
value -- I mean, I pass them by value, not by symbol reference.
IOW, (sort alist (lambda(x)...)) instead of
     (sort alist '(lambda(x)...))

Now in SORT I declare (defun sort (sort:alist sort:fun)) and sort:fun
gets set to the value of user supplied function, so no problem
with symbol name shadowing. I call it directly as (sort:fun x)
inside the body of sort, instead of (apply 'ufun (list x)), which
is also a bit more efficient, because the unneeded lists aren't
constructed -- I once measured the performance gain as 15% only
from this (I beleive I posted it then). When calling recursively,
there's another approach: don't transfer the function as parameter;
call it directly as (sort:fun) which is a global function from the
point of view of the sort_aux function that's called from sort.
Have a look into my mergesort.lsp. It goes like
 (defun mergesort (alist ufun)
   (setq ufun (make-usubr ufun))
   (_mergesort_aux alist))
... whereas a _mergesort_aux only gets alist arg; ufun is global
to it. (of course in a real code we must prepend a prefixes, as
discussed, like (sort sort:alist sort:ufun)). make-usubr makes usubr
from a user supplied function, be it usubr already, or a quoted
lambda expression, so that it's ready to be called directly.

The real problem with symbol shadowing is when you pass as a
user supplyed function a routine which depens/alters a global
(from its point of view) vars. That's the big problem, but hopefully
we may require a user not to program in that way. (may we?)

Wait -- actually, if we put prefix on every local var, no problem.

--
http://www.netvision.net.il/php/vnestr/