), фактически подстрочник.
Некоторые вещи в источнике освещены не очень. Может быть имеет смысл заменить на варианты из лекций Душкина (МИФИ) по функциональному пронраммированию ( и+или других).
3. Технические вопросы
Этот раздел дает краткие ответы на разные технические вопросы, касающиеся функциональных языков, и некоторые ссылки на литературу и Интернет ресурсы.
3.1. Чистота
Что такое «чисто функциональный» язык программирования?
Этот вопрос был предметом многочисленных обсуждений в функциональном программировании. Принято считать, что языки, такие как Haskell и Miranda – это «чисто функциональные», в то время как SML и Scheme – нет. Однако, существуют некоторые различия во мнениях о точной технической мотивации для такого разбиения. Одно из определений, которое было предложено, звучит следующим образом:
Термин «чисто функциональный» часто используется для описания языков, которые производят все вычисления посредством применения функций, в противоположность к языкам, таким как SML и Scheme, которые преимущественно функциональны, но допускают «побочные эффекты» (эффекты, вызванные вычислением, которые сохраняются после того, как вычисление закончено ) .
Иногда термин «чисто функциональный» используют в более широком смысле, подразумевая языки, которые могут включать вычислительные эффекты, но без изменения понятия «функция» ( само собой, сохраняя важнейшие свойства функций ). Типично, вычисление выражений может получить «задание», которое затем выполняется отдельно, вызывая побочные эффекты. Фазы вычисления и выполнения разделены таким образом, что фаза вычисления не подрывает стандартные свойства выражений и функций. Механизм ввода/вывода на Haskell’е построен именно таким образом.
Дополнительная литература:
• "What is a purely functional language", Amr Sabry, Journal of Functional Programming, 8(1):1-22, Cambridge University Press, January 1998.
3.2. Каррирование
Что такое каррирование и откуда оно пришло?
Каррирование берет свое начало из математического исследования функций. В 1893 году Фреге (Frege) заметил, что такого приема достаточно, чтобы ограничиться функциями одного аргумента. Например, для любой функции двух аргументов f(x,y) существует однопараметрическая функция f' такая, что f'(x) – это функция, которая может быть применена к y, чтобы получилось (f'(x)(y)) = f(x,y). Это соответствует хорошо известному факту, что множества (AxB -> C) и (A -> (B -> C)) изоморфны, где x – это декартово произведение, и «->» — это функциональное пространство (is function space). В функциональном программировании применение функции обозначается записью в ряд и считается лево-ассоциативным так, что равенство выше становиться f' x y = f(x,y).
По-видимому, Фреге не стал развивать идею далее. Она была независимо переоткрыта Шёнфинкелем (Schoenfinkel), вместе с результатом, что все функции, имеющие отношение к структуре функций, могут быть построены из двух базисных элементов, K и S. Спустя десятилетие эта мысль породила комбинаторную логику Хаскелла Карри, в честь которого и появился термин «каррирование». Функция f' в примере выше называется каррированной формой функции f. С точки зрения функционального программирования каррирование может быть описано функцией:
curry : ((a,b) -> c) -> (a -> b -> c)
Обратная операция, очевидно, будет декаррирование:
uncurry : (a -> b -> c) -> ((a,b) -> c)
Дополнительная литература:
• "Highlights of the history of the lambda-calculus", J. Barkley Rosser, ACM Lisp and Functional Programming, 1982.
• "Ueber die Bausteine der mathematischen Logik", Moses Sch\"onfinkel, Mathematische Annalen, 92, 1924. An English translation, "On the building blocks of mathematical logic", appears in "From Frege to G\"odel", Jean van Heijenoort, Harvard University Press, Cambridge, 1967.
• "Combinatory logic", Haskell B. Curry and Robert Feys, North-Holland, 1958. This work also contains many references to earlier work by Curry, Church, and others.
3.3. Монады
Что такое монады и для чего они нужны?
Концепция монад пришла из теории категорий, их полное описание можно найти в любом стандартном учебнике по этому предмету. Самое интересное в монадах, касаемо функционального программирования – это результаты недавних исследований, показывающие, как монады могут быть использованы для описания всех возможностей языка программирования ( например, ввод/вывод, изменение состояния, возобновления и исключения) в чисто функциональном языке таком, как Haskell:
• "Comprehending monads", Philip Wadler, Mathematical Structures in Computer Science, Special issue of selected papers from 6th Conference on Lisp and Functional Programming, 1992. В электронном виде:
http://www.cs.bell-labs.com/~wadler/topics/monads.html#monads
• "The essence of functional programming", Philip Wadler, Invited talk, 19th Symposium on Principles of Programming Languages, ACM Press, Albuquerque, January 1992. В электронном виде:
http://www.cs.bell-labs.com/~wadler/topics/monads.html#essence
• "Imperative functional programming", Simon Peyton Jones and Philip Wadler, 20th Symposium on Principles of Programming Languages, ACM Press, Charlotte, North Carolina, January 1993. В электронном виде:
http://www.cs.bell-labs.com/~wadler/topics/monads.html#imperative
• "How to declare an imperative", Philip Wadler, ACM Computing Surveys, to appear. В электронном виде:
http://www.cs.bell-labs.com/~wadler/topics/monads.html#monadsdeclare
3.4. Парсеры (синтаксические анализаторы)
Как мне написать парсер на функциональном языке?
Парсер – это программа, которая преобразует список введенных символов в значения подходящего типа. Простым примером может быть функция, которая находит целое из строки цифр. Более сложным примером служит трансляция программы, написанной в некотором определенном синтаксе, в подходящий абстрактный, как первый этап компиляции или интерпретации. Существует два общепринятых способа написания парсера на функциональном языке:
• Использовать генератор парсеров. Некоторые функциональные языки имеют набор вспомогательных инструментов для автоматической генерации парсеров по заданной грамматике. См.:
o Happy: генератор парсеров для Haskell и Gofer, аналогичный `yacc' для C. Доступен на:
http://www.dcs.gla.ac.uk/fp/software/happy/.
o Ratatosk: генератор парсеров и сканеров для Gofer. Доступен на:
Host: ftp.diku.dk;
Directory: /pub/diku/dists.
o ML-Yacc и ML-Lex: LALR – генератор парсеров и генератор лексических анализаторов для Standard ML. Включен в SML/NJ, доступен на:
Host: ftp.research.bell-labs.com;
Directory: /dist/smlnj.
• Использовать комбинаторный разбор. Парсеры представляются функциями и комбинируются в небольшие наборы, составляя парсер, который наиболее походит на грамматику заданного языка. Парсеры, написанные таким образом могут использовать перебор с возвратами. См.:
o "How to replace failure with a list of successes", Philip Wadler, FPCA '85, Springer Verlag LNCS 201, 1985.
o "Higher-order functions for parsing", Graham Hutton, Journal of Functional Programming, Volume 2, Number 3, July 1992. Доступен на:
http://www.cs.nott.ac.uk/~gmh/bib.html#parsing.
3.5. Строгость
Что означает, когда говорят про функциональный язык «строгий» или «нестрогий»?
Вот одно из (практических) объяснений этого различия:
• В строгом языке аргументы функции всегда вычисляются перед тем как она вызвана. В результате, если вычисление выражения exp не завершилось соответствующим образом (например, произошла ошибка во время выполнения или вычисление вошло в бесконечный цикл), тогда и не завершиться соответствующе выражение f(exp). ML и Scheme – этому пример.
• В нестрогих языках, аргументы функций не вычисляются, пока ни потребуются их значения. Например, вычисление выражения f(exp) может завершиться как положено, даже если вычисление exp – нет, если значение параметра нигде не используется в теле f. Miranda и Haskell – примеры такого подхода.
Существует много споров в функциональном программировании об относительных достоинствах строгих и нестрогих языков. Возможно, однако, и смесь этих двух подходов, например, в некоторых версиях функционального языка Hope.
3.6. Производительность
Какова производительность функциональных программ?
В некоторых кругах, программы, написанные на функциональных языках, заработали репутацию медленных. Частично, за это ответственен высокий уровень абстракции, какой присущ таким программам, частично – такие мощные средства, как функции высших порядков (функционалы), автоматическое управление памятью и т.д. Конечно, производительность интерпретаторов и компиляторов для функциональных языков улучшается в свете новых технологических разработок.
Вот подборка ссылок для дальнейшего чтения:
• Более 25 реализаций различных функциональных языков были сравнены на программе «Pseudoknot» — приложение из молекулярной биологии, интенсивно использующее операции с плавающей запятой. См:
o "Benchmarking implementations of functional languages with 'Pseudoknot', a float-intensive benchmark", Pieter H. Hartel et al, Journal of Functional Programming, 6(4):621-655, July 1996. Доступно на:
ftp://ftp.fwi.uva.nl/pub/computer-systems/functional/reports/.
• Ниже статьи сравнивающие пять реализаций ленивых функциональных языков:
o "Benchmarking implementations of lazy functional languages", P.H. Hartel and K.G. Langendoen, FPCA 93, ACM, pp 341-349. Доступны на:
Host: ftp.fwi.uva.nl;
Directory: pub/functional/reports.
• Эксперименты на сильно оптимизированном компиляторе для Sisal, строгом функциональном языке, показали, что функциональные программы могут быть быстрее, чем Фортран. См.:
o "Retire FORTRAN? A debate rekindled", D.C. Cann, Communications of the ACM, 35(8), pp. 81-89, August 1992.
• Материалы работы конференции 1995 года по высокопроизводительному функциональному вычислению (High Performance Functional Computing (HPFC)) доступны на:
ftp://sisal.llnl.gov/pub/hpfc/index.html.
3.7. Применение
Что я могу найти о применении функциональных языков?
Вот небольшая подборка:
• "Special issue on state-of-the-art applications of pure functional programming languages", edited by Pieter Hartel and Rinus Plasmeijer, Journal of Functional Programming, Volume 5, Number 3, July 1995.
• "Applications of functional programming", edited by Colin Runciman and David Wakeling, UCL Press, 1995. ISBN 1-85728-377-5.
• Электронный список реальных приложений функционального программирования, который включает программы, написанные на нескольких различных функциональных языках. Главным критерием «реальности» приложения было то, что программа была написана для некоторой задачи, а не ради эксперимента по функциональному программированию.
Более детально здесь:
http://www.cs.bell-labs.com/~wadler/realworld/.
)
