1| /-------------------------------------------\ 2| |*******************************************| 3| |*** ***| 4| |*** PRINCIPLES OF PROGRAMMING LANGUAGES ***| 5| |*** ***| 6| |*******************************************| 7| \-------------------------------------------/ 8| 9| This course is about building COMPUTATIONAL PROCESSES. We need 10| computational processes for computing functions, and for performing 11| computational tasks. The means for performing computational processes are 12| PROGRAMS. 13| 14| The POWER and WEAKNESS of a computational process, realized within a 15| program depends on: 16| 1. Quality of the description/understanding of the computational process: 17| How it is split and combined from simpler processes; 18| How clear the structures used are; 19| How natural is the organization of the process; 20| etc. 21| 2. How powerful is the language used to write the program: 22| Does it support the needed structures; 23| Does it enable high level thinking, ignoring irrelevant details; 24| etc. 25| 26| Using a powerful, elegant language that can account for all 27| computational processes that we wish to study, without requiring too much 28| time in learning the language's details can greatly simplify the study of 29| programming computational processes. 30| 31| In this course we do it by using the language ***SCHEME*** as a means 32| for the study of computational processes. This is NOT a course *about* 33| Scheme, but a course carried out *in* Scheme. 34| We use Scheme because it is SMALL and POWERFUL: 35| SMALL-- It has a very simple syntax, with few details. 36| POWERFUL-- It combines, in an elegant way, the ideas of **functional** 37| programming (LISP), and **imperative** programming (ALGOL-60, 38| Pascal, C). 39| It can be used to demonstrate *ALL* programming approaches. 40| 41| We cover the subjects: 42| 1. Abstraction as a major computation means: 43| Abstraction with procedures. 44| Abstraction with data. 45| Typing. 46| Scoping. 47| 2. Evaluation of procedures: 48| Substitution model. 49| Normal-order model. 50| Assignments and the environments model. 51| Methods for parameter passing. 52| 3. Mutable data: lists, queues, tables. 53| 4. Principles of object-oriented programming; message passing. 54| 5. Streams and delayed evaluation. 55| 6. Packages. 56| 7. Principles of logic programming. 57| 60| 61| TEXTBOOKS: 62| ~~~~~~~~~~ 63| 1. Abelson & Sussman: Structure and Interpretation of Computer Programs. 64| MIT Press, 1996 (2nd Ed). 65| 2. Springer & Friedman: Scheme and the Art of Programming. 66| MIT Press, 1989. 70| 71| A language for expressing computational processes needs: 72| 73| 1. Primitive expressions. 74| 2. Combination means: Create compound expressions from simpler ones. 75| 3. Abstraction: Give a compound object a name, and manipulate it as a 76| unit. 77| 4. Reference: Mention possibly already abstracted units by their names. 78| 79| Scheme possesses these four features in an extremely clean and elegant 80| way: 81| The objects to be combined are all of a SINGLE KIND; 82| abstraction of a combination yields an object of the SAME KIND; 83| naming that object enables reference to it in other contexts. 84| There is a SINGLE kind of object that can be 85| COMBINED, ABSTRACTED, NAMED, and REFERENCED. 86| This elegancy is based on a uniform approach to DATA and PROCEDURES: 87| Except for some primitive expressions, everything can be both DATA and 88| PROCEDURES. It all depends on how objects are used. Procedures can be data 89| to be combined, abstracted into other procedures, named, and APPLIED. 90| This elegancy frees us from learning the details of many data structures, 91| and the rules for using them, and is the source of power of functional 92| languages. 93| 94| 95| CHAPTER 1 96| ~~~~~~~~~ 97| 98| BUILDING ABSTRACTIONS WITH PROCEDURES 99| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 100| 101| 102| 103| 1.1 THE ELEMENTS OF PROGRAMMING 104| =============================== 105| 106| 1.1.1 EXPRESSIONS 107| ~~~~~~~~~~~~~~~~~ 108| 109| steel ~ 12 eli> scm 110| ;;; 111| ;;; Expressions 112| ;;; ~~~~~~~~~~~ 113| > 467 114| 467 115| ;;; This is a primitive expression. 116| > (+ 45 78) 117| 123 118| > (- 56 9) 119| 47 120| > (* 6 50) 121| 300 122| > (/ 25 5) 123| 5 124| > ^D 125| ;;; The compound expressions are called FORMS or COMBINATIONS. They are 126| ;;; list expressions. The leftmost expression is the OPERATOR, the rest 127| ;;; are the OPERANDS. 128| ;;; The VALUE of the combination is obtained by applying the procedure 129| ;;; specified by the operator to the arguments that are the VALUES of 130| ;;; the operands. 131| ;;; Prefix notation in LISP forms. 132| ;;; More examples of combinations: 133| ;;; (5 9), (*5 9), (5 * 9), (* (5 9)). 134| ;;; 135| ;;; Nesting forms: 136| ;;; ~~~~~~~~~~~~~~ 137| > (/ 25 6) 138| 4.16666666666667 139| > (+ 1.5 3) 140| 4.5 141| > (+ 2 10 75.7) 142| 87.7 143| > (+ (* 3 15) (- 9 2)) 144| 52 145| > (+ (* 3 (+ (* 2 4) (+ 13 5))) (+ (- 10 5) 3)) 146| 86 147| ;;; 148| ;;; Pretty printing: 149| ;;; ~~~~~~~~~~~~~~~~ 150| > (+ (* 3 151| (+ (* 2 4) 152| (+ 13 5))) 153| (+ (- 10 5) 154| 3)) 155| 86 156| 157| ;;; The Scheme interpreter operates in a READ-EVAL-PRINT loop. 158| ;;; 159| ;;; 160| ;;; 1.1.2 Naming and the Environment 161| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 162| ;;; 163| ;;; Naming computational objects is an essential feature of any 164| ;;; programming language. Whenever we use naming we have a NAME that 165| ;;; identifies a variable, and a VALUE which is the named object. 166| ;;; "define" is the Scheme's operator for "naming". It declares a 167| ;;; variable, and binds it to a value. 168| (define size 6) 169| # 170| ;;; size is now a name, associated with the value 6. 171| ;;; The VALUE of the last combination is unspecified. 172| > size 173| 6 174| > (* 2 size) 175| 12 176| > (define a 3) 177| # 178| > (+ a (* size 1.5)) 179| 12 180| > (define result (+ a (* size 1.5)) ) 181| # 182| > result 183| 12 184| ;;; 'define' is the simplest means of ABSTRACTION: It allows for using 185| ;;; names for the results of complex operations. 186| ;;; Enables INCREMENTAL DEVELOPMENT of programs. 187| ;;; 188| ;;; ENVIRONMENT: The memory that keeps track of the name-value pairs. 189| ;;; So far, the pairs defined by 'define' are kept in the GLOBAL 190| ;;; ENVIRONMENT. A name-value pair is called a BINDING. An environment is 191| ;;; a place where bindings are defined. Names can be re-defined. 192| ;;; 193| ;;; Characters in names: Any character, except space and parentheses. 194| ;;; Numbers cannot function as names. 195| ;;; Note the uniform treatment of names: 196| > (define + (* 2 3)) 197| WARNING: redefining built-in + 198| # 199| > + 200| 6 201| > (+ 2 3) 202| ERROR: Wrong type to apply: 6 203| ; in expression: (... + 2 3) 204| ; in top level environment. 205| > (* 2 +) 206| 12 207| 208| 209| ;;; 1.1.3 Evaluating Combinations 210| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 211| ;;; Computation is carried out by following specified instructions. 212| ;;; In Scheme, a computation is carried out by EVALUATING combinations. 213| ;;; The operation of the Scheme interpreter on a combination is called 214| ;;; EVALUATION of combinations. 215| ;;; 216| ;;; The evaluation process for a combination that is not a definition: 217| ;;; 1. EVALUATE all subexpressions of the combination. 218| ;;; 2. APPLY the procedure which is the VALUE of the leftmost 219| ;;; subexpression, to the VALUES of the other subexpressions. 220| ;;; If the first subexpression does not evaluate into a procedure -- 221| ;;; FAIL. For example: (5* 9). 222| ;;; 223| ;;; The evaluation rule is RECURSIVE: 224| ;;; 225| > (* (+ 4 (+ 5 7)) 226| (* 6 1 9)) 227| 864 228| ;;; 229| ;;; We can visualize the evaluation process by drowing an "evaluation 230| ;;; tree", in which each combination is assigned an internal node, whose 231| ;;; direct descendents are the operator and operands of the combination. 232| ;;; The evaluation process is carried out from the leafs to the root, 233| ;;; where every combination node is replaced by the value of applying its 234| ;;; operator child to its operands children: 235| 236| ------------------864------------- 237| | | 238| * ------16---- ----54------- 239| | | | | | | | 240| + 4 ---12---- * 6 1 9 241| | | | 242| + 5 7 243| 244| ;;; Evaluation of primitive expressions: 245| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 246| ;;; 1. Numerals evaluate to the numberes they denote. 247| ;;; 2. Built-in operators evaluate to the machine instruction sequences 248| ;;; that perform the denoted operation. 249| ;;; 3. All other names evaluate to the objects (values) associated with 250| ;;; them in the environment (for example, via 'define' combinations). 251| ;;; 252| ;;; Note the importance of ENVIRONMENT in determining the meaning of 253| ;;; symbols. The environment is the place where the meanings of symbols 254| ;;; are defined. In a multiple environments framework, the same symbol 255| ;;; might have different meanings in different environments. 256| ;;; Apart from numerals and built-in procedures, ALL evaluations are 257| ;;; environment dependent. 258| ;;; 259| ;;; Special forms: 260| ;;; Forms that do not evaluate by the above rules. 261| ;;; For example: 'define' forms--the second expression is NOT evaluated. 262| ;;; 263| ;;; SUMMARY: 1. Numbers and arithmetic operation are primitive data and 264| ;;; operations. 265| ;;; 2. Operators can be combined by Nesting of combinations. 266| ;;; 3. The "define" operator associates names with values. 267| ;;; (abstraction). 268| ;;; 269| ;;; 1.1.4 Compound Procedures 270| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 271| ;;; Procedure definition is an abstraction mechanism that associates a 272| ;;; name with a compound operation. The compound operation turns into a 273| ;;; single unit. 274| ;;; 275| > (define (square x) (* x x)) 276| # 277| ;;; The evaluation of the "define" form associates the name "square" with 278| ;;; the procedure (* x x) with **formal parameter** x, in the current 279| ;;; environment (global). That is, this evaluation results the following 280| ;;; BINDING in the global environment: 281| ;;; square <---> procedure with: formal parameters (x), 282| ;;; body (* x x) 283| ;;; Note that a procedure is treated as just ANY value, that can be given 284| ;;; a name!! Also, distinguish between **procedure definition** to 285| ;;; **procedure call/application**. 286| ;;; 287| ;;; Syntax of procedure definition: 288| ;;; ( define ( ) ) 289| ;;; is a symbol. 290| ;;; is a sequence of names (to name the arguments of 291| ;;; the procedure). 292| ;;; is an expression (or a sequence of expressions). 293| ;;; The value of in the environment is the procedure definition. 294| ;;; The value of the "define" combination is . 295| ;;; Intuitively: When the procedure is applied, the formal 296| ;;; parameters in are replaced by **actual arguments**, and the 297| ;;; value of the application form is the value of the last expression in 298| ;;; . 299| > (square 4) 300| 16 301| > (square (+ 2 5)) 302| 49 303| > (square (square 4)) 304| 256 305| > (define (sum-of-squares x y) 306| (+ (square x) (square y ))) 307| # 308| > (sum-of-squares 3 4) 309| 25 310| > (define (f a) 311| (sum-of-squares (+ a 1) (* a 2) ) ) 312| # 313| > (f 3) 314| 52 315| ;;; A procedure is a VALUE like any other value. A definition of a 316| ;;; compound procedure associates a name with a value which is a 317| ;;; peocedure. The above syntax for definition of compound procedures is, 318| ;;; actually, a syntactic sugar for the real definition: 319| > (define square (lambda (x) (* x x)) 320| # 321| ;;; 'lambda' is a built-in procedure for "making" procedure values. 322| ;;; In the above definition, the name 'square' is associated with the 323| ;;; procedure object (lambda (x) (* x x)). 324| ;;; We see also that, actually, there is a SINGLE syntax for associating 325| ;;; names with values. The special syntax for procedure definitions is 326| ;;; just a "syntactic sugar". 327| ;;; 328| ;;; Try to re-define 'lambda' and see what happens to procedure 329| ;;; definitions. 330| ;;; 331| ;;; 332| ;;; 1.1.5 The Substitution Model for Procedure Application -- 333| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 334| ;;; Applicative-Order Evaluation 335| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 336| ;;; Evaluation of a form whose operator is a compound procedure: 337| ;;; Same rules-- Evaluate the elements of the combination, and APPLY THE 338| ;;; PROCEDURE which is the value of the operator of the combination, to 339| ;;; the ARGUMENTS, which are the values of the operands of the 340| ;;; combination. 341| ;;; What is the mechanism for PROCEDURE APPLICATION? 342| ;;; +-------------------------------------------------------------------+ 343| ;;; | I. For primitive procedure: Built into the interpreter. | 344| ;;; | II. For compound procedure: | 345| ;;; | 1. EVALUATE the elements of the combination. | 346| ;;; | 2. SUBSTITUTE: Replace each formal parameter in the body of | 347| ;;; | the procedure, by the corresponding argument. | 348| ;;; | 3. REDUCTION: Evaluate the resulting body of the procedure. | 349| ;;; | The value of the form is the value of the procedure application. | 350| ;;; +-------------------------------------------------------------------+ 351| ;;; 352| ;;; Example of using the SUBSTITUTION MODEL FOR PROCEDURE APPLICATION 353| ;;; (we use STACK like writing to keep track of the order of operations): 354| > (f 5) 355| 136 356| ;;; Evaluation of (f 5) follows the following steps: 357| ;;; 1. The value of f is: procedure with formal parameters (a) 358| ;;; body: (sum-of-squares (+ a 1) (* a 2) ) 359| ;;; The value of 5 is 5. 360| ;;; 2. Substitution yields: (sum-of-squares (+ 5 1) (* 5 2) ) 361| ;;; 3. Reduction: Evaluation of the new form: 362| ;;; 1. The value of sum-of-squares is: 363| ;;; procedure with formal parameters (x y) 364| ;;; body: (+ (square x) (square y )) 365| ;;; Evaluation of the operands: 6 for the first argument, 366| ;;; 10 for the second. 367| ;;; 2.Substitution: (+ (square 6) (square 10 )) 368| ;;; 3. Reduction: Evaluation of the form: (+ (square 6) (square 10 )) 369| ;;; 1. Evaluation of (square 6): 370| ;;; 1. Value of square is the definition of the square procedure. 371| ;;; 2. Substitution: (* 6 6) 372| ;;; 3. Reduction: Evaluate (* 6 6) 373| ;;; 3. Reduction: 36 374| ;;; Evaluation of (square 10): 375| ;;; 1. Value of square is the definition of the square procedure. 376| ;;; 2. Substitution: (* 10 10) 377| ;;; 3. Reduction: Evaluate (* 10 10) 378| ;;; 3. Reduction: 100 379| ;;; 3. Reduction: Evaluate (+ 36 100) 380| ;;; 3. 136 381| ;;; 382| ;;; The evaluation of a form with a compound procedure can be visualized 383| ;;; by a STACK of forms and BINDINGS waiting to be evaluated. 384| ;;; Evaluation of elements of the form ADDS bindings to the stack. 385| ;;; In the substitution step, the formal parameters are treated as part 386| ;;; of a LOCAL ENVIRONMENT, where they are BOUND to the values of the 387| ;;; actual arguments. 388| ;;; In the reduction step, the top combination and bindings are replaced 389| ;;; by the result of the substitution step. 390| ;;; (f 5) 391| ;;; f: procedure (a) (sum-of-squares (+ a 1) (* a 2) ) 392| ;;; 5 393| ;;; a: 5 394| ;;; 395| ;;; (sum-of-squares (+ 5 1) (* 5 2) ) 396| ;;; sum-of-squares: procedure (x y) (+ (square x) (square y )) 397| ;;; (+ 5 1) 398| ;;; 399| ;;; (sum-of-squares (+ 5 1) (* 5 2) ) 400| ;;; sum-of-squares: procedure (x y) (+ (square x) (square y )) 401| ;;; (+ 5 1) 402| ;;; + 403| ;;; 5 404| ;;; 1 405| ;;; 406| ;;; (sum-of-squares (+ 5 1) (* 5 2) ) 407| ;;; sum-of-squares: procedure (x y) (+ (square x) (square y )) 408| ;;; 6 409| ;;; 410| ;;; (sum-of-squares (+ 5 1) (* 5 2) ) 411| ;;; sum-of-squares: procedure (x y) (+ (square x) (square y )) 412| ;;; 6 413| ;;; (* 5 2) 414| ;;; 415| ;;; (sum-of-squares (+ 5 1) (* 5 2) ) 416| ;;; sum-of-squares: procedure (x y) (+ (square x) (square y )) 417| ;;; 6 418| ;;; (* 5 2) 419| ;;; * 420| ;;; 5 421| ;;; 2 422| ;;; 423| ;;; (sum-of-squares (+ 5 1) (* 5 2) ) 424| ;;; sum-of-squares: procedure (x y) (+ (square x) (square y )) 425| ;;; 6 426| ;;; 10 427| ;;; 428| ;;; (sum-of-squares (+ 5 1) (* 5 2) ) 429| ;;; sum-of-squares: procedure (x y) (+ (square x) (square y )) 430| ;;; 6 431| ;;; 10 432| ;;; x: 6 433| ;;; y: 10 434| ;;; 435| ;;; (+ (square 6) (square 10)) 436| ;;; + 437| ;;; (square 6) 438| ;;; 439| ;;; (+ (square 6) (square 10)) 440| ;;; + 441| ;;; (square 6) 442| ;;; square: procedure (x) (* x x) 443| ;;; 6 444| ;;; x: 6 445| ;;; 446| ;;; (+ (square 6) (square 10)) 447| ;;; + 448| ;;; (* 6 6) 449| ;;; 450| ;;; (+ (square 6) (square 10)) 451| ;;; + 452| ;;; (* 6 6) 453| ;;; * 454| ;;; 6 455| ;;; 6 456| ;;; 457| ;;; (+ (square 6) (square 10)) 458| ;;; + 459| ;;; 36 460| ;;; (square 10) 461| ;;; 462| ;;; (+ (square 6) (square 10)) 463| ;;; + 464| ;;; 36 465| ;;; (square 10) 466| ;;; square: procedure (x) (* x x) 467| ;;; 10 468| ;;; x: 10 469| ;;; 470| ;;; (+ (square 6) (square 10)) 471| ;;; + 472| ;;; 36 473| ;;; (* 10 10) 474| ;;; 475| ;;; (+ (square 6) (square 10)) 476| ;;; + 477| ;;; 36 478| ;;; (* 10 10) 479| ;;; * 480| ;;; 10 481| ;;; 10 482| ;;; 483| ;;; (+ (square 6) (square 10)) 484| ;;; + 485| ;;; 36 486| ;;; 100 487| ;;; 488| ;;; 136 489| ;;; 490| ;;; 491| ;;; Another example-- A procedure with no formal parameters, and with a 492| ;;; primitive expression as body: 493| > (define (five) 5) 494| five 495| ;;; This equivalent to: 496| > (define five (lambda () 5)) 497| # 498| ;;; 499| ;;; Evaluation of (five) 500| ;;; (five) 501| ;;; 502| ;;; (five) 503| ;;; five: (lambda () 5) 504| ;;; 505| ;;; 5 506| 507| > (define four 4) 508| # 509| > four 510| 4 511| > (four) 512| ERROR: Wrong type to apply: 4 513| ; in expression: (... four) 514| ; in top level environment. 515| > five 516| # 517| ;;; Note: In practice, interpreters do not literally follow the 518| ;;; substitution model. Operating on the text of a procedure body 519| ;;; is very expensive. Typically, interpreters generate "local 520| ;;; environment" for the formal parameters, in which they are bound 521| ;;; to their corresponding actual arguments. The text is not really 522| ;;; rewritten for every application. 523| ;;; 524| ;;; +--------------------------------------------------------------------+ 525| ;;; | The substitution model uses the CALL-BY-VALUE method for | 526| ;;; | PARAMETER PASSING method: In procedure application, the VALUES of | 527| ;;; | the actual arguments are substituted for the formal parameters. | 528| ;;; | This is the STANDARD eveluation model in Scheme (LISP), and the | 529| ;;; | most frequent in other languages (PASCAL, C). | 530| ;;; +--------------------------------------------------------------------+ 531| ;;; 532| ;;; An Alternative Evaluation Model for a form--NORMAL ORDER EVALUATION: 533| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 534| ;;; 1. EXPANSION: 535| ;;; For each element of the form that includes a non-primitive 536| ;;; operator do: 537| ;;; a. Evaluate the operator. 538| ;;; b. Substitute the actual arguments (without any evaluation) for 539| ;;; the formal parameters in the procedure's body. 540| ;;; c. Replace the element form by the result of step b. 541| ;;; 2. Reduction: 542| ;;; Evaluate the primitive forms from inside outside. 543| ;;; 544| ;;; Example: 545| ;;; Expansions: In this step there are no evaluations, just replacements. 546| ;;; We write the sucessive replacements, following step c (no stack): 547| ;;; (f 5) 548| ;;; (sum-of-squares (+ 5 1) (* 5 2) ) 549| ;;; (+ (square (+ 5 1)) (square (* 5 2) ) ) 550| ;;; (+ (* (+ 5 1) (+ 5 1) ) (* (* 5 2) (* 5 2) ) ) 551| ;;; Reductions: (+ (* 6 6) (* 10 10) ) 552| ;;; (+ 36 100) 553| ;;; 136 554| ;;; 555| ;;; Note: Result is the same, but some evaluations are repeated. 556| ;;; 557| ;;; This evaluation model is called: NORNAL-ORDER EVALUATION. 558| ;;; 559| ;;; Most interpreters use application-order evaluation. 560| ;;; 561| ;;; +--------------------------------------------------------------------+ 562| ;;; | The normal-order evaluation model uses the CALL-BY-NAME method for| 563| ;;; | PARAMETER PASSING method: In procedure application, the actual | 564| ;;; | arguments themselves are substituted for the formal parameters. | 565| ;;; | This eveluation model is used in Scheme (LISP) for SPECIAL FORMS, | 566| ;;; | and for DELAYED EVALUATION when infinite structures (streams) are | 567| ;;; | used. Call be name was first introduced in ALGOL-60. | 568| ;;; +--------------------------------------------------------------------+ 569| ;;; 570| 571| (exit) 572| Script started on Wed Feb 26 11:49:14 1992 573| 1>> scm 574| > ;; 1.1.6 CONDITIONAL EXPRESSIONS and PREDICATES 575| ;;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 576| 577| ;;; Absolute value function: 578| (define (abs x) 579| (cond ((> x 0) x) 580| ((= x 0) 0) 581| ((< x 0) (- x)))) 582| # 583| > (abs -6) 584| 6 585| > (abs (* -1 3)) 586| 3 587| ;;; Form of conditional expression: 588| ;;; (cond ( ) 589| ;;; ( ) 590| ;;; ... 591| ;;; ( ) ) 592| ;;; 593| ;;; The arguments of "cond" are pairs (

), where

is a 594| ;;; PREDICATION (binary expression) and is any Scheme expression. 595| ;;; ( can be a sequence of expressions). 596| ;;; A predication is an expression whose value is interpreted as either 597| ;;; false or true. The operator of a predication is a PREDICATE>. 598| ;;; The "false" value is represented by the symbol "nil", whose value is 599| ;;; nil (#f). The symbol "t" represents "true". 600| > nil 601| #f 602| > t 603| #t 604| > (> 3 0) 605| #t 606| > (< 3 0) 607| #f 608| > 609| ;;; Evaluation of conditional expressions: 610| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 611| ;;; is evaluated first. If the value is false then is 612| ;;; evaluated. If its value is false then element of that pair is evaluated, and this is the 615| ;;; value of the "cond" form. If no predicate evaluates to true, the 616| ;;; value of the conditional is unspecified. 617| ;;; Definition: a PREDICATE is a procedure (primitive or not), that 618| ;;; returns the values true or false. 619| ;;; 620| (cond (nil t) 621| ( (not nil) nil) ) 622| #f 623| > (cond (#f t)) 624| # 625| > 626| ;;; Another syntax for conditional: 627| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 628| (define (abs x) 629| (cond ((< x 0) (- x)) 630| (else x))) 631| # 632| ;;; "else" is a special symbol that can replace the predication

in the 633| ;;; last pair. If all previous pairs in the conditional expression have 634| ;;; been bypassed, the that follows the "else" symbol is evaluated and 635| ;;; returned as the value of the conditional. "else" can be replaced by 636| ;;; any "always true" expression. 637| ;;; 638| ;;; Another syntax for conditional: 639| ;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 640| (define (abs x) 641| (if (< x 0) 642| (- x) 643| x)) 644| # 645| ;;; The syntax of "if" expressions: 646| ;;; (if ) 647| ;;; if is true the is 649| ;;; is evaluated and its value returned as the value of the "if" form. 650| ;;; 651| ;;; Note: "if" is a restricted form of "cond". 652| ;;; 653| ;;; Arithmetic predicates: <, =, >. 654| ;;; Logical predicates: and, or, not. 655| ;;; 656| (<= 3 4) 657| #t 658| > (>= 3 4) 659| #f 660| > (define (>= x y) 661| (or (> x y) (= x y))) 662| WARNING: redefining built-in >= 663| # 664| > (>= 6 5) 665| #t 666| > (define (>= x y) 667| (not (< x y))) 668| # 669| > (exit) 670| ;;; 671| ;;; Conditional expressions can be used like any other expression: 672| > (define a 3) 673| # 674| > (define b 4) 675| # 676| > (+ 2 (if (> a b) a b) ) 677| 6 678| > (* (cond ( (> a b) a) 679| ( (< a b) b) 680| (else -1 ) ) 681| (+ a b) ) 682| 28 683| > ( (if (> a b) + -) a b) 684| -1 685| 686| 1.1.7 Example: Square roots by Newoton's Method 687| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 688| 689| The mathematical definition of 'square root' is DECLARATIVE: 690| *** The square root of x is THE y such that its square is x. *** 691| This definition does not tell us HOW TO COMPUTE square-root(x); it just 692| tells us what are the properties of square-root(x). Such descriptions are 693| called DECLARATIVE. The purpose of intelligent systems is to be able to 694| perform declaratively stated processes. In such systems, the user will not 695| have to tell the machine HOW TO COMPUTE the process, but just to declare 696| WHAT ARE THE PROPERTIES of the desired process. 697| A declarative description corresponds to a FUNCTION; 698| A procedural/imperative description corresponds to a COMPUTATIONAL PROCESS 699| 700| In order to compute 'square-root' we need a PROCEDURAL/IMPERATIVE 701| description of a process that computes the function 'square-root'. 702| One such method is Newton's method. 703| The method consists of succesive application of steps, each of which 704| improves a former approximation of the square root. The improvement is 705| based on the idea that if y is a guess for a square root of x, 706| then (y + (x/y)) / 2 is a better approximation. 707| The computation starts with an arbitrary guess (like 1). 708| For example: x=2, initial-guess=1 709| 1st step: guess=1 improved-guess= (1+ (2/1))/2 = 1.5 710| 2nd step: guess=1.5 improved-guess= (1.5 + (2/1.5) )/2 = 1.4167 711| ... 712| 713| Note the difference between this computational notion of a function as an 714| EFFECTIVE COMPUTATION (PROCEDURAL notion) to the mathematical notion of a 715| function that does not involve the PROCESS of computation (DECLARATIVE 716| notion). 717| 718| A close look into Newton's method shows that it consists of a repetitive 719| step as follows: 720| 1. Is the current guess close enough to the square-root? (good-enough?) 721| 2. If not--compute a new guess. (improve). 722| Let's call the step 'sqrt-iter'. Then the method consists of repeated 723| applications of sqrt-iter. 724| The following procedures implement Newton's method: 725| 726| (define (sqrt-iter guess x) 727| (if (good-enough? guess x) 728| guess 729| (sqrt-iter (improve guess x) 730| x))) 731| 732| (define (improve guess x) 733| (average guess (/ x guess))) 734| 735| (define (average x y) 736| (/ (+ x y) 2)) 737| 738| (define (good-enough? guess x) 739| (< (abs (- (square guess) x)) .001)) 740| 741| The computation is triggered by making an initial arbitrary guess: 742| 743| (define (sqrt x) 744| (sqrt-iter 1 x)) 745| 746| 747| Example of using "sqrt": 748| 749| Script started on Thu Feb 27 10:20:16 1992 750| 2>> scm 751| > (define (sqrt-iter guess x) 752| (if (good-enough? guess x) 753| guess 754| (sqrt-iter (improve guess x) 755| x))) 756| # 757| > (define (improve guess x) 758| (average guess (/ x guess))) 759| # 760| > (define (average x y) 761| (/ (+ x y) 2)) 762| # 763| > (define (good-enough? guess x) 764| (< (abs ( - (square guess) x)) .001)) 765| # 766| > (define (sqrt x) 767| (sqrt-iter 1 x)) 768| # 769| > (sqrt 6) 770| 771| ERROR: unbound variable: square 772| ; in expression: (... square guess) 773| ; in scope: 774| ; (guess x) 775| > (define (square x) (* x x)) 776| square 777| > (sqrt 6) 778| 2.44949437160697 779| > (sqrt (+ 100 44)) 780| 12.0000000124087 781| > (sqrt (+ (sqrt 2) (sqrt 9))) 782| 2.10102555114187 783| > (square (sqrt 4)) 784| 4.00000037168919 785| > (exit) 786| 3>> ^D 787| script done on Thu Feb 27 10:24:53 1992 788| 789| 790| 1.1.8 PROCEDURES AS BLACK BOX ABSTRACTIONS: 791| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 792| 793| The square roots example demonstrates how a problem can be de-composed 794| into a cluster of subproblems, carried out by independent procedures. 795| Each procedure name is used as an ABSTRACTION for a procedure. 796| For example: "square" can be a name for ANY procedure that computes the 797| square function. Here is another version of "square": 798| (define (square x) 799| (exp (double (log x)))) 800| 801| (define (double x) (+ x x)) 802| 803| 804| Formal parameters of procedures are LOCAL to the body of the procedure. 805| Changing the names of formal parameters (consistently throughout the body 806| of the procedure) does not change the MEANING of the procedure. 807| Definition: A symbol whose CONSISTENT RENAMING through out an expression 808| does not change the meaning of the expression, is a BOUND VARIABLE. The 809| expression BINDS the variable, and it is also its SCOPE. 810| The meaning of BINDING a variable within an expression is that whenever 811| the expression is applied, bindings for that variable are taken from the 812| environment of the expression application. 813| In procedure definition: The formal parameters are bound variables. 814| The procedure body is their scope: Each occurrence of a formal parameter 815| in the procedure's body is BOUND. 816| 817| Definition: A symbol that is not bound in an expression, is a FREE 818| VARIABLE. 819| In the definition of good-enough?, 'guess' and 'x' are bound variables, 820| while '<', 'abs', and 'square' are free. 821| 822| In sum: Expressions are INDEPENDENT of the names of their bound 823| variables, but NOT INDEPENDENT of the names of their free variables. 824| The notions of BINDING and SCOPE are extremely important since: 825| 1. The scope of a variable determines the environment where the binding 826| for the variable resides. 827| 2. They enable PACKAGING if software into unrelated/independent parts. 828| 829| In Pascal/C the variables declared within a procedure/function are bound 830| within the procedure/function. 831| In Pascal, every 'with' statement BINDS the names of the record's fields. 832| 833| INTERNAL DEFINITIONS AND BLOCK STRUCTURE: 834| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 835| Sub-procedures can be localized within other procedure definitions. 836| This can be used to LOCALIZE/HIDE/ENCAPSULATE auxiliary procedures. 837| For example, in different problems, there might be many 'improve' methods, 838| and we wish each such method to be local to its environment. 839| The names of the internally defined procedures are bound variables, whose 840| scope is the body of the procedure within which they are defined. 841| 842| For example: 843| Block-structured SQRT 844| 845| (define (sqrt x) 846| (define (good-enough? guess x) 847| (< (abs (- (square guess) x)) .001)) 848| (define (improve guess x) 849| (average guess (/ x guess))) 850| (define (sqrt-iter guess x) 851| (if (good-enough? guess x) 852| guess 853| (sqrt-iter (improve guess x) x))) 854| (sqrt-iter 1 x)) 855| 856| The nesting of procedure definition is a way of HIDING procedures within 857| their environment. This nesting yields a BLOCK STRUCTURE. 858| The nested procedure-definitions must precede other expressions 859| in the enclosing procedure's body. 860| 861| The evaluation of the last 'define' just binds the variable sqrt, in the 862| global environment. The internally defined procedures are, yet, undefined. 863| Each application of 'sqrt', triggers evaluation of all internal 'define' 864| forms, within a LOCAL ENVIRONMENT specialized to the current application, 865| followed by evaluation of the rest of the procedure body. The internal 866| definitions cannot be seen from outside the current application of sqrt. 867| When the application is completed, its environment, including the internal 868| definitions, is removed. 869| 870| Variables within a block structure are LEXICALLY SCOPED by their 871| enclosing procedure--the nearset procedure where they are local (bound). 872| In other words, they are bound to their procedures' bodies. 873| In the last 'sqrt' example: 874| Global environment: bindings for 'abs', 'sqrt', 'average'. 875| These names are bound in the global environment. 876| In sqrt: x, good-enough?, improve, sqrt-iter are bound variables. 877| their binding scope is the entire body of sqrt. 878| In good-enough?: guess, x are bound variables. 879| <, -, abs are free variables. 880| 881| BOUND VARIABLES IN NESTED DEFINITIONS: 882| If a variable is bound within an expression, all of its occurrences 883| are LOCAL to that expression. They are HIDDEN from other expressions. 884| Hence, in the substitutin model, the lexical scoping prevents substitution 885| of bound variables in nested definitions: 886| (define (f x) 887| (define (g x) 888| .... )) 889| The evaluation of (f 3) does not substitute the occurrences of x in the 890| the body of 'g', since x is bound in g. 891| 892| The binding scope of the formal parameter 'x' of sqrt is the entire 893| body of sqrt. 894| In particular, its scope includes the definitions of the internal 895| procedures. Hence, there is no point in passing 'x' as an actual argument 896| to the internal procedures. Any occurrence of 'x' in the internal 897| procedures is, anyhow, bound by the formal parameter 'x' of 'sqrt'. 898| Note that the simplification is not "name based" (not because the name 899| of the formal parameters in all internal definitions is 'x'), but value 900| based. The internal formal parameters can be removed one by one, based on 901| their substitutions. This can be made more clear is we use different 902| names for the formal parameters. But then-- it requires replacements in 903| the body of the internal procedures. 904| 905| Example: Block-structured SQRT using lexical scoping 906| 907| (define (sqrt x) 908| (define (good-enough? guess) 909| (< (abs (- (square guess) x)) .001)) 910| (define (improve guess) 911| (average guess (/ x guess))) 912| (define (sqrt-iter guess) 913| (if (good-enough? guess) 914| guess 915| (sqrt-iter (improve guess)))) 916| (sqrt-iter 1)) 917| 918| The SIMPLIFICATIONS we get from block-structuring are: 919| 1. Hiding internal definitions. 920| 2. Save formal parameters, where lexical scoping takes care of 921| substituting the right variables. 922| 3. Simplify names: In the last example, 'sqrt-iter' can be replaced by 923| 'iter'. 924| 925| This method of binding variables by their lexical context is called 926| LEXICAL SCOPING. It is used in Pascal, C, COMMON LISP. 927| Its dual method is called DYNAMIC SCOPING: The binding of variables is 928| determined, in run time, by the LATEST binding to the variable. 929| 930| Example: 931| (define (f) 932| (define a +) 933| (define (f1 x) (.....(a x 1)...)) 934| (define (f2 x) 935| (define a *) 936| (f1 x) ) 937| (f2 3) 938| ) 939| 940| In lexical scoping, the evaluation of (f) yields 4; in dynamic scoping 941| it is 3. 942| 943| ---------------------------------------------------------------------- 944| 945| Glossary: 946| ~~~~~~~~~ 947| environment; special forms; binding; combination; names; values; 'define'; 948| operator; operand; evaluation; abstraction; procedure; formal parameters; 949| actual arguments; parameter passing; call-by-value; call-by-name; 950| conditional expression; predicate; declarative; imperative; procedural; 951| local names; free variable; bound variable; scope; hiding/localizing/ 952| encapsulation; block structure; lexical scoping; dynamic scoping. 953| 954| 955| ADDITIONS: 956| More explanation about normal order. Expecially, about normal 957| order with special forms, where the substitution is stoped and directed 958| by the laws of the special form. 959|