К сожалению, создается впечатление, что идея о создании отдельного раздела посвященного ФЯ постепенно заглохла. Предлагаю заинтересованным лицам все-таки собраться и написать общими силами хотя бы статью-введение. Поскольку не совсем ясно, о чем стоит писать, а о чем нет, было бы неплохо, если бы незнакомые с ФП, но заинтересованные в его изучении люди, запостили здесь свои вопросы, на которые знакомые с ФП люди написали бы им ответы, объяснили трудные для понимания аспекты ФП и т.п. В общем, как писал VladD2 в соседней ветке, предлагается совместно создать документ, который действительно был бы полезен программистам не знакомым с функциональным стилем, чтобы изучив его, они легко могли бы составить впечатление о возможностях ФЯ, отличиях их от ИЯ, основных приемах программирования под ними и т.д.
Для начала со своей стороны я готов дать информацию по Haskell'ю и общим вопросам, связанным с ФП, а пока пощу здесь свою расшифровку некоторых базовых терминов часто употребляющихся по отношению к ФЯ.
Чистые ФЯ
Когда говорят о чистых ФЯ, обычно имеют ввиду языки, вычисления в которых осуществляются исключительно
при помощи композиции функции и где отсутствуют какие-либо сторонние эффекты. Данное
определение через чур строгое и, собственно говоря, под него не подходит ни один реальный
язык программирования. Т.е. ни один ЯП, который стоило бы использовать на практике.
Тем не менее полностью чистые ФЯП существуют. В качестве примера можно привести лямбда
исчисление.
Однако, имеет смысл несколько ослабить требование отсутствия сторонних эффектов, ибо ни
одна программа, которая принимает данные от пользователя и выдает ему в ответ результат, не
может без них обойтись. Если сторонние эффекты в ЯП "практически" отсутствуют, то ФЯ
называется чистым. К таким языкам относят, например, Haskell, где императивный ввод-вывод
осуществляется с помощью специального механизма монад, которые изолируют чистую
функциональную часть программы от нечистой императивной. В тоже время SML и OCaml
не являются чистыми функциональными языками, поскольку допускают использование императивных
конструкций типа операций присваивания и исключений.
Вызов по значению и вызов по имени
При вызове функции у нас есть два способа передать ей параметры. Первый способ заключается в
том, чтобы сначала вычислить параметры и потом передать в функцию вычисленные значения. А второй
в том, чтобы ничего не вычисляя передать в функцию выражения, по которым можно вычислить
ее параметры. Если функции понадобятся значения этих выражений, она их вычислит по мере
необходимости. Первый способ вызова называется вызовом по значению, поскольку в функцию передается
конкретное значение — целое, строка, список и т.д. Второй способ называется вызовом по имени,
поскольку в функцию передается невычисленное выражение. Вызов по имени в целом более выгоден,
так как экономится время необходимое для вычисления ненужных параметров, но он работает только
в чистых ФЯ, где нет сторонних эффектов. Другой особенностью вызова по имени является устойчивость
к ошибкам. Даже если вычисление одного из параметров приводит к ошибке, выражение в целом может быть
вычисленно, если в нем не задействовано значение этого параметра. В императивных языках есть функции,
которые симулируют вызов по имени. Например логическое "И" — && в С не вычисляет свой второй аргумент,
если первый равен 0. Эта особенность широко используется во многих программах, в том числе и в ядре Linux.
Языки поддерживающие вызов по значению называются строгими, те, что поддерживают вызов по имени,
называются нестрогими. Haskell нестрогий язык, а SML и OCaml строгие.
Строгая типизация
Не все функциональные языки обладают системой типов. Например, Lisp является бестиповым языком. Однако,
здесь речь пойдет только о языках со строгой типизацией. В таких языках каждая константа, каждое выражение
или функция имеют свой тип. Не допускается смешивание разных типов, даже если один из них можно легко
преобразовать в другой. Например, если у функции есть вещественный параметр, ей нельзя передать целое число
как в С++, сначала его нужно явно преобразовать в вещественное. Не допускается обестипливание как,
например, в C#. Невозможно преобразовать целое число к некоторому общему типу object. Эти строгости
компенсируются развитостью системы типов, легкостью работы со сложными типами и полиморфизмом. Легкость
работы обеспечивается сравнением с образцом (объяснено в другом разделе), а другие две темы мы обсудим чуть
ниже. При компиляции программы компилятор проверяет на соответствие все типы в программе и при несовпадении
типов выдает ошибку. В дальнейшем при выполнении программы уже не могут возникнуть исключительные ситуации
связанные с ошибочным типом, как это часто происходит в С++ или даже C#. Вам придется поверить мне на слово,
однако, я (и не только я) утверждаю, что благодаря строгой типизации и рвению компилятора в области
выявления связанных с этим ошибок, удается значительно сократить количество проблем, возникающих при
выполнении программы.
Ранее я упомянул, что строгость системы типов компенсируется ее развитостью. В самом деле, ФЯ позволяют
программисту малыми силами определять сложные типы данных типа списков, деревьев и т.п. Основным типом
ФЯ можно назвать список — создание списков и работа с ними упрощены до безобразия. Например, чтобы создать
список вам достаточно написать
[a,b,c]
где a,b и c — это элементы списка. Хотите создать список в списке? Пожалуйста
[[a,b,c],[],[n,r]]
Для работы со списками существует огромное количество функций, в том числе специальная функция помещения
элемента в список, которая обычно обозначается : или ::
1:[2,3]
Вторым важным конструктором новых типов является кортеж (tuple). Это всего лишь набор разнотипных значений
вроде
(1,"str",'a')
Кортежы используются для возвращения из функций нескольких значений, определения сложных типов типа деревьев
или списков и т.п.
Многие ФЯ допускают использование структур, которые по сути своей являются кортежами с именоваными полями.
Допускается определение древовидных или циклических структур данных. Например, определим тип для выражения
в языке программирования
data Expr = Var String | Integer Int | Str String | Assign Var Expr | Func Var [Expr]
Var, Integer, Str, Func и Assign — это так называемые конструкторы типа. С их помощью можно создать
значение типа Expr
Assign (Var "my_var") (Func (Var "my_func") [(Str "str"),(Integer 10)])
Возможности впечатляют, однако, это еще не все. Система типов в ФЯ полиморфна. Мы можем определять как
полиморфные функции так и полиморфные типы данных и при этом не теряется строгость типизации! Как
определить можно ли в качестве параметра функции типа A подставить значение или выражение типа B? Нужно
просто посмотреть, можно ли свести тип B к типу A. В С++ аналогичная ситуация возникает, если от класса
A унаследованы классы B и C. B можно свести к A, но нельзя свести к C. В ФЯ производится аналогичная
процедура проверки, только ввиду всеобщего полиморфизма она намного сложнее. Например функция
my_func x = [x]
имеет тип
a->[a]
т.е. преобразует значение типа a в список значений типа a.
my_func2 x = (Integer 10):[x]
имеет тип
Expr -> [Expr]
т.е. ee тип является частным случаем типа первой функции.
my_func my_func2
my_func:(my_func my_func2)
типы этих выражений
[Expr->[Expr]]
[Expr->[Expr]]
Заметьте мы смогли положить полиморфную функцию my_func в список специализированных функций. Обратное
было бы невозможно.
Данные примеры довольно просты, в реальных программах типы выражений и функций могут иметь весьма
значительный размер. Тот, кто видел шаблоны в С++ поймет о чем я говорю. Слава богу, в случае с ФЯ
программист не обязан переписывать километровые объявления типов раз за разом. Всю эту тяжелую работу
берет на себя компилятор. Более того, он выводит для каждой функции максимально общий (самый
полиморфный) из всех возможных типов. В принципе, вы можете вообще забыть о них и даже не знать точно
какой тип имеет ваша любимая функция. Если вы сомневаетесь в возможностях компилятора, то смею вас заверить,
что за всем этим стоит особая теория (что в случае ФЯ неудивительно), где строго доказывается возможность
вывода самого общего типа в любой ситуации, где это вообще возможно. Тем не
менее рекомендуется указывать типы по крайней мере у основных функций с тем,
чтобы повысить читаемость программы и облегчить работу компилятору. Иногда, в
сложных случаях, явное указание типа становится необходимостью, поэтому важно
знать, как выглядят объявления типов и уметь указывать из самому.
Остается добавить, что отдельные ФЯ расширяют стандартную систему типов разными способами. Например, в
OCaml добавлены классы, а в Haskell'e существуют классы типов, которые чем-то похожи на интерфейсы в ООП
языках.
Сравнение с образцом (pattern matching)
Поскольку в ФЯ широко используются сложные типы данных, для эффективной работы с ними существуют
мощные инструменты, а именно сравнение с образцом. Суть данного метода заключается в том, что мы
указываем некоторый каркас предполагаемого значения (образец), а программа пытается подогнать под этот
образец полученное значение. Например в этом примере
case list of
head:tail -> ...
| [] -> ...
мы пытаемся сравнить список list с двумя образцами head:tail и []. Если список не пустой, то сработает
первый образец, при этом head будет равен первому элементу списка, а в tail будет сохранен его хвост.
Если же список пустой, то сработает второй образец. Сложность образцов неограничена, вы можете использовать
для их создания все методы, с помощью которых можно создавать данные. Например в данном примере
case expr of
Assign (Var my_var) (Func my_func [(Str "str"),(Integer 10)]) -> ...
если expr имеет указанную структуру, то my_var будет равен имени переменной, my_func будет равен
Var some_string. Заметим, что в образце можно указывать не только переменные, которые в случае
успешного сравнения будут связаны с частями сложного типа, но и константы.
Карринг
Одна из первых деталей, которая бросается в глаза человеку, привыкшему к императивным языкам
программирования, когда он видит функциональную программу, это отсутствие скобок вокруг параметров при
объявлении функций:
my_func a b c = ...
Это так называемая карринговая форма записи, которая получила свое название от имени Карри, который
первый указал на преимущества, которые она дает в ФЯП. В самом деле, поскольку в ФЯП функции и данные
равноправны, при такой записи параметров появляется ценная возможность использовать частичное определение
функций. Рассмотрим, например, функцию сложения двух чисел
add a b = a + b
Имея эту функцию мы можем создать новые функции типа
inc x = add 1 x
add10 x = add 10 x
первая из которых увеличивает свой аргумент на 1, а вторая на 10. Разница с обычным вызовом более
общей подфункции с некоторыми фиксированными аргументами заключается в том, что функция add 1 будет
частично вычислена один раз и при дальнейших вызовах перевычислятся не будет. В данном простом примере
это врядли приведет к существенному сокращению вычислений, однако, в более сложных случаях, выгода может
быть значительной. Дополнительно устраняется необходимость отдельного объявления специализированных
функций, что было бы неизбежно в случае обычной формы записи.
Функции высшего порядка (higher order functions)
Это функции, которые могут принимать в качестве аргумента и возвращать другие функции. Такие функции
повсеместно используются в ФЯП. Одной из классических функций такого рода является функция map, которая
принимает в качестве аргументов список элементов и функцию, которая преобразует эти элементы и возвращает
список с преобразоваными элементами. Вот как выглядит ее объявление
map f (head:tail) = (f head):(map f tail)
map f [] = []
Если мы объявим f как
f x = x*2
И применим map к f и списку [1,2,3], то получим список [2,4,6].
Ленивые вычисления
Как уже было сказано ранее, ФЯ делятся на строгие и нестрогие. Нестрогие языки
еше называют ленивыми. Это значит, что реальные вычисления в них откладываются
до того момента, когда они действительно становятся необходимы. На вопрос о том
насколько полезны ленивые вычисления нельзя дать однозначного ответа. В одних
случаях ленивость позволяет уменьшить количество вычислений и использовать
ленивые структуры данных типа бесконечных списков, а в других она становится
проблемой, когда память забивается недовычисленными выражениями, о которых
пока неизвестно, нужно их вычислять или нет. Такая ситуация возникает,
например, в LL(inf) парсере — парсере с произвольным заглядыванием вперед.
Для борьбы с лишней ленивостью применяются различные средства — форсирование
вычислений, специальные методы программирования типа CPS, строгие поля у типов
данных и т.п. Программист имеет возможность найти слабые места в своей
программе с помощью специальных инструментов и устранить их убрав, например,
ленивые вычисления там, где они не нужны.
16.10.04 22:19: Перенесено модератором из 'Философия программирования' — AndrewVK
Здравствуйте, Quintanar, Вы писали:
Q>Чистые ФЯ
Чистый ФЯ — язык в котором
единственным результатом работы любой функции является возвращяемое значение.То есть максимально близко к математическому аналогу — функция это отображение множества входных
параметров в выходной.Результат функции не зависит от того
когда эта фунция выполняется.Более того различные части одной функции могут быть вычеслены в разное время например result=f1(f2(A,B),f3(C,D))
Может быть вычислена так
A->C->D->B->f2->f3->f1
Это обстоятельсто усложняет отладку программ

Отсюда следут отсутствие глобальных переменных.Так как не одна ф-ия не может их изменить и не может от них зависить.С этим же связано отсутствие операции
изменения переменной.
Q>Вызов по имени в целом более выгоден,
Спорно сам пишешь ниже.Выгодно когда то что нужно вычислить достатчно мало (занимает мало памяти для описания)
а вычисления достаточно долгие например 1000000000000! и не выгодно когда вычисленный результат во много раз меньше чем исходный.Например размер дерева или списка — проще сразу получить размер и удалить саму структуру(если она не используется далее) чем хранить ее до последнего
Q>Языки поддерживающие вызов по значению называются строгими, те, что поддерживают вызов по имени,
Q>называются нестрогими. Haskell нестрогий язык, а SML и OCaml строгие.
И Haskell и Ocaml поддерживают оба способа.Просто
по умолчанию поведение Haskell нестрогое а OCaml строгое.
Q> Основным типом ФЯ можно назвать список
Основным типом ФЯ Haskell является алгебраический тип данных.Близкий аналог в ИЯ это enum(C).
Списки и кортежи является частным случаем.
2.4 Built-in Types Are Not Special
Earlier we introduced several "built-in" types such as lists, tuples, integers, and characters. We have also shown how new user-defined types can be defined. Aside from special syntax, are the built-in types in any way more special than the user-defined ones? The answer is no. The special syntax is for convenience and for consistency with historical convention, but has no semantic consequences.
We can emphasize this point by considering what the type declarations would look like for these built-in types if in fact we were allowed to use the special syntax in defining them. For example, the Char type might be written as:
data Char = 'a' | 'b' | 'c' | ... -- This is not valid
| 'A' | 'B' | 'C' | ... -- Haskell code!
| '1' | '2' | '3' | ...
...
These constructor names are not syntactically valid; to fix them we would have to write something like:
data Char = Ca | Cb | Cc | ...
| CA | CB | CC | ...
| C1 | C2 | C3 | ...
...
Even though these constructors are more concise, they are quite unconventional for representing characters.
In any case, writing "pseudo-Haskell" code in this way helps us to see through the special syntax. We see now that Char is just an enumerated type consisting of a large number of nullary constructors. Thinking of Char in this way makes it clear that we can pattern-match against characters in function definitions, just as we would expect to be able to do so for any of a type's constructors.
[This example also demonstrates the use of comments in Haskell; the characters -- and all subsequent characters to the end of the line are ignored. Haskell also permits nested comments which have the form {-...-} and can appear anywhere (§2.2).]
Similarly, we could define Int (fixed precision integers) and Integer by:
data Int = -65532 | ... | -1 | 0 | 1 | ... | 65532 -- more pseudo-code
data Integer = ... -2 | -1 | 0 | 1 | 2 ...
where -65532 and 65532, say, are the maximum and minimum fixed precision integers for a given implementation. Int is a much larger enumeration than Char, but it's still finite! In contrast, the pseudo-code for Integer is intended to convey an infinite enumeration.
Tuples are also easy to define playing this game:
data (a,b) = (a,b) -- more pseudo-code
data (a,b,c) = (a,b,c)
data (a,b,c,d) = (a,b,c,d)
. .
. .
. .
Each declaration above defines a tuple type of a particular length, with (...) playing a role in both the expression syntax (as data constructor) and type-expression syntax (as type constructor). The vertical dots after the last declaration are intended to convey an infinite number of such declarations, reflecting the fact that tuples of all lengths are allowed in Haskell.
Lists are also easily handled, and more interestingly, they are recursive:
data [a] = [] | a : [a] -- more pseudo-code
We can now see clearly what we described about lists earlier: [] is the empty list, and : is the infix list constructor; thus [1,2,3] must be equivalent to the list 1:2:3:[]. (: is right associative.) The type of [] is [a], and the type of : is a->[a]->[a].
[The way ":" is defined here is actually legal syntax---infix constructors are permitted in data declarations, and are distinguished from infix operators (for pattern-matching purposes) by the fact that they must begin with a ":" (a property trivially satisfied by ":").]
At this point the reader should note carefully the differences between tuples and lists, which the above definitions make abundantly clear. In particular, note the recursive nature of the list type whose elements are homogeneous and of arbitrary length, and the non-recursive nature of a (particular) tuple type whose elements are heterogeneous and of fixed length. The typing rules for tuples and lists should now also be clear:
For (e1,e2,...,en), n>=2, if ti is the type of ei, then the type of the tuple is (t1,t2,...,tn).
For [e1,e2,...,en], n>=0, each ei must have the same type t, and the type of the list is [t].
(
отсюда)
Или по другому список
data List a = Only a | Pair a (List a)
кортеж
data C1 a = C1 a
data C2 a b = C2 a b
...
Списки — это основной тип данных для Lisp
Q>Карринг
Предположим есть функция — сложение.
Можно рассматривать ее как функцию от 2 аргументов int и возвращающюю int
А можно как функцию 1-ого числа x возвращающюю другую функцию 1-ого аргумента f ,такую что f y =x+y — это карринг или частичное применение функции