Как может существовать функция времени в функциональном программировании?

550

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

Например, рассмотрим следующее:

f(x,y) = x*x + y; //it is a mathematical function

Независимо от того, сколько раз вы используете f(10,4), его значение всегда будет 104. Таким образом, везде, где вы написали f(10,4), вы можете заменить его на 104, не изменяя значения всего выражения. Это свойство называется ссылочной прозрачностью выражения.

Как говорит Википедия (ссылка),

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

Итак, мой вопрос: может ли функция времени (которая возвращает текущее время) в функциональном программировании?

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

  • Или, если нет, то как узнать текущее время в функциональном программировании?

  • 0
    Я сразу подумал, что функция принимает параметр метода для времени, а вызывающая сторона просто указывает текущее время. Таким образом, с теми же аргументами, он дает тот же результат, и вызывающий может изменить аргумент.
  • 12
    Я думаю, что большинство (или все) функциональные языки не так строги и сочетают в себе функциональное и императивное программирование. По крайней мере, это мое впечатление от F #.
Показать ещё 21 комментарий
Теги:
haskell
functional-programming
f#
clean-language

13 ответов

101
Лучший ответ

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

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

Теперь, как вы можете распечатать текущее время на консоли? Ну, вы должны объединить два действия. Итак, как мы можем это сделать? Мы не можем просто передать getClockTime в print, так как печать ожидает метку времени, а не действие. Но мы можем предположить, что существует оператор >>=, который объединяет два действия: одно, которое получает временную метку, и тот, который принимает один аргумент и печатает его. Применив это к ранее упомянутым действиям, результат... tadaaa... новое действие, которое получает текущее время и печатает его. И это точно, как это делается в Haskell.

Prelude> System.Time.getClockTime >>= print
Fri Sep  2 01:13:23 東京 (標準時) 2011

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

Я не знаю, было ли это более ясным, чем другие объяснения, но иногда это помогает мне думать об этом так.

  • 29
    Это не убедительно для меня. Вы getClockTime называете getClockTime действием вместо функции. Хорошо, если вы вызываете так, а затем вызываете каждое действие функции, тогда даже императивное программирование станет функциональным программированием. Или, может быть, вы хотели бы назвать это активным программированием.
  • 78
    @Nawaz: Ключевым моментом здесь является то, что вы не можете выполнить действие внутри функции. Вы можете только объединить действия и функции вместе, чтобы сделать новые действия. Единственный способ выполнить действие - это объединить его в main действие. Это позволяет отделить чистый функциональный код от императивного кода, и это разделение обеспечивается системой типов. Рассматривая действия как объекты первого класса, вы также можете передавать их и создавать свои собственные «управляющие структуры».
Показать ещё 21 комментарий
347

Да и нет.

Различные языки FP решают их по-разному.

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

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

Как отметил Джеффри Бурка в своем комментарии: Вот хороший intro для IO Monad прямо из HaskellWiki.

  • 210
    Ключевая вещь, которую нужно понять о монаде ввода / вывода в Haskell, состоит в том, что это не просто хак, чтобы обойти эту проблему; Монады - это общее решение проблемы определения последовательности действий в некотором контексте. Одним из возможных контекстов является реальный мир, для которого у нас есть монада IO. Другой контекст находится внутри атомарной транзакции, для которой у нас есть монада STM. Еще один контекст заключается в реализации процедурного алгоритма (например, Knuth shuffle) как чистой функции, для которой мы имеем монаду ST. И вы можете определить свои собственные монады тоже. Монады - это своего рода перегруженная точка с запятой.
  • 2
    Я считаю полезным не называть такие вещи, как получение текущего времени, «функциями», а что-то вроде «процедур» (хотя можно утверждать, что решение Haskell является исключением из этого).
Показать ещё 4 комментария
138

В Haskell используется конструкция, называемая monad для обработки побочных эффектов. Монада в основном означает, что вы инкапсулируете значения в контейнер и имеете некоторые функции для цепочки функций от значений до значений внутри контейнера. Если наш контейнер имеет тип:

data IO a = IO (RealWorld -> (a,RealWorld))

мы можем безопасно реализовать действия IO. Этот тип означает: Действие типа IO - это функция, которая принимает маркер типа RealWorld и возвращает новый токен вместе с результатом.

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

(>>=) :: IO a -> (a -> IO b) -> IO b

>>= принимает одно действие и функцию, которая принимает результат этого действия и создает новое действие из этого. Тип возврата - это новое действие. Например, допустим, что существует функция now :: IO String, которая возвращает строку, представляющую текущее время. Мы можем связать его с функцией putStrLn, чтобы распечатать его:

now >>= putStrLn

Или написано в do -Notation, которое более знакомо императивному программисту:

do currTime <- now
   putStrLn currTime

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

  • 2
    -1: я недоволен дымовой завесой RealWorld . Тем не менее, наиболее важным является то, как этот предполагаемый объект передается по цепочке. Недостающий фрагмент находится там, где он начинается, где находится источник или соединение с реальным миром - он начинается с главной функции, которая выполняется в монаде IO.
  • 2
    @ kaizer.se Вы можете думать о глобальном объекте RealWorld который передается в программу при запуске.
Показать ещё 4 комментария
65

Большинство языков функционального программирования не являются чистыми, т.е. позволяют функциям не только зависеть от их значений. В этих языках вполне возможно, чтобы функция возвращала текущее время. С языков, на которые вы отметили этот вопрос, это относится к scala и f # (а также к большинству других вариантов ML).

В таких языках, как Haskell и Clean, которые чисты, ситуация другая. В Haskell текущее время не будет доступно через функцию, но так называемое действие IO, которое является способом Hackell для инкапсуляции побочных эффектов.

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

  • 2
    Это звучит так, как будто Haskell и Clean делают разные вещи. Из того, что я понимаю, они делают то же самое, только что Haskell предлагает более хороший синтаксис (?) Для достижения этой цели.
  • 26
    @Konrad: они делают то же самое в том смысле, что оба используют функции системы типов для абстрагирования побочных эффектов, но это все. Обратите внимание, что очень хорошо объяснить монаду ввода-вывода в терминах типа мира, но стандарт Haskell на самом деле не определяет тип мира, и фактически невозможно получить значение типа World в Haskell (хотя это очень возможно и действительно необходимо в чистоте). Кроме того, Haskell не использует уникальную типизацию как функцию системы типов, поэтому, если он действительно дает вам доступ к Миру, он не может гарантировать, что вы используете его чисто так, как это делает Clean.
Показать ещё 1 комментарий
44

"Текущее время" не является функцией. Это параметр. Если ваш код зависит от текущего времени, это означает, что ваш код параметризуется по времени.

21

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

В С# вы можете реализовать его следующим образом:

// Exposes mutable time as immutable time (poorly, to illustrate by example)
// Although the insides are mutable, the exposed surface is immutable.
public class ClockStamp {
    public static readonly ClockStamp ProgramStartTime = new ClockStamp();
    public readonly DateTime Time;
    private ClockStamp _next;

    private ClockStamp() {
        this.Time = DateTime.Now;
    }
    public ClockStamp NextMeasurement() {
        if (this._next == null) this._next = new ClockStamp();
        return this._next;
    }
}

(Имейте в виду, что это пример, который должен быть простым, а не практичным. В частности, узлы списка не могут быть собраны в мусор, поскольку они основаны на ProgramStartTime.)

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

// Immutable. A result accompanied by a clockstamp
public struct TimeStampedValue<T> {
    public readonly ClockStamp Time;
    public readonly T Value;
    public TimeStampedValue(ClockStamp time, T value) {
        this.Time = time;
        this.Value = value;
    }
}

// Times an empty loop.
public static TimeStampedValue<TimeSpan> TimeALoop(ClockStamp lastMeasurement) {
    var start = lastMeasurement.NextMeasurement();
    for (var i = 0; i < 10000000; i++) {
    }
    var end = start.NextMeasurement();
    var duration = end.Time - start.Time;
    return new TimeStampedValue<TimeSpan>(end, duration);
}

public static void Main(String[] args) {
    var clock = ClockStamp.ProgramStartTime;
    var r = TimeALoop(clock);
    var duration = r.Value; //the result
    clock = r.Time; //must now use returned clock, to avoid seeing old measurements
}

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

  • 0
    Интересно, что i++ в цикле for не является прозрачным по ссылкам;)
  • 0
    @ snim2 Я не идеален. : P Примите утешение в том факте, что грязная изменчивость не влияет на ссылочную прозрачность результата. Если вы дважды пройдете один и тот же «lastMeasurement», вы получите несвежее следующее измерение и вернете тот же результат.
Показать ещё 3 комментария
11

Да, возможно, чтобы чистая функция возвращала время, если оно дало это время в качестве параметра. Различные аргументы времени, разные результаты времени. Затем формируем и другие функции времени и объединяем их с простым словарем функций (-of-time) -трансформирования (высших порядков). Поскольку этот подход не имеет места, время здесь может быть непрерывным (независимым от разрешения), а не дискретным, значительно повышающим модульность. Эта интуиция является основой функционального реактивного программирования (FRP).

10

Я удивлен, что ни один из ответов или комментариев не упоминает коалгебры или coinduction. Как правило, coinduction упоминается при рассуждении о бесконечных структурах данных, но она также применима к бесконечному потоку наблюдений, например, к регистру времени на CPU. Коалгебра моделирует скрытое состояние; и модели монументации, соблюдающие это состояние. (Нормальные индукционные модели, строящие состояние.)

Это горячая тема в реактивном функциональном программировании. Если вас интересуют такие вещи, прочтите следующее: http://digitalcommons.ohsu.edu/csetech/91/ (28 стр.)

  • 3
    И как это связано с этим вопросом?
  • 4
    Ваш вопрос был о моделировании поведения, зависящего от времени, чисто функциональным способом, например, функцией, которая возвращает текущие системные часы. Вы можете либо пропустить что-то эквивалентное монаде IO через все функции и их дерево зависимостей, чтобы получить доступ к этому состоянию; или вы можете моделировать состояние, определяя правила наблюдения, а не конструктивные правила. Вот почему моделирование сложного состояния индуктивно в функциональном программировании кажется таким неестественным, потому что скрытое состояние действительно является коиндуктивным свойством.
Показать ещё 1 комментарий
10

Да! Ты прав! Now() или CurrentTime() или любая сигнатура метода такого аромата не имеют ссылочной прозрачности в одном направлении. Но по команде компилятору он параметризуется вводом системных часов.

В результате вывода Now() может выглядеть не следующим ссылочным прозрачностью. Но фактическое поведение системных часов и функции поверх него придерживается реляционная прозрачность.

10

Да, функция получения времени может существовать в FP, используя слегка измененную версию на FP, известную как нечистая FP (по умолчанию или основная - чистая FP).

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

Немногие языки программирования FP имеют такую ​​встроенную в них примесную функцию, что нелегко выделить, какой код является нечистым и который является чистым (например, F # и т.д.), а некоторые языки FP удостоверяются, что когда вы делаете нечистые вещи, которые код явно выделяется по сравнению с чистым кодом, например Haskell.

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

  • 1
    «В конце концов, программное обеспечение, которое не взаимодействует с внешним миром, не является чем-то полезным, кроме как делать некоторые математические вычисления». Насколько я понимаю, даже в этом случае ввод в вычисления будет жестко запрограммирован в программе, что также не очень полезно. Как только вы захотите прочитать входные данные для своих математических вычислений из файла или терминала, вам понадобится нечистый код.
  • 1
    Как насчет входных данных в качестве аргументов командной строки :)
Показать ещё 7 комментариев
7

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

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

Чистый язык не создает или не зависит от побочных эффектов, а нечистый язык использует их повсюду.

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

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

-- this is a pure function, written in functional style.
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

-- This is an impure wrapper around the pure function, written in imperative style
-- It depends on inputs and produces outputs.
main = do
    putStrLn "Please enter the input parameter"
    inputStr <- readLine
    putStrLn "Starting time:"
    getCurrentTime >>= print
    let inputInt = read inputStr    -- this line is pure
    let result = fib inputInt       -- this is also pure
    putStrLn "Result:"
    print result
    putStrLn "Ending time:"
    getCurrentTime >>= print
  • 4
    Было бы полезно, если бы вы могли решить конкретную проблему получения времени и немного объяснили, в какой степени мы считаем значения и результаты IO чистыми.
  • 0
    Фактически, даже 100% чистые программы нагревают процессор, что является побочным эффектом.
1

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

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

Пример: clock_t c = time(NULL); printf("%d\n", c + 2); в C, vs. main = getCPUTime >>= \c -> print (c + 2*1000*1000*1000*1000) в Haskell. Оператор >>= используется для составления действий, передавая результат первой функции, приводящей к второму действию. Это довольно загадочно, компиляторы Haskell поддерживают синтаксический сахар, что позволяет нам написать последний код следующим образом:

type Clock = Integer -- To make it more similar to the C code

-- An action that returns nothing, but might do something
main :: IO ()
main = do 
    -- An action that returns an Integer, which we view as CPU Clock values
    c <- getCPUTime :: IO Clock 
    -- An action that prints data, but returns nothing
    print (c + 2*1000*1000*1000*1000) :: IO ()

Последний выглядит весьма императивным, не так ли?

1

Если да, то как он может существовать? Разве это не нарушает принцип функциональное программирование? Это особенно нарушает Прозрачность

Это не существует в чисто функциональном смысле.

Или, если нет, то как узнать текущее время в функциональном программирование?

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


Для Haskell существует понятие "действия IO", которое представляет собой тип, который может быть выполнен для выполнения некоторого процесса ввода-вывода. Поэтому вместо ссылки на значение time мы ссылаемся на значение IO Time. Все это было бы чисто функционально. Мы не ссылаемся на time, но что-то вроде строк "читаем значение регистра времени".

Когда мы на самом деле выполняем программу Haskell, действие IO действительно будет иметь место.

Ещё вопросы

Сообщество Overcoder
Наверх
Меню