BuK-Kreativaufgabe10 G2

Aus ProgrammingWiki

Archivierte Version vom 2011-06-21T10:52:38+00:00. Aktuelle Version

Aufgabenstellung

Entwickeln Sie einen Werkzeugkasten für primitiv rekursive Funktionen. Es wird erwartet, dass aus primitiv rekursiven (Basis-)Funktionen unter Verwendung der Kompositionstechniken (Substitution und primitive Rekursion) neue primitiv rekursive Funktionen generiert werden. Diese sollen verwendbar sein. Es wird nicht erwartet, dass ein universelles Beweisprogramm, das für eine gegebene Funktion konstruktiv nachweist, dass sie primitiv rekursiv ist, entwickelt wird.

Basisfunktionen

Zuerst definieren wir die Basisfunktionen.

(define S 
  (lambda (n)
    (add1 n)))

(define C0 
  (lambda n 0))

(define U 
  (lambda (i . n)
    (letrec
        ([helper
          (λ (counter args)
            (if (= counter i)
                (car args)
                (helper (+ counter 1) (cdr args))))])
      (helper 1 n))))

Die Nullfunktion kann mit beliebig vielen Parametern aufgerufen werden.

(C0)

(C0 1 2 3 4)

Die Projektionsfunktion erwartet als ersten Parameter den Inde des zu ermittelnden Arguments und anschließend eine variable Anzahl von Argumenten.

(U 1 1 2 3)

(U 3 1 2 3)

Als nächstes definieren wir die Substitution und die primitive Rekursion:

(define my-apply
  (lambda (ls)
    (apply (car ls) (cdr ls))))

(define substitute
  (lambda (f . g)
    (lambda n ; h
      (apply f
             (map my-apply
                  (map
                   (lambda (currentG)
                     (cons currentG n))
                   g))))))

(define prim-rec
  (lambda (f g)
    (lambda ni
      (letrec
          ([h
            (lambda (n1 rest)
              (if (= 0 n1)
                  (f rest)
                  (g n1 (h (P n1) rest) rest)
                  ))])
        (h (car ni) (cdr ni))))))

An Hand einiger Beispiele kann die Funktionsweise der beiden Prozeduren nachvollzogen werden. Als erstes betrachten wir die Potenzierung. Die beiden benötigten Prozeduren f und g werden wie folgt definiert:

(define pot-f
  (lambda (a)
    (C 1 a)))

(define pot-g
  (lambda (n h . args)
    (let ((x n) (a (caar args)))
      (mult (U 3 (P x) h a) 
            (U 2 (P x) h a)))))

Um nun aus diesen beiden Prozeduren die Potenzfunktion zu generieren wird die primitive Rekursion angewandt:

(define pot-x-a (prim-rec pot-f pot-g))

(pot-x-a 2 5)

BuK-Kreativaufgabe10 G2

Aufgabenstellung

Basisfunktionen

Suche