D120.de/forum

We wrote general recursive functions using a fixpoint combinator in the untyped lambda calculus, see Assignment 4.
Our problems only started when we moved on to the simply typed calculus because we could not - as you said - type the fixpoint combinator.

I have some problems to understand the task. Are the relevant kinds of analyses limited to controlflow insensitive analyses or is the "controlflow ignoring" or "arbitrary execution order" to be understood as, e.g., the permutation c() b() d() a() instead of the right method call order a() b() c() d(...

With your approach you can a _subset_ of the possible lists, namely the lists of length n (to stick with your example). But that is not what the type defintion calls for. You can define lists of a maximal length with our language (and type system) namely by inlining the NumList definition but you ca...

Well and I don't know how to get more specific without spelling out the problem with our language

Because our language is typed (or rather the way it is typed) you can't do what you want to do with lambda expressions.

We also have types in our language.

AlexanderF hat geschrieben:so I cannot show that progress stil holds because in this example it does not?

It does. Consider the definition of progress /preservation in detail, for how many reduction steps progress is "guaranteed" and if you still satisfy the premise for e'.

Das ist auch richtig.

Mit
\(\ln_a(n)' = \frac{1}{n}\)
und einem Basiswechsel zu e kommt man aber zu
\(\log_a(n)' = const \cdot \frac{1}{n}\)

Die Invariante bedeutet, dass in dem Pfad nur Knoten sind, die schon bearbeitet wurden. Mit dem zitierten Satz aus dem Korrektheitsbeweis habe ich auch so meine Probleme, die Idee ist hier aber, dass Q noch nicht leer ist und u der naechste Knoten ist der bearbeitet wird.

Auch wenn die Standardlibrary von Java relativ umfangreich ist, enthaelt sie nicht jede Datenstruktur oder jeden Algorithmus. Mehr zu UnionFind (dem Algorithmus) und Disjoint-set (der Datenstruktur) gibt es bei Wikipedia, inklusive Links Implementierungen: https://en.wikipedia.org/wiki/Disjoint-set_...

Danke!

In Aufgabe 2 wird die Datei `bakertilly.txt` erwaehnt, im Moodle fehlt sie aber noch.

@AnnaW: Hum, nun ... genau unter \(F\).

Es ist geplant, dass die (Theorie-)Workshops vor der Klausur in der vorlesungsfreien Zeit nochmal wiederholt werden.

Die Invariante der Datenstruktur ist nicht die einzige, die verletzt werden kann.

All fields, yes.