Scheme Tutorial

Scheme is a simple and powerful programming language, designed to be minimal but not minimalistic: this means for us that Scheme includes all necessary notions for concise and efficient programming, without any fuzz,

Scheme is much simpler than C++, Ada, or Java: the essential documentation takes just a few dozen pages, as opposed to more than 1000 pages for those complex languages. But this is enough to get lots of things out of your computer!

• Expressions - shell language and scripts
• Handling lists and trees
• Functions
• Some advanced techniques

Expressions, interactive shell, and scripts

In the most basic use, a Scheme system is an interactive shell: the user types in an expression, the Scheme system computes the expression's value, and prints it out. This is called the read-eval-print loo Look at the folowing sample session; the characters ;> at the beginning of a line are the Scheme prompt, the character = precedes the printout of a result.

:>(+ 1 2)
= 3
:>(* (sin 0.2) (cos 0.2))
= 0.194709
:>(string-append "abc" "123")
= "abc123"

Syntaxe - basic rules

We define an expression E using the terminal symbols id for identifier (symbol), num for number, and parentheses.

  E -> id | num | ( E* )

In the third rule - E -> (E*) the first expression in the parentheses denotes a function, the following expressions are the parameters.

The standard functions defined in all Scheme systems include the classical mathematical functions: the operators + - * / , and functions like sin, cos, sqrt, exp, log

Defining variables

For computations with a shell, it is useful (in fact, it is necessary) to be able to define variables for constants, and for intermediate results.

(define piby2 (acos 0.0))
(define piby4 (/ piby2 2.0))
(display-l "pi square = " (* (* 2.0 piby2) (* 2.0 piby2)) "\n")

Functions

Numbers are not the only things that you can manipulate in Scheme - functions are just as good.

(lambda (x) (* x pi)) is a function that computes the product of its argument by pi.:

:>((lambda (x) (* x pi)) pi)
= 9.86960

Such a lambda expression is just a function, without a name. You can assign this function to a name using the define expression:

:>(define productpi (lambda (x) (* x pi)))
=
:>(productpi 2.0)
= 6.28319

Hold and belo

To get really off the ground, you want to define recursive functions, and you need some form of conditional expression.

:> (define fact (lambda (n)
                  (if (< n 2)
                      1
                      (* n (fact (- n 1))))))
:>(fact 10)
= 3628800

Compare with C:

int fact(int n){
 return n < 2 ? 1 : n * fact(n-1);
}

Using the few features described so far - expressions, variable definition, numbers and recursive functions - you can do lots of useful calculations!

Exercise It is an amazing fact that the number of seconds in a bisextile year is very close to the square root of 10 raised to the 15th power. How many digits of the two numbers are identical? How big is the error - expressed in seconds, expressed in percentage?

Handling lists and trees

More about functions

Functions as arguments

(map productpi (list 1 2 3))

Higher order functions

(define compose
        (lambda (f g)    ; f and g are one argument functions
             (lambda (x) ; the result is the composite function
                (f (g x)))))

Defining local variables with let expressions

Lexical scope and indefinite extent

State and variable assignment

(define (make-counter)
   (let ((val 0))
     (lambda ()
        (set! val (+ val 1))
	val)))

Message passing

Some advanced techniques

Continuations

La norme Scheme et Ravi

Scheme est un langage de programmation defini par un standard. Ce standard ne specifie pas tout: certains choix sont laisses a l'appreciation de chaque implementeur.

scm est une implementation de Scheme qui vient du MIT; c'est un interpreteur ecrit en C, d'une qualite excellente.

ravi est egalement une implementation de Scheme, mais c'est un "produit local" qui, en plus du Scheme standard, propose une interface avec C++ (et plein d'autres choses).

Au meilleur de notre connaissance, scm et ravi donnent rigoureusement les memes resultats pour des programmes respectant la norme Scheme.

Mais: si vous sortez de la norme, vos programmes sont "non portables" ce qui veut dire que scm et ravi peuvent diverger. En voici une illustration prise dans la vie réelle:

La fonction suivante n'est pas correcte, car elle utilise mal le define internes:

 (define (fn a b)
	(define x a)
	(define (ff z) (cons x b))
	(define y (cdr x))
    (if (pair? y)
	(ff x)
	x))

Le define interne

Le paragraphe le plus obscur de la definition de Scheme concerne le letrec et le define pour les fonctions internes; il est pourtant essentiel.

Regle: les define internes sont faits pour la definition de fonctions mutuellement recursives. Pour les definitions de variables, il vaut mieux utiliser let ou let*.

Plus exactement: le calcul de la valeur d'un define ne peut pas utiliser la valeur d'un define "parallele", c. a d. au même niveau. Dans l'exemple ci-dessus, la definition de y est illegale pire (malheureusement): son effet n'est pas specifié!

Mais: scm interprete ces define de facon purement sequentielle - donc ca marche comme on le voudrait. Par contre, ravi recupere une valeur "non-specifiee" ... d'ou divergence de programmes. De plus, l'interpreteur ne sort aucun message; il devrait, peut-etre.

Ceci etant, le compilateur de ravi sort bien un message d'erreur dans cette configuration. Avec ravi -mod compile monfichiervous pouvez donc vous informer.

Morale: imaginez comment c'est de porter des programmes dans un langage moins bien defini que Scheme, comme C, par exemple.