Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 9
Текст из файла (страница 9)
Определенная выше процедура sum порождает линейный рекурсивныйпроцесс. Переопределите процедуру sum так, чтобы процесс,порожденный процедурой, был итеративным. Для этого заполните <??>в следующем определении.(define (sum term a next b)(define (iter a result) (if<??> <??>(iter <??> <??>)))(iter <??> <??>))lambda выраженияОпределенным неудобством при использовании процедур высшихпорядков является необходимость давать имена процедурам,используемым как фактические параметры, например, pi-next, приопределении процедуры pi-sum. Более удобно было бы иметьвозможность определять безымянную «процедуру, которая возвращаетзначение аргумента, увеличенное на 4» .
Это можно сделать, используяспециальную форму, называемую lambda выражением:(lambda (х)(+ х 4) )Таким образом, определение pi-sum можно записать без использованиялишних имен:(define (pi-sum a b)(sum (lambda (х) (/ 1.0 (* х (+ х 2) ) ) ) а(lambda (х) (+ 4 х) )Ы)В общем случае, синтаксис lambda выражения следующий:(lambda <formals> <body>)где < formals > представляет собой список имен формальных параметров, а<body> является последовательностью из одного или более выражений.Значением lambda выражения является процедура, с которой не связаноникакое имя.
По существу, определение процедуры (define (plus4 х)(+ х 4 ) ) эквивалентно определению (define plus4 (lambda (x) (+ 4х ) ) ).49Как любое выражение, значением которого является процедура, lambdaвыражение может быть использовано в качестве оператора.(lambda (х) (+ х х))((lambda (х у z) (+ х у (square z) ) ) 1 2 3)-> процедура-> 12Формальные параметры lambda выражения могут быть описаны одним изследующих способов:• (variable1 ...
variablen) - процедура имеет фиксированноеколичество аргументов. При вызове процедуры происходит заменаформальных параметров фактическими аргументами;• variable - процедура может иметь произвольное количествоаргументов. При вызове процедуры последовательность аргументовпреобразуется в список;• (variable1 . . . variablen-1 . variablen) - процедура должна иметьхотя бы п-1 аргументов.
При вызове процедуры происходит замена п-1формальных параметров фактическими аргументами, остальныеаргументы преобразуются в список.((lambda х х) 3 4 5 6)((lambda (х у . z) z) 3 4 5 6)-> (3 4 5 6)-> (5 6)Создание локальных переменныхДля создания локальных переменных в процедуре можно использоватьlambda выражения. Рассмотрим пример вычисления функцииf(x, y)=x(l+ ху) 2 + у(1-у) + (1+ху) (1 -у)Ее можно записать кака = 1 + ху b = 1-уf(x,y)=-xa 2 + yb + abПри определении процедуры, вычисляющей f потребуются не толькопеременные х и у, но также переменные для хранения промежуточныхзначений а, b. Можно определить вспомогательную процедуру f-helper илокализовать эти переменные:(define (f х у)(define (f-helper a b)(+ (* х (square a)) (* у b) (* a b) } )(f-helper (+ 1 {* x у)}(- 1 у) )Можно использовать lambda выражение для определения анонимнойпроцедуры с такой же возможностью локализации переменных.
В этомслучае тело процедуры f представляет собой просто вызов процедуры:(d efin e ( f x у)((lambda (а b) ( + (* x (square a))(* у b) (* а b)) ) ( + 1 (* х у ) )(- 1 у ) ) )Существует специальная форма, называемая let, для определениялокальных переменных. С помощью let процедуру f можно записать так:(define (f x у)(let ( ( a ( + 1 (* х у ) ) ) (b(- 1 у ) ) ) (+ (* х(square a) ) (* у b) (*а b) ) ) )Общий синтаксис let выражения:(let <bindings> <body>)где <bindings> имеет вид( (<var1> <exp1>)(<var2> <exp2>)...(<varn> <expn>) )Семантика let выражения следующая, переменная <var1> связывается созначением выражения <exp1>, переменная <var 2 > - со значениемвыражения <ехр2>, ...
и переменная <varn> - со значение выражения<ехр п >. Первая часть let выражения является списком пар (имя значение). Тело let выражения вычисляется в контексте имен, имеющихобласть видимости, ограниченной let выражением. По существу, letвыражение является альтернативной записью конструкции((lambda (<var 1 >...<var n >) <body>) <exp1>...<ехр n >)Для спецификации локальных переменных интерпретатору не требуетсяникаких новых механизмов вычисления. Из альтернативной записи letвыражения следует, что областью видимости переменных, определенных вlet выражении является тело let. Поэтому:• let выражение позволяет локализовать переменные там, где онииспользуются. Например, если значением х является 5, то значениемвыражения (+ (let ((х 3)) (+ х (* х 10))) х) будет 38.
Значениех в теле let равно з, значение let выражения равно 33. Однако вне letвыражения х имеет значение 5,51• значения аргументов вычисляются вне let выражений. Это имеетзначение, если выражение, которое определяет значение локальныхпеременных, зависит от переменных с теми же именами, что илокальные.
Например, пусть х имеет значение 2, тогда (let ((х 3) (у(+ х 2 ) ) ) (* х у)) будет иметь значение 12, так как внутри тела letвыражения х будет иметь значение 3, а у - значение 4 (котороеполучается как внешнее значение х, увеличенное на 2).Заметим, что при вычислении lambda выражений глобальные переменныевычисляются в месте определения, а не в месте вызова процедуры.
Такоймеханизм вычисления называется статическим связыванием. Например:(let((n 1))(let ((f ((lambda z) (+ z n)))(let ( ( n 2 ) ) (f 3 ) ) ) )При вычислении выражения сначала выполняется локальное связываниеn с 1, затем вычисляется lambda выражение, связывая f со значением типапроцедура (z + 1), после этого переопределяется n и затем вызывается f сфактическим параметром з. Так как f связано с определением процедуры(+ z 1), то получаем значение 4.Упражнения18. Пусть имеется определение процедуры (define (f g) (g 2 ) ) . Тогда:(f s qu a re)(f (lambda (z) (* z (+ z 1) ) ) )->->46Что произойдет при вычислении (f f). Объясните.Процедуры как возвращаемые значенияВ языке Scheme можно определить процедуру (высшего порядка), котораявозвращает результат типа процедура.
Рассмотрим определение:(define(incn n)((lambda x)(+ x n)))где incn является процедурой, которой в качестве аргумента передаетсяцелое число п. Результат применения этой процедуры являетсяпроцедурой, которая увеличивает на n передаваемый ей аргумент.Например, (incn 3) есть процедура, которая выдает в качестве результатазначение аргумента, увеличенное на з. Таким образом,( (incn 3 ) 2 )->5Можно переопределить процедуру incl-list как(define (incl-list x)(map x (incn 1))Рассмотрим пример процедуры высшего порядка, аргументы которойявляются процедурами, и результатом которой также является процедура.Определим процедуру compose. Она принимает в качестве аргументов двепроцедуры и выдает в качестве результата процедуру, которая применяетпоследовательно обе исходные процедуры.(define (compose f g)((lambda x)(f (g x))))Таким образом, она применяет f к результату g.
Преимущество процедурвысшего порядка состоит в том, что они позволяют разрабатыватьпрограммы в терминах более высоких абстракций, чем элементарныеконструкции языка. С помощью процедур высшего порядка с такимиабстракциями можно работать, так же как и с элементарнымиконструкциями языка.В языках программирования существуют ограничения на некоторыедействия с элементами языка. Элементами «первого класса» называютсяконструкции языка, которые могут:••••иметь имя;быть переданы в качестве аргументов процедуры,быть возвращены в качестве значения процедуры;из которых можно строить структуры данных.В Scheme процедуры являются объектами первого класса, что существенноувеличивает выразительную силу языка. А возможность создавать новыепроцедуры во время выполнения других процедур, обеспечиваетвозможность программирования, управляемого данными.ПрисваиваниеДо настоящего момента, все рассматриваемые процедуры можно былосчитать спецификациями, описывающими требуемый вычислительныйпроцесс.
При вызове процедуры происходило вычисление значениявыражения для заданных аргументов. При обращении к процедуре содними и теми же аргументами мы всегда получали один и тот жерезультат.53Однако разработку программ можно вести в терминах объектов и ихсостояний, которые изменяются во времени. Состояние объекта можетбыть описано набором переменных состояния, которые определяютповедение объекта в данный момент времени. Значение переменныхсостояния изменяется во время вычисления. Для описания изменениязначений переменных в языках программирования используется операторприсваивания.При использовании оператора присваивания процесс примененияпроцедур к аргументам не может быть описан с помощью моделиподстановок.
Оператор присваивания позволяет описывать систему какнабор взаимодействующих объектов, каждый из которых можетнаходиться в определенном состоянии и изменять свое состояние. Сдругой стороны, для описания работы с объектами и операторомприсваивания нет простой математической модели.Программирование без использования оператора присваивания называетсяфункциональным программированием. Программирование, в которомиспользуется оператор присваивания, называется императивнымпрограммированием.До сих пор переменные Scheme использовались только для именованиязначений. При использовании присваивания и возможности изменятьзначение переменной, имя должно указывать на некоторую областьпамяти, в которой хранится значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
