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

 
 

bug #47829: Over eager tail call optimization

Submitted by:  Edward McDowell <emcdowell48>
Submitted on:  Mon 02 May 2016 05:02:06 PM UTC  
 
Category: Code generationSeverity: 3 - Normal
Item Group: Unexpected resultStatus: Works For Me
Privacy: PublicAssigned to: Per Bothner <bothner>
Open/Closed: Open

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

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>
Project AdministratorIn charge of this item.
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>

 

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

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

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

     

     

    Follow 2 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 02 May 2016 05:10:04 PM UTCbothnerStatusNone=>Works For Me
      Assigned toNone=>bothner

    Back to the top


    Powered by Savane 3.1-cleanup1