Как чисто функциональный язык программирования обходится без операторов присваивания?

26

Читая знаменитый SICP, я обнаружил, что авторы, скорее всего, неохотно представляют инструкцию присваивания Схеме в главе 3. Я читаю текст и понимаю, почему они так думают.

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

Давайте использовать пример, который предлагает книга, bank accountпример. Если нет оператора присваивания, как это можно сделать? Как изменить balanceпеременную? Я спрашиваю об этом, потому что знаю, что существуют некоторые так называемые чисто функциональные языки, и согласно полной теории Тьюринга это тоже можно сделать.

Я изучил C, Java, Python и много использую назначения в каждой написанной мной программе. Так что это действительно открывающий глаза опыт. Я действительно надеюсь, что кто-то вкратце объяснит, как избегать назначений в этих функциональных языках программирования и какое глубокое влияние (если таковое имеется) оно оказывает на эти языки.

Пример, упомянутый выше, здесь:

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

Это изменило свой balanceпуть set!. Для меня это очень похоже на метод класса для изменения члена класса balance.

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

Gnijuohz
источник
1
Что касается изучения чисто функционального языка: я бы не рекомендовал делать это прямо сейчас. Если вы изучите Haskell, то, кроме того, что вы научитесь писать программы без изменяемых переменных, вам также придется узнать о лени и способах Haskell выполнять операции ввода-вывода. Это может быть немного много сразу. Если вы хотите научиться писать программы без изменяемого состояния, возможно, проще всего было бы просто написать набор программ схем без использования set!или других функций, заканчивающихся на !. Как только вы освоитесь с этим, переход на чистый FP должен быть более легким.
sepp2k

Ответы:

21

Если нет оператора присваивания, как это можно сделать? Как изменить переменную баланса?

Вы не можете изменять переменные без какого-либо оператора присваивания.

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

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

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

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


Поскольку вы запросили пример, давайте рассмотрим императивную программу, которая использует вашу функцию make -draw (в псевдокоде). Эта программа позволяет пользователю снимать со счета, вносить на него деньги или запрашивать сумму денег на счете:

account = make-withdraw(0)
ask for input until the user enters "quit"
    if the user entered "withdraw $x"
        account(x)
    if the user entered "deposit $x"
        account(-x)
    if the user entered "query"
        print("The balance of the account is " + account(0))

Вот способ написать ту же программу без использования переменных-переменных (я не буду беспокоиться о ссылочно-прозрачном вводе-выводе, потому что вопрос был не об этом):

function IO_loop(balance):
    ask for input
    if the user entered "withdraw $x"
        IO_loop(balance - x)
    if the user entered "deposit $x"
        IO_loop(balance + x)
    if the user entered "query"
        print("The balance of the account is " + balance)
        IO_loop(balance)
    if the user entered "quit"
        do nothing

 IO_loop(0)

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

sepp2k
источник
Я могу понять вашу точку зрения, но давайте посмотрим, хочу ли я программу, которая также имитирует банковский счет и может также выполнять эти действия (вывод и внесение), тогда есть ли какой-нибудь простой способ сделать это?
Gnijuohz
@Gnijuohz Это всегда зависит от того, какую именно проблему вы пытаетесь решить. Например, если у вас есть начальный баланс и список снятия средств и депозитов, и вы хотите знать баланс после этих снятий и депозитов, вы можете просто рассчитать сумму депозитов за вычетом суммы снятия и добавить ее к начальному балансу , Так в коде это будет newBalance = startingBalance + sum(deposits) - sum(withdrawals).
sepp2k
1
@Gnijuohz Я добавил пример программы в свой ответ.
sepp2k
Спасибо за время и усилия, которые вы вложили в написание и переписывание ответа! :)
Gnijuohz
Я хотел бы добавить, что использование продолжения также может быть средством достижения этого в схеме (если вы можете передать аргумент продолжению?)
dader51
11

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

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

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

Мейсон Уилер
источник
Мне действительно интересен наш ответ и пример Haskell, но из-за недостатка знаний о нем я не могу полностью понять последнюю часть вашего ответа (ну, а также вторую часть :()
Gnijuohz
3
@Gnijuohz Последний абзац говорит , что вместо того , b = makeWithdraw(42); b(1); b(2); b(3); print(b(4))вы можете просто сделать , b = 42; b1 = withdraw(b1, 1); b2 = withdraw(b1, 2); b3 = withdraw(b2, 3); print(withdraw(b3, 4));где withdrawпросто определяется как withdraw(balance, amount) = balance - amount.
сентября
3

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

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

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

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

blueberryfields
источник
«В конечном счете, любой чисто функциональный язык иногда должен порвать с чисто функциональным подходом - у подавляющего большинства полезных программ есть побочные эффекты» Правда, но тогда вы говорите о выполнении ввода-вывода и тому подобное. Множество полезных программ могут быть написаны без изменяемых переменных.
сентября
1
... и под «подавляющим большинством» полезных программ вы подразумеваете «все», верно? Мне трудно даже представить возможность существования любой программы, которую можно разумно назвать «полезной», которая не выполняет ввод-вывод, действие, которое требует побочных эффектов в обоих направлениях.
Мейсон Уилер
SQL-программы @MasonWheeler не выполняют IO как таковые. Также нередко пишут несколько функций, которые не выполняют IO на языке с REPL, а затем просто вызывают их из REPL. Это может быть очень полезно, если ваша целевая аудитория способна использовать REPL (особенно если ваша целевая аудитория это вы).
сентября
1
@MasonWheeler: всего лишь один простой контрпример: концептуальный расчет n цифр числа пи не требует ввода-вывода. Это только математика и переменные. Единственный обязательный ввод - n, а возвращаемое значение - Pi (до n цифр).
Иоахим Зауэр
1
@Joachim Sauer в конечном итоге вы захотите распечатать результат на экране или иным образом сообщить о нем пользователю. И изначально вы захотите загрузить некоторые константы в программу откуда-то. Итак, если вы хотите быть педантичным, все полезные программы должны в какой-то момент выполнять IO, даже если это тривиальные случаи, которые неявны и всегда скрыты от программиста средой
blueberryfields
3

На чисто функциональном языке можно было бы запрограммировать объект банковского счета как функцию преобразователя потока. Объект рассматривается как функция от бесконечного потока запросов от владельцев учетной записи (или кого-либо еще) к потенциально бесконечному потоку ответов. Функция начинается с начального баланса и обрабатывает каждый запрос во входном потоке для вычисления нового баланса, который затем возвращается к рекурсивному вызову для обработки оставшейся части потока. (Я помню, что SICP обсуждает парадигму потокового преобразователя в другой части книги.)

Более сложная версия этой парадигмы называется «функционально-реактивное программирование», обсуждаемое здесь на StackOverflow .

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

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

Удай Редди
источник
Я полагаю, вы принадлежите к какому-нибудь храму? :-P
Gnijuohz
1
Храм свободного мышления. Там нет проповедников.
Uday Reddy
2

Невозможно сделать программу на 100% функциональной, если она должна делать что-то полезное. (Если побочные эффекты не нужны, тогда весь процесс можно было бы свести к постоянному времени компиляции). Как и в примере с выводом, вы можете сделать большинство процедур функциональными, но в конечном итоге вам понадобятся процедуры, которые имеют побочные эффекты (ввод от пользователя, вывод на консоль). Тем не менее, вы можете сделать большую часть своего кода функциональной, и эту часть будет легко протестировать, даже автоматически. Затем вы создаете некоторый императивный код для ввода / вывода / базы данных / ..., который потребует отладки, но поддержание большей части кода в чистоте не составит большого труда. Я буду использовать ваш пример вывода:

(define +no-founds+ "Insufficient funds")

;; functional withdraw
(define (make-withdraw balance amount)
    (if (>= balance amount)
        (- balance amount)
        +no-founds+))

;; functional atm loop
(define (atm balance thunk)
  (let* ((amount (thunk balance)) 
         (new-balance (make-withdraw balance amount)))
    (if (eqv? new-balance +no-founds+)
        (cons +no-founds+ '())
        (cons (list 'withdraw amount 'balance new-balance) (atm new-balance thunk)))))

;; functional balance-line -> string 
(define (balance->string x)
  (if (eqv? x +no-founds+)
      (string-append +no-founds+ "\n")
      (if (null? x)
          "\n"
          (let ((first-token (car x)))
            (string-append
             (cond ((symbol? first-token) (symbol->string first-token))
                   (else (number->string first-token)))
             " "
             (balance->string (cdr x)))))))

;; functional thunk to test  
(define (input-10 x) 10) ;; define a purly functional input-method

;; since all procedures involved are functional 
;; we expect the same result every time.
;; we use this to test atm and make-withdraw
(apply string-append (map balance->string (atm 100 input-10)))

;; no program can be purly functional in any language.
;; From here on there are imperative dirty procedures!

;; A procedure to get input from user is needed. 
;; Side effects makes it imperative
(define (user-input balance)
  (display "You have $")
  (display balance)
  (display " founds. How much to withdraw? ")
  (read))

;; We need a procedure to print stuff to the console 
;; as well. Side effects makes it imperative
(define (pretty-print-result x)
  (for-each (lambda (x) (display (balance->string x))) x))

;; use imperative procedure with atm.
(pretty-print-result (atm 100 user-input))

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

Сильвестер
источник
+1 за обширный пример и реалистичные объяснения функциональных частей и не чисто функциональных частей программы и упоминания, почему FP все же имеет значение.
Зельфир Кальцталь
1

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

  1. Параметры функции связаны напрямую с возвращаемыми значениями
  2. выбор различных объектов для возврата вместо изменения существующих объектов.
  3. создание новых ленивых значений
  4. список всех возможных объектов, а не только тех, которые должны быть в памяти
  5. без побочных эффектов
ТР1
источник
Похоже, это не решает поставленный вопрос. Как вы программируете объект банковского счета на чистом функциональном языке?
Uday Reddy
это просто функции преобразования одной банковской записи в другую. Ключ в том, что когда такие преобразования происходят, новые объекты выбираются вместо изменения существующих.
1
Когда вы преобразуете одну запись банковского счета в другую, вы хотите, чтобы клиент выполнял следующую транзакцию с новой записью, а не со старой. «Контактная точка» для клиента должна постоянно обновляться, чтобы указывать на текущую запись. Это фундаментальная идея «модификации». «Объекты» банковского счета не являются записями банковского счета.
Uday Reddy