Вопрос по – Маленькая интрижка только для вечеринок * & co

13

Мне трудно понять, что происходит с The Little Schemer.evens-only*&co пример на стр. 145.

Вот код:

(define evens-only*&co
 (lambda (l col)
   (cond
    ((null? l)
     (col '() 1 0))
    ((atom? (car l))
     (cond
      ((even? (car l))
       (evens-only*&co (cdr l)
                    (lambda (newl product sum)
                      (col (cons (car l) newl)
                           (opx (car l) product)
                           sum))))
      (else
       (evens-only*&co (cdr l)
                    (lambda (newl product sum)
                      (col newl product (op+ (car l) sum)))))))
    (else
     (evens-only*&co (car l)
                  (lambda (newl product sum)
                    (evens-only*&co (cdr l)
                                    (lambda (dnewl dproduct dsum)
                                      (col (cons newl dnewl)
                                           (opx product dproduct)
                                           (op+ sum dsum))))))))))

Начальныйcol может быть:

(define evens-results
 (lambda (newl product sum)
   (cons sum (cons product newl))))

Что я не получаю, так это сl как'((1) 2 3)Сразу же идет в финалelse с(car l) как(1) а также(cdr l) как(2 3), Хорошо, но мой разум сходит с ума, пытаясь разобратьсяdnewl, dproduct, dsum отnewl, product, sum, Также было бы полезно, если бы кто-нибудь мог научить меня, как настроить DrRacket, Chez Scheme или MIT-Scheme для запуска степпера.

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

Для настройки степпера см.stackoverflow.com/questions/10499514/… soegaard

Ваш Ответ

4   ответа
0

как разрабатывать программы (felleisen et.al.). Я иду через раздел, где они определяютlocal определения. Я написал код, который реализует вышеприведенные четные & amp; co с использованием локального определения. Вот что я написал:

(define (evens-only&co l)
  (local ((define (processing-func sum prod evlst lst)
            (cond ((null? lst) (cons sum (cons prod evlst)))
                  ((atom? (car lst))
                   (cond ((even? (car lst)) (processing-func sum (* prod (car lst)) (append evlst (list (car lst))) (cdr lst)))
                         (else
                          (processing-func (+ sum (car lst)) prod evlst (cdr lst)))))
                  (else
                   (local ((define inner-lst (processing-func sum prod  '() (car lst))))
                   (processing-func (car inner-lst) (cadr inner-lst) (append evlst (list (cddr inner-lst))) (cdr lst)))))))
    (processing-func 0 1 '() l)))

Для тестирования, когда я ввожу (только по четному и со) ((9 1 2 8) 3 10 ((9 9) 7 6) 2)), возвращается «(38 1920 (2 8) 10 (()») 6) 2) как и положено в маленьком интриганке. Но мой код не выполняется в одном условии: когда четных чисел нет вообще, произведение четных чисел по-прежнему отображается как 1. Например (только четные и параллельные) ((9 1) 3 ((9 9) 7 ))) возвращает '(38 1 () (())). Я думаю, мне понадобится дополнительная функция, чтобы исправить это. @melwasul: если вы не знакомы сlocal определение, извините, чтобы опубликовать это здесь. Я предлагаю вам прочитать HTDP тоже. Это отличная книга для начинающих. Но ребята, которые являются экспертами в схеме, могут также оставить свои комментарии к моему коду. Правильно ли мое понимание локального определения?

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded1Error: User Rate Limit Exceeded1Error: User Rate Limit Exceeded0Error: User Rate Limit Exceeded(*)Error: User Rate Limit Exceeded
1

ответ отДжон О. действительно большое подробное объяснение основных понятий. Хотя для меня (и, надеюсь, для некоторых других людей), понимание таких понятий намного проще, когда они имеют визуальное представление.

Итак, я подготовил две блок-схемы (аналогичноте, которые я сделал дляmultirember&coраспутывая происходящее во время вызоваevens-only*&co

даноl является:

'((9 1 2 8) 3 10 ((9 9) 7 6) 2) 

а такжеcol является:

(define the-last-friend
    (lambda (newl product sum)
        (cons sum (cons product newl))
    )
)

Одна блок-схема, отражающаяhow variables relate in different steps of recursion: Visual walkthrough showing relations between variables Вторая блок-схема, показывающаяactual values, being passed: Visual walkthrough with values

Я надеюсь, что этот ответ станет достойным дополнением кОбъяснение Джона выше.

0

KRCкак записьf x y для вызова(f x y)где это однозначно) это

evens-only*&co l col 
   = col [] 1 0                                     , IF null? l
   = evens-only*&co (cdr l) 
                    ( newl product sum =>
                        col (cons (car l) newl)
                            (opx (car l) product)
                            sum )                   , IF atom? (car l) && even? (car l)
   = evens-only*&co (cdr l) 
                    ( newl product sum =>
                        col  newl  product  (op+ (car l) sum) )      , IF atom? (car l)
   = evens-only*&co (car l) 
                    ( anewl aproduct asum =>
                         evens-only*&co (cdr l)
                                        ( dnewl dproduct dsum =>
                                             col (cons anewl    dnewl)
                                                 (opx  aproduct dproduct)
                                                 (op+  asum     dsum) ) )   , OTHERWISE

ЭтоКПС код, который собирает все четности из входного вложенного списка (то есть дерева) при сохранении древовидной структуры, а также находит произведение всех четностей; что касается нечетных, этоsums их вверх:

if l is an empty list, the three basic (identity) values are passed as arguments to col;

if (car l) is an even number, the results of processing the (cdr l) are newl, product and sum, and then they are passed as arguments to col while the first two are augmented by consing  ⁄  multiplying with the (car l) (the even number);

if (car l) is an atom which is not an even number, the results of processing the (cdr l) are newl, product and sum, and then they are passed as arguments to col with the third one augmented by summing with the (car l) (the non-even number atom);

if (car l) is a list, the results of processing the (car l) are anewl, aproduct and asum, and then the results of processing the (cdr l) are dnewl, dproduct and dsum, and then the three combined results are passed as arguments to col.

[], 1 а также0 базового случая являются элементами идентичностимоноиды списков, чисел при умножении и чисел при сложении соответственно. Это просто означает специальные значения, которые не меняют результат при объединении в него.

В качестве иллюстрации для'((5) 2 3 4) (что близко к примеру в вопросе), это создает расчет

evens-only*&co [[5], 2, 3, 4] col
=
col  (cons []                   ; original structure w only the evens kept in,
           (cons 2              ;   for the car and the cdr parts
              (cons 4 [])))
     (opx 1                     ; multiply the products of evens in the car and 
          (opx 2 (opx 4 1)))    ;   in the cdr parts
     (op+ (op+ 5 0)             ; sum, for the non-evens
          (op+ 3 0))     

Похожий намой другой ответ (к вопросу о сестре), вот еще один способ написать это с помощью псевдокода, соответствующего шаблону (с охранниками):

evens-only*&co  =  g   where
  g [a, ...xs...] col 
         | pair? a    = g a  ( la pa sa =>
                         g xs ( ld pd sd =>
                                        col [la, ...ld...] (* pa pd) (+ sa sd) ) )
         | even? a    = g xs ( l p s => col [ a, ...l... ] (* a  p )       s     )
         | otherwise  = g xs ( l p s => col         l            p   (+ a  s )   )
  g []            col =                 col []              1         0

Экономика (и разнообразие) этой нотации действительно делает все это намного понятнее, легчеjust see вместо того, чтобы заблудиться в слове салат из длинных имен для функций и переменных одинаково, с паренами, перегруженными как синтаксические разделители для данных списка, группировками предложений (как вcond выражения), привязки имен (вlambda выражения) и обозначения вызова функций всеlooking именно такalike, Та же самая однородность обозначений S-выражений, которая способствует легкости манипулирования машиной (то есть lisp 'sread и макросы) - это то, что наносит ущербhuman удобочитаемость этого.

19

и начал понимать его только после того, как прочитал в другом месте о продолжениях и стиле прохождения продолжения (что и есть).

С риском объяснить что-то, что вы уже получили, один способ взглянуть на это, который помог мне, - подумать о «сборщике» или "продолжение" как замена нормального способа для функции возвращать значения. В обычном стиле программирования вы вызываете функцию, получаете значение и что-то делаете с ним в вызывающей программе. Например, стандартная рекурсивнаяlength функция включает в себя выражение(+ 1 (length (cdr list))) для непустого случая. Это означает, что когда-то(length (cdr list)) возвращает значение, вычисление, ожидающее выполнения с любым значением, которое оно производит, которое мы могли бы представить как(+ 1 [returned value]), В обычном программировании интерпретатор отслеживает эти ожидающие вычисления, которые, как правило, «складываются», как вы можете видеть в первых нескольких главах книги. Например, при рекурсивном вычислении длины списка мы имеем «ожидание вычислений». столько уровней, сколько список длинный.

В стиле передачи продолжения вместо вызова функции и использованияreturned В результате в вызывающей функции мы сообщаем функции, что делать, когда она выдает свое значение, предоставляя ей «продолжение». звонить. (Это похоже на то, что вы делаете с обратными вызовами в асинхронном программировании Javascript, например: вместо записиresult = someFunction(); ты пишешьsomeFunction(function (result) { ... })и весь код, который используетresult идет внутри функции обратного вызова).

Здесь & APOS; slength в стиле продолжения, просто для сравнения. Я назвал параметр продолженияreturn, который должен предполагать, как он функционирует здесь, но помните, что это просто обычная переменная Scheme, как и любая другая. (Часто параметр продолжения называетсяk в этом стиле).

(define (length/k lis return)
  (cond ((null? lis) (return 0))
        (else
         (length/k (cdr lis)
                   (lambda (cdr-len)
                     (return (+ cdr-len 1)))))))

Существует полезный совет для чтения такого рода кода встатья о продолженииLittle Schemer co-author Dan Friedman, (См. Раздел II-5, начиная со стр. 8). Перефразируя, вот чтоelse пункт выше говорит:

imagine you have the result of calling length/k on (cdr lis), and call it cdr-len, then add one and pass the result of this addition to your continuation (return).

Обратите внимание, что это почти то, что переводчик должен делать при оценке(+ 1 (length (cdr lis))) в обычной версии функции (за исключением того, что она не должна давать имя промежуточному результату(length (cdr lis)), Обойдя продолжения или обратные вызовы, мы сделали явный поток управления (и имена промежуточных значений) вместо того, чтобы интерпретатор следил за ним.

Давайте применим этот метод к каждому предложению вevens-only*&co, Это немного усложняется тем фактом, что эта функция производитthree значения, а не одно: вложенный список с удаленными нечетными числами; произведение четных чисел; и сумма нечетных чисел. Вот первый пункт, где(car l) известно, что это четное число:

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col (cons (car l) newl)
                       (opx (car l) product)
                       sum)))

Imagine that you have the results of removing odd numbers, multiplying evens, and adding odd numbers from the cdr of the list, and call them newl, product, and sum respectively. cons the head of the list onto newl (since it's an even number, it should go in the result); multiply product by the head of the list (since we're calculating product of evens); leave sum alone; and pass these three values to your waiting continuation col.

Вот случай, когда заголовок списка является нечетным числом:

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col newl product (op+ (car l) sum))))

Как и раньше, но передать те же значенияnewl а такжеproduct к продолжению (то есть «вернуть» их) вместе с суммойsum и заголовок списка, так как мы суммируем нечетные числа.

И вот последний, где(car l) это вложенный список, который немного усложняется двойной рекурсией:

(evens-only*&co (car l)
                (lambda (newl product sum)
                  (evens-only*&co (cdr l)
                                  (lambda (dnewl dproduct dsum)
                                    (col (cons newl dnewl)
                                         (opx product dproduct)
                                         (op+ sum dsum))))))

Imagine you have the results from removing, summing and adding the numbers in (car l) and call these newl, product, and sum; then imagine you have the results from doing the same thing to (cdr l), and call them dnewl, dproduct and dsum. To your waiting continuation, give the values produced by consing newl and dnewl (since we're producing a list of lists); multiplying together product and dproduct; and adding sum and dsum.

Обратите внимание: каждый раз, когда мы делаем рекурсивный вызов, мы создаем новое продолжение рекурсивного вызова, которое «закрывается». текущие значения аргумента,lи обратное продолжение -colдругими словами, вы можете думать о цепочке продолжений, которые мы строим во время рекурсии, как о моделировании «стека вызовов»; более условно написанной функции!

Надеюсь, что это даст часть ответа на ваш вопрос. Если я немного переборщил, то это только потому, что я думал, что после самой рекурсии продолжения - вторая действительно изящная, расширяющая сознание идея вThe Little Schemer и программирование в целом.

Error: User Rate Limit Exceeded melwasul
Error: User Rate Limit Exceeded((2))Error: User Rate Limit Exceededcol (cons (cons 2 ()) ()) (* (* 2 1) 1) (+ 0 0).

Похожие вопросы