Groups | Search | Server Info | Login | Register

Groups > gnu.emacs.help > #60982

TCO with named-let via macros (was: thanks - calculate pi fn. in elisp)

Show all headers | View raw

Richard Smith <null@void.com> writes:
>
> You will know better ways, but this "scribble" was a nice bit of
> learning maths.

I can imagine. Maths and Lisp are fascinating mind games.   (:

Some comments ...

> (setq max-lisp-eval-depth (expt 2 20))

This sets some limit for stack recursion to some high value. My
understanding is that this is not the number of recursive calls, but
something different, which I could not find out. Pointers appreciated.

> (defun h-invnsq (this-n invnsq-sum)
>   (if (zerop this-n)
>       invnsq-sum
>     (h-invnsq (1- this-n) (+ invnsq-sum (/ 1e0 (expt this-n 2))))))

So here h-invnsq calls itself, with a different set of arguments, and
this is the last action within this function, no matter the outcome of
the "if". So h-invnsq is in "tail position". Other Lisps will transform
a recursive call in tail position into a simple jump ("goto"). This is
required behaviour for all Scheme implementations, but some Common Lisp
implementations, e.g., SBCL, will do it as well.

Unfortunately, Emacs Lisp does not do this TCO ("Tail Call
Optimization"), with the exception of named-let. So I have taken to the
habit of writing recursive stuff not only with tail calls (where
possible, and this often mandates "helper functions", in your case
"pi-calc", kind of initializing the recursive "workhorse"), but also
with "named-let", to reap the benefits of TCO.

Your example would then look like this:

(defun pi-calc (n-to)
  "calculates Pi - arg integer is to how 1/n^2 integer to sum"
  (named-let h-invnsq ((this-n n-to)
                       (invnsq-sum 0))
    (if (zerop this-n)
        (sqrt (* 6 invnsq-sum))
      (h-invnsq (1- this-n) (+ invnsq-sum (/ 1.0 (expt this-n 2)))))))

So this-n gets bound to n-to and invnsq-sum to 0 (this is the "let"
part; as you know, let is used for local bindings). However, this also
names a function (this is the "named" part of "named-let") which can
then be called in the body of the named-let (guaranteering TCO).

(pi-calc 1000000)

will then work fine without increasing "max-lisp-eval-depth".

Now if you think this boilerplate code is annoying, then I am with
you. Fortunately, since all Lisps are extremely malleable languages
(think metal plasticity ...), automation of this is just a macro (not:
keyboard macro) away:

(defmacro defun-tco (name args body)
  "Wraps a 'named-let' around BODY to have a TCO of function NAME with ARGS."
  (declare (indent defun))
  (let ((bindings (gensym)))
    (setq bindings (mapcar #'(lambda (arg) (list arg arg)) args))
    `(defun ,name ,args
       (named-let ,name ,bindings
         ,body))))

Ignore the "declare" and the "gensym" for now. With this, you can simply
do

(defun-tco pi-calc (this-n invnsq-sum)
  (if (zerop this-n)
      (sqrt (* 6 invnsq-sum))
    (pi-calc (1- this-n) (+ invnsq-sum (/ 1.0 (expt this-n 2))))))

and then call

(pi-calc 1000000 0)

without exploding the stack. There is room for improvement (neither
support for good-practice docstrings nor local variables eliminating the
need to give two arguments to "pi-calc"), but I am sure the Emacs Lisp
gurus here could help with this. It was meant as a brief sketch. For a
discussion on optional docstrings in macros (Common Lisp, not Emacs
Lisp), see

  https://stackoverflow.com/questions/66364347/correct-way-to-incorporate-a-docstring-in-a-def-macro

Best regards

Axel

Back to gnu.emacs.help | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

thanks - calculate pi fn. in elisp Richard Smith <null@void.com> - 2024-07-09 19:48 +0100
  TCO with named-let via macros (was: thanks - calculate pi fn. in elisp) Axel Reichert <mail@axel-reichert.de> - 2024-07-09 23:15 +0200
    Re: TCO with named-let via macros Richard Smith <null@void.com> - 2024-07-10 06:28 +0100
      Re: TCO with named-let via macros steve g <sgonedes1977@gmail.com> - 2024-08-10 15:56 -0400
        Re: TCO with named-let via macros Richard Smith <null@void.com> - 2024-08-10 22:28 +0100
    Re: TCO with named-let via macros Richard Smith <null@void.com> - 2024-07-10 06:36 +0100
      Re: TCO with named-let via macros steve g <sgonedes1977@gmail.com> - 2024-08-10 16:22 -0400
        Re: TCO with named-let via macros Axel Reichert <mail@axel-reichert.de> - 2024-08-10 23:15 +0200
          Re: TCO with named-let via macros steve g <sgonedes1977@gmail.com> - 2024-08-11 14:56 -0400
          Re: TCO with named-let via macros Richard Smith <null@void.com> - 2025-04-08 10:26 +0100
    Re: TCO with named-let via macros Richard Smith <null@void.com> - 2024-07-10 06:59 +0100
    Re: TCO with named-let via macros Richard Smith <null@void.com> - 2024-07-10 09:18 +0100
      Re: TCO with named-let via macros steve g <sgonedes1977@gmail.com> - 2024-08-10 16:26 -0400
        Re: TCO with named-let via macros Richard Smith <null@void.com> - 2024-08-10 22:51 +0100

csiph-web