понимание ссылочной прозрачности

Вот моя попытка ответить на вопрос:

Любую систему можно описать как комбинаторную функцию, большую или маленькую.

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

Вы даже можете описать, скажем, работу игрового движка как таблицу истинности или комбинаторную функцию.

У вас может быть детерминированная функция, которая принимает «текущее состояние всей игры» как ОЗУ, занимаемое игровым движком и вводом с клавиатуры, и возвращает «состояние игры на один кадр позже». Возвращаемое значение будет определяться комбинациями битов на входе.

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

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

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

Язык, на котором вы могли бы проверить, чтобы узнать, как все делается на чисто функциональном языке, был бы Haskell . Есть способы использовать «возможности обновляемого хранилища», например, Reader Monad и State Monad . Если вас интересуют чисто функциональные структуры данных, Okasaki может быть хорошим чтением.

И да, вы правы: порядок оценки на чисто функциональном языке, таком как haskell, не имеет значения, как в нефункциональных языках, потому что, если нет побочных эффектов, нет причин делать что-то до / после чего-то. else - если ввод одного не зависит от вывода другого или не означает, что в игру вступают монады.

Я действительно не знаю о вопросе с таблицей истинности.

Вопрос: где ошибка в этом рассуждении?

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

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

Редактировать: Хотя я, очевидно, упустил из виду настоящий вопрос, я думаю, что мой ответ довольно хорош, поэтому я сохраняю его :-) (см. Ниже).

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

Прежде всего, предположим, что вы взяли императивный язык, такой как C, и сделали его таким, чтобы вы могли » t изменить переменные после их определения. Например.:

int i;

for (i = 0;  // okay, that's one assignment
     i < 10; // just looking, that's all
     i++)    // BUZZZ!  Sorry, can't do that!

Ну, вот и ваш цикл для . Можем ли мы сохранить цикл while ?

while (i < 10)

Конечно, но это не очень полезно. i не может быть изменен, поэтому он либо будет работать вечно, либо не будет работать вообще.

Как насчет рекурсии? Да, вы можете сохранить рекурсию, и она по-прежнему очень полезна:

int sum(int *items, unsigned int count)
{
    if (count) {
        // count the first item and sum the rest
        return *items + sum(items + 1, count - 1);
    } else {
        // no items
        return 0;
    }
}

Теперь, когда речь идет о функциях, мы не меняем состояние, но переменные могут, ну, в общем, варьироваться. Как только переменная передается в нашу функцию, она блокируется. Однако мы можем вызвать функцию снова (рекурсия), и это похоже на получение нового набора переменных (старые остаются прежними). Хотя существует несколько экземпляров элементов и count , sum ((int []) {1,2,3}, 3) всегда будет оценивать как 6 , поэтому вы можете заменить это выражение на 6 , если хотите.

Можем ли мы делать все, что захотим? Я не уверен на 100%, но думаю, что ответ положительный. Вы, конечно, можете, если у вас есть закрытие.

Вы правы. Идея в том, что после определения переменной ее нельзя переопределить. Ссылочно прозрачное выражение для одних и тех же переменных всегда дает одно и то же значение результата.

Я рекомендую изучить Haskell, чисто функциональный язык. Строго говоря, в Haskell нет оператора «присваивания». Например:

my_sum numbers = ??? where
    i     = 0
    total = 0

Здесь вы не можете написать «цикл for», который увеличивает i и total по мере выполнения. Однако еще не все потеряно.Просто используйте рекурсию, чтобы получать новые i s и total s:

my_sum numbers = f 0 0 where
    f i total =
        if i < length numbers
            then f i' total'
            else total
        where
            i' = i+1
            total' = total + (numbers !! i)

(Обратите внимание, что это глупый способ суммирования списка в Haskell, но он демонстрирует метод решения с одним присваиванием.)

Теперь рассмотрим этот крайне императивно выглядящий код:

main = do
    a <- readLn
    b <- readLn
    print (a + b)

Фактически это синтаксический сахар для:

main =
    readLn >>= (\a ->
    readLn >>= (\b ->
    print (a + b)))

Идея состоит в том, что вместо того, чтобы main быть функцией, состоящей из списка операторов, main является Действие ввода-вывода, которое выполняет Haskell, и действия определяются и связываются вместе с операциями связывания. Кроме того, действие, которое ничего не делает, дающее произвольное значение, можно определить с помощью функции return .

Обратите внимание, что привязка и возврат не относятся к конкретным действиям. Их можно использовать с любым типом, который называет себя монадой, для всяких забавных вещей.

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

a = readLn

Если бы это было разрешено, значение a зависело бы от мира и каждый раз было бы другим мы назвали readLn , что означает, что readLn не будет ссылочно прозрачным.

Вместо этого мы привязываем действие readLn к функции, которая имеет дело с действием, давая новое действие, например:

readLn >>= (\x -> print (x + 1))

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