Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 6
Текст из файла (страница 6)
Способность2 Большинство крупных Лисп-программ 1970х, были написаны на одном из двух диалектов: MacLisp (Moon1978; Pitman 1983), разработанный в рамках проекта MAC в MIT, и InterLisp (Teitelman 1974), разработанный в компании «Болт, Беранек и Ньюман» и в Исследовательском центре компании Xerox в Пало Альто.Диалект Portable Standard Lisp (Переносимый Стандартный Лисп, Hearn 1969; Griss 1981) был спроектировантак, чтобы его легко было переносить на разные машины. MacLisp породил несколько поддиалектов, напримерFranz Lisp, разработанный в Калифорнийском университете в Беркли, и Zetalisp (Moon 1981), который основывался на специализированном процессоре, спроектированном в лаборатории Искусственного Интеллекта вMIT для наиболее эффективного выполнения программ на Лиспе. Диалект Лиспа, используемый в этой книге,называется Scheme (Steele 1975). Он был изобретен в 1975 году Гаем Льюисом Стилом мл.
и ДжеральдомДжеем Сассманом в лаборатории Искусственного Интеллекта MIT, а затем заново реализован для использования в учебных целях в MIT. Scheme стала стандартом IEEE в 1990 году (IEEE 1900). Диалект Common Lisp(Steele 1982; Steele 1990) был специально разработан Лисп-сообществом так, чтобы сочетать свойства болееранних диалектов Лиспа и стать промышленным стандартом Лиспа. Common Lisp стал стандартом ANSI в1994 году (ANSI 1994).3 Одним из таких приложений был пионерский эксперимент, имевший научное значение — интегрированиедвижения Солнечной системы, которое превосходило по точности предыдущие результаты примерно на двапорядка и продемонстрировало, что динамика Солнечной системы хаотична.
Это вычисление стало возможнымблагодаря новым алгоритмам интегрирования, специализированному компилятору и специализированному компьютеру; причем все они были реализованы с помощью программных средств, написанных на Лиспе (Abelsonet al. 1992; Sussman and Wisdom 1992).1.1. Элементы программирования25представлять процедуры в качестве данных делает Лисп еще и замечательным языкомдля написания программ, которые должны манипулировать другими программами в качестве данных, таких как интерпретаторы и компиляторы, поддерживающие компьютерные языки. А помимо и превыше всех этих соображений, писать программы на Лиспе —громадное удовольствие.1.1.
Элементы программированияМощный язык программирования — это нечто большее. чем просто средство, с помощью которого можно учить компьютер решать задачи. Язык также служит средой, вкоторой мы организуем свое мышление о процессах. Таким образом, когда мы описываемязык, мы должны уделять особое внимание тем средствам, которые в нем имеются длятого, чтобы комбинировать простые понятия и получать из них сложные. Всякий языкпрограммирования обладает тремя предназначенными для этого механизмами:элементарные выражения, представляющие минимальные сущности, с которыми языкимеет дело;средства комбинирования, с помощью которых из простых объектов составляютсясложные;средства абстракции, с помощью которых сложные объекты можно называть и обращаться с ними как с единым целым.В программировании мы имеем дело с двумя типами объектов: процедурами и данными.
(Впоследствии мы обнаружим, что на самом деле большой разницы между ними нет.)Говоря неформально, данные — это «материал», который мы хотим обрабатывать, а процедуры — это описания правил обработки данных. Таким образом, от любого мощногоязыка программирования требуется способность описывать простые данные и элементарные процедуры, а также наличие средств комбинирования и абстракции процедур иданных.В этой главе мы будем работать только с простыми численными данными, так что мысможем сконцентрировать внимание на правилах построения процедур4 .
В последующихглавах мы увидим, что те же самые правила позволяют нам строить процедуры дляработы со сложными данными.4 Называть числа «простыми данными» — это бесстыдный блеф. На самом деле работа с числами являетсяодной из самых сложных и запутанных сторон любого языка программирования. Вот некоторые из возникающих при этом вопросов: Некоторые компьютеры отличают целые числа (integers), вроде 2, от вещественных(real numbers), вроде 2.71. Отличается ли вещественное число 2.00 от целого 2? Используются ли одни и теже арифметические операции для целых и для вещественных чисел? Что получится, если 6 поделить на 2:3 или 3.0? Насколько большие числа мы можем представить? Сколько десятичных цифр после запятой мыможем хранить? Совпадает ли диапазон целых чисел с диапазоном вещественных? И помимо этих вопросов,разумеется, существует множество проблем, связанных с ошибками округления — целая наука численногоанализа.
Поскольку в этой книге мы говорим о проектировании больших программ, а не о численных методах,все эти проблемы мы будем игнорировать. Численные примеры в этой главе будут демонстрировать такое поведение при округлении, какое можно наблюдать, если использовать арифметические операции, сохраняющиепри работе с вещественными числами ограниченное число десятичных цифр после запятой.26Глава 1. Построение абстракций с помощью процедур1.1.1. ВыраженияСамый простой способ начать обучение программированию — рассмотреть несколькотипичных примеров работы с интерпретатором диалекта Лиспа Scheme. Представьте, чтоВы сидите за терминалом компьютера. Вы печатаете выражение (expression), а интерпретатор отвечает, выводя результат вычисления (evaluation) этого выражения.Один из типов элементарных выражений, которые Вы можете вводить — это числа.(Говоря точнее, выражение, которое Вы печатаете, состоит из цифр, представляющихчисло по основанию 10.) Если Вы дадите Лиспу число486интерпретатор ответит Вам, напечатав5486Выражения, представляющие числа, могут сочетаться с выражением, представляющим элементарную процедуру (скажем, + или *), так что получается составное выражение, представляющее собой применение процедуры к этим числам.
Например:(+ 137 349)486(- 1000 334)666(* 5 99)495(/ 10 5)2(+ 2.7 10)12.7Выражения такого рода, образуемые путем заключения списка выражений в скобки с целью обозначить применение функции к аргументам, называются комбинациями (combinations). Самый левый элемент в списке называетсяоператором (operator), аостальные элементы — операндами (operands). Значение комбинации вычисляется путем применения процедуры, задаваемой оператором, каргументам (arguments), которыеявляются значениями операндов.Соглашение, по которому оператор ставится слева от операндов, известно как префиксная нотация (prefix notation), и поначалу оно может сбивать с толку, посколькусущественно отличается от общепринятой математической записи. Однако у префикснойнотации есть несколько преимуществ.
Одно из них состоит в том, что префиксная записьможет распространяться на процедуры с произвольным количеством аргументов, как вследующих примерах:5 Здесь и далее, когда нам нужно будет подчеркнуть разницу между вводом, который набирает на терминале пользователь, и выводом, который производит компьютер, мы будем изображать последний наклоннымшрифтом.1.1. Элементы программирования27(+ 21 35 12 7)75(* 25 4 12)1200Не возникает никакой неоднозначности, поскольку оператор всегда находится слева, ався комбинация ограничена скобками.Второе преимущество префиксной нотации состоит в том, что она естественным образом расширяется, позволяя комбинациям вкладываться (nest) друг в друга, то естьдопускает комбинации, элементы которых сами являются комбинациями:(+ (* 3 5) (- 10 6))19Не существует (в принципе) никакого предела для глубины такого вложения и общейсложности выражений, которые может вычислять интерпретатор Лиспа.
Это мы, люди,путаемся даже в довольно простых выражениях, например(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))а интерпретатор с готовностью вычисляет его и дает ответ 57. Мы можем облегчить себезадачу, записывая такие выражения в форме(+ (* 3(+ (* 2 4)(+ 3 5)))(+ (- 10 7)6))Эти правила форматирования называются красивая печать (pretty printing). Согласноим, всякая длинная комбинация записывается так, чтобы ее операнды выравнивалисьвертикально.
Получающиеся отступы ясно показывают структуру выражения6 .Даже работая со сложными выражениями, интерпретатор всегда ведет себя одинаковым образом: он считывает выражение с терминала, вычисляет его и печатает результат.Этот способ работы иногда называют циклом чтение-вычисление-печать (read-eval-printloop). Обратите особое внимание на то, что не нужно специально просить интерпретаторнапечатать значение выражения7 .1.1.2.
Имена и окружениеОдна из важнейших характеристик языка программирования — какие в нем существуют средства использования имен для указания на вычислительные объекты. Мы6 Какправило, Лисп-системы содержат средства, которые помогают пользователям форматировать выражения. Особенно удобны две возможности: сдвигать курсор на правильную позицию для красивой печати каждыйраз, когда начинается новая строка и подсвечивать нужную левую скобку каждый раз, когда печатается правая.7 Лисп следует соглашению, что у всякого выражения есть значение. Это соглашение, вместе со старойрепутацией Лиспа как неэффективного языка, послужило источником остроумного замечания Алана Перлиса(парафразы из Оскара Уайльда), что «Программисты на Лиспе знают значение всего на свете, но ничему незнают цену».Глава 1.
Построение абстракций с помощью процедур28говорим, что имя обозначает переменную (variable), чьим значением (value) являетсяобъект.В диалекте Лиспа Scheme мы даем вещам имена с помощью слова define. Предложение(define size 2)заставляет интерпретатор связать значение 2 с именем size8 . После того, как имя sizeсвязано со значением 2, мы можем указывать на значение 2 с помощью имени:size2(* 5 size)10Вот еще примеры использования define:(define pi 3.14159)(define radius 10)(* pi (* radius radius))314.159(define circumference (* 2 pi radius))circumference62.8318Слово define служит в нашем языке простейшим средством абстракции, поскольку оно позволяет нам использовать простые имена для обозначения результатов сложныхопераций, как, например, вычисленная только что длина окружности — circumference.Вообще говоря, вычислительные объекты могут быть весьма сложными структурами, ибыло бы очень неудобно, если бы нам приходилось вспоминать и повторять все их деталикаждый раз, когда нам захочется их использовать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
