|
Scheme is a multi-paradigm programming language and a dialect of Lisp which supports functional and procedural programming. It was developed by Guy L. Steele and Gerald Jay Sussman in the 1970s. Scheme was introduced to the academic world via a series of papers now referred to as Sussman and Steele's Lambda Papers. There are two standards that define the Scheme language: the official IEEE standard, and a de facto standard called the Revisedn Report on the Algorithmic Language Scheme, nearly always abbreviated RnRS, where n is the number of the revision. Image File history File links Lambda_lc. ...
A programming paradigm is a paradigmatic style of programming (compare with a methodology, which is a paradigmatic style of doing software engineering). ...
A multiparadigm programming language is a programming language that supports more than one programming paradigm. ...
Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...
This article or section does not cite its references or sources. ...
Guy Lewis Steele, Jr. ...
Gerald Jay Sussman is the Matsushita Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT). ...
In computer science, a type system defines how a programming language classifies values and expressions into types, how it can manipulate those types and how they interact. ...
PLT Scheme is an umbrella name for a family of implementations of the Scheme programming language. ...
GNU Guile is an interpreter for Scheme, a version of LISP, packaged as a library so that it can be embedded in other programs. ...
Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...
ALGOL (short for ALGOrithmic Language) is a family of imperative computer programming languages originally developed in the mid 1950s which became the de facto standard way to report algorithms in print for almost the next 30 years. ...
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ...
A multiparadigm programming language is a programming language that supports more than one programming paradigm. ...
A dialect of a programming language is a (relatively small) variation or extension of the language that does not change its intrinsic nature. ...
Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...
Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ...
This article or section does not cite its references or sources. ...
Guy Lewis Steele, Jr. ...
Gerald Jay Sussman is the Matsushita Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT). ...
Lambda the Ultimate Papers were written by Gerald Jay Sussman and Guy Steele Jr. ...
The Institute of Electrical and Electronics Engineers or IEEE (pronounced as eye-triple-ee) is an international non-profit, professional organization incorporated in the State of New York, United States. ...
Scheme's philosophy is minimalist. Scheme provides as few primitive notions as possible, and, where practical, lets everything else be provided by programming libraries. Scheme, like all Lisp dialects, has very little syntax compared to many other programming languages. There are no operator precedence rules because fully nested and parenthesized notation is used for all function calls, and so there are no ambiguities as are found in infix notation, which mimics conventional algebraic notation. This article is about computing. ...
Illustration of an application which may use libvorbisfile. ...
Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...
This article is about the concept of operator precedence. ...
An S-expression (S stands for symbolic) is a convention for representing data or an expression in a computer program in a text form. ...
Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e. ...
Scheme uses lists as the primary data structure, but also has support for vectors. Scheme was the first dialect of Lisp to choose static (a.k.a. lexical) over dynamic variable scope.[citation needed] It was also one of the first programming languages to support first-class continuations.[citation needed] In computer programming, an array, also known as a vector or list (for one-dimensional arrays) or a matrix (for two-dimensional arrays), is one of the simplest data structures. ...
In computer programming in general, a scope is an enclosing context. ...
In computing, a continuation is a representation of the execution state of a program (for example, the call stack or values of variables) at a certain point. ...
History
Origin Scheme started as an attempt to understand Carl Hewitt's Actor model.[1] Scheme was originally called "Schemer", in the tradition of other Lisp-derived languages like Planner or Conniver. The current name resulted from the authors' use of the ITS operating system, which limited filenames to two components of at most six characters each. Currently, "Schemer" is commonly used to refer to a Scheme programmer. Image File history File links File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ...
Knights of the Lambda-Calculus is a semi-mythical organisation of expert LISP and Scheme hackers. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
A fixed point combinator (or fixed-point operator) is a higher-order function which computes a fixed point of other functions. ...
A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ...
Carl E. Hewitt is an Associate Professor (Emeritus) in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology (MIT). ...
In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation. ...
Planner (often seen in publications as PLANNER) is a programming language designed by Carl Hewitt at MIT, and first published in 1969. ...
ITS, the Incompatible Timesharing System, was an early, revolutionary, and influential MIT time-sharing operating system; it was developed principally by the Artificial Intelligence Laboratory at MIT, with some help from Project MAC. ITS development was initiated in the late 1960s by those (the majority of the MIT AI Lab...
Future A new language standardization process began at the 2003 Scheme workshop, with the goal of producing an R6RS standard in 2006. It breaks with the earlier RnRS approach of unanimity. R6RS will feature a standard module system; allowing a split between the core language and libraries.
Advantages Scheme's macro facilities allow it to be adapted to many different problem domains. They can be used to add support for new paradigms, like object-oriented programming, logic programming, etc.[citation needed] Scheme provides a hygienic macro system which, while not quite as powerful as Common Lisp's macro system, is much safer and often easier to work with.[citation needed] The advantage of a hygienic macro system (as found in Scheme and other languages such as Dylan) is that any name clashes in the macro and surrounding code will be automatically avoided.[citation needed] The hygienic macro system is usually built on some low-level facility which provides the full power of non-hygienic macros, including arbitrary syntax-time computations. ...
In computer science, object-oriented programming, OOP for short, is a computer programming paradigm. ...
Logic programming (sometimes called logical programming) is programming that makes use of pattern-directed invocation of procedures from assertions and goals. ...
The Scheme programming language is a functional programming language and a dialect of Lisp. ...
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ...
The Dylan programming language (pronounced , like the name) is functional, object-oriented, reflective and dynamic. ...
Scheme encourages functional programming. Purely functional programs have no state and no side effects, and are therefore automatically thread-safe and considerably easier to verify, optimize, and parallelize than imperative programs. Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ...
Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications (updates). ...
In computer science, a function is said to produce a side effect if it modifies some state other than its return value. ...
Thread-safety is a computer programming concept applicable to multi-threaded programs. ...
Program verification is the process of formally proving that a computer program does exactly what is stated in the program specification it was written to realize. ...
In computer science, imperative programming, as opposed to declarative programming, is a programming paradigm that describes computation in terms of a program state and statements that change the program state. ...
In Scheme, functions are first-class objects. This allows for higher-order functions which can further abstract program logic. Functions can also be created anonymously with lambda.[2] In computing, a first-class object (also -value, -entity, -citizen), in the context of a particular programming language, is an entity which can be used in programs without restriction (when compared to other kinds of objects in the same language). ...
In mathematics and computer science, higher-order functions are functions which can take other functions as arguments, and may also return functions as results. ...
Scheme has a minimalistic standard. While this can be seen as a disadvantage, it can also be valuable. For example, writing a conforming Scheme compiler is easier (since there are fewer features to implement) than for a Common Lisp compiler.[citation needed] The complete Scheme standard is smaller than the index to Guy Steele's Common Lisp: The Language (that is, about 50 pages). Guy Lewis Steele, Jr. ...
Disadvantages The Scheme standard is very minimalist, specifying only the core language. This means that there are many different implementations, each with its own extension to the language and libraries. The Scheme Requests for Implementation (SRFI) process has done much to remedy this.
The Scheme community is still somewhat fragmented, and some libraries only work in specific implementations.
Some Common Lisp users see functions and variables declared in the same namespace as a disadvantage, since that makes it impossible to use the same name for a function and a separate variable in the same scope. Many Scheme programmers (and a few Common Lisp users, who prefer CL for other reasons) see this as an advantage, since it makes use of higher-order functions easier. [3] Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ...
Language elements Comments Each comment is preceded by a semicolon (;) and extends for the rest of the line. Some implementations allow comments to span multiple lines by wrapping them with a #|...|# (possibly nested). Other implementations provide a way of commenting out an entire s-expression by prepending it with #;.[4] A semicolon ( ; ) is a type of punctuation mark. ...
An S-expression (S stands for symbolic) is a convention for representing data or an expression in a computer program in a text form. ...
Variables Variables are dynamically typed. Variables are bound by a define, a let expression, and a few other Scheme forms. Variables bound at the top level with a define are in global scope. (define var1 value) Variables bound in a let are in scope for the body of the let. (let ((var1 value)) ... ; scope of var1 ...)
Functions 1 (define fun (lambda (arg1 arg2) ...)) 2 (define (fun arg1 arg2) ...) 3 (fun value1 value2) 4 (apply fun (list value1 value2)) Functions are first-class objects in Scheme. They can be arguments to other functions and be returned by them. They can be assigned to variables. For example a function with two arguments arg1 and arg2 is defined in line 1 and line 2 is an abbreviation of it. Line 3 shows how functions are applied. Note that the function being applied is in the first position of the list while the rest of the list contains the arguments. The apply function will take the first argument and apply it to a given list of arguments, so the previous function call can also be written as seen on line 4.
In Scheme, functions are divided into two basic categories: procedures and primitives. All primitives are procedures, but not all procedures are primitives. Primitives are pre-defined functions in the Scheme language. These include +, -, *, /, set!, car, cdr, and other basic procedures. Procedures are user-defined functions. In several variations of Scheme, a user can redefine a primitive. For example, the code In computer programming, operator overloading (less commonly known as operator ad-hoc polymorphism) is a specific case of polymorphism in which some or all of operators like +, = or == have different implementations depending on the types of their arguments. ...
(define (+ x y) (- x y)) actually redefines the + primitive to perform subtraction, rather than addition.
Lists Scheme uses the linked list data structure in the same form as it exists in Lisp. "list" builds a new linked list structure, for example: In computer science, a linked list is one of the fundamental data structures used in computer programming. ...
Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...
(list 1 2 3) (list (list 1 2) 3) " car" (pronounced: [kɑr] listen (help·
info)) gives the value of the head node of the list, for example: Introduced in the Lisp programming language, car (IPA [kar], just like the English word car) and cdr (IPA [kʌ dər] or [ku dər]) are primitive operations upon linked lists composed of cons cells. ...
Image File history File links Car. ...
(car (list 1 2 3)) gives 1 and (car (list (list 1 2) 3)) gives (1 2) " cdr" (pronounced "could-er" ['kədər listen (help·
info)] or ['kudər]) gives the list after the head node, for example: Introduced in the Lisp programming language, car (IPA [kar], just like the English word car) and cdr (IPA [kÊŒ dÉ™r] or [ku dÉ™r]) are primitive operations upon linked lists composed of cons cells. ...
Image File history File links Cdr. ...
(cdr (list 1 2 3)) gives (2 3) and (cdr (list (list 1 2) 3) gives (3) "cons" constructs a new list with a given car value and cdr list, for example: CONS, Connection-Oriented Network Service, is one of the two OSI stack network layer protocols, the other being CLNS (Connectionless Network Service). ...
(cons 1 (list 2 3)) gives (1 2 3) and (cons (list 1 2) (list 3)) gives ((1 2) 3) Each node in the linked list is a cons cell, also called a pair. As the name pair implies, a cons cell consists of two values: the first one is the car, and the second is the cdr. For Image File history File links Schemeboxandptr. ...
(list 1 2 3) there are three cons cells, or pairs. The first cons cell has the number 1 in the first slot, and a pointer to the second cons cell in the second. The second cons cell has the number 2 in the first slot, and a pointer to the third cons cell in the second slot. The third cons cell has the number 3 in the first slot and a null constant in the second slot. The null constant is usually represented by '() or (quote ()). The cons function constructs these cons cells, which is why (cons 1 (list 2 3)) gives the list (1 2 3) If both of the arguments are not lists, then a pair is created, represented with a dot. For example (cons 1 2) gives (1 . 2) where the cons cell consists of 1 and 2 in its slots instead of a pointer to another cons cell in its second slot.
The names of the two primitive operations for decomposing lists, car and cdr, originally come from assembly language macros for the IBM 704; they stood for "contents of address register" and "contents of decrement register" respectively.[citation needed] Introduced in the Lisp programming language, car (IPA [kar], just like the English word car) and cdr (IPA [kʌ dər] or [ku dər]) are primitive operations upon linked lists composed of cons cells. ...
The IBM 704, the first mass-produced computer with floating point arithmetic hardware, was introduced by IBM in April, 1956. ...
Data types Other common data types in Scheme besides functions and lists are: integer, rational, real, complex numbers, symbols, strings, and ports.[2] Most Scheme implementations also offer association lists, hash tables, vectors, arrays and structures.[citation needed] Since the IEEE Scheme standard and the R4RS Scheme standard, Scheme has asserted that all of the above types are disjoint, that is no value can belong to more than one of these types; however some ancient implementations of Scheme predate these standards such that #f and '() refer to the same value, as is the case in Common Lisp.[citation needed] The integers consist of the positive natural numbers (1, 2, 3, …) the negative natural numbers (−1, −2, −3, ...) and the number zero. ...
In mathematics, a rational number (or informally fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ...
In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ...
Wikibooks Algebra has more about this subject: Complex numbers In mathematics, a complex number is an expression of the form where a and b are real numbers, and i is a specific imaginary number, called the imaginary unit, with the property i 2 = −1. ...
In computer programming and some branches of mathematics, strings are sequences of various simple objects. ...
In computing, an associative array, also known as a map, lookup table, or dictionary, is an abstract data type very closely related to the mathematical concept of a function with a finite domain. ...
In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...
A vector in computing, specifically when talking about malicious code such as viruses or worms, is the method that this code uses to propagate itself or infect the computer and this sense is similar to, and derived from, its meaning in Biology. ...
In computer programming, an array, also known as a vector or list (for one-dimensional arrays) or a matrix (for two-dimensional arrays), is one of the simplest data structures. ...
Look up Structure in Wiktionary, the free dictionary. ...
Most Scheme implementations offer a full numerical tower as well as exact and inexact arithmetic.[2] In computing, numerical tower refers to the set of number types (datatypes that represent numbers) in a given programming language. ...
True and false are represented by #t and #f. Actually only #f is really false when a Boolean type is required, everything else will be considered true, including the empty list.[2] Symbols can be created in at least the following ways:
'symbol (string->symbol "symbol")
Equality Scheme has three different types of equality: "eq?" returns #t if its parameters represent the same data object in memory; "eqv?" is generally the same as eq? but treats some objects (eg. characters and numbers) specially so that numbers that are = are eqv? even if they are not eq?; equal? compares data structures such as lists, vectors and strings to determine if they have congruent structure and eqv? contents.[2]
Type dependent equivalence operations also exist in Scheme: string=?; compares two strings; char=? compares characters; = compares numbers.[2]
Control structures
Conditional evaluation (if test then-expr else-expr) The test expression is evaluated, and if the evaluation result is true (anything other than #f) then the then-expr is evaluated, otherwise else-expr is evaluated.
A form that is more convenient when conditionals are nested is cond:
(cond (test1 expr1) (test2 expr2) ... (else exprn)) The first expression for which the test evaluates to true will be evaluated. If all tests result in #f, the else clause is evaluated.
A variant of the cond clause is
(cond ... (test => expr) ...) In this case, expr should evaluate to a function that takes one argument. If test evaluates to true, the function is called with the return value of test.
Loops Loops in Scheme usually take the form of tail recursion. Scheme implementations are required to optimize tail calls so as to eliminate use of stack space where possible, so arbitrarily long loops can be executed using this technique.[2] In computer science, tail recursion is a special case of recursion that can be easily transformed into an iteration. ...
A classic example is the factorial function, which can be defined non-tail-recursively:
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) (factorial 5) ;; => 120 This is a direct translation of the mathematical recursive definition of the factorial: the factorial of zero (usually written 0!) is equal to 1, while the factorial of any greater natural number n is defined as n! = n * (n − 1)!.
However, plain recursion is by nature less efficient, since the Scheme system must maintain a stack to keep track of the returns of all the nested function calls. A tail-recursive definition is one that ensures that in the recursive case, the outermost call is one back to the top of the recurring function. In this case, we recur not on the factorial function itself, but on a helper routine with two parameters representing the state of the iteration:
(define (factorial n) (let loop ((total 1) (i n)) (if (= i 0) total (loop (* i total) (- i 1))))) (factorial 5) ;; => 120 A higher order function like map which applies a function to every element of a list, and can be defined non-tail-recursively: (define (map f lst) (if (null? lst) lst (cons (f (car lst)) (map f (cdr lst))))) (map (lambda (x) (* x x)) '(1 2 3 4)) ;; => (1 4 9 16) This can also be defined tail-recursively: (define (map f lst) (let loop ((lst lst) (res '())) (if (null? lst) (reverse res) (loop (cdr lst) (cons (f (car lst)) res))))) (map (lambda (x) (* x x)) '(1 2 3 4)) ;; => (1 4 9 16) In both cases the tail-recursive version is preferable due to its decreased use of space.
For basic looping, Scheme supports a simple do iterator construct:
(do ((<variable1> <init1> <step1>) ...) (<test> <expression> ...) <command> ...) For example: (let ((x '(1 3 5 7 9))) (do ((x x (cdr x)) (sum 0 (+ sum (car x)))) ((null? x) sum)))
Input/output Scheme has the concept of ports to read from or to write to.[2] R5RS defines two default ports, accessible with the functions current-input-port and current-output-port, which correspond to the Unix notions of stdin and stdout. Most implementations also provide current-error-port.
Examples
Hello world (begin (display "Hello, World!") (newline)) Scheme code can be found in the following articles: In mathematics, the arithmetic-geometric mean M(x, y) of two positive real numbers x and y is defined as follows: we first form the arithmetic mean of x and y and call it a1, i. ...
A Church integer is a representation of natural numbers as functions, invented by Alonzo Church as part of his lambda calculus. ...
Continuation passing style (CPS) is a term used within functional programming to describe a style of programming wherein functions never return. ...
This page is about the computer science continuation. ...
In computer science, currying is the technique of transforming a function taking multiple arguments into a function that takes a single argument (the first of the arguments to the original function) and returns a new function that takes the remainder of the arguments and returns the result. ...
This article lacks information on the importance of the subject matter. ...
The following is a list of hello world programs. ...
An infinite loop is a sequence of instructions in a computer program which loops endlessly. ...
In computer science, tail recursion is a special case of recursion that can be easily transformed into an iteration. ...
In providing services to people, and in computer science, transport and operations research a queue is a First-In-First-Out (FIFO) process — the first element in the queue will be the first one out. ...
In computing, a quine is a program (a form of metaprogram) that produces its complete source code as its only output. ...
See also Front cover Structure and Interpretation of Computer Programs (SICP) is a textbook published in 1985 about general computer programming concepts from MIT press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman. ...
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
Front cover How to Design Programs (HTDP) is a textbook from MIT Press on the systematic design of computer programs. ...
Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...
Programming languages are used for controlling the behavior of a machine (often a computer). ...
References Gerald Jay Sussman is the Matsushita Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT). ...
Guy Lewis Steele, Jr. ...
A digital object identifier (or DOI) is a permanent identifier (permalink) given to a World Wide Web file or other Internet document so that if its Internet address changes, users will be redirected to its new address. ...
ISSN, or International Standard Serial Number, is the unique eight-digit number applied to a periodical publication including electronic serials. ...
2006 (MMVI) is a common year starting on Sunday of the Gregorian calendar. ...
June 19 is the 170th day of the year (171st in leap years) in the Gregorian Calendar, with 195 days remaining. ...
A digital object identifier (or DOI) is a permanent identifier (permalink) given to a World Wide Web file or other Internet document so that if its Internet address changes, users will be redirected to its new address. ...
Richard P. Gabriel (b. ...
Kent M. Pitman is the President of HyperMeta, Inc. ...
Guy Lewis Steele, Jr. ...
Richard P. Gabriel (b. ...
Front cover Structure and Interpretation of Computer Programs (SICP) is a textbook published in 1985 about general computer programming concepts from MIT press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman. ...
External links |
Feeds |
Contact