linkfly (linkfly) wrote,
linkfly
linkfly

Устройство ASDF. Подсистема загрузки. Подсистема планирования операций. TRAVERSE.

(сказаное ниже относится к версии 2.019.2)

Это 7-ая статья цикла.
Первая статья.
Архитектура ASDF.
Предыдущая статья.

    Предназначение ф-ии TRAVERSE в том, чтобы вернуть список точечных пар, состоящих их объекта класса операция и объекта класса компонент. По сути, эти точечные пары представляют собой готовый план действий с компонентами. Ниже будет показана часть результата работы этой ф-ии, возвращеного для некой экспериментальной ASDF системы. Вызов был таким:

   (traverse (make-instance 'load-op) (find-system :exp-system))

А вот часть результата:

((#<COMPILE-OP NIL {B898FC1}> . #<CL-SOURCE-FILE "exp-system" "src" "file1">)
 (#<LOAD-OP NIL {B929AB1}> . #<CL-SOURCE-FILE "exp-system" "src" "file1">)
 (#<COMPILE-OP NIL {B898FC1}>
           . #<CL-SOURCE-FILE "exp-system" "src" "file2">
)

 ...
)

    Главная, самая интеллектуальная часть ф-ии TRAVERSE, это вызываемая ею ф-ия DO-TRAVERSE, которая использует явные и неявные рекурсивные вызовы. Ниже представлена упрощенная схема взаимозависимостей ф-ий работающих в traverse:

;;;;;;;;;;;;;;;;;;;
traverse -> do-traverse -> do-dep -> resolve-dependency-spec -> resolve-dependency-name
                                                        -> do-one-dep -> make-sub-operation
                                                                                 -> do-traverse <-
                                       -> component-visited-p
                                       -> component-visiting-p
                                       -> component-depends-on
                                       -> do-traverse <-
                                       -> operation-done-p
                                       -> visit-component
               -> flatten-tree
;;;;;;;;;;;;;;;;;;;    

Разберём по шагам логику работы ф-ии traverse:

1. Если в слоте forced объекта список, то преобразовать элементы списка в имена:

   (when (consp (operation-forced operation))
      (setf (operation-forced operation)
              (mapcar #'coerce-name (operation-forced operation))
)
)


    Значение forced задаётся ключом :forced при вызове operate (а также LOAD-SYSTEM и OOS). Если ключ был задан и равен значению T или списку содержащему, в том числе, имя загружаемой системы, то происходит повторное планирование операций для компонентов системы.

2. Создать динамический контекст со специальной переменной-счётчиком *VISIT-COUNT*, равным 0, определить ф-ию collect для сбора значений:

    (while-collecting (collect)
   
   (let ((*visit-count* 0))
   
      ...))

3. Далее вызывается ф-ия DO-TRAVERSE для формирования результата (окончательная обработка которого будет производится ф-ией FLATTEN-TREE). Ф-ия DO-TRAVERSE возвращает древообразный список (элементы которого списки и вектора), который затем можно преобразовать в список правил компиляции и загрузки с помощью FLATTEN-TREE. В этом древообразном списке, векторами помечены элементы внутрь которых нужно "зайти", взять список (в векторе должен быть только один элемент и являться списком) и "вытащить наружу" элементы этого списка. Форма вызова:

   (while-collecting (collect)
      (let ((*visit-count* 0))
          (do-traverse (make-instance 'load-op) (find-system :exp-system) #'collect)
)
)


    ... вернёт (показана только часть):

(#((#((#(NIL)
          (#<COMPILE-OP NIL {B1CE711}>
           . #<FILE-MY "exp-system" "src" "file1">
)

          #(NIL)
          (#<LOAD-OP NIL {B209AC9}>
           . #<FILE-MY "exp-system" "src" "file1">
)

       ...
)
)
)
)
)

 
    Эта списочная структура создана специально для дальнейшей обработки ф-ией FLATTEN-TREE.

4. Ф-ия FLATTEN-TREE является хорошим примером использования взаимной рекурсии. Логика её работы в следующем:
        - она проходит по списку, собирая элементы в новый список, оставляя все элементы как есть, кроме векторов.
        - для них делается исключение - берётся первый элемент (который должен быть единственным и должен быть списком) и в новый список попадают уже элементы этого списка, а не сам вектор, например:

       (setq l '(1 (2 3) #((4 (5))) 6 #(((7 8)))))
        => (1 (2 3) #((4 (5))) 6 #(((7 8))))

        (flatten-tree l)
        => (1 (2 3) 4 (5) 6 (7 8))

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

(defun* flatten-tree (l)
  (while-collecting (c)
    (labels ((r (x)
               (if (typep x '(simple-vector 1))
                   (r* (svref x 0))
                   (c x)
)
)

             (r* (l)
               (dolist (x l) (r x))
)
)

      (r* l)
)
)
)

--------------------------------------------------
Продолжение следует ...
Tags: asdf, lisp, programming, лисп, программирование
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

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