named-let

named-let

[Stefan Monnier]

The recent discussion around loops motivated me to look a bit further
into named-let.  It's actually easy to define:

    (defmacro named-let (name bindings &rest body)
      "Looping construct taken from Scheme.
    Like `let', bind variables in BINDINGS and then evaluate BODY,
    but with the twist that BODY can evaluate itself recursively by
    calling NAME, where the arguments passed to NAME are used
    as the new values of the bound variables in the recursive invocation."
      (declare (indent 2) (debug (symbolp (&rest (symbolp form)) body)))
      (let ((fargs (mapcar (lambda (b) (if (consp b) (car b) b)) bindings))
            (aargs (mapcar (lambda (b) (if (consp b) (cadr b))) bindings)))
        ;; According to the Scheme semantics of named let, `name' is not in scope
        ;; while evaluating the expressions in `bindings', and for this reason, the
        ;; "initial" function call below needs to be outside of the `cl-labels'.
        `(funcall
          (cl-labels ((,name ,fargs . ,body)) #',name)
          . ,aargs)))

You can then define

    (defun my-length (xs)
      (named-let loop ((xs xs) (n 0))
        (if xs
            (loop (cdr xs) (1+ n))
          n)))

Now this definition of length is recursive, so without some proper tail
call optimization, it'll burp on any longish list (apparently 1000
elements are sufficient).

But with the recent tail-call optimization I installed into `master`,
the above `my-length` now works without eating up stack space.
It's still not as efficient as a hand-written `while` loop, but it's not
that bad.  Here's the byte-code for the above function:

    byte code:
      doc:   ...
      args: (arg1)
    0       dup       
    1       constant  0
    2       constant  nil
    3:1     stack-ref 2
    4       stack-ref 2
    5       stack-ref 1
    6       goto-if-nil 2
    9       stack-ref 1
    10      cdr       
    11      stack-set 5
    13      dup       
    14      add1      
    15      stack-set 4
    17      constant  :recurse
    18      goto      3
    21:2    dup       
    22      stack-set 3
    24      constant  nil
    25:3    discardN-preserve-tos 2
    27      goto-if-not-nil 1
    30      dup       
    31      stack-set 1
    33      return    

Notice how there's really no `lambda` nor `funcall` that remains.


        Stefan

Re: named-let

[tomas]

[-- Attachment #1: Type: text/plain, Size: 497 bytes --]

On Fri, Jan 08, 2021 at 08:43:13PM -0500, Stefan Monnier wrote:
> The recent discussion around loops motivated me to look a bit further
> into named-let.  It's actually easy to define:

:-)

I'm always impressed by the tricks the Lisps can do, at
the hands of experts.

And thanks, Stefan, for explaining things in a way I
can (think I) understand them :-)

(Back on topic: I grew some affection for the named let
from the Scheme/Guile side, so thanks for that, too)

Cheers
 - t

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: named-let

[Joost Kremers]

On Sat, Jan 09 2021, tomas@tuxteam.de wrote:
> (Back on topic: I grew some affection for the named let
> from the Scheme/Guile side, so thanks for that, too)

Hmpf, I prefer loop/recur... *grumblegrumble*

/s


-- 
Joost Kremers
Life has its moments

Re: named-let

[Stefan Monnier]

>> (Back on topic: I grew some affection for the named let
>> from the Scheme/Guile side, so thanks for that, too)
> Hmpf, I prefer loop/recur... *grumblegrumble*

Well,

    (defmacro loop (&rest r)
      `(named-let recur . ,r))

does the trick AFAIK, except that it won't signal an error for uses of
`recur` which aren't recognized as tail-calls.

It would be easy to make a replacement of `cl-labels` which signals an
error if the recursice calls aren't recognized as tail-calls (the
current code already tests for it, but only in order to optimize the
`letrec` into a `let*` rather than to signal an error).


        Stefan

Re: named-let

[Tomas Hlavaty]

> But with the recent tail-call optimization I installed into `master`,
> the above `my-length` now works without eating up stack space.

That's great news.

Is TCO always used (like in Scheme) or in which cases is it used or not
used?  Is it possible to turn it on or off?

Re: named-let

[Stefan Monnier]

>> But with the recent tail-call optimization I installed into `master`,
>> the above `my-length` now works without eating up stack space.
> That's great news.

Probably not as great as you think.

> Is TCO always used (like in Scheme) or in which cases is it used or not used?

It's basically never used.  It's only applied for the particular case of
tail recursive calls to functions defined by `cl-labels` and only for
those calls that are "self-recursive" (i.e. come from within the code of
that function).

> Is it possible to turn it on or off?

No.


        Stefan

Re: named-let

[Helmut Eller]

On Sat, Jan 09 2021, Stefan Monnier wrote:

>> Is TCO always used (like in Scheme) or in which cases is it used or not used?
>
> It's basically never used.  It's only applied for the particular case of
> tail recursive calls to functions defined by `cl-labels` and only for
> those calls that are "self-recursive" (i.e. come from within the code of
> that function).

Is there hope for general contification? So that things like

(defun my-even? (x)
  (cl-labels ((even? (x) (or (= x 0) (odd? (1- x))))
              (odd?  (x) (or (= x 1) (even? (1- x)))))
    (even? x)))

are translated to a bunch of gotos and no lambdas.

Helmut

Re: named-let

[Stefan Monnier]

> Is there hope for general contification? So that things like
>
> (defun my-even? (x)
>   (cl-labels ((even? (x) (or (= x 0) (odd? (1- x))))
>               (odd?  (x) (or (= x 1) (even? (1- x)))))
>     (even? x)))
>
> are translated to a bunch of gotos and no lambdas.

I have no plans to go there in the foreseeable future, but that
shouldn't stop anyone else.

I think an intermediate step would be to do it for code like

    (defun my-even? (x)
      (cl-labels ((even? (x)
                    (let ((odd? (lambda (x) (or (= x 1) (even? (1- x))))))
                      (or (= x 0) (odd? (1- x))))))
        (even? x)))

but even that requires a fair bit more work than what I've just done,
I think.


        Stefan

Re: named-let

[Tomas Hlavaty]

On Sat 09 Jan 2021 at 11:44, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> Is TCO always used (like in Scheme) or in which cases is it used or not used?
>
> It's basically never used.  It's only applied for the particular case of
> tail recursive calls to functions defined by `cl-labels` and only for
> those calls that are "self-recursive" (i.e. come from within the code of
> that function).

I see.  That's already good step forward.  Thank you!

Re: named-let

[Zhu Zihao]

[-- Attachment #1: Type: text/plain, Size: 516 bytes --]


Tomas Hlavaty writes:

>> But with the recent tail-call optimization I installed into `master`,
>> the above `my-length` now works without eating up stack space.
>
> That's great news.
>
> Is TCO always used (like in Scheme) or in which cases is it used or not
> used?  Is it possible to turn it on or off?

I think the advice mechanism prevent us to do optimization like TCO and
auto inlining.

-- 
Retrieve my PGP public key:

  gpg --recv-keys D47A9C8B2AE3905B563D9135BE42B352A9F6821F

Zihao

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 255 bytes --]

Re: named-let

[Tomas Hlavaty]

On Mon 11 Jan 2021 at 02:49, Zhu Zihao <all_but_last@163.com> wrote:
> I think the advice mechanism prevent us to do optimization like TCO and
> auto inlining.

TCO for cl-labels is great already.

As for inlining, is there a way to specify that a function should be
inline/notinline?

Re: named-let

[Stefan Monnier]

Tomas Hlavaty [2021-01-11 23:27:38] wrote:
> On Mon 11 Jan 2021 at 02:49, Zhu Zihao <all_but_last@163.com> wrote:
>> I think the advice mechanism prevent us to do optimization like TCO and
>> auto inlining.

Actually, no.

We have `defsubst` to declare a function as inlinable (which implies
that things like the advice mechanism won't work reliably on it).
And we can also use approaches like "inline, together with a check that
the function was not advised" for functions which have not been
officially declared as inlinable (such checks are already used in the
native-comp code, IIRC, tho just to use "fast call" rather than do
inlining).

As for TCO, the last time this came up the issue is rather that if we
want to have it, it needs to work for all implementations of ELisp,
whereas all the patches we ever received only addressed the case of
byte-compiled code.

With the advent of the native-compiler, "all implementations" is even
harder to reach, since it means, interpreter, byte-code, and native code.


        Stefan

Re: named-let

[Tomas Hlavaty]

On Mon 11 Jan 2021 at 17:36, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> We have `defsubst` to declare a function as inlinable

How does one find such information?

> With the advent of the native-compiler, "all implementations" is even
> harder to reach, since it means, interpreter, byte-code, and native
> code.

How is it controlled if something is interpreted, byte-compiled or
native-compiled?

Re: named-let

[Andrea Corallo via Emacs development discussions.]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> With the advent of the native-compiler, "all implementations" is even
> harder to reach, since it means, interpreter, byte-code, and native code.

Well as I mentioned the native compiler is already capable of that if
asked, but in general whichever optimization is done by the
byte-compiler is picked by the native compiler cause currently the
compilation input is LAP.  So I'm not really sure this is adding much
complexity from this POV.

As a side note I'd be surprised if interpreters in CL implementation are
supporting TRE, I guess the interpreter is typically used only for debug
or bootstrap therefore should be not very important.  Am I wrong?

  Andrea

Re: named-let

[Stefan Monnier]

>> With the advent of the native-compiler, "all implementations" is even
>> harder to reach, since it means, interpreter, byte-code, and native code.
> Well as I mentioned the native compiler is already capable of that if
> asked, but in general whichever optimization is done by the
> byte-compiler is picked by the native compiler cause currently the
> compilation input is LAP.  So I'm not really sure this is adding much
> complexity from this POV.

All the patches I've seen so far do it in the bytecode interpreter,
without changing the bytecode itself.

Note that it also depends on what we mean by TCO.
To me, the "real TCO" is like what Scheme does (so it's not limited to
recursive functions).  I don't know how easy it is to implement for
native-comp.  Maybe GCC magically does it for us?

[ TCO has also undesirable interactions with debugging/tracing, but
  I think that would be a secondary concern which should be
  manageable somehow.  ]

> As a side note I'd be surprised if interpreters in CL implementation are
> supporting TRE, I guess the interpreter is typically used only for debug
> or bootstrap therefore should be not very important.  Am I wrong?

I wouldn't know.  But at least for ELisp , it was perceived that
the plain interpreter is important enough that if it doesn't support TCO
then we can't write code which relies on TCO, in which case implementing
TCO in the bytecode interpreter is not very useful.

[ That's part of the reason why I implemented this limited TCO as
  a macro: it works the same for bytecode as for any other mode of
  execution so it can really be considered part of the guaranteed
  semantics rather than a mere optimization.  ]


-- Stefan

Re: named-let

[Andrea Corallo via Emacs development discussions.]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>> With the advent of the native-compiler, "all implementations" is even
>>> harder to reach, since it means, interpreter, byte-code, and native code.
>> Well as I mentioned the native compiler is already capable of that if
>> asked, but in general whichever optimization is done by the
>> byte-compiler is picked by the native compiler cause currently the
>> compilation input is LAP.  So I'm not really sure this is adding much
>> complexity from this POV.
>
> All the patches I've seen so far do it in the bytecode interpreter,
> without changing the bytecode itself.

Ah okay, as not said, indeed it should use a goto in bytecode.

> Note that it also depends on what we mean by TCO.
> To me, the "real TCO" is like what Scheme does (so it's not limited to
> recursive functions).  I don't know how easy it is to implement for
> native-comp.  Maybe GCC magically does it for us?

Nope, AFAIU it does it, but not for us (ATM) :)

> [ TCO has also undesirable interactions with debugging/tracing, but
>   I think that would be a secondary concern which should be
>   manageable somehow.  ]

It's also a change in semantic as one must assume that `bar' is not
redefining `foo'.

(defun foo ()
  (bar)
  (foo))

Indeed this does not apply for `named-let' where the scope is lexical
and so you could do the magic :)

>> As a side note I'd be surprised if interpreters in CL implementation are
>> supporting TRE, I guess the interpreter is typically used only for debug
>> or bootstrap therefore should be not very important.  Am I wrong?
>
> I wouldn't know.  But at least for ELisp , it was perceived that
> the plain interpreter is important enough that if it doesn't support TCO
> then we can't write code which relies on TCO, in which case implementing
> TCO in the bytecode interpreter is not very useful.
>
> [ That's part of the reason why I implemented this limited TCO as
>   a macro: it works the same for bytecode as for any other mode of
>   execution so it can really be considered part of the guaranteed
>   semantics rather than a mere optimization.  ]

I see.

Thanks

  Andrea

Re: named-let

[Stefan Monnier]

>> [ TCO has also undesirable interactions with debugging/tracing, but
>>   I think that would be a secondary concern which should be
>>   manageable somehow.  ]
>
> It's also a change in semantic as one must assume that `bar' is not
> redefining `foo'.
>
> (defun foo ()
>   (bar)
>   (foo))

I think there's a bit of confusion: you can have TCO without having to
pay any attention to whether `bar` changes `foo`.  True TCO will also
avoid eating up stack space when you have code like

    (defun foo (x)
      (baz (1+ x)))

or

    (defun foo (x)
      (funcall (if (something) #'bar #'foo) (1+ x)))

or

    (defun foo (x)
      (let ((k (lambda (y) (foo (1+ x)))))
        (k 5)))

or ... and that doesn't depend on analyzing the code at all.

IOW, it shouldn't matter whether it's a recursive call or whether it's
a call to "self": all calls in tail position would conceptually pop
their stack frame before jumping to the destination function.


        Stefan

Re: named-let

[Andrea Corallo via Emacs development discussions.]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>> [ TCO has also undesirable interactions with debugging/tracing, but
>>>   I think that would be a secondary concern which should be
>>>   manageable somehow.  ]
>>
>> It's also a change in semantic as one must assume that `bar' is not
>> redefining `foo'.
>>
>> (defun foo ()
>>   (bar)
>>   (foo))
>
> I think there's a bit of confusion: you can have TCO without having to
> pay any attention to whether `bar` changes `foo`.  True TCO will also
> avoid eating up stack space when you have code like

Yes, I was discussing Tail Recursion Eliminination (or self TCO).

Actually I was thinking one could even check if `foo' was redefined
before performing the TRE sequence (well I guess that's what the
byteinterpreter patches you've mentioned did), in this case we could
have it also at speed 2.

As a side note I think we could have full TCO in Emacs, but at the cost
of a relatively invasive patch and a some (probably small but hard
to quantify a priori) performance regression.  Not sure it is
sufficiently important to justify that.

  Andrea

Re: named-let

[Stefan Monnier]

> As a side note I think we could have full TCO in Emacs, but at the cost
> of a relatively invasive patch and a some (probably small but hard
> to quantify a priori) performance regression.  Not sure it is
> sufficiently important to justify that.

That's the question, indeed.
Also, I have the impression that "full TCO" could be difficult if we
consider the mixed case where a compiled function calls an interpreted
function and vice-versa.


        Stefan

Re: named-let

[Andrea Corallo via Emacs development discussions.]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> As a side note I think we could have full TCO in Emacs, but at the cost
>> of a relatively invasive patch and a some (probably small but hard
>> to quantify a priori) performance regression.  Not sure it is
>> sufficiently important to justify that.
>
> That's the question, indeed.
> Also, I have the impression that "full TCO" could be difficult if we
> consider the mixed case where a compiled function calls an interpreted
> function and vice-versa.

I might be wrong but I think should be possible to harmonize both sides
with not much problems (other than the mentioned enormous codebase
diff).

But anyway, I've no time to prove I'm right or wrong on this :/

  Andrea

Re: named-let

[Helmut Eller]

On Mon, Jan 11 2021, Stefan Monnier wrote:

> I don't know how easy it is to implement for
> native-comp.  Maybe GCC magically does it for us?

GCC can optimize sibling-calls; that's a class of tail-calls where the
argument count of the callee and caller are the same.  Other tail-calls
are difficult to optimize, because most systems prescribe a the
caller-pops-arguments calling convention (including the varargs stuff).

Last time I checked LLVM, doesn't even optimize sibling-calls.

Helmut

Re: named-let

[Zhu Zihao]

[-- Attachment #1: Type: text/plain, Size: 1111 bytes --]


Stefan Monnier writes:

> And we can also use approaches like "inline, together with a check that
> the function was not advised" for functions which have not been
> officially declared as inlinable (such checks are already used in the
> native-comp code, IIRC, tho just to use "fast call" rather than do
> inlining).

I'm not sure I understand it. Given code like

(defun add1 (b)
  (+ b 1))

(defun test ()
  (advice-add (intern "add1") :after (lambda (&rest _)
                                       (message "Whoa!")))
  (+ 10 (add1 20)))

We want to inline (add1 20) so the program becomes (+ 10 (+ 1 20)). But
advice can happened at run time. For example, I run advice-add in the
body of function "test" before calling "add1". What's more, that call to
advice-add may hidden in another function(And that function may also be
adviced) and make the program very complicated and hard to determine in
compile time. Would native-comp break the semantic of that program or not?

-- 
Retrieve my PGP public key:

  gpg --recv-keys D47A9C8B2AE3905B563D9135BE42B352A9F6821F

Zihao

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 255 bytes --]

Re: named-let

[Stefan Monnier]

>> And we can also use approaches like "inline, together with a check that
>> the function was not advised" for functions which have not been
>> officially declared as inlinable (such checks are already used in the
>> native-comp code, IIRC, tho just to use "fast call" rather than do
>> inlining).
>
> I'm not sure I understand it. Given code like
>
> (defun add1 (b)
>   (+ b 1))
>
> (defun test ()
>   (advice-add (intern "add1") :after (lambda (&rest _)
>                                        (message "Whoa!")))
>   (+ 10 (add1 20)))
>
> We want to inline (add1 20) so the program becomes (+ 10 (+ 1 20)). But
> advice can happened at run time.

The inlining would basically lead to the following code:

    (+ 10 (if (eq (symbol-function 'add1) <thethingweexpect>) (+ 20 1)
              (add1 20)))

which the compiler might be able to optimize to something equivalent to:

    (if (eq (symbol-function 'add1) <thethingweexpect>) 31
        (+ 10 (add1 20)))


-- Stefan

Re: named-let

[Andrea Corallo via Emacs development discussions.]

Tomas Hlavaty <tom@logand.com> writes:

> TCO for cl-labels is great already.

As a side note, the native compiler supports that also for regular
functions when compiling at speed 3 (not much tested tho :)

  Andrea

Re: named-let

[Tomas Hlavaty]

On Mon 11 Jan 2021 at 22:40, Andrea Corallo <akrl@sdf.org> wrote:
> As a side note, the native compiler supports that also for regular
> functions when compiling at speed 3 (not much tested tho :)

Which Emacs version has native compiler available?

How does one specify speed 3?  Is that like in Common Lisp (declare
(optimize (speed 3)))?

Re: named-let

[Andrea Corallo via Emacs development discussions.]

Tomas Hlavaty <tom@logand.com> writes:

> On Mon 11 Jan 2021 at 22:40, Andrea Corallo <akrl@sdf.org> wrote:
>> As a side note, the native compiler supports that also for regular
>> functions when compiling at speed 3 (not much tested tho :)
>
> Which Emacs version has native compiler available?

That's a feature branch in feature/native-comp

> How does one specify speed 3?  Is that like in Common Lisp (declare
> (optimize (speed 3)))?

ATM one can use (declare (speed 3)) or (declare (cl-optimize (speed 3)))
or bind the special variable `comp-speed' to 3 during compilation.

  Andrea

Re: named-let

[Tomas Hlavaty]

ok, thanks for the info

Re: named-let

[Stefan Monnier]

> The recent discussion around loops motivated me to look a bit further
> into named-let.  It's actually easy to define:

I now added this `named-let` to `subr-x.el`.
Along with it, I installed two additional optimizations to the byte-code
optimizer.  With those optimization, the byte code generated from

    (defun length-named (xs)
      (named-let recurse ((xs xs) (l 0))
        (if xs (recurse (cdr xs) (1+ l)) l)))

is about 33% slower than that generated from:

    (defun length-fast (xs)
      (let ((l 0))
        (while xs (setq l (1+ l)) (setq xs (cdr xs)))
        l))

(for reference, without the tail-call optimization, `length-named` was
about 300% (i.e. 4x) slower, and with TCO but without the recent extra
tweaks, it was about 70% slower; and the native `length` is 15x faster).

The remaining 33% seem harder to reach, tho.  They're 3 extra
instructions: 2 `stack-ref` instructions to copy the two parameters at
the beginning of the loop body, and one `discardN` instruction to drop
those 2 parameters at the end of the loop body.

I guess we can live with those 33% for now: this is a fairly
pathological test where the loop's body does particularly little, so the
loop overhead is magnified.


        Stefan