Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Комбинатор W как средство написания подпрограмм

В HN0 подпрограммы реализуются тем же способом что и разделяемые данные - через комбинатор W, представленный функцией join.

Декларация flip = curry flip1 where flip1 = __builtin2 __flip - это не подпрограмма, а макрос, простая подстановка. Как же реализовать подпрограмму?

Возьмем для примера программу на Хаскеле na x y j  = (x + y) * (x + j)

Дупликация "+ x" не влияет на результат или на скорость работы программы, но влияет на размер кода. (Размер кода, конечно, влияет на скорость, но опосредованно - за счет засорения кеша кода.). На Хаскеле можно было бы записать:
na х y j = (plusX y) * (plusX j) where plusX = + x
Переводим это решение сначала в префиксную, а затем в бесточечную запись:
na х у j = * (plusX y) (plusX j) where plusX = + x
na x y = o (* (plusX y)) plusX where plusX = + x
na x y = flip o plusX (* (plusX y)) where plusX = + x
na x y = flip o plusX (o * plusX y) where plusX = + x
na x = o (flip o plusX) (o * plusX) where plusX = + x
na x = o (flip o plusX) (o *) plusX where plusX = + x
na x = o (flip o plusX) (o *) plusX where plusX = + x
na x = flip o (o *) (flip o plusX) plusX where plusX = + x
na x = o (flip o (o *)) (flip o) plusX plusX where plusX = + x
na x = join (o (flip o (o *)) (flip o)) (+ x) 
na = o (join (o (flip o (o *)) (flip o))) +
Забавно сравнить это с результатом перевода исходной программы, без выделения plusX. Аргументы y и j убираются таким же точно образом. Разница начинает проявляться в том, что нам надо передать в join ("разделить") только x, а не + x:
na x = o (flip o (+ x)) (o * (+ x))
na x = o (flip o (+ x))  (o (o *) +) x
na x = flip o (o (o *) +) (flip o (+ x)) x
na x = flip o (o (o *) +) (o (flip o) +) x) x
na x = o (flip o (o (o *) +)) (o (flip o) +) x x
na = join (o (flip o (o (o *) +)) (o (flip o) +))
Черт! Определенно пора писать компилятор из лямбд в комбинаторы - я не уверен, что нигде не запутался в процессе преобразований. Но если я не запутался, тогда сравним:
na = o (join (o (flip o (o *)) (flip o))) +
na = join (o (flip o (o (o *) +)) (o (flip o) +))
Первая программа вроде как действительно короче получилась! Но в ней обнаружилась дупликация:
na = o (join (o (f (o *)) f)) + where
    f = flip o
Всегда ли возможно устранить дупликацию путем применения W? Не будет ли процесс применения W бесконечным? Локализуем минимальное поддерево с дупликацией, и попробуем избавиться от нее с помощью join:
g = o (f h) f
g = o o f h f
g = flip (o o)) h f f
g = join (flip (o o)) h) f 
Новой дупликации не возникло, ура! Хотя выражение и удлиннилось. Подставляем в исходное:
g = join (flip (o o)) (o *)) (flip o)

na = o (join (join (flip (o o)) (o *)) (flip o))) +
Похоже, что join для данных (представленных в коде HN0 неявно) нельзя устранить, а join для кода (представленного явно) устраняется путем дупликации. Таким образом, мой вопрос об инстанцировании можно переформулировать более узко:
  • Существует ли для деревьев алгоритм поиска повторений, аналогичный LZ-77 и LZW для списков? Если да, насколько эффективно такой подход (поиск паттернов и устранение их через join) будет устранять copy-paste?
  • В каком порядке должен оптимизатор выполнять дедупликацию, fusion, инстанцирование? Нужно ли перед fusion убирать все join для кода, дуплицируя код, или наоборот, убирать всю дупликацию?
Tags: hn0
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment