About tail call optimization (and the module system) ================================================================= In order to speak of Scheme performance one needs to write at least a few benchmarks. This is not completely trivial, for at least a couple of reasons. The first reason is shallow, but it may be baffling for beginners: since there is no ``for`` loop in Scheme, how are we supposed to write a benchmark, which is usually based on running many times the same instructions and measuring the total time spent? We will see in a moment that there is an easy solution to this question (use recursion). On the other hand, there is a second more serious question: since there is no fully portable way to write a library in Scheme, how can we write a benchmark library? There is no real answer, so we will restrict ourselves to R6RS-compliant Scheme implementations where there is a standard concept of library. There are no ``for`` loops in Scheme ------------------------------------------------------- The ``for`` loop is missing in Scheme as a primitive construct since it is useless in a language that guarantees tail call optimization. If you studied the concept of *tail call* at college you know what I am talking about; on the other hand, if you forgot it, or if you did study Physics like me, it is worth spending a couple of words on the subject. The ones who want to know more, may consult this `Wikipedia article`_. .. image:: Ouroboros.png The important point beyond the tail recursion concept is that it is always possibile to convert a ``for`` into a recursive function in *tail call* form, i.e. a recursive function returning a value or a call to itself. For instance, the Python loop:: # a loop printing 1 2 3 for i in range(1,4): print i, can be converted to a recursive function ``print_up_to_3``:: def print_up_to_3(i): if i == 4: return print i, return print_up_to_3(i+1) print_up_to_3(1) Here the last instruction of the function (the tail) is a call to itself, hence the name *tail call*. Tail call optimization is guaranteed by the Scheme language. Scheme compilers/interpreters are able to recognize recursive functions in tail call form and to convert them internally in ``for`` loops. As a consequence, the programmer has no need to write ``for`` loops directly: she can just use recursive function. Our example would look as follows in Scheme:: (define (print-up-to-3 i) (unless (= i 4) (display i) (display " ") (print-up-to-3 (+ i 1)))) (print-up-to-3 1) This works, but it is not really readable; to improve the situation Scheme provides a little syntactic sugar called *named let*:: (let loop ((i 1)) (unless (= i 4) (display i) (display " ") (loop (+ i 1)))) Traditionally the function in the *named let* construct is called ``loop`` to make clear to the programmer that we are emulating a ``for`` loop. In this example ``loop`` is exactly equivalent to ``print-up-to-3``. Let me point out two things before closing this paragraph: 1) there are other ``let`` forms, used to define local variables. The simplest one is ``let``:: > (let ((a 1) (b 2)) (+ a b)) ; => 3 The scope of ``a`` and ``b`` is limited to the current S-expression/form; if ``a`` and ``b`` are defined outside the ``let`` form, internally ``a`` and ``b`` *shadow* the outer names. 2) there is actually a ``do`` loop in the language, but it is cumbersome to use and redundant because the *named let* allows you to perform everything ``do`` does. I see it as a useless construct in a language that would like to be minimalist but it is not. .. _Wikipedia article: http://en.wikipedia.org/wiki/Tail_call_optimization There is no portable module system --------------------------------------------------------------------- As I have anticipated, libraries are the weak point of Scheme. There are few libraries available and it is also difficult to write portable ones. The reason is that historically Scheme never had any standard module system until very recently, with the R6RS document: that means nearly all current implementations provide different and incompatible module systems. In order to understand the reason for this serious lack, you must understand the philosophy behind Scheme, i.e. the so called `MIT approach`_: things must be done well, or not at all. For thirty years the Scheme community has not been able to converge on a well done single module system. It is only in 2007 that a standard module system has been blessed by the Scheme committee: but even that was done with a lot of opposition and there are implementors who said they will *never* support R6RS. As a consequence of history and mentality, if you want to write a library for implementation X, you need to do a lot of boring and uninspiring work to port the library to implementations Y, Z, W, ... (there are *dozens* of different implementations). Moreover, a few implementations do not have a module system at all, so you may be forced to solve name clashes issue *by hand*, changing the names of the functions exported by your library, if they shadow names coming from third party libraries (!) Personally, I picked up Scheme 5 years ago, but never used it because of the lack of a standardized module system. The main reason why I have decided to go back to Scheme and to write this series is the coming of the R6RS document last year. The R5RS standard has lots of defects, but at least now I can write a library and I can have people using different implementations install it and use it (nearly) seemlessly. .. _MIT approach: http://www.jwz.org/doc/worse-is-better.html .. _psyntax: http://www.cs.indiana.edu/~aghuloum/r6rs-libraries/index.html .. _not trivial at all: http://www.cs.utah.edu/plt/publications/macromod.pdf Since there is some hope for a large diffusion of R6RS module system in the future, I have decided to use it and to ignore implementations not supporting it. I should notice however that there are solutions to run R6RS modules on top of R5RS implementations, like the psyntax_ package, but I have not tried it, so I cannot comment on its reliability. As first example of usage of the R6RS module system, I will define a ``repeat`` library exporting a ``call`` function which is able to call a procedure ``n`` times. Here is the code, that should be self-explanatory:: (library (repeat) (export call) (import (rnrs)) (define (call n proc . args) (let loop ((i 0)) (when (< i n) (apply proc args) (loop (+ 1 i)))))) The ``export`` declaration corresponds to Python's ``__all__``: only the names listed in ``export`` are exported. In this case we will export only the function ``(call n proc . args)``. Notice the dot in the argument list: that means that the functions accept a variable number of arguments, which are collected in the list ``args``. In other words, ``. args`` is the moral equivalent of ``*args`` in Python, with some difference that we will ignore for the moment. The ``apply`` function applies the argument list to the input procedure ``proc``, which is called many times until the index ``i`` reaches the value ``n``. ``(import (rnrs))`` imports all the libraries of the current version of the "Revised Report on Scheme", i.e. the R6RS report. At the REPL this is automatically done by the system, but for batch scripts it is mandatory (as Pythonistas say *explicit is better than implicit*). It is also possible to import subsections of the whole library. For instance ``(import (rnrs base))`` imports only the base library of the R6RS, ``(import (rnrs io))`` imports only the I/O libraries, et cetera. The usage of the libray is trivial: it is enough to put the file ``repeat.sls`` somewhere in the Ikarus search path (specified by the environment variable ``IKARUS_LIBRARY_PATH``). Then, you can import the library as follows:: $ rlwrap ikarus Ikarus Scheme version 0.0.2 Copyright (c) 2006-2007 Abdulaziz Ghuloum > (import (repeat)) > (call 3 display "hello!\n") hello! hello! hello! By default ``(import (repeat))`` imports all the names exported by the module ``repeat``, something that a Pythonista would never do (it is equivalent to a ``import * from repeat``); fortunately it is possible to list the names to be imported, or to add a custom prefix:: > (import (only (repeat) call)); import only call from repeat call # > (import (prefix (repeat) repeat:)); import all with prefix repeat: > repeat:call # A simple benchmark ----------------------------------------------------------------- .. _episode 4: http://www.artima.com/weblogs/viewpost.jsp?thread=239568 The main advantage of Scheme with respect to Python is the performance. In order to show the differences in performance I will go back to the factorial example of `episode 4`_. I will compare the following Python script:: # fact.py import sys, timeit def fact(x): if x == 0: return 1 else: return x * fact(x-1) if __name__ == '__main__': n = int(sys.argv[-1]) t = timeit.Timer('fact(%d)' % n, 'from fact import fact') print t.repeat(1, number=10000000) print fact(n) with the following R6RS-compliant script (written in Ikarus Scheme):: ; fact.ss (import (rnrs) (only (repeat) call) (only (ikarus) time)) (define (fac x) (if (= x 0) 1 (* x (fac (- x 1))))) (define n (string->number (car (reverse (command-line))))) (time (call 10000000 (lambda () (fac n)))) (display "result:") (display (fac n)) (newline) .. image:: clessidra.png :width: 175 I will notice two things: 1. Python manages to compute the factorial of 995, but then it faces the stack wall and it raises a ``RuntimeError: maximum recursion depth exceeded`` whereas Scheme has no issues whatsoever; 2. In order to compute the factorial of 995 ten thousands times, Python takes 15.2 seconds, whereas Ikarus takes 7.2 seconds. Notice that since the factorial of 995 is a *large* number, the computation time is spent in multiplication of large numbers, which are implemented in C. Python has its own implementation of long integers, whereas Ikarus uses the GNU Multiprecision library (gmp_): the times measured here mean that the gmp_ implementation of long integers is more efficient than the Python one, but they say nothing on the relative performances of the two languages. It is more interesting to see what happens for small numbers. For instance, in order to compute the factorial of 7 for 10 millions of times, Python takes 30.5 seconds, whereas Ikarus takes 3.08 seconds and thus it is nearly *ten times* faster than Python. This is not surprising at all, since function calls in Python are especially slow whereas they are optimized in Scheme. Moreover Ikarus is a native code compiler. It means Ikarus' REPL_ works by compiling expressions to native code, whereas Python's REPL compiles to bytecode. The technology is called incremental compilation and it is commonly used in Lisp languages from decades, even if it may look futuristic for C/C++ programmers. The factorial example is not very practical (on purpose), but it is significant, in the sense that it is legitimate to expect good performances from Scheme compilers. The fastest Scheme compiler out there is Stalin_, but I would not recommend it to beginners. .. _REPL: http://en.wikipedia.org/wiki/REPL .. _gmp: http://gmplib.org/ .. _Stalin: http://community.schemewiki.org/?Stalin The next episodes will be devoted to the dangers of benchmarks, do not miss it!