Навигация
Функциональное программирование
25575
знаков
0
таблиц
1
изображение
Н.Н.Непейвода, Интернет Университет Информационных Технологий, INTUIT.ru
Функциональное программирование объясняется на примере диалекта Common Lisp языка LISP. Этот диалект наиболее распространен и имеет официальный стандарт. Common Lisp может работать не только в пакетном режиме (когда он запускается как обычная программа), но и в режиме диалога.
LISP - вероятно, первый из практически реализованных языков1, который основывался на серьезном теоретическом фундаменте и пытался поднять практику программирования до уровня концепций, а не наоборот - опустить концепции до уровня существовавшей на момент создания языка практики.
В настоящий момент функциональное программирование представлено целым семейством языков, но LISP свои позиции не сдает.
λ-абстракции
В некоторых случаях осознанное усвоение концепций даже на самом низком уровне нереально без базовых теоретических сведений. А знакомство с таким базисом, в свою очередь, стимулирует значительно более глубокий интерес к теории и способствует пониманию того, что на высшие уровни знаний и умений не подняться без овладения теорией.
Теоретической основой языка LISP является логика функциональности: комбинаторная логика или (по наименованию одного из основных понятий в наиболее популярной из нынешних ее формализаций) λ-исчисление.
В λ-исчислении выразительные средства, на первый взгляд, крайне скупы. Имеются две базисные операции: применение функции к аргументу (λx) и квантор образования функции по выражению λx t[x]. В терминах λ-исчисления функция возведения числа в квадрат записывается как λx (sqrx) или, если быть ближе к обычным математическим обозначениям, λx x2.
Основная операция - символьное вычисление применения функции к аргументу: (λx t[x] u) преобразуется в t[u]. Но эта операция может применяться в любом месте выражения, так что никакая конкретная дисциплина вычислений не фиксируется. Более того, функции могут вычисляться точно так же, как аргументы. Уже эта маленькая тонкость приводит к принципиальному расширению возможностей λ-исчисления по сравнению с обычными вызовами процедур. Если мы желаем ограничиться лишь ею, рассматривается типизированное λ-исчисление, в котором, как принято в большинстве современных систем программирования, значения строго разделены по типам. В типизированном λ-исчислении есть только типы функций, но этого хватает, поскольку функции могут принимать в качестве параметров и выдавать функции.
Но в исходной своей форме λ-исчисление является нетипизированным, любой объект может быть и функцией, и аргументом, и, более того, функция может применяться к самой себе. Конечно же, при этом появляется возможность зацикливания, но без нее не обойдется ни одна <универсальная> алгоритмическая система. Например, выражение
(λx (xx) λx (xx))
вычисляется бесконечно, а чуть более сложное выражение
((λx λy x a) (λx (xx) λx (xx)))
может либо дать a, либо зациклиться, в зависимости от выбора порядка его вычисления. Но все равно, если мы приходим к результату, то он определяется однозначно. Так что совместность вычислений не портит однозначности, если язык хорошо сконструирован.
Дж. Маккарти перенес идеи λ-исчисления в программирование, не потеряв практически ничего из исходных концепций. Далее, он заметил, что в рудиментарном виде в λ-исчислении появилось понятие списка, и перенес списки в качестве основных структур данных в свой язык. λ-исчислением было навеяно и соглашение языка LISP о том, что первый член списка трактуется как функция, применяемая к остальным.
Списки и функциональные выраженияОсновной единицей данных для LISP-системы является список.
Списки задаются следующим индуктивным определением.
Пустой список () (обозначаемый также nil) является списком.
Если l1,. . . , ln, n ≥ 1 - атомы либо списки, то (l1, . . . , ln) - также список.
Элементами списка (l1, . . . , ln) называются l1, . . . , ln. Равенство списков задается следующим индуктивным определением.
l = nil тогда и только тогда, когда l также есть nil.
(l1, . . . , ln) = (k1, . . . , km) тогда и только тогда, когда n = m и соответствующие li = ki.
Пример 8.2.2. Все списки (), (()), ((())) и т. д. различны. Различны также и списки nil, (nil, nil), (nil, nil, nil) и так далее. Попарно различны и списки ((a,b), c), (a, (b,c)), (a,b,c), где a, b, c - различные атомы.
Поскольку понятие, задаваемое индуктивным определением, должно строиться в результате конечного числа шагов применения определения, мы исключаем списки, ссылающиеся сами на себя. Списки в нашем рассмотрении изоморфны упорядоченным конечным деревьям, листьями которых являются nil либо атомы.
Вершины списка l задаются следующим индуктивным определением.
Элементы списка являются его вершинами.
Вершины элементов списка являются его вершинами.
Длиной списка называется количество элементов в нем. Глубиной списка называется максимальное количество вложенных пар скобок в нем. Соединением списков (l1, . . . , ln) и (k1, . . . , km) называется список
(l1, . . . , ln, k1, . . . , km).
Замена вершины a списка l на атом либо список m получается заменой поддерева l, соответствующего a, на дерево для m. Замена обозначается l[a | m]. Через l[a || m] будем обозначать результат замены нескольких вхождений вершины a на m.
Атомами в языке lisp являются числа, имена, истина T. Ложью служит пустой список nil, который в принципе атомом не является, но в языке lisp при проверке на то, является ли он атомом, выдается истина. Точно так же выдается истина и при проверке, является ли он списком. Однако все списковые операции применимы к nil, а те, которые работают с атомами, часто к нему неприменимы. Например, попытка присваивания значения выдает ошибку.
Основная операция для задания списков (list a b . . . z). Она вычисляет свои аргументы и собирает их в список. Для этой операции без вычисления аргументов есть скоропись '(a b . . . z). Она является частным случаем функции quote (сокращенно обозначаемой '), которая запрещает всякие вычисления в своем аргументе и копирует его в результат так, как он есть.
По традиции, элементарные операции разбора списков обозначаются именами, которые начинаются с c и кончаются на r, а в середине идет некоторая последовательность букв a и d; (car s) выделяет голову (первый член списка), (cdr s) - хвост (подсписок всех членов, начиная со второго). Буквы a и d применяются, начиная с конца. Общее число символов в получающемся атоме должно быть не больше шести. Рассмотрим фрагмент диалога, иллюстрирующий эти операции. Как только в диалоге вводится законченное выражение, оно вычисляется либо выдается ошибка.
[13]>(setq a '(b c (d e) f g))
(B C (D E) F G)
[14]> (cddr a)
((D E) F G)
[15]> (cddar a)
*** - CDDAR: B is not a list
Похожие работы
... . В частности: (8) Из (7) и (8) следует, что в M нет двух неравных натуральных чисел. Доказательство закончено. 3.2 Рекурсия Особое место для систем функционального программирования приобретает рекурсия, поскольку она позволяет учитывать значения функции на предыдущих шагах. С теоретической точки зрения рекурсивные определения являются теоретической основой всей современной ...
... программирование [application programming] — разработка и отладка программ для конечных пользователей, например бухгалтерских, обработки текстов и т. п. Системное программирование [system programming] — разработка средств общего программного обеспечения, в том числе операционных систем, вспомогательных программ, пакетов программ общесистемного назначения, например: автоматизированных систем ...
... разработки программ, но и разработку пакетов прикладных программ. Эти разработки должны обеспечивать высокое качество и вестись примерно так же, как и выпуск промышленной продукции. Достижения компьютерной техники 1. Универсальные настольные ПК Что такое настольный компьютер, объяснять никому не надо — это любимое молодежью устройство, чтобы красиво набирать тексты рефератов, а ...
... набор процедур и функций языков программирования Basic и Pascal, позволяют управлять графическим режимом работы экрана, создавать разнооборазные графические изображения и выводить на экран текстовые надписи. ГЛАВА 2. ГРАФИЧЕСКИЕ ВОЗМОЖНОСТИ ЯЗЫКА ПРОГРАММИРОВАНИЯ В КУРСЕ ИНФОРМАТИКИ БАЗОВОЙ ШКОЛЫ (НА ПРИМЕРЕ BASIC И PASCAL) 2.1 Разработка мультимедиа курса «Графические возможности языков ...
0 комментариев