- Type Predictes
- Numbers, Arithmetic Operators, and Functions
- Lambda Expressions
- Nested Definitions
- Mismatching Parentheses
- Using Too Many Parentheses
- Unnecessary Single Quotes
- Attempting to Modify Variables
- Debugging and Tracing
- You must use recursion rather than iteration.
- No assignment is permitted. Assignment is an imperative concept, based on the model of a stored memory machine, and it does not exist in pure functional languages. Scheme does have some imperative features, and those are the ones to avoid: set! , setcar! , setcdr! , and all other operations with named ending in "!" are not allowed.
- Do not use global variables--bound names with values that change over the life of your program. In fact, none of your bound names, whether global or local, should change in value over time. Global constants with values that never change are fine. For local names, think of them as names for common subexpressions that you wish to use in more than one place.
- The control structures you cannot use are do and begin . That still leaves you with plenty of control structures to work with, though. Here are some suggestions:
- For selection, use cond or if . The if function is a special case of cond . If you only use cond , you'll probably never miss begin .
- For iteration, use a named let . That means using recursion in spirit whenever you need to repeat a series of actions. Alternatively, you can define a separate recursive function if you prefer.
- For grouping a series of expressions into one sequence, use let (instead of begin ). This most commonly arises if you use an if instead of cond , which is one reason that cond is often preferred.
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, in cases where you do not want one or more arguments to be evaluated, non-numeric arguments must be preceded with a single quote to prevent their evaluation. The examples in the following sections should clarify this issue.
Scheme is a weakly typed language with dynamic type checking and lexical scope rules.
A Scheme program consists of a set of function definitions. There is no structure imposed on the program and there is no main function. Function definitions may be nested. A Scheme program is executed by submitting an expression for evaluation. Functions and expressions are written in the form
(function_name arguments)
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
(+ 3 (* 4 5))
Some additional examples:
(+ 3 5) (fac 6) (append '(a b c) '(1 2 3 4))
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. The third presupposes the existence of the function append to which two lists are presented. Note that the single quote in front of each argument in this third example is required to prevent the (eager) evaluation of the lists. Without the use of those two single quotes, both list arguments would themselves be interpreted as function applications. Note the uniform use of the standard prefix notation for functions.
Among the constants (atoms) provided in Scheme are numbers, the boolean constants #t and #f , the empty list (), and strings. Here are some examples of atoms and a string:
A, abcd, THISISANATOM, AB12, 123, 9Ai3n, "A string"
Atoms are used for variable names and names of functions. Scheme is case-insensitive, and it is common to use lower case or mixed case for readability (despite the examples in the text). Please do not write your code in all caps!
Some of the simple types provided in Scheme are:
Type Values boolean #t, #f number integers, floating point, rationals, complex, etc. symbol character sequences (unevaluated atoms) The basic composite types provided in Scheme are:
Type Values dotted pair a simple two-item record, not discussed here list parenthesized, space-separated sequence of items function all functions and procedures The list is the most frequently used composite data structure in Scheme. A list is an ordered set of elements consisting of atoms or other lists. Lists are enclosed by parentheses with elements separated by white space, as in LISP. Here are some examples of lists:
(A B C) (138 abcde 54 18) (SOMETIMES (PARENTHESIS (GET MORE)) COMPLICATED) ()
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 ())) .
Type Predicates
A predicate is a function that returns a boolean result. By convention, Scheme predicates have names that end in a question mark ( ? ). A type predicate is a boolean function that is used to determine membership in a given type. Since Scheme is weakly typed, Scheme provides a wide variety of type checking predicates. Here are some of them.
Predicate True If (boolean? arg ) arg is a boolean (number? arg ) arg is a number (pair? arg ) arg is a pair (a list or dotted pair) (list? arg ) arg is a list (symbol? arg ) arg is a symbol (procedure? arg ) arg is a function (null? arg ) arg is empty list (zero? arg ) arg is zero (odd? arg ) arg is odd (even? arg ) arg is even Numbers, Arithmetic Operations, and Functions
Scheme number data type includes the integer, rational, real, and complex numbers. Some Examples:
Scheme Expression Operational Meaning (+ 4 5 2 7 5 2) 4 + 5 + 2 + 7 + 5 + 2 (/ 36 6 2) ((36 / 6) / 2) = 3 (+ (* 2 2 2 2 2) (* 5 5)) 2 5 + 5 2 The basic arithmetic operators are:
Symbol Operation + addition - subtraction * multiplication / division (can give integer, rational, or real result, depending on arguments) quotient integer division modulo modulus Lists are the basic structured data type in Scheme. Note that in the following examples the parameters are quoted. The quote prevents Scheme from evaluating the arguments. Here are examples of some of the built in list handling functions in Scheme. cons takes two arguments and returns a pair (a list).
(cons '1 '(2 3 4)) is (1 2 3 4) (cons '(1 2 3) '(4 5 6)) is ((1 2 3) 4 5 6) (cons '1 '2) is (1 . 2)
The last example is a dotted pair and the others are lists.
car returns the first member of a list or dotted pair.
(car '(123 245 564 898)) is 123 (car '(first second third)) is first (car '(this (is no) more difficult)) is this
cdr returns the list without its first item, or the second member of a dotted pair.(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
null? returns #t if the object is the empty list, () . It returns the null list, () (which is the same as #f ), if the object is anything else. list returns a list constructed from its arguments.
(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 returns the length of a list.(length '(1 3 5 9 11)) is 5
reverse returns the list reversed.(reverse '(1 3 5 9 11)) is (11 9 5 3 1)
append returns the concatenation of two lists.(append '(1 3 5) '(9 11)) is (1 3 5 9 11)
The standard boolean objects for true and false are written #t and #f . However, Scheme treats any value other than #f as true and only #f as false (Some implementations, such as MIT Scheme, treat the empty list () as if it were the same as #f ). Scheme provides not , and , and or , as well as several tests for equality among objects.
Relational Operators
The most common comparison operator is equal? which works for all objects. Scheme also provides eqv? (which works for everything but lists or pairs) and eq? (which only works correctly for atoms), but equal? is recommended to beginners for all comparisons.
For numeric values, the normal relational operator symbols are used: = , < , , and >= . Since prefix notation is used uniformly in Scheme, when you mean to test x ( .
For string values, predicates that use a lexicographic ordering exist: string=? , string? , and string>=? . Also, for every stringop? predicate, there is a case-insensitive version called string-ciop? (e.g., string-ci=? performs a case-insensitive equality comparison).
Conditional expressions are of the form:
(if test-exp then-exp) (if test-exp then-exp else-exp)
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 evaluated and its result is returned; otherwise, the else-exp is evaluated and its result is returned.
Some examples include:
(if (> n 0) (= n 10)) (if (null? lst) lst (cdr lst) )
In the second example above, lst is the then-exp while (cdr lst) is the else-exp .
Scheme has an alternative conditional expression that is more like a multi-way if statement (or a case statement) in that several test-result pairs may be listed. It takes one of two forms:
(cond (test-exp1 exp . ) (test-exp2 exp . ) . ) (cond (test-exp exp . ) . (else exp . ) )
The following conditional expressions are equivalent.
(cond ; Test condition ; Result to return ((= n 10) m) ((> n 10) (* n m)) (( < n 10) 0) ) (cond ((= n 10) m) ((>n 10) (* n m)) (else 0) )
To aid readability, many Scheme programmers use square brackets ( [ . ] ) around each test/value pair in a cond expression:
(cond ; Test condition ; Result to return [(= n 10) m] [(> n 10) (* n m)] [( < n 10) 0] ) (cond [(= n 10) m] [(>n 10) (* n m)] [else 0] )
Scheme will only match right square brackets with left square brackets, and right parentheses with left parentheses, so these delimiters can also aid in detecting incorrectly balanced parentheses within any particular branch of the cond expression. Otherwise, they mean the same thing that parentheses do.
Definition expressions bind names and values and are of the form:
(define id exp)
Here is an example of a definition.
(define pi 3.14)
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. Definitions of this form are most often used to introduce global constants.
An alternative form of definition expression is used to bind a name to a function value:
(define (id formal-params . ) body )
Here, id is the name being introduced. The list of zero or more formal-params determines both the number of arguments the new function will take, and their formal parameter names. The body expression defines the meaning of the function.
Here is a definition of a squaring function.
(define (square x) (* x x) )
Here is an example of an application of the function (exact output may differ depending on the Scheme implementation being used):
1 ]=> (square 3) ;Value: 9
Here are function definitions for the factorial function, gcd function, Fibonacci function and Ackerman's function.
(define (fac n) (cond [(= n 0) 1] [else (* n (fac (- n 1))) ] ) ) (define (fib n) (cond [(= n 0) 0] [(= n 1) 1] [else (+ (fib (- n 1)) (fib (- n 2))) ] ) ) (define (ack m n) (cond [(= m 0) (+ n 1)] [(= n 0) (ack (- m 1) 1)] [else (ack (- m 1) (ack m (- n 1)))] ) ) (define (gcd a b) (cond [(= a b) a] [(> a b) (gcd (- a b) b)] [else (gcd a (- b a))] ) )
Here are definitions of the list processing functions, sum, product, length and reverse. You'll notice that many function definitions in Scheme are recursive, and are written as cond expressions, where the base case(s) are listed first, followed by the recursive case(s). This is an extremely common pattern, especially for list processing functions.
(define (sum lst) (cond [(null? lst) 0] [else (+ (car lst) (sum (cdr lst)))] ) ) (define (product lst) (cond [(null? lst) 1] [else (* (car lst) (product (cdr lst)))] ) ) (define (length lst) (cond [(null? lst) 0] [else (+ 1 (length (cdr lst)))] ) ) (define (reverse lst) (cond [(null? lst) ()] [else (append (reverse (cdr lst)) (list (car lst)))] ) )
Lambda Expressions
In addition to top-level function definitions introduced using define it is also possible to define custom functions "in-line" for various purposes. This is done through a lambda expression. Lambda expressions are unnamed functions of the form:
(lambda (id . ) exp )
The (possibly empty) list of symbols (id . ) is the list of formal parameters to the annonymous function, and exp represents the body of the lambda expression. Here are two examples the application of lambda expressions.
((lambda (x) (* x x)) 3) is 9 ((lambda (x y) (+ x y)) 3 4) is 7
In both of these examples, the lambda expression appears as the first element in a function application, and thus denotes the function to apply. You can also bind the result of a lambda expression to a name:
(define square (lambda (x) (* x x)))
This is exactly the same as the alternative form of define presented earlier. In fact, the "function form" of define presented above is just shorthand for using a lambda expression; both of the following are equivalent:
(define (name params) body) ; just shorthand for . (define name (lambda (params) body))
What good are lambda expressions? They are most commonly used for two purposes:
Defining one-time-use (or "throw away") functions that are being passed as custom values to higher-order functions.
Nested Definitions
Scheme provides for local definitions by permitting definitions to be nested. Local definitions are introduced using let , let* and letrec . Each of these forms may introduce a sequence of local 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, which requires all of the definitions to be independent. Here are some examples:
; 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) )
As with cond expressions, Scheme programmers often use square brackets around each name/value pair in a let declaration list for readability and improved error detection:
; 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) )
Think of a let expression as a local declaration block. The first item in the let is a list of name-value pairs (note the way the parentheses are written in the examples here). The first value in each pair is a new name to introduce, and the second is the value to bind to that name. Lexical scoping rules are used, so "redefining" an existing name really introduces a new "local" name that hides the outer definition (which will once again be visible after the end of the let expression).
let* is similar in structure to let except for the way the values are evaluated. In let* , the values and bindings are computed sequentially, which means that later definitions may depend on the earlier ones.
(let* ( [x 10] [y (* 2 x)] ) ; Not legal for "let" (* x y) )
In letrec , the bindings are in effect while values are being computed to permit mutually recursive definitions. As an illustration of local definitions here is an 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.
(define (isort lst) (letrec ( ; Only one local definition: insert [insert (lambda (x l) (cond [(null? l) (list x)] [(
In this example, letrec is used since insert is recursively defined.
Let s may be nested. For example:
(let ( [a 3] [b 4] ) ; The body of the first let (let ( [double (* 2 a)] [triple (* 3 b)] ) ; The body of the second let (+ double triple) ) )
This let example produces the value 18 .
(+ 3 (read))
returns the sum of 3 and the next item from the input. A succeeding call to will return the next item from the standard input, thus, is not a true function. -->
The basic output operation in Scheme is called display (the write and print functions are similar, with minor differences in the way they format various types of values). Note that in DrScheme these functions are only available at the "Advanced Student" language level and above, since they produce side-effects. The function display prints its argument to the standard output.
(display (+ 3 5))
This expression displays the result of the addition expression. Display prints out all forms of Scheme data, including human-readable representations of lists. It also prints character strings (leaving out the surrounding double quotes). Most plain text output can be produced using just display and the operation (newline) , which simply prints a new line character on standard output.
One powerful functional for dealing with lists is map . The function map takes two arguments: a function to apply, and a list of values. It returns a new list which is the result of applying its first argument to each element of its second argument.
1 ]=> (map odd? '(2 3 4 5 6)) ;Value: (() #t () #t ())
Here is another example:
(define (dbl x) (* 2 x)) (map dbl '(1 2 3 4))
If the function being passed into map is not generally useful and you do not want to go to the trouble of creating a separate, stand-alone definition for it, you can use a lambda expression instead:
(map (lambda (x) (* 2 x)) '(1 2 3 4))
Actually, in Scheme, map can be used on functions of any arity (that is, any number of arguments), as long as you provide the correct number of arguments:
1 ]=> (map + '(1 2 3 4) '(5 6 7 8)) ;Value: (6 8 10 12)
Some other powerful higher-order functions for manipulating lists include:
- there-exists? takes a list and a predicate and returns #t if the predicate is true for any element of the list (and () otherwise).
- list-search-positive takes a list and a predicate, and returns the first element in the list for which the predicate is true.
- list-search-negative is similar, but looks for the first element where the predicate is false.
- for-all? takes a list and a predicate and returns #t if the predicate is true for every element of the list (and () otherwise).
- list-transform-positive takes a list and a predicate, and returns a list of all elements for which the predicate is true.
- list-transform-negative is similar, but looks for values where the predicate is false.
- for-each is just like map , except that for-each is guaranteed to evaluate its given function on the lists in order from first to last, while map does not guarantee the order of evaluation (and usually operates on the lists you give it from the rear forward instead). For purely functional operations, there is no difference between for-each and map , but if you are generating output (to standard output or a file) as a side-effect of the function you pass in, then for-each will give you the ordering you expect.
- reduce takes a binary operation, an initial value, and a list, and successively applies the binary operator "in between" pairs of elements in the list, accumulating a result. For example, (reduce + 0 '(1 2 3 4)) produces 10. reduce is left associative, and only uses the initial value if the given list is empty (in which case the initial value is the answer produced).
- reduce-right is the right-associative version of reduce .
- fold-left is like reduce , except that it always uses the given initial value to start off the sequence of evaluation.
- fold-right is the right-associative version of fold-left .
The four most common errors that beginning Scheme programmers in this course make are:
- Mismatching parentheses.
- Using too many parentheses.
- Adding single quotes where they shouldn't be used.
- Attempting to modify variables "in place" (an imperative idea) instead of programming functionally.
If you are using DrScheme, set the language level to "Intermediate Student with lambda" (or a more restricted teaching language--use the Language->Choose Language. menu command). DrScheme enforces restrictions on how you use many of Scheme's features and will give specific help on these types of errors when they occur. In addition, this setting will ensure that you do not use any features that use mutable state (i.e., that force a variable's value to change using imperative features).
(a b c) . When executed, however, the second example produces this error:
;The object (a b c) is not applicable.
The "not applicable" error message is the tell-tale sign that there are too many parentheses. In the second example, first (cons 'a '(b c)) is evaluated, giving the result (a b c) . However, this expression appears as the first element inside the extra set of parentheses. Scheme dutifully interprets this extra set of parentheses as indicating another function application, and attempts to invoke the first element (with no arguments). Since the list (a b c) does not represent a function that can be invoked (or "applied"), the error message is generated.
If you receive this error message, take note of the value that Scheme is trying to apply, which may give some indication of where in your program the extra parentheses are located. Also, be sure you know exactly how many parentheses should be used in a given expression--don't just throw more parentheses in to be thorough (unlike in C++ or Pascal), since anything other than exactly the right amount of parentheses will cause problems.
Unnecessary Single Quotes
The general rule of thumb is to use single quotes only when you are writing a literal value (like a hard-coded constant) that you do not want Scheme to evaluate or interpret.
Attempting to Modify Variables
For many programmers who are used to programming in imperative languages, the "habit" of modifying or updating a variable's value is a hard one to give up. Often, it is tempting to think of an imperative solution where a single list variable gets "added to" over an over, or where a numeric result accumulates work over many iterations. When one tries to encode these imperative concepts into Scheme, trouble invariably ensues.
Instead, remember that in programming for 5314, variables should be immutable--once a value is bound to a name, that value never changes. Instead, one most often reflects a "change" in some conceptual value by passing the new value as a parameter in a new function application, rather than by attempting to change the "old" value. It also helps to think of a recursive solution to a problem before trying to write the code, rather than starting with an iterative approach and trying to write an "equivalent" Scheme implementation.
DrScheme provides a Stepper that can be used to interactively step through the evaluation of any expression. To use the stepper, make sure that you have the language level set to a restricted subset of Scheme between "Beginner" and "Intermediate Student with lambda" (more advanced language levels, including full R5RS Scheme, do not support the stepper).
Suppose you have defined your own function called dbl and you would like to trace its execution on a sample value, like 13. If your already have a definition for dbl in the definitions window, just add the expression you want to trace to the bottom of the definitions window:
(define (dbl x) (* 2 x)) ; The expression to step through (dbl 13)
Now, press the Step button at the top of the window. The Step button starts the Stepper, which shows the evaluation of a program as a series of small steps. Each evaluation step replaces an expression in the program with an equivalent one using the evaluation rules of DrScheme. For example, a step might replace (* 2 x ) with (* 2 13 ) . Another step might replace this S-expression with 26 . These are the same rules used by DrScheme to evaluate a program. Clicking Step opens a new window that contains the program from the definitions window, plus five new buttons: Home, |< Application, < Step, Step >, and Application >|. Clicking Step > performs a single evaluation step, clicking < Stepretraces back a single step, and clicking Home returns to the initial program. Clicking Application >| jumps forward to the next top-level expression in the definitions window, and | < Applicationreturns to the previous one.
One important note: The Stepper has trouble with test cases in the current version of DrScheme. There are two ways around this limitation, however. First, you can move the expression you wish to trace earlier in your source file, and/or move your test cases closer toward the end. The Stepper will work fine on expressions it evaluates before it reaches your first test case. Second, you can instead temporarily comment out any test cases appearing before the expression to place--just place the cursor at the beginning of the line containing the test case box and add a semicolon in front of it. If you use the second approach, be sure to uncomment your test cases once you are done stepping so that you will get credit for them in program submissions!
display expressions) throughout their code. This technique, which allows one to take a "divide and conquer" approach to locating defects, can be very effective.
If you are primarily interested in tracing the execution of your code rather than seeing the values of internal variables, however, the trace function can be very useful. It takes a single function name as a parameter, and causes the interpreter to print out a diagnostic message on entry to and exit from every invocation of the given function (including both the arguments and the produced return value). You can interactively turn tracing on or off (using untrace ) for individual functions, or place these calls directly in your source file so tracing is turned on for problem operations every time new definitions are reloaded. If trace provides too much information, you can use trace-entry to only get messages when the given function is entered, or trace-exit to only get messages when the given function returns. Finally, the break function is just like trace , except that it halts the program in the interactive debugger instead of printing a diagnostic ( break , unbreak , break-entry , and break-exit are similar to their trace counterparts).
