Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 7
Текст из файла (страница 7)
Приописании рекурсивного процесса как некоторой схемы, например,линейной рекурсии, мы имеем в виду развитие процесса, а не синтаксиснаписания процедуры. Рекурсивная процедура (например, iter) можетпорождать итеративный процесс.Проблемы в понимании отличий процесса от порождающей его процедурывозникают потом у, что реализация большинства языковпрограммирования, например Ada, Pascal или С спроектирована такимобразом, что выполнение любой рекурсивной процедуры требуетбольшого количества памяти, которое растет при каждом вызовепроцедуры, даже когда процесс, порождаемый процедурой, является впринципе итеративным. Как следствие, описать итеративный процесс натаких языках возможно только с помощью специальных конструкций длязаписи циклов.
Реализация Scheme выполняет итеративный процесс наконстантном пространстве, даже когда он описан рекурсивнойпроцедурой.Упражнения8. Ниже приведены две процедуры, которые определяют сложение двухположительных целых чисел в терминах процедур inc и dec.(define (+ a b) (if (= а 0) b (inc (+ (dec а) b) ) } )(define (+ a b) (if (= а 0) b (+ (dec a) (inc b) ) ) )36Используя модель подстановок, опишите поведение npoцессовпорожденных процедурами при вычислении (+ 4 5). Какими являютсяпроцессы - итеративными или рекурсивными?Символьные выраженияОпределим класс символьных выражений. Каждая из следующих строксодержит символьное выражение.(JOHN SMITH 33 YEARS)((DAVE 17) (MARY 24) (ELIZABETH 6 ) )((my house) has (large (light windows)))Символьные выражения состоят из элементов, которые называютсяатомами, объединенных в список с помощью скобок.
Если изменитьположение и количество скобок, то вместе с этим изменится структура исмысл выражения. Атомы бывают символьные и числовые. Логическиеконстанты также считаются атомами. Символьный атом рассматриваетсякак одно неделимое целое. К символьным атомам применяется только однаоперация - сравнение.
Общие правила построения символьныхвыражений1. Атом есть символьное выражение.2. Последовательность символьных выражений, заключенная в скобки,является символьным выражением.Списки. Селекторы и конструкторыДля того чтобы оперировать символьными выражениями,операции, с помощью которых можно выделять изподвыражения (селекторы) и составлять выражения извыражений (конструкторы).рассмотримвыраженийимеющихсяПроцедура car может быть применена к списку и ее результатом являетсяпервый (самый левый) элемент в списке. Этот элемент может быть либоатомом, либо списком.
Процедура саг от атома не определена.(саг(саг(саг(саг' (а b с) )' ( (а) b с d) )'а)' () )-> а-> (а)-> ошибка-> ошибкаПроцедура cdr от списка возвращает в результате список, полученный изисходного отбрасыванием его первого элемента. Для атома процедура cdr37не определена. Если исходный список состоит из единственного атома, тозначением процедуры cdr для этого списка является специальный атомni 1, обозначающий пустой список.(cdr ' ( (а) b с d) )d)(cdr ' ( а ) )(cdr ' () )->(b c->->nilошибкаПри помощи процедур саг и cdr можно получить любой элемент спискаНапример, третий элемент списка х задается выражением.(car (cdr (cdr x)))Пусть х есть список (A B С D). Тогда (cdr x) есть (B C D ) , a (cdr(cdr х)) есть (C D).
Таким образом, (car (cdr (cdr x))) есть элементc, который является третьим в исходном списке.В библиотеку языка Scheme входят композиции процедур саг и cdr. Toесть для того, чтобы выбрать элемент из списка, можно воспользоватьсябиблиотечными процедурами:(caar <list>)(cadr <list>)(cdddar <list>)(cddddr <list>)Например, процедура caddr определяется как(define (caddr x) (car (cdr (cdr x)))))В состав библиотеки Scheme входят и более мнемоничные аналогипроцедур выбора элемента из списка:(first <list>)(second <list>)(eighth <list>)Результатом этих процедур являются соответственно первый, второй, ...,восьмой элемент заданного списка.(first ' ( (a b) с d) )(second ' ( (a b) с d) )(eighth ' (a b с d e f g h) )38-> (a b)-> с-> hС помощью процедуры cons можно объединить два символьныхвыражения в новое символьное выражение.
Исходные компонентывыражения (аргументы процедуры cons) можно получить с помощьюпроцедур саг и cdr. Если второй аргумент процедуры cons являетсясписком или специальным атомом nil, то результатом cons будет список,полученный включением первого аргумента в качестве первого элементасписка. Если у есть список длины и то (cons х у) будет списком длинып + 1. Атом nil удобно рассматривать как список нулевой длины, илипустой список. Это символьный атом, но он играет также специальнуюроль, обозначая пустой список.(define x (cons 1 2) )(car x)(cdr x)(definey(cons(definez(cons(car (car z) )(car (cdr z) )(cons 'a ' ( ) )(cons ' ( a ) ' (b с d) )(cons "a" ' ( b e ) )->->3x124))y))-> 1-> 3->->->(a)( ( a ) b с d)("a" b c)Для того чтобы построить список из элементов можно последовательновоспользоваться процедурой cons:(cons 1 (cons 2 (cons 3 (cons 4 nil)))) ->( 1 2 3 4)В Scheme есть также специальная процедура для построения списков(list <a1 > <a 2> <а 3 > .
. . <ап>)которая эквивалентна(cons <a1> (cons <a2> (cons <a3> . . .(cons <an> n i l ) . . . ) ) )Например,(list 1 2 3 4 )(list 'a (+ 3 4) ' c )(list)-»-»->(1 2 3 4)(a 7 c)()Для обработки списков произвольной вложенности, необходимо уметьраспознавать, является ли значение символьного выражения атомом илисписком, и устанавливать равенство атомов. Для этого можноиспользовать следующие предикаты.39(atom? <obj>)Предикат возвращает значение истина, если <obj> (любой объект данныхязыка) является атомом.(atom?(atom?(atom?(atom?(atom?(atom?3)->->car)->' (a 3 ->->'nil)->'#t#t#t#f#t#tУзнать, является ли выражение списком, можно с помощью предиката(list? <obj>)Предикат возвращает значение истина, если <ob j > является списком.(list?(list?(list?(list?'a)' ())' (а b) )' (а .
b ) )->->->->#f#t#t#fПроверка списка на пустоту:(null? <obj>)Предикат возвращает значение истина, если <obj> является пустымсписком.Для сравнения выражений используют предикаты eq?, сравнивающийзначения двух атомов, и equal?, производящий поэлементное сравнениесписков. В последнем случае элементы списка сравниваются по значению,тогда как первый предикат производит сравнение адресов в памяти своихаргументов.(equal? ' (а b) ' (a b))(equal? 3 3 )(equal? 'а 'а)(eq? ' (a b) ' (a b ) )(eq? 3 3 )->->->->->#t#t#t#f#tПроцедуры со спискамиРассмотрим, как определить процедуру list-ref от двух аргументов,списка items и числа п, которая возвращает п-ый элемент списка.40Элементы списка пронумерованы, начиная с 1. Для п = 1 list-refвозвращает первый элемент списка, полученный в результате примененияпроцедуры саг.
Иначе list-ref возвращает (n-l)-ый элемент списка,полученный в результате применения процедуры cdr к исходному списку.(define (list-ref items n)( i f (= n 1)(car items)(list-ref (cdr items) (- n 1 ) ) ) )(define squares (list 1 4 9 16 25))(list-ref squares 4)-> 16Процедура вычисления длины списка (количества элементов в нем)строится по той же схеме.(define (length items)(if (null? items) 0(+ 1 (length (cdr items)))))(length squares)-> 5Длину списка можно вычислить и итеративно:(define (length items)(define (length-iter a count)(if (null? a) count(length-iteg (cdr a) (+ 1 count))))(length-iter items 0))Процедура append строит из двух списков новый, добавляя в началовторого списка элементы первого:(define (append list1 Iist2) (if (null? listl) list2 (cons(car listl) (append (cdr listl) list2))))Упражнения9. Определить процедуру last-element от одного аргумента, непустогосписка, результатом которой является последний элемент заданногосписка.(last-pair (list 1 2 3 4 ) )->410.
Определить процедуру reverse, которая по заданному списку строитновый список, элементы которого расположены в обратном порядке.41(reverse (list 1 2 3 4 ) ) - >(4321)Точечные парыВ общем случае, вторым аргументом процедуры cons может быть каксписок, так и просто атом. И в первом и во втором случае получаем объекттипа точечная пара.(cons 'a 3)(cons ' (а Ь) 'с)(cons 'а (b) )-> (а . 3)-> ((а Ь) .
с)-> (а Ь)Список является частным случаем пары, в которой самый правый элементявляется атомом nil.(pair? <obj>)Предикат возвращает значение истина, если <obj> является парой.Заметим, что пустой список является списком, но не является паройПустой список - это атом.(pair?(pair?(pair?(pair?' (а . b) )' (a b с) )'( ) )' \# ( a b))->->->->#t#t#f#fЗначение выражения (cons e 1 e 2 ) представляется точечной парой(v1.v2), где v1 и v2 суть символьные выражения для значений e1 и е2,независимо от того, какого типа эти значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
