8 ms·

How does it change the semantics of Scheme? It avoids blowing the stack for sure, but the stack size isn’t part of the semantics of Scheme. If you imagine a com

by OskarS 6y ago

How does it change the semantics of Scheme? It avoids blowing the stack for sure, but the stack size isn’t part of the semantics of Scheme. If you imagine a computer with arbitrary amounts of memory, then the language behaves identically with or without tail call elimination, right? The only difference is performance and memory usage, but the meaning of programs is still the same.

rcxdude 6y ago
it changes it from 'all functions can recurse only up to some limit' to 'functions with tail calls can recurse indefinitely' (i.e. you can write an infinite loop recursively). It's not just a performance improvement but a change in capability.
- bachmeier 6y ago
  Aren't you adding some assumptions about the implementation in your comment? Common Lisp doesn't require TCO, but it doesn't forbid it either, and SBCL chooses to do it. Your first sentence would be incorrect for a Common Lisp program someone executes with SBCL.
  - masklinn 6y ago
    > Aren't you adding some assumptions about the implementation in your comment? You'd have a point if they were talking about implementation semantics, but they're talking about language semantics. A Scheme program can assume TCE, a CL program can not, an SBCL program can.
    - bachmeier 6y ago
      It's not clear to me that the person I replied to was talking about language semantics. The phrasing of that comment would have taken the form "may not" or "can't assume", but instead asserted that you can write some code that's guaranteed to run differently, which is implementation semantics.
      - sokoloff 6y ago
        It says “semantics of Scheme” directly (and IMO unambiguously) upthread. What would that more likely be than the language?
    - travv0 6y ago
      > an SBCL program can. SBCL will only perform TCO at specific optimization levels, so you can't even rely on it in SBCL.
  - rcxdude 6y ago
    Well, then the statement 'functions many only recurse up to some limit' applies to Common Lisp as specified but not to this implementation of it. This isn't particularly unusual, since language implementations often have capabilities which aren't part of the specifications (see the many extensions to C, for example. e.g. in standard C you can't assume that type punning using a union will be defined, but almost all implementations explicitly allow for it). These are differences in the semantics of the language (namely in what is and isn't allowed), not just optimisations.
  - mcguire 6y ago
    That depends on whether you are claiming your code is written in Common Lisp (the language) or for SBCL (the implementation). The former will run on other implementations.
- ragnese 6y ago
  Yes. You generally just should not write a recursive function in a language without TCO/TCE.
  - jdmichal 6y ago
    Recursion is nothing but a loop with a stack. So yes, can certainly rewrite things that way, but all you're doing is trading the stack for a stack structure on the heap.
chrisseaton 6y ago
Can you observe the difference as a programmer? Through things like the stack-trace? Then it's not an optimization.
- OskarS 6y ago
  So you’re saying inlining doesn’t count as an optimization, then?
  - chrisseaton 6y ago
    No, that doesn't follow. Inlining doesn't change what a call stack looks like - the call stack frames are still there, yes possibly just a metadata annotations on real call stack frames and recovered when needed. With tail calls, the call stack frames are completely gone, and cannot be recovered. Try this thought experiment - can you implement tail calls in Java and meet the same language specification? I think you cannot. Therefore it is not an optimisation. If you can please email me how and I will implement it and you can publish the paper and get the glory!
    - MaxBarraclough 6y ago
      > can you implement tail calls in Java and meet the same language specification? I think you cannot. Is this because Java exposes stack traces in a way most languages don't?
      - chrisseaton 6y ago
        That's one reason - there are also a few more minor technical places in the spec where the depth of the call stack is observable in semantics such as I think the security manager. But I don't think it's unusual for a language to expose call stacks? Ruby, Python, C#, etc all do it.
        Someone 6y ago
        I think a Java implementation could do tail calls, but it would have to create a fake stack trace when needed. (I haven’t looked, but I would expect modern Java implementations already make up quite a bit of the stack trace only when it is needed, for example when inlining calls) And, traditionally, it _is_ unusual to expose call stacks to calling programs for Algol-style languages (implementations typically dumped a call stack and might add a way for a program to walk its stack, but that would be implementation-dependent) Without exceptions or a repl, where would you use them, other than in a crash dump?
joppy 6y ago
The scheme R5RS [1] (essentially, an edition of the language standard) defines in section 3.5 what it means for an implementation to be “Properly tail recursive”: it must support an unbounded number of active (yet-to-return) tail calls. I think “proper tail call” is a good terminology for a tail call that replaces the callers stack frame (or some equivalent, depending on implementation). It doesn’t necessarily change the semantics, but it does change what kind of programs are sure to crash your machine, and what kind are going to run fast, which is also an important property of programming languages. [1]: https://schemers.org/Documents/Standards/R5RS/ https://schemers.org/Documents/Standards/R5RS/
- OskarS 6y ago
  > It doesn’t necessarily change the semantics, but it does change what kind of programs are sure to crash your machine, and what kind are going to run fast, which is also an important property of programming languages. Yeah, this is exactly what I meant. The semantics of the language are the same regardless (i.e. the meanings of programs doesn’t change), but in practice it makes a huge difference.
mumblemumble 6y ago
My sense is that the only unique thing about Scheme here is the fact that it's specified in the standard. That means that developers are going to develop software that expects to be able to write tail-recrusive code without fear of blowing the stack. Other language standards keep this from affecting the semantics of the language by simply leaving it out of the semantics of the language. When the expected behavior is undefined, the implementors can do anything they want without, strictly speaking, affecting the semantics of the language.
- beagle3 6y ago
  Some languages (Python, Tcl, R and possibly others) expose the stack as part of the language/standard-library, and thus an implementation that DOES do TCE cannot be compatible. In python, it's mostly visible through exception objects. In Tcl and R, it's in common use because it is standard practice to do things in your caller's scope instead of your own. In C++ (and any language with destructors), many routines are invisibly not TCEable because the language semantics require the destructor to run after the tail call returns - which means that a change to a different part of the code determines if a specific function is TCEable or not. So, despite your claim being technically true, it is in practice often informally specified by the language or standard library.

by OskarS 6y ago

rcxdude 6y ago

it changes it from 'all functions can recurse only up to some limit' to 'functions with tail calls can recurse indefinitely' (i.e. you can write an infinite loop recursively). It's not just a performance improvement but a change in capability.

bachmeier 6y ago
Aren't you adding some assumptions about the implementation in your comment? Common Lisp doesn't require TCO, but it doesn't forbid it either, and SBCL chooses to do it. Your first sentence would be incorrect for a Common Lisp program someone executes with SBCL.
- masklinn 6y ago
  > Aren't you adding some assumptions about the implementation in your comment? You'd have a point if they were talking about implementation semantics, but they're talking about language semantics. A Scheme program can assume TCE, a CL program can not, an SBCL program can.
  - bachmeier 6y ago
    It's not clear to me that the person I replied to was talking about language semantics. The phrasing of that comment would have taken the form "may not" or "can't assume", but instead asserted that you can write some code that's guaranteed to run differently, which is implementation semantics.
    - sokoloff 6y ago
      It says “semantics of Scheme” directly (and IMO unambiguously) upthread. What would that more likely be than the language?
  - travv0 6y ago
    > an SBCL program can. SBCL will only perform TCO at specific optimization levels, so you can't even rely on it in SBCL.
- rcxdude 6y ago
  Well, then the statement 'functions many only recurse up to some limit' applies to Common Lisp as specified but not to this implementation of it. This isn't particularly unusual, since language implementations often have capabilities which aren't part of the specifications (see the many extensions to C, for example. e.g. in standard C you can't assume that type punning using a union will be defined, but almost all implementations explicitly allow for it). These are differences in the semantics of the language (namely in what is and isn't allowed), not just optimisations.
- mcguire 6y ago
  That depends on whether you are claiming your code is written in Common Lisp (the language) or for SBCL (the implementation). The former will run on other implementations.
ragnese 6y ago
Yes. You generally just should not write a recursive function in a language without TCO/TCE.
- jdmichal 6y ago
  Recursion is nothing but a loop with a stack. So yes, can certainly rewrite things that way, but all you're doing is trading the stack for a stack structure on the heap.

chrisseaton 6y ago

Can you observe the difference as a programmer? Through things like the stack-trace? Then it's not an optimization.

OskarS 6y ago
So you’re saying inlining doesn’t count as an optimization, then?
- chrisseaton 6y ago
  No, that doesn't follow. Inlining doesn't change what a call stack looks like - the call stack frames are still there, yes possibly just a metadata annotations on real call stack frames and recovered when needed. With tail calls, the call stack frames are completely gone, and cannot be recovered. Try this thought experiment - can you implement tail calls in Java and meet the same language specification? I think you cannot. Therefore it is not an optimisation. If you can please email me how and I will implement it and you can publish the paper and get the glory!
  - MaxBarraclough 6y ago
    > can you implement tail calls in Java and meet the same language specification? I think you cannot. Is this because Java exposes stack traces in a way most languages don't?
    - chrisseaton 6y ago
      That's one reason - there are also a few more minor technical places in the spec where the depth of the call stack is observable in semantics such as I think the security manager. But I don't think it's unusual for a language to expose call stacks? Ruby, Python, C#, etc all do it.
      - Someone 6y ago
        I think a Java implementation could do tail calls, but it would have to create a fake stack trace when needed. (I haven’t looked, but I would expect modern Java implementations already make up quite a bit of the stack trace only when it is needed, for example when inlining calls) And, traditionally, it _is_ unusual to expose call stacks to calling programs for Algol-style languages (implementations typically dumped a call stack and might add a way for a program to walk its stack, but that would be implementation-dependent) Without exceptions or a repl, where would you use them, other than in a crash dump?

joppy 6y ago

The scheme R5RS [1] (essentially, an edition of the language standard) defines in section 3.5 what it means for an implementation to be “Properly tail recursive”: it must support an unbounded number of active (yet-to-return) tail calls. I think “proper tail call” is a good terminology for a tail call that replaces the callers stack frame (or some equivalent, depending on implementation). It doesn’t necessarily change the semantics, but it does change what kind of programs are sure to crash your machine, and what kind are going to run fast, which is also an important property of programming languages. [1]: https://schemers.org/Documents/Standards/R5RS/ https://schemers.org/Documents/Standards/R5RS/

OskarS 6y ago
> It doesn’t necessarily change the semantics, but it does change what kind of programs are sure to crash your machine, and what kind are going to run fast, which is also an important property of programming languages. Yeah, this is exactly what I meant. The semantics of the language are the same regardless (i.e. the meanings of programs doesn’t change), but in practice it makes a huge difference.

mumblemumble 6y ago

My sense is that the only unique thing about Scheme here is the fact that it's specified in the standard. That means that developers are going to develop software that expects to be able to write tail-recrusive code without fear of blowing the stack. Other language standards keep this from affecting the semantics of the language by simply leaving it out of the semantics of the language. When the expected behavior is undefined, the implementors can do anything they want without, strictly speaking, affecting the semantics of the language.

beagle3 6y ago
Some languages (Python, Tcl, R and possibly others) expose the stack as part of the language/standard-library, and thus an implementation that DOES do TCE cannot be compatible. In python, it's mostly visible through exception objects. In Tcl and R, it's in common use because it is standard practice to do things in your caller's scope instead of your own. In C++ (and any language with destructors), many routines are invisibly not TCEable because the language semantics require the destructor to run after the tail call returns - which means that a change to a different part of the code determines if a specific function is TCEable or not. So, despite your claim being technically true, it is in practice often informally specified by the language or standard library.