Макросы ОЛ: с побочными эффектами и/или детерминированные?

[Владимир Ситников]

В обсуждении Конечный автомат на ПР200 тов anthrwpos выссказал мысль, что

PS ОЛ по сути есть функциональный язык программирования. Каждый макрос в нем есть детерминированная функция без побочных эффектов, то есть макрос не может изменить значения каких бы то ни было внешних переменных, и результат его работы зависит только от значения входящих аргументов, поэтому попытка реализовать там что либо из императивной парадигмы будет проваливаться)
К сожалению, ОЛ лишен всех преимуществ настоящих функциональных ЯП таких как полиморфизм, частичное применение, функции высшего порядка, рекурсия и прочее. Иначе ничего бы не стоило организовать например, списки и пользоваться ими аки массивами)
Таким образом, если вы хотите сделать полноценный Case, который мог бы совершать произвольные действия на определенные значения бегущей переменной, то ничего у вас не выйдет ввиду того, что ОЛ не поддерживает доступ к внешним переменным. Если вы хотите просто сделать функцию результат которой зависит от входной переменной, то это функция SEL.

Мысль занятная, но к сожалению неправильная с точки зрения классической теории программирования.

Во-первых, Wikipedia:

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

В английской статье:

Side effects. In the presence of side effects, a program's behaviour may depend on history; that is, the order of evaluation matters. Understanding and debugging a function with side effects requires knowledge about the context and its possible histories

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

Апофеозом выступает такое сообщение:

блинк - обычная чистая функция.

И это при том, что чистая функция это

Чистота функции: 1. является детерминированной;
2. не обладает побочными эффектами.
Наличие только одного из свойств недостаточно, для того чтобы функция была чистой.
...
Недетерминированность функции — возможность возвращения функцией разных значений несмотря на то, что ей передаются на вход одинаковые значения входных аргументов. В этом случае невозможно построить однозначную таблицу значений функции

Очевидно, что blink возвращает разные значения, несмотря на то, что значения на входе не изменяются. Blink выдаёт то нолик, то единичку. Значение изменилось? Да. Агрументы запуска blink меняли? Нет. Всё -- это недетерминированность функции.
Значит ли это, что "blink ущербная функция"? Едва ли. Просто с точки зрения computer science, blink не является чистой функцией.


В конце концов, anthrwpos выдал такое заключение:

Итого, всё во что уперлись наши разногласия - это правомерно ли считать ли развертку во времени аргументом или результатом работы функции.

Я, конечно, соглашусь, что считать Wikipedia "основой основ" неправильно, но, если в Wikipedia написано "странное", то стоит перепроверить _свою_ позицию.
Вот откуда такая уверенность, что все авторы на Wikipedia ошиблись (и в русской и в английской версии статьи)?

Внимание, вопрос:

На этом, вопрос к тов. anthrwpos: приведите, пожалуйста, пример недетерминированной функции. Раз утверждаете, что ОЛ макрос это "детерминированная функция без побочных эффектов", и считаете, что "развертка по времени это тоже простой аргумент" то приведите пример недетерминированной функции.
Поясню к чему я веду: в подавляющем количестве случаев (почти во всех), выходное значение функции зависит от текущих аргументов и истории прошлых запусков.
Если следовать логике "история запусков это просто аргумент", то получается, что почти все функции являются "детерминированная функция без побочных эффектов".
Очевидно, что это ересь, но давайте посмотрим как у вас получится?

Если такой вариант не устраивает, процитируйте "из учебной литературы" (ну или из оттуда, чему вы доверяете) что-нибудь, подтверждающее, что "если вызывали функцию несколько раз с одними аргументами и она вернула разные результаты, то она называется <<детерменированная без побочных эффектов>>".

Ну или процитируйте хоть что-нибудь, говорящее о том, что "развертка во времени это аргумент".
Слова "есть единое пространство-время и относительность одновременности" в контексте "чистых функций" это, простите, бред сивой кобылы. Это реально так, ведь у слова "чистая функция" есть определение, и на него пространство-время не действует.
У ФБ SET_RESET_TRIGGER(S, R) сколько аргументов? Два или бесконечное количество? Ну вот реально как вы собрались вкрячивать "развертку времени" в качестве аргумента?


Более того, сама длительность выполнения программы это тоже побочный эффект.
Приведу пример: в ОЛ длительность обычной функци fMUL наверняка зависит от входных аргументов (процессор ПР200 не умеет работать с плавающей точкой, и в Си библиотеке для этого процессора функция fMUL эмулируется). Поэтому, если совсем строго говорить, то ОЛ макрос уж точно с побочными эффектами.
Да, длительность выполнения важна в какой-нибудь безопасности, поэтому сейчас длительностью можно пренебречь. Но я привожу длительность тут для того, чтобы вы хоть как-то задумались над тем, что на самом деле в классической литературе по программированию принято называть словом "побочный эффект".


PS. Пункт 4.г правил я видел, но считаю, что тема интересна не только одному anthrwpos.

[anthrwpos]

Вообще говоря, чтобы предметно спорить по теории программирования, нам следует ссылаться на литературу по теории программирования.
Я к сожалению, компьютер сайенс курса не слышал, поэтому я такой литературы не знаю.
Мои сведения о чистых функциях я почерпнул из учебной литературы по языку Haskell.
И я не знаю, как у вас в Википедии, но у нас в Хаскеле действуют следующие определения:

Детерминированностью функции называется однозначное состояние выхода зависящее только от состояния входа и не зависящее от каких бы то ни было внешних состояний.

Побочным эффектом функции называется возможность функции подействовать на какое либо внешнее состояние (переменную, физическую реальность посредством вывода).

То что у вас написано в ссылке с русской википедии, так там перепутано понятие недетерминированности (разный выход при одинаковом входе) и побочный эффект. При чем здесь побочный эффект? Само выражение "побочный эффект" подразумевает, что источник побочного эффекта оказывает некое неявное, побочное влияние на что либо другое. Влияние чего-то там на результат работы функции было бы странно называть побочным эффектом функции, не так ли?)

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

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

Пример функции с побочным эффектом - функция записи в файл.

[Владимир Ситников]

Вообще говоря, чтобы предметно спорить по теории программирования, нам следует ссылаться на литературу по теории программирования.

Давайте, же, хоть куда-нибудь сошлитесь. Забавно выглядит, когда вы ругаете мои ссылки, а сами вообще никаких не приводите.

У ФБ SET_RESET_TRIGGER(S, R) сколько аргументов?
Это чистая функция в вашем понимании?

Можете сделать set_reset "чистую функцию" в Haskell понимании термина "pure function"?
Давайте же:

set_reset s r = ...

То что у вас написано в ссылке с русской википедии, так там перепутано понятие недетерминированности (разный выход при одинаковом входе) и побочный эффект. При чем здесь побочный эффект? Само выражение "побочный эффект" подразумевает, что источник побочного эффекта оказывает некое неявное, побочное влияние на что либо другое. Влияние чего-то там на результат работы функции было бы странно называть побочным эффектом функции, не так ли?)

1) Присмотритесь, и поймёте, что слова "Если вызвать функцию с побочным эффектом дважды" wikipedia не являются определением "недетерминированности", а они описывают пример того, что может произойти, если функция с побочным эффектом. В этом ключе, никакого перепутывания нет.
Там говорится, что, если функцию вызывали 2 раза и она вернула разное на одних и тех же данных, то такую функцию называют недетерминированной.
Да, бывают другие недетерминированные функци. Но, если так окажется, что вызвали с одними аргументами, а вернулось разное, то уж детерминированной эту функцию называть никак нельзя.
Опираясь на этот пример, я настаиваю на том, что set_reset_trigger (SR триггер в ОЛ) это недетерминированная функция с побочным эффектом (побочный эффект заключается в изменении скрытого состояние, которое можно наблюдать по результатам последующих вызовов этого SR триггера).

2) Странно или нет называть, но и в русской и в английской версии говорится, что "функция обладает побочным эффектом, если она взаимодействует с окружением".
"observable interaction with its calling functions or the outside world"

side effects For example, a particular function might modify a global variable or static variable, modify one of its arguments, raise an exception, write data to a display or file, read data, or call other side-effecting functions

3) Вот специальный пример из английской статьи:

side effects A function without side effects may be impure, for example if its output depends on the value of a global variable.

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

Оу, оу. SET_RESET_TRIGGER это чистая функция? Это функция без побочных эффектов?
По какому признаку?

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

Пример функции с побочным эффектом - функция записи в файл.

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


С точки зрения "классики жанра", да примеры с чтением и записью файла хорошие, но вот незадача: эти примеры слабо подходят под ваши же собственные определения про "пространство-время и развёртку времени". Грубо говоря, если развернуть время, то чтение файла становится вполне детерминированным.

[Филоненко Владислав]

Переводя с заумного на русский.
Правильно ли, что машина поворачивает ВСЕГДА налево, если налево крутится руль или допустимы варианты (но машина будет иметь в 2 раза более мощный двигатель)?

[Владимир Ситников]

Переводя с заумного на русский.
Правильно ли, что машина поворачивает ВСЕГДА налево, если налево крутится руль или допустимы варианты (но машина будет иметь в 2 раза более мощный двигатель)?

Зависит от.
Если бы машина была чистой функцией, то, да, она всегда поворачивала бы налево при вращении руля налево.

Но, по факту, может быть скрытое состояние ("сломалась рулевая"), и при повороте руля машина вообще не повернёт.
Или же, при движении по льду руль можно хоть обкрутиться, а машина не повернёт.

[anthrwpos]

Можете сделать set_reset "чистую функцию" в Haskell понимании термина "pure function"?
Давайте же:

set_reset s r = ...

Ну, просто ради развлечения)

set_reset :: Bool -> Bool -> State Bool ()
set_reset False False = state (\w -> ((),w))
set_reset True False = state (\_ -> ((),True))
set_reset _ True = state (\_ -> ((),False))

Здесь есть некоторое жульничество, но формально с точки зрения языка, вся эта конструкция является девственно чистой)
Я просто хочу посмотреть, что вы на это скажете

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

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

[Владимир Ситников]

Ну, просто ради развлечения)

Пока я вспоминаю Haskell, ответьте, всё-таки на вопросы про то, сколько аргументов у ФБ SR-триггер, и является ли он детерминированной и/или чистой функцией.

[anthrwpos]

У SR два аргумента, он определенно не имеет побочных эффектов, а вот является ли он детерминированным, я еще не решил. Всё будет зависеть от того, смогу я убедить самого себя, что детерминированность в смысле развертки входов во времени считается или нет)
Если есть конкретные контраргументы против такого определения детерминированности, я с удовольствием их обсужу)

[Владимир Ситников]

У SR два аргумента, он определенно не имеет побочных эффектов, а вот является ли он детерминированным, я еще не решил. Всё будет зависеть от того, смогу я убедить самого себя, что детерминированность в смысле развертки входов во времени считается или нет)
Если есть конкретные контраргументы против такого определения детерминированности, я с удовольствием их обсужу)

Контраргументы простые и не менялись с самого моего первого сообщения.
Аргумента у SR два. Аргумента типа "развёртка входов во времени" у SR просто-напросто нет.

0) О какой "развёртке времени" вообще идёт речь, если у SR только два аргумента S и R?

1) Представим себе реальный блок SR.
Внимание, вопрос: что вернёт вызов SR(S=FALSE, R=FALSE). Что вернёт блок?
Может вернуть как TRUE, так и FALSE. Значит, это недетерминированная функция.

В этом плане, SR триггер ничем не отличается от "чтения файла" или "чтения координат мыши"

2) Теперь к "побочным эффектам".
У SR есть скрытое состояние. И вызовы с параметрами (S=TRUE, R=FALSE), (S=FASLE, R=TRUE) меняют это самое скрытое состояние SR триггера.
Изменение этого состояния можно наблюдать через вызов SR(S=FALSE, R=FALSE).
По определению, это и называется "функция с побочными эффектами".

[Владимир Ситников]

Ну, просто ради развлечения)

set_reset :: Bool -> Bool -> State Bool ()
set_reset False False = state (\w -> ((),w))
set_reset True False = state (\_ -> ((),True))
set_reset _ True = state (\_ -> ((),False))

Здесь есть некоторое жульничество, но формально с точки зрения языка, вся эта конструкция является девственно чистой)
Я просто хочу посмотреть, что вы на это скажете

Делаю ставку на то, что тут вы пропихиваете дополнительный аргумент через pointfree.
На вопрос "сколько аргументов у SR-триггера" вы отвечаете два, но тут дополнительно подали аргумент "историю прошлых серий" он же "глобальное состояние".

Если объяснение неверное, то я попрошу вас дописать пример использования этого самого SR-триггера и всё встанет на свои места.

Потому что изменение файла происходит во внешнем по отношению к функции окружению.

Да, про файлы всё верно пишете.
Но я хотел бы подчеркнуть, что вы напираете на слово "внешнее окружение", а с математической (она же computer science) точки зрения, невозможно определить что именно является "внешним окружением".

Ну, реально.

Поэтому, "изменение состояния" формулируется обычно как "наблюдаемое изменение состояние". Иными словами, если какое-то глобальное состояние изменяется, но это невозможно увидеть, то это "не считается". Именно поэтому я и называю ФБ SR-триггера блоком с побочным эффектом.

Ответить на вопрос "меняет ли SR триггер глобальное состояние?", на самом деле, тяжело, ведь непросто сказать где именно хранится состояние SR триггера.
Но на вопрос "можно ли заметить изменение состояния SR триггера?" ответ напрашивается сам собой. Очевидно, что заметить можно. Значит состояние есть, значит есть и побочный эффект по изменению этого состояния.