Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 19
Текст из файла (страница 19)
описывавшей олпу из первых программ ислусственного интеллекта, програк1му (.ой)са1 Тйеопм. а также язык. на котором она могла быть реализована (Ыеттей апд 5(шоп. 1956). Язык. названный 1Р1-1 (1п1оппабоп Ргосезьйпд 1 апйиайе — язык обработки информации). никогда не был внедрен. Слелуюшая версия этого языка ! РЬ-П была реализована на компьютере )оЬпп)ас корпорации Канд Согрогаиоп. Развитие языка 1РЕ продолжалось до 1960 года. в котором было опубликовано описание языка 1Р1 -Ч (Ыеией апб Тапсе. 1960). Широкому распространению языков семейства!РЕ мешал их низкий уровень. Для гипотетического компьютера. реализо- 2.4.
Функциональное программирование: язык ЫБР ванного посредством интерпретаторов с включенными в него командами обработки списков. эти языки фактически были языками ассемблера. Первая их реализация была выполнена на ничем ие примечательной машине 3о!зпп1ас, что также не очень способствовало распространению языков семейства 1Р1.. Вкладом языков семейства!Р(.
в развитие языков программирования были их списковые структуры и наглядная демонстрация того, что обработка списков вполне возможна и полезна. Корпорация 1ВМ заинтересовалась искусственным интеллектом в середине 1950-х годов и в качестве демонстрационной области выбрала доказательство теорем. В то время полным ходом шла разработка языка ГОКТКАХ. Высокая стоимость компилятора языка ГОКТКАХ !убедила корпорацию 1ВМ в том, что обработку списков проще присоединить к языку ГОКТКАХ, чем вылелять ее в отдельный язык.
Так и возник язык ГЕТР (ГОКТКАХ Ызг Ргосеи!пз Еапйцайе — язык обработки списков на базе языка ГОКТКАХ), который был разработан и реализован в качестве расширения языка ГОКТКАХ. Язык Г).РЬ использовался лля доказательства теорем в области планиметрии, которая тогда рассматривалась как простейшая область для механического доказательства теорем. 2.4.2. Процвсс разработки языка 03Р Летом 1958 года отделом информационных исслелований корпорации 1ВМ (!ВМ 1п(огщабоп КезеагсЬ Оераггшепг) был нанят Джон Мак-Карти (1опп МсСаппу) из института М!Т.
Его целью на это лето было исследование символьных вычислений и разработка конструктивных требований для проведения подобных вычислений. В качестве пробной проблемной области он выбрал дифференцирование алгебраических выражений. При изучении этой области появился набор требований к языку. Среди них были методы управления выполнением математических функций: рекурсия и условные выражения. Язык ГОКТКАХ1, единственный существующий на то время язык высокого уровня, ни одной из этих функций не имел. Другие требования вознидли при исследовании символьного дифференцирования изакзючались в необходимости наличия связных списков, динамически размещаемых в памяти, и некоторого способа неявного удаления списков из памяти, использование которых в программе уже не предполагалось.Мак-Карти просто не мог позволить явным операторам освобождения памяти загромождать его изящный алгоритм дифференцирования.
Поскольку язык ГЕРА не поддерживал рекурсию, условные выражения, динамическое выделение памяти или неявное ее освобождение, Мак-Карти стало ясно, что нужен новый язык. Когла осенью 1958 года Мак-Карти вернулся в институт М1Т, он вместе с Марвином Мински (Магч!п М!пзку) основал проект, посвященный искусственному интеллекту, М)Т А! Рго3есг, финансировавшийся Исследовательской электротехнической лабораторией (КезеагсЫ.аЬогагогу Гог Е!ее!гоп(сз).
Первой важной работой нового проекта было создание системы обработки списков. Ее планироваяось использовать лля первоначальной реазизации предложенной Мак-Карти программы, названной Адч1се Такег. Это приложение стало стимулом к развитию языка обработки списков ЫЬР.
Первую версию этого языка иногда называют чистым языком ЫЬР, поскольку он представляет собой язык функционального программирования в чистом виле. Эволюция чистого языка 1.1$Р описывается в следующем разделе. УО Глава 2, Обзор основных языков программирования 2.4.3. Обзор языка 2.4.3.1. Структуры данных В чистом языке ).)БР сушествовато только два типа структур данных: атомы и списки. Атомы могли быть либо символами. принимавшими форму идентификаторов, либо числовыми константами. Естественно использовать для хранения снивольной информации связные списки.
что и было сделано в языке !Р(.-И. Подобные структуры позволяют вставки и улаления в любол~ месте (операции. которые тогда считазись неотьемлемой частью обработки списков). Правда, в конце концов было обнаружено. что подобное в языке Е! БР требуется очень редко. Списки определялись путем разграничения составляющих их элементов круглыми скобками. Простые списки, в которых элементы разделены на атомы, имеют слелуюшую форму: (А В С ()) Структуры со вложенными списками также опрелелялись круглыми скобками. Например, список (А (В С) 0 (В (Г 8))) состоит из четырех элементов. Первый — это атом А, второй — подсписок (В С), третий — атом (), а четвертый — полсписок (В (Г В) ), содержащий в качестве второго элемента подсписок (Г С).
Списки, как правило, представляются в виде односвязных списковых структур, каждый узел которых содержит два указателя и прелставляет собой элемент списка. Первый указатель узла. соответствующего атому, указывает на прелставление атома, т.е. на его символьное или числовое значение. Первый указатель узла. соответствующего элементу подсписка, указывает на первый узел полсписка. В обоих случаях второй указатель узла указывает на следующий элемент списка.
Ссылаются на список, указывая его первый элемент. Внутренние представления двух списков. упомянутых ранее, изображены на рис. 2.2. Отметим, что элементы списка показаны горизонтально. Последний элемент списка не имеет последующего элемента, так что он связан с нулевым указателем )ч? Ь. С помощью подобной же структуры показаны подсписки. 2.4.3.2. Процессы в функциональном программировании Язык ИКР создавался как язык функционального программирования. Все вычисления в функциональной программе производятся путем применения функций к аргументам. Ни операторы присваивания, ни переменные, с избытком имеющиеся в императивных языках программирования, не нужны в программах, написанных на языках функционального программирования.
Более того, итеративные процессы могут определяться с помощью рекурсивных вызовов функций, что делает ненужными циклы. Эти основные концепции функционального программирования отличают его от программирования на императивных языках. 2А. Функциональное программирование: язык ОБР 71 в с 0 г 0 Рис. 2.2. Внутреннее нредстаазение двух списков в языке ИЯР 2.4.З.З. Синтаксис языка й1$Р Язык 1.1БР значительно отличается от императивных языков как из-за того, что он является функциональным языком, так и из-за того, что программы, написанные на этом языке, выглядят совершенно иначе, чем программы, написанные на таких языках, как РСнсТКАХ кли С. Синтаксис языка С, например.
является сложной смесью английского и алгебры, тогда как синтаксис языка 1.18Т вЂ” эталон простоты. Рассмотрим снова список (А В С В) Если интерпретировать его в терминах данных. то это — список из четырех элементов. Если же рассматривать его как программу, то это значит, что функция А применяется к трем параметрам: В, С и О. 2.4.4. Оцвнка Язык 1.1БР всецело ломинировал в сфере искусственного интеллекта четверть столетия, и все еше остается самым распространенным языком в этой области. Устранено большинство причин, создавших языку ЫБР репутацию неэффективного. Скомпилированы многие современные реализации, и результируюшие программы выполняются значительно быстрее, чем интерпретация их исхолного кода. Помимо успехов в области искусственного интеллекта, язык 1.18Р оказался пионером функционального программирования, доказавшего свою жизнеспособность в качестве области исследования языков программирования.
Как указывалось в главе!, многие исследователи языков программирования полагают, что функциональное программирование значительно лучше подходит для разработки программного обеспечения. чем использование императивных языков. На протяжении 1970-х и в начале 1980-х годов было разработано и использовано множество различных диалектов языка 1.18Р. Это привело к знакомой проблеме перено- 72 Глава 2. Обзор основных языков программирования симости. Для исправления возникшей ситуации была создана стандартная версия языка. названная СОММОХ Ь(5Р (5(ее(е. ) 984).
Подробно язык Бсбеве (диалект языка ЫБР) и функшюнальное программирование в целом рассмотрены в главе 14. Ниже следует пример программы на языке Ь)БР. г Пример функции языка Ь51Р Следующая программа определяет греликативную функцию языка Ь1БР, принимающую в качестве аргументов два списка и возвращающую значение ЕОЕ, если оса списка идентичны, и значение И1Ь (РАЬБЕ) в противном случае (ПЕРОМ ес)иа1 11ятя (11я1 11я2) (СОБР ((АТОМ 11я1) (ЕО 11я1 11я2)) ((АТОМ 11я2) И1Ь] ((ес)ца1 11ят (САП 11я1) (СА(( 11я2)) (ес)ца1 11ят (СЭР 11я1) (СО(( 11я2))) (Т (ч1( ) 2.4.5. Два потомка языка ИЗР В наше время широко используются два диалекта языка Ь(БР— язык СОММОХ Ь(БР и язык Бебеле.
Оба кратко рассмотрены в слелуюших подразделах. 2.Я.З.8. Язык Зсйепзе Язык Бсйеше был разработан в институте М)Т в середине 1970-х годов (Бцптап апб 5(ее)е, 1975). Для него характерен небольшой размер, использование исключительно статического обзора данных (рассматриваемого в главе 4). а также обработка функций как объектов первого класса. В таком качестве функции языка Бс(зете могут быть значениями выражений и элементами в списках. присваиваться переменным, передаваться в качестве параметров и возврашаться в качестве результата применения функции к своим аргументам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
