Scheme


Scheme (pronounced “skiim”) is a programming language derived from the functional language Lisp , created in the 1970s at the Massachusetts Institute of Technology (MIT) by Gerald Jay Sussman and Guy L. Steele .

The aim of the creators of language was to purify the Lisp by retaining the essential aspects, flexibility and expressive power. Scheme therefore has an extremely simple syntax, with a very limited number of keywords. As in Lisp, the notation prefixed makes it possible to dispense with a precedence of the operators . Moreover, the power of Scheme macros allows it to adapt to any problem, especially to make it object-oriented and thus multi-paradigm.

The specification of Scheme 1 specifies that all implementations must optimize the case of terminal recursion .

The basic data types of Scheme are Booleans , numbers, which can be integers of indefinite size, rational or complex, characters or symbols, which are variables.

To these are added composite data types: strings, vectors, oriented pairs, lists, associative lists, hash tables and a generic type, the S-expression , of which all other types are derived, making possible metaprogramming , that is to say the ability to extend the language with new special operators .

History

Gérald Sussman and Guy Steele returned to the birth of Scheme in an article entitled The First Report on Scheme Revisited 2 and published in 1998.

In 1973, Carl Hewitt proposed his model of actor and wrote with his students an implementation in Lisp called Planner-73, then PLASMA (acronym PLAnner-like System Modeled on Actors ). Sussman and Steele want to better understand Hewitt’s model, in particular by linking it to the traditional notions of programming, write a little Lisp interpreter and primitives to create actors and send messages between them. They use the same syntax for functions and actors, the first being closures declared by the keyword lambdaand returning a value, and the second by alpha. The actors do not return, but call for continuations , which are the other actors that he knows.

The language is called “Schemer”, following the naming of the Planner and Conniver languages, from which it is inspired. However, the ITS system used at the time limits 6-character file names, truncating the name to “SCHEME”. Sussman and Steele say they no longer remember why they did not choose to abbreviate “SCHMR”, as Planner and Conniver used “PLNR” and “CNVR”.

They discover, after writing programs with actors, that the implementation of the interpreter was identical, that the code to be evaluated concerns functions or actors, and that the same applies to the code that creates the functions And actors. The difference between the fact that only functions return values ​​and not actors did not exist in the implementation, but only in the primitives used in the body of definitions of functions and actors. They deduce that actors and closures are in fact the same concept, and Hewitt himself admitted it later.

These discoveries on the embryo that was then Scheme led to three major conclusions. First, the model of actor Hewitt was perfectly represented in λ-calculus . This was not new in itself for the theoreticians of denotational semantics , but Scheme made it possible to bring a practical dimension to these theories. Then, it appeared that the simple and small formalism of the λ-calculus can be used for a kernel of an expressive and powerful programming language Note 1 , Scheme is therefore an applied λ-calculus. The corollary is immediate: the denotational semantics is equivalent to the operational semantics . Finally, the quest for an ultimate language for artificial intelligence has turned round,

Overview of Language Syntax

The variables are dynamically typed and their scope is lexical :

 ( Define var1 value )
 ( Let ([ var2 value ])
 ... )

Lists :

 ( Cons 1 ( Cons 2 ( Cons 3 ( Cons 4 ' ())))

This concatenation can be shortened to

 ( List 1 2 3 4 )

Or

 ' ( 1 2 3 4 )

Functions : they are defined as lambda-expressions

 ( Define fun
 ( lambda ( arg1 arg2 )
 ... ))

Or more simply

 ( Define ( fun arg1 arg2 )
 ... )

Application to a list:

 ( Apply fun ( list value1 value2 ))

Conditional Ratings :

 ( Cond ( test1 expr1 )
 ( test2 expr2 )
 ...
 ( else exprn ))

and also

 ( If condition
 then-expr
 else-expr )

Example 1 – calculation of a factorial:

 ( Define ( factorial n )
 ( if ( = n 0 )
 1
 ( * n ( factorial ( - n 1 )))))
 (Factorial 5)
 ; ⇒ 120

Example 2 – definition of a map function, which applies a lambda-expression (which raises its argument to the square) to all the elements of a list:

 ( Define ( map f lst )
 ( cond (( null? Lst ) lst )
 ( else ( cons ( f ( car lst ))
 ( map f ( cdr lst ))))))
 (Map (lambda (x) (* xx)) '(1 2 3 4))
 ; ⇒ (1 4 9 16)

Tail-recursive versions of the two preceding examples:

 ( Define ( factorial n )
 ( let loop (( fact 1 )
 ( n n ))
 ( cond (( = n 0 ) fact )
 ( else ( loop ( * n fact ) ( - n 1 ))))))
 (Factorial 5)
 ; ⇒ 120
 ( Define ( map f lst )
 ( do (( lst lst ( cdr lst ))
 ( res ' () ( cons ( f ( car lst )) res )))
 (( null? Lst ) ( reverse res ))))
 (Map (lambda (x) (* xx)) '(1 2 3 4))
 ; ⇒ (1 4 9 16)

Implementation

R n RS

Scheme is, with Common Lisp , the most popular dialect of Lisp. Like Lisp, there are multiple implementations each adding functionality according to the needs of their users. A report regularly updates the various implementations, in order to define a definition of consensual language. These reports are named Revised n Report on the Algorithmic Language Scheme note 2 , where n is the number of the revision, and abbreviated R n RS . Their goal is to be able to exchange code between different implementations that conform to a given revision of the report.

The sixth revision 1 was issued in September 2007 and ratified by 102 people, or two thirds of voters 3 . This report is immediately controversial, some of the authors of the main implementations indicated that they would integrate some new features of the R 6 RS, but not the entire report 4 , Marc Feeley considers that the goal of the R6RS can not be reached and that, We must work on a new standard.

In 2009, the Scheme Steering Committee issued a press release 3 in which it recalls the diversity of Scheme’s implementations, which are both its weakness and strength. He said that the current diversity justifies the distinction between two Scheme languages, one so-called small , inheriting from the IEEE Scheme and the R 5 RS, and a large , inheriting from the R 6 RS, but nevertheless compatible with each other. The Steering Committee creates two working groups to prepare the new revision (R 7RS) of the language.

The first part of the report, called R 7 RS-small , was finalized in July 2013 5 .

Major implementations

[ View ]Too many external links (January 13, 2017) .
  • MIT / GNU Scheme  [ archive ]
  • Scheme  (en) , a free Scheme interpreter and commercial compiler [ref. Necessary] for Microsoft Windows and several Unix systems
  • Chicken  [ archive ] is a Scheme-to-C compiler.
  • Gambit  [ archive ] is a R5RS compliant Scheme-to-C compiler.
  • Guile is the extension language of the GNU project. The Scheme interpreter is a library that can be used as a scripting language for applications.
  • Racket  [ archive ] , formerly PLT-Scheme, a suite of programs including an interpreter (racket), a graphical development tool (MrEd), a pedagogical oriented editor (DrRacket), and various components including Component object model (COM) And ODBC.
  • Kawa  [ archive ] is an implementation of Scheme in Java.
  • Scsh  [ archive ] or Scheme Shell is an R5RS product that can be used as a system scripting language and command interpreter.
  • Left  [ archive ] is a multilingual R5RS product under BSD license, for programmers and system administrators.
  • Bigloo  (en) 6 is a Scheme-to-C compiler and Scheme-to-Java which produces compact and fast executable, with a relatively large number of libraries.
  • STklos  [ archive ] is a free implementation of the Scheme language of the University of Nice which is light and efficient.
  • Elk  [ archive ] is a free implementation of the language.
  • The image editing software GIMP includes an interpreter of a language derived from Scheme, TinyScheme , to write in script (called script-fu) some manipulations of image.
  • More products can be found on schemers.org FAQ  [ archive ]

Differences with Lisp

This section is empty, insufficiently detailed or incomplete. Your help is welcome!

Scheme takes the syntax of the Lisp S-expressions by changing a few keywords. A scheme expression is either an atomic value (number, string, identifier, etc. ), or a list of expressions. The notable differences with Lisp are:

  • Lexical scope through closures ;
  • Unique namespace for functions and variables: Scheme uses definewhere Lisp chooses or defvarwhere defun ;

Common Lisp vs. Scheme  [ archive ]

Notes and references

Notes

  1. ↑ Although Lisp has used the notation λ, but without knowing handle free variables , the theoretical core of Lisp based on recursive equations, not the λ-calculus.
  2. ↑ That could be translated by: ” n e revision of the report on the algorithmic language Scheme”.

References

  1. a and b ( in ) Revised⁶ Report on the Algorithmic Language Scheme  [ archive ] .
  2. ↑ ( in ) Gerald Jay Sussman and Guy L. Steele, Jr. , ” The First Report on Scheme Revisited ” , Higher-Order and Symbolic Computation , vol.  11, n o 4,, P.  399-404 ( ISSN  1388-3690 and 1573-0557 , read online  [ Archive ] ).
  3. a and b ( in ) Scheme Steering Committee Position Statement [ archive ] , 20 August 2009, accessed 26 January 2013.
  4. ↑ ( in ) Marc Feeley, ” Implementors’ intentions concernant R6RS [ archive ] , on lists.r6rs.org , ( Consulted on January 26, 2013 ) :”  It seems clear to me that the R6RS fully. Generally each implementor intends to pick and choose minor R6RS features that will be supported (but not the same set of features for all Scheme implementations). For this reason I believe that R6RS will fail to achieve its goal of allowing the sharing of code between different Scheme subcommunities. We need to start working on a standard that will.  “.
  5. ↑ ( in ) Revised 7 Report on the Algorithmic Language Scheme [ archive ] [PDF] .
  6. ↑ Bigloo  [ archive ] in inria.fr