Scheme for scientific computing

2018-10-29

Introduction

Lisp is the family of most powerful (simple and expressive) programming languages available to date. Scheme is one of its most elegant dialects. (For a fast overview of Scheme see Appendix: Scheme of SICM; for a more detailed study see SICP; for Lisp motivational essays see here and here.)

Scheme is not a common language. This implies fewer available libraries than mainstream choices, and difficulty in interfacing Scheme programs to large collaborations' code bases. Furthermore, there are different implementations and dialects, leading to a fragmented community. A program written for one implementation is likely not to work with another one. The language standards are themselves controversial, having R6RS introduced breaks over previous versions.

This is a comparison of four Scheme implementations/dialects (Chez 9.5, Chicken 4, Gambit 4.2, Racket 7.1) in view of modern scientific computing needs (see this post for a more general guide). These include purely numerical applications, but also symbolic computations. See scmutils (online README) for an exemplar package that shows the expressiveness of Scheme.

Comparison

For each item the implementations in bold outperform the others. Items are listed roughly from the most to the less important. Technical details refer to information retrieved on October, 2018. Tests where performed under Debian 4.18.10-2 (2018-10-07) x86_64 GNU/Linux.

Speed and reliability

According to these benchmarks the fastest and most reliable Scheme implementations with larger community are: Chez, Chicken, Gambit, Racket. All are available as Debian packages and also provide simple installation from source.

(Bigloo (R5RS) and Larceny (R5RS, R6RS, R7RS) also perform well, but they are not available as Debian packages.)

• Chez is faster for a wider range of applications (same ballpark as SBCL Common Lisp).
• Chicken. There are apparently contrasting results for Chicken benchmarks. E.g., according to Gambit benchmarks page it performs similarly or better than Racket (MZScheme). Instead, on this page (same algorithms), Racket is often a factor 2 faster than Chicken, except when continuations are used and Racket is much slower. Note that in these benchmark sets, compiling options are kept constant for Chicken. Playing with Chicken compiler and runtime options (as described on Chicken website) can speed up significantly a specific program, so that in my experience Chicken usually outperforms Racket (still remaining in the same ballpark).
• Compared to Chez, Gambit performs similarly especially in numerical benchmarks, and similarly or within a few factors in general (worst case 10x slower).
• Racket has a larger variance, typically within O(1)-(10) w.r.t Chez/Gambit, but for a few cases it is to O(100) times slower. Racket vs Gambit benchmarks suggest that for most purposes Racket is in the same ballpark, except for programs that require capturing and invoking continuations. Racket vs Java suggest that Racket is typically 1x-5x slower than Java (some benchmark reaches a factor 10x slower, but it has very different CPU load.)

That said, the kind of benchmarks mentioned above should be taken with a grain of salt. They only consider runtime efficiency (not always optimally, see the Chicken Scheme case) and neglect development time. Python is one of the most popular languages for science, yet it (CPython) can be easily perform 100x slower than C. Having a Scheme implementation that is only 1x-10x slower than C/C++ is a significant improvement. It is also important to keep in mind that the variance between programmers can be larger than the variance between languages, suggesting that an appropriate programming style is more important for overall efficiency than the particular language choice (provided they are in the same ballpark).

3rd-party libraries and package manager

• Chez lacks of established 3rd-party libraries package manager (although it has tools to support it). There are efforts to provide standard repositories. Thunderchez looks like the most promising project in this direction. Raven aims at being a reliable package manager, however the installation instructions are not necessarily convenient (e.g., requires "scheme" executable name to be reserved for Chez Scheme compiler).
• Chicken: Eggs is a comprehensive set of reliable packages, well supported by the community. They can be installed with Chicken own package manager. Unfortunately there is a lack of scientific libraries.
• Gambit lists repositories R5RS-compatible with some possibly useful library. However, several links on the official website are broken, library support is rather limited anyway (hardly include SRFI's), installation scripts are often broken or require hacks. Gerbil aims at providing a battery-included Gambit for system programming, but its installation instructions did not work right away.
• Racket has a good package manager, raco. Libraries have surprisingly good support, e.g., for plotting. However, there are few numerical libraries. Also, while there are complete and well documented packages (the standard library has excellent support especially for beginners), a non-negligible fraction of 3rd party packages is at a rather incomplete prototype level and lacks of documentation. This is better than nothing (given the skeleton of let's say a wrapper to a C library, it is easy to extend it), but not ideal.

Foreign Function Interface

The Foreign Function Interface (to call procedures written in C or in languages that obey the same calling conventions as C, and viceversa to call scheme procedures from C) is important given the lack of native libraries.

• Chez has procedure to import/export Scheme functions from/to C. Documentation is less clear then Gambit. For instance, when mentioning distribution the documentation only considers the Petite Chez Scheme interpreter (not available at the up-to-date, Chez Scheme 9, download page), not the Chez Scheme interpreter and compiler.
• Chicken has an excellent C interface (it even allows to easily embed C code into Scheme source files) and extensions that makes it even easier to use. It supports embedding Scheme procedures into C. An extension to call Python 2 functions is also available.
• Gambit has simple procedures to import C function in Scheme, and to make Scheme functions available to be imported in C-compatible languages (they only work with the compiler, not from the interpreter). The compiler can easily create shared libraries.
• Racket has a relatively simple interface to import C functions, but embedding Racket into C seems involved.

Parallel computing

• Chez supports native threads on several architectures. The lack of libraries to simplify its use (e.g. via parallel map procedures) limits the practical utility.
• Chicken core only supports green threads (extensions also support Termite-like concurrency, see, below), parallel computing is available via Eggs extensions (e.g., MPI).
• Gambit supports green threads via the Termite language (written atop Gambit), but it it lacks documentation.
• Racket has support for parallelization (with futures and places), including MPI and user-friendly parallel mapping (pmap) libraries. However it is tricky, it is not uncommon for parallel computations to take longer than serial jobs due to the associated overheads.

Debugging and profiling

• Chez has a nice debugger and excellent profiling tools.
• Chicken also has a nice debugger, great error messages, but the profiler is rather limited (e.g., it is at least not obvious how to trace procedures defined internally to other procedures).
• Gambit debugger jumps into nested prompts each time that something is evaluated erroneously, which may be annoying when coding interactively. However, there are shortcuts and commands that makes it nice to use.
• Racket has great error messages, both in DrRacket and Emacs. It has a debugger with macros stepper. The profiler also supports multiple threads.

Source documentation tools

• Chez: stex is a Latex-like language to write documentation (separate from source code) with built-in commands for Scheme code display.
• Chicken: core and eggs documentation is available via a wiki. The chicken-doc extension makes all the documentation available via command line and from the interpreter, providing good accessibility to both the core language and to those Eggs extensions uploaded on the Chicken infrastructure. There is also an extension (the Hahn egg) for in-source documentation similar to Doxygen, but it does not seem widely used.
• Gambit: no option.
• Racket: Scribble. Powerful language, a pity that it is mainly used to write documentation separately from source code. This is the standard to document Racket projects.

Chez and Gambit are also supported by SLIB that has a nice inline documentation language, Schmooz.

Community

• Chez, Gambit: in both cases the core of the project is mainly the effort of a small group of developers.
• Chicken: extremely helpful community, help (mailing lists and IRC) is often provided by the core developers of the language. Welcoming guidance about how to contribute to the projects. While the documentation is overall clear, it suffers form being scattered around an official manual and a wiki.
• Racket: helpful community, excellent documentation and several pedagogical resources are available (there is actually a tendency towards verbosity). Development and mailing lists require accounts on proprietary platforms.

Editor

• Chez: no IDE. Great native REPL.
• Chicken: no IDE, very basic native REPL. There are extensions to be installed via Eggs that enhance it and make it a great REPL.
• Gambit: no IDE, good native REPL.
• Racket: DrRacket. It is the best option for non-Emacs users. Note that Racket is less interactive than typical Scheme REPL's, since there is a definition buffer that is evaluated as a whole before switching to the REPL (there is no Emacs-like eval-last-sexp, C-x C-e, for single definitions).

That said, all implementations are supported in Emacs.

Standards support

R6RS is controversial, incompatible with R5RS. However, it also introduced useful features (e.g., exceptions, libraries) compared to R5RS.

R7RS-small is the most recent minimalistic Scheme revision, improving over controversial R6RS.

• Chez: R6RS. (Discussion on development issues page says that Chez may think to support R7RS.)
• Chicken: R5Rs, R7RS (experimental).
• Gambit: R5RS. It has a number of extensions over R5RS (e.g., exception-handling), but lacks some feature (e.g., library tools like define-library, import, export).
• Racket: while it does not aims to support Scheme standards, it has an almost super-set of R6RS.

Discussion

Here we discuss more in details similar implementations.

Chez and Gambit

Gambit is smaller and simpler, and documentation more clear. Chez is larger and its documentation is more extended (and integrated by excellent The Scheme Programming Language); however, the chapter about software distribution could profit from an update. Chez has a R6RS-compliant library support, but it has limited 3rd-party libraries availability and no established package manager; Gambit has its own library system and a few 3rd-party libraries are available via semi-official package managers, but often their installation is difficult and several links to documentation are broken.

Working only with Gambit would mainly require to write interfaces to C programs even for most basic tasks; distribution as shared libraries is nice, but the process requires cumbersome makefiles. Chez is better supported by 3rd party libraries and The Scheme Programming Language (written by Chez author) targets specifically numerical examples. Among the two, at the present Chez seems better suited for numerical computing.

Chicken and Racket

Chicken has reliable package manager, libraries and an helpful lively community (it is also the only Scheme discussed here whose source files are available on self-hosted git repository). There are extensive tutorials on several practical aspects of the language, also targeted to programmers coming from other languages. The compiler requires experimenting (and can be quite slow with inappropriate options), but it allows large room for optimization if needed. Online publicly available benchmarks put Chicken in the ballpark 10x slower than C, comparable to Racket but with a significantly smaller variance (especially more convenient when capturing continuations).

Racket has many nice features. Racket main language is not RnRS-compatible, not necessarily a (dis-)advantage. It has an excellent package manager and a large library repository. It is maybe the most friendly implementation for people coming from Python. However, embedding Racket into C will be likely challenging if needed. Performance has a large variance, use of continuations and I/O operations can seriously slow down programs by a factor O(10-100). Overall it is placed in the ballpark of 10x slower than C (see also Benchmarks Game).

Conclusions

We compared Chez, Chicken, Gambit and Racket in view of usage in scientific programming. They can be divided into two groups:

• Chez and Gambit. Speed competitive with C/C++/Fortran. Relatively small community and serious lack of libraries.
• Chicken and Racket. Good performance, typically only some factor slower (roughly within O(10)) than Chez and Gambit. Good community support and large set of libraries. Yet, lack of scientific libraries.

Unfortunately the lack of scientific libraries is a serious practical issue and there is no ideal implementation to promptly replace popular languages like Python. Non-negligible efforts are likely required to write from scratch wrappers to C/C++/Fortran libraries. The absence of a package manager in Chez and Gambit makes it too unpractical to use these highly efficient and reliable implementations. Due to Racket large variance in runtime efficiency (especially when capturing continuations) and in packages quality, Chicken seems the most suited candidate for a Scheme implementation usable in scientific computing tasks.

A significant community effort around Chez (starting from establishing a package manager) is much desirable. As Chez is being adopted by larger projects (e.g., there are plans to implement Racket itself in Chez), a critical mass of users may be reached.

Other Lisps

An obvious alternative to Scheme as a Lisp dialect is Common Lisp. Common Lisp has excellent, efficient (runtime usually of the same order as C, only a few factors slower) implementations like SBCL (same ballpark than Chez Scheme), a large community, an established package manager to easily access an extensive library (quicklisp) that receives frequent new contributions. Scheme is conceptually simpler than Common Lisp thanks to only one namespace for functions and variables (among other differences). E.g., Scheme only needs define for both variables and functions, there are no defun, setf, defvar, etc. (but, of course, they can be defined if needed as an extension of Scheme, e.g., in a Domain Specific Language). Especially, Scheme does not need the awkward funcall for function application.

Another Lisp dialect worth considering is Clojure. It is actively maintained, the community is significantly larger than those around Scheme implementations (although relatively small compared to mainstream languages like Python, it still provides excellent documentation and support). While being a battery-included modern language, it feels much simpler than Common Lisp. In some aspect its design choices makes it also more immediate than Scheme, see for instance the implementation of hash tables and sets. Notably, the core language has excellent support for concurrency. The number of native Clojure packages is not competitive with Python, and integration of C/C++ code is not trivial. However, running on the Java Virtual Machine, it is easy to access all libraries available for Java (one of the best supported languages for Machine Learning). Projects building and automatic dependency resolution are managed via Leiningen (build automation tool ideal for medium size and large projects). Benchmarks put it in the same ballpark as Java and SBCL (Common Lisp) for runtime performance, while it can easily be a factor 2 more requiring in memory.

Given that Scheme implementations present serious practical difficulties for usage in scientific computing (e.g., as a replacement for typical joint C/C++ and Python use), Clojure seems an excellent, Lisp-based ready-to-use alternative that still does not deviate too much from Scheme simplicity.

Updates

• 2020-05-17 Thanks to Jason Hemann for mentioning ChezWEB, a literate programming environment for Chez Scheme.
• 2019-10-22 Thanks to Louis de Guenchy for mentioning Darkart, a binary interface to let Chez Scheme use libraries of several languages at the forefront of scientific computing (Python, Julia, OCaml, etc.).
• 2019-09-12 Thanks to Marc-André Bélanger for pointing out that Gerbil is now very simple to build and it comes with a package manager and a build system to facilitate software delivery.