swizard (swizard) wrote,
swizard
swizard

Categories:
  • Location:
  • Music:

Рекурсия лямбдой

Как-то на рсдн-e я прочитал в местном форуме, что если в языке отсутствует конструкция letrec, то рекурсию реализовать уже не получится. Честно говоря, тогда я не придал этому высказыванию значения, пока у меня не всплыла похожая задача. И сегодня в метро я решил проверить, так ли это на самом деле.

Итак, возьмем какую-нибудь простенькую рекурсивную функцию, например, такую:

(define make-sequence
  (lambda (start count)
    (if (<= count 0)
        '()
        (cons start
              (make-sequence (+ start 1) (- count 1))))))



"Легко видеть, что"© она нам даст список чисел, начинающихся со start и размером count:

#;10> (make-sequence 4 7)
(4 5 6 7 8 9 10)


Хорошо, с примером должно быть все понятно, поэтому давайте представим себе, что наша схема не поддерживает ключевые слова define и letrec. Интересно, можно ли теперь выполнить наше упражнение? Давайте проверим. Положим, make-sequence у нас уже есть. Давайте вынесем основную логику в анонимную функцию, а make-sequence оставим аргументом:

(lambda (make-sequence)
  (make-sequence 4 7))


Теперь надо как-то определить make-sequence, чтобы было, что передать в лямбду. Попробуем использовать наши наработки:

((lambda (make-sequence)
   (make-sequence 4 7))
 (lambda (start count)
   (if (<= count 0)
       '()
       (cons start
             (make-sequence (+ start 1) (- count 1))))))


Разумеется, хуй там был:

#;13> Error: unbound variable: make-sequence

        Call history:

        <eval>          ((lambda (make-sequence) (make-sequence 4 7)) (lambda (start count) (if (<= count 0) (quote ()) (cons start (make-sequ......
        <eval>          (make-sequence 4 7)
        <eval>          (<= count 0)
        <eval>          (cons start (make-sequence (+ start 1) (- count 1)))
        <eval>          (make-sequence (+ start 1) (- count 1))
        <eval>          (+ start 1)
        <eval>          (- count 1)     <--


Дело в том, что в пределах видимости (lambda (start count) ... переменная make-sequence не определена. Сразу встает вопрос: каким макаром нам организовать рекурсию на анонимной функции? Собственно, этим вопросом я сегодня и мучал мозг в метро.

Прежде, чем я представлю свое решение, сразу оговорюсь: я знаю, что такое continuation passing style, читал про него не одну статью, представляю зачем он нужен, и даже более-менее умею пользоваться call/cc. Тем не менее, несмотря на все эти знания, я сегодня изобрел cps заново :)

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

(lambda (self start count)
  (if (<= count 0)
      '()
      (cons start
            (self self (+ start 1) (- count 1)))))


Здесь в качестве self функции нужно передать ее же. Это уже сделать несложно уровнем выше, где можно получить необходимый биндинг:

((lambda (f)
   (lambda (start count)
     (f f start count)))
 (lambda (self start count)
   (if (<= count 0)
       '()
       (cons start
             (self self (+ start 1) (- count 1))))))


Грубо говоря, в результате выполнения этой каши скобочек, мы получим фунцию от двух аргументов, start и count (собственно, это и есть наша make-sequence), которая сделает следующее:
  • возьмет функцию f (она ее получила из замыкания)
  • передаст ей саму себя -- f и аргументы для make-sequence


А что такое f? Это как раз то, что мы определили пару страницей назад. Вот и получилось, что в качестве аргумента self анонимная функция получила сама себя :)

Вот так все это будет выглядеть вместе:

((lambda (make-sequence)
   (make-sequence 4 7))
 ((lambda (f)
    (lambda (start count)
      (f f start count)))
  (lambda (self start count)
    (if (<= count 0)
        '()
        (cons start
              (self self (+ start 1) (- count 1)))))))


Страшновато, но цели своей мы добились: реализовали рекурсию без define и letrec, одними лямбдами:

#;14> 
(4 5 6 7 8 9 10)


Для более понятной записи можно, воспользовавшись синтаксическим сахаром, избавиться от лямбд и нескольких сотен пар скобочек:

(let* ((cps-lambda (lambda (self start count)
                     (if (<= count 0)
                         '()
                         (cons start
                               (self self (+ start 1) (- count 1))))))
       (proc-maker (lambda (f)
                     (lambda (start count)
                       (f f start count))))
       (make-sequence (proc-maker cps-lambda)))
  (make-sequence 4 7))


Tags: code, continuation passing style, cps, define, letrec, recursion, scheme
Subscribe
  • Post a new comment

    Error

    default userpic

    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.
  • 42 comments