Scheme, Scheme Implementations, SCM

-> In Japanese

-> In French

Updated: Wed Jan 18 03:41:41 2006

Table of Contents

Scheme

Scheme is a dialect of Lisp (List Processing programming language). The programs are written mainly with procedures returning a value (functions) and Lisp is called a functional language. The classification of programming languages into functional or procedural is not so meaningful because the end of all programming languages is program. The Lisp way of thinking is also for making good programs and the C language has similar ways to Lisp's to a certain extent since its beginning. In practice, however, there seems to be only a few programmers thinking in Lisp.

A document entitled "Lisp as an Alternative to Java -- Erann Gatt, Jet Propulsion Laboratory, California Institute of Technology", dated November 9 1999, says the following. Their expreriment "results show that Lisp's performance is comparable to or better than C++ in terms of execution speed, with significantly lower variability ... Furthermore, development time is significantly lower and less variable than either C++ or Java. Memory consumption is comparable to Java." It also says "development time for the Lisp programs was significantly lower than the development time for the C, C++ and Java programs" and "the difference cannot be accounted for by programmer experience." The experiment was performed with all the programs compiled to native code. So the execution speed has to be evaluated differently for the interpreted Lisp code but the other results seem to be commonly applicable to all Lisp.

For those who like Lisp, there is nothing to be surprised with the above experiment results. They beleive firmly that Lisp is an excellent programming language. But if Lisp is so excellent, a small puzzling fact remains why Lisp is not widely diffused. It would be of time consuming effort to unriddle it if not impossible. The best way would be to show the Lisp's advantages by practice as Mr. Shiro Kawai's Practical Scheme does.

Scheme is the smallest among all the Lisp dialects providing all the necessary features for programming. Scheme is perfectly specified within 50 pages, including index. This is due partly that Scheme is Lisp but no other languages have these compact specifications. Before Scheme, other languages appear to be obtaining a circle from polygon by increasing the number of sides infinitely .

Because Scheme specifications are extremely clear, Scheme programs are to be simple, correct and beautiful from the very beginning of programming skill.

Scheme was created with the concept that "Programming languages shoud be designed not by piling feature on top of feature, but by removing the weakness and restrictions that make additional features appear necessary." It was so designed that "a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language (Revised5 Report on the Algorithmic Language Scheme--r5rs--Introduction)."

If the rules are correct, the programs on those rules are correct. If the number of necessary and sufficient rules are reduced, the applicable domain of the rules is extended. The rules of a programming language are what provides the ways of expression, which give Scheme a diversiform expressiveness. Because each of the diversiform Scheme programs is subject strictly to Scheme rules, every Scheme program is duly correct and clear.

Scheme, invented by Guy Lewis Steele Jr. and Gerald Jay Sussman was first described in 1975. Guy Lewis Steele Jr. is the author of the "Common Lisp Reference Manual(First edition-1984, Second edition-1989)--Digital Press." He writes that Common Lisp is influenced to some extent by Scheme in its Introduction.

Scheme specifications were almost fixed on "Revised4 Report on the Algorithmic Language Scheme--r4rs-1991" after several revisions with introduction of new features such as Common Lisp's study results. The almost all actual Scheme implementaions are at least compliant with r4rs.

The latest specifications of Scheme are provided by Revised5 Report on the Algorithmic Language Scheme--r5rs-1998. R5rs is a super set of r4rs.

プログラミング言語Scheme kindly makes available my translation of r5rs into Japanese.
My translation was first made for myself when I was compelled to use Scheme unable to find documents on it in Japanese. I dared to make it public hoping to have no grave errors because the programs I wrote worked as my understanding of r5rs. I find inacurcies now in my translation. But once made public, it is difficult to motivate myself to remake the translation. I wish the readers to be tolerant enough.
In the meanwhile, it is known there are other versions of translation of r4rs and r5rs and a new translation appears lately made by Mr. Masaaki Murakami. The original r5rs contains lots of difficulties at least for me. Various translations would be of great help for better understanding of the original one.

Scheme was first diffused as educational language due to its above mentioned features but it's not limited to education. This page follows Mr. Shiro Kawai and is intended to care the practical aspect of Scheme application.

Scheme Implementations

An implementation must be installed to make use of Scheme.
In order to select one among lots of Scheme implementations, our criterion would be the Japanese language processing for us Japanese. If a Scheme implementaion is written in C, the char type is used to represent the Scheme characters for which char? returns #t. The Japanese locale need not necessarily be supported but if two successive bytes like Japanese characters are processed always as independent bytes, they can not be input nor displayed though able to be processed.
Among the implementations I experienced, these are the ones accepting Japanese input and display shown in an frequency of use order: (1)SCM, (2)Gauche, (3)STklos, (4)STk, (5)guile and (6)mit-scheme. Especially with Gauche, the r5rs STRINGS are so naturally extended that the standard procedures can be called as they are to handle multi-byte characters once compiled with the character code to be used specified.

The OSs I am using are, in the frequency of use order, too, FreeBSD 7.0-CURRENT, 6.0-STABLE, Debian Linux Unstable (kernel 2.4.26), Sarge (kernel 2.6.10) and Windows 2000. This seems to be in reverse order, seen from number of users.

This table shows how I installed the Scheme implementations for each of them.

Scheme implementaions I installed
OS SCM Gauche stklos STk guile mit-scheme
FreeBSD* 7.0-CURRENT**/6.0-STABLE*** rpm or gmake && ./build configure && make configure && gmake configure && make ports collection binary
Debian Linux Unstable****/Sarge***** rpm or make configure && make configure && make configure && make apt-get install binary
Windows 2000****** make configure && make or binary / / / /

x ... I couldn't install.
/ ... No try.

* Note when compiling on FreeBSD The actual FreeBSDs' (7.0-CURRENT and 6.0-STABLE) system C compiler seems to have a transitory problem. See
http://www.freebsd.org/cgi/query-pr.cgi?pr=ports/71684
The problem can be avoided by adding a 'volatile' modifier to the variable, excluding it from the compiler's optimization process as the ports did with eval.c (volatile struct {SCM arg_1;} t;), or by passing an agument to the 'build' script, which modifies the variable type so that the compiler keeps track of it while the optimization (see compiling with arguments to the build script.
** 7.0-CURRENT
% uname -a
FreeBSD daip 7.0-CURRENT FreeBSD 7.0-CURRENT #0: Mon Jan 16 19:00:29 JST 2006 daip@daip:/usr/obj/usr/src/sys/DAIKERNEL i386
% cc -v
Using built-in specs.
Configured with: FreeBSD/i386 system compiler
Thread model: posix
gcc version 3.4.4 [FreeBSD] 20050518

*** 6.0-STABLE
% uname -a
FreeBSD naho 6.0-STABLE FreeBSD 6.0-STABLE #0: Mon Jan 16 22:09:49 JST 2006 root@naho:/usr/obj/usr/src/sys/DAIKERNEL i386
% cc -v
Using built-in specs.
Configured with: FreeBSD/i386 system compiler
Thread model: posix
gcc version 3.4.4 [FreeBSD] 20050518

**** Debian Linux Unstable Version
% cc -v
Reading specs from /usr/lib/gcc-lib/i486-linux/3.3.4/specs
Configured with: ../src/configure -v --enable-languages=c,c++,java,f77,pascal,objc,ada,treelang --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-gxx-include-dir=/usr/include/c++/3.3 --enable-shared --with-system-zlib --enable-nls --without-included-gettext --enable-__cxa_atexit --enable-clocale=gnu --enable-debug --enable-java-gc=boehm --enable-java-awt=xlib --enable-objc-gc i486-linux
Thread model: posix
gcc version 3.3.4 (Debian 1:3.3.4-4)
***** Debian Linux Sarge
% uname -a
Linux colinux 2.6.10-co-0.6.2 #5 Sat Feb 5 10:19:16 IST 2005 i686 GNU/Linux
% gcc -v
Reading specs from /usr/lib/gcc/i486-linux/3.4.4/specs Configured with: ../src/configure -v --enable-languages=c,c++,java,f77,pascal,objc,ada,treelang --prefix=/usr --libexecdir=/usr/lib --with-gxx-include-dir=/usr/include/c++/3.4 --enable-shared --with-system-zlib --enable-nls --without-included-gettext --program-suffix=-3.4 --enable-__cxa_atexit --enable-libstdcxx-allocator=mt --enable-clocale=gnu --enable-libstdcxx-debug --enable-java-gc=boehm --enable-java-awt=gtk --disable-werror i486-linux
Thread model: posix
gcc version 3.4.4 20050314 (prerelease) (Debian 3.4.3-13)
****** Cygwin environment is used for installing on Windows 2000.
Cygwin environment is available from http://sources.redhat.com/cygwin.
- On floating point numbers: Shiro Kawai develops a detailed consideration about a queer behaviour of gcc compiling on the Intel derived CPUs.
For the floating point numbers, there seems to be implementations leaving some inaccuracies on their input/output (cf. (/ 1448997445238699 (expt 10 15) ≒ 1.448997445238699 and (* 6525704354437806 (expt 2 -52))).
Mr. Shiro Kawai kindly informed me of a paper: "Printing Floating-Point Numbers Quickly and Accurately", Robert G. Burger and R. Kent Dybvig, Proceedings of the SIGPLAN '96 Conference on Programming Language Design and Implementation. It describes a quick and accurate output algorithm of the floating point numbers, justified using Chez Scheme. Chez Scheme, principally developed by Mr. R. Kent Dyvig, seems to implement the algorithm.
Most of Scheme implementations provide, howerver, a formatting module like 'printf' or 'format' (SLIB abandonned it though) and the exact output is assured.

About SCM

In order to use SCM, SLIB must be installed beforehand so that SCM can require it on need.

SLIB

SLIB is available from http://swissnet.ai.mit.edu/~jaffer/SLIB.html maintained by Mr. Aubrey Jaffer. The latest version is "3a2". SLIB and SCM are closely related to each other and the simultaneous updates of both seem preferable in order not to get any oddities.

Unzip slib3a2.zip under the same write permitted directory with scm, for instance to $HOME, if scm is unzipped to $HOME.


    % unzip slib3a2 -d $HOME
  
SLIB libraries are opened out into the directory named `slib' under the specified directory. SCM searches the file location with reference to the directory where the scm executable resides. And the setting of the environment variable 'SCHEME_LIBRARY_PATH' seems not required. However, the SLIB library packages are searched from the directory of the environment varbiable if it is set.

Installing SCM

  1. Unzip scm5e1.zip to a convenient directory, for instance to $HOME. SCM source files are opened out into the directory named scm under the specified directory.
    
        unzip scm5e1 -d $HOME
        
  2. It might be worthwhile to check the followings before compiling SCM.

    • Using the bignum data format

      To make maximum use of SCM's bignum data format, I recommend to set the NUMDIGS_MAX defined in scmfig.h to around 20000 digits. If your own Makefiles are used, -DNUMDIGS_MUX=20000 can be passed to the compiler.

    • The prompt string for the SCM session can also be changed with this file.
      
      	    % diff -C3 scmfig.h.orig scmfig.h
      	    *** scmfig.h.orig       Tue Jun 28 07:43:45 2005
      	    --- scmfig.h    Tue Jun 28 07:43:55 2005
      	    ***************
      	    *** 392,398 ****
      	      # ifdef SICP
      	      #  define PROMPT "==> "
      	      # else
      	    ! #  define PROMPT "> "
      	      # endif
      	      #endif
      		        
      	    --- 392,398 ----
      	      # ifdef SICP
      	      #  define PROMPT "==> "
      	      # else
      	    ! #  define PROMPT "scm5e1> "
      	      # endif
      	      #endif
        
                  ***************
                  *** 437,443 ****
                    # define BIGLO(x) ((x) & (BIGRAD-1))
                    /* NUMDIGS_MAX is the maximum number of digits for BIGNUMS */
                    # ifndef NUMDIGS_MAX
                  ! #  define NUMDIGS_MAX 1000
                    # endif
                    #endif
        
                  --- 437,443 ----
                    # define BIGLO(x) ((x) & (BIGRAD-1))
                   /* NUMDIGS_MAX is the maximum number of digits for BIGNUMS */
                    # ifndef NUMDIGS_MAX
                  ! #  define NUMDIGS_MAX 20000
                    # endif
                    #endif
                

  3. From scm5e1, the disk based B-Tree database library 'wb' is ready to be compiled as part of the standard Makefile. The wb source code 'wb1c1.zip' can be obtained from http://swissnet.ai.mit.edu/~jaffer/WB. Unzip it to the same directory:
    
              unzip wb1c1 -d $HOME
            
  4. Create scmlit.
    
          make scmlit (gmake scmlit on FreeBSD)
          
    - scmlit is created and ready to execute the script file build written in Scheme.
    Scmlit is composed of minimum modules allowing to execute the build script and it is highly possible that it is compiled on any OSs.
  5. If `scmlit' is successfully created, "make all" will do all the rest in the Linux environment. In other environments where `executable image dump' is not available like FreeBSD, or if the image dump is not wanted, the executable can be created with the 、Makeffile and the `build' script with arguments to it.

    There are two formats for build arguments: short one like '-p freebsd' and long one like '--platform=freebsd'. I am explaining with short formats. See for details 'scm.info' file opened out into the scm directory: SCM -- Installing SCM -- Building SCM -- Build Options.

    • -h batch-script-format
      One of unix, dos, vms, amigados or system can be specified for batch-script-format.
      If '-h system' is specified, the compilation is executed actually. Other specifications let the program output the batch script to the standard output. SCM in fact is able to choose the batch script format from the environment where the build is executed. So -h option is not needed except for '-h system' specification.
    • -p platform-name
      Specify the name build database has for platform-name, one of the followings in present case: freebsd, linux, os/2-emx or unix(for cygwin).
      The build program will select from its database the compile options and link options related to the platform-name.
    • -F feature-name ...
      Specify for -F options the names separated by a space from the following table. The feature names marked with * (asterisk) indicate that I could not compile the feature. See scm.info and source files for details of the features.

      Features with ability of compilation(o = I could, * = I couldn't, / = not tested)
      Feature name Description FreeBSD Debian Linux cygwin
      arrays Multi dimensional arrays o o o
      array-for-each Array mapping o o o
      bignums Multiple precision data o o o
      cautious Number check of arguments o o o
      compiled-closure Integration of C functions o o o
      curses curses library o o o
      debug Error check for debugging o o o
      dump Executable image dump * o *
      dynamic-linking Dl library * o *
      edit-line Line editor o o /
      engineering-notation Engineering notation o o o
      generalized-c-arguments Variable number args C functions o o o
      i/o-extensions ANSI C file I/O o o *
      inexact Floating point arithmetic o o o
      macro r5rs macro o o o
      posix posix functions (pipe,fork,uname etc.) o o o
      unix Unix functions other than posix(symlink,nice,mknod etc.) o o *
      record Record data type o o o
      regex Regular expressions o o *
      rev2-procedures r2rs procedures o o /
      sicp (eq? () #f)==>#t, etc / / /
      socket BSD sockets o o /
      tick-interrupts ticks, ticks-interrupt, alarm etc. o o o
      wb wb, disk based B-tree associative array primitives d o o /

      - dynamic-linking uses `libdl'. 'libdl' is a separate library with Linux. It is included in 'libc' with FreeBSD.
      - edit-line uses an external library `libreadline'. It brings conveniences for the interactive use of SCM in Terminal mode. If there is inadequacy in `libreadline' or if it is unwanted, just compile SCM without it. Interactive operations can be provided by calling SCM as a subprocess of Emacs or XEmacs.
    Executing build without -F creates an scm executable featuring only 'arrays', 'bignums' and 'inexact' as default.
    
          build example 1(FreeBSD)
            ./build -h system -p freebsd 
          
    The above specifications force compiling and linking to create a minimum but general-purpose scm executable. The extention modules, however, can not be loaded dynamically.

    This will create another scm executable accepting dynamic load libraries. Only the specified features are included if -F option is specified and all the necessary features must be specified explicitly.

    
          build example 2(FreeBSD)
    
           ./build -h system -p freebsd -F arrays bignums inexact dynamic-linking
           
          
    From the scm5e1, the Makefile becomes easier to use allowing to pass arguments to the build script.
    • Passing arguments to the build script via Makefile

      There are three varibales defined in the Makefile among others: SCMLIT (call for the executable `scmlit'), SCMEXE (call for the executable `scm' and BUILD (call for the `build' script. Passing new definitions to the Makefile controls compiling and linking more flexibly.
      • Dumping an executable image using Linux specific compiler options (I am still unable to dump images with FreeBSD.)

        	    make dscm5 BUILD="./build -h system -p linux"
                  
        An scm executable, saved image of the scm session at the time of dumping, including r5rs extensions is output. This executable does not need to newly load the libraries which were under execution when dumping occurred. But the disk file is as huge as about 1M.
      • The variables and codes required upto the r5rs extensions, dynamic-wind, values and macro are compiled without dumping the scm execution image.

        	      make scm5 BUILD="./build -h system -p linux"
        	    
      • Building the same executable on FreeBSD

        The system C compilers of the 7.0-CURRENT and 6.0-STABLE as of today still suffer from errors of referencing the non existing variable due to a certain loss of the variable when the compilers' optimization level is increased. The error can be avoided by excluding the variable from the optimization process with the `volatile' modifier to the variable or by changing the variable type. This provides a workaround with the latter.
        	      gmake scm5 BUILD="./build -DGCC_SPARC_BUG --linker-options=-DGCC_SPARC_BUG -hsystem -pfreebsd" SCMLIT="./scmlit -no-init-file" SCMEXE="./scm -no-init-file"
        	    
        The option `-no-init-file' prohibits the executables from reading ScmInit.scm which may reside in the `Home Directory' from the previous scm's environment settings and may cause unexpected errors.

    In every case, the Makefile loads and executes r4rstest.scm, syntest1.scm (verification of the r4rs macro) and syntest2.scm (redefinition of the keywords). Though the scm on Debian Linux reports some inexactness due to the rounding errors of floating numbers, the results show that the compilation completes correctly and the program codes are executed correctly.

  6. Create dynamic-linking libraries
    
           % make mydlls BUILD="./build -h system -p linux" (Debian Linux)
           % gmake mydlls BUILD="./build -h system -p freebsd" (FreeBSD)
          
  7. Create the wb library.
            % cd $HOME/scm
    
    	% ln -s $HOME/scm/scm.h $HOME/scm/scmfig.h $HOME/scm/scmflags.h ../wb
    
            % make db.so BUILD="./build -h system -p linux" (Debian Linux)
    
    	% gmake db.so BUILD="./build -h system -p freebsd" (FreeBSD)
          
  8. Install

    The install is done into the `prefix' directory specified in the Makefile. The catalog files SCM creates are written into it, too. So the directory must be write permitted. Install as super user or specify to `prefix' a directory to which you have the write permission.

    
          % cd $HOME/scm
          % make install prefix=$HOME/ (Don't forget the last forward slash.)
          % cd ../slib
          % make install prefix=$HOME/ (Install the slib library packages.)
        

    The executable is installed into the `bin' directory under `prefix', the intilization files like Init$(VERSION).scm into $(prefix)/lib/scm and the `slib library packages' into $(prefix)/lib/slib. If there are dynamically loadable libraries (*.so), they are installed into the lib/scm directory, too.

    Issue 'new-catalog to update the `catalog' files.

          % scm -no-init-file -e'(require (quote new-catalog))'
        
    Enjoy Scheme world.

-> Back to previous page

-> Home


Dai Inukai