Использование схемы и ленивых вычислений для формирования бесконечных списков

Инструменты

В этом руководстве я буду использовать язык программирования Racket. Это значительно расширенный диалект схемы, но большая часть этого кода должна быть непосредственно перенесена на схему R5RS-R7RS. Я считаю, что концепции могут быть полезны и реализованы вне схемы, это просто инструмент, который я выбрал для использования. В Haskell встроены бесконечные списки, другие Lisps и функциональные языки, такие как Javascript, безусловно, могут использоваться для реализации бесконечных списков. Даже Python может создавать бесконечные списки, используя похожие или совершенно разные методы.

Ленивая оценка и потоки

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

Задержка оценки

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

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

Потоки

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

Бесконечные списки!

простейший бесконечный поток — это поток всех единиц. Это определяется как

ones фактически является бесконечным списком. Есть два способа объяснить происходящее.

Декларативный подход

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

Предположим, что существует поток бесконечных единиц. Назовем его ones. Голова этого потока должна быть 1 по определению. Таким образом, мы довольно легко получаем (define ones (stream-cons 1 _)), но теперь нам нужно выяснить, что у него за хвост. Если в потоке есть бесконечные единицы, его хвост должен быть потоком бесконечных единиц. К счастью, у нас уже есть поток таких: ones ! Получаем (define ones (stream-cons 1 ones))

Императивный подход

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

Давайте посмотрим на определение ones :(define ones (stream-cons 1 ones)) . Это определение рекурсивно — оно ссылается само на себя. Что, если мы заменим ones в выражении его определением. Поскольку мы только заменяем переменную на ее определение, это приведет к эквивалентному выражению.

(equal? ones (stream-cons 1 ones)) — по определению
(equal? ones (stream-cons 1 (stream-cons 1 ones))) — по определению единиц
(equal? ones (stream-cons 1 (stream-cons 1 (stream-cons 1 ones)))) — по определению единиц

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

Потоковое добавление

Давайте определим функцию stream-add, которая сканирует два потока, складывает вместе соответствующие элементы и возвращает новый поток.

Теперь поток двоек

Рассуждая декларативно, добавляя два потока своих результатов ко всем двойкам. Рассуждая императивно, stream-add складывает вместе начало каждого потока (1 + 1 = 2), а затем добавляет хвосты. Решка тоже единица, так что это просто 1 + 1 = 2 до конца.

Возрастающая сложность

Пока что наши бесконечные списки хоть и бесконечны, но не очень интересны. Попробуем сделать поток натуральных чисел.

Декларативное рассуждение

Предположим, что поток натуральных чисел существует. Назовем его nats. Заголовок этого потока должен быть равен 1 по определению. Таким образом, мы довольно легко получаем (define nats (stream-cons 1 _)), но теперь нам нужно выяснить, что у него за хвост. Хвост списка теперь должен быть '(2 3 4 5 6 7 8 …). Этот список представляет собой сложение потока натуральных чисел и потока единиц. К счастью для нас, у нас уже есть и то, и другое. Таким образом, мы получаем (define nats (stream-cons 1 (stream-add ones nats)))

Императивное рассуждение

Давайте посмотрим на определение nats:(define nats (stream-cons 1 (stream-add ones nats))) . Это определение рекурсивно — оно ссылается само на себя. Что, если мы заменим (stream-add ones nats))) в выражении его определением. Это создаст эквивалентное выражение.

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

Числа Фибоначчи

Здесь я думаю, что эта концепция выходит на новый уровень. Поток чисел Фибоначчи

Давайте посмотрим, почему это работает. Еще раз предположим, что поток чисел Фибоначчи существует. Назовем его fibs. Фибоначчи — это бесконечный список
'(0 1 1 2 3 5 8 13 21 ...). Давайте также посмотрим на (stream-cdr fibs) :
'(1 1 2 3 5 8 13 21 34 ...). Когда мы складываем эти два потока вместе, мы получаем '(1 2 3 5 8 13 21 34 55). Итак, (equal? (stream-add fibs (stream-cdr fibs)) (stream-cdr (stream-cdr fibs))).

Первые два элемента fibs по определению равны 0 и 1, следовательно, (define fibs (stream-cons 0 (stream-cons 1 _))). Теперь нам просто нужно выяснить, каков хвост этого потока; Другими словами, что (stream-cdr (stream-cdr fibs)). У нас уже есть определение для этого! Давайте подключим ранее обнаруженное нами свойство fibs. Получаем (define fibs (stream-cons 0 (stream-cons 1 (stream-add fibs (stream-cdr fibs))))). На мой взгляд, этот поток довольно красив, и он дает представление о потенциальной силе и элегантности функционального программирования и ленивых вычислений.

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

Продолжение

Эта история — часть первая. Вторая часть теперь здесь. Дальше идут более бесконечные списки и грандиозный финал бесконечного списка простых чисел.

Об авторе

Эрик Брейер — студент факультета компьютерных наук Университета Райса. Найти его можно на его сайте, а также на GitHub и LinkedIn.