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.
|