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
Item Group:  Unexpected result Status:  Works For Me
Privacy:  Public Assigned to:  bothner
Open/Closed:  Open
* Mandatory Fields

Add a New Comment Rich Markup
   

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>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    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.

     

    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.13-758e.
    Corresponding source code