Benutzer:MartinThoma/Programmierparadigmen

Fragen zur Vorlesung

Teil 2: Theoretische Grundlagen

Eta-Äquivalenz

Kann mir jemand die $\eta$-Äquivalenz, also insbesondere folgende Schreibweise von Folie 158 erklären:

$\lambda x.\lambda y.fzxy{\stackrel {\eta }{=}}\lambda x.fzx$

Frage auf cs.stackexchange.

Regelsysteme (Folie 186)

Frage: Was soll "Beispiel Prädikatenlogik: Syntaktische Herleitbarkeit ($\psi \vdash \varphi$)" bedeuten?

Antwort: Es wird ein Beispiel zur Funktionsweise des Frege'schen Schlussstrich an Hand den Regeln zur Syntaktischen Herleitbarkeit in der Prädikatenlogik gemacht.

Typinferenz

Allgemeines

Frage: Bekomme ich nur durch die APP-Regel neue Constraints?

Antwort: Nein, bei ABS ergibt sich ebenfalls ein neuer Constraint. Wenn man den unteren Typ $\alpha$ nennt, und die oberen beiden $\alpha _{1}$ und $\alpha _{2}$ so muss gelten, dass $\alpha =\alpha _{1}\rightarrow \alpha _{2}$. Im Beispiel ab Seite 197 werden auch bei VAR und CONST neue Constraints hinzugefügt.

Typsystem (Folie 191)

Frage: Was heißt $\vdash$ auf Folie 191, z.B.:

$\vdash (\lambda x.2):{\text{bool}}\rightarrow {\text{int}}$

Insbesondere will ich hier wissen, wie man $\vdash$ ausspricht.

Antwort:

• In der Fragestunde wurde gesagt, dass man es "aus <linke Seite> folgt syntaktisch <rechte Seite>". Dasselbe Zeichen mit einem doppelten horizontalen Strich wird "aus <linke Seite> folgt semantisch <rechte Seite>" gelesen.
• Rechts von diesem Zeichen stehen die Typannahmen. Den Sinn von dieser Schreibweise versteht man, glaube ich, am besten bei der "ABS"-Regel: Wenn man "ABS" anwendet, macht man die Typannahme "kleiner" und bekommt dafür ein "lambda"

Typsystem (Folie 192)

Frage: Was ist "Const"? Ich vermute eine Menge aller Konstanten, aber wo kommt diese her?7 Antwort: Ich erinnere mich daran, dass er sowas meinte wie "wo auch immer die Menge Const herkommt".

Frage: Was bedeutet es, dass keine Überschneidungen bei Typvariablen generiert weden dürfen? Kann mir jemand ein Beispiel sagen, wo das passieren würde?

Typsystem (Folie 193)

Frage:

• Was ist $(\sigma ,\tau )$? $\sigma$ ist eine Menge von Typsubstitutionen, aber was ist $\tau$?
• Was ist $(\Gamma ,t)$? $\Gamma$ ist ein Typkontext, aber was ist $t$?

Antwort:

• $\tau$ ist ein beliebiger, aber fester Typ.
• $t$ ist eine beliebige, aber feste, freie Variable.
  • Edit: $t$ ist glaube ich ein Term und keine Variable.

Typschema (Folie 206)

Frage: Ist ${\text{int}}\succeq {\text{int}}$ eine Typschemainstanziierung? Müsste dann nicht ${\text{int}}$ ein Typschema sein?

Typschema (Folie 207)

Frage: Warum sind $\lambda$-Gebundene Bezeichner niemals polymorph?

Antwort: "Ist halt so :-)". Ich denke die Typsierung funktioniert nun mal so, dass jeder Term _einen_ Typen erhält.

Parallelität

MPI

MPI_Gather

int MPI_Gather(void *sendbuf, int sendcount, 
    MPI_Datatype sendtype, 
    void *recvbuf, int recvcount, 
    MPI_Datatype recvtype, 
    int root, MPI_Comm comm)

Frage: Wann ist jemals sendcount != recvcount? Antwort: Vergleiche drittes Beispiel. Ohne spezielle Datenstruktur scheint es aber immer dasselbe zu sein.

Folie 10

Frage: Was soll die äußere for-Schleife in folgendem Beispiel?

for (i=0; i<size; i++) {
    MPI_Barrier(MPI_COMM_WORLD);
    if (i == myrank) {
        printf("Hello World, I have rank %d out of %d.\n",
            myrank, size);
    }
}

Wenn ich das mit mpicc for-example.c kompiliere und mit mpirun -np 3 a.out ausführe, erhalte ich:

Hello World, I have rank 0 out of 3.
Hello World, I have rank 1 out of 3.
Hello World, I have rank 2 out of 3.

Antwort:

• Durch die for-Schleife wird die Reihenfolge garantiert. Da i von 0-2 geht, werden auch in dieser Reihenfolge die Nachrichten ausgegeben.
• Ich glaube aber, dass es ohne MPI_Barrier(MPI_COMM_WORLD); nichtdeterministisch ist. Also die Hauptarbeit erledigt hier das Barrier Konstrukt. Kannst du es mal ohne Barrier probieren?

Folie 11

Frage: Wie kann eine Operation sowohl blockierend, als auch asynchron sein? Ich dachte, asynchrone Operationen sind gerade nicht blockierend.

Folie 13

Frage: Was ist das potentielle Probleme mit dem destination rank 1 in folgendem Beispiel?

#include "mpi.h"
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[]) {
    char msg[20];
    int myrank, tag=42;
    MPI_Status status;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank);

    if (myrank == 0) {
        strcpy(msg, "Hello student!");
        MPI_Send(msg, strlen(msg)+1, MPI_CHAR, 1, tag, MPI_COMM_WORLD);
    } else {
        MPI_Recv(msg, 20, MPI_CHAR, 0, tag, MPI_COMM_WORLD, &status);
        printf("received \"%s\"\n", msg);
    }
    
    MPI_Finalize();
    return 0;
}

Antwort: Es wird nicht geprüft, ob es überhaupt den rank 1 gibt. Vielleicht wurde das Programm nur mit einem Prozessor gestartet.

X10

Folie 22

Frage: Was ist 'remote data'?

Compilerbau

Frage: Was genau ist der abstrakte Syntaxbaum, was der konkrete Syntaxbaum?

Antwort:

• Der konkrete Syntaxbaum hat - im Gegensatz zum abstrakten Syntaxbaum - noch keine Typannotationen. (Richtig?)
• Siehe Seite 359f. Jedes Token erhält eine abstrakte Klasse. Dem Syntaxbaum kann man abgelesen, mit welchen Produktionen das Wort erzeugt wurde. Dem abstrakten Syntaxbaum sieht man an, welche "abstrakte" Struktur das Wort hat. Zum Beispiel hat der Term $5*x/7$ die abstrakte Struktur MultOp -> (Val->5, DivOp -> (Var->x, Val->7)). Dem Compiler ist es egal, wie das Wort erzeugt wurde, meistens soll es aber eine bestimmte Struktur haben, die hiermit geprüft werden kann. (Bin mir damit nicht sicher, macht im Moment aber am meisten Sinn für mich).

First / Follow

Frage: Warum ist auf Folie 348 Follow(E') = {#, )}? Ich dachte, es müsste Follow(E') = {#} sein.

Antwort: Wegen der Regel "F -> id | (E)" . E kann auf TE' abgebildet werden und somit folgt ein ")" auf ein E'

Fragen zur Klausuren

Altklausuren

WS2010/11

• Klausur mit Lösungen

Aufgabe 3: Typinferenz

Frage: Kann das bitte jemand erklären?

Aufgabe 4: Logische Programmierung

Frage zu b): Was bedeuten die gestrichelten Pfeile? Warum existiert ein Pfeil von $h$ nach $h$? Warum existiert sowohl ein Pfeil von $h$ nach $U$ als auch ein Pfeil von $U$ nach $h$?

Aufgabe 5: C

Code:

#include <stdio.h>

char p[] = "HelloWorld";
int i[] = {2,1,3,5,6}, j = 4;

int main()
{
    printf(&(p[*(i + j)]));
    return 0;
}

Ausgabe: orld

Frage: Wie kommt es zu dieser Ausgabe? Frage auf SO

Antwort: Auf SO

Aufgabe 7: MPI

Frage: Kann mir jemand erklären, warum die Musterlösung hier stimmt? (a und b)

Antwort zu a):

MPI_Scatter(sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, root, comm)

MPI_Scatter verteilt Daten vom Prozess root unter alle anderen Prozesse in der Gruppe, so daß, soweit möglich, alle Prozesse gleich große Anteile erhalten.

Konkret bedeutet das:

• buf_1 ist ein Buffer mit $k^{2}$ Werten. Jeder Prozess soll $k$ Werte erhalten. Also erhält jeder Prozess eine Zeile von dem Prozess 0.
• In der for-Schleife, also $k$-mal (für Prozess $i$, also den der Zeile $i$ der $k\times k$ Matrix hat): Jeder der $k$ verschiedenen Prozesse erhält genau einen int. Dieser wird im Array buf_3 an die i-te Stelle geschrieben. Also:
  • Knoten 0 hat Zeile 0 der Matrix (ich nenne sie mal A[zeile][spalte]) erhalten. Also: (buf_2 auf Knoten 0) == A[0]
  • Knoten 0 schickt den ersten Array-Eintrag von buf_2 an Knoten 0: (buf_2[0] auf Knoten 0) == A[0][0]
  • Knoten 0 schickt den zweiten Array-Eintrag von buf_2 an Knoten 1: (buf_2[1] auf Knoten 0) == A[0][1]
  • Allgemein: Knoten 0 schickt den i-ten Array-Eintrag von buf_2 auf Knoten_i: (buf_2[i] auf Knoten 0) == A[0][i]
  • Knoten 1 schickt den ersten Array-Eintrag von buf_2 an Knoten 0: (buf_2[0] auf Konten 1) == A[1][0]
  • Allgemein: Knoten 1 schickt den i-ten Array-Eintrag von buf_2 auf Knoten_i: (buf_2[i] auf Knoten 1) == A[1][i]
  • Allgemein: Knoten j schickt den i-ten Array-Eintrag von buf_2 auf Knoten_i: (buf_2[i] auf Knoten j) == A[j][i]

=> Knoten i Enthält die i-te Spalte

Antwort zu b):

int MPI_Alltoall(const void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, MPI_Comm comm)

MPI_Alltoall teilt Daten von jedem Prozeß einer Gruppe an alle anderen auf.

Also konkret:

MPI_Alltoall(buf_2, 1, MPI_INT, buf_3, 1, MPI_INT, comm)

• Für jeden der $k$ Prozesse in comm gilt:
  • Für die Elemente aus buf_2 wird jeweils 1 Element auf einen Prozess in comm gelegt.
  • Dort wird es jeweils in buf_3 gelegt.

Ich glaube da gibt es nicht viel mehr zu erklären. Die Operation macht halt das gewünschte.

SS2011

• Klausur mit Lösungen

Aufgabe 3: Typinferenz

Frage: Wie muss man bei dieser Aufgabe vorgehen?

Frage: Warum ist $y:\beta$ nicht im Typkontext $\Gamma$? Ich dachte, wenn etwas im Typkontext höher, also als Bedingung für den Schlussstrich, ist, dann muss es in allen tieferen Ebenen mitgezogen werden?

Aufgabe 4: Logische Programmierung

Frage: Wie funktioniert das Rätsel?

Antwort: Folgende Schritte durchführen:

1. 8-0-0
2. 5-0-3
3. 5-3-0
4. 2-3-3
5. 2-5-1
6. 0-5-1
7. 1-5-0
8. 1-0-3
9. 4-0-0

Frage: Wie funktioniert Teil b?

Teilantwort

• F0 ist eine Liste mit 3 Elementen für die 3 Eimer (8L-Eimer, 5L-Eimer, 3L-Eimer).
• FL ist der gewünschte Füllzustand.
• Ms ist eine Liste aus Strings, die die durchgeführten Aktionen beschreibt.
• Fs ist eine Liste von bereits besuchten zuständen.

 solve(X,X,[],_).
 solve(X,Y,[M|Ms],Fs) :- move(X,M,F),not(member(F,Fs)),solve(F,Y,Ms,[F|Fs]).

Die erste Zeile deckt den Fall ab, dass wir bereits die gewünschte Konfiguration haben

Die zweite Zeile ist interessanter.

• A :- B ist als "Wenn B gilt, dann mache A" zu lesen.
• , auf der rechten Seite ist als logisches "und" zu lesen.
• [F|Fs] nimmt eine Liste Fs und eine Element F und erstellt eine neue Liste, die mit F beginnt und die Elemente aus Fs hat

Also: Falls wir den Zug machen, in dem wir von der Konfiguration X mit der Beschreibung M in die Konfiguration F übergehen UND diese Konfiguration F nicht in der Liste Fs ist UND wir von der Konfiguration F in die Konfiguration Y kommen, dann mache den übergang von der Konfiguration X in die Konfiguration Y. (TODO: Stimmt das so?)

Für das 4L Problem würde man das so benutzen:

 solution(Ms) :- start(F0), solve(F0, FL, Ms, [F0]), final(FL).
 start((8,0,0)).
 final((_,4,_)).
 final((4,_,_)).

Aufgabe 6: X10

Frage: Was ist here?
Antwort: Im Aufgabentext beschrieben. here in diesem Kontext ist ein bestimmter Place. Siehe Seite 16 der X10-Folien.

Aufgabe 7: Scala

Frage: Was macht ein einzelnes Ausrufezeichen in folgendem Code?

class SquareChecker extends Actor {
    def squareCheckPartA(input: Int): Boolean = {
        var resultA = (input % 10 != 2 && input % 10 != 3)
        return resultA
    }
    def squareCheckParallel(input: Int): Boolean = {
        val firstHelper = new HelperActor(this).start
        firstHelper ! input
        val resultA = squareCheckPartA(input)
        var resultHelper = true
        receive { // default "case _" not used here
            case x : Boolean => resultHelper = x
        }
        return resultA && resultHelper
    }
    def act() { }
}
class HelperActor(parent: SquareChecker) extends Actor {
    def act = receive { case x: Int => squareCheckPartB(x)}
    def squareCheckPartB(input: Int) {
        var resultB = input % 10 != 7 && input % 10 != 8
        parent ! resultB
    }
}

Frage im Forum im VAB

Antwort: Siehe Scala-Folien Seite 52. Zitat Forum: "parent ! resultB" sendet eine Nachricht mit Inhalt "resultB" an (den Actor) "parent" (nachzulesen in den Scala-Folien, Folie Nr. 52, "Messaging, the Basics")."

SS2012

• Klausur mit Lösungen

Aufgabe 2: Prolog

Frage: Wie Funktioniert das Kohlkopf / Ziege / Wolf - Rätsel?

Antwort: Man kann nur den Kohlkopf und den Wolf unbeaufsichtigt lassen.

1. Also bringt man im ersten Schritt die Ziege auf die andere Seite.
2. Dann fährt man zurück, nimmt den Kohlkopf mit auf die andere Seite und nimmt die Ziege wieder zurück
3. Man läd die Ziege aus, den Wolf ein und fährt den Wolf auf die andere Seite.
4. Nun fährt man wieder zurück und hohlt die Ziege.

Aufgabe 7: Syntaktische Analyse

Frage: Ich glaube die Lösung ist falsch. Wie würde der Parser den Regulären Ausdruck $((char\cup \varepsilon )\cup char)$ parsen?

Antwort: Ich bin das mal durchgegangen und komme auf das korrekte Ergebnis. Beachte, dass char ein Zeichen ist. Zum Beispiel ist $((A\cup \varepsilon )\cup B)$ ein konkretes Beispiel zu deinem regulären Ausdruck.

Step-by-step:

"Methode"	Aktuelles Zeichen	AST (Ergebnis aus selber Zeile)
R("$((A\cup \varepsilon )\cup B)$")	(	--
R'(R("$(A\cup \varepsilon )\cup B)$"))	(	--
R'(R'(R("$A\cup \varepsilon )\cup B)$")))	A	char->A
R'(R'("$\cup \varepsilon )\cup B)$","$A$"))	$\cup$	Union -> (char->A, R($\varepsilon )\cup B)$)) = Union -> (char->A, $\varepsilon )$))
R'("$\cup B)$", "$((A\cup \varepsilon )$")	$\cup$ (Durch geschachtelten Aufruf von R ist aktuelles Token weiter vorgerückt)	Union -> (Union -> (char->A, $\varepsilon )$)), R($B)$)) = Union -> (Union -> (char->A, $\varepsilon )$)), char->B)

Dabei sind der erste Parameter immer der aktuelle Rest des RegEx, und die zweiten Parameter bei R'-Aufrüfen die Belegung von left für die R' Methode. Hoffentlich versteht man das so besser, mir ist keine bessere Formatierung eingefallen.

Das komplizierte ist es, bei den inneren Verschachtelungen zu beachten, dass der Token weitergerückt wird. Nach dem letzten Schritt ist man fertig, da wiederum im geschachtelten Aufruf von R das aktuelle Token auf ')' verschoben wurde, was im UNION-case von R' "akzeptiert" wird und weiter gesprungen wird an das Wortende.

Der erhaltene AST stimmt mit dem überein, den ich bekomme, wenn ich deinen RegEx manuell produziere.

WS 2011/2012

• Klausur mit Lösung

Aufgabe 2: Prolog

Frage: Warum wird die zweite Zeile in

remove([(X,A)|L],X,[(X,ANew)|L]) :- A>0, ANew is A-1.
remove([ X   |L],Y,[   X    |L1]):- remove(L,Y,L1).

benötigt?

Aufgabe 4: Typinferenz

Frage: Wie kommt man in der a) auf $\Gamma$?

Aufgabe 7: X10

Frage: What is the difference of 'async' before or after for in X10?

Aufgabe 8: Syntaktische Analyse

Teilaufgabe a

Frage: Wo kommt diese Syntax her? Antwort: Folie 359f.

WS 2012/2013

• Klausur mit Lösung

Aufgabe 2

Frage zu Teil b): Was ist die Normalform einer $\lambda$-Funktion?

Aufgabe 9

Frage: Warum ist * nicht in Follow(R)?

SS 2013

• Klausur mit Lösung

Aufgabe 3: Typinferenz

Frage:

Sind alle Terme der Form

$(\alpha \rightarrow \alpha )\rightarrow \alpha \rightarrow \alpha$

auch von der Form

$(\alpha \rightarrow \alpha )\rightarrow (\alpha \rightarrow \alpha )$?

Antwort: Ja, weil rechtsassoziativ.

Materialien

• Klausur-Artikel
• Skript (Quellen)
• Videos
  • Why Scala?