fp

Wir haben zuerst die vorgeschlagene Syntax aus dem Angaben-pdf implementiert wobei wir dann an einem Punkt etwas stecken geblieben sind. Ich bin dann nicht mehr weitergekommen und hab mir eine alternative Syntax überlegt und begonnen diese zu implementieren. Fabian konnte schließlich die erste retten und so haben wir nun zwei Implementationen zweier unterschiedlicher Syntax (wobei wir uns trotzdessen stark gegenseitig geholfen haben und eigentlich sehr gut von der Zweigleisigkeit profitieren konnten), genannt fpd (d für default wie in der Angabe) und fpa (a für alternativ). Die Interpreter haben auch diese Namensgebung - mehr zur Syntax weiter unten.

how to compile

Python 3.8.5 (sollte ab Python >= 3 funktionieren): entfällt.

how to run

Je nach Version

python fpd.py file.fpd

oder

python fpa.py file.fpa

Zum Beispiel liegt Beispiel gen aus der Angabe in test_gen.(fpd|fpa).

test_gen.fpd

{
append= x->y->cond x {head=x head, tail=append(x tail)y} y,
gen=x->cond x (append(gen(minus x 1)) {head=x, tail={}}) {}
}
gen 3

Ausführen liefert

❯ python fpd.py test_gen.fpd
{'head': 1, 'tail': {'head': 2, 'tail': {'head': 3, 'tail': {}}}}

test_gen.fpa

(
    {
        APPEND=<x>(<y>(? x {HEAD=(x HEAD), TAIL=(APPEND (x TAIL) y)} y)), 
        GEN=<x>(? x (APPEND (GEN (- x 1)) {HEAD=x, TAIL={}}) {})
    } 
    (GEN 3)
)

Ausführen liefert

❯ python fpa.py test_gen.fpa
{'HEAD': i'1,
 'TAIL': {'HEAD': i'2, 'TAIL': {'HEAD': i'3, 'TAIL': {}}}}

Weil ja schließlich mindestens eine Version bewertet werden muss, entscheiden wir uns für fpa und der Rest dieser Readme beschäftigt sich nur mehr damit.

fpa

syntax

• Zahl: zahl, z.B. 3, 80, -6
• Operatoren:
  • + Addition
  • - Subtraktion
  • * Multiplikation
  • / Division
  • ? Ternary Operator / Conditional
• Lambda function: <varname>(...) wobei varname lowercase sein muss und ... den function body darstellt. Z.B. <x>(+ x 1) oder <x>(<y>(* x y)).
• Record: {IDENTONE=..., IDENTTWO=..., .,.} wobei die Identifier uppercase sein müssen und ... die zuzuweisende Expression darstellt, welche eine Zahl, ein anderer Record, eine Lambda function, oder ein Call sein kann. .,. weißt darauf hin, dass records beliebig groß sein können (falls ihr Computer den nötigen RAM hat)
• Call: (callee arg1 arg2 arg3 ...) wobei die Argumente beliebig sind. Die Ausführung eines calls hängt vom callee ab:
  • Keine Argumente: Evaluation des callee ohne neue Items am Call Stack. Dies hat den Zweck beliebige Klammern tolerieren zu können, i.e. ((+ (5) (3))).
  • Lambda function: Wird mit dem letzten Argument aufgerufen. Die restlichen werden rekursiv als call_stack nach innen weitergegeben.
  • Record: Der Eintrag des Records mit dem Identifier oder Call arg1 wird evaluiert. Es muss genau ein Argument übergeben werden, sonst Fehler.
  • Call: Rekursive Behandlung. Alle Argumente werden dem Call Stack zugefügt.
  • Operator:
    • * und +: Beliebig viele argumente, also z.b. (+ 1 2 3 4)
    • / und -: Genau zwei Argumente, also z.B. <x>(- x 1) oder (/ 8 2)
    • ?: Genau drei Argumente mit der Semantik (? condition then else). Condition ist dann erfüllt wenn sie zu ungleich 0 evaluiert. Siehe z.B. das Beispiel zur Fakultät weiter unten. Die Evaluation ist lazy.

Betrachten wir das Beispiel der Fakultät (an diesem wir auch Rekursion sehen können):

({FAC=<x>(? x (* x (FAC (- x 1))) 1)} (FAC 4))

Zuerst stecken wir unsere Fakultätsfunktion in einen Record um sie leicht rekursiv aufrufen zu können. In dieser betrachten wir zunächst die Variable x: Falls Sie ungleich 0 ist, so machen wir einen call der x multipliziert mit dem Ergebnis eines rekursives Aufrufs von FAC dessen Argument (- x 1) ist, also eines weniger als x, andernfalls geben wir 1 zurück, was dann die Rekursion stoppt. Um nun diese Funktion aufrufen zu können, packen wir Sie in einen Call mit dem Record als Callee und haben nun im (einzigen) Argument Zugriff darauf, wo wir FAC mit 4 ausführen. Alternativ kann man auch wie folgt vorgehen:

(({FAC=<x>(? x (* x (FAC (- x 1))) 1)} FAC) 4)

In beiden Fällen lautet das Ergebnis 24.

testing

Klarerweise wurde während der Programmierung die ganze Zeit getestet. Folgende Tests haben sich als nützlich herausgestellt, beim Einführen neuer Features während des Entwicklungsprozesses, um das Brechen älterer Features zu erkennen bzw. zu verhindern:

assert parse("(+ 5 (* 3 9))").eval() == 32
assert parse("(((+ 5 ((((* ((3)) 9)))))))").eval() == 32
assert parse("(<x>(* 5 x) 3)").eval() == 15
assert parse("(<y>(<x>(- y x)) 5 3)").eval() == 2
assert parse("(<y>(((<x>(- y x)))) 3 5)").eval() == -2
assert parse("((<y>(<x>(- y x)) 5) 3)").eval() == 2
assert parse("((<y>(<x>(- y x)) 3) 5)").eval() == -2
assert parse("({A = 5, B = <x>(+ A x)} (B 11))").eval() == 16
assert parse("({A = 5, B = <x>(+ A x)} (B A))").eval() == 10
assert parse("({FAC=<x>(? x (* x (FAC (- x 1))) 1)} (FAC 4))").eval() == 24
assert parse("(({FAC=<x>(? x (* x (FAC (- x 1))) 1)} FAC) 4)").eval() == 24
assert parse("({A=8, B={C=3}} (B C))").eval() == 3
assert parse("(<x>(x A) {A=5})").eval() == 5

complexity

Zur Laufzeit von parse lässt sich sagen, dass, bezeichne n die Länge des Programms als Input, in jedem rekursiven Aufruf mindestens ein Zeichen behandelt wird und pro Zeichen mit maximal konstanter Anzahl an Aufrufen alle Zeichen danach betrachtet werden. Pro Zeichen lässt sich dieser Aufwand dann mit cn von oben beschränken und damit erhalten wir insgesamt die worst case performance von parse mit O(n^2)

Die Laufzeit des Evaluierens hängt klarerweise von dem zu interpretierenden Programm ab.

allocation of work

Wir haben gemeinsam begonnen mit dem Grundgerüst für fpd und uns gegenseitig geholfen Fehler zu finden und Ratschläge zu geben. Nach einem komplizierterem Bug hat Herr Weissenfels dann begonnen eine alternative Version zu schreiben. Schließlich konnten wir mit gegenseitiger Hilfe (-Werbung- lässt sich gut durch VSCode Liveshare umsetzen) beide Versionen zum Laufen bringen und waren dann mit Testen und Bug Fixing beschäftigt. Tatsaechlich war der Entwicklungsprozess ineinander stark verflochten und eine genauere Aufteilung ist den Git-Logs zu entnehmen.

Hiermit bestaetigen wir, dieses Programm persoenlich entwickelt zu haben.