John Harrison - Введение в функциональное программирование (1108517), страница 2
Текст из файла (страница 2)
. . . . . . . .5.6 Связывания и объявления . . . . . .5.7 Полиморфные функции . . . . . . . .5.8 Равенство функций . . . . . . . . . .6 Более подробно о ML6.1 Основные типы данных и операции6.2 Дальнейшие примеры . . . . . . . .6.3 Определения типов .
. . . . . . . .6.3.1 Сопоставление с образцом .6.3.2 Рекурсивные типы . . . . . .6.3.3 Древовидные структуры . .6.3.4 Тонкости рекурсивных типов7 Доказательство корректности7.1 Функциональные программы7.2 Вычисление степени . . . . .7.3 Вычисление НОД . . . . .
.7.4 Конкатенация списков . . . .7.5 Обращение списков . . . . ...........................................................................................................................................................................................................программкак математические объекты. .
. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .8 Эффективный ML8.1 Полезные комбинаторы . . . . . . . . . . . .8.2 Создание эффективного кода . . . . . . . .8.2.1 Хвостовая рекурсия и аккумуляторы8.2.2 Минимизация операций cons .
. . . .8.2.3 Принудительное вычисление . . . . .8.3 Императивные возможности . . . . . . . . .8.3.1 Исключения . . . . . . . . . . . . . .8.3.2 Ссылки и массивы . . . . . . . . . . .8.3.3 Последовательность вычислений . . .8.3.4 Работа с системой типов . . . . . .
.9 Примеры9.1 Символьное дифференцирование .9.1.1 Термы первого порядка . . .9.1.2 Печать . . . . . . . . . . . .9.1.3 Дифференцирование . . . .9.1.4 Упрощение . . . . . . . . . .9.2 Синтаксический анализ . . . . . . .9.2.1 Метод рекурсивного спуска .viii.............................................................................................................................................................................................................................................................................................................................................................................................515154555556575960.......6364676970737577.....818384858788....................9595979799102103103104106106.......111. 111.
111. 112. 116. 117. 119. 121....................Оглавление9.39.4Оглавление9.2.2 Комбинаторы синтаксического анализа . .9.2.3 Лексический анализ . . . . . . . . . . . . .9.2.4 Анализатор термов . . . . . . . . . . . . .9.2.5 Автоматический учёт приоритетов . . . .9.2.6 Недостатки метода . . . . .
. . . . . . . .Точная арифметика вещественных чисел . . . . .9.3.1 Выбор представления вещественных чисел9.3.2 Целые числа произвольной разрядности .9.3.3 Основные операции . . . . . . . . . . . . .9.3.4 Умножение: общий случай . . . . . . . . .9.3.5 Обратные числа . . . . . .
. . . . . . . . .9.3.6 Отношения порядка . . . . . . . . . . . . .9.3.7 Кэширование . . . . . . . . . . . . . . . . .Пролог и доказательство теорем . . . . . . . . . .9.4.1 Термы пролога . . . . . . . . . . . . . . . .9.4.2 Лексический анализ . . . . . . . . . . . . .9.4.3 Синтаксический анализ . . . . . . . . . . .9.4.4 Унификация . . . . . . . .
. . . . . . . . .9.4.5 Перебор с возвратами . . . . . . . . . . . .9.4.6 Примеры . . . . . . . . . . . . . . . . . . .9.4.7 Доказательство теорем . . . . . . . . . . .ix.................................................................................................................................................................................................................................................................................122124125126128131131132133137138140141144145145146148150151152Глава 1ВведениеПрограммы, написанные на традиционных языках программирования, такихкак FORTRAN, Algol, C и Modula-3, в своей работе опираются на изменениезначений набора переменных, называемого состоянием.
Если мы пренебрежёмоперациями ввода-вывода и вероятностью того, что программа будет работатьпостоянно (например, управляющая система для производства), то мы можемприйти к следующей абстракции. Первоначально состояние имеет некотороезначение σ, представляющее собой входные данные для программы, а послезавершения её исполнения — новое значение σ 0 , представляющее результаты.Выполнение отдельных операторов сводится к изменению ними состояния, котороепоследовательно проходит через конечное число значений:σ = σ0 → σ1 → σ2 → · · · → σn = σ 0Например, в программе сортировки состояние первоначально включает всебя массив значений, а после того, как программа завершается, состояниемодифицируется таким образом, что эти значения становятся упорядоченными, в товремя как промежуточные состояния представляют собой ход достижения даннойцели.Состояние обычно изменяется с помощью операторов присваивания, частозаписываемых в виде v = E или v := E, где v – переменная, а E – некотороевыражение.
Последовательность выполнения таких операторов задаётся в текстепрограммы их размещением друг за другом (при этом часто в качестве разделителяприменяется точка с запятой). С помощью составных операторов, таких как ifи while, можно выполнять операторы в зависимости от условия или циклически,часто полагаясь на другие свойства текущего состояния. В результате программапревращается в набор инструкций по изменению состояния, и поэтому данныйстиль программирования часто называется императивным или процедурным.Соответственно, традиционные языки программирования, поддерживающие такойстиль, также известны как императивные или процедурные языки.Функциональное программирование радикально отличается от этой модели. Посуществу, функциональная программа представляет собой просто выражение, авыполнение программы — процесс его вычисления.1 В общих чертах мы можемпонять, как это возможно, используя следующие рассуждения.
Предположим, что1Функциональное программирование часто называют «аппликативным программированием»,поскольку основной его механизм – это аппликация (применение) функции к аргументам.1Глава 1. Введениеимперативная программа (вся целиком) детерминирована, т.е. выход полностьюопределяется входом; мы можем сказать, что конечное состояние или тот егофрагмент, который нас интересует, являются функцией начального состояния,например σ 0 = f (σ).2 В функциональном программировании эта точка зрения имеетособое значение: программа – это выражение, которое соответствует математическойфункции f . Функциональные языки поддерживают создание таких выражений засчет того, что позволяют использовать мощные функциональные конструкции.Функциональное программирование может противопоставляться императивномукак c хорошей, так и в плохой стороны. К недостаткам ФП можно отнестито, что функциональные программы не используют переменные – то есть неимеют состояния.
Соответственно, они не могут использовать присваивание,поскольку нечему присваивать. Кроме того, идея последовательного выполненияоператоров также бессмысленна, поскольку первый оператор не имеет никакоговлияния на второй, так как нет никакого состояния, передаваемого между ними.К достоинствам функционального подхода можно отнести то, что функциональныепрограммы могут использовать функции более изящным способом.
Функциимогут рассматриваться точно так же, как и более простые объекты, такиекак целые числа: они могут передаваться в другие функции как аргументыи возвращаться в качестве результатов, а также применяться в вычислениях.Вместо последовательного выполнения операторов и использования циклов,функциональные языки программирования предлагают рекурсивные функции, т.е.функции, определённые в терминах самих себя. Большинство традиционных языковпрограммирования обеспечивают весьма скудные возможности в этих областях.Язык C имеет некоторые ограниченные возможности работы с функциями припомощи указателей, но не позволяет создавать новые функции динамически, а языкFORTRAN вообще не поддерживает рекурсию.Продемонстрируем разницу между императивным и функциональнымпрограммированием на примере функции вычисления факториала. Она можетбыть записана императивно на языке C как:int f a c t ( int{ int x = 1 ;while ( n >{ x = x ∗n = n −}return x ;}n)0)n;1;в то время как на языке ML (функциональном языке программирования, которыймы обсудим позже) она может быть реализована в виде рекурсивной функции:l e t rec f a c t n =i f n = 0 then 1else n ∗ f a c t (n − 1 ) ; ;Можно отметить, что такое определение достаточно просто реализовать и2Сравните это с замечанием Наура (Raphael 1966) о том, что мы можем записать любуюпрограмму в виде одного выражения Output = P rogram(Input).2Глава 1.
Введение1.1. Достоинства функционального программированияна языке C. Однако, при необходимости более сложной работы с функциямифункциональные языки не имеют себе равных.1.1ДостоинствапрограммированияфункциональногоНа первый взгляд, язык без переменных или возможности последовательноговыполнения инструкций кажется совершенно непрактичным. Это впечатление неможет быть разрушено с помощью нескольких слов, написанных тут.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
