bugKawa - Bugs: bug #47829, Over eager tail call optimization

 
 

bug #47829: Over eager tail call optimization

Submitter:  Edward McDowell <emcdowell48>
Submitted:  Mon 02 May 2016 05:02:06 PM UTC
   
 
Category:  Code generation Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Unexpected result
Status:  Works For Me Privacy:  Public
Assigned to:  bothner Open/Closed:  Open
* Mandatory Fields

Post a Comment

Add a New Comment Rich Markup
   

Discussion

Mon 02 May 2016 05:10:04 PM UTC, comment #1: 

Looks like this is already fixed in the Subversion sources.
(I tested both trunk, and the "invoke" branch I've been working on.)

Could you verify that it works for you?

Per Bothner <bothner>
Group administrator
Mon 02 May 2016 05:02:06 PM UTC, original submission:  

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.

Edward McDowell <emcdowell48>

 

Attached Files

This item currently has no attached files.

(Note: upload size limit is set to 4.0MiB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

 

Dependencies

This item does not depend on any other items.

No items depend on this one.

 

Mail Notification Carbon-Copy List

Carbon-Copy List
  • -email is unavailable- added by bothner (Posted a comment)
  • -email is unavailable- added by emcdowell48 (Submitted the item)
  •  

    Votes

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

    History

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-05-02 bothner StatusNone Works For Me
        Assigned toNone bothner

    Back to the top

    Powered by Savane 3.16-598c.
    Corresponding source code