[Openmcl-devel] impact of number of arguments and closures on performance

[Waldek Hebisch]

On Tue, May 12, 2020 at 08:54:03AM +0200, Taoufik Dachraoui wrote:
> I am implementing a new lisp dialect programming language (statically
> typed, generic programming, lambda calculus + syntax)
> I found that limiting the number of variables in a closure may be of help
> in optimising the interpreter (simulator)
> 
> I would like to know how closures are efficiently implemented in lisp
> languages
> 
> In the implementation I have a notion of frame which contains the address
> of a function and the variables in a closure
> 
> and I am trying to optimise the implementation by limiting the size of the
> closure but this may not be acceptable
> 
> Any thoughts are welcome, and wanted to know how Clozure CL is implemented
> and if there is a notion of frames
 
I do not know how Clozure CL implements closures, but I can tell
you about two different system.  One is FriCAS which contains
staticaly typed language compiling to Common Lisp (you can run
FriCAS on top of Clozure CL).  In FriCAS finction is represented
by Lisp dotted pair, CAR is Lisp function while CDR is extra
argument.  For closures the extra argument is Lisp vector
containing captured values.  Currently FriCAS has no limit
on number of captured, while number of arguments to functions
is limited to about 30.  Limit on number of arguments is
kind of soft: FriCAS need a few Lisp symbols for each argument.
If needed one can increase number of arguments by adding
extra sysmbols (but up to now current limits are adequate).

Concerning efficiency, FriCAS compiler in several places
uses linear searches and large number of relevant objects
slows down compilation.  My experiments suggest that
Clozure CL has similar problem, normaly Clozure CL
compiler is quite fast, but with large number of variables
it considerably slowed down (at least that happended in the
past using earlier version).  Still, slowing down
compilation seems to be mcuh better than hard coded
limit.

Another system is Poplog.  It offers Lispy data structures
and user defined syntax (there is user accessible interface
to code generator, so users can generate arbitrary code
from new sysntax).  In Poplog closures are implemented
in two step way.  Namely, Poplog allows "partial
evaluation", that is you can replace last k arguments
to function by fixed values.  "partial evaluation" via
small stub which has table of fixed values and copies
values from table to argument positions.  Actual code of
function takes extra arguments for each closed over
variable.

-- 
                              Waldek Hebisch