вторник, 1 февраля 2011 г.

Функциональное программирование, неизменяемые состояния, ленивость

Сегодня проклятый день: я написал императивный код макросом loop, который изменял переменную выше в лексическом окружении и, в добавок, наступил на чрезмерную энергичность у loop. Ещё бы чуть чуть, и запутался в скобках и понадобилась статическая типизация ;)

Собственно, по-порядку:

Не мог понять, почему простейший find выдаёт неправильный результат, когда дебажный printf format, воткнутый прям перед этим find, показывал, что входные данные, получаемые вызовом функции, 100% верны, и такого результата в этой галактике получиться не может. Потом догадался вотнуть в format ещё один вызов той функции и увидел, что результат разный. После этого баг быстро нашёлся, но факт: с чистым ФП с запрещёнными сайд-эффектами такого бы не произошло.

Опечалился от собственного говнокода, давай переписывать. Вот какую неприятность у loop нашёл:

(loop for x in nil
   for y from 1
   collect y)

В этом примере оба for выполняются параллельно, но т.к. первый из них не даёт итерации, то всё тело не исполняется и loop возвращает nil.

(loop for x in nil
   for y from 1 by (1+ x)
   collect y)

Похожий, казалось бы, код, но он не выполняется, ругаясь что числа с nil'ами складывать нельзя. Шаг приращения в by вычисляется ещё до того, как развернувшийся макрос начинает смотреть, а надо ли вообще что-то делать?

Обидно, досадно. Переписал на одном reduce. Красиво, функционально, без сайд-эффектов, да ещё и работает. Но больше мусора генерит и не так оптимально в машинном плане, как loop, в котором я запутался. Я тут на сях ембеддед  пложу, и, видать, мозг всякий низкий уровень и экономия битов затуманили. В данном случае экономия идёт лесом.

Правильно всё пишут про иммутабельность, ленивые вычисления, функциональный подход и прочую казуистику. Надо гантели, что ли, купить?..

17 комментариев:

  1. Учитывая местность и климат, можно просто лопату брать побольше и потяжелее. :)

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

    ОтветитьУдалить
  3. loop действительно выглядит (и является?) каким-то монстром. Вот Scheme приучил меня либо пользоваться fold-ами, либо рекурсивными вызовами named let. Кстати, тот CL, на котором пишите, оптимизирует хвостовые вызовы? Вообще, насколько при программировании на CL кошерно закладываться на оптимизацию хвостовых вызовов?

    ОтветитьУдалить
  4. > насколько при программировании на CL кошерно
    > закладываться на оптимизацию хвостовых вызовов?

    Совсем не кошерно. Во-первых, не все реализации её поддерживают (ибо стандарт не требует), а во вторых даже те, которые поддерживают, не факт, что будут её делать. Например, SBCL при высоких отладочных режимах её не производит (http://lisper.ru/articles/sbcl-debugging).

    ОтветитьУдалить
  5. > Совсем не кошерно
    Вот черт, а я уже привык.

    ОтветитьУдалить
  6. > Просто юзай iterate.
    iterate не парацея. В нём имеет место ровно та же самая проблема - попробуй заменить в приведённом примере loop на iterate и удивись.

    По поводу "функционально": есть ещё Series из CLTL2 - совмещают декларативную запись (во многом совпадающую с функциональной) с эффективным результирующим кодом (большинство конструкций преобразуется в циклы вроде iterate).

    ЗЫ куда-то пропал мой предыдущий коммент, пишу ещё раз.

    ОтветитьУдалить
  7. Да, про Series я хотел написать пост ещё в сентябре, но что-то отвлекло. Сейчас не могу вспомнить, что там главного сказать хотел. Так черновик в драфтах и валяется ;)

    А Series с её ленивыми последовательностями для моей задачи подошли бы лучше всего: мне нужно строить карту памяти, для этого набор штатных функций над множествами (set) отлично подходил бы, если множества были ленивыми. Так пришлось городить велосипед со слиянием и исключением множеств. На Series это был бы однострочник.

    ОтветитьУдалить
  8. 2 archimag: да беда в том, что алгоритм хорошо и функционально ложится на множества, но множества должны быть ленивыми. С итерациями замутился, потому что изкоробочные множества, увы, не ленивые.

    ОтветитьУдалить
  9. 2 srgb:

    > ЗЫ куда-то пропал мой предыдущий коммент, пишу ещё раз.

    В спам коммент твой попал почему-то...

    ОтветитьУдалить
  10. > попробуй заменить в приведённом примере loop
    > на iterate и удивись.

    Смешно. Если просто заменить, то, конечно, ничего хорошего не получится. Но это вроде и так очевидно?

    ОтветитьУдалить
  11. > но множества должны быть ленивыми

    В iterate есть генераторы.

    ОтветитьУдалить
  12. > Но это вроде и так очевидно?

    То, что CL писали дебилы? Конечно, не очевидно. Более того, для меня до сего момента было очевидно обратное. Но если эти люди не способны написать тривиальную форму для итерации на три строчки - то вопросов нет.

    ОтветитьУдалить
  13. Ахахах, это просто п****ц, сейчас поглядел на экспанд лупа - мой день сделан. Оказывается эти умники не осилили сделать нормальный кодогенератор и вместо того, чтобы подставлять форму на место итератора делают из нее лямбду (!), замкнутую на контекст определения. А вы вкурсе, как у них определяется начальное значение х в форме (loop for x in `(1 2 3 ...))? Не поверите - NILL, а это значит что? Правильно - лямбда замыкается на NILL и инжой йу эррор в
    (loop for x in `(1 2 3) for y from 1 by (+ 1 x) ...).

    ОтветитьУдалить
  14. "Умник" здесь только ты. Причём не умеющий читать. Потому что если бы ты умел это делать, то прочитал бы раздел 6.1.2.1.1 стандарта, особенно первый абзац оттуда:


    In the for-as-arithmetic subclause, the for or as construct iterates from the value supplied by form1 to the value supplied by form2 in increments or decrements denoted by form3. Each expression is evaluated only once and must evaluate to a number.


    Так что там даже наличие переменной x в области видимости выплнения (+ 1 x) из твоего кода стандартом не гарантируется. И смысл в этом есть, ибо позволяет писать что-то вроде (loop for x below (some-func) by (some-func2)...) не создавая руками переменные для значений конца итерирования и инкремента. Такое нужно гораздо чаще чем твой пример.

    А твой пример правильно писать так: (loop for x in '(1 2 3) and y = 1 then (+ y x 1) collect y)

    ОтветитьУдалить
  15. > Each expression is evaluated only once and must evaluate to a number.

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

    > Так что там даже наличие переменной x в области видимости выполнения (+ 1 x) из твоего кода стандартом не гарантируется.

    Стандартом там вообще ничерта не гарантируется, ага. Факт, однако, состоит в том, что поведение стандартных конструкций должно быть предсказуемым. Где здесь логика, что
    (loop for x from 1 to 10 for y from 1 by (+ 1 x) collect y) прекрасно работает, а (loop for x in `(1 2 3) for y from 1 by (+ 1 x) collect y) - нет? Почему обработка итерационных форм неюниморфна? Почему во втором случае x инициализируется первым элементом итерации, а в первом - каким-то NIL'ом, который хрен пойми откуда взялся?

    > позволяет писать что-то вроде (loop for x below (some-func) by (some-func2)...) не создавая руками переменные для значений конца итерирования и инкремента.

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

    ОтветитьУдалить

Архив блога