2015-12-14

Or, and-let* and tail position

It's about I was stupid enough not to think where actually tail position is.

Let's see the following expression:
(or (returns-false)
    (returns-true))
The first returns-false wouldn't be tail position unless implementation does some magic. It's easy to explain why not only it's explicitly written in R7RS. If you write or with macro, the it'd look like this:
(define-syntax or
  (syntax-rules ()
    ((_ expr) expr)
    ((_ expr expr* ...)
     (let ((t expr)) ;; this is why it's not tail position
       (if t t (or expr* ...))))))
I'm not that stupid just in case you'd think like that.

Now, there's a SRFI which defines and-let*. Using this, you can write nested and and let very simply like this:
(and-let* ((a (returns-something))
           ( (symbol? a) )
           (b (returns-other-thing))
           ( (string? b) ))
  (do-something a b))
#|
would be expanded like this:
(let ((a (returns-something)))
  (and a
       (symbol? a)
       (let ((b (returns-other-thing)))
         (and b
              (string? b)
              (do-something a b))))) ;; this is tail position
|#
You'd probably know what I want to say. Yes, combination like this made me lost...
(or (and-let* (...) body ...)
    (other))
For some reason, I was thinking the last expression in the body would be tail position. Well, doesn't it look like it? And my defence, might make me look more stupid, is that the place where it happened was rather deeply nested (at least for me) and kinda long process. So I couldn't see or in a glance.

Although, it wouldn't hurt that much if you aren't doing recursion. You know what? Yes, I did... on the compiler. If you make a huge expression with internal define, then stack overflow happened because of this mistake. It can happen when the internal define is more than 100 or so (if not, it just consume large stack). Who would write more than 100 internal define? Me, of course.

Don't get me wrong, I don't write by hand (well, rarely maybe) but with macro. Recently, I'm writing SQL parser with (packrat) library and the packrat-parser macro converts the BNF looks like definition into bunch of internal define expressions. If you have never seen how BNF of SQL looks like, then just look this. Even though, it's not completed yet however the parser definition is already close to 2000 LoC. Haven't counted the number of internal definition but at least more than 100. If there's such numbers of internal definition, then stack overflow would happen.

When I fix this problem on compiler, I would expect that it'd also improve the performance. Because of the occupation of the stack area, it'd have impacted some GC performance. The result was not that much. The simple benchmark (just loading sitelib/text/sql/parser.scm) showed 300ms improvement from 7700ms. Well, it's more like an error range.

Anyway, this improvement, at least, save my sanity a bit.

No comments:

Post a Comment