На своём пути к функциональному миру, читаю различные книжки, пока остаётся загадкой пара вопросов. Если можно, поясните.
В чисто функциональном языке (возьмём для примера Хаскель) все переменные есть константы, функции детерминированы — результат вызова зависит только от её аргументов.
1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно. Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш?
2. Как возможно определить и вообще работать с явно недетерминированными функциями типа rand()?
28.08.07 08:42: Перенесено модератором из 'Философия программирования' — Odi$$ey
Здравствуйте, johny5, Вы писали:
J>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно. Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш?
Как и в любом императивном — Map, Array, List
J>2. Как возможно определить и вообще работать с явно недетерминированными функциями типа rand()?
С такой сигнатурой:
rand :: StateType -> (Int, StateType)
функция становится детерминированной. Если само значение состояния (типа StateType) нам не нужно, остается только его тип. Так получаются монады.
J>На своём пути к функциональному миру, читаю различные книжки, пока остаётся загадкой пара вопросов. Если можно, поясните.
J>В чисто функциональном языке (возьмём для примера Хаскель) все переменные есть константы, функции детерминированы — результат вызова зависит только от её аргументов.
J>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно.
в чистом ФП функция не может делать никакой работы. Это всего лишь декларация соответствия результата параметрам. Поэтому о скорости ее работы говорить не имеет смысла.
Это реализация делает некоторую работу по собственно вычислению всего, чего надо. J>Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш?
Среда исполнения и должна решать, что такое кэш и что такое вызов.
Умные компиляторы ухитряются, к примеру, экономить вызовы при переборе чисел Фибоначчи, так, чтобы вместо O(2^n) каждое число отдавалось за О(1). Именно благодаря использованию чего-то вроде кэша вызовов.
J>2. Как возможно определить и вообще работать с явно недетерминированными функциями типа rand()?
Приходится вводить состояние. Функции типа rand на самом деле жестко детерминированы. В процедурном программировании состояние rand хранится в скрытой глобальной переменной; в ООП — в экземпляре ГСЧ. В ФП придется передавать состояние явно (либо воспользоваться монадами или еще каким-нибудь мега-способом): rand(current_state)->(random, next_state).
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: Немного поясните про чистую функциональщину
Здравствуйте, johny5, Вы писали:
A>>С такой сигнатурой:
A>>rand :: StateType -> (Int, StateType)
A>>
функция становится детерминированной. Если само значение состояния (типа StateType) нам не нужно, остается только его тип. Так получаются монады.
J>Интересно, а, например, в Clean нет никаких монад, и как там?
в clean каждая императивная операция получает и возвращает доп. аргумент, который рассматривается как "состояние мира"
монады сами по себе — это только способ декларации императивности. реализация же их либо использует тот же фокус с "состоянием мира" (в большинстве компиляторов), либо continuations (в hbc). почитай http://haskell.org/haskellwiki/IO_inside
Здравствуйте, johny5, Вы писали:
J>В чисто функциональном языке (возьмём для примера Хаскель) все переменные есть константы, функции детерминированы — результат вызова зависит только от её аргументов.
В чисто функциональном языке вообще нет переменных. Есть только именованные значения. Это сахар, вообще можно писать в чисто функциональном стиле на одних комбинаторах, но это не удобно
J>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно. Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш?
Как уже писал Sinclair, об этом должен заботиться компилятор. Причём, ИМХО, это должен делать не только компилятор, но и рантайм, который считает статистику вызовов и т.д., т.к. на этапе компиляци не всегда можно предсказать такие вещи.
... << RSDN@Home 1.2.0 alpha rev. 710>>
Re[2]: Немного поясните про чистую функциональщину
J>>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно. S>в чистом ФП функция не может делать никакой работы. Это всего лишь декларация соответствия результата параметрам. Поэтому о скорости ее работы говорить не имеет смысла. S>Это реализация делает некоторую работу по собственно вычислению всего, чего надо. J>>Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш? S>Среда исполнения и должна решать, что такое кэш и что такое вызов.
Т.е. реализовать ручное кэширование в случае необходимости будет невозможно?
Re[3]: Немного поясните про чистую функциональщину
J>>>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно. S>>в чистом ФП функция не может делать никакой работы. Это всего лишь декларация соответствия результата параметрам. Поэтому о скорости ее работы говорить не имеет смысла. S>>Это реализация делает некоторую работу по собственно вычислению всего, чего надо. J>>>Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш? S>>Среда исполнения и должна решать, что такое кэш и что такое вызов.
J>Т.е. реализовать ручное кэширование в случае необходимости будет невозможно?
Просто насколько я понимаю, для ленивого языка, коим является Haskell, само понятие "кэширование результатов вызова функции" является неприменимым, т.к. мы не знаем, в какой точно момент понадобится результат вычисления, и соответственно, когда этот результат будет вычислен. В принципе, можно получить желаемый результат, путем strict вычисления нужной функции, но вот нужно ли это...
Для строгих языков, типа OCaml, подобное вполне реализуемо, вот например обсуждение...
--
WBR, Alexander
Re[3]: Немного поясните про чистую функциональщину
J>Т.е. реализовать ручное кэширование в случае необходимости будет невозможно?
это можно сделать двумя способами:
— использовать lazy семантику вычисления. фактически, laziness — это само по себе система кеширования однажды вычисленных значений, надо просто уметь ею управлять
— использовать unsafePerformIO
что касается первого — вот типичный пример из базовой библиотеки GHC:
power x n | x==2 && (n>=0 && n<=317) = powers2!n
| otherwise = x^n
powers2 :: Array Int Double
powers2 = array (0,318) [2^n | n <- [0..317]]
благодаяр laziness, значения в массиве powers2 вычисляются только по необходимости и запоминаются. степени же, не включённые в этот массив, вычисляются каждый раз заново. для более сложных ключей аналогиынйм образом можно прменить Map или Trie
Люди, я люблю вас! Будьте бдительны!!!
Re[4]: Немного поясните про чистую функциональщину
DD>Просто насколько я понимаю, для ленивого языка, коим является Haskell, само понятие "кэширование результатов вызова функции" является неприменимым, т.к. мы не знаем, в какой точно момент понадобится результат вычисления, и соответственно, когда этот результат будет вычислен.
порядок вычисления в хаскеле определён. недавно об этом рассказывали в cafe. способ вычисления — graph reduction, т.е. подставновка вместо левой части определения функции правой части. при этом вычисляется всегда самый наружный вызов, для которого уже достаточно данных
вот кусочек из моего письма:
simple example: consider evaluation of "head [1..]". [1..] may be
represented with the following recursive function:
list n = n:list n+1
so we have "head (list 1)" where head defined as
head (x:_) = x
let's evaluate expression:
head (list 1) =>
head (1:list 2) =>
1
as you see, "list 2" was just dropped during evaluation.
но лучше поглядеть в оригинале — там высказывались настоящие теоретики, не мне чета
Здравствуйте, johny5, Вы писали:
J>В чисто функциональном языке (возьмём для примера Хаскель) все переменные есть константы, функции детерминированы — результат вызова зависит только от её аргументов.
Хорошо бы ещё взять для примера ML — потому что один ленивый, второй энергичный. (Надо сказать, каждый из них умеет делать и то, и другое).
J>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно. Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш?
Есть три разных способа редукции выражений.
Какая-то там теорема Чёрча показывает, что все эти способы — возможно, за разное время (вплоть до бесконечного ), — приводят к одному результату.
f(x) = expr(....., x, ....., x, .....) -- аргумент используется несколько раз
f(g()) -- подставим туда нечто вычисляемое
-- подставить копии (лямбда-исчисление на строках)
f(g())
= expr(....., g(), ....., g(), .....)
-- вычислить и подставить <ссылку на> результат (путь ML)
f(g())
= let v=g() in f(v)
= let v=g() in expr(....., v, ....., v, .....)
-- подставить ссылку на одно и то же ленивое значение (путь Haskell)
-- которое вычислится единожды, когда потребуется первый раз
f(g())
= expr(....., v, ....., v, .....) where v=g()
Поэтому ни в ML, ни в Haskell не нужно делать фанатичную мемоизацию.
Другое дело, что если написать
let
x = g()
y = g()
in f(x,y)
то компилятор+рантайм может догадаться, а может не догадаться, что x==y и, соответственно, выполнит редукцию g() единожды или дважды.
Вот тут уже нужно смотреть, стоит ли доверять интеллекту компилятора и объёму кэша рантайма, или переписать руками.
Говорят, что некоторые диалекты Пролога работают, как суперкомпьютер Крей-1: вычисляют бесконечный цикл за 6 секунд.
% Question of Life, Universe and Everything
qlue(X) :- qlue(X).
qlue(42).
?- qlue(N)
% благодаря мемоизации распознано зацикливание, и второй раз уже машина поехала по второй ветке
N=42
Yes
Хотя для большинства реализаций это не так.
J>2. Как возможно определить и вообще работать с явно недетерминированными функциями типа rand()?
Во-первых, можно предположить, что функция всё-таки детерминирована
rand :: RandSeed -> (Int, RandSeed)
srand :: Int -> RandSeed
r0 = srand 0
(x1,r1) = rand r0
(x2,r2) = rand r1
-- осталось только протащить нитку из последовательно вычисляемых r_k через все функции
-- например,
randoms :: Int -> RandSeed -> ([Int], RandSeed)
randoms 0 r0 = ([],r0)
randoms n r0 =
let
(x,r1) = rand r0
(xs,rn) = randoms r1
in ((x:xs),rn)
(xs1,_) = randoms r2
(xs2,_) = randoms r2 -- новая серия (повторяет предыдущую)
Это подход монады State.
Во-вторых, недетерминированная функция — это функция со скрытым параметром World, природа которого не поддаётся расшифровке.
Монада IO в Хаскеле — это, по сути, монада State, только намертво засахаренная (чтобы нельзя было хакнуть вселенную и запустить два параллельных потока вычислений над копиями мира).
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: Немного поясните про чистую функциональщину
К>Хорошо бы ещё взять для примера ML — потому что один ленивый, второй энергичный. (Надо сказать, каждый из них умеет делать и то, и другое).
по-моему, не столько делать, сколько эмулировать через всякие "состояния мира"
К>Другое дело, что если написать К>
К>let
К> x = g()
К> y = g()
К>in f(x,y)
К>
К>то компилятор+рантайм может догадаться, а может не догадаться, что x==y и, соответственно, выполнит редукцию g() единожды или дважды. К>Вот тут уже нужно смотреть, стоит ли доверять интеллекту компилятора и объёму кэша рантайма, или переписать руками.
дело не в интеллекте. представь себе, что результат g() — список из миллиарда элементов, а f=(++) т.е. безопасно соптимизировать это можно только если x имеет примитивный тип (и следовательно его значение не превосходит по занимаемой памяти thunk для вычисления g() )
Здравствуйте, Константин Л., Вы писали:
КЛ>Здравствуйте, johny5, Вы писали:
КЛ>[]
КЛ>че то меня начинает раздражать эта мода на "чистую" функциональщину. Эдакий гламур в программинге, от которого в чистом виде нету ничего хорошего.
а мода на применение компьютеров уже не раздражает?
Здравствуйте, johny5, Вы писали:
J>В чисто функциональном языке ...
Нет таких языков. Разве что лямбда исчисления Чёрча, но это не язык программирования.
Во всех остальных состояние в том или ином виде (зачастую очень завуалированном) есть. Кое что умеют делать компиляторы (оптимизировать). Где-то используется магия вроде монад.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Немного поясните про чистую функциональщину
Здравствуйте, BulatZiganshin, Вы писали:
К>>то компилятор+рантайм может догадаться, а может не догадаться, что x==y и, соответственно, выполнит редукцию g() единожды или дважды. К>>Вот тут уже нужно смотреть, стоит ли доверять интеллекту компилятора и объёму кэша рантайма, или переписать руками.
BZ>дело не в интеллекте. представь себе, что результат g() — список из миллиарда элементов, а f=(++) т.е. безопасно соптимизировать это можно только если x имеет примитивный тип (и следовательно его значение не превосходит по занимаемой памяти thunk для вычисления g() )
Вот именно, что в интеллекте.
Глупый рантайм — не мемоизирует вообще ничего, расходуя время.
Деятельно-глупый — мемоизирует всё подряд, расходуя память (и время тоже).
Умный — пребывает в дао, находя равновесие между крайностей.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: Немного поясните про чистую функциональщину
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, johny5, Вы писали:
J>>В чисто функциональном языке ...
VD>Нет таких языков. Разве что лямбда исчисления Чёрча, но это не язык программирования.
VD>Во всех остальных состояние в том или ином виде (зачастую очень завуалированном) есть. VD>Кое что умеют делать компиляторы (оптимизировать). Где-то используется магия вроде монад.
По-моему, чистый функциональный язык не тот, где нет состояние, а тот, где нет побочных эффектов.
Побочный эффект, это что-либо, что не является преобразованием аргумента в результат.
Соответственно, чтобы язык был чисто функциональный надо, чтобы состояние было в качестве аргумента и в качестве результата.
По-моему, так и делается в clean, нанапример.
А IO монада в haskell, насколько я понял, состоит в том, что функция возвращает не состояние, а функуцию, которая для текущего состояние мира вычисляет действие с ним. А использование этой функции происходит за пределами языка haskell.
Таким образом, они оба чистые.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: Немного поясните про чистую функциональщину
no4>Соответственно, чтобы язык был чисто функциональный надо, чтобы состояние было в качестве аргумента и в качестве результата.
no4>По-моему, так и делается в clean, нанапример.
это не состояние, а фиктивный аргумент, пощволяющий управлять последоватенльностью исполнения. подробности в http://haskell.org/haskellwiki/IO_inside
no4>А IO монада в haskell, насколько я понял, состоит в том, что функция возвращает не состояние, а функуцию, которая для текущего состояние мира вычисляет действие с ним. А использование этой функции происходит за пределами языка haskell.
я чуть выше написал — реализация монады IO в большинстве хаскеловских компиляторов точно такая же, как в clean. разница только в том, что в clean это *спецификация*, а в хаскеле — одна из возможных *реализаций*
Люди, я люблю вас! Будьте бдительны!!!
Re[3]: Немного поясните про чистую функциональщину
Здравствуйте, no4, Вы писали:
no4>По-моему, чистый функциональный язык не тот, где нет состояние, а тот, где нет побочных эффектов.
Если есть состояние, то его надо менять. Изменение дает побочные эффекты.
В любмо случае языков без побочных эффектов тоже небывает. Тот же Хаскель содержит опасные манады.
no4>А IO монада в haskell, насколько я понял, состоит в том, что функция возвращает не состояние, а функуцию, которая для текущего состояние мира вычисляет действие с ним. А использование этой функции происходит за пределами языка haskell.
no4>Таким образом, они оба чистые.
Ага щас блин. А разные ансэйфперформио и т.п.?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Немного поясните про чистую функциональщину
), — приводят к одному результату.
Перекуём баги на фичи!
т.е. безопасно соптимизировать это можно только если x имеет примитивный тип (и следовательно его значение не превосходит по занимаемой памяти thunk для вычисления g() )
