Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 5
Текст из файла (страница 5)
Пусть, например, необходимоопределить операцию возведения в квадрат. Средствами языка Scheme этоможно сделать следующим образом:(define (square x) (* x x))При этом выполняются два действия: создание процедуры и связывание еес именем. Позже будет рассмотрен способ создания процедуры без имени.Общий вид определения процедуры можно записать следующим образом:(define (<name> <formal parameters>) <body>)В этой записи <name> представляет собой имя, которое будет связано сопределением процедуры в соответствующем контексте. < formal24parameters> определяют имена формальных параметров, которыелокализованы в теле процедуры. <body> представляет собой выражение,которое получит значение в результате применения процедуры, когдаформальные параметры будут заменены фактическими.
В общем случае,тело процедуры может быть последовательностью выражений.Интерпретатор вычисляет последовательно все выражения, и в качестверезультата выдает значение последнего выражения, которое быловычислено. Определив процедуру square, ее можно использовать.(square 21)-> 441(square ( + 2 5 ) )-> 49(square (square 3)) -> 81Определенную ранее процедуру можно также использовать приопределении следующих процедур. Например, выражение х2 + у2 можетбыть записано как(+ (square x)(square у)) ипредставлено в виде процедуры.(define (sum-of-squares х у)(sum-of-squares 3 4 )->(+ (square x)25(square у)))В свою очередь процедуру sum-of-squares можно использовать вкачестве блока для построения следующих процедур:(define (f a)(f 5)(sum-of-squares (+ a 1)-> 136(* а 2 ) ) )Составные процедуры используются так же, как и встроенные процедуры.По внешнему виду нельзя определить, является ли процедура встроенной винтерпретатор, или определенной пользователем.Модель подстановок при применении процедурДля того чтобы вычислить выражение, оператор которого является именемсоставной процедуры, интерпретатор выполняет те же действия, которыебыли описаны выше.
То есть, интерпретатор вычисляет значенияподвыражений и применяет процедуру к аргументам. Способ примененияпримитивных процедур к аргументам встроен в интерпретатор. Для тогочтобы применить составную процедуру к аргументам необходимовычислить выражение, являющееся телом процедуры, заменяя каждыйформальный параметр соответствующим аргументом. Рассмотрим примервычисления (f 5 ) , где f - процедура, определенная выше. Начинаем свосстановления тела процедуры f:25(sum-of-squares (+ a 1)(* a 2)) Далеезаменяем формальный параметр, на аргумент 5:(sum-of-squares ( + 5 1 )(* 5 2})Таким образом, задача сведена к вычислению выражения с двумяоперандами и оператором sum-of-squares.
Вычисление этого выражениявключает три подзадачи. Сначала необходимо вычислить оператор, длятого, чтобы получить процедуру, которую нужно применить, а затемвычислить значения операндов, чтобы получить аргументы процедуры.Вычисляя ( + 5 1 ) и (* 5 2) получаем 6 и 10 соответственно. Далеетребуется применить sum-of-squares к аргументам 6 и 10. Получаем(+ (square 6)(square 10))Затем в соответствии с определением square получаем(+(* 6 6)(* 10 10) )что сводится к вычислению (+ 36 100) и приводит к результату 136.Описанный процесс называется моделью подстановок при применениипроцедуры к аргументам.Аппликативный и нормальный порядокСогласно описанию вычисления выражений, интерпретатор сначалавычисляет оператор и операнды, а потом применяет полученнуюпроцедуру к полученным аргументам.
Это не единственный способвыполнения вычисления. Альтернативным способом является модель, вкоторой операнды не вычисляются до тех пор, пока они не требуются.Вместо этого, сначала производится подстановка всех подвыражений, покане будет получено выражение, состоящее только из примитивныхоператоров, после чего выполняются все вычисления. Рассмотрим этотметод на примере вычисления (f 5).
На первом шаге раскрываются всеподвыражения(sum-of-squares ( + 5 1) (* 5 2))(+ (square (+ 5 1)) (square (* 5 2)))(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2) ))и далее происходят свертки26{+ (* 6 6)( + 36 100)136(* 10 10) )Заметам, что вычисление выражений (+ 5 1) и (* 5 2 ) выполняетсядважды, в соответствии со сверткой выражения (* х х), и заменойкаждого х на (+ 5 1) и (* 5 2 ) .Метод «полностью подставь, потом сворачивай», известен как нормальныйпорядок вычисления. Метод «вычисли аргументы, потом примени»,который, как правило, использует интерпретатор, называетсяаппликативным порядком вычисления. Для приведенных выше примеров,оба метода дают одинаковые результаты.
Однако далее будут рассмотреныслучаи, при которых порядок вычисления может привести к разнымрезультатам. Scheme использует аппликативный порядок вычислений,отчасти потому, что он повышает эффективность, в частности, позволяетодин раз вычислять общие подвыражения.Условные выражения и предикатыВ языке Scheme поддерживается набор специальных форм, играющих туже роль, что и управляющие конструкции в традиционных языкахпрограммирования. В частности для записи условных выраженийприменяется форма cond. С ее использованием вычисление модуля целогочисла может быть представлено в следующем виде:(define (abs x)(cond((> х 0) х)( ( = х 0) 0)( (< х 0) ( - х) ) ) )В общем случае условное выражение имеет вид(cond (<p 1> <e2>)(<р2> <е2>)(<рn> <еn>) )где за ключевым словом cond следует список пар выражений <pi> <el>,заключенных в скобки.
Первое выражение в каждой паре являетсяпредикатом, то есть выражением, которое интерпретируется как истинноеили ложное. В Scheme поддерживаются константы #f и #t, обозначающиесоответственно ложь и истину. При вычислении значения не ложь являетсяистиной. Условное выражение вычисляется следующим образом. Сначалавычисляется предикат <pi>.
Если его значение ложь, то вычисляетсяпредикат <р2>. Если значение предиката <р2> также ложь, то вычисляетсяпредикат <рэ>. Процесс продолжается до тех пор, пока не будет найденпредикат<pi >, значением которого будет истина. В этом случае,значением условного выражения будет значение соответствующеговыражения <ei> Если ни один из предикатов не имеет значение истина,значение условного выражения не определено.Процедура abs использует примитивные предикаты >, <, =. Она такжеиспользует оператор «минус», который при использовании с однимаргументом означает изменение знака числа. Процедуру abs можноопределить и другим способом:(define (abs x)(cond ( (< x 0) (-x) )(else x ) ) )else является специальным символом, который можно использоватьвместо предиката в последней альтернативе cond.
В случае невыполненияни одного из условий альтернатива else будет определять значениеусловного выражения. Вместо else можно использовать любоевыражение, которое всегда имеет истинное значение (например, константа#t).Рассмотрим еще один способ определения процедуры abs.(define (abs x)( i f (< x 0)(-x) x) )В этом определении используется специальная форма if, представляющаясобой ограниченный тип условного выражения, который можноиспользовать для рассмотрения ровно двух альтернатив.
Общая форма ifвыражения имеет вид:(if <predicate> <consequent> <alternative>)При вычислении if выражения интерпретатор вычисляет <predicate>.При получении значения истина интерпретатор вычисляет значение<consequent> и оно становится значением if выражения, иначевычисляется значение <alternative> и оно становится значением ifвыражения. Небольшим отличием между if и cond выражениями являетсято, что часть <е i > каждого cond предложения может бытьпоследовательностью выражений, и результатом тогда становитсязначение последнего вычисленного выражения. В if выражении<consequent> и <alternative> должны быть простыми выражениями.28Наряду с примитивными предикатами, такими, как <, >, = в языкеимеются логические операции, которые позволяют строить составныепредикаты. Наиболее часто используемыми являются and, or и not.(and <e1> .
. . <en>)В форме and интерпретатор вычисляет слева направо выражения <e1>.Если одно из вычисленных значений выражений стало ложным, тозначение and выражения будет ложь, а остальные выражения невычисляются. Если все выражения имеют значения истина, то и значениемand выражения будет истина.(or <e1> . . .
<еп>)В форме or интерпретатор вычисляет выражения <e1> слева направо. Еслиодно из вычисленных выражений стало истинным, то это значение и будетзначением or выражения, а остальные выражения вычисляться не будут.Если все выражения имеют значения ложь, то значением всего orвыражения также будет ложь.(not <e>)Значением not выражения будет истина, если значение выражения <е>ложь. Заметим, что and и or выражения являются специальными формами,так как не все их подвыражения вычисляются, not является обычнойпроцедурой.В качестве примера использования логических операций рассмотримвычисление условия 5 < х < 10.(and (< х 5)(< х 10) )Другим примером может быть определение предиката «больше илиравно»:(define (>= х у)(or (> х у)(= х у) ) )(define (>= х у)(not (< х у) ) ) Упражнения 1 . Что будет выданоилиинтерпретатором в ответ на следующие выражения?2910(+534)(- 91) ( / б 2)(+ (* 24) (-4 6))(define a 3)(define b (+ a 1))(+ a b (* a b) )(= a b)(if (and (> b a) (< b (* a b) ) ) b a)(cond ((= a 4) 6) ((= b 4) (+ 6 7 a) ) (else 25))(+ 2 (if (> b a) b a) )(* (cond ((> a b) a) ( (< b a) b) (else -1) ) (+ a 1) )2.
Определить процедуру от трех параметров-чисел, которая вычисляетсумму квадратов двух больших чисел.3 В соответствии с моделью вычисления выражений описать поведениеследующей процедуры:(define (a-plus-abs-b a b)(if (> b 0) + -) a b)) 4.Пусть определены следующие процедуры:(define (p) (p))(define (test х у)( i f (= х 0) 0 у) )Определить поведение интерпретатора при вычислении значениявыражения (test о (р)) в случае апшшкативного порядка вычисления ив случае нормального порядка вычисления. Замечание: вычисление ifвыражения происходит одинаково в обоих случаях.
Вычисляется предикат,и в зависимости от его результата вычисляется первое или второевыражение.Пример. Нахождение квадратного корня методом НьютонаКвадратный корень у из числа х может быть определен следующимобразом: /*корень*/k = у, если у > = 0 и у2 = х. Для вычисления корнявоспользуемся методом приближений Ньютона, по которому, имеяприближенное значение у можно получить более точное приближение ккорню из х, взяв среднее значение у и х/у. Вычислять корень из 2,например, можно следующим образом.Предположим, что начальное приближение .у = /. Тогда:Приближение ух/у11.52/1=21.5/2=1.333330Среднее /у, у)(2+1)/2=1.5(1.3333+ 1.5J/2-1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
