Chapter 2/ Functional Programming in ML / Функциональное программирование в МЛ: Functional Programming in ML

Функциональное программирование в ML

KuznetsovaMarina 22.04.14 в 09:49

Эта глава является введением в некоторые аспекты функционального программирования. Это также руководство по языку программирования ML. В нескольких следующих главах мы будем использовать программные конструкции ML для теории категорий. Те, кто знаком с ML-языком, может смело пропустить главу. Индекс ключевых слов ML находится в конце книги в качестве справки при чтении программ на ML.

KuznetsovaMarina 22.04.14 в 09:50

Функциональное программирование возникло из двух источников: исполнения программ вычислительной техникой и интереса специалистов в области логики к языкам и функциям. Ранние компьютерные программы состояли из последовательностей машинных команд. Была сложность в разборе этих программ, с тем чтобы установить их поведение. Частично проблема была лингвистическая: было различие между отдельными командами и предполагаемым поведением. Кроме того, простые свойства подстановки, обычно связанные с переменными, не были применимы к этим программам. Действие, связанное с командой, зависело не только от контекста команды в программе, но и от состояния машины, которая определялась вычислительной историей программы.

KuznetsovaMarina 22.04.14 в 09:52

Ландин [1966] отметил, что многие из особенностей языков программирования можно было бы сохранить, при этом используя обычные правила подстановки. Маккарти [1960] ранее разработал такой язык программирования под названием Lisp. С тех пор было разработано и много других «функциональных» языков программирования. Все они основаны на определении функций и удовлетворяют, в основном, стандартным правилам подстановки.

KuznetsovaMarina 22.04.14 в 09:53

9

KuznetsovaMarina 22.04.14 в 09:53

Другой исторической ветвью является развитие специалистами-логиками языков для описания функций. Это была попытка трактовать функции примитивно, определяя "правилами", а не в виде графов, определенных на основе множеств. Развивались два направления. Комбинаторная логика [Карри, Фьюс 68] предложила описание независимых переменных функции. Бэкус [1978] предложил язык независимых переменных и язык комбинатор, разработаный для программирования. Примерно в то же время, когда начиналось развитие комбинаторной логики, Чеч [1941] предложили λ-нотацию для функций и связанных с ними вычислений. λ-вычисления повлияли на теорию и разработку современных языков программирования.

KuznetsovaMarina 22.04.14 в 09:55

Наш интерес заключается в языках для описания математических конструкций. Конструкции преобразуют ввод в вывод, переводя структуры одного вида в структуры иного вида. Такая зависимость вывода от входных данных функциональна и создает функциональный язык программирования, подходящий для программирования выражений, которые используются в теории категорий. Мы описываем здесь функциональный язык программирования ML, который мы использовали для программ по теории категорий.

KuznetsovaMarina 22.04.14 в 09:56

ML был разработан Милнером [1978] в качестве языка для построения математических доказательств на компьютере - отсюда и название: это метаязык (ML), получивший развитие. ML обязан своим предшественникам, таким как Lisp [Маккарти 60] и ISWIM [Ландин 66], а также λ-вычислениям. Он имеет сходства с другими языками программирования, типа Миранда [Turner 86] и OBJ [Гоген 79]. Новинкой является его система типизации с полиморфными типами и наличием механизма определения типа. Язык основан на уравнениях рекурсий высшего порядка для определения функции. Он включает в себя механизм абстрактного типа и поддержку модульного программирования [Маккуин 85].

KuznetsovaMarina 22.04.14 в 09:58

Различные не функциональные особенности, такие как исключения и ссылки, оказались очень удобны и были включены в язык. ML можно использовать в интерактивном режиме. Типы и функции могут быть определены, а выражения вычислены достаточно простыми методами. Читателям предлагается попробовать попрограммировать на ML; они смогут получить приятный опыт.

KuznetsovaMarina 22.04.14 в 09:59

Версия ML, которую мы описываем, известна как Standard ML, была разработана командой в Эдинбурге под руководством Робина Милнера [1984]. Она включает в себя функции предыдущих версий ML, а также языка Hope [Берсталл, Маккуин, Санелла 80]. Полное и доступное языка [Викстро 87] и [Харпер, Митчелл 86]. Последнее оказалось полезным при составлении этой главы. В последующем описании мы концентрируемся на тех особенностях ML, которые мы используем в программировании для теории категорий.

KuznetsovaMarina 22.04.14 в 10:00