summaryrefslogtreecommitdiff
path: root/doc/tutorial
diff options
context:
space:
mode:
authorNeil Jerram <neil@ossau.uklinux.net>2002-07-16 20:57:34 +0000
committerNeil Jerram <neil@ossau.uklinux.net>2002-07-16 20:57:34 +0000
commitc5d130619390fc3fd815011e69abe32fa8e13092 (patch)
tree2bcbbd4a33f0fc3a1c44b9c90ca52a3e2ec428d7 /doc/tutorial
parent3063e30a6dca1e0abc0b40d3c62f755a9155fccd (diff)
downloadguile-c5d130619390fc3fd815011e69abe32fa8e13092.tar.gz
Apply patch from M. Luedde on use of tail recursion to avoid stack overflow
Diffstat (limited to 'doc/tutorial')
-rw-r--r--doc/tutorial/ChangeLog10
-rw-r--r--doc/tutorial/guile-tut.texi60
2 files changed, 58 insertions, 12 deletions
diff --git a/doc/tutorial/ChangeLog b/doc/tutorial/ChangeLog
index eea1de221..b24d6004f 100644
--- a/doc/tutorial/ChangeLog
+++ b/doc/tutorial/ChangeLog
@@ -1,3 +1,13 @@
+2002-07-16 Neil Jerram <neil@ossau.uklinux.net>
+
+ * guile-tut.texi (Jump Start): Apply patch from M. Luedde on use
+ of tail recursion to avoid stack overflow (with minor editing).
+
+2002-07-14 Neil Jerram <neil@ossau.uklinux.net>
+
+ * guile-tut.texi (Jump Start):
+ (Jump Start):
+
2001-11-18 Neil Jerram <neil@ossau.uklinux.net>
* guile-tut.texi (History of Guile and its motivations): Update
diff --git a/doc/tutorial/guile-tut.texi b/doc/tutorial/guile-tut.texi
index eb6345d86..e73f9b248 100644
--- a/doc/tutorial/guile-tut.texi
+++ b/doc/tutorial/guile-tut.texi
@@ -99,6 +99,7 @@ by the author.
* Type Index::
@end menu
+
@node Jump Start
@chapter Jump Start
@@ -106,8 +107,8 @@ by the author.
Before giving an overview of Guile, I present some simple commands and
programs that you can type to get going immediately.
-Start by invoking the Guile interpreter (usually you do this by just
-typing @code{guile}). Then type (or paste) the following expressions at
+Start by invoking the Guile interpreter. Usually you do this by just
+typing @code{guile}. Then type (or paste) the following expressions at
the prompt; the interpreter's response is preceded (in this manual) by
@result{}.
@@ -118,11 +119,26 @@ the prompt; the interpreter's response is preceded (in this manual) by
(+ 20 35)
@result{} 55
(define (recursive-factorial n)
- (if (= n 0)
- 1
- (* n (recursive-factorial (- n 1)))))
+ (if (zero? n)
+ 1
+ (* n (recursive-factorial (- n 1)))))
(recursive-factorial 5)
@result{} 120
+(quit)
+@end lisp
+
+In this example we did some simple arithmetic @code{(+ 20 35)} and got
+the answer @code{55}. Then we coded the classic (and rather wasteful)
+factorial algorithm and computed the factorial of @code{55}. Finally we
+quit with @code{(quit)}.
+
+@cindex bignumbers
+We can find out about some of Scheme's nice features by asking for the
+factorial of some big number, say @code{500}. On some systems the
+correct answer will be returned (I do not indicate calling and leaving
+the guile session anymore).
+
+@lisp
(recursive-factorial 500)
@result{} 1220136825991110068701238785423046926253574342803192842192413588
3858453731538819976054964475022032818630136164771482035841633787
@@ -142,15 +158,35 @@ the prompt; the interpreter's response is preceded (in this manual) by
3896881639487469658817504506926365338175055478128640000000000000
0000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000
-<control-D>
@end lisp
-In this example we did some simple arithmetic @code{(+ 20 35)} and got
-the answer @code{55}. Then we coded the classic (and rather wasteful)
-factorial algorithm, and got a glimpse of Scheme's nice
-@emph{bignumbers} by asking for the factorial of 500. Then we quit
-with @code{(quit)}.
-@cindex bignumbers
+The result is an example of Scheme's @emph{bignumbers}. However, there
+are operating environments that provide (by default) too little stack
+space. They will instead produce an error message like this:
+
+@lisp
+(recursive-factorial 500)
+@print{}
+ERROR: Stack overflow
+ABORT: (stack-overflow)
+@end lisp
+
+Rather than enlarging the system's stack, we can implement the algorithm
+such that it does not consume increasing stack space. This is called a
+@emph{tail recursive} implementation. The following definition is tail
+recursive and so should work on all systems.
+
+@lisp
+(define (tail-recursive-factorial n)
+ (define (loop k l)
+ (if (zero? k) l
+ (loop (- k 1) (* k l))))
+ (loop n 1))
+
+(tail-recursive-factorial 500)
+@result{} 1220136825991110068701238785423046926253574342803192842192413588
+ ;; ... skipped
+@end lisp
This is the most basic use of Guile: a simple Scheme interpreter. In
the rest of this tutorial I will show you how Guile has many facets: it