In functional programming, parameters play the same role that assignments do in imperative programming. Scheme is an applicative programming language. By applicative, we mean that a Scheme function is applied to its arguments and returns the answer. Scheme is a descendent of LISP. It shares most of its syntax with LISP but it provides lexical rather than dynamic scope rules. LISP and Scheme have found their main application in the field of artificial intelligence.
The purely functional part of Scheme has the semantics we expect of mathematical expressions. One word of caution: Scheme evaluates the arguments of functions prior to entering the body of the function (eager evaluation). This causes no difficulty when the arguments are numeric values. However, non-numeric arguments must be preceded with a single quote to prevent evaluation of the arguments. The examples in the following sections should clarify this issue.
Scheme is a weakly typed language with dynamic type checking and lexical scope rules.
This syntax differs from the usual mathematical syntax in that the function name is moved inside the parentheses and the arguments are separated by spaces rather than commas. For example, the mathematical expression 3 + 4 * 5 is written in Scheme as(function_name arguments)
(+ 3 (* 4 5))
Scheme SyntaxThe star `*' following a syntactic category indicates zero or more repetitions of elements of that category thus Scheme permits lambda abstractions of more than one parameter. Scheme departs from standard mathematical notation for functions in that functions are written in the form (Function-name Arguments...) and the arguments are separated by spaces and not commas.E in Expressions
I in Identifiers (variables)
K in ConstantsE ::= K | I | (E_0 E^*) | (lambda (I^*) E_{2}) | (define I E')
For example,
The first expression is the sum of 3 and 5, the second presupposes the existence of a function fac to which the argument of 6 is presented and the third presupposes the existence of the function append to which two lists are presented. Note that the quote is required to prevent the (eager) evaluation of the lists. Note uniform use of the standard prefix notation for functions.(+ 3 5) (fac 6) (append '(a b c) '(1 2 3 4))
Atoms are used for variable names and names of functions. A list is an ordered set of elements consisting of atoms or other lists. Lists are enclosed by parenthesis in Scheme as in LISP. Here are some examples of lists.A, abcd, THISISANATOM, AB12, 123, 9Ai3n, "A string"
Lists are can be represented in functional notation. There is the empty list represented by () and the list construction function cons which constructs lists from elements and lists as follows: a list of one element is (cons X ()) and a list of two elements is (cons X (cons Y ())).(A B C) (138 abcde 54 18) (SOMETIMES (PARENTHESIS (GET MORE)) COMPLICATED) ()
TYPE & VALUES
boolean & #T, #F
number & integers and floating point
symbol & character sequences
pair & lists and dotted pairs
procedure & functions and procedures
TYPE & REPRESENTATION & VALUES
list & (space separated sequence of items) & any
in function& defined in a later section &
in
PREDICATE & CHECKS IF
(boolean? arg ) & arg is a boolean
in (number? arg ) & arg is a number
in (pair? arg ) & arg is a pair
in (symbol? arg ) & arg is a symbol
in (procedure? arg ) & arg is a function
in (null? arg ) & arg is empty list
in (zero? arg ) & arg is zero
in (odd? arg ) & arg is odd
in (even? arg ) & arg is even
in
Some Examples:
(+ 4 5 2 7 5 2) - is equivalent to \( 4 + 5 + 2 + 7 + 5 + 2 \) (/ 36 6 2) - is equivalent to \(\frac{\frac{36}{6}}{2} \) (+ (* 2 2 2 2 2) (* 5 5)) - is equivalent to \( 2^{5} + 5^{2} \)
SYMBOL & OPERATION
+ & addition
in - & subtraction
in * & multiplication
in / & real division
in quotient & integer division
in modulo & modulus
in
The first example is a dotted pair and the others are lists. \marginpar{expand} Either lists or dotted pairs can be used to implement records.(cons '1 '2) is (1 . 2) (cons '1 '(2 3 4)) is (1 2 3 4) (cons '(1 2 3) '(4 5 6)) is ((1 2 3) 4 5 6)
(car '(123 245 564 898)) is 123 (car '(first second third)) is first (car '(this (is no) more difficult)) is this
(cdr '(7 6 5)) is (6 5) (cdr '(it rains every day)) is (rains every day) (cdr (cdr '(a b c d e f))) is (c d e f) (car (cdr '(a b c d e f))) is b
(list 'a) is (a) (list 'a 'b 'c 'd 'e 'f) is (a b c d e f) (list '(a b c)) is ((a b c)) (list '(a b c) '(d e f) '(g h i)) is ((a b c)(d e f)(g h i))
(length '(1 3 5 9 11)) is 5
(reverse '(1 3 5 9 11)) is (11 9 5 3 1)
(append '(1 3 5) '(9 11)) is (1 3 5 9 11)
SYMBOL & OPERATION not & negation
and & logical conjunction
or & logical disjunction
SYMBOL & OPERATION
= & equal (numbers)
(< ) & less than
(<= ) & less or equal
(> ) & greater than
(>= ) & greater or equal
eq? & args are identical
eqv? & args are operationally equivalent
equal? & args have same structure and contents
The test-exp is a boolean expression while the then-exp and else-exp are expressions. If the value of the test-exp is true then the then-exp is returned else the else-exp is returned. Some examples include:(if test-exp then-exp) (if test-exp then-exp else-exp).
(if (> n 0) (= n 10)) (if (null? list) list (cdr list))The list is the then-exp while (cdr list ) is the else-exp. Scheme has an alternative conditional expression which is much like a case statement in that several test-result pairs may be listed. It takes one of two forms:
The following conditional expressions are equivalent.(cond (test-exp1 exp ...) (test-exp2 exp ...) ...) (cond (test-exp exp ...) ... (else exp ...))
(cond ((= n 10) (= m 1)) ((> n 10) (= m 2) (= n (* n m))) ((< n 10) (= n 0)))
(cond ((= n 10) (=m 1)) ((> n 10) (= m 2) (= n (* n m))) (else (= n 0)))
Here is an example of a definition.(define id exp)
This defines pi to have the value 3.14. This is not an assignment statement since it cannot be used to rebind a name to a new value.(define pi 3.14)
The expression (id...) is the list of formal parameters and exp represents the body of the lambda expression. Here are two examples the application of lambda expressions.(lambda (id...) exp )
Here is a definition of a squaring function.((lambda (x) (* x x)) 3) is 9 ((lambda (x y) (+ x y)) 3 4) is 7
Here is an example of an application of the function.(define square (lambda (x) (* x x)))
1 ]=> (square 3) ;Value: 9Here are function definitions for the factorial function, gcd function, Fibonacci function and Ackerman's function.
%(define fac (lambda (n) (if (= n 0) 1 (* n (fac (- n 1)))))) %
%(define fib (lambda (n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))) %
%(define ack (lambda (m n) (if (= m 0) (+ n 1) (if (= n 0) (ack (- m 1) 1) (ack (- m 1) (ack m (- n 1))))))) %
Here are definitions of the list processing functions, sum, product, length and reverse.(define gcd (lambda (a b) (if (= a b) a (if (> a b) (gcd (- a b) b) (gcd a (- b a))))))
%(define sum (lambda (l) (if (null? l) 0 (+ (car l) (sum (cdr l)))))) %
%(define product (lambda (l) (if (null? l) 1 (* (car l) (sum (cdr l)))))) %
(define length (lambda (l) (if (null? l) 0 (+ 1 (length (cdr l)))))) (define reverse (lambda (l) (if (null? l) nil (append (reverse (cdr l)) (list (car l))))))
Scheme SyntaxNote that there may be a sequence of bindings. For purposes of efficiency the bindings are interpreted differently in each of the ``let'' functions. The let values are computed and bindings are done in parallel, this means that the definitions are independent. The let* values and bindings are computed sequentially, this means that later definitions may be dependant on the earlier ones. The letrec bindings are in effect while values are being computed to permit mutually recursive definitions. As an illustration of local definitions here is a definition of insertion sort definition with the insert function defined locally. Note that the body of isort contains two expressions, the first is a letrec expression and the second is the expression whose value is to be returned.E in Expressions
I in Identifier(variable)
...
B in Bindings
...E ::= ...| (lambda (I...) E... ) |
(let B_0 E_0) | (let* B_{1} E_{1}) | (letrec B_{2} E_{2}) |...
B ::= ((I E)...)
{letrec is used since insert is recursively defined. Here are some additional examples:(define isort (lambda (l) (letrec ((insert (lambda (x l) (if (null? l) (list x) (if (<= x (car l)) (cons x l) (cons (car l) (insert x (cdr l)))))))) (if (null? l) nil (insert (car l) (isort (cdr l)))))))
Lets may be nested. For example, the expression; this binds x to 5 and yields 10 (let ((x 5)) (* x 2)) ; this bind x to 10, z to 5 and yields 50. (let ((x 10) (z 5)) (* x z))
(let ((a 3) (b 4) (let ((double (* 2 a)) (triple (* 3 b))) (+ double triple))))is 18.
returns the sum of 3 and the next item from the input. A succeeding call to {\tt read} will return the next item from the standard input, thus, {\tt read} is not a true function. The function {\bf display} prints its argument to the standard output. For example,(+ 3 (read))
displays the result of the previous function. The following is an example of an interactive program. It displays a prompt and returns the next value from the standard input.(display (+ 3 (read)))
(define prompt-read (lambda (Prompt) (display Prompt) (read)))
1 ]=> (apply + '(7 5)) ;Value: 12 1 ]=> (apply max '(3 7 2 9)) ;Value: 9
1 ]=> (map odd? '(2 3 4 5 6)) ;Value: (() #T () #T ())
1 ]=> (define dbl (lambda (x) (* 2 x))) ;Value: dbl 1 ]=> (map dbl '(1 2 3 4)) ;Value: (2 4 6 8) 1 ]=>
1 ]=> (map (* 2) '(1 2 3 4)) ;Value: (2 4 6 8) 1 ]=>
(define checkbook (lambda () ; This check book balancing program was written to illustrate ; i/o in Scheme. It uses the purely functional part of Scheme. ; These definitions are local to checkbook (letrec ; These strings are used as prompts ((IB "Enter initial balance: ") (AT "Enter transaction (- for withdrawal): ") (FB "Your final balance is: ") ; This function displays a prompt then returns ; a value read. (prompt-read (lambda (Prompt) (display Prompt) (read))) ; This function recursively computes the new ; balance given an initial balance init and ; a new value t. Termination occurs when the ; new value is 0. (newbal (lambda (Init t) (if (= t 0) (list FB Init) (transaction (+ Init t))))) ; This function prompts for and reads the next ; transaction and passes the information to newbal (transaction (lambda (Init) (newbal Init (prompt-read AT))))) ; This is the body of checkbook; it prompts for the ; starting balance (transaction (prompt-read IB)))))
Send comments to: webmaster@cs.wwc.edu