http___fmi.wikidot.com_fp6_1.xml
http___www.300455.net_blog_61068151698141091845.html.xml
1.1 1.2 1.3 2.1 3.1 3.2 3.3 4.1 5.1 6.1 7.1 8.1 9.1 13.1 14.1 15.1 17.1 17.2 18.1 19.1 20.1 20.2 21.1 22.1 22.2 22.3 22.4 23.1 24.1 24.2 24.3 25.1 26.1 28.1 29.1 30.1 30.2 30.3 30.4 31.1 31.2 31.3 32.1 32.2 33.1 33.2 34.1 34.2 34.3 35.1 35.2 36.1 37.1 39.1 40.1 42.1 42.2 42.3 42.4 43.1 43.2 44.1 45.1 46.1 47.1 47.2 48.1 48.2 48.3 48.4 49.1 50.1 50.2 52.1 53.1 54.1 58.1 59.1 61.1 61.2 62.1 63.1 64.1 65.1 65.2 66.1 66.2 66.3 67.1 67.2 67.3 68.1 68.2 68.3 69.1 70.1 70.2 70.3 71.1 71.2 71.3 72.1 72.2 72.3 72.4 72.5 72.6 72.7 73.1 73.2 73.3 74.1 75.1 75.2 76.1 77.1 78.1 79.1 83.1 83.2 84.1 85.1 86.1 87.1 88.1 88.2 89.1 90.1 91.1 93.1 94.1 95.1 98.1 100.1 100.2 100.3 101.1 102.1 103.1 105.1 107.1 108.1 109.1 110.1 114.1 116.1 116.2 117.1 118.1 118.2 118.3 118.4 119.1 120.1 122.1 123.1 125.1 126.1 128.1 129.1 132.1 133.1 134.1 135.1 136.1 137.1 137.2 137.3 137.4 137.5 137.6 138.1
Тази лекция е малко по-дълга от повечето. Хайде, предишните бяха за по пет минути. Ще издържиш и една по-голяма, Вярвам в теб! Преговор В трета лекция ставаше дума за генератори на функции. Там имаше хубави идеи, но темата все още не е изчерпана. Да погледнем кода от миналия път: (define (aggregate oper term n step min_n null_value) (if (<= n min_n) null_value (oper (term n) (aggregate oper term (- n step) step min_n null_value) Процедурата aggregate се извиква по веднъж за всяко от числата от n до min_n, като на всяко от тях съпоставя term, зависещо от n, и накрая извършва операцията oper върху всички получени стойности. Например, ако ни трябва сумата на числата от 1 до 10, кодът ще изглежда така: (aggregate + (lambda (x) x) 10 1 0 0) Ако нещо дотук не е ясно, най-добре иди и виж предишните лекции, защото това ще ни трябва. Спокойно, аз ще те изчакам. Така, да започваме Генератори на списъци Горният код работи. Освен това, ако смея сам да кажа, е елегантно написан и дава сравнително голяма свобода на програмиста. Какъв, тогава, е фундаменталният му проблем? Горният код приема числа и връща числа. Не че с числа може да се правят малко неща, де. Но все пак, за да може да се очаква от програмата да прави нещо различно от прости математически операции, трябва да я направим по-качествена. Само тогава светът отново ще стане ярък и красив. Връщане на списък По-наблюдаделните читатели1 ще обединят знанията от предишните няколко лекции и ще се сетят, че term и oper могат да бъдат процедурите car и cons. Тоест, вместо да събираме, умножаваме или каквото там правехме резултатите до момента - можем да си ги направим на списъче. Ето как: (define (map n step min_n) (aggregate cons (lambda x (car x)) n step min_n '()) По този начин се получава списък, в който на всяко число от n до min_n през стъпка step се съпоставя (term n). Функционални инструменти за програмиране Процедурата неслучайно се казва map. В почти всички езици има такава. Съпоставянето между нещо и нещо друго е много базова част в програмирането въобще. Май е на второ място само след сортирането. - Например - даден ти е списък от записи. Всеки запис характеризира един човек и има по осемдесет и три полета - име, рожден ден, роден език, държава, адрес на лична страница, снимка, девиз… Това е много. На теб ти трябва списък от имена, девизи и снимки. - Например - даден ти е масив от имена на хора и рождени дати. От него искаш да вземеш само тези хора, които имат рожден ден в близките три дни и да ги върнеш като списък. - Например - имаш списък с чат съобщения между теб и някой твой приятел през последните две години. Искаш да видиш колко хиляди символа сте изписали за това време. Тези функции обикновено се наричат съответно map, filter и reduce2. В по-новите езици се наричат инструменти на функционалното програмиране. В Лисп се наричат инструменти, защото Лисп е толкова стар, че за него Бийтълс не са Ретро3. Когато става дума за подобни функции, друг често използван термин е list comprehension. Тоест, обработка на списъци4. Пример, на Python: [item*2 for item in [1,2,3,4]] И на Ruby: [1, 2, 3, 4].map { |item| item*2 } Чу ли това, Lisp? Какво правят другите езици? Нима ще ги оставиш да им се размине? Нито пък аз. Време е да си напишем качествена map процедура. Тя ще приема списък и процедура, ще съпоставя на всеки от елементите му резултата от процедурата извикана с този елемент и ще връща списък от тези резултати. Приемане на списък Този път вече няма да ни се размине - ще трябва да модифицираме вече написания код. Как може да се направи така, че да работи програмата със списък, вместо с интервала $[min_n, n]$? Това наистина е интересен въпрос и ако държиш да се развиваш самостоятелно в ученията си, бих ти препоръчал в този момент да спреш да четеш и да се върнеш когато в главата ти се е оформила идеята. Иначе, на следващия ред просто ще го кажа, няма проблем. В момента прехода от един елемент към следващия се изчислява по възможно най-елементарния начин - от текущия елемент се изважда стъпката. Това, което искаме, е на текущия елемент да му се взема cdr-то. Тоест, да се взема следващия елемент в списъка, с който работим. Ще предефинираме стъпката, значи: (define (map lst term) (if (null? lst) (cons (term (car lst)) (map (cdr lst) term) Това принципно работи и може да се извика с: (map (list 1 2 3 4) (lambda (x) (* x 2))) Забележи, че се казва lambda (x). Това означава, че ламбдата приема точно един аргумент. Обърни внимание, че това няма да работи за: (map (list 1 2 3 4) (lambda x (* x 2))) > *: expects type   as 1st argument, given: (1); other arguments were: 2 Ако беше казано lambda x, Scheme щеше да реши не че се подава един аргумент, а един списък с всичките аргументи на функцията. Такава функция може да се извика с произволен брой аргументи (оставям на теб да решиш дали това е хубаво или лошо нещо). Така де, map все още не е достатъчно добре написано. След малко ще си напишем filter и reduce функции - ако и те са като тази, всичко ще го има написано по три пъти. Ако някъде, някога, нещо трябва да се промени, ще трябва да се променя три пъти. Какво ще стане, когато това се наложи? Ще забравиш. Или въобще няма да го променяш ти и горкото същество, на което се пада честта, ще изгуби часове, може би дни, в дебъгване на глупав проблем, когато се окаже, че подобни функции не се държат…подобно. Точно затова трябва да се спазва DRY принципът - "Don't Repeat Yourself". Да не говорим, че като го спазваш, реално се напъваш по-малко. Йей, програмиране! Още веднъж, този път с чувство Сега заедно ще напишем map, filter и reduce процедурите, използвайки една базова процедура, към която трите ще се обръщат. Впрочем, ако очакваш домашно в тази лекция - няма да има. Ако вече се чувстваш като джедай, първо напиши тези три функции и после ела да ги сравниш с моите. Преди няколко лекции си направихме добре изглеждаща и обмислена aggregate процедура. Съвсем малко работа е нужна там, за да я накараме да работи за списъци. Ще я вземем назаем като прототип за процедура accumulate. Забележка: Не си мисли, че този стил на работа говори за мързел. На мен в началото така ми се струваше. Това е правилният начин. Ако нещо те съмнява - пробвай се да напишеш всичко без да ползваш готов код, започвайки от нулата. Виж колко време ще ти отнеме. И виж дали няма да има бъгове. След това сравни с този метод :) Първо, махаме n и min_n полетата. На тяхно място има един списък - lst. Не го кръщаваме list, защото вече има такава процедура. null_value си остава, защото май ще му намеря приложение. (define (accumulate term oper null_value lst) (if (null? lst) null_value (oper (term (car lst)) (accumulate term oper null_value (cdr lst)) Оттук вече Reduce се пише лесно. Това е функция, приемаща следните аргументи: - Списък - начина, по който от цял списък правим едно нещо - началната стойност. Тя връща едно нещо, което е резултатът от операцията върху всички елементи на списъка. Ще си дефинирам една процедурка identity, която ще връща единствения си аргумент непроменен. За по-лесно тестване. (define (identity x) x) (define (reduce oper base lst) (accumulate identity oper base lst) ;Удвоеният сбор на числата в (1 2 3 4): (reduce + 0 (map (lambda (x) (* x 2)) (list 1 2 3 4)) (reduce identity * 1 (list 1 2 3 4)) Няма да е зле да се погрижим за някакви стойности по подразбиране на term, oper, и base, но за момента това не ни е приоритет. Освен това, когато ни стане приоритет, ще трябва да го сменяме само на едно място. Кой е шефа, а? Сега вече можем да си викаме map само по списък и операция за всеки елемент: (define (map term lst) (accumulate term cons '() lst) (map (lambda (x) (+ (* x 2) 4)) (list 1 2 3 4)) А как се прави филтър? (define (filter pred lst) (accumulate identity (lambda (x y) (if (pred x) (cons x y) y)) (filter (lambda (x) (not (= x 3))) (list 1 2 3 4)) Също толкова лесно. Само ни трябва някакъв предикат, който да казва кое влиза в новия списък и кое - не. Функции от по-висок ред със списъци Може, ако ни мързи, да си направим процедури, които връщат процедура със съответната операция върху списъци. Те ще приемат всички нужни аргументи, освен списък. Списъкът ще се подава на получената процедура. Така, ако по някаква причина три пъти подред ни трябва да вземем квадратите на числа в списък, няма да е трудно: (define (reduce_proc oper base) (lambda (lst) (reduce oper base lst)) (define (map_proc term) (lambda (lst) (map term lst)) (define (filter_proc pred) (lambda (lst) (filter pred lst)) (let ((map_square (map_proc (lambda (x) (* x x))))) (map_square (map_square (map_square (list 1 2 3 4)))) Задача Промених си мнението, все пак ще има и нещо за упражнение. Естествено, това включва написването на map, filter, reduce процедурите, ако още не ти се е получило да се накараш да ги напишеш. Преправи процедурата accumulate така, че да може да се използва както от днешните три процедури, така и от предишната aggregate, която не работеше със списък, а с n, min_n и step. За да стане това ще трябва да: Напиши си и процедури all? и any?. И двете получават като аргументи предикат и списък. Първата връща #t когато предикатът е изпълнен за всеки елемент на списъка, втората - когато е изпълнен поне за един елемент. Иначе връщат #f. Не е нужно да правят каквото и да е ако списъкът е празен. Ето сорс за това, което беше изписано днес.
1.1 2.1 3.1 4.1 4.2 4.3 5.1 5.2 5.3 5.4 5.5 5.6 6.1 6.2 6.3 6.4 6.5 7.1 7.2 8.1 8.2 8.3 8.4 8.5 9.1 9.2 10.1 10.2 11.1 12.1 13.1 13.2 14.1 15.1 15.2 15.3 15.4 16.1 16.2 17.1 17.2 17.3 17.4 18.1 18.2 18.3 19.1 20.1 21.1 21.2 21.3 21.4 21.5 21.6 21.7 21.8 21.9 21.10 21.11 21.12 22.1 23.1 24.1 24.2 24.3 24.4 24.5 24.6 24.7 24.8 24.9 24.10 24.11 24.12 24.13 24.14 25.1 25.2 25.3 25.4 25.5 25.6 25.7 26.1 27.1 27.2 27.3 27.4 28.1 28.2 28.3 29.1 30.1 31.1 32.1 32.2 32.3 33.1 33.2 34.1 34.2 35.1 36.1 37.1 38.1 39.1 40.1 41.1 41.2 42.1 42.2 43.1 43.2 43.3 44.1 44.2 44.3 44.4 45.1 45.2 46.1 47.1 47.2 47.3 47.4 47.5 47.6 47.7 47.8 47.9 48.1 48.2 49.1 49.2 50.1 51.1 51.2 52.1 52.2 52.3 52.4 53.1 53.2 53.3 54.1 54.2 54.3 54.4 54.5 54.6 54.7 54.8 55.1 55.2 55.3 55.4 55.5 55.6 55.7 55.8 55.9 55.10 55.11 55.12 55.13 55.14 55.15 55.16 55.17 55.18 55.19 55.20 55.21 55.22 55.23 55.24 56.1 58.1
Scheme TutorialIntroductionStructureSyntaxTypesSimpleCompositeType PredictesNumbers, Arithmetic Operators, and FunctionsArithmetic Operators 正文 Scheme Tutorial IntroductionStructureSyntaxTypesSimpleCompositeType PredictesNumbers, Arithmetic Operators, and FunctionsArithmetic OperatorsListsBoolean ExpressionsLogical OperatorsRelational OperatorsConditional ExpressionsFunctionsLambda ExpressionsInput and Output ExpressionsHigher-Order FunctionsAn Example ProgramAppendixReferences Introduction Scheme is an imperative language with a functional core. The functional core is based on the lambda calculus. In this chapter only the functional core and some simple I/O is presented. In functional programming, parameters play the same role that assignments do in imperative programming. Scheme is an applicative programming language. By applicative, we mean that a Scheme function is applied to its arguments and returns the answer. Scheme is a descendent of LISP. It shares most of its syntax with LISP but it provides lexical rather than dynamic scope rules. LISP and Scheme have found their main application in the field of artificial intelligence. The purely functional part of Scheme has the semantics we expect of mathematical expressions. One word of caution: Scheme evaluates the arguments of functions prior to entering the body of the function (eager evaluation). This causes no difficulty when the arguments are numeric values. However, non-numeric arguments must be preceded with a single quote to prevent evaluation of the arguments. The examples in the following sections should clarify this issue. Scheme is a weakly typed language with dynamic type checking and lexical scope rules. The Structure of Scheme Programs A Scheme program consists of a set of function definitions. There is no structure imposed on the program and there is no main function. Function definition may be nested. A Scheme program is executed by submitting an expression for evaluation. Functions and expressions are written in the form(function_name arguments) This syntax differs from the usual mathematical syntax in that the function name is moved inside the parentheses and the arguments are separated by spaces rather than commas. For example, the mathematical expression 3 + 4 * 5 is written in Scheme as(+ 3 (* 4 5)) Syntax The programming language Scheme is syntactically close to the lambda calculus. Scheme Syntax E in Expressions I in Identifiers (variables) K in Constants E ::= K | I | (E_0 E^*) | (lambda (I^*) E2) | (define I E') The star `*' following a syntactic category indicates zero or more repetitions of elements of that category thus Scheme permits lambda abstractions of more than one parameter. Scheme departs from standard mathematical notation for functions in that functions are written in the form (Function-name Arguments...) and thearguments are separated by spaces and not commas. For example,(+ 3 5) (fac 6) (append '(a b c) '(1 2 3 4)) The first expression is the sum of 3 and 5, the second presupposes the existence of a functionfacto which the argument of 6 is presented and the third presupposes the existence of the function append to which two lists are presented. Note that the quote is required to prevent the (eager) evaluation of the lists. Note uniform use of the standard prefix notation for functions. Types Among the constants (atoms) provided in Scheme are numbers, the boolean constants #T and #F, the empty list (), and strings. Here are some examples of atoms and a string:A, abcd, THISISANATOM, AB12, 123, 9Ai3n, "A string" Atoms are used for variable names and names of functions. A list is an ordered set of elements consisting of atoms or other lists. Lists are enclosed by parenthesis in Scheme as in LISP. Here are some examples of lists.(A B C) (138 abcde 54 18) (SOMETIMES (PARENTHESIS (GET MORE)) COMPLICATED) () Lists are can be represented in functional notation. There is the empty list represented by () and the listconstruction functionconswhich constructs lists from elements and lists as follows: a list of one element is (cons X ()) and a list of two elements is (cons X (cons Y ())). Simple Types The simple types provided in Scheme are summarized in this table.TYPE & VALUES boolean & #T, #F number & integers and floating point symbol & character sequences pair & lists and dotted pairs procedure & functions and procedures Composite Types The composite types provided in Scheme are summarized in this table.TYPE & REPRESENTATION & VALUES list & (space separated sequence of items) & any in function& defined in a later section & in Type Predicates A predicate is a boolean function which is used to determine membership. Since Scheme is weakly typed, Scheme provides a wide variety of type checking predicates. Here are some of them.PREDICATE & CHECKS IF (boolean? arg ) & arg is a boolean in (number? arg ) & arg is a number in (pair? arg ) & arg is a pair in (symbol? arg ) & arg is a symbol in (procedure? arg ) & arg is a function in (null? arg ) & arg is empty list in (zero? arg ) & arg is zero in (odd? arg ) & arg is odd in (even? arg ) & arg is even in Numbers, Arithmetic Operations, and Functions Scheme provides the data type,number, which includes the integer, rational, real, and complex numbers. Some Examples:(+ 4 5 2 7 5 2) - is equivalent to \( 4 + 5 + 2 + 7 + 5 + 2 \) (/ 36 6 2) - is equivalent to \(\frac{\frac{36}{6}}{2} \) (+ (* 2 2 2 2 2) (* 5 5)) - is equivalent to \( 2^{5} + 5^{2} \) Arithmetic Operators SYMBOL & OPERATION + & addition in - & subtraction in * & multiplication in / & real division in quotient & integer division in modulo & modulus in Lists Lists are the basic structured data type in Scheme. Note that in the following examples the parameters are quoted. The quote prevents Scheme from evaluating the arguments. Here are examples of some of the built in list handling functions in Scheme.constakes two arguments and returns a pair (list). (cons '1 '2) is (1 . 2) (cons '1 '(2 3 4)) is (1 2 3 4) (cons '(1 2 3) '(4 5 6)) is ((1 2 3) 4 5 6) The first example is a dotted pair and the others are lists. \marginpar{expand} Either lists or dotted pairs can be used to implement records.carreturns the first member of a list or dotted pair. (car '(123 245 564 898)) is 123 (car '(first second third)) is first (car '(this (is no) more difficult)) is this cdrreturns the list without its first item, or the second member of a dotted pair. (cdr '(7 6 5)) is (6 5) (cdr '(it rains every day)) is (rains every day) (cdr (cdr '(a b c d e f))) is (c d e f) (car (cdr '(a b c d e f))) is b null?returns \#t if the {\bf obj}ect is the null list, (). It returns the null list, (), if the object is anything else.listreturns a list constructed from its arguments. (list 'a) is (a) (list 'a 'b 'c 'd 'e 'f) is (a b c d e f) (list '(a b c)) is ((a b c)) (list '(a b c) '(d e f) '(g h i)) is ((a b c)(d e f)(g h i)) lengthreturns the length of a list. (length '(1 3 5 9 11)) is 5 reversereturns the list reversed. (reverse '(1 3 5 9 11)) is (11 9 5 3 1) appendreturns the concatenation of two lists. (append '(1 3 5) '(9 11)) is (1 3 5 9 11) Boolean Expressions The standard boolean objects for true and false are written \verb+#t+ and \verb+#f+. However, Scheme treats any value other than \verb+#f+ and the empty list \verb+()+ as true and both \verb+#f+ and \verb+()+ as false. Scheme provides {\bf not, and, or} and several tests for equality among objects. Logical Operators SYMBOL & OPERATION not & negation and & logical conjunction or & logical disjunction Relational Operators SYMBOL & OPERATION = & equal (numbers) (  ) & greater than (>= ) & greater or equal eq? & args are identical eqv? & args are operationally equivalent equal? & args have same structure and contents Conditional Expressions Conditional expressions are of the form:(if test-exp then-exp) (if test-exp then-exp else-exp). Thetest-expis a boolean expression while thethen-expandelse-expare expressions. If the value of thetest-expis true then thethen-expis returned else theelse-expis returned. Some examples include:(if (> n 0) (= n 10)) (if (null? list) list (cdr list)) Thelistis the then-exp while(cdr list )is the else-exp. Scheme has an alternative conditional expression which is much like a case statement in that several test-result pairs may be listed. It takes one of two forms:(cond (test-exp1 exp ...) (test-exp2 exp ...) ...) (cond (test-exp exp ...) ... (else exp ...)) The following conditional expressions are equivalent.(cond ((= n 10) (= m 1)) ((> n 10) (= m 2) (= n (* n m))) ((  n 10) (= m 2) (= n (* n m))) (else (= n 0))) Functions Definition expressions bind names and values and are of the form:(define id exp) Here is an example of a definition.(define pi 3.14) This definespito have the value 3.14. This is not an assignment statement since it cannot be used to rebind a name to a new value. Lambda Expressions User defined functions are defined using lambda expressions. Lambda expressions are unnamed functions of the form:(lambda (id...) exp ) The expression(id...)is the list of formal parameters andexprepresents the body of the lambda expression. Here are two examples the application of lambda expressions.((lambda (x) (* x x)) 3) is 9 ((lambda (x y) (+ x y)) 3 4) is 7 Here is a definition of a squaring function.(define square (lambda (x) (* x x))) Here is an example of an application of the function.1 ]=> (square 3) ;Value: 9 Here are function definitions for the factorial function, gcd function, Fibonacci function and Ackerman's function.(define fac (lambda (n) (if (= n 0) 1 (* n (fac (- n 1)))))) % %(define fib (lambda (n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))) % %(define ack (lambda (m n) (if (= m 0) (+ n 1) (if (= n 0) (ack (- m 1) 1) (ack (- m 1) (ack m (- n 1))))))) % %(define gcd (lambda (a b) (if (= a b) a (if (> a b) (gcd (- a b) b) (gcd a (- b a)))))) Here are definitions of the list processing functions, sum, product, length and reverse.(define sum (lambda (l) (if (null? l) 0 (+ (car l) (sum (cdr l)))))) % %(define product (lambda (l) (if (null? l) 1 (* (car l) (sum (cdr l)))))) % %(define length (lambda (l) (if (null? l) 0 (+ 1 (length (cdr l)))))) (define reverse (lambda (l) (if (null? l) nil (append (reverse (cdr l)) (list (car l)))))) Nested Definitions Scheme provides for local definitions by permitting definitions to be nested. Local definitions are introduced using the functionslet,let*andletrec. The syntax for thedefinefunction is expanded to permit local definitions. The syntax of thedefinefunction and theletfunctions isScheme Syntax E in Expressions I in Identifier(variable) ... B in Bindings ... E... ) | (let B_0 E_0) | (let* B1E1) | (letrec B2E2) |... Note that there may be a sequence of bindings. For purposes of efficiency the bindings are interpreted differently in each of the ``let'' functions. Theletvalues are computed and bindings are done in parallel, this means that the definitions are independent. Thelet*values and bindings are computed sequentially, this means that later definitions may be dependant on the earlier ones. Theletrecbindings are in effect while values are being computed to permit mutually recursive definitions. As an illustration of local definitions here is a definition of insertion sort definition with the insert function defined locally. Note that the body ofisortcontains two expressions, the first is aletrecexpression and the second is the expression whose value is to be returned.(define isort (lambda (l) (letrec ((insert (lambda (x l) (if (null? l) (list x) (if (<= x (car l)) (cons x l) (cons (car l) (insert x (cdr l)))))))) (if (null? l) nil (insert (car l) (isort (cdr l))))))) {letrecis used sinceinsertis recursively defined. Here are some additional examples:; this binds x to 5 and yields 10 (let ((x 5)) (* x 2)) ; this bind x to 10, z to 5 and yields 50. Lets may be nested. For example,the expression(let ((a 3) (b 4) (let ((double (* 2 a)) (triple (* 3 b))) (+ double triple)))) Input and Output Expressions Scheme does not readily support the functional style of interactive programming since input is not passed as a parameter but obtained by successive evaluations of the builtin functionread. For example,(+ 3 (read)) returns the sum of 3 and the next item from the input. A succeeding call to{\tt read}will return the next item from the standard input, thus,{\tt read}is not a true function. The function{\bf display}prints its argument to the standard output. For example,(display (+ 3 (read))) displays the result of the previous function. The following is an example of an interactive program. It displays a prompt and returns the next value from the standard input.(define prompt-read (lambda (Prompt) (display Prompt) (read))) Higher Order Functions A higher order function (or functional) is a function that either expects a function as a parameter or returns a function as a result. In Scheme functions may be passed as parameters and returned as results. Scheme does not have an extensive repertoire of higher order functions but {\tt apply} and {\tt map} are two builtin higher order functions. The functionapplyreturns the result of applying its first argument to its second argument. 1 ]=> (apply + '(7 5)) ;Value: 12 1 ]=> (apply max '(3 7 2 9)) ;Value: 9 The functionmapreturns a list which is the result of applying its first argument to each element of its second argument. 1 ]=> (map odd? '(2 3 4 5 6)) ;Value: (() #T () #T ()) Here is an example of a ``curried'' function passed as a parameter.dblis a dubbling function. 1 ]=> (define dbl (lambda (x) (* 2 x))) ;Value: dbl 1 ]=> (map dbl '(1 2 3 4)) ;Value: (2 4 6 8) 1 ]=> The previous example could also be written as: 1 ]=> (map (* 2) '(1 2 3 4)) ;Value: (2 4 6 8) 1 ]=> An Example Program The purpose of the following function is to help balance a checkbook. The function prompts the user for an initial balance. Then it enters the loop in which it requests a number from the user, subtracts it from the current balance, and keeps track of the new balance. Deposits are entered by inputting a negative number. Entering zero (0) causes the procedure to terminate and print the final balance.(define checkbook (lambda () ; This check book balancing program was written to illustrate ; i/o in Scheme. It uses the purely functional part of Scheme. ; These definitions are local to checkbook (letrec ; These strings are used as prompts ((IB "Enter initial balance: ") (AT "Enter transaction (- for withdrawal): ") (FB "Your final balance is: ") ; This function displays a prompt then returns ; a value read. (prompt-read (lambda (Prompt) (display Prompt) (read))) ; This function recursively computes the new ; balance given an initial balance init and ; a new value t. Termination occurs when the ; new value is 0. (newbal (lambda (Init t) (if (= t 0) (list FB Init) (transaction (+ Init t))))) ; This function prompts for and reads the next ; transaction and passes the information to newbal (transaction (lambda (Init) (newbal Init (prompt-read AT))))) ; This is the body of checkbook; it prompts for the ; starting balance (transaction (prompt-read IB))))) Appendix DERIVED EXPRESSIONS(cond (test1 exp1) (test2 exp2) ...)a generalization of the conditional expression.ARITHMETIC EXPRESSIONS(exp x)which returns the value of \(e^{x}\)(log x)which returns the value of the natural logarithm of {\bf x}(sin x)which returns the value of the sine of {\bf x}(cos x)(tan x)(asin x)which returns the value of the arcsine of {\bf x}(acos x)(atan x)(sqrt x)which returns the principle square root of x(max x1x2...)which returns the largest number from the list of given {\bf num}bers(min x1x2...)(quotient x1x2)which returns the quotient of \(\frac {x1}{x2}\)(remainder x1x2)which returns the integer remainder of \(\frac {x1}{x2}\)(modulo x1x2)returns x1modulo x2(gcd num1 num2 ...)which returns the greatest common divider from the list of given {\bf num}bers(lcm num1 num2 ...)which returns the least common multiple from the list of given {\bf num}bers(expt base power)which returns the value of {\bf base} raised to {\bf power}{\bf note: For all the trigonometric functions above, the x value should be in radians}LIST EXPRESSIONS(list obj)returns a list given any number of {\bf obj}ects.(make-list n)returns a list of length {\bf n} and every atom is an empty list ().HIGHER ORDER FUNCTIONS(apply procedure obj ... list)returns the result of applying {\it procedure} to {\it object} and returns the elements of {\it list}. It passes the first obj as the first parameter to procedure, the second obj as the second and so on. List is the remag arguments into a list to procedure. This is useful when some or all of the arguments are in a list.(map procedure list)returns a list which is the result of applying procedure to each element of {\bf list}. I/O(read)returns the next item from the standard input file.(write obj)prints {\bf obj} to the screen.(display obj)prints {\bf obj} to the screen. Display is mainly for printing messages that do not have to show the type of object that is being printed. Thus, it is better for standard output.(newline)sends a newline character to the screen.(transcript-on filename)opens the file filename and takes all input and pipes the output to this file. An error is displayed if the file cannot be opened.(transcript-off)ends transcription and closes the file. References Abelson, Harold. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, Mass. Dybvig, R. Kent.The Scheme Programming Language. Prentice Hall, Inc. Englewood Cliffs, New Jersey, 1987. Springer, G. and Friedman, D.,Scheme and the Art of Programming. The MIT Press, 1989. Aaby Send comments to:webmaster@cs.wwc.edu