Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 7
Текст из файла (страница 7)
На самом деле сложные программыконструируются методом построения шаг за шагом вычислительных объектов возрастающей сложности. Интерпретатор делает такое пошаговое построение программы особенноудобным, поскольку связи между именами и объектами могут создаваться последовательно по мере взаимодействия программиста с компьютером. Это свойство интерпретаторовоблегчает пошаговое написание и тестирование программ, и во многом благодаря именноему получается так, что программы на Лиспе обычно состоят из большого количестваотносительно простых процедур.Ясно, что раз интерпретатор способен ассоциировать значения с символами и затем вспоминать их, то он должен иметь некоторого рода память, сохраняющую парыимя-объект. Эта память называется окружением (environment) (а точнее, глобальным8 Мы не печатаем в этой книге ответы интерпретатора при вычислении определений, поскольку они зависятот конкретной реализации языка.1.1.
Элементы программирования29окружением (global environment), поскольку позже мы увидим, что вычисление можетиметь дело с несколькими окружениями)9 .1.1.3. Вычисление комбинацийОдна из наших целей в этой главе — выделить элементы процедурного мышления.Рассуждая в этом русле, примем во внимание, что интерпретатор, вычисляя значениекомбинации, тоже следует процедуре:• Чтобы вычислить комбинацию, требуется:– Вычислить все подвыражения комбинации.– Применить процедуру, которая является значением самого левого подвыражения (оператора) к аргументам — значениям остальных подвыражений (операндов).Даже в этом простом правиле видны несколько важных свойств процессов в целом.Прежде всего, заметим, что на первом шаге для того, чтобы провести процесс вычисления для комбинации, нужно сначала проделать процесс вычисления для каждого элемента комбинации.
Таким образом, правило вычисления рекурсивно (recursive) по своейприроде; это означает, что в качестве одного из своих шагов оно включает применениетого же самого правила10 .Заметьте, какую краткость понятие рекурсии придает описанию того, что в случаекомбинации с глубоким вложением выглядело бы как достаточно сложный процесс. Например, чтобы вычислить(* (+ 2 (* 4 6))(+ 3 5 7))требуется применить правило вычисления к четырем различным комбинациям. Картинуэтого процесса можно получить, нарисовав комбинацию в виде дерева, как показано нарис. 1.1.
Каждая комбинация представляется в видевершины, а ее оператор и операнды — в виде ветвей, исходящих из этой вершины. Концевые вершины (то есть те, изкоторых не исходит ни одной ветви) представляют операторы или числа. Рассматриваявычисление как дерево, мы можем представить себе, что значения операндов распространяются от концевых вершин вверх и затем комбинируются на все более высокихуровнях. Впоследствии мы увидим, что рекурсия — это вообще очень мощный методобработки иерархических, древовидных объектов. На самом деле форма правила вычисления «распространить значения наверх» является примером общего типа процессов,известного как накопление по дереву (tree accumulation).9В главе 3 мы увидим, что понятие окружения необходимо как для понимания работы интерпретаторов,так и для их реализации.10 Может показаться странным, что правило вычисления предписывает нам в качестве части первого шагавычислить самый левый элемент комбинации, — ведь до сих пор это мог быть только оператор вроде +или *, представляющий встроенную процедуру, например, сложение или умножение.
Позже мы увидим, чтополезно иметь возможность работать и с комбинациями, чьи операторы сами по себе являются составнымивыражениями.Глава 1. Построение абстракций с помощью процедур30390*15267++3242*564Рис. 1.1. Вычисление, представленное в виде дерева.Далее, заметим, что многократное применение первого шага приводит нас к такойточке, где нам нужно вычислять уже не комбинации, а элементарные выражения, аименно числовые константы, встроенные операторы или другие имена. С этими случаямимы справляемся, положив, что:• значением числовых констант являются те числа, которые они называют;• значением встроенных операторов являются последовательности машинных команд, которые выполняют соответствующие операции; и• значением остальных имен являются те объекты, с которыми эти имена связаны вокружении.Мы можем рассматривать второе правило как частный случай третьего, постановив,что символы вроде + и * тоже включены в глобальное окружение и связаны с последовательностями машинных команд, которые и есть их «значения».
Главное здесь — этороль окружения при определении значения символов в выражениях. В таком диалоговомязыке, как Лисп, не имеет смысла говорить о значении выражения, скажем, (+ x 1),не указывая никакой информации об окружении, которое дало бы значение символу x(и даже символу +). Как мы увидим в главе 3, общее понятие окружения, предоставляющего контекст, в котором происходит вычисление, будет играть важную роль в нашемпонимании того, как выполняются программы.Заметим, что рассмотренное нами правило вычисления не обрабатывает определений.Например, вычисление (define x 3) не означает применение define к двум аргументам, один из которых значение символа x, а другой равен 3, поскольку смысл defineкак раз и состоит в том, чтобы связать x со значением. (Таким образом, (definex 3) — не комбинация.)1.1. Элементы программирования31Такие исключения из вышеописанного правила вычисления называются особымиформами (special forms).
Define — пока что единственный встретившийся нам примерособой формы, но очень скоро мы познакомимся и с другими. У каждой особой формы свое собственное правило вычисления. Разные виды выражений (вместе со своимиправилами вычисления) составляют синтаксис языка программирования. По сравнениюс большинством языков программирования, у Лиспа очень простой синтаксис; а именно, правило вычисления для выражений может быть описано как очень простое общееправило плюс специальные правила для небольшого числа особых форм11 .1.1.4. Составные процедурыМы нашли в Лиспе некоторые из тех элементов, которые должны присутствовать влюбом мощном языке программирования:• Числа и арифметические операции представляют собой элементарные данные ипроцедуры.• Вложение комбинаций дает возможность комбинировать операции.• Определения, которые связывают имена со значениями, дают ограниченные возможности абстракции.Теперь мы узнаем об определениях процедур (procedure definitions) — значительноболее мощном методе абстракции, с помощью которого составной операции можно датьимя и затем ссылаться на нее как на единое целое.Для начала рассмотрим, как выразить понятие «возведения в квадрат».
Можно сказать так: «Чтобы возвести что-нибудь в квадрат, нужно умножить его само на себя».Вот как это выражается в нашем языке:(define (square x) (* x x))Это можно понимать так:(define↑Чтобы(square↑возвести в квадратx)↑что-л.*↑умножьx↑этоx))↑само на себяЗдесь мы имеем составную процедуру (compound procedure), которой мы дали имяsquare. Эта процедура представляет операцию умножения чего-либо само на себя.
Тавещь, которую нужно подвергнуть умножению, получает здесь имя x, которое играет ту11 Особые синтаксические формы, которые представляют собой просто удобное альтернативное поверхностноепредставление для того, что можно выразить более унифицированным способом, иногда называют синтаксическим сахаром (syntactic sugar), используя выражение Питера Ландина. По сравнению с пользователямидругих языков, программистов на Лиспе, как правило, мало волнует синтаксический сахар. (Для контраставозьмите руководство по Паскалю и посмотрите, сколько места там уделяется описанию синтаксиса).
Такоепрезрение к синтаксису отчасти происходит от гибкости Лиспа, позволяющего легко изменять поверхностныйсинтаксис, а отчасти из наблюдения, что многие «удобные» синтаксические конструкции, которые делают языкменее последовательным, приносят в конце концов больше вреда, чем пользы, когда программы становятсябольшими и сложными. По словам Алана Перлиса, «Синтаксический сахар вызывает рак точки с запятой».32Глава 1. Построение абстракций с помощью процедурже роль, что в естественных языках играет местоимение. Вычисление этого определениясоздает составную процедуру и связывает ее с именем square12 .Общая форма определения процедуры такова:(define (hимяi hформальные-параметрыi) hтелоi)hИмяi — это тот символ, с которым нужно связать в окружении определение процедуры13 . hФормальные-параметрыi — это имена, которые в теле процедуры используютсядля отсылки к соответствующим аргументам процедуры. hТелоi — это выражение, которое вычислит результат применения процедуры, когда формальные параметры будут заменены аргументами, к которым процедура будет применяться14 .
hИмяi и hформальныепараметрыi заключены в скобки, как это было бы при вызове определяемой процедуры.Теперь, когда процедура square определена, мы можем ее использовать:(square 21)441(square (+ 2 5))49(square (square 3))81Кроме того, мы можем использовать square при определении других процедур.
Например, x2 + y 2 можно записать как(+ (square x) (square y)))Легко можно определить процедуру sum-of-squares, которая, получая в качествеаргументов два числа, дает в результате сумму их квадратов:(define (sum-of-squares x y)(+ (square x) (square y)))(sum-of-squares 3 4)25Теперь и sum-of-squares мы можем использовать как строительный блок при дальнейшем определении процедур:12 Заметьте, что здесь присутствуют две различные операции: мы создаем процедуру, и мы даем ей имяsquare. Возможно, и на самом деле даже важно, разделить эти два понятия: создавать процедуры, никак ихне называя, и давать имена процедурам, уже созданным заранее.
Мы увидим, как это делается, в разделе 1.3.2.13 На всем протяжении этой книги мы будем описывать обобщенныйсинтаксис выражений, используя курсивв угловых скобках — напр. hимяi, чтобы обозначить «дырки» в выражении, которые нужно заполнить, когдаэто выражение используется в языке.14 В более общем случае тело процедуры может быть последовательностью выражений. В этом случае интерпретатор вычисляет по очереди все выражения в этой последовательности и возвращает в качестве значенияприменения процедуры значение последнего выражения.1.1. Элементы программирования33(define (f a)(sum-of-squares (+ a 1) (* a 2)))(f 5)136Составные процедуры используются точно так же, как элементарные.
В самом деле,глядя на приведенное выше определение sum-of-squares, невозможно выяснить, былали square встроена в интерпретатор, подобно + и *, или ее определили как составнуюпроцедуру.1.1.5. Подстановочная модель применения процедурыВычисляя комбинацию, оператор которой называет составную процедуру, интерпретатор осуществляет, вообще говоря, тот же процесс, что и для комбинаций, операторыкоторых называют элементарные процедуры — процесс, описанный в разделе 1.1.3. Аименно, интерпретатор вычисляет элементы комбинации и применяет процедуру (значение оператора комбинации) к аргументам (значениям операндов комбинации).Мы можем предположить, что механизм применения элементарных процедур к аргументам встроен в интерпретатор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
