[Bug-kawa] [bug #47829] Over eager tail call optimization

[Edward McDowell]

URL:
  <http://savannah.gnu.org/bugs/?47829>

                 Summary: Over eager tail call optimization
                 Project: Kawa
            Submitted by: emcdowell48
            Submitted on: Mon 02 May 2016 05:02:06 PM GMT
                Category: Code generation
                Severity: 3 - Normal
              Item Group: Unexpected result
                  Status: None
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

When run with the --full-tailcalls switch, kawa-2.1 misses
required recursive calls in applications that make multiple
recursive calls to produce printed side effects.  True
recursion in required in these applications.  I present
two examples: the Towers of Hanoi puzzle and inorder binary
tree traversal.

In both cases, the problem is resolved by adding an explicit
return value of '() following the second recursive call,
which ensures that the call is not in tail position.

H:\user\kawa>type hanoi.scm

(define (print-move disk from dest)
  (display "Move disk ")
  (display disk)
  (display " from peg ")
  (display from)
  (display " to peg ")
  (display dest)
  (display ".")
  (newline))

(define (hanoi height from dest via)
  (if (zero? height) '()
    (let ((newh (- height 1)))
      (hanoi newh from via dest)
      (print-move height from dest)
      (hanoi newh via dest from)
      )))

(hanoi 3 "A" "B" "C")

H:\user\kawa>java -cp kawa.jar kawa.repl --full-tailcalls -f hanoi.scm
Move disk 1 from peg A to peg B.
Move disk 2 from peg A to peg C.
Move disk 3 from peg A to peg B.
Move disk 1 from peg C to peg A.
Move disk 2 from peg C to peg B.
Move disk 1 from peg A to peg B.

The third line of the correct output is missed:
Move disk 1 from peg A to peg B.
Move disk 2 from peg A to peg C.
Move disk 1 from peg B to peg C.
Move disk 3 from peg A to peg B.
Move disk 1 from peg C to peg A.
Move disk 2 from peg C to peg B.
Move disk 1 from peg A to peg B.

H:\user\kawa>type tree.scm

(define (inorder tree)
  (if (null? tree) '()
    (let ((left (car tree))
          (value (cadr tree))
          (right (caddr tree)))
      (inorder left)
      (display value)
      (newline)
      (inorder right))))

(inorder '(((() 1 ()) 2 (() 3 ())) 4 (() 5 ())))

H:\user\kawa>java -cp kawa.jar kawa.repl --full-tailcalls -f tree.scm
1
2
4
5

The third line of the correct output is missed:
1
2
3
4
5

The examples above were run using Kawa-2.1 on Java 1.8.0_92
on Windows 8.  Both run successfully on other Scheme implementations,
including MIT-Scheme, Racket, Gambit, Chicken Scheme and Larceny.





    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?47829>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/