Many of you have been frustrated because of Scheme's apparent lack of several features you've come to rely on in your programs: sequencing, input, output, and references (mutable variables). We will discuss these in this lecture.
Most programming languages offer a way of telling a program what order to to execute statements and expressions.
In Pascal and C, for example, the semicolon, indicates sequencing and separates statements that are to be executed sequentially. You can think of it as a high-level operator if you want that connects statements.
Sometimes, we care about order and sometimes we don't. One of the greatest barriers to parallel programming is artificial sequentiality introduced by the programmer. However, when you need things to happen in a certain order, there must be a way of indicating that order. Sequencing is primarily required when statements have side effects: they cause some state change to the program other than through their own return value. Sequencing and side effects go hand-in-hand with programming language design.
Perhaps the best example of a statement that must be executed in a certain order are input and output statements.
Some languages rely heavily on sequenced statements, each with side effects. The paradigm is one of "do this, then do that, then do this other thing, ...." This is known as the imperative paradigm for programming and is the one you were probably most familiar with before this course.
In addition to the imperative paradigm, there is also the functional paradigm. This relies not on carefully-sequenced side effects but on expression evaluation. The model isn't "do this", but "evaluate this". This is the model for Scheme, LISP, Haskell, ML, and other functional programming languages
There are other programming paradigms besides imperative and function. The declarative paradigm is based on declaring facts and rules, then asking questions. You don't program in declarative languages by giving the computer a set of steps to execute: you give it facts and rules, then it figures out how best to answer the questions you ask. Imagine being able to tell the computer how chess pieces move, then being able to ask it what the legal moves are for any given board configuration. That's what declarative programming is like.
In Scheme, we can introduce order in several ways. The most explicit is the begin expression:
(begin
<expr_1>
...
<expr_n>
)
The begin expression guarantees that Scheme will execute the expressions inside it in order one after the other.
For example, we can write:
(begin
(display "Here is my answer: ")
(display (+ 2 4 (* 4 5)))
)
Here is my answer: 26
In this example, we also introduce the display procedure which prints its argument on the console. Another procedure newline can be used to force a line break:
(begin
(display "Here is my answer: ")
(newline)
(display (+ 2 4 (* 4 5)))
)
Here is my answer:
26
We can use begin to create a function not unlike the for statement in shell programming languages:
(define for-each
(lambda (proc lst)
(if (null? lst)
'done
(begin
(proc (car lst))
(for-each proc (cdr lst))))))
This function performs an operation on each member of a list in order. The list can, of course, be given as a literal, but may generated by another function.
We can use the for-each procedure to create a procedure which displays each member of a list in order on a single line:
(define displayln
(lambda lst
(begin
(for-each display lst)
(newline))))
(displayln "The answer is: " (+ 3 4 5))
The answer is: 12
Its turns out that the begin expression in the last procedure is not really necessary. We could have written it like this:
(define displayln
(lambda lst
(for-each display lst)
(newline)
))
(displayln "The answer is: " (+ 3 4 5))
The answer is: 12
The reason we can get away with this is that lambda expressions can have multiple expressions in their bodies. Only the value of the last expression is returned as the result of the function.
In addition, to lambda expressions, the bodies of let and letrec expressions and the consequents of cond, case, and variant-case expressions can also take multiple expressions without being enclosed in a begin expression.
Now that we know about output functions and sequencing, we can add output functions to functions for debugging purposes:
(define fact
(lambda (n)
(displayln "Entering fact with n = " n)
(let ((ans (if (zero? n)
1
(* n (fact (- n 1))))))
(displayln "Returning from fact with " ans)
ans)))
(fact 5)
Entering fact with n = 5
Entering fact with n = 4
Entering fact with n = 3
Entering fact with n = 2
Entering fact with n = 1
Entering fact with n = 0
Returning from fact with 1
Returning from fact with 1
Returning from fact with 2
Returning from fact with 6
Returning from fact with 24
Returning from fact with 120
120
There are other I/O statements you should be aware of:
For example, we can use read and write to create out own read-eval-print loop:
(define read-eval-print
(lambda ()
(display "--> ")
(write (eval (read) user-initial-environment)) ;; different from book
(newline)
(read-eval-print)))
(read-eval-print)
--> (+ 2 3)
5
--> (* 4 5)
20
--> (cdr '(3 4 5))
(4 5)
--> (cdr 4)
;The object 4, passed as the first argument to cdr, is not the correct type.
;To continue, call RESTART with an option number:
; (RESTART 2) => Specify an argument to use in its place.
; (RESTART 1) => Return to read-eval-print level 1.
We use display to print the prompt since we don't want it to have quotes around it. We use read to read entire expressions. We use write to print to results so that they contain relevant information such as quotes when they are printed out:
(read-eval-print)
--> "3 4 5"
"3 4 5"
-->
foreach, consider the three
functions map, apply, and foreach.
How are they different? How are they alike?>/li>
Besides I/O, the most common form of side effect is changing the values of variables. If a particular piece of data can be changed, it is said to be mutable.
Mutable data and assignment statements are an integral part of imperative programming, which is why your first instinct coming from your background in imperative languages is to think in these terms.
In functional programming languages, explicitly mutating data is much less common. In fact, it should be avoided whenever possible. Remember, assignment is a side effect, and side effects mean sequencing. Side effects and sequencing mean code that is more difficult to understand, process, or execute efficiently. Still, making permanent state changes to data is sometimes necessary, and most functional programming languages make some provision for assignment as (hopefully infrequently) needed.
The assignment operator in Scheme is set!:
(define a 10)
(define dec-a
(lambda (x)
(set! a (- a x))
))
The function dec-a decrements the variable a when it is called. Notice here the problem now created for the programmer. When you call dec-a, the variable a changes, even though you don't pass a to the function or have any other way of knowing that this happens other than documentation or a descriptive name (or by reading all of the source code and trying to keep it all straight in your head!).
To alert each other to when functions modify data, Scheme programmers have adopted the convention of using an exclamation point (!) at the end of the name of functions that modify data. So, perhaps we could have named our function "dec-a!" to be more descriptive.
Other assignment operators in Scheme include set-car! and set-cdr!:
(set-car! a 10) |
Sets the car of the pair a to 10. |
(set-cdr! a 20) |
Sets the cdr of the pair a to 20. |
(set-cdr! p p) does to it? (I wouldn't advise typing it in.)Once you introduce mutable data into a programming language, you now have the problem of controlling who has access to that data, especially who can changing it. Imperative languages go to great lengths to provide this control through modules, classes, etc. Although less common in functional programming languages (but increasingly being added), you can still use scoping rules to control data access.
Last updated at 9:54 am on Friday, August 27, 2004.