4 ms·

> I'm just wondering what is the exact scenario, involving what structure. > Was: Re: bug#30626 (seq-doseq (_ (stream-range 1 1000000)) nil)

by sebcat 9y ago

kazinator 9y ago
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=+bug%2330626 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=+bug%2330626 Looks like an X Y problem here. Let's fix the garbage collector (X) because of some badly implemented lazy processing (Y) where the real issue is. I don't believe anyone has a filesystem that can't be traversed by a lazy data structure in Lisp, with a recursive GC, in 8 megs of stack. (Unless, say, the traversal is being fooled by cycles created by directory symlinks.)
- sebcat 9y ago
  One could argue that. One could also argue that it should be possible to collect any garbage successfully created.
  - kazinator 9y ago
    Nope; worse is better. It has to be recognized that a garbage collection scheme which can satisfy this idealist requirement has some disadvantages relative to one which doesn't. Should it also be possible to successfully read any well-formed S-expression that we can create in a text stream? Oops, don't use recursion in the reader, then.
    - jemfinch 9y ago
      It doesn't have disadvantages apart from the code to manually manage an explicit stack. The actual space used will be reduced. And yes, it should be possible to successfully read any well formed sexp that can be created in a text stream and held in memory. That's why quality parsers use an explicit stack as well. Recursion is a useful development tool in some cases, but when iterative algorithms fail because they use it, the implementations are buggy.
      - kazinator 9y ago
        You can hold a S-exp in memory such that you don't have anywhere near enough memory left to scan it with even your condensed explicit stack. > That's why quality parsers use an explicit stack as well. Observation: that rules out the entire description of the ANSI CL reader from being quality, haha.
      - olliej 9y ago
        I rewrote the JSC parser to be mostly iterative many years ago - for a “real” language making an iterative parser that is readable is incredibly challenging. Especially in something like js where an expression could actually contain a statement. The current state is “as iterative as is sanely understandable” and handles all real (and some insane) programs fine. I suspect similar is true for other production hand written parsers. Your alternative is table based parsers which can only reasonably be implemented with generators. The problem is that table based parsers are slower than hand rolled recursive descent parser by a fairl large margin, and general purpose generators (bison, yacc , etc) tend to have difficulty with the quirky syntax of large languages. Note there have been a number of papers over the years that demonstrated 2x perf improvements in yacc/bison by switching from indexed state transitions to computed go to, but even that leaves them slower than hand rolled.
        kazinator 9y ago
        > for a “real” language making an iterative parser that is readable is incredibly challenging. Not to mention if it is defined in terms of a character-classifying read-table which dispatches functions, which can be patched by the user program (as in Common Lisp).

> I'm just wondering what is the exact scenario, involving what structure. > Was: Re: bug#30626 (seq-doseq (_ (stream-range 1 1000000)) nil)

by sebcat 9y ago

> I'm just wondering what is the exact scenario, involving what structure. > Was: Re: bug#30626 (seq-doseq (_ (stream-range 1 1000000)) nil)

kazinator 9y ago

https://debbugs.gnu.org/cgi/bugreport.cgi?bug=+bug%2330626 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=+bug%2330626 Looks like an X Y problem here. Let's fix the garbage collector (X) because of some badly implemented lazy processing (Y) where the real issue is. I don't believe anyone has a filesystem that can't be traversed by a lazy data structure in Lisp, with a recursive GC, in 8 megs of stack. (Unless, say, the traversal is being fooled by cycles created by directory symlinks.)

sebcat 9y ago
One could argue that. One could also argue that it should be possible to collect any garbage successfully created.
- kazinator 9y ago
  Nope; worse is better. It has to be recognized that a garbage collection scheme which can satisfy this idealist requirement has some disadvantages relative to one which doesn't. Should it also be possible to successfully read any well-formed S-expression that we can create in a text stream? Oops, don't use recursion in the reader, then.
  - jemfinch 9y ago
    It doesn't have disadvantages apart from the code to manually manage an explicit stack. The actual space used will be reduced. And yes, it should be possible to successfully read any well formed sexp that can be created in a text stream and held in memory. That's why quality parsers use an explicit stack as well. Recursion is a useful development tool in some cases, but when iterative algorithms fail because they use it, the implementations are buggy.
    - kazinator 9y ago
      You can hold a S-exp in memory such that you don't have anywhere near enough memory left to scan it with even your condensed explicit stack. > That's why quality parsers use an explicit stack as well. Observation: that rules out the entire description of the ANSI CL reader from being quality, haha.
    - olliej 9y ago
      I rewrote the JSC parser to be mostly iterative many years ago - for a “real” language making an iterative parser that is readable is incredibly challenging. Especially in something like js where an expression could actually contain a statement. The current state is “as iterative as is sanely understandable” and handles all real (and some insane) programs fine. I suspect similar is true for other production hand written parsers. Your alternative is table based parsers which can only reasonably be implemented with generators. The problem is that table based parsers are slower than hand rolled recursive descent parser by a fairl large margin, and general purpose generators (bison, yacc , etc) tend to have difficulty with the quirky syntax of large languages. Note there have been a number of papers over the years that demonstrated 2x perf improvements in yacc/bison by switching from indexed state transitions to computed go to, but even that leaves them slower than hand rolled.
      - kazinator 9y ago
        > for a “real” language making an iterative parser that is readable is incredibly challenging. Not to mention if it is defined in terms of a character-classifying read-table which dispatches functions, which can be patched by the user program (as in Common Lisp).