Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Axel Reichert <mail@axel-reichert.de>
Newsgroups: comp.lang.lisp
Subject: Tail call recursion macro with named-let in Emacs Lisp (was: A simple lisp problem.)
Date: Sat, 15 Jun 2024 12:17:42 +0200
Organization: A noiseless patient Spider
Lines: 107
Message-ID: <87o782h5mh.fsf@axel-reichert.de>
References: <v4j2p1$3a0lu$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Sat, 15 Jun 2024 12:17:45 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ecc537ebfc5213417124a7d49f80461d";
	logging-data="3599724"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+7OHUeTZeUZhFwtl3sheiI2hxOgdBb2rM="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.2 (gnu/linux)
Cancel-Lock: sha1:EUzXnOCANkfSpnPRn7tT+1oIZQ0=
	sha1:3HsDE+X2aP56zMsPdpTBfA5uypM=
Bytes: 3880

"B. Pym" <No_spamming@noWhere_7073.org> writes:

> Frank Schwieterman wrote:
>
>> (defun difference (param)
>>      (if (> (length param) 1)
>>         (if (<= (abs (- (first param) (first (rest param)))) 1 )
>>            (difference (rest param))
>>            nil
>>            )
>>         T
>>         )
>>      )
>
> Gauche Scheme
>
> (define (diff1? xs)
>   (every
>     (lambda (a b) (= 1 (abs (- a b))))
>     xs
>     (cdr xs)))
>
> (diff1? '(2 3 4 3 4 5 6 7 8 9 8))
>   ===>
> #t
> (diff1? '(2 3 4 3 4 5 6 7 8 9 8 0))
>   ===>
> #f

A nice, recursive solution in Emacs Lisp would be

  (defun single-step-p (xs)
    (cond ((null (cdr xs)) t)
          ((= 1 (abs (- (car xs) (cadr xs)))) (single-step-p (cdr xs)))
          (t nil)))

but it fails for longer lists such as

  (single-step-p (number-sequence 1 1000))

because Emacs Lisp does not have proper tail call elimination. There is
an exception, though, "named-let", see here:

  https://www.gnu.org/software/emacs/manual/html_node/elisp/Local-Variables.html

So I rewrote the function to

  (defun single-step-p (xs)
    (named-let single-step-p ((xs xs)) 
      (cond ((null (cdr xs)) t)
            ((= 1 (abs (- (car xs) (cadr xs)))) (single-step-p (cdr xs)))
            (t nil))))

which work fine also for

  (single-step-p (number-sequence 1 1000000))

but of course looks a bit redundant compared to the "normal" use of
"named-let" for helper functions such as accumulating results etc.

So I wrote a small macro doing the wrapping in a "named-let" for me:

  (defmacro defun-tco-1 (name args body)
    `(defun ,name ,args
       (named-let ,name (,args ,args)
         ,body)))

Now

  (defun-tco-1 single-step-p (xs)
    (cond ((null (cdr xs)) t)
          ((= 1 (abs (- (car xs) (cadr xs)))) (single-step-p (cdr xs)))
          (t nil)))

works, but the macro of course fails for a different number of
arguments, as can be seen with

  (macroexpand-1 '(defun-tco-1 foo (a b) (+ a b)))

which gives

  (defun foo (a b) (named-let foo ((a b) (a b)) (+ a b)))

and of course also wrong results (14 instead of 10) for

  (foo 3 7)
  
So I needed to loop through the args of the macro and construct the
proper bindings for the "named-let":

  (defmacro defun-tco (name args body)
    (let ((bindings (mapcar #'(lambda (arg) (list arg arg)) args)))
      `(defun ,name ,args
         (named-let ,name ,bindings
           ,body))))

Is this fine from the point of the experts here (in fact, it is my first
macro that is unrelated to any macro tutorials/book, but rather came
from my own needs)? I am quite sure that I could suffer from variable
capture and perhaps also from multiple evaluation, but this would be the
second step for me after a first, general criticism here.

Many thank for any comments!

Best regards

Axel