Funktionskatalog

SUBLIS

Format

Beschreibung

Die Funktion erwartet einen Ausdruck und eine Paarliste. Sie führt in dem Ausdurck alle durch die Paarliste definierten Ersetzungen aus.

Beispiele

(sublis (pair '(?x ?y)
              '((times a b) (plus a b))
        )
        '(quotient (plus ?x ?y) (times ?x ?y))
)
= (quotient (plus (times a b) (plus a b))
            (times (times a b) (plus a b))
  )

(sublis '((a . b) (b . a))
        '(list a b)
)
= (list b a)

Definition

Für diese Funktion lassen sich mit geringer Mühe verschiedene Definitionen angeben. Die wohl kürzeste Definition ist diese:

(defun sublis
   (lambda (sl exp)
      (cond ((assoc exp sl) (cdr (assoc exp sl)))
            ((atom  exp)    exp)
            (t (cons (sublis sl (car exp))
                     (sublis sl (cdr exp))
)  )  )     )  )

Bemerkungen:

Restrekursive Definition

Die restrekursive Definition verwendet ein Hilfspaar, in dessen cdr-Feld das Ergebnis eingetragen wird.

(defun append
  (lambda (a b)
     ((lambda (a b root)
         ((label append*
            (lambda (a b root ip)
                 (cond ((null a)  (and (rplacd ip b)
                                       (cdr root)
                       )          )
                       (t (append* (cdr a)
                                   b
                                   root
                                   (cdr (rplacd ip (list (car a))))
                 )     )  )
          )  )
          a
          b
          root
          root
         )
      )
      a
      b
      (list nil)
) )  )

Es ginge auch:

(defun append
  (lambda (a b)
     ((lambda (a b root)
         ((label append*
            (lambda (a ip)
                 (cond ((null a)  (and (rplacd ip b)
                                       (cdr root)
                       )          )
                       (t (append* (cdr a)
                                   (cdr (rplacd ip (list (car a))))
                 )     )  )
          )  )
          a
          root
         )
      )
      a
      b
      (list nil)
) )  )

Regeln

(length (pair <a> <b>))  <=>  (min (length <a>) (length <b>))

(length (append <a> <b>))  <=>  (plus (length <a>) (length <b>))

Implementierung im Interpeter

Die Prozedur zählt die Top-Level-Elemente der der durchsuchten Liste. Die Überschreitung der Zahl der verfügbaren Paare weist auf das Vorliegen einer zirkulären Struktur hin; in diesem Fall wird ein Fehler gemeldet.

function length(list : reference) : integer;
  var i   : integer;
begin
  i := 0;
  while (list <> 0) do
    if isAtom(list)
      then
             handleError(malformedList)
      else begin
             i := i + 1;
             if i > nroPairs
                then handleError(circularStructure);
             list := pairs[list].cdr;
           end
  length := i;
end;