Объясните пример продолжения на стр .137 "Маленькой схемы"

Ответ 1

Пройдите через пример; может быть, это поможет.:-) Для простоты я просто собираюсь использовать list как коллекционер/продолжение, который просто вернет список с аргументами к продолжению.

(multirember&co 'foo '(foo bar) list)

В начале

a = 'foo
lat = '(foo bar)
col = list

На первой итерации выполняется условие (eq? (car lat) a), так как lat не пуст, а первый элемент lat - 'foo. Это устанавливает следующую рекурсию на multirember&co следующим образом:

a = 'foo
lat = '(bar)
col = (lambda (newlat seen)
        (list newlat (cons 'foo seen))

На следующей итерации else соответствует: поскольку lat не пуст, а первый элемент lat равен 'bar (а не 'foo). Таким образом, для следующей рекурсии мы имеем:

a = 'foo
lat = '()
col = (lambda (newlat seen)
        ((lambda (newlat seen)
           (list newlat (cons 'foo seen)))
         (cons 'bar newlat)
         seen))

Для удобства чтения человеком (и избегайте путаницы) мы можем переименовать параметры (из-за лексического охвата) без каких-либо изменений в семантике программы:

col = (lambda (newlat1 seen1)
        ((lambda (newlat2 seen2)
           (list newlat2 (cons 'foo seen2)))
         (cons 'bar newlat1)
         seen1))

Наконец, предложение (null? lat) соответствует, так как lat теперь пуст. Поэтому мы называем

(col '() '())

который расширяется до:

((lambda (newlat1 seen1)
   ((lambda (newlat2 seen2)
      (list newlat2 (cons 'foo seen2)))
    (cons 'bar newlat1)
    seen1))
 '() '())

который (при подстановке newlat1 = '() и seen1 = '()) становится

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 (cons 'bar '())
 '())

или (оценка (cons 'bar '()))

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 '(bar)
 '())

Теперь, подставляя значения newlat2 = '(bar) и seen2 = '(), получаем

(list '(bar) (cons 'foo '()))

или, другими словами,

(list '(bar) '(foo))

чтобы дать окончательный результат

'((bar) (foo))

Ответ 2

Я нашел замечательный ответ здесь: http://www.michaelharrison.ws/weblog/?p=34

Я тоже пробовал это. Ключ состоит в том, чтобы понять лексическое охват (для меня, а-ля Javascript) и внутренние функции, переданные в мультиребер и co на ветвях eq, а не eq. Поймите это, и вы поймете всю процедуру.

Ответ 3

Какая ссылка выше (http://www.michaelharrison.ws/weblog/?p=34) хорошо объясняет, как все это упражнение в том, чтобы избегать императивного программирования (C, Java), нужно объявить два "держателя", или "collector" (или списки, векторы) явно в памяти, чтобы поймать ваши ответы, когда вы перебираете список. При использовании продолжения на языке FP язык, вы не "нажимаете" результаты теста при прохождении (клубника тунца и меч-рыба) в любые отдельно созданные "корзины"; вместо этого вы объединяете два списка, отправляя соответствующие функции consing - один для eq? true, другой для eq? false - через повторение., наконец, заканчивается в третьей функции col, которая в первом примере TLS является "a-friend", который спрашивает, пустой ли список, который содержит все совпадения (null?). Затем TLS попросит вас "запустить" мультирежим и снова с новым "последним" столбцом, который просто запрашивает список, содержащий все атомы "не тунца", сколько он содержит ( "последний друг" ). Таким образом, есть две функции "первого класса", которые используются для работы с задачей сбора, т.е. Создания двух отдельных списков, а затем в конце разворота рекурсии исходный col ( "a-friend" ) задает последний вопрос. Возможно, имя "multirember & co" не является самым большим именем, потому что оно действительно не перестраивает список минус удаляемый атом; скорее, он строит два отдельных списка, которые никогда не отображаются, а затем применяет окончательный столбец (друг или друг друга)., который отображает либо #t, либо #f, либо длину списка "не тунца".

Здесь вывод:

> (multirember&co 'tuna '(and tuna) a-friend)
#f
> (multirember&co 'tuna '(and not) a-friend)
#t

Здесь col, чтобы вернуть список несоответствий:

(define list-not  (lambda (x y) x))

и его использование:

> (multirember&co 'tuna '(and not) list-not)
(and not)

Ответ 4

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

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

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

(define multirember&co
  (lambda (a lat col)
    (cond
     ((null? lat)
      (col (quote ()) (quote ())))
     ((eq? (car lat) a)
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col newlat
                             (cons (car lat) seen)))))
     (else
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col (cons (car lat) newlat)
                             seen)))))))

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

• Случай 1:

(multirember&co 'a
                '()
                (lambda (x y) (list x y)))

is the same as    

(let ((col (lambda (x y) (list x y))))
  (col '() '()))

Это тривиальный случай, он никогда не зацикливается.

Теперь интересные случаи:

• Случай 2:

(multirember&co 'a
                '(x)
                (lambda (x y) (list x y)))

is the same as    

(let ((col
       (let ((col (lambda (x y) (list x y)))
             (lat '(x))
             (a 'a))
         (lambda (newlat seen)
           (col (cons (car lat) newlat)
                seen)))))
  (col '() '()))

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

• Случай 3

(multirember&co 'a
                '(a)
                (lambda (x y) (list x y)))

is the same as    

(let ((col
       (let ((col (lambda (x y) (list x y)))
             (lat '(a))
             (a 'a))
         (lambda (newlat seen)
           (col newlat
                (cons (car lat) seen))))))
  (col '() '()))

Это создает код, но на другой ветке, которая накапливает результат в другой переменной.

Все остальные случаи являются комбинациями из 1 из этих 3 случаев, и ясно, как каждый 1 действует, добавляя новый слой.

Ответ 5

Я боролся сам, чтобы понять, что происходит внутри multirember&co, довольно multirember&co. Проблема в том, что в тот момент, когда я подумал, что у меня есть это - следующая задача/пример доказала, что я этого не сделал.

Что помогло мне собрать визуальное представление о том, что происходит (для меня, по какой-то причине, трудно понять, какие походы в тексте трудно понять).

Итак, я собрал две блок-схемы:

Один, просто показывающий отношения между различными этапами рекурсии:

И еще один, отражающий фактические значения:



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

Еще одна вещь, которую я понял после просмотра "целой картины" с помощью блок-схемы, заключается в том, что функция " a-friend просто проверяет, не seen ли какие-либо значения или нет (хотя она возвращает ее другим способом, т.е. #f когда значения в seen и #t когда seen пуст, что может привести к путанице.

PS: Я сделал аналогичные блок-схемы для evens-only*&co, которые появляются позже в книге.

Ответ 6

Позвольте использовать некоторый эквациональный псевдокод, а некоторые скобки опущены для ясности (поэтому мы пишем fxy для вызова (fxy), где это однозначно):

multirember&Co a lat col
    = col [] []                                , IF lat == [] 

    = multirember&Co a (cdr lat)
         ( newlat seen => 
             col newlat
                 (cons (car lat) seen) )       , IF (car lat) == a

    = multirember&Co a (cdr lat)
         ( newlat seen => 
             col (cons (car lat) newlat)
                 seen )                        , OTHERWISE

Разве это не просто самоочевидно, что это делает? :) Еще нет? :) Повторная запись снова с воображаемым псевдокодом, сопоставляющим шаблоны (с охранниками), у нас есть

multirember&Co = g where
    g a [b, ...lat] col | b == a  =  g a lat ( n s => col     n     [b, ...s] )
                        | else    =  g a lat ( n s => col [b, ...n]     s     )
    g a []          col           =                   col     []        []

Семантика сопоставления шаблонов должна быть совершенно очевидной: [b,...lat] соответствует [1,2,3] где b = 1 и lat = [2,3]. Таким образом, это просто уравнение с тремя телами:

• Когда второй аргумент представляет собой пустой список, функция col получает сразу два пустых списка в качестве двух аргументов;

• Когда элемент заголовка второго аргумента (который является списком) совпадает с первым аргументом, результат будет таким же, как и для рекурсии с хвостом списка, с измененным коллектором, который после получения двух аргументов, n и s, - добавит текущий элемент заголовка (который является a) в список s и будет комбинировать два списка с этой функцией коллектора вызовов col;

• В противном случае элемент головки будет добавлен в список n, после того, как n и s будут получены сконструированным коллектором, и оба будут дополнительно введены в функцию токоприемника.

Другими словами, мы имеем дело с двумя результаты возвращения из рекурсивного вызова, предваряя головы до второй, если голова, или к первой, если это не было. a

Таким образом, вызов

    (g 1 [ 2, 1, 3, 1, 4, 5 ] col)

то же, что (приведет к) вызову

    (col [ 2, ...[3, ...[4, ...[5, ...[]]]]]
         [    1, ...[1,            ...[]]  ])

т.е.

    (col [ 2,     3,     4,     5          ]
         [    1,     1                     ])

Другой способ взглянуть на это состоит в следующем: эквивалентная формулировка:

multirember&Co a lat col = g a lat id id where
    id   = (x => x)            ; identity function  
    (f ∘ g) x = f (g x)        ; function composition
    g a [b, ...lat] c d 
                | b == a  =  g a lat  c     (d ∘ (x => (cons b x)))  ;    (d ∘ {cons b})
                | else    =  g a lat (c ∘ (x => (cons b x)))    d    ; (c ∘ {cons b})
    g a []          c d   =  col     (c [])                  (d [])

и поэтому

multirember&Co 1 [ 2, 1, 3, 1, 4, 5 ] col 
=
col (((((id ∘ {cons 2}) ∘ {cons 3}) ∘ {cons 4}) ∘ {cons 5}) [])   ; { } is for
    ( ( (id ∘       {cons 1}) ∘ {cons 1}                  ) [])   ;  partial application
=
col     (id   (cons 2     (cons 3     (cons 4    (cons 5   [])))))
        (id         (cons 1     (cons 1                    []) ) )  

что само по себе очевидно одно и то же.

В еще одном псевдокоде (со списком) это показывает, что

multirember&Co a lat col  
   = col [ b for b in lat if (b /= a) ] 
         [ b for b in lat if (b == a) ] 
   = ( ((n,s) => col n s) ∘ {partition {/= a}} ) lat

за исключением того, что выполняется только один обход списка lat (в исходном коде), создавая вложенную цепочку лямбда-функций, имитирующую исходную структуру списка; которая затем оценивается для создания двух результатов, передавая их в самую большую коллекционную функцию col.

Все это показывает нам силу стиля Continuation-Passing Style (что является тем, что это такое), по сути, создает свой собственный протокол вызовов функций, например, передавая два результата от каждого вызова рекурсивной функции, хотя обычно в лямбда-исчислении a функция может иметь только один результат (даже если, скажем, пара).

Ответ 7

Я надеюсь, что это пошаговое руководство поможет

Как предложил Крис, я переименовал newlat/seen в n/s и добавил индекс. Книга дает ужасные имена функциям (друг друга, новый друг, недавно обжаренный), поэтому я просто сохранил L (для лямбда) и определения.

multirember&co 'tuna '(strawberries tuna and swordfish) a-friend)
  multirember&co 'tuna '(tuna and swordfish) (L(n1 s1)(a-friend (cons 'strawberries n1) s1))
    multirember&co 'tuna '(and swordfish) (L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))
      multirember&co 'tuna '(swordfish) (L(n3 s3)((L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2)) (cons 'and n3) s3))
        multirember&co 'tuna '() (L(n4 s4)((L(n3 s3)((L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2)) (cons 'and n3) s3)) (cons 'swordfish n4) s4))

((lambda(n4 s4)((lambda(n3 s3)((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) (cons 'and n3) s3)) (cons 'swordfish n4) s4)) '() '())
               ((lambda(n3 s3)((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) (cons 'and n3) s3)) '(swordfish) '())
                              ((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) '(and swordfish) '())
                                             ((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) '(and swordfish) '(tuna))
                                                            (a-friend '(strawberries and swordfish) '(tuna))