Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 150
Текст из файла (страница 150)
Необходимость уделять внимание ячейкам йамятн приводит к методологии программирования относительно низкого уровня, близкого к машинным командам. Программа на языке ассемблера часто к тому же должна хранить результаты промежуточных вычислений. Например, чтобы вычислить выражение (х+уйа-Ы, значение выражения (х+у) должно быть вычислено первым.
Это значение должно быть помещено в память, пока вычисляется значение выражения (а-Ы. Чтобы облегчить эту залачу, размешенце промежуточных результатов вычисления выражений в языках высокого уровня обрабатывается компилятором. Размещение промежуточных результатов в этих языках все еше необходимо, но детали скрыты от программиста. Чисто функциональный язык программирования не использует нн переменных, нн операторов присваивания. Это освобождает программиста от заботы о ячейках памяти компьютера, на котором будет выполняться программа. Отсутствие переменных делает невозможным использование итеративных конструкций, поскольку онн управляются перемен- 583 ) 4.3. Основы функциональных языков программирования ными. Повторение должно выполняться только с помощью релурсии.
Программы представляют собой определения функций и спецификашгй применения функций, а выполнение заключается в вычислении применений функции. В отсутствие переменных выполнение программы. написанной на чисто функциональном языке, не имеет структуры в смысле операционной или денотационной семантики. Выполнение функции при одних и тех же параметрах всегда приводит к одному и тому же результату. Это явление называется прозрачностью ссылок (ге(егепйа! ггаиврагепсу). Она делает семантику чисто функциональных языков программирования намного более простой, чел» семантика императивных языков и функциональных языков, обладающих императивными свойствами.
Функциональный язык содержит набор элементарных функций, набор функциональных форм для построения сложных функций из этих элементарных функций, операцию применения функшш и некоторую структур> или структуры для представления данных. Эти структуры используются для представления параметров и значений, вычисленных функциями. Хорошо определенный язык функционального программирования нуждается лишь в небольшом количестве элементарных функций.
Несмотря на то что функциональные языки программирования часто реализуются с помощью интерпретаторов, они также могут быть компюшруемымгь Императивные языки обычно предусматривают лишь ограниченную поддержку функционального программирования. Большинство из иих, например. содержат некоторый вид определений функций и средства лля их применения. Наиболее серьезный недостаток использования императивного языка для функционального программирования состоит в том, что функции в императивных языках имеют ограничения, наложенные на типы значений, которые они возвращают. В таких языках. как РОКТйАН и Рааса!, функции возвращают только переменные скалярного типа, Еще более важным является то, что они не могут возвращать функции. Такие ограничения сужают круг функциональных форм, поддерживаемых императивным языком.
Другая серьезная проблема, относящаяся к функциям в императивных языках, заключается в том, что функции могут иметь побочные эффекты. 14.4. Первый язык функционального программирования — Е!$Р К настоящему моменту разработано много языков программирования. Наиболее старым и широко используемым из них является язык 1.15Р. Изучение функциональных языков программирования на примере языка Б15Р сродни изучению императивных языков на примере языка РОВТЙАН: язык 1.15Р был первым функциональным языком, но некоторые сейчас думают, несмотря на его постоянное развитие на протяжении последних 30 лет, что он больше не соответствует современным концепциям разработки функциональных языков.
Кроме того, за исключением первой версии, все диалекты языка 1.15Р обладают такими императивными свойствами, как переменные в императивном стиле, операторы присваивания и операторы цикла. (Переменные в императивном стиле используются для именования ячеек памяти, значения в которых могут изменяться много раз в ходе выполнения программы.) Несмотря на это, а также на их довольно странную форму, наследники исходного языка 1.15Р хорошо представляют основные концепции функционального программирования и, следовательно, достойны изучения.
Глава 14. Функциональные языки программирования 14.4.1. Типы и структуры данных Существуют только два типа данных в языке ЬЮР; атомы и списки, В языке ЬБР нет типов в том смысле. в котором они с>шеста>ют в императивных языках. В действительности, язык Ь!БТ вЂ” это язык, лишенный типов. Атомы, имеющие вид идентификаторов, — это символы языка Ь)$Р. Числовые константы также рассматриваются как атомы. Напомним (см. главу 2), что язык Ь(ВР сначала использовал в качестве своей структуры данных списки.
поскольку они считазись существенной частью процесса обработки списков. Со временем, однако. язык ЫБР стал редко нуждаться в операциях вставки и удаления. Списки указываются в виде разлеленных межл> собой элементов. заключенных в скобки. Элементы простых списков являются атомами. как в приведеннол1 примере: (А В С В) Вложенные структуры списков также указываются с помощью скобок. Например, список (А (В С) С (Е (Г С))) представляет собой список из четырех элементов. Первый элемент — атом А; второй элемент — подсписок (В С); третий элемент — атом Гл четвертый элемент — подсписок (Е (Г С) ) .
который солержит в качестве своего второго элемента подсписок (Г 6) . Списки обычно хранятся в виде односвязных структур списков. в которых каждый узел имеет два указателя и представляет собой элемент списка. Первый указатель в узле, представляющем собой атом. ссылается на некоторое представление атома, например, символ или числовое значение. В узле, соответствующем подсписку. первый указатель ссылается на первый узел подсписка. В обоих случаях второй указатель в узле ссылается на следующий элемент списка. Ссылка на список осуществляется через указатель на его первый элемент.
Внутреннее представление списков в лвух наших примерах показано на рис. 14.1. Заметим, что элементы списка показаны горизонтально. Последний элемент списка не имеет последующего элемента, поэтому он содержит нулевой указатель И1Ь. Показаны также подсписки той же самой стрултуры. 14.4.2. Первый интерпретатор языке ЕЗЗР Первоначальным намерением разработчиков было получить обозначения для программы на языке Ь)ВР.
которые были бы как можно ближе к языку ЕОйТКАХ с необходимыми дополнениями. Эти обозначения получили название М-обозначений (мета- обозначения). Требовался компилятор, который мог бы транслировать программы, написанные в системе М-обозначений, в семантически эквивалентные программы на машинном коде компьютера (ВМ 704. На ранней стадии развития языка ЫБР Мак-Карти решил написать статью, которая могла бы обосновать применение обработки списков в качестве полхола к реализации обшей символьной обработки. Мак-Карти полагал. что обработка списков могла быть использована для изучения вопросов вычислимости. которые в то время обычно изучались с помощью машин Тьюринга. Мак-Карти счгггкч.
что обработка символьных списков — более естественная модель вычислений, чем машины Тьюринга. Одно из основных требований при изучении вопросов вычислимости заключается в том, что необхо- 585 ) 4.4. Первый язык функционального программирования — 11$Р димо доказывать определенные характеристики вычислимости целого класса функций при любой модели вычислений. Можно построить универсальную машину Тьюринга, способную имитировать операции, выполняемые любой другой машиной Тьюринга. На основе этой концепции возникла идея построить универсальную 11$Р-функцию, способную вычислять любую функцию в языке 1.1$Р.
а с э (к в с ш ~к ~в с) э ~к <г ш м Рис. 14.1. Внутреннее предстааэение двкп списков в языке 1.1БР Первое требование к универсальной 1.1$Р-функции состояло в необходимости создания системы обозначений, позволяюших выражать функции тем же способом, что и данные. Обозначение списка в виде элементов, заключенных в скобки, описанное в разделе!4.4.1, уже было принято для обозначения данных в языке (.1БР, поэтому было решено придумать соглашения для определения и вызовов функций, позволяюшие выразить их в виде списков, Вызовы функций записывались в префиксной форме списка, получившей название польской записи (СашЪг)бйе Ро!)зй), как показано ниже: (имя функции аргумент 1 ... аргумент п) Например, если + представляет собой функцию, получающую два числовых параметра, то результатом выражения (+ 5 7) является число 12. Для определения функций была выбрана система лямбда-обозначений, описанная в разделе 14.2.1. Однако ее следовало модифицировать, чтобы позволить связывать функции с их именами так, чтобы на функш~и можно было бы ссылаться с помошью других функций или ее самой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
