| 1 | @c -*-texinfo-*- |
| 2 | @c This is part of the GNU Guile Reference Manual. |
| 3 | @c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2012 |
| 4 | @c Free Software Foundation, Inc. |
| 5 | @c See the file guile.texi for copying conditions. |
| 6 | |
| 7 | @node Hello Scheme! |
| 8 | @chapter Hello Scheme! |
| 9 | |
| 10 | In this chapter, we introduce the basic concepts that underpin the |
| 11 | elegance and power of the Scheme language. |
| 12 | |
| 13 | Readers who already possess a background knowledge of Scheme may happily |
| 14 | skip this chapter. For the reader who is new to the language, however, |
| 15 | the following discussions on data, procedures, expressions and closure |
| 16 | are designed to provide a minimum level of Scheme understanding that is |
| 17 | more or less assumed by the chapters that follow. |
| 18 | |
| 19 | The style of this introductory material aims about halfway between the terse |
| 20 | precision of R5RS and the discursiveness of existing Scheme tutorials. For |
| 21 | pointers to useful Scheme resources on the web, please see @ref{Further |
| 22 | Reading}. |
| 23 | |
| 24 | @menu |
| 25 | * About Data:: Latent typing, types, values and variables. |
| 26 | * About Procedures:: The representation and use of procedures. |
| 27 | * About Expressions:: All kinds of expressions and their meaning. |
| 28 | * About Closure:: Closure, scoping and environments. |
| 29 | * Further Reading:: Where to find out more about Scheme. |
| 30 | @end menu |
| 31 | |
| 32 | |
| 33 | @node About Data |
| 34 | @section Data Types, Values and Variables |
| 35 | |
| 36 | This section discusses the representation of data types and values, what |
| 37 | it means for Scheme to be a @dfn{latently typed} language, and the role |
| 38 | of variables. We conclude by introducing the Scheme syntaxes for |
| 39 | defining a new variable, and for changing the value of an existing |
| 40 | variable. |
| 41 | |
| 42 | @menu |
| 43 | * Latent Typing:: Scheme as a "latently typed" language. |
| 44 | * Values and Variables:: About data types, values and variables. |
| 45 | * Definition:: Defining variables and setting their values. |
| 46 | @end menu |
| 47 | |
| 48 | |
| 49 | @node Latent Typing |
| 50 | @subsection Latent Typing |
| 51 | |
| 52 | The term @dfn{latent typing} is used to describe a computer language, |
| 53 | such as Scheme, for which you cannot, @emph{in general}, simply look at |
| 54 | a program's source code and determine what type of data will be |
| 55 | associated with a particular variable, or with the result of a |
| 56 | particular expression. |
| 57 | |
| 58 | Sometimes, of course, you @emph{can} tell from the code what the type of |
| 59 | an expression will be. If you have a line in your program that sets the |
| 60 | variable @code{x} to the numeric value 1, you can be certain that, |
| 61 | immediately after that line has executed (and in the absence of multiple |
| 62 | threads), @code{x} has the numeric value 1. Or if you write a procedure |
| 63 | that is designed to concatenate two strings, it is likely that the rest |
| 64 | of your application will always invoke this procedure with two string |
| 65 | parameters, and quite probable that the procedure would go wrong in some |
| 66 | way if it was ever invoked with parameters that were not both strings. |
| 67 | |
| 68 | Nevertheless, the point is that there is nothing in Scheme which |
| 69 | requires the procedure parameters always to be strings, or @code{x} |
| 70 | always to hold a numeric value, and there is no way of declaring in your |
| 71 | program that such constraints should always be obeyed. In the same |
| 72 | vein, there is no way to declare the expected type of a procedure's |
| 73 | return value. |
| 74 | |
| 75 | Instead, the types of variables and expressions are only known -- in |
| 76 | general -- at run time. If you @emph{need} to check at some point that |
| 77 | a value has the expected type, Scheme provides run time procedures that |
| 78 | you can invoke to do so. But equally, it can be perfectly valid for two |
| 79 | separate invocations of the same procedure to specify arguments with |
| 80 | different types, and to return values with different types. |
| 81 | |
| 82 | The next subsection explains what this means in practice, for the ways |
| 83 | that Scheme programs use data types, values and variables. |
| 84 | |
| 85 | |
| 86 | @node Values and Variables |
| 87 | @subsection Values and Variables |
| 88 | |
| 89 | Scheme provides many data types that you can use to represent your data. |
| 90 | Primitive types include characters, strings, numbers and procedures. |
| 91 | Compound types, which allow a group of primitive and compound values to |
| 92 | be stored together, include lists, pairs, vectors and multi-dimensional |
| 93 | arrays. In addition, Guile allows applications to define their own data |
| 94 | types, with the same status as the built-in standard Scheme types. |
| 95 | |
| 96 | As a Scheme program runs, values of all types pop in and out of |
| 97 | existence. Sometimes values are stored in variables, but more commonly |
| 98 | they pass seamlessly from being the result of one computation to being |
| 99 | one of the parameters for the next. |
| 100 | |
| 101 | Consider an example. A string value is created because the interpreter |
| 102 | reads in a literal string from your program's source code. Then a |
| 103 | numeric value is created as the result of calculating the length of the |
| 104 | string. A second numeric value is created by doubling the calculated |
| 105 | length. Finally the program creates a list with two elements -- the |
| 106 | doubled length and the original string itself -- and stores this list in |
| 107 | a program variable. |
| 108 | |
| 109 | All of the values involved here -- in fact, all values in Scheme -- |
| 110 | carry their type with them. In other words, every value ``knows,'' at |
| 111 | runtime, what kind of value it is. A number, a string, a list, |
| 112 | whatever. |
| 113 | |
| 114 | A variable, on the other hand, has no fixed type. A variable -- |
| 115 | @code{x}, say -- is simply the name of a location -- a box -- in which |
| 116 | you can store any kind of Scheme value. So the same variable in a |
| 117 | program may hold a number at one moment, a list of procedures the next, |
| 118 | and later a pair of strings. The ``type'' of a variable -- insofar as |
| 119 | the idea is meaningful at all -- is simply the type of whatever value |
| 120 | the variable happens to be storing at a particular moment. |
| 121 | |
| 122 | |
| 123 | @node Definition |
| 124 | @subsection Defining and Setting Variables |
| 125 | |
| 126 | To define a new variable, you use Scheme's @code{define} syntax like |
| 127 | this: |
| 128 | |
| 129 | @lisp |
| 130 | (define @var{variable-name} @var{value}) |
| 131 | @end lisp |
| 132 | |
| 133 | This makes a new variable called @var{variable-name} and stores |
| 134 | @var{value} in it as the variable's initial value. For example: |
| 135 | |
| 136 | @lisp |
| 137 | ;; Make a variable `x' with initial numeric value 1. |
| 138 | (define x 1) |
| 139 | |
| 140 | ;; Make a variable `organization' with an initial string value. |
| 141 | (define organization "Free Software Foundation") |
| 142 | @end lisp |
| 143 | |
| 144 | (In Scheme, a semicolon marks the beginning of a comment that continues |
| 145 | until the end of the line. So the lines beginning @code{;;} are |
| 146 | comments.) |
| 147 | |
| 148 | Changing the value of an already existing variable is very similar, |
| 149 | except that @code{define} is replaced by the Scheme syntax @code{set!}, |
| 150 | like this: |
| 151 | |
| 152 | @lisp |
| 153 | (set! @var{variable-name} @var{new-value}) |
| 154 | @end lisp |
| 155 | |
| 156 | Remember that variables do not have fixed types, so @var{new-value} may |
| 157 | have a completely different type from whatever was previously stored in |
| 158 | the location named by @var{variable-name}. Both of the following |
| 159 | examples are therefore correct. |
| 160 | |
| 161 | @lisp |
| 162 | ;; Change the value of `x' to 5. |
| 163 | (set! x 5) |
| 164 | |
| 165 | ;; Change the value of `organization' to the FSF's street number. |
| 166 | (set! organization 545) |
| 167 | @end lisp |
| 168 | |
| 169 | In these examples, @var{value} and @var{new-value} are literal numeric |
| 170 | or string values. In general, however, @var{value} and @var{new-value} |
| 171 | can be any Scheme expression. Even though we have not yet covered the |
| 172 | forms that Scheme expressions can take (@pxref{About Expressions}), you |
| 173 | can probably guess what the following @code{set!} example does@dots{} |
| 174 | |
| 175 | @lisp |
| 176 | (set! x (+ x 1)) |
| 177 | @end lisp |
| 178 | |
| 179 | (Note: this is not a complete description of @code{define} and |
| 180 | @code{set!}, because we need to introduce some other aspects of Scheme |
| 181 | before the missing pieces can be filled in. If, however, you are |
| 182 | already familiar with the structure of Scheme, you may like to read |
| 183 | about those missing pieces immediately by jumping ahead to the following |
| 184 | references. |
| 185 | |
| 186 | @itemize @bullet |
| 187 | @item |
| 188 | @ref{Lambda Alternatives}, to read about an alternative form of the |
| 189 | @code{define} syntax that can be used when defining new procedures. |
| 190 | |
| 191 | @item |
| 192 | @ref{Procedures with Setters}, to read about an alternative form of the |
| 193 | @code{set!} syntax that helps with changing a single value in the depths |
| 194 | of a compound data structure.) |
| 195 | |
| 196 | @item |
| 197 | @xref{Internal Definitions}, to read about using @code{define} other |
| 198 | than at top level in a Scheme program, including a discussion of when it |
| 199 | works to use @code{define} rather than @code{set!} to change the value |
| 200 | of an existing variable. |
| 201 | @end itemize |
| 202 | |
| 203 | |
| 204 | @node About Procedures |
| 205 | @section The Representation and Use of Procedures |
| 206 | |
| 207 | This section introduces the basics of using and creating Scheme |
| 208 | procedures. It discusses the representation of procedures as just |
| 209 | another kind of Scheme value, and shows how procedure invocation |
| 210 | expressions are constructed. We then explain how @code{lambda} is used |
| 211 | to create new procedures, and conclude by presenting the various |
| 212 | shorthand forms of @code{define} that can be used instead of writing an |
| 213 | explicit @code{lambda} expression. |
| 214 | |
| 215 | @menu |
| 216 | * Procedures as Values:: Procedures are values like everything else. |
| 217 | * Simple Invocation:: How to write a simple procedure invocation. |
| 218 | * Creating a Procedure:: How to create your own procedures. |
| 219 | * Lambda Alternatives:: Other ways of writing procedure definitions. |
| 220 | @end menu |
| 221 | |
| 222 | |
| 223 | @node Procedures as Values |
| 224 | @subsection Procedures as Values |
| 225 | |
| 226 | One of the great simplifications of Scheme is that a procedure is just |
| 227 | another type of value, and that procedure values can be passed around |
| 228 | and stored in variables in exactly the same way as, for example, strings |
| 229 | and lists. When we talk about a built-in standard Scheme procedure such |
| 230 | as @code{open-input-file}, what we actually mean is that there is a |
| 231 | pre-defined top level variable called @code{open-input-file}, whose |
| 232 | value is a procedure that implements what R5RS says that |
| 233 | @code{open-input-file} should do. |
| 234 | |
| 235 | Note that this is quite different from many dialects of Lisp --- |
| 236 | including Emacs Lisp --- in which a program can use the same name with |
| 237 | two quite separate meanings: one meaning identifies a Lisp function, |
| 238 | while the other meaning identifies a Lisp variable, whose value need |
| 239 | have nothing to do with the function that is associated with the first |
| 240 | meaning. In these dialects, functions and variables are said to live in |
| 241 | different @dfn{namespaces}. |
| 242 | |
| 243 | In Scheme, on the other hand, all names belong to a single unified |
| 244 | namespace, and the variables that these names identify can hold any kind |
| 245 | of Scheme value, including procedure values. |
| 246 | |
| 247 | One consequence of the ``procedures as values'' idea is that, if you |
| 248 | don't happen to like the standard name for a Scheme procedure, you can |
| 249 | change it. |
| 250 | |
| 251 | For example, @code{call-with-current-continuation} is a very important |
| 252 | standard Scheme procedure, but it also has a very long name! So, many |
| 253 | programmers use the following definition to assign the same procedure |
| 254 | value to the more convenient name @code{call/cc}. |
| 255 | |
| 256 | @lisp |
| 257 | (define call/cc call-with-current-continuation) |
| 258 | @end lisp |
| 259 | |
| 260 | Let's understand exactly how this works. The definition creates a new |
| 261 | variable @code{call/cc}, and then sets its value to the value of the |
| 262 | variable @code{call-with-current-continuation}; the latter value is a |
| 263 | procedure that implements the behaviour that R5RS specifies under the |
| 264 | name ``call-with-current-continuation''. So @code{call/cc} ends up |
| 265 | holding this value as well. |
| 266 | |
| 267 | Now that @code{call/cc} holds the required procedure value, you could |
| 268 | choose to use @code{call-with-current-continuation} for a completely |
| 269 | different purpose, or just change its value so that you will get an |
| 270 | error if you accidentally use @code{call-with-current-continuation} as a |
| 271 | procedure in your program rather than @code{call/cc}. For example: |
| 272 | |
| 273 | @lisp |
| 274 | (set! call-with-current-continuation "Not a procedure any more!") |
| 275 | @end lisp |
| 276 | |
| 277 | Or you could just leave @code{call-with-current-continuation} as it was. |
| 278 | It's perfectly fine for more than one variable to hold the same |
| 279 | procedure value. |
| 280 | |
| 281 | |
| 282 | @node Simple Invocation |
| 283 | @subsection Simple Procedure Invocation |
| 284 | |
| 285 | A procedure invocation in Scheme is written like this: |
| 286 | |
| 287 | @lisp |
| 288 | (@var{procedure} [@var{arg1} [@var{arg2} @dots{}]]) |
| 289 | @end lisp |
| 290 | |
| 291 | In this expression, @var{procedure} can be any Scheme expression whose |
| 292 | value is a procedure. Most commonly, however, @var{procedure} is simply |
| 293 | the name of a variable whose value is a procedure. |
| 294 | |
| 295 | For example, @code{string-append} is a standard Scheme procedure whose |
| 296 | behaviour is to concatenate together all the arguments, which are |
| 297 | expected to be strings, that it is given. So the expression |
| 298 | |
| 299 | @lisp |
| 300 | (string-append "/home" "/" "andrew") |
| 301 | @end lisp |
| 302 | |
| 303 | @noindent |
| 304 | is a procedure invocation whose result is the string value |
| 305 | @code{"/home/andrew"}. |
| 306 | |
| 307 | Similarly, @code{string-length} is a standard Scheme procedure that |
| 308 | returns the length of a single string argument, so |
| 309 | |
| 310 | @lisp |
| 311 | (string-length "abc") |
| 312 | @end lisp |
| 313 | |
| 314 | @noindent |
| 315 | is a procedure invocation whose result is the numeric value 3. |
| 316 | |
| 317 | Each of the parameters in a procedure invocation can itself be any |
| 318 | Scheme expression. Since a procedure invocation is itself a type of |
| 319 | expression, we can put these two examples together to get |
| 320 | |
| 321 | @lisp |
| 322 | (string-length (string-append "/home" "/" "andrew")) |
| 323 | @end lisp |
| 324 | |
| 325 | @noindent |
| 326 | --- a procedure invocation whose result is the numeric value 12. |
| 327 | |
| 328 | (You may be wondering what happens if the two examples are combined the |
| 329 | other way round. If we do this, we can make a procedure invocation |
| 330 | expression that is @emph{syntactically} correct: |
| 331 | |
| 332 | @lisp |
| 333 | (string-append "/home" (string-length "abc")) |
| 334 | @end lisp |
| 335 | |
| 336 | @noindent |
| 337 | but when this expression is executed, it will cause an error, because |
| 338 | the result of @code{(string-length "abc")} is a numeric value, and |
| 339 | @code{string-append} is not designed to accept a numeric value as one of |
| 340 | its arguments.) |
| 341 | |
| 342 | |
| 343 | @node Creating a Procedure |
| 344 | @subsection Creating and Using a New Procedure |
| 345 | |
| 346 | Scheme has lots of standard procedures, and Guile provides all of these |
| 347 | via predefined top level variables. All of these standard procedures |
| 348 | are documented in the later chapters of this reference manual. |
| 349 | |
| 350 | Before very long, though, you will want to create new procedures that |
| 351 | encapsulate aspects of your own applications' functionality. To do |
| 352 | this, you can use the famous @code{lambda} syntax. |
| 353 | |
| 354 | For example, the value of the following Scheme expression |
| 355 | |
| 356 | @lisp |
| 357 | (lambda (name address) @var{expression} @dots{}) |
| 358 | @end lisp |
| 359 | |
| 360 | @noindent |
| 361 | is a newly created procedure that takes two arguments: |
| 362 | @code{name} and @code{address}. The behaviour of the |
| 363 | new procedure is determined by the sequence of @var{expression}s in the |
| 364 | @dfn{body} of the procedure definition. (Typically, these |
| 365 | @var{expression}s would use the arguments in some way, or else there |
| 366 | wouldn't be any point in giving them to the procedure.) When invoked, |
| 367 | the new procedure returns a value that is the value of the last |
| 368 | @var{expression} in the procedure body. |
| 369 | |
| 370 | To make things more concrete, let's suppose that the two arguments are |
| 371 | both strings, and that the purpose of this procedure is to form a |
| 372 | combined string that includes these arguments. Then the full lambda |
| 373 | expression might look like this: |
| 374 | |
| 375 | @lisp |
| 376 | (lambda (name address) |
| 377 | (string-append "Name=" name ":Address=" address)) |
| 378 | @end lisp |
| 379 | |
| 380 | We noted in the previous subsection that the @var{procedure} part of a |
| 381 | procedure invocation expression can be any Scheme expression whose value |
| 382 | is a procedure. But that's exactly what a lambda expression is! So we |
| 383 | can use a lambda expression directly in a procedure invocation, like |
| 384 | this: |
| 385 | |
| 386 | @lisp |
| 387 | ((lambda (name address) |
| 388 | (string-append "Name=" name ":Address=" address)) |
| 389 | "FSF" |
| 390 | "Cambridge") |
| 391 | @end lisp |
| 392 | |
| 393 | @noindent |
| 394 | This is a valid procedure invocation expression, and its result is the |
| 395 | string: |
| 396 | |
| 397 | @lisp |
| 398 | "Name=FSF:Address=Cambridge" |
| 399 | @end lisp |
| 400 | |
| 401 | It is more common, though, to store the procedure value in a variable --- |
| 402 | |
| 403 | @lisp |
| 404 | (define make-combined-string |
| 405 | (lambda (name address) |
| 406 | (string-append "Name=" name ":Address=" address))) |
| 407 | @end lisp |
| 408 | |
| 409 | @noindent |
| 410 | --- and then to use the variable name in the procedure invocation: |
| 411 | |
| 412 | @lisp |
| 413 | (make-combined-string "FSF" "Cambridge") |
| 414 | @end lisp |
| 415 | |
| 416 | @noindent |
| 417 | Which has exactly the same result. |
| 418 | |
| 419 | It's important to note that procedures created using @code{lambda} have |
| 420 | exactly the same status as the standard built in Scheme procedures, and |
| 421 | can be invoked, passed around, and stored in variables in exactly the |
| 422 | same ways. |
| 423 | |
| 424 | |
| 425 | @node Lambda Alternatives |
| 426 | @subsection Lambda Alternatives |
| 427 | |
| 428 | Since it is so common in Scheme programs to want to create a procedure |
| 429 | and then store it in a variable, there is an alternative form of the |
| 430 | @code{define} syntax that allows you to do just that. |
| 431 | |
| 432 | A @code{define} expression of the form |
| 433 | |
| 434 | @lisp |
| 435 | (define (@var{name} [@var{arg1} [@var{arg2} @dots{}]]) |
| 436 | @var{expression} @dots{}) |
| 437 | @end lisp |
| 438 | |
| 439 | @noindent |
| 440 | is exactly equivalent to the longer form |
| 441 | |
| 442 | @lisp |
| 443 | (define @var{name} |
| 444 | (lambda ([@var{arg1} [@var{arg2} @dots{}]]) |
| 445 | @var{expression} @dots{})) |
| 446 | @end lisp |
| 447 | |
| 448 | So, for example, the definition of @code{make-combined-string} in the |
| 449 | previous subsection could equally be written: |
| 450 | |
| 451 | @lisp |
| 452 | (define (make-combined-string name address) |
| 453 | (string-append "Name=" name ":Address=" address)) |
| 454 | @end lisp |
| 455 | |
| 456 | This kind of procedure definition creates a procedure that requires |
| 457 | exactly the expected number of arguments. There are two further forms |
| 458 | of the @code{lambda} expression, which create a procedure that can |
| 459 | accept a variable number of arguments: |
| 460 | |
| 461 | @lisp |
| 462 | (lambda (@var{arg1} @dots{} . @var{args}) @var{expression} @dots{}) |
| 463 | |
| 464 | (lambda @var{args} @var{expression} @dots{}) |
| 465 | @end lisp |
| 466 | |
| 467 | @noindent |
| 468 | The corresponding forms of the alternative @code{define} syntax are: |
| 469 | |
| 470 | @lisp |
| 471 | (define (@var{name} @var{arg1} @dots{} . @var{args}) @var{expression} @dots{}) |
| 472 | |
| 473 | (define (@var{name} . @var{args}) @var{expression} @dots{}) |
| 474 | @end lisp |
| 475 | |
| 476 | @noindent |
| 477 | For details on how these forms work, see @xref{Lambda}. |
| 478 | |
| 479 | Prior to Guile 2.0, Guile provided an extension to @code{define} syntax |
| 480 | that allowed you to nest the previous extension up to an arbitrary |
| 481 | depth. These are no longer provided by default, and instead have been |
| 482 | moved to @ref{Curried Definitions} |
| 483 | |
| 484 | (It could be argued that the alternative @code{define} forms are rather |
| 485 | confusing, especially for newcomers to the Scheme language, as they hide |
| 486 | both the role of @code{lambda} and the fact that procedures are values |
| 487 | that are stored in variables in the some way as any other kind of value. |
| 488 | On the other hand, they are very convenient, and they are also a good |
| 489 | example of another of Scheme's powerful features: the ability to specify |
| 490 | arbitrary syntactic transformations at run time, which can be applied to |
| 491 | subsequently read input.) |
| 492 | |
| 493 | |
| 494 | @node About Expressions |
| 495 | @section Expressions and Evaluation |
| 496 | |
| 497 | So far, we have met expressions that @emph{do} things, such as the |
| 498 | @code{define} expressions that create and initialize new variables, and |
| 499 | we have also talked about expressions that have @emph{values}, for |
| 500 | example the value of the procedure invocation expression: |
| 501 | |
| 502 | @lisp |
| 503 | (string-append "/home" "/" "andrew") |
| 504 | @end lisp |
| 505 | |
| 506 | @noindent |
| 507 | but we haven't yet been precise about what causes an expression like |
| 508 | this procedure invocation to be reduced to its ``value'', or how the |
| 509 | processing of such expressions relates to the execution of a Scheme |
| 510 | program as a whole. |
| 511 | |
| 512 | This section clarifies what we mean by an expression's value, by |
| 513 | introducing the idea of @dfn{evaluation}. It discusses the side effects |
| 514 | that evaluation can have, explains how each of the various types of |
| 515 | Scheme expression is evaluated, and describes the behaviour and use of |
| 516 | the Guile REPL as a mechanism for exploring evaluation. The section |
| 517 | concludes with a very brief summary of Scheme's common syntactic |
| 518 | expressions. |
| 519 | |
| 520 | @menu |
| 521 | * Evaluating:: How a Scheme program is executed. |
| 522 | * Tail Calls:: Space-safe recursion. |
| 523 | * The REPL:: Interacting with the Guile interpreter. |
| 524 | * Syntax Summary:: Common syntactic expressions -- in brief. |
| 525 | @end menu |
| 526 | |
| 527 | |
| 528 | @node Evaluating |
| 529 | @subsection Evaluating Expressions and Executing Programs |
| 530 | |
| 531 | In Scheme, the process of executing an expression is known as |
| 532 | @dfn{evaluation}. Evaluation has two kinds of result: |
| 533 | |
| 534 | @itemize @bullet |
| 535 | @item |
| 536 | the @dfn{value} of the evaluated expression |
| 537 | |
| 538 | @item |
| 539 | the @dfn{side effects} of the evaluation, which consist of any effects of |
| 540 | evaluating the expression that are not represented by the value. |
| 541 | @end itemize |
| 542 | |
| 543 | Of the expressions that we have met so far, @code{define} and |
| 544 | @code{set!} expressions have side effects --- the creation or |
| 545 | modification of a variable --- but no value; @code{lambda} expressions |
| 546 | have values --- the newly constructed procedures --- but no side |
| 547 | effects; and procedure invocation expressions, in general, have either |
| 548 | values, or side effects, or both. |
| 549 | |
| 550 | It is tempting to try to define more intuitively what we mean by |
| 551 | ``value'' and ``side effects'', and what the difference between them is. |
| 552 | In general, though, this is extremely difficult. It is also |
| 553 | unnecessary; instead, we can quite happily define the behaviour of a |
| 554 | Scheme program by specifying how Scheme executes a program as a whole, |
| 555 | and then by describing the value and side effects of evaluation for each |
| 556 | type of expression individually. |
| 557 | |
| 558 | @noindent |
| 559 | So, some@footnote{These definitions are approximate. For the whole |
| 560 | and detailed truth, see @ref{Formal syntax and semantics,R5RS |
| 561 | syntax,,r5rs,The Revised(5) Report on the Algorithmic Language |
| 562 | Scheme}.} definitions@dots{} |
| 563 | |
| 564 | @itemize @bullet |
| 565 | |
| 566 | @item |
| 567 | A Scheme program consists of a sequence of expressions. |
| 568 | |
| 569 | @item |
| 570 | A Scheme interpreter executes the program by evaluating these |
| 571 | expressions in order, one by one. |
| 572 | |
| 573 | @item |
| 574 | An expression can be |
| 575 | |
| 576 | @itemize @bullet |
| 577 | @item |
| 578 | a piece of literal data, such as a number @code{2.3} or a string |
| 579 | @code{"Hello world!"} |
| 580 | @item |
| 581 | a variable name |
| 582 | @item |
| 583 | a procedure invocation expression |
| 584 | @item |
| 585 | one of Scheme's special syntactic expressions. |
| 586 | @end itemize |
| 587 | @end itemize |
| 588 | |
| 589 | @noindent |
| 590 | The following subsections describe how each of these types of expression |
| 591 | is evaluated. |
| 592 | |
| 593 | @menu |
| 594 | * Eval Literal:: Evaluating literal data. |
| 595 | * Eval Variable:: Evaluating variable references. |
| 596 | * Eval Procedure:: Evaluating procedure invocation expressions. |
| 597 | * Eval Special:: Evaluating special syntactic expressions. |
| 598 | @end menu |
| 599 | |
| 600 | @node Eval Literal |
| 601 | @subsubsection Evaluating Literal Data |
| 602 | |
| 603 | When a literal data expression is evaluated, the value of the expression |
| 604 | is simply the value that the expression describes. The evaluation of a |
| 605 | literal data expression has no side effects. |
| 606 | |
| 607 | @noindent |
| 608 | So, for example, |
| 609 | |
| 610 | @itemize @bullet |
| 611 | @item |
| 612 | the value of the expression @code{"abc"} is the string value |
| 613 | @code{"abc"} |
| 614 | |
| 615 | @item |
| 616 | the value of the expression @code{3+4i} is the complex number 3 + 4i |
| 617 | |
| 618 | @item |
| 619 | the value of the expression @code{#(1 2 3)} is a three-element vector |
| 620 | containing the numeric values 1, 2 and 3. |
| 621 | @end itemize |
| 622 | |
| 623 | For any data type which can be expressed literally like this, the syntax |
| 624 | of the literal data expression for that data type --- in other words, |
| 625 | what you need to write in your code to indicate a literal value of that |
| 626 | type --- is known as the data type's @dfn{read syntax}. This manual |
| 627 | specifies the read syntax for each such data type in the section that |
| 628 | describes that data type. |
| 629 | |
| 630 | Some data types do not have a read syntax. Procedures, for example, |
| 631 | cannot be expressed as literal data; they must be created using a |
| 632 | @code{lambda} expression (@pxref{Creating a Procedure}) or implicitly |
| 633 | using the shorthand form of @code{define} (@pxref{Lambda Alternatives}). |
| 634 | |
| 635 | |
| 636 | @node Eval Variable |
| 637 | @subsubsection Evaluating a Variable Reference |
| 638 | |
| 639 | When an expression that consists simply of a variable name is evaluated, |
| 640 | the value of the expression is the value of the named variable. The |
| 641 | evaluation of a variable reference expression has no side effects. |
| 642 | |
| 643 | So, after |
| 644 | |
| 645 | @lisp |
| 646 | (define key "Paul Evans") |
| 647 | @end lisp |
| 648 | |
| 649 | @noindent |
| 650 | the value of the expression @code{key} is the string value @code{"Paul |
| 651 | Evans"}. If @var{key} is then modified by |
| 652 | |
| 653 | @lisp |
| 654 | (set! key 3.74) |
| 655 | @end lisp |
| 656 | |
| 657 | @noindent |
| 658 | the value of the expression @code{key} is the numeric value 3.74. |
| 659 | |
| 660 | If there is no variable with the specified name, evaluation of the |
| 661 | variable reference expression signals an error. |
| 662 | |
| 663 | |
| 664 | @node Eval Procedure |
| 665 | @subsubsection Evaluating a Procedure Invocation Expression |
| 666 | |
| 667 | This is where evaluation starts getting interesting! As already noted, |
| 668 | a procedure invocation expression has the form |
| 669 | |
| 670 | @lisp |
| 671 | (@var{procedure} [@var{arg1} [@var{arg2} @dots{}]]) |
| 672 | @end lisp |
| 673 | |
| 674 | @noindent |
| 675 | where @var{procedure} must be an expression whose value, when evaluated, |
| 676 | is a procedure. |
| 677 | |
| 678 | The evaluation of a procedure invocation expression like this proceeds |
| 679 | by |
| 680 | |
| 681 | @itemize @bullet |
| 682 | @item |
| 683 | evaluating individually the expressions @var{procedure}, @var{arg1}, |
| 684 | @var{arg2}, and so on |
| 685 | |
| 686 | @item |
| 687 | calling the procedure that is the value of the @var{procedure} |
| 688 | expression with the list of values obtained from the evaluations of |
| 689 | @var{arg1}, @var{arg2} etc. as its parameters. |
| 690 | @end itemize |
| 691 | |
| 692 | For a procedure defined in Scheme, ``calling the procedure with the list |
| 693 | of values as its parameters'' means binding the values to the |
| 694 | procedure's formal parameters and then evaluating the sequence of |
| 695 | expressions that make up the body of the procedure definition. The |
| 696 | value of the procedure invocation expression is the value of the last |
| 697 | evaluated expression in the procedure body. The side effects of calling |
| 698 | the procedure are the combination of the side effects of the sequence of |
| 699 | evaluations of expressions in the procedure body. |
| 700 | |
| 701 | For a built-in procedure, the value and side-effects of calling the |
| 702 | procedure are best described by that procedure's documentation. |
| 703 | |
| 704 | Note that the complete side effects of evaluating a procedure invocation |
| 705 | expression consist not only of the side effects of the procedure call, |
| 706 | but also of any side effects of the preceding evaluation of the |
| 707 | expressions @var{procedure}, @var{arg1}, @var{arg2}, and so on. |
| 708 | |
| 709 | To illustrate this, let's look again at the procedure invocation |
| 710 | expression: |
| 711 | |
| 712 | @lisp |
| 713 | (string-length (string-append "/home" "/" "andrew")) |
| 714 | @end lisp |
| 715 | |
| 716 | In the outermost expression, @var{procedure} is @code{string-length} and |
| 717 | @var{arg1} is @code{(string-append "/home" "/" "andrew")}. |
| 718 | |
| 719 | @itemize @bullet |
| 720 | @item |
| 721 | Evaluation of @code{string-length}, which is a variable, gives a |
| 722 | procedure value that implements the expected behaviour for |
| 723 | ``string-length''. |
| 724 | |
| 725 | @item |
| 726 | Evaluation of @code{(string-append "/home" "/" "andrew")}, which is |
| 727 | another procedure invocation expression, means evaluating each of |
| 728 | |
| 729 | @itemize @bullet |
| 730 | @item |
| 731 | @code{string-append}, which gives a procedure value that implements the |
| 732 | expected behaviour for ``string-append'' |
| 733 | |
| 734 | @item |
| 735 | @code{"/home"}, which gives the string value @code{"/home"} |
| 736 | |
| 737 | @item |
| 738 | @code{"/"}, which gives the string value @code{"/"} |
| 739 | |
| 740 | @item |
| 741 | @code{"andrew"}, which gives the string value @code{"andrew"} |
| 742 | @end itemize |
| 743 | |
| 744 | and then invoking the procedure value with this list of string values as |
| 745 | its arguments. The resulting value is a single string value that is the |
| 746 | concatenation of all the arguments, namely @code{"/home/andrew"}. |
| 747 | @end itemize |
| 748 | |
| 749 | In the evaluation of the outermost expression, the interpreter can now |
| 750 | invoke the procedure value obtained from @var{procedure} with the value |
| 751 | obtained from @var{arg1} as its arguments. The resulting value is a |
| 752 | numeric value that is the length of the argument string, which is 12. |
| 753 | |
| 754 | |
| 755 | @node Eval Special |
| 756 | @subsubsection Evaluating Special Syntactic Expressions |
| 757 | |
| 758 | When a procedure invocation expression is evaluated, the procedure and |
| 759 | @emph{all} the argument expressions must be evaluated before the |
| 760 | procedure can be invoked. Special syntactic expressions are special |
| 761 | because they are able to manipulate their arguments in an unevaluated |
| 762 | form, and can choose whether to evaluate any or all of the argument |
| 763 | expressions. |
| 764 | |
| 765 | Why is this needed? Consider a program fragment that asks the user |
| 766 | whether or not to delete a file, and then deletes the file if the user |
| 767 | answers yes. |
| 768 | |
| 769 | @lisp |
| 770 | (if (string=? (read-answer "Should I delete this file?") |
| 771 | "yes") |
| 772 | (delete-file file)) |
| 773 | @end lisp |
| 774 | |
| 775 | If the outermost @code{(if @dots{})} expression here was a procedure |
| 776 | invocation expression, the expression @code{(delete-file file)}, whose |
| 777 | side effect is to actually delete a file, would already have been |
| 778 | evaluated before the @code{if} procedure even got invoked! Clearly this |
| 779 | is no use --- the whole point of an @code{if} expression is that the |
| 780 | @dfn{consequent} expression is only evaluated if the condition of the |
| 781 | @code{if} expression is ``true''. |
| 782 | |
| 783 | Therefore @code{if} must be special syntax, not a procedure. Other |
| 784 | special syntaxes that we have already met are @code{define}, @code{set!} |
| 785 | and @code{lambda}. @code{define} and @code{set!} are syntax because |
| 786 | they need to know the variable @emph{name} that is given as the first |
| 787 | argument in a @code{define} or @code{set!} expression, not that |
| 788 | variable's value. @code{lambda} is syntax because it does not |
| 789 | immediately evaluate the expressions that define the procedure body; |
| 790 | instead it creates a procedure object that incorporates these |
| 791 | expressions so that they can be evaluated in the future, when that |
| 792 | procedure is invoked. |
| 793 | |
| 794 | The rules for evaluating each special syntactic expression are specified |
| 795 | individually for each special syntax. For a summary of standard special |
| 796 | syntax, see @xref{Syntax Summary}. |
| 797 | |
| 798 | |
| 799 | @node Tail Calls |
| 800 | @subsection Tail calls |
| 801 | @cindex tail calls |
| 802 | @cindex recursion |
| 803 | |
| 804 | Scheme is ``properly tail recursive'', meaning that tail calls or |
| 805 | recursions from certain contexts do not consume stack space or other |
| 806 | resources and can therefore be used on arbitrarily large data or for |
| 807 | an arbitrarily long calculation. Consider for example, |
| 808 | |
| 809 | @example |
| 810 | (define (foo n) |
| 811 | (display n) |
| 812 | (newline) |
| 813 | (foo (1+ n))) |
| 814 | |
| 815 | (foo 1) |
| 816 | @print{} |
| 817 | 1 |
| 818 | 2 |
| 819 | 3 |
| 820 | @dots{} |
| 821 | @end example |
| 822 | |
| 823 | @code{foo} prints numbers infinitely, starting from the given @var{n}. |
| 824 | It's implemented by printing @var{n} then recursing to itself to print |
| 825 | @math{@var{n}+1} and so on. This recursion is a tail call, it's the |
| 826 | last thing done, and in Scheme such tail calls can be made without |
| 827 | limit. |
| 828 | |
| 829 | Or consider a case where a value is returned, a version of the SRFI-1 |
| 830 | @code{last} function (@pxref{SRFI-1 Selectors}) returning the last |
| 831 | element of a list, |
| 832 | |
| 833 | @example |
| 834 | (define (my-last lst) |
| 835 | (if (null? (cdr lst)) |
| 836 | (car lst) |
| 837 | (my-last (cdr lst)))) |
| 838 | |
| 839 | (my-last '(1 2 3)) @result{} 3 |
| 840 | @end example |
| 841 | |
| 842 | If the list has more than one element, @code{my-last} applies itself |
| 843 | to the @code{cdr}. This recursion is a tail call, there's no code |
| 844 | after it, and the return value is the return value from that call. In |
| 845 | Scheme this can be used on an arbitrarily long list argument. |
| 846 | |
| 847 | @sp 1 |
| 848 | A proper tail call is only available from certain contexts, namely the |
| 849 | following special form positions, |
| 850 | |
| 851 | @itemize @bullet |
| 852 | @item |
| 853 | @code{and} --- last expression |
| 854 | |
| 855 | @item |
| 856 | @code{begin} --- last expression |
| 857 | |
| 858 | @item |
| 859 | @code{case} --- last expression in each clause |
| 860 | |
| 861 | @item |
| 862 | @code{cond} --- last expression in each clause, and the call to a |
| 863 | @code{=>} procedure is a tail call |
| 864 | |
| 865 | @item |
| 866 | @code{do} --- last result expression |
| 867 | |
| 868 | @item |
| 869 | @code{if} --- ``true'' and ``false'' leg expressions |
| 870 | |
| 871 | @item |
| 872 | @code{lambda} --- last expression in body |
| 873 | |
| 874 | @item |
| 875 | @code{let}, @code{let*}, @code{letrec}, @code{let-syntax}, |
| 876 | @code{letrec-syntax} --- last expression in body |
| 877 | |
| 878 | @item |
| 879 | @code{or} --- last expression |
| 880 | @end itemize |
| 881 | |
| 882 | @noindent |
| 883 | The following core functions make tail calls, |
| 884 | |
| 885 | @itemize @bullet |
| 886 | @item |
| 887 | @code{apply} --- tail call to given procedure |
| 888 | |
| 889 | @item |
| 890 | @code{call-with-current-continuation} --- tail call to the procedure |
| 891 | receiving the new continuation |
| 892 | |
| 893 | @item |
| 894 | @code{call-with-values} --- tail call to the values-receiving |
| 895 | procedure |
| 896 | |
| 897 | @item |
| 898 | @code{eval} --- tail call to evaluate the form |
| 899 | |
| 900 | @item |
| 901 | @code{string-any}, @code{string-every} --- tail call to predicate on |
| 902 | the last character (if that point is reached) |
| 903 | @end itemize |
| 904 | |
| 905 | @sp 1 |
| 906 | The above are just core functions and special forms. Tail calls in |
| 907 | other modules are described with the relevant documentation, for |
| 908 | example SRFI-1 @code{any} and @code{every} (@pxref{SRFI-1 Searching}). |
| 909 | |
| 910 | It will be noted there are a lot of places which could potentially be |
| 911 | tail calls, for instance the last call in a @code{for-each}, but only |
| 912 | those explicitly described are guaranteed. |
| 913 | |
| 914 | |
| 915 | @node The REPL |
| 916 | @subsection Using the Guile REPL |
| 917 | |
| 918 | If you start Guile without specifying a particular program for it to |
| 919 | execute, Guile enters its standard Read Evaluate Print Loop --- or |
| 920 | @dfn{REPL} for short. In this mode, Guile repeatedly reads in the next |
| 921 | Scheme expression that the user types, evaluates it, and prints the |
| 922 | resulting value. |
| 923 | |
| 924 | The REPL is a useful mechanism for exploring the evaluation behaviour |
| 925 | described in the previous subsection. If you type @code{string-append}, |
| 926 | for example, the REPL replies @code{#<primitive-procedure |
| 927 | string-append>}, illustrating the relationship between the variable |
| 928 | @code{string-append} and the procedure value stored in that variable. |
| 929 | |
| 930 | In this manual, the notation @result{} is used to mean ``evaluates |
| 931 | to''. Wherever you see an example of the form |
| 932 | |
| 933 | @lisp |
| 934 | @var{expression} |
| 935 | @result{} |
| 936 | @var{result} |
| 937 | @end lisp |
| 938 | |
| 939 | @noindent |
| 940 | feel free to try it out yourself by typing @var{expression} into the |
| 941 | REPL and checking that it gives the expected @var{result}. |
| 942 | |
| 943 | |
| 944 | @node Syntax Summary |
| 945 | @subsection Summary of Common Syntax |
| 946 | |
| 947 | This subsection lists the most commonly used Scheme syntactic |
| 948 | expressions, simply so that you will recognize common special syntax |
| 949 | when you see it. For a full description of each of these syntaxes, |
| 950 | follow the appropriate reference. |
| 951 | |
| 952 | @code{lambda} (@pxref{Lambda}) is used to construct procedure objects. |
| 953 | |
| 954 | @code{define} (@pxref{Top Level}) is used to create a new variable and |
| 955 | set its initial value. |
| 956 | |
| 957 | @code{set!} (@pxref{Top Level}) is used to modify an existing variable's |
| 958 | value. |
| 959 | |
| 960 | @code{let}, @code{let*} and @code{letrec} (@pxref{Local Bindings}) |
| 961 | create an inner lexical environment for the evaluation of a sequence of |
| 962 | expressions, in which a specified set of local variables is bound to the |
| 963 | values of a corresponding set of expressions. For an introduction to |
| 964 | environments, see @xref{About Closure}. |
| 965 | |
| 966 | @code{begin} (@pxref{begin}) executes a sequence of expressions in order |
| 967 | and returns the value of the last expression. Note that this is not the |
| 968 | same as a procedure which returns its last argument, because the |
| 969 | evaluation of a procedure invocation expression does not guarantee to |
| 970 | evaluate the arguments in order. |
| 971 | |
| 972 | @code{if} and @code{cond} (@pxref{Conditionals}) provide conditional |
| 973 | evaluation of argument expressions depending on whether one or more |
| 974 | conditions evaluate to ``true'' or ``false''. |
| 975 | |
| 976 | @code{case} (@pxref{Conditionals}) provides conditional evaluation of |
| 977 | argument expressions depending on whether a variable has one of a |
| 978 | specified group of values. |
| 979 | |
| 980 | @code{and} (@pxref{and or}) executes a sequence of expressions in order |
| 981 | until either there are no expressions left, or one of them evaluates to |
| 982 | ``false''. |
| 983 | |
| 984 | @code{or} (@pxref{and or}) executes a sequence of expressions in order |
| 985 | until either there are no expressions left, or one of them evaluates to |
| 986 | ``true''. |
| 987 | |
| 988 | |
| 989 | @node About Closure |
| 990 | @section The Concept of Closure |
| 991 | |
| 992 | @cindex closure |
| 993 | |
| 994 | The concept of @dfn{closure} is the idea that a lambda expression |
| 995 | ``captures'' the variable bindings that are in lexical scope at the |
| 996 | point where the lambda expression occurs. The procedure created by the |
| 997 | lambda expression can refer to and mutate the captured bindings, and the |
| 998 | values of those bindings persist between procedure calls. |
| 999 | |
| 1000 | This section explains and explores the various parts of this idea in |
| 1001 | more detail. |
| 1002 | |
| 1003 | @menu |
| 1004 | * About Environments:: Names, locations, values and environments. |
| 1005 | * Local Variables:: Local variables and local environments. |
| 1006 | * Chaining:: Environment chaining. |
| 1007 | * Lexical Scope:: The meaning of lexical scoping. |
| 1008 | * Closure:: Explaining the concept of closure. |
| 1009 | * Serial Number:: Example 1: a serial number generator. |
| 1010 | * Shared Variable:: Example 2: a shared persistent variable. |
| 1011 | * Callback Closure:: Example 3: the callback closure problem. |
| 1012 | * OO Closure:: Example 4: object orientation. |
| 1013 | @end menu |
| 1014 | |
| 1015 | @node About Environments |
| 1016 | @subsection Names, Locations, Values and Environments |
| 1017 | |
| 1018 | @cindex location |
| 1019 | @cindex environment |
| 1020 | @cindex vcell |
| 1021 | @cindex top level environment |
| 1022 | @cindex environment, top level |
| 1023 | |
| 1024 | We said earlier that a variable name in a Scheme program is associated |
| 1025 | with a location in which any kind of Scheme value may be stored. |
| 1026 | (Incidentally, the term ``vcell'' is often used in Lisp and Scheme |
| 1027 | circles as an alternative to ``location''.) Thus part of what we mean |
| 1028 | when we talk about ``creating a variable'' is in fact establishing an |
| 1029 | association between a name, or identifier, that is used by the Scheme |
| 1030 | program code, and the variable location to which that name refers. |
| 1031 | Although the value that is stored in that location may change, the |
| 1032 | location to which a given name refers is always the same. |
| 1033 | |
| 1034 | We can illustrate this by breaking down the operation of the |
| 1035 | @code{define} syntax into three parts: @code{define} |
| 1036 | |
| 1037 | @itemize @bullet |
| 1038 | @item |
| 1039 | creates a new location |
| 1040 | |
| 1041 | @item |
| 1042 | establishes an association between that location and the name specified |
| 1043 | as the first argument of the @code{define} expression |
| 1044 | |
| 1045 | @item |
| 1046 | stores in that location the value obtained by evaluating the second |
| 1047 | argument of the @code{define} expression. |
| 1048 | @end itemize |
| 1049 | |
| 1050 | A collection of associations between names and locations is called an |
| 1051 | @dfn{environment}. When you create a top level variable in a program |
| 1052 | using @code{define}, the name-location association for that variable is |
| 1053 | added to the ``top level'' environment. The ``top level'' environment |
| 1054 | also includes name-location associations for all the procedures that are |
| 1055 | supplied by standard Scheme. |
| 1056 | |
| 1057 | It is also possible to create environments other than the top level one, |
| 1058 | and to create variable bindings, or name-location associations, in those |
| 1059 | environments. This ability is a key ingredient in the concept of |
| 1060 | closure; the next subsection shows how it is done. |
| 1061 | |
| 1062 | |
| 1063 | @node Local Variables |
| 1064 | @subsection Local Variables and Environments |
| 1065 | |
| 1066 | @cindex local variable |
| 1067 | @cindex variable, local |
| 1068 | @cindex local environment |
| 1069 | @cindex environment, local |
| 1070 | |
| 1071 | We have seen how to create top level variables using the @code{define} |
| 1072 | syntax (@pxref{Definition}). It is often useful to create variables |
| 1073 | that are more limited in their scope, typically as part of a procedure |
| 1074 | body. In Scheme, this is done using the @code{let} syntax, or one of |
| 1075 | its modified forms @code{let*} and @code{letrec}. These syntaxes are |
| 1076 | described in full later in the manual (@pxref{Local Bindings}). Here |
| 1077 | our purpose is to illustrate their use just enough that we can see how |
| 1078 | local variables work. |
| 1079 | |
| 1080 | For example, the following code uses a local variable @code{s} to |
| 1081 | simplify the computation of the area of a triangle given the lengths of |
| 1082 | its three sides. |
| 1083 | |
| 1084 | @lisp |
| 1085 | (define a 5.3) |
| 1086 | (define b 4.7) |
| 1087 | (define c 2.8) |
| 1088 | |
| 1089 | (define area |
| 1090 | (let ((s (/ (+ a b c) 2))) |
| 1091 | (sqrt (* s (- s a) (- s b) (- s c))))) |
| 1092 | @end lisp |
| 1093 | |
| 1094 | The effect of the @code{let} expression is to create a new environment |
| 1095 | and, within this environment, an association between the name @code{s} |
| 1096 | and a new location whose initial value is obtained by evaluating |
| 1097 | @code{(/ (+ a b c) 2)}. The expressions in the body of the @code{let}, |
| 1098 | namely @code{(sqrt (* s (- s a) (- s b) (- s c)))}, are then evaluated |
| 1099 | in the context of the new environment, and the value of the last |
| 1100 | expression evaluated becomes the value of the whole @code{let} |
| 1101 | expression, and therefore the value of the variable @code{area}. |
| 1102 | |
| 1103 | |
| 1104 | @node Chaining |
| 1105 | @subsection Environment Chaining |
| 1106 | |
| 1107 | @cindex shadowing an imported variable binding |
| 1108 | @cindex chaining environments |
| 1109 | |
| 1110 | In the example of the previous subsection, we glossed over an important |
| 1111 | point. The body of the @code{let} expression in that example refers not |
| 1112 | only to the local variable @code{s}, but also to the top level variables |
| 1113 | @code{a}, @code{b}, @code{c} and @code{sqrt}. (@code{sqrt} is the |
| 1114 | standard Scheme procedure for calculating a square root.) If the body |
| 1115 | of the @code{let} expression is evaluated in the context of the |
| 1116 | @emph{local} @code{let} environment, how does the evaluation get at the |
| 1117 | values of these top level variables? |
| 1118 | |
| 1119 | The answer is that the local environment created by a @code{let} |
| 1120 | expression automatically has a reference to its containing environment |
| 1121 | --- in this case the top level environment --- and that the Scheme |
| 1122 | interpreter automatically looks for a variable binding in the containing |
| 1123 | environment if it doesn't find one in the local environment. More |
| 1124 | generally, every environment except for the top level one has a |
| 1125 | reference to its containing environment, and the interpreter keeps |
| 1126 | searching back up the chain of environments --- from most local to top |
| 1127 | level --- until it either finds a variable binding for the required |
| 1128 | identifier or exhausts the chain. |
| 1129 | |
| 1130 | This description also determines what happens when there is more than |
| 1131 | one variable binding with the same name. Suppose, continuing the |
| 1132 | example of the previous subsection, that there was also a pre-existing |
| 1133 | top level variable @code{s} created by the expression: |
| 1134 | |
| 1135 | @lisp |
| 1136 | (define s "Some beans, my lord!") |
| 1137 | @end lisp |
| 1138 | |
| 1139 | Then both the top level environment and the local @code{let} environment |
| 1140 | would contain bindings for the name @code{s}. When evaluating code |
| 1141 | within the @code{let} body, the interpreter looks first in the local |
| 1142 | @code{let} environment, and so finds the binding for @code{s} created by |
| 1143 | the @code{let} syntax. Even though this environment has a reference to |
| 1144 | the top level environment, which also has a binding for @code{s}, the |
| 1145 | interpreter doesn't get as far as looking there. When evaluating code |
| 1146 | outside the @code{let} body, the interpreter looks up variable names in |
| 1147 | the top level environment, so the name @code{s} refers to the top level |
| 1148 | variable. |
| 1149 | |
| 1150 | Within the @code{let} body, the binding for @code{s} in the local |
| 1151 | environment is said to @dfn{shadow} the binding for @code{s} in the top |
| 1152 | level environment. |
| 1153 | |
| 1154 | |
| 1155 | @node Lexical Scope |
| 1156 | @subsection Lexical Scope |
| 1157 | |
| 1158 | The rules that we have just been describing are the details of how |
| 1159 | Scheme implements ``lexical scoping''. This subsection takes a brief |
| 1160 | diversion to explain what lexical scope means in general and to present |
| 1161 | an example of non-lexical scoping. |
| 1162 | |
| 1163 | ``Lexical scope'' in general is the idea that |
| 1164 | |
| 1165 | @itemize @bullet |
| 1166 | @item |
| 1167 | an identifier at a particular place in a program always refers to the |
| 1168 | same variable location --- where ``always'' means ``every time that the |
| 1169 | containing expression is executed'', and that |
| 1170 | |
| 1171 | @item |
| 1172 | the variable location to which it refers can be determined by static |
| 1173 | examination of the source code context in which that identifier appears, |
| 1174 | without having to consider the flow of execution through the program as |
| 1175 | a whole. |
| 1176 | @end itemize |
| 1177 | |
| 1178 | In practice, lexical scoping is the norm for most programming languages, |
| 1179 | and probably corresponds to what you would intuitively consider to be |
| 1180 | ``normal''. You may even be wondering how the situation could possibly |
| 1181 | --- and usefully --- be otherwise. To demonstrate that another kind of |
| 1182 | scoping is possible, therefore, and to compare it against lexical |
| 1183 | scoping, the following subsection presents an example of non-lexical |
| 1184 | scoping and examines in detail how its behavior differs from the |
| 1185 | corresponding lexically scoped code. |
| 1186 | |
| 1187 | @menu |
| 1188 | * Scoping Example:: An example of non-lexical scoping. |
| 1189 | @end menu |
| 1190 | |
| 1191 | |
| 1192 | @node Scoping Example |
| 1193 | @subsubsection An Example of Non-Lexical Scoping |
| 1194 | |
| 1195 | To demonstrate that non-lexical scoping does exist and can be useful, we |
| 1196 | present the following example from Emacs Lisp, which is a ``dynamically |
| 1197 | scoped'' language. |
| 1198 | |
| 1199 | @lisp |
| 1200 | (defvar currency-abbreviation "USD") |
| 1201 | |
| 1202 | (defun currency-string (units hundredths) |
| 1203 | (concat currency-abbreviation |
| 1204 | (number-to-string units) |
| 1205 | "." |
| 1206 | (number-to-string hundredths))) |
| 1207 | |
| 1208 | (defun french-currency-string (units hundredths) |
| 1209 | (let ((currency-abbreviation "FRF")) |
| 1210 | (currency-string units hundredths))) |
| 1211 | @end lisp |
| 1212 | |
| 1213 | The question to focus on here is: what does the identifier |
| 1214 | @code{currency-abbreviation} refer to in the @code{currency-string} |
| 1215 | function? The answer, in Emacs Lisp, is that all variable bindings go |
| 1216 | onto a single stack, and that @code{currency-abbreviation} refers to the |
| 1217 | topmost binding from that stack which has the name |
| 1218 | ``currency-abbreviation''. The binding that is created by the |
| 1219 | @code{defvar} form, to the value @code{"USD"}, is only relevant if none |
| 1220 | of the code that calls @code{currency-string} rebinds the name |
| 1221 | ``currency-abbreviation'' in the meanwhile. |
| 1222 | |
| 1223 | The second function @code{french-currency-string} works precisely by |
| 1224 | taking advantage of this behaviour. It creates a new binding for the |
| 1225 | name ``currency-abbreviation'' which overrides the one established by |
| 1226 | the @code{defvar} form. |
| 1227 | |
| 1228 | @lisp |
| 1229 | ;; Note! This is Emacs Lisp evaluation, not Scheme! |
| 1230 | (french-currency-string 33 44) |
| 1231 | @result{} |
| 1232 | "FRF33.44" |
| 1233 | @end lisp |
| 1234 | |
| 1235 | Now let's look at the corresponding, @emph{lexically scoped} Scheme |
| 1236 | code: |
| 1237 | |
| 1238 | @lisp |
| 1239 | (define currency-abbreviation "USD") |
| 1240 | |
| 1241 | (define (currency-string units hundredths) |
| 1242 | (string-append currency-abbreviation |
| 1243 | (number->string units) |
| 1244 | "." |
| 1245 | (number->string hundredths))) |
| 1246 | |
| 1247 | (define (french-currency-string units hundredths) |
| 1248 | (let ((currency-abbreviation "FRF")) |
| 1249 | (currency-string units hundredths))) |
| 1250 | @end lisp |
| 1251 | |
| 1252 | According to the rules of lexical scoping, the |
| 1253 | @code{currency-abbreviation} in @code{currency-string} refers to the |
| 1254 | variable location in the innermost environment at that point in the code |
| 1255 | which has a binding for @code{currency-abbreviation}, which is the |
| 1256 | variable location in the top level environment created by the preceding |
| 1257 | @code{(define currency-abbreviation @dots{})} expression. |
| 1258 | |
| 1259 | In Scheme, therefore, the @code{french-currency-string} procedure does |
| 1260 | not work as intended. The variable binding that it creates for |
| 1261 | ``currency-abbreviation'' is purely local to the code that forms the |
| 1262 | body of the @code{let} expression. Since this code doesn't directly use |
| 1263 | the name ``currency-abbreviation'' at all, the binding is pointless. |
| 1264 | |
| 1265 | @lisp |
| 1266 | (french-currency-string 33 44) |
| 1267 | @result{} |
| 1268 | "USD33.44" |
| 1269 | @end lisp |
| 1270 | |
| 1271 | This begs the question of how the Emacs Lisp behaviour can be |
| 1272 | implemented in Scheme. In general, this is a design question whose |
| 1273 | answer depends upon the problem that is being addressed. In this case, |
| 1274 | the best answer may be that @code{currency-string} should be |
| 1275 | redesigned so that it can take an optional third argument. This third |
| 1276 | argument, if supplied, is interpreted as a currency abbreviation that |
| 1277 | overrides the default. |
| 1278 | |
| 1279 | It is possible to change @code{french-currency-string} so that it mostly |
| 1280 | works without changing @code{currency-string}, but the fix is inelegant, |
| 1281 | and susceptible to interrupts that could leave the |
| 1282 | @code{currency-abbreviation} variable in the wrong state: |
| 1283 | |
| 1284 | @lisp |
| 1285 | (define (french-currency-string units hundredths) |
| 1286 | (set! currency-abbreviation "FRF") |
| 1287 | (let ((result (currency-string units hundredths))) |
| 1288 | (set! currency-abbreviation "USD") |
| 1289 | result)) |
| 1290 | @end lisp |
| 1291 | |
| 1292 | The key point here is that the code does not create any local binding |
| 1293 | for the identifier @code{currency-abbreviation}, so all occurrences of |
| 1294 | this identifier refer to the top level variable. |
| 1295 | |
| 1296 | |
| 1297 | @node Closure |
| 1298 | @subsection Closure |
| 1299 | |
| 1300 | Consider a @code{let} expression that doesn't contain any |
| 1301 | @code{lambda}s: |
| 1302 | |
| 1303 | @lisp |
| 1304 | (let ((s (/ (+ a b c) 2))) |
| 1305 | (sqrt (* s (- s a) (- s b) (- s c)))) |
| 1306 | @end lisp |
| 1307 | |
| 1308 | @noindent |
| 1309 | When the Scheme interpreter evaluates this, it |
| 1310 | |
| 1311 | @itemize @bullet |
| 1312 | @item |
| 1313 | creates a new environment with a reference to the environment that was |
| 1314 | current when it encountered the @code{let} |
| 1315 | |
| 1316 | @item |
| 1317 | creates a variable binding for @code{s} in the new environment, with |
| 1318 | value given by @code{(/ (+ a b c) 2)} |
| 1319 | |
| 1320 | @item |
| 1321 | evaluates the expression in the body of the @code{let} in the context of |
| 1322 | the new local environment, and remembers the value @code{V} |
| 1323 | |
| 1324 | @item |
| 1325 | forgets the local environment |
| 1326 | |
| 1327 | @item |
| 1328 | continues evaluating the expression that contained the @code{let}, using |
| 1329 | the value @code{V} as the value of the @code{let} expression, in the |
| 1330 | context of the containing environment. |
| 1331 | @end itemize |
| 1332 | |
| 1333 | After the @code{let} expression has been evaluated, the local |
| 1334 | environment that was created is simply forgotten, and there is no longer |
| 1335 | any way to access the binding that was created in this environment. If |
| 1336 | the same code is evaluated again, it will follow the same steps again, |
| 1337 | creating a second new local environment that has no connection with the |
| 1338 | first, and then forgetting this one as well. |
| 1339 | |
| 1340 | If the @code{let} body contains a @code{lambda} expression, however, the |
| 1341 | local environment is @emph{not} forgotten. Instead, it becomes |
| 1342 | associated with the procedure that is created by the @code{lambda} |
| 1343 | expression, and is reinstated every time that that procedure is called. |
| 1344 | In detail, this works as follows. |
| 1345 | |
| 1346 | @itemize @bullet |
| 1347 | @item |
| 1348 | When the Scheme interpreter evaluates a @code{lambda} expression, to |
| 1349 | create a procedure object, it stores the current environment as part of |
| 1350 | the procedure definition. |
| 1351 | |
| 1352 | @item |
| 1353 | Then, whenever that procedure is called, the interpreter reinstates the |
| 1354 | environment that is stored in the procedure definition and evaluates the |
| 1355 | procedure body within the context of that environment. |
| 1356 | @end itemize |
| 1357 | |
| 1358 | The result is that the procedure body is always evaluated in the context |
| 1359 | of the environment that was current when the procedure was created. |
| 1360 | |
| 1361 | This is what is meant by @dfn{closure}. The next few subsections |
| 1362 | present examples that explore the usefulness of this concept. |
| 1363 | |
| 1364 | |
| 1365 | @node Serial Number |
| 1366 | @subsection Example 1: A Serial Number Generator |
| 1367 | |
| 1368 | This example uses closure to create a procedure with a variable binding |
| 1369 | that is private to the procedure, like a local variable, but whose value |
| 1370 | persists between procedure calls. |
| 1371 | |
| 1372 | @lisp |
| 1373 | (define (make-serial-number-generator) |
| 1374 | (let ((current-serial-number 0)) |
| 1375 | (lambda () |
| 1376 | (set! current-serial-number (+ current-serial-number 1)) |
| 1377 | current-serial-number))) |
| 1378 | |
| 1379 | (define entry-sn-generator (make-serial-number-generator)) |
| 1380 | |
| 1381 | (entry-sn-generator) |
| 1382 | @result{} |
| 1383 | 1 |
| 1384 | |
| 1385 | (entry-sn-generator) |
| 1386 | @result{} |
| 1387 | 2 |
| 1388 | @end lisp |
| 1389 | |
| 1390 | When @code{make-serial-number-generator} is called, it creates a local |
| 1391 | environment with a binding for @code{current-serial-number} whose |
| 1392 | initial value is 0, then, within this environment, creates a procedure. |
| 1393 | The local environment is stored within the created procedure object and |
| 1394 | so persists for the lifetime of the created procedure. |
| 1395 | |
| 1396 | Every time the created procedure is invoked, it increments the value of |
| 1397 | the @code{current-serial-number} binding in the captured environment and |
| 1398 | then returns the current value. |
| 1399 | |
| 1400 | Note that @code{make-serial-number-generator} can be called again to |
| 1401 | create a second serial number generator that is independent of the |
| 1402 | first. Every new invocation of @code{make-serial-number-generator} |
| 1403 | creates a new local @code{let} environment and returns a new procedure |
| 1404 | object with an association to this environment. |
| 1405 | |
| 1406 | |
| 1407 | @node Shared Variable |
| 1408 | @subsection Example 2: A Shared Persistent Variable |
| 1409 | |
| 1410 | This example uses closure to create two procedures, @code{get-balance} |
| 1411 | and @code{deposit}, that both refer to the same captured local |
| 1412 | environment so that they can both access the @code{balance} variable |
| 1413 | binding inside that environment. The value of this variable binding |
| 1414 | persists between calls to either procedure. |
| 1415 | |
| 1416 | Note that the captured @code{balance} variable binding is private to |
| 1417 | these two procedures: it is not directly accessible to any other code. |
| 1418 | It can only be accessed indirectly via @code{get-balance} or |
| 1419 | @code{deposit}, as illustrated by the @code{withdraw} procedure. |
| 1420 | |
| 1421 | @lisp |
| 1422 | (define get-balance #f) |
| 1423 | (define deposit #f) |
| 1424 | |
| 1425 | (let ((balance 0)) |
| 1426 | (set! get-balance |
| 1427 | (lambda () |
| 1428 | balance)) |
| 1429 | (set! deposit |
| 1430 | (lambda (amount) |
| 1431 | (set! balance (+ balance amount)) |
| 1432 | balance))) |
| 1433 | |
| 1434 | (define (withdraw amount) |
| 1435 | (deposit (- amount))) |
| 1436 | |
| 1437 | (get-balance) |
| 1438 | @result{} |
| 1439 | 0 |
| 1440 | |
| 1441 | (deposit 50) |
| 1442 | @result{} |
| 1443 | 50 |
| 1444 | |
| 1445 | (withdraw 75) |
| 1446 | @result{} |
| 1447 | -25 |
| 1448 | @end lisp |
| 1449 | |
| 1450 | An important detail here is that the @code{get-balance} and |
| 1451 | @code{deposit} variables must be set up by @code{define}ing them at top |
| 1452 | level and then @code{set!}ing their values inside the @code{let} body. |
| 1453 | Using @code{define} within the @code{let} body would not work: this |
| 1454 | would create variable bindings within the local @code{let} environment |
| 1455 | that would not be accessible at top level. |
| 1456 | |
| 1457 | |
| 1458 | @node Callback Closure |
| 1459 | @subsection Example 3: The Callback Closure Problem |
| 1460 | |
| 1461 | A frequently used programming model for library code is to allow an |
| 1462 | application to register a callback function for the library to call when |
| 1463 | some particular event occurs. It is often useful for the application to |
| 1464 | make several such registrations using the same callback function, for |
| 1465 | example if several similar library events can be handled using the same |
| 1466 | application code, but the need then arises to distinguish the callback |
| 1467 | function calls that are associated with one callback registration from |
| 1468 | those that are associated with different callback registrations. |
| 1469 | |
| 1470 | In languages without the ability to create functions dynamically, this |
| 1471 | problem is usually solved by passing a @code{user_data} parameter on the |
| 1472 | registration call, and including the value of this parameter as one of |
| 1473 | the parameters on the callback function. Here is an example of |
| 1474 | declarations using this solution in C: |
| 1475 | |
| 1476 | @example |
| 1477 | typedef void (event_handler_t) (int event_type, |
| 1478 | void *user_data); |
| 1479 | |
| 1480 | void register_callback (int event_type, |
| 1481 | event_handler_t *handler, |
| 1482 | void *user_data); |
| 1483 | @end example |
| 1484 | |
| 1485 | In Scheme, closure can be used to achieve the same functionality without |
| 1486 | requiring the library code to store a @code{user-data} for each callback |
| 1487 | registration. |
| 1488 | |
| 1489 | @lisp |
| 1490 | ;; In the library: |
| 1491 | |
| 1492 | (define (register-callback event-type handler-proc) |
| 1493 | @dots{}) |
| 1494 | |
| 1495 | ;; In the application: |
| 1496 | |
| 1497 | (define (make-handler event-type user-data) |
| 1498 | (lambda () |
| 1499 | @dots{} |
| 1500 | <code referencing event-type and user-data> |
| 1501 | @dots{})) |
| 1502 | |
| 1503 | (register-callback event-type |
| 1504 | (make-handler event-type @dots{})) |
| 1505 | @end lisp |
| 1506 | |
| 1507 | As far as the library is concerned, @code{handler-proc} is a procedure |
| 1508 | with no arguments, and all the library has to do is call it when the |
| 1509 | appropriate event occurs. From the application's point of view, though, |
| 1510 | the handler procedure has used closure to capture an environment that |
| 1511 | includes all the context that the handler code needs --- |
| 1512 | @code{event-type} and @code{user-data} --- to handle the event |
| 1513 | correctly. |
| 1514 | |
| 1515 | |
| 1516 | @node OO Closure |
| 1517 | @subsection Example 4: Object Orientation |
| 1518 | |
| 1519 | Closure is the capture of an environment, containing persistent variable |
| 1520 | bindings, within the definition of a procedure or a set of related |
| 1521 | procedures. This is rather similar to the idea in some object oriented |
| 1522 | languages of encapsulating a set of related data variables inside an |
| 1523 | ``object'', together with a set of ``methods'' that operate on the |
| 1524 | encapsulated data. The following example shows how closure can be used |
| 1525 | to emulate the ideas of objects, methods and encapsulation in Scheme. |
| 1526 | |
| 1527 | @lisp |
| 1528 | (define (make-account) |
| 1529 | (let ((balance 0)) |
| 1530 | (define (get-balance) |
| 1531 | balance) |
| 1532 | (define (deposit amount) |
| 1533 | (set! balance (+ balance amount)) |
| 1534 | balance) |
| 1535 | (define (withdraw amount) |
| 1536 | (deposit (- amount))) |
| 1537 | |
| 1538 | (lambda args |
| 1539 | (apply |
| 1540 | (case (car args) |
| 1541 | ((get-balance) get-balance) |
| 1542 | ((deposit) deposit) |
| 1543 | ((withdraw) withdraw) |
| 1544 | (else (error "Invalid method!"))) |
| 1545 | (cdr args))))) |
| 1546 | @end lisp |
| 1547 | |
| 1548 | Each call to @code{make-account} creates and returns a new procedure, |
| 1549 | created by the expression in the example code that begins ``(lambda |
| 1550 | args''. |
| 1551 | |
| 1552 | @lisp |
| 1553 | (define my-account (make-account)) |
| 1554 | |
| 1555 | my-account |
| 1556 | @result{} |
| 1557 | #<procedure args> |
| 1558 | @end lisp |
| 1559 | |
| 1560 | This procedure acts as an account object with methods |
| 1561 | @code{get-balance}, @code{deposit} and @code{withdraw}. To apply one of |
| 1562 | the methods to the account, you call the procedure with a symbol |
| 1563 | indicating the required method as the first parameter, followed by any |
| 1564 | other parameters that are required by that method. |
| 1565 | |
| 1566 | @lisp |
| 1567 | (my-account 'get-balance) |
| 1568 | @result{} |
| 1569 | 0 |
| 1570 | |
| 1571 | (my-account 'withdraw 5) |
| 1572 | @result{} |
| 1573 | -5 |
| 1574 | |
| 1575 | (my-account 'deposit 396) |
| 1576 | @result{} |
| 1577 | 391 |
| 1578 | |
| 1579 | (my-account 'get-balance) |
| 1580 | @result{} |
| 1581 | 391 |
| 1582 | @end lisp |
| 1583 | |
| 1584 | Note how, in this example, both the current balance and the helper |
| 1585 | procedures @code{get-balance}, @code{deposit} and @code{withdraw}, used |
| 1586 | to implement the guts of the account object's methods, are all stored in |
| 1587 | variable bindings within the private local environment captured by the |
| 1588 | @code{lambda} expression that creates the account object procedure. |
| 1589 | |
| 1590 | |
| 1591 | @c Local Variables: |
| 1592 | @c TeX-master: "guile.texi" |
| 1593 | @c End: |