Особенности ФП

[_Ivana]

Несколько раз набирал длинные тексты стартового сообщения, но каждый раз стирал. И подумал, что можно поступить проще: с чего-то начать, пусть с одной фразы -> а дальше если тема интересна, то она разовьется. А иначе (в Haskell нельзя if без else) справедливо заглохнет. А дело, собственно не в конкретном языке - с того же Haskell для многих платформ его компилятор сначала предварительно транслирует код на язык С, а потом сишный компилятор уже делает исполняемый код. И не в конкретной целевой платформе - Lisp код может выполняться на специальных аппаратно реализованных Lisp-машинах или на обычных RISC-процессорах, Clojure - на той же виртуальной Java машине, что и императивный Java код и т.п. И дело не в памяти, не в распараллеливании на несколько процессоров и прочем.
А дело в отдельной парадигме. В том наборе абстракций, которыми оперирует программист, создавая код. Кто не пробовал (я сам всего несколько дней пробую), представьте, что у вас нет ни переменных, ни циклов, ни переходов по меткам, ни хранимого изменяемого контекста или состояния чего-либо (в чистом случае), ни процедур, ни четко определенной последовательности выполнения инструкций, и если написано

Используется синтаксис C

a = a + 1

то это впадет в бесконечную рекурсию, причем не сразу, а только если где-то потребуется это значение.
ЗЫ я еще совсем функционально не подкован, хотя тоже могу говорить слова про оптимизацию хвостовой рекурсии в цикл, чистоту и прозрачность по ссылкам, энергичность/ленивость, вот про моноид в категории эндофункторов пока не могу, но скоро думаю это исправить. Однако, тетрис на F# (мультипарадигмальный язык из семейства .NET) я все-же написал в функциональном стиле, хотя и с применением пары ссылочных констант для хранения состояния и грязных функций ввода-вывода.
Если кто желает форсировать дальше выполнение задекларированных в этом посте направлений, или также задекларировать свои параллельно, то будет интересно почитать, даже без выравнивания.

[Sonic86]

Ага, я тоже хочу что-нибудь сказать, чтоб понять (я примерно треть SICP прочел).
Хочется хотя бы собрать в кучу все фишки функционального программирования, поскольку их довольно много.
Я допишу из головы все, что вспомню, а потом доредактирую пост.
0. Куча необычного матана нахаляву.
1. Чистые функции + кэширование значений в качестве подарка, что влечет почти ненужность тривиальной оптимизации.
2. Высшие функции и структуры данных: возможность получить функцию как аргумент, вернуть как значение, встроить функцию в структуру данных. (штуки типа (inc inc) удивительны)
3. Лямбды. Возможность описать и заюзать функцию без отдельного наименования.
4. Каррирование (еще не знаю толком, что оно дает).
5. Универсальная структура данных "пара". Возможность сконструировать из нее что угодно.
6. Многоместные функции (f(.))
7. Ленивость. Как следствие, возможность объявлять и юзать бесконечные объекты (бесконечные списки в Haskell).
8. Возможность объявить довольно абстрактные функции у которых аргументы - это произвольные типы из какого-то класса (например, проверка на равенство, вернуть $k$-й элемент пары и т.п.)
Чего я еще забыл или где наврал?
Самый простой вывод: ФП - это не просто функциональное программирование - это большое количество взаимосвязанных и удобных плюшек, которых обычно не наблюдается.

Кстати, я не понимаю, почему в ФП нет состояния у программы? Есть же! Она же как-то исполняется.

[_Ivana]

Sonic86 в сообщении #909321 писал(а):

Каррирование (еще не знаю толком, что оно дает)

Есть утверждения, что каррирование и частичное применение это разные вещи, но я пока не постиг сути отличий. И в моем представлении каррирование просто дает возможность применять "промежуточные" функции. Например, функция двух аргументов

Используется синтаксис C

fun x y = x + y

- конструкция

Используется синтаксис C

fun 5

даст функцию одной переменной, которая будет прибавлять к ней 5. Ее можно как-то обозвать отдельно и использовать в дальнейшем. Например, квадратный корень, как частный случай степени, и т.п.

[rockclimber]

Я, честно говоря, прочитав "тот самый" топик в разделе "работа форума", уже и сам хотел было создать такой топик про ФП.
Но не успел.
Все мои познания в ФП определяются только статьей в русскоязычной Википедии, ну и плюс пара-тройка дискуссий на форумах. Ах да, еще год назад прочитал пару глав в учебнике по какому-то из функциональных языков, но сейчас даже не помню, по какому
Во-первых, имхо, исходное сообщение темы не содержит четко сформулированного вопроса, в связи с чем есть опасения, что модераторы тему закроют. Мне бы не хотелось, поэтому я быстренько задам свои вопросы
Первый - а в чем, собственно, вопрос? Вроде основные отличия ФП от императивного описаны, если не в википедии, то где-нибудь еще. Или статья в википедии сильно неполна (хотя все источники, которые я читал, пишут примерно одно и то же)?
Второй вопрос - а где на практике применяются функциональные языки? Мне почему-то кажется, что у них сильно ограниченная область применения будет.

Sonic86 в сообщении #909321 писал(а):

2. Высшие функции и структуры данных: возможность получить функцию как аргумент, вернуть как значение, встроить функцию в структуру данных

Давно мучает вопрос - что здесь имеется ввиду? В Delphi и freepascal тоже можно получить функцию как аргумент (да и в С/С++, а уж какие штуки в PL/SQL можно вытворять, хотя это и оффтоп, - вы бы знали). В ФП тоже самое или нет?
"Встроить функцию в структуру данных" - это как ООП классы или что-то другое?

[_Ivana]

Sonic86 в сообщении #909321 писал(а):

почему в ФП нет состояния у программы? Есть же! Она же как-то исполняется

Как она "на самом деле" исполняется - за кадром. Я же писал про Lisp машины. Один и тот же код на разных платформах скомпилируется под инструкции данного процессора/платформы. Главное, что "снаружи" состояния нет. А на некоторых платформах может и внутри тоже нет. А исполняется она очень просто - вся программа это одна единственная функция, которая при вычислении вызывает кучу вложенных функций, и т.д., при этом независимые блоки могут вычисляться параллельно, а начальные узлы - "константные функции" - конкретные значения.

rockclimber, с позиции дилетанта, позволю себе сказать, что там все - функция. Одного аргумента, причем.

Используется синтаксис C

a = 5

это функция, возвращающая числовой тип. Вычисляющаяся как "просто взять 5".

[arseniiv]

Кстати, вот лисп мой знакомый (пишет на Comon Lisp и радуется) считает императивщиной. В принципе, ясно, почему. Остальное пока не читал, но обещаю.

-- Пт сен 19, 2014 02:58:28 --

_Ivana в сообщении #909323 писал(а):

Есть утверждения, что каррирование и частичное применение это разные вещи, но я пока не постиг сути отличий.

Каррирование — это, как я понимаю, просто факт существования изоморфизма между $A\to B\to C$ и $A\times B\to C$ (и аналогичных). Частичное применение — это вон та прехорошая синтаксическая штуковина. Без частичного применения пришлось бы заново абстрагироваться по всем переменным для применения всего одной. Но возможны альтернативные и сосуществующие в одном языке конструкции. Каррированные функции использовать при наличии частичного применения намного удобнее, чем без него, а для их написания, в принципе, используется отдельный кусок грамматики (хотя и выглядит это в итоге в языках обычно похоже, ну и правильно).

[_Ivana]

(Оффтоп)

arseniiv, машинально потянулся мышкой к кнопке "плюсануть", и обнаружил, что тут ее так же нет, как переменных и состояния в ФП :)

[arseniiv]

_Ivana в сообщении #909314 писал(а):

то это впадет в бесконечную рекурсию, причем не сразу, а только если где-то потребуется это значение

Замечу, что без наличия ленивых вычислений это неверно (при первом же вызове, даже если не нужно значение, будет бадабум), а разные называемые функциональными языки к лени подходят по-разному: где по-умолчанию включена, где выключена, где можно включить/выключить и где нельзя, и как эти вещи выглядят. (Читаю дальше…)

[_Ivana]

arseniiv в сообщении #909339 писал(а):

Замечу

Я не стал это отмечать в первом посте, чтобы он хоть на страницу влез :) Но уточняющую фразу написал с тем расчетом, что под "только если где-то потребуется" в энергичных языках понимается одно, а в ленивых - другое. С возможностью явного ручного форсирования опять же, где эта возможность есть.

[arseniiv]

Sonic86 в сообщении #909321 писал(а):

1. Чистые функции + кэширование значений в качестве подарка, что влечет почти ненужность тривиальной оптимизации.

Чистота помогает ещё и в нетривиальной — пишутся правила, по которым компилятор может заменять одни куски на другие (хотя корректность правил у, например, компилятора хаскеля GHC, лежит на писателе — компилятор их не проверяет).

Sonic86 в сообщении #909321 писал(а):

взаимосвязанных и удобных плюшек, которых обычно не наблюдается

Ничего, языки тянутся к ним всё сильнее.

Sonic86 в сообщении #909321 писал(а):

Кстати, я не понимаю, почему в ФП нет состояния у программы? Есть же! Она же как-то исполняется.

Во время исполнения есть, а в коде доступа нет. С другой стороны, do-нотация хаскеля даёт «иллюзию» императивного кода и состояний, хотя на деле эта нотация просто чуть более наглядным образом строит значение какой-то монады. И даже значения типов IO a выполнятся только где-то там вне main, куда она какое-то такое значение передаст, и выполнится, конечно, только оно.

_Ivana в сообщении #909331 писал(а):

позволю себе сказать, что там все - функция. Одного аргумента, причем

Или нуля! Ну и можно вообразить себе ф. язык без карринга. А, чего воображать — те же лиспы.

rockclimber в сообщении #909328 писал(а):

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

Какая-то фирма англоязычная, как-то связанная с самолётами, попадалась несколько месяцев назад, гордо говорящая, что они пишут на CL, и потому их код надёжен (потому что они ещё и пишут его аккуратно, конечно, но язык помогает).

-- Пт сен 19, 2014 03:28:01 --

Но вот когда придёт Xaositect, будет ещё лучше. А то у меня какие-то пространные слова; когда пишу на хаскеле или читаю про него, как-то не думаю о том чтобы делать заметки на будущее и сохранять интересные или проясняющие, или просто на конкретику, ссылки. Совершенно не знаю монаду ST или как делать и правильно использовать многопоточность. Для реального применения это важно, и стоило бы об этом рассказать, думаю.

[_Ivana]

arseniiv в сообщении #909342 писал(а):

Или нуля! Ну и можно вообразить себе ф. язык без карринга. А, чего воображать — те же лиспы.

Не знаю, может отсутствие аргументов у функции все равно трактуется как существующий NULL аргумент - но это вопрос не принципиальный. А без карринга и частичного применения - запросто и без Лиспа, аргумент один, но являющийся кортежем произвольного числа произвольных типов - и в синтаксисе это и выглядит соответствующе

Используется синтаксис C

fun (a, d, c, d)

не помню, что в Haskell а что в F# разделяет элементы кортежа - "," или ";" но это не важно - аргумент все равно один.

[Pphantom]

rockclimber в сообщении #909328 писал(а):

а уж какие штуки в PL/SQL можно вытворять, хотя это и оффтоп, - вы бы знали). В ФП тоже самое или нет?

Так ведь SQL, вообще говоря, и является функциональным языком. Не тьюринг-полным, не универсальным, но все же...

[rockclimber]

Pphantom в сообщении #909345 писал(а):

rockclimber в сообщении #909328 писал(а):

а уж какие штуки в PL/SQL можно вытворять, хотя это и оффтоп, - вы бы знали). В ФП тоже самое или нет?

Так ведь SQL, вообще говоря, и является функциональным языком. Не тьюринг-полным, не универсальным, но все же...

Является ли SQL функциональным языком, имхо, большой вопрос - ведь это же язык запросов к данным, лежащим на устройстве хранения информации (разве данные в таблицах нельзя назвать "состоянием"?), плюс к тому же в конкретных реализациях много всего наворочено. Например, запросы могут работать сильно по-разному в зависимости от настроек сессии - от этого зависят форматы даты и чисел, как минимум.
А я писал именно про PL/SQL - это процедурное расширение языка SQL (императивный язык, брат паскаля в некотором смысле), использующееся в СУБД Oracle для написания логики, выполняющейся на сервере. Язык со своей спецификой и, как следствие, некоторыми оригинальными фишками.

[Mysterious Light]

Вроде бы, в этой теме спутываются понятия декларативного и функционального программирования.
ФП предполагает только использование предпочтительно чистых функций как объектов первого порядка. Даже манипуляции над списками, говоря придирчиво, уже не является «фишкой» ФП, будучи самостоятельным стилем спискового программирования. Сравните: в Хаскеле есть функции concatMap, filter, map и т.п., есть list comprehension, есть do-нотация, которые для списков обозначают в точности одно и то же. Почему же синтаксические структуры разные? Потому что они немного от разных стилей, которые и связаны, но и немного несовпадают.

Говорить, что в ФП всё равно работают с состоянием, только оно скрыто, всё равно, что говорить, что в ООП есть GOTO, только он скрытый. Напомню, что ни в Java, ни в C# нет оператора безусловного перехода.

[rockclimber]

Mysterious Light в сообщении #909451 писал(а):

Говорить, что в ФП всё равно работают с состоянием, только оно скрыто, всё равно, что говорить, что в ООП есть GOTO, только он скрытый. Напомню, что ни в Java, ни в C# нет оператора безусловного перехода.

Тоже спорный вопрос. Я где-то встречал мнение, что обработка исключений (блок try) - это и есть неявный GOTO.