Tutorium 11

Gruppen 5 und 7
Samuel Teuber
propa@teuber.dev
https://teuber.dev/propa

Evaluation

Übungsblätter

  • Fragen?
  • Probleme?
  • Zu schwierig?

Übungsblatt 9

Aufgabe 1a: Unifikatoren

$$ X_1 = X_2\\ X_2 = X_3 $$

Ist $\left[X_1⇨X_2, X_2⇨X_3\right]$ ein Unifikator?

Was ist $\left[X_2⇨X_3\right]\circ\left[X_1⇨X_2\right]$ "ausmultipliziert"?
Ist das ein mgu? Ist das ein Unifikator?

Wie sieht es aus mit $\left[X_1⇨a,X_2⇨a, X_3⇨a\right]$?

Aufgabe 1b: Unifikatoren

$$ a(t_1,a(X_3,X_4))=a(X_1,X_2)\\ X_3=t_2\\ X_4=X_1 $$

Unifikator?

Ergebnis: $$ \left[X_1⇨t_1,X_2⇨a(t_2,t_1),X_3⇨t_2,X_4⇨t_1\right] $$

Aufgabe 1c: Unifikatoren

$$ a\left( \left[1,2,3\right],\left[3,4\right],L \right) = a\left( \left[X\mid Xs\right], \left[Y\mid Ys\right], L2 \right) $$

Unifikator?

Ergebnis: $$ \left[X⇨1,Xs⇨\left[2,3\right],Y⇨3,Ys⇨[4],L⇨L2\right] $$

Aufgabe 2: $\lambda$-Terme und die Herleitung ihrer allgemeinsten Typen

$$ t_1 = \lambda z.\ z\ :\ \alpha\rightarrow\alpha\\ t_2 = \lambda f.\ \lambda x.\ f\ x\ :\ \left(\alpha\rightarrow\beta\right) \rightarrow \alpha \rightarrow \beta \\ t_3 = \lambda f.\ \lambda x.\ f\ (f\ x)\ :\ \left(\alpha \rightarrow \alpha\right) \rightarrow \alpha \rightarrow \alpha \\ t_4 = \lambda x.\ \lambda y.\ y\ (x\ y)\ :\ \left( \left(\beta \rightarrow \alpha\right) \rightarrow \beta\right) \rightarrow \left(\beta \rightarrow \alpha\right) \rightarrow \alpha $$

Fragen?

Aufgabe 3: Typabstraktion

In der Typabstraktion $ta(\tau, \Gamma)$ werden nicht alle freien Typvariablen von $\tau$ quantifiziert, sondern nur die, die nicht frei in den Typannahmen $\Gamma$ vorkommen.

Beispiel: $$ \tau = \alpha \rightarrow \left(\beta\rightarrow\gamma\right) \rightarrow \gamma\\ \Gamma = \{y : \beta, g : \beta \rightarrow \beta\} $$

Was ist hier jetzt $ta(\tau, \Gamma)$?

$$ ta(\tau,\Gamma) = \forall \alpha. \alpha\rightarrow\left(\beta\rightarrow\beta\right)\rightarrow\beta $$

Warum machen wir das so?

Einfachstes Beispiel: $\Gamma\vdash \textbf{let } f=\lambda x.\lambda z.z y \textbf{ in } f 1 g$

Aufgabe 4: LET Polymorphismus

Fragen?

Übungsblatt X: Tutorenrätsel

  • indexOf(E,L,N) Prädikat
In [3]:
indexOf(X,[X|_],0).
indexOf(X,[_|XS],N) :- indexOf(X,XS,M), N is M+1.





















    

  • solution(S) Prädikat
    • 














In [5]:



    


solution(S) :-
   % Lösung ist eine Liste mit Einträgen der Form ["Name", "Lieblingsspiel", "Programmiersprache", "Algorithmus"]
   S = [[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]],
   clue1(S),
   clue2(S),
   clue3(S),
   clue4(S),
   clue5(S),
   clue6(S),
   clue7(S),
   clue8(S),
   clue9(S).



    















    


























    

  • clue2(S)?
    Der Tutor, der gern Battlefield 2 spielt, befindet sich links von dem Tutor der gern in Rustprogrammiert.
    

    

    • 














In [6]:



    


clue2(Solution) :-
    indexOf([_,"Battlefield 2",_,_], Solution, N1),
    indexOf([_,_,"Rust",_], Solution, N2),
    N2 > N1.



    















    
























In [13]:



    


solution(S) :-
   S = [[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]],
   clue1(S),clue2(S),clue3(S),clue4(S),clue5(S),clue6(S),clue7(S),clue8(S),clue9(S).
clue1(Solution) :-
  indexOf([_,_,_,"Boyer-Moore"], Solution, N1),
  indexOf([_,_,"C",_], Solution, N2),
  N2 > N1.
clue2(Solution) :-
    indexOf([_,"Battlefield 2",_,_], Solution, N1),
    indexOf([_,_,"Rust",_], Solution, N2),
    N2 > N1.
clue3(Solution) :-
	indexOf(["Daniel",_,_,_], Solution, N1),
	indexOf([_,"GTA: San Andreas",_,_], Solution, N2),
	AbsDiff is abs(N2 - N1),
	AbsDiff >= 2.
clue4(Solution) :-
	indexOf([_,"Assassin's Creed 2",_,_], Solution, N1),
	indexOf([_,_,_,"DPLL"], Solution, N2),
	Diff is N2 - N1,
	Diff >= 2.
clue5(Solution) :-
    indexOf([_,_,"C#",_], Solution, N1),
    indexOf([_,"GTA: San Andreas",_,_], Solution, N2),
    Diff is N2 - N1,
    member(Diff, [-1,1]).
clue6(Solution) :-
    indexOf([_,_,_,"Dijkstra"], Solution, N1),
    indexOf(["Lars",_,_,_], Solution, N2),
	N2 is N1 + 1.
clue7(Solution) :-
    indexOf([_,_,"Racket",_], Solution, N1),
    indexOf(["Paul",_,_,_], Solution, N2),
	AbsDiff is abs(N2-N1),
	AbsDiff is 3.
clue8(Solution) :-
   indexOf(["Samuel",_,_,_], Solution, N1),
   N2 is N1 + 1,
   indexOf([_,"Satisfactory",_,_], Solution, N2).
clue9(Solution) :-
  member([_,"Assassin's Creed 2",_,"Kruskal"], Solution).
indexOf(X,[X|_],0).
indexOf(X,[_|XS],N) :- indexOf(X,XS,M), N is M+1.
QUERYSTART
solution(S)
QUERYEND



    















    






Warning: /tmp/tmpifqbuqa3/code.pl:53:
	Singleton variables: [S]
 
----------------------------------------- 
 Call of: 	 solution(_3186) 
 TRUE with:	 solution([[Daniel,Battlefield 2,Racket,Dijkstra],[Lars,Assassin's Creed 2,C#,Kruskal],[Samuel,GTA: San Andreas,Rust,Boyer-Moore],[Paul,Satisfactory,C,DPLL]])





















Ergebnis:



Warning: /tmp/tmp_xmuxsip/code.pl:53:
    Singleton variables: [S]

----------------------------------------- 
 Call of:    solution(_3186) 
 TRUE with:  solution([[Daniel,Battlefield 2,Racket,Dijkstra],[Lars,Assassin's Creed 2,C#,Kruskal],[Samuel,GTA: San Andreas,Rust,Boyer-Moore],[Paul,Satisfactory,C,DPLL]])















C/C++














Pointer
    

  • Deklaration: type *name = ...;  
    • 

  • Adressoperator: &variable  
    • 

  • Dereferenzierungsoperator: *variable
    • 



int myint = 10;
int *myptr = &myint;
int myint_again = myint;
















Arrays
    

  • Initialisierung:
      

    • type myarray[n];
      • 

    • type myarray[] = {1,2,3};
      • 

    • type myarray[n] = {1,2,3};
      • 

    

    • 

  • Arrayzugriff: myarray[i]
    • 
















Mit Pointern
int array[] = {42, 24, 21, 12};
int *myptr = array;
int i1 = array[1];
int i2 = myptr[1];
int i3 = *(myptr + 1);
















Annahme:


sizeof(int); // = 4
sizeof(char); // = 1



Auf was greift der folgende Code Snippet zu?


int i4 = *(((char*)myptr)+4);
















Speicher
    

  • Variablen etc. in Funktion: Auf dem Stack
    • 

  • Für den Heap in C:
      

    • malloc(size) allokiert size btyes auf dem Heap
      • 

    • free(pointer) gibt den Speicherplatz an der Stelle pointer wieder frei
      • 

    

    • 

  • Für den Heap in C++:
      

    • Mit new/delete Keywords Objekte erstellen/löschen
      • 

    

    • 
















Übungsaufgabe
#include<stdio.h>

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

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



Läuft dieses Programm?

Ausgabe?















Funktionen und Pointer
Beispiel:


void my_int_func(int x, int *y) {
    *y = x+1;
}

void (*foo)(int, int*);
int main() {
    foo = &my_int_func; // Das hier ist spannend
    int y = 2;
    foo(4,&y);
    printf("%d", y); // Und das hier
}
















Raw Pointers in modernem C++
    

  • Vermeidet das in eurem eigenen (Nicht-ProPa) Code! Nutzt stattdessen lieber Smartpointers!
    
(Mögliche Stichwörter: std:unique_ptr, std:shared_ptr, std::weak_ptr)
    • 

  • Oder nutzt einfach gleich Rust ¯\(ツ)/¯
    • 
















Parallelprogrammierung
Parallelism: At least two threads executed simultaneously

Concurrency: At least two threads make progress















Flynn's Taxonomy
$$
\{\text{Single},\text{Multiple}\}\times\{\text{Instruction},\text{Data}\}
$$
    

  • SISD: von Neumann
    • 

  • SIMD: e.g. vector processors, GPU,...
    • 

  • MISD: redundant architectures (maybe pipelines of modern processors)
    • 

  • MIMD: multi-core processors
    • 
















Task Parallelism (MI)
Definierte Tasks laufen parallel


Data Parallelism (MD)
Aufteilung der Daten für ein und den selben Task















Amdahl's Law
Speedup
$$
S(n) = \frac{T(1)}{T(n)}
$$
mit $T(n)$ Zeit bei Nutzung von $n$ Prozessoren


Amdahl's Law: Maximal Speedup
$$
S(n) = \frac{1}{(1-p)+\frac{p}{n}} < \frac{1}{1-p}
$$
wobei $p$ der parallelisierbare Prozentsatz des Programms















MPI
Message Passing Interface















Praktische Hinweise
    

  • Kompilierung: mpic++ INPUTFILES
    • 

  • Ausführung: mpirun -np N PROGRAM ARGUMENTS
    • 
















Konzept
    

  • N Berechnungsprozessen
    • 

  • Kommunikation über Communiators
      

    • Standardcommunicator: MPI_COMM_WORLD
      • 

    

    • 

  • Jeder Prozess: Eigenen Rank $0\leq R_j < N$
      

    • Prozess mit Rank 0 wird oft als Master Control Program/root genutzt
      • 

    

    • 



Funktionen:


int my_rank;
int total_size;

MPI_Comm_size(MPI_COMM_WORLD,&total_size);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
















Übungsaufgabe
#include<stdio.h>
#include<mpi.h> //Wichtig!
int main(int argc, char** args) {
    MPI_Init(&argc,&args);

    // Erhalte Rank und Size in MPI_COMM_WORLD
    // Gib Rank und Size mit printf aus

    MPI_Finalize();
    return 0;
}
















Message Exchange
    

  • int MPI_Send(void *buffer, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)
      

    • Parameter:
        

      • buffer: Der Buffer
        • 

      • count: Wie viele Elemente senden wir?
        • 

      • datatype: Der Datentyp der Buffer Elemente
        • 

      • dest: Ziel Rank
        • 

      • tag: "Kontext" der Nachricht
        • 

      • comm: Communicator
        • 

      

      • 

    • Blockiert bis Buffer wiederverwendet werden kann
      • 

    

    • 

  • int MPI_Recv(void *buffer, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)
      

    • Parameter:
        

      • source: Rank der Quelle (kann auch MPI_ANY_SOURCE sein)
        • 

      • tag: kann auch MPI_ANY_TAG sein
        • 

      • status: Notwendig, kann Infos wie Tag, Quelle etc. enthalten
        • 

      

      • 

    • Blockiert bis Nachricht vollständig im Buffer
      • 

    

    • 
















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) { // Root Prozess
        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;
}
















Kommunikationsmodi
Für Send:


    

  1. Synchron: Aufeinander warten
    2. 

  2. Buffered: Explizite Buffer
    3. 

  3. Ready: Aufeinander warten, aber Receive muss bei Send schon initiiert sein
    
sonst undefined behaviour!
    4. 

  4. Standard: Implementation dependent
    5. 



Recv matcht alle Send Modi gleichzeitig















(Non-)Blocking
    

  • Blocking: Warten bis Buffer freigegeben/voll beschrieben
    • 

  • Non-Blocking: Sofortiger Return, Buffer möglicherweise noch nicht voll beschrieben
      

    • MPI_Isend(...,MPI_Request *request)
      • 

    • MPI_Irecv(...,MPI_Request *request)
      • 

    

    • 
















Kollektive Operationen
    

  • Broadcast
    • 

  • Scatter
    • 

  • Gather
    • 

  • Allgather
    • 

  • Alltoall
    • 

  • Reduce
    • 



    

  • Allreduce
    • 

  • Reduce-Scatter
    • 

  • Scan
    • 
















Beispiel: Zahlen 0 bis N sehr ineffizient aufsummieren
int MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm);
int MPI_Reduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype type, MPI_Op op, int root, MPI_Comm comm)

int main(int argc, char** argv) {
    int value;
    int myrank, size;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
    if(myrank== 0) { // Root Prozess
        int generated_values[size*10];
        for(int i = 1; i<=size; i++) {
            generated_values[i-1]=i;
        }
        MPI_Scatter(&generated_values, 1, MPI_INT, &value, 1, MPI_INT, 0, MPI_COMM_WORLD);
    } else {
        MPI_Scatter(NULL, 1, MPI_INT, &value, 1, MPI_INT, 0, MPI_COMM_WORLD);
    }
    int result;
    MPI_Reduce(&value,&result,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
    if(myrank==0){
        printf("Sum: %d",result);
    }
    MPI_Finalize();
    return 0;
}