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

Question

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

Например, рассмотрим это:

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

И да и нет.

Различные функциональные языки программирования решают их по-разному.

В Хаскеле (очень чистом) все это должно происходить в чем-то, что называется монадой ввода / вывода - смотрите здесь.

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

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

Как отметил в своем комментарии Джеффри Бурка: вот хорошее введение в монаду ввода / вывода прямо из вики Haskell.

Answer 3

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

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-Примечание, которое более привычно для императивного программиста:

do currTime <- now
   putStrLn currTime

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

В C# вы можете реализовать это так:

// 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
}

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

Answer 7

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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

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

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

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

Answer 11

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

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

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

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

Чтобы быть вообще полезной, программа должна быть как минимум нечистой. Один из способов сделать чистую программу полезной - поместить ее в тонкую нечистую оболочку. Как эта непроверенная программа на 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

Answer 12

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

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

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

Пример: clock_t c = time(NULL); printf("%d\n", c + 2); в С, против main = getCPUTime >>= \c -> print (c + 2*1000*1000*1000*1000) в Хаскеле. Оператор >>= используется для составления действий, передавая результат первого в функцию, приводящую ко второму действию. Это выглядит довольно загадочно, компиляторы 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 ()

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

Answer 13

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

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

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

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

---

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

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

Answer 14

На него можно ответить, не вводя другие концепции ФП.

Возможность 1: время как аргумент функции

Язык состоит из

1. ядро языка и
2. стандартная библиотека.

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

Используя обозначение OP, если у вас есть функция

f(t) = t*v0 + x0; // mathematical function that knows current time

Они попросили бы стандартную библиотеку получить текущее время, скажем 1.23, и вычислить функцию с этим значением в качестве аргумента f(1.23) (или просто 1.23*v0 + x0, ссылочная прозрачность!). Таким образом, код узнает текущее время.

Возможность 2: время как возвращаемое значение

Отвечая на вопрос OP:

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

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

f(s) = t(s)*v0 + x0; // mathematical function t(s) returns current time

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

Возможность 3: функциональное реактивное программирование

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

(x, t2) = t(); // it's x o'clock now
...
(x2, t3) = t2(); // now it's already x2 o'clock
...
t(); x; // both evaluate to the initial time, referential transparency!

---

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

Answer 15

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

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

       val time_now    : () -> time
fun time_now () = ...

для подходящего определения time, конечно.

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

Это возможно в Standard ML, если вы будете осторожны...

Например, рассмотрим это:

        f(x,y) = x*x + y;

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

Ага! Это требует смены языка - давайте попробуем... Миранда(R)!

Как вы правильно догадались, что-то вроде:

       unit ::= Unit

time_now :: unit -> time

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

       time_taken x        =  t1 $seq x $seq t2 $seq (x, tdiff)
                       where
                           t1      =  time_now u1
                           t2      =  time_now u2
                           tdiff   =  t2 $minus_time t1
                           u1:u2:_ =  ...               || what goes here?

где:

       minus_time :: time -> time -> time

и time уже определены в другом месте.

(Примечание: пока он здесь, seqна самом деле не является последовательным на всех языках, которые его определяют...)

Но что насчет:

       times_taken xs      =  map time_taken xs

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

Предпочитая простоту, мы повторно используем изменения, внесенные в time_now - использовать разные входы для каждого вызова time_taken:

       times_taken xs      =  map2 time_taken xs us
                       where
                           us =  ...                    || what about here?

Это подразумевает:

       time_taken x u      =  t1 $seq x $seq t2 $seq (x, tdiff)
                       where
                           t1      =  time_now u1
                           t2      =  time_now u2
                           tdiff   =  t2 $minus_time t1
                           u1:u2:_ =  ...               || what goes here?

что, в свою очередь, подразумевает:

       times_taken xs u    =  map2 time_taken xs us
                       where
                           us =  ...                    || what about here?

так что times_taken также можно использовать повсюду.

Теперь о загадочном u1, u2 и us - поскольку мы добавили u как дополнительный параметр к time_taken и times_taken, давайте воспользуемся этим с помощью нового определения, например parts:

       time_taken x u      =  t1 $seq x $seq t2 $seq (x, tdiff)
                       where
                           t1      =  time_now u1
                           t2      =  time_now u2
                           tdiff   =  t2 $minus_time t1
                           u1:u2:_ =  parts u

times_taken xs u    =  map2 time_taken xs us
                       where
                           us =  parts u

Пока мы это делаем, давайте также назовем тип всех этих u-значения. поскольку time_now использует внешний источник информации, как насчет:

       time_now :: outside_information -> time
parts    :: outside_information -> [outside_information]

... да - если подумать, давайте просто будем использовать инициалы:

       time_now :: oi -> time
parts    :: oi -> [oi]

Намного лучше! Это также позволяет нам предоставлять time_taken и times_taken с собственными сигнатурами типов:

       time_taken  ::   * -> oi -> (*, time)
times_taken :: [*] -> oi -> [(*, time)]

Это просто оставляет parts и time_now - как они будут использовать свои соответствующие oi аргументы?

Что ж, вы можете вспомнить требования для каждого oiзначение быть уникальным, чтобы все это работало. Но обычное определение:

       oi ::= ...

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

Теперь рассмотрим:

       what_time_taken     :: * -> oi -> (*, time)
what_time_taken x u =  t1 $seq x $seq t2 $seq (x, tdiff)
                       where
                           t1      =  time_now u1
                           t2      =  time_now u
                           tdiff   =  t2 $minus_time t1
                           u1:u2:_ =  parts u

Ты видел это?

В местном определении t2, time_now был применен к u, вместо (предположительно) u2 - uиспользуется дважды, в отличие от свойства одноразового использования, которое мы пытаемся сохранить. Это Миранда (R), а не Clean, поэтому нет типов уникальности, которые можно было бы использовать для отражения таких аномалий...

Эти два наблюдения предполагают oi должен быть предопределен, например char или же num - реализация могла бы затем проверить, есть ли oivalue уже было использовано, и отреагируйте соответствующим образом, например, вызовите ошибку времени выполнения, чтобы остановить программу-нарушитель (подумайте, как теперь поступить с делением на ноль). Самый простой способ time_now и parts может получить доступ к этой проверке времени выполнения, чтобы оба они также были предопределены (например, ord или же div) - вместе с oi, они образуют абстрактный тип данных, предоставляемый реализацией.

Разобравшись с этим, давайте объединим все вместе:

       || oi ADT
parts    :: oi -> [oi]
time_now :: oi -> Time

minus_time :: time -> time -> time  || defined elsewhere

time_taken          :: * -> oi -> (*, time)
time_taken x u      =  t1 $seq x $seq t2 $seq (x, tdiff)
                       where
                           t1      =  time_now u1
                           t2      =  time_now u2
                           tdiff   =  t2 $minus_time t1
                           u1:u2:_ =  parts u

times_taken         :: [*] -> oi -> [(*, time)]
times_taken xs u    =  map2 time_taken xs us
                       where
                           us =  parts u

К настоящему времени вы, вероятно, уже заметили, как использование parts, uи т. д. образуют дерево, встроенное в times_taken и times_taken, с его листьями в приложениях time_now. Это говорит о существовании единого предкового oi значение, например:

       start_here :: oi -> unit

Мы уже знаем, что есть что-то вроде:

       start_up :: oi

бесполезен, потому что он всегда будет иметь одно и то же значение... подождите, мы пытаемся создать новый oi ценность для start_now? Это так в первую очередь!

В Miranda(R) функции могут использоваться как любое другое значение, например bool, char, или же numт.е. функции являются первоклассными ценностями. Давай просто принесем start_here новоиспеченному oiзначение внутри реализации, так как она уже выбирает, как обрабатывать ввод в зависимости от типа:

• использование кавычек для печати char значения;

• использование десятичной точки (при необходимости) для печати num значения.

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

1. оценить входное выражение, если это еще не функция;

2. создать новый oi значение;

3. применить функцию к oi значение для формирования нового входного выражения;

4. который затем отправляется обратно для дальнейшей обработки, снова в зависимости от типа.

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

Заключить:

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

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