?

Log in

No account? Create an account
Что такое Haskell: часть 3 - Лямбда - функциональное программирование [entries|archive|friends|userinfo]
Лямбда - функциональное программирование

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Что такое Haskell: часть 3 [Jan. 2nd, 2006|10:03 pm]
Лямбда - функциональное программирование

ru_lambda

[avva]
[Tags|]

Предыдущие выпуски:

Что такое Haskell: часть 1
Что такое Haskell: часть 2

Продолжаю идти по списку основных черт Haskell.

  • non-strict semantics / нестрогая семантика

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

    На самом деле, когда говорят "нестрогая семантика", обычно имеют в виду то же самое, что ленивое вычисление (lazy evaluation). На практике, более того, второй термин чаще используется. Пуристы их различают, но я не буду входить в эти очень теоретические детали, и поговорю поэтому о ленивом вычислении.



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

    Посмотрим на следующий псевдокод, опять-таки на C:

    for (i=0; i < 10; i++)
    some_array[i] = some_func(i);
    .....
    for (i=0; i< 5; i++)
    printf("some_array[i]: %d\n", some_array[i]);

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

    Представьте себе на секунду, что вы - компилятор C, причём очень умный компилятор, практически всевидящий. У вас есть полный контроль над тем, какую память выделять под массив и как компилировать, и вы подделываете всё так (не обращая внимания на реальные типы и ограничения языка C), что в первом цикле в каждую клетку массива some_array записывается не результат выполнения some_func(i). Вместо этого вы пишете туда пометку себе на будущее, что в этом месте должен стоять результат вычисления функции some_func (пишете её адрес) с аргументом i (пишете аргумент), но на самом деле эту функцию не вызываете. А потом, когда во втором цикле some_array[i] должен передаваться функции printf для распечатки, и вы не можете больше откладывать его вычисление, вы действительно в этот самый момент компилируете вызов some_func(i) и умело подставляете результат в список аргументов printf. Что вы выиграли таким образом? Ну ясно что: функция вызывалась только 5 раз, а не 10, потому что половина её вызовов так никогда и не понадобилась. Если её вычисление занимает много времени и ресурсов, то выигрыш налицо. Программисту не пришлось даже задумываться о том, понадобятся или нет некоторые вызовы функции. Просто те, что не понадобились, так никогда и не произошли!

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

    Но в чисто функциональном языке это как раз возможно, именно благодаря тем ограничениям, которые упомянуты выше. Именно это и называется lazy evaluation, ленивое вычисление. В языках с ленивым вычислением, таких, как Haskell, собственно работа функции почти никогда не происходит именно там, где она "написана". Любой вызов функции "запоминается" и тянется шлейфом по мере работы программы. С точки зрения кода мы, казалось бы, давно уже получили результат функции, записали его, скажем, в список, этот список, может быть, отсортировали, передали его ещё одной функции... А на самом деле всё это время там стоит не этот результат, а пометка на будущее, как его получить, когда припрёт и откладывать дальше уже будет невозможно. Например, когда нужно, наконец, вывести это куда-то наружу пользователю, но есть и другие ситуации; в частности, программист может специально заставить какое-то выражение вычисляться сразу, а не откладываться, если это ему нужно. Но по умолчанию и обычно — всё откладывается до предела. И при этом (важно!) программисту не нужно об этом думать, не нужно, за исключением относительно редких случаев, прослеживать в уме, что когда вычисляется. Оно просто происходит само собой, а свойства функций гарантируют ему, что с одной стороны он получит правильный результат, когда он будет нужен, а с другой - ненужные вычисления просто не произойдут никогда.

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

    Вернёмся ненадолго к этому самому примеру на C. Изменим первый цикл, который заполняет массив, так, чтобы он вообще стал бесконечным циклом:

    for (i=0;;i++)
    some_array[i] = some_func(i);

    Этот цикл никогда не завершится. Если запустить его на C, программа зависнет или упадёт (от переполнения массива и испорченной памяти). Но вернёмся к нашей фантазии о всевидящем и всемогущем компиляторе. Представьте себе, что компилятор настолько умён, что он не просто не вызывает some_func(i) для каждого элемента массива, а только "пометку" вставляет. Представьте себе, что он и сам цикл не запускает, пока кому-то не понадобятся элементы массива! Каким-то образом он знает, что цикл используется именно для заполнения этого массива. И вот, только когда кому-то понадобится some_array[0], он пробежит цикл первый раз. Кто-то попросит some_array[1] - пробежит его ещё раз. Захочется кому-то перескочить сразу к some_array[5] - пробежит ещё 4 раза. Но ни разу не зайдёт по-настоящему в бесконечный цикл, а только будет пробегать его снова или снова ленивым образом - когда нужен очередной элемент того, что он делает.

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

    Вот пример из Haskell. Я предполагаю, что мы используем ghc, но другие компиляторы/интерпретаторы тоже подойдут. Запишите в какой-то файл, скажем foo.hs, строку "list = [1..]" . Теперь запустите "ghci foo.hs". Интерпретатор запустится, и заодно скомпилирует и запустит ваш файл, и в результате определит ('=' означает определение новой функции с именем, в отличие от символа \, определяющего безымянную функцию, как мы видели раньше) функцию list, которая не принимает никаких аргументов, и возвращает бесконечный список [1,2,3,....] и так до бесконечности.

    На самом деле, как мы теперь понимаем, функция list не возвращает бесконечный список. Она возвращает объект, в котором записано рекурсивное правило того, как строить этот список дальше и дальше, сколько понадобится. Но пока его никто не попробовал полностью вычислить, принцип ленивого вычисления не мешает этому списку спокойно существовать. Наберите теперь "list", и ghci вызовет функцию и собственно попытается вычислить весь список. На экране замелькают числа 1, 2, и так далее - пока не остановите (любопытно, что памяти при этом он не расходует всё больше и больше). Нажмите ctrl-C, чтобы остановить. Теперь попробуйте набрать "take 10 list". take - стандартная функция, принимающая два аргумента: число N и список, и возвращающая первые N элементов списка. Что происходит? list - это функция, и ghci знает, что она возвращает список; но он не будет её пока вычислять, а "сделает пометку". Дальше идёт take, и он записывает себе, что нужно когда-нибудь будет вычислить её с аргументами 10 и list (то, что вернёт list, если её запустить). Наконец, он исчерпал команду, лень подошла к концу, и надо собственно вычислять. Функция take захочет "увидеть" первые 10 элементов своего второго аргумента, чтобы собрать их вместе в список и вернуть. Значит, Haskell будет теперь пытаться по одному брать первый, второй, третий и так далее элементы списка list - т.е. результата работы функции list. И получит по одному: 1, 2, 3 и так далее до 10, не входя ни разу в бесконечную рекурсию. И вернёт результат: [1,2,3,4,5,6,7,8,9,10]. И всё хорошо.

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

    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

    Эту строку тоже можно записать в какой-то файл bar.hs, потом запустить "ghci bar.hs". Теперь если просто написать fibs, функция вернёт "бесконечный" список чисел Фибоначчи, который начнёт распечатываться на экране. Если написать "take 10 fibs", то, как раньше, можно получить первые 10 чисел Фибоначчи. Как это работает? Каким образом ленивое вычисление даёт возможность написать такую странную рекурсию, и что здесь происходит?

    Сначала о функциях. В этой строке используются четыре функции. ':' берёт элемент с левой стороны и список с правой, и составляет их вместе в новый список. '+' - это обычный плюс. 'tail' - функция, берущая список и возвращающая новый список, идентичный исходному, но без первого элемента. zipWith берёт в качестве аргументов функцию и два списка, после чего составляет новый третий список, каждый элемент которого составлен из соответствующих элементов первого и второго списков в применении к ним данной функции (представьте себе молнию, zipper, которая движется по двум спискам и "соединяет" их вместе в третий с помощью данной функции).

    Все эти четыре функции вычисляются "лениво", как и обычно в Haskell.

    Что происходит, когда мы пишем, скажем, "take 10 fibs"? Начинается раскручивание "лениво" составленного вычисления. Функция take просит один за другим первый, второй... десятый элементы списка, который должна вернуть функция fibs. Haskell начинает вычислять функцию fibs, чтобы получить эти элементы. Вычисляет и видит, что вначале получается [1,1...]: список, состоящий пока из двух элементов, а дальше неизвестно что. Что дальше? Для этого начнём вычислять функцию zipWith. Не всю, конечно (мы же лентяи!), а пока только первый элемент того списка, что она вернёт, чтобы подставить его в третий элемент списка, что вернёт fibs. Функция zipWith говорит нам: мой первый элемент? Это очень просто: найдите первые элементы двух моих аргументов и подставьте их в функцию (+). Что ж, Haskell лениво переваливается по направлению к её аргументам. Ух ты: первый из них - уже знакомая функция fibs; казалось бы, вот она, бесконечная рекурсия! - но нет, мы же хотим только первый элемент того, что она вернёт, а он у нас к этому моменту уже есть: 1. Подобным образом tail fibs попросит у нас второй элемент того, что вернёт fibs, а это у нас тоже есть: тоже 1. Наконец, + сложит их вместе и вернёт 2, которое становится на следующее место в списке результата fibs: [1,1,2...]. Идём дальше: теперь мы хотим четвёртый элемент fibs, он же второй элемент того, что возвращает zipWith. Не проблема, говорит zipWith: смотрите на вторые элементы двух моих аргументов. Они к этому времени у нас уже есть: это 1 и только что подставленная 2; складываем, получаем 3: [1,1,2,3...] Следующий элемент будет 2+3=5, и так далее, на каждом ленивом пробеге рекурсии мы проходим ещё одну позицию в списках-аргументах zipWith, вычисляем следующее число, оно становится на новую позицию в списке-значении fibs, и на следующем пробеге уже будет использовано для сложения. Обратите внимание, что всё это очень эффективно: каждое число Фибоначчи вычисляется только один раз. А когда мы дойдём до 10 элементов, функция take будет удовлетворена, и кажущаяся бесконечной рекурсия fibs благополучно оборвётся.

    Вот такое оно, ленивое вычисление.

    Продолжение следует.
  • linkReply

    Comments:
    [User Picture]From: stas
    2006-01-02 08:26 pm (UTC)
    А ленивый факториал будет что-то вроде:

    let fact = 1 : zipWith (*) fact [1..]

    (Reply) (Thread)
    [User Picture]From: stas
    2006-01-02 08:33 pm (UTC)
    Кстати вопрос. Мне ведь на самом деле в вышеуказанном примере значения факториалов предыдущих не нужны. Это я его так по аналогии написал. Аналогичным образом, для чисел Фибоначчи мне не нужны все предыдущие числа как только я их использовал. Можно ли мне как-то это записать так, чтобы он забывал эти ненужные числа, как только в них отпала нужда - т.е. чтобы был не целый длинный список, а только то, что нужно прямо сейчас?
    (Reply) (Parent) (Thread)
    [User Picture]From: stas
    2006-01-02 08:39 pm (UTC)
    Кажается я сам нашёл ответ. fibs !! 239 или fact !! 239 должны приводить по уму именно к такому эффекту (!! это взятие элемента списка по номеру).
    (Reply) (Parent) (Thread)
    [User Picture]From: kozodoev
    2006-01-03 10:03 am (UTC)
    right
    Memoizing Haskell programmer:
    facs = scanl (*) 1 [1..]
    fac n = facs !! n
    (Reply) (Parent) (Thread)
    [User Picture]From: avva
    2006-01-02 08:33 pm (UTC)
    Точно.
    (Reply) (Parent) (Thread)
    From: (Anonymous)
    2006-01-02 08:40 pm (UTC)
    >Что происходит, когда мы пишем, скажем, "tail 10 fibs"
    take, казалось бы
    (Reply) (Thread)
    [User Picture]From: avva
    2006-01-02 08:41 pm (UTC)
    описка. Спасибо, исправил!
    (Reply) (Parent) (Thread)
    [User Picture]From: aburachil
    2006-01-02 08:51 pm (UTC)
    Опять два вопроса:

    fst А Вы точно уверены, что если попросить напечатать ВСЕ числа Фибоначчи, то память не будет сжираться? (в принципе, из-за того, что вывод на экран ужасно медленный, это было бы не так уж и заметно)

    snd Представьте себе функцию fake_take которая в принципе делает то же самое, что и take, но начинает вычисления не с 1-го элемента, а с десятого. Правильно я понимаю, что в таком случае, программа будет тратить экспоненциально много времени (если предпологать, что ответ на мой вопрос fst положительный)?
    (Reply) (Thread)
    From: ex_ex_zhuzh
    2006-01-02 09:50 pm (UTC)
    1. Не будет, сборщик мусора удалит ненужные элементы списка. Память будет медленно расти, но это только из-за того, что сами числа длинные, и их надо где-то хранить, тут уж никуда не денешься.
    2. Eсть функция drop n, возвращающая все элементы списка, кроме первых n, и с ней тоже все в порядке.
    (Reply) (Parent) (Thread)
    From: dizzy57
    2006-01-02 10:29 pm (UTC)
    В связи с take и drop возникает несколько вопросов: можно ли как-нибудь объяснить компилятору, что две функции коммутируют (f . g == g . f), умеет ли он, глядя на функцию определять это сам, и, главное, будет ли выгода от таких объявлений(т.е. переставит ли он трудновычислимую функцию в то место, где ей придётся считать меньше всего)? =)
    (Reply) (Parent) (Thread)
    From: ex_ex_zhuzh
    2006-01-02 10:39 pm (UTC)
    1. Стандартным образом нельзя, но ghc, как всегда, поддерживает ;) См. http://www.haskell.org/ghc/docs/6.4/html/users_guide/rewrite-rules.html
    2. Сомневаюсь.
    3. Определенно нет.
    (Reply) (Parent) (Thread)
    [User Picture]From: omerm
    2006-01-03 03:53 pm (UTC)
    y f = f (y f)
    (Reply) (Thread)
    [User Picture]From: bugabuga
    2006-03-01 02:46 am (UTC)
    Любопытно... Сразу подумалось, что компилятор строит большой неконечный граф-автомат из данных ему функций, а потом оббегает его для данных аргументов :)
    Глупость скорее всего сказал. Надо перечитать теорию графов :)
    (Reply) (Thread)