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

[Mysterious Light]

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

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

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

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

Я более скажу: if, while, continue и break — самые настоящие условные (первые два) и безусловные (последние два) переходы. Но покуда эти переходы не позволяют, например, перескочить из одного метода в другой, или заскочить внутрь цикла из-вне, они являются неполноценными. А для эмуляции — да, они сгодятся, чтоб сыммитировать GOTO. Но ровно в том же смысле есть State Monad и IO в ФП для иммитации состояния.

Я обращаю внимание только на тот момент, что с появлением структурного программирования, а позже ООП, ФП и др., в среде программистов не принято говорить, что некий язык использует GOTO неявно. Говорят так: в этом языке есть явная конструкция GOTO или в нём нет её. Это ещё не значит, что Ваша мысль не правильна.
Говорить о неявных состояниях в ФП ровно настолько же корректно. Утверждать так и говорить, что в современном программировании GOTO не используется, есть типичный пример двойных стандартов. Или и то, и то, либо ни то и ни то одновременно.

[Pphantom]

Проще не быть пуристами и учитывать тот факт, что достаточно распространенных языков, реализующих одну и строго одну парадигму программирования, практически нет.

[Sonic86]

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

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

Покажите, пожалуйста, что имеется ввиду для Delphi, freepascal, C++.
В PL/SQL ничего подобного нет (а иначе - какой тип у аргументов, в который передаются функции?). В PL/SQL есть execute immediate от строки - когда строка интерпретируется как код и исполняется. А "передавать и возвращать функции в другие функции" сводится к передаче строк из одних функций в другие - тут все понятно.

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

"Встроить функцию в структуру данных" - это как ООП классы или что-то другое?

Это я могу объявить список из $n$ элементов, и запихать в него $n$ функций. Потом, например, пробежаться по списку и применить каждую функцию.

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

Во время исполнения есть, а в коде доступа нет.

понял

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

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

Эээ, что?! Это как? Вы имеете ввиду изоморфизм некоторой части функциональных языков? А где в SQL структуры данных?

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

Даже манипуляции над списками, говоря придирчиво, уже не является «фишкой» ФП, будучи самостоятельным стилем спискового программирования.

Да? Жаль, а я думал, что это тоже оно. А существует ли нефункциональный язык со структурой данных "пара" или "список"?

[rockclimber]

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

Покажите, пожалуйста, что имеется ввиду для Delphi, freepascal, C++.

Ну С/С++ я не знаю (хотя там все то же самое), напишу на паскале. Вообще, это то, что называется "функция обратного вызова" (callback function).

program abc;
type
  TFunc = function(a: integer): integer);  // тип - ссылка на адрес функции

  function Square(a: integer);
  begin
    Result:= a * a;
  end;
 
  function Cube(a: integer): integer;
  begin
    Result:= a * a * a;
  end;

  procedure Executor(x: integer; f: TFunc);
  begin
    writeln(f(x));  // здесь происходит вызов функции, адрес которой находится по адресу в переменной f
  end;

begin
  Executor(5, @Square);
  Executor(6, @Cube);
end;

Сейчас под рукой ничего нет, код этот я не запускал, но вроде он должен быть работоспособен.
Результат выполнения должен быть:

25
216

Так работают, в частности, API-функции windows, имена которых начинаются на Enum (или заканчиваются, не помню уже). В качестве одного из аргументов они принимают ссылку на вашу функцию и вызывают ее внутри себя энное количество раз. В Delphi и freepascal так реализованы события (это свойства классов процедурного типа).

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

В PL/SQL ничего подобного нет (а иначе - какой тип у аргументов, в который передаются функции?). В PL/SQL есть execute immediate от строки - когда строка интерпретируется как код и исполняется.

Да, я имел ввиду именно execute immediate. Это такой PL/SQL-ный револьвер для простреливания собственных ног. Там можно не только сымитировать функцию обратного вызова, но и DDL втихаря запихать, и много чего еще.

[_hum_]

По-моему, такие вопросы надо начинать с рассмотрения фундаментальных концептов программирования: модель вычисления, переменная vs именованная ячейка памяти, декларативный подход vs императивный, понятия обобщения по параметрам и специализации, стратегии вычисления выражений (аппликативная, нормальная), способы передачи аргументов функцию, статическое vs динамическое связывания и т.п.
Когда-то мне в этом плане (насколько многообразно программирование) "открыла глаза" книга P.Van Roy, S. Haridi. Concepts, Techniques, and Models of Computer Programming. Но и в ней все-таки не достаточно общий взгляд на такие вещи.

Вот когда-то сам пытался разобраться на примере лямбда-исчисления: "Базовые концепты computer science на примере λ-исчисления"

[Mysterious Light]

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

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

Даже манипуляции над списками, говоря придирчиво, уже не является «фишкой» ФП, будучи самостоятельным стилем спискового программирования.

Да? Жаль, а я думал, что это тоже оно. А существует ли нефункциональный язык со структурой данных "пара" или "список"?

Да, любой современный язык поддерживает пару (record/struct) и список, а прокаченный ОО-язык позволит программировать в списковом стиле. Например, можно написать некоторый код, используя Fluent Interface, Generics и прочее, после которого можно будет писать так:

new List([1,3,4,2,5,4,3]).tail().filter(new OddFilter()).sort(new StandardOrder()).excludeDuplicated();
// в значении
nub . sort . filter odd . tail $ [1,3,4,2,5,4,3]

Просто тут так и напрашивается передавать первым аргументом filter, map и прочих операторов именно функцию, а не объект, делегат или что-то другое. Поэтому стиль спискового программирования, как правило, соседствует с ФП.

Присоединяюсь к _hum_, эта книга интерсна для общего развития.

(Оффтоп)

Sonic86, мне подумалось следующее:
Наверное, функциональному программированию более свойственнен взгляд на любый структуры данных, в частности, АДТ, как на функцию. Например, в ФП пар нет, есть тип $\forall c. (a\to b\to c)\to c$ с двумя проекциями $\lambda p. p (\lambda xy.x)$ и $\lambda p. p (\lambda xy.y)$ и конструктором $\lambda xyf.fxy$

[Sonic86]

Посмотрел Вику. Похоже, что пары и списки не относятся к ФП. А я-то думал... Или относятся?

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

напишу на паскале. Вообще, это то, что называется "функция обратного вызова" (callback function).

Вот как, спасибо, надо с этим разобраться. TFunc пока малость смущает, но надо разбираться.
В Вики прочитал, что функции высшего порядка в C++ можно реализовать передачей классов в функции.
А как насчет возврата функции в качестве значения? Тоже инициализируем функцию в классе и возвращаем класс?

_hum_ в сообщении #909602 писал(а):

Когда-то мне в этом плане (насколько многообразно программирование) "открыла глаза" книга P.Van Roy, S. Haridi. Concepts, Techniques, and Models of Computer Programming.

не грузиццо

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

Да, любой современный язык поддерживает пару (record/struct)

Я пока не врубился. Например, PL/SQL. Там есть record, но там с типами вообще плохо (и вообще отвратный язык). Я могу объявить некий record:

rRec is record(
  a in %type1%,
  b in %type2%
)

Здесь %type1%, %type2% уже должны быть предварительно объявлены, впихнуть туда rRec нельзя. ЕМНИП, аналогично со struct в C++, или это не так?

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

Наверное, функциональному программированию более свойственнен взгляд на любый структуры данных, в частности, АДТ, как на функцию. Например, в ФП пар нет, есть тип $\forall c. (a\to b\to c)\to c$ с двумя проекциями $\lambda p. p (\lambda xy.x)$ и $\lambda p. p (\lambda xy.y)$ и конструктором $\lambda xyf.fxy$

Вот сразу вопрос, я пока такие тексты не понимаю. Откуда Вы берете вот эту теорию типов, соответствие лямбда-конструкциям?
Вот сейчас нагуглил Пирса 600-страничного про типы в ЯП, пойдет?

[Xaositect]

Давайте я тут немножко что-нибудь напишу, раз уж меня уже упомянули.

"Функциональное программирование" - это достаточно размытое словосочетание, и понимают его по-разному.

Это может означать просто то, что функции в языке являются данными, и их можно создавать, передавать в другие функции и возвращать как результаты. Началось это с LISP. В C есть указатели на функции, но они очень ограниченные - сделать можно только указатель на существующую функцию, нельзя, например, создать функцию, которая принимает число и возвращает функцию умножения на это число. В C++03 такую функцию можно сымитировать с помощью объектов-функторов, но для того, чтобы сделать функторы, поведение которых может быть достаточно разнообразным, надо по сути впилить в программу интерпретатор лиспа. В C++11 уже есть лямбды, которые позволяют взять некоторый кусок кода и засунуть функцию, которая выполняет этот кусок, в переменную. Вот примерно тут граница и проходит - LISP, C# и C++11 поддерживают функциональную парадигму, а Pascal, C, C++03 - нет.

Это может означать чисто функциональное программирование или, что примерно то же самое, программирование с иммутабельными переменными - когда каждое имя в программе всегда означает одно и то же значение. Это подход Haskell. Нельзя изменять значения переменных, можно вызывать функции, которые возвращают новое значение. В частности, поскольку функция всегда должна делать одно и то же, она не может использовать глобальные переменные. Соответственно, если нужно сделать что-то с внешним миром, то нужно использовать некий объект, отличный от функции (в Haskell это значение в монаде IO).

Это может означать декларативное программирование в противовес императивному, то есть программирование не в терминах "что должен сделать процессор", а в терминах "что должно получиться при таком входе". Оно часто путается с функциональным, потому что декларативное описание программы - это, по сути, какое-то описание функции, которую она выполняет.

Наличие/отсутствие каких-то структур данных к функциональности программирования имеет мало отношения, в лямбдах действительно можно все закодировать функциями - см. Church numerals, например.

[rockclimber]

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

А как насчет возврата функции в качестве значения? Тоже инициализируем функцию в классе и возвращаем класс?

Хм. Интересный вопрос. Хотя я таких конструкций не встречал (и даже не задумывался о том, что они могут понадобиться), формально, ничто не мешает написать так:

type
  TFunc = function (a: integer): integer;

  function GetMyFunc(x:integer): TFunc;
    function MyInternalFunc(a: integer): integer;
    begin
      Result:= a * 2;
    end;
  begin
    Result:= @MyInternalFunc;
  end;

var
  f: TFunc;
  a: integer;
begin
  f:= GetMyFunc(5);
  a:= f(6);
  
end;

И это даже наверно будет работать, но вот если мы поробуем внутри MyInternalFunc проделывать некие операции с x - я, честно, говоря, не берусь предсказать, как поведет себя программа. Завтра попробую поставить freepascal и попробовать.

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

TFunc пока малость смущает, но надо разбираться.

А что именно смущает? Это такой тип данных - ссылка на функцию с определенной сигнатурой.

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

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

Да, любой современный язык поддерживает пару (record/struct)

Я пока не врубился. Например, PL/SQL. Там есть record, но там с типами вообще плохо (и вообще отвратный язык). Я могу объявить некий record:

rRec is record(
  a in %type1%,
  b in %type2%
)

Здесь %type1%, %type2% уже должны быть предварительно объявлены, впихнуть туда rRec нельзя. ЕМНИП, аналогично со struct в C++, или это не так?

Так, но вы не смотрите на PL/SQL - это не язык общего назначения, у него своя специфическая область применения, и за ее пределами он не особо-то и нужен, а специфика этой области - реляционные БД. Любые структуры, которые есть в PL/SQL, нужны, как правило, для промежуточной обработки данных этих БД, а там такая структура просто не понадобится никогда.

[_Ivana]

Sonic86 то что вас смущает, используется в Паскале и С с самого их появления - указатели на функции. Не задумывались, как работает простейшая библиотечная функция сортировки массива, если значения массива составного типа? Требуется отдельная функция сравнения значений этого типа на больше/меньше, так называемый компаратор. Программист пишет необходимое количество компараторов для своих типов и вызывает одну и ту же библиотечную функцию сортировки, передавая в нее указатель на соответствующую функцию-компаратор.

То, что описал Xaositect во втором варианте понимания, можно реализовать и на строго императивном языке - не использовать изменяемые переменные, циклы реализовывать через рекурсию и т.п. Хотя конечно функции как объекты первого класса не появятся, но некоторый функционал реализовать можно.

А Prolog и скриптовые языки запросов имхо стоят особняком и для них можно открыть отдельную тему.

ЗЫ про нумералы Чёрча и прочее, пытаюсь овладеть хоть минимальной базой для осознанного применения инструмента, а не просто тупого обезьянничания, но даже такие вводные статьи являются для меня большим откровением и не усваиваются сразу.

[arseniiv]

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

Напомню, что ни в Java, ни в C# нет оператора безусловного перехода.

В C# есть внутри-switch-ный goto case.

-- Сб сен 20, 2014 21:54:51 --

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

ЗЫ про нумералы Чёрча и прочее, пытаюсь овладеть хоть минимальной базой для осознанного применения инструмента, а не просто тупого обезьянничания, но даже такие вводные статьи являются для меня большим откровением и не усваиваются сразу.

На мой взгляд, на одних комбинаторах далеко не убежишь. Точнее, на комбинаторах, которые не всунуты в λ-исчисление (там это просто термы без свободных переменных, как вы могли где-нибудь видеть). В последнем случае, когда видна «внутренняя структура», как-то, по-моему, проще.

[Joker_vD]

Об отсутствии явного состояния (state) и переменных в функциональных языках программирования — Ben Lippmeier, "Type Inference and Optimisation for an Impure World". PhD-диссертация, посвящена явному включению деструктивного обновления в ФЯП. Содержит обсуждение, почему эта возможность важна и нужна, обзор использующихся ныне подходов для работы с состоянием.

[arseniiv]

(Оффтоп)

Joker_vD, спасибо! Как-то натыкался уже на Disciple, но ничего не понял. Надеюсь, сейчас будет по-другому.

[joke-100]

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

Чего я еще забыл или где наврал?

Вы забыли единственное, что ДЕЙСТВИТЕЛЬНО относится непосредственно к ФП: иммутабельность, и, как следствие, ссылочная прозрачность.
И что характерно, все что Вами перечислено, относится к ФП чуть менее, чем никак, как, впрочем и SICP. Это мода сейчас такая, притягивать за уши сикп к быдло-фп? Кто хочет показаться умным, рекомендуют, в качестве фетиша TAPL, оно гораздо сильней воняет в унисон с фп.

-- 29.09.2014, 16:01 --

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

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

Суть отличия понять очень легко. Каррирование -- это механизм позвляющий частичное применение, КЭП, нам, какбы, подсказывает.

-- 29.09.2014, 16:11 --

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

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

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

-- 29.09.2014, 16:15 --

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

В ФП тоже самое или нет?

Может не совсем то же, но к ФП это не имеет ни малейшего отношения. Первоклассные функции имеют тысячи императивных ЯП, некоторые имеют и безымянные, это ни о чем.

-- 29.09.2014, 16:19 --

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

как переменных и состояния в ФП

Переменные в ФП есть, нет муттабельных переменных. Состояние в ФП, естественно, есть, оно меняется с каждой редукцией.

-- 29.09.2014, 16:21 --

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

считает императивщиной

Имхо, надо быть идиотом, чтобы считать CL, да и любой лисп, функциональным. Раньше считали, но в это вкладывался совершенно иной смысл.

-- 29.09.2014, 16:26 --

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

ни четко определенной последовательности выполнения инструкций

А в обычных ЯП в условных конструкциях (ленивых) есть четко определенная последовательность?

-- 29.09.2014, 16:32 --

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

Каррирование — это, как я понимаю, просто факт существования изоморфизма между

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

-- 29.09.2014, 16:38 --

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

А существует ли нефункциональный язык со структурой данных "пара" или "список"?

лисп

[Toucan]

joke-100 в сообщении #913581 писал(а):

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

joke-100, предупреждение за недопустимые формы ведения дискуссии