---
# System prepended metadata

title: ' Lista 4'

---

# Lista 4
E ogólnie to, co już zaczęłam, to sobie pisałam w plikach na moim dysku, więc jak wam pasuje taka forma, a gdzieś będą błędy, to możecie poprawić tutaj i wkleić nowego screena zamiast pisać od 0 u siebie nie:
https://uniwroc-my.sharepoint.com/:f:/g/personal/322282_uwr_edu_pl/EhaGVtAQwqNAoYEqRR1Zr28BVKZskC4IBiofowiawTvS8w?e=Z3HPcl

## Zadanie 1
:::success
Zrobione
:::
### Flow through assignments and tests
![image](https://hackmd.io/_uploads/HJPJBM70T.png)

### Flow along the control
![image](https://hackmd.io/_uploads/r1XVBfXA6.png)

### Sprawdzenie 
![image](https://hackmd.io/_uploads/Hy8W8MmR6.png)

## Zadanie 2
:::success
Raczej zrobione
:::
*Wykład - koło 45 minuty*
Algorytm działa tak, że dopóki w jakimś równaniu lewa i prawa strona nie spełniają zależności między sobą, to aktualizujemy równanie, aż do momentu gdy nie mamy takiej nierówności. Może nie jest to super intuicyjne, ale tutaj rozwiązaniami równań są zbiory (np. {(x, ?), (y, 1)}), a zamiennymi są nazwy/oznaczenia (np. $RD\circ(1)$). **Algorytm wylicza najmniejszy punkt stały.**
### Układ równań
![image](https://hackmd.io/_uploads/Sk1k1QmC6.png)


### Algorytm
Każde równanie jest postaci $RD_j = F_j(RD_1, RD_2, ..., RD_{18})$
![image](https://hackmd.io/_uploads/SyGiJQ7Rp.png)

### Rozwiązanie
Algorytm zaczynamy od podstawienia wartości, którą znamy.
Używam skróconego zapisu $xk = (x, l)$, żeby było czytelnie no i wycofałam się z tych oznaczeń bez kółeczek w sensie RD1, RD2, ... RD18, bo to kompletnie nieprzejrzyste dla mnie było.
![image](https://hackmd.io/_uploads/SyszmV7Ap.png)

**Porównując roziwązanie d ozadania 6**


## Zadanie 3
### Definicje, których nie rozumiem
$Kill$ (wykład koło 1:40-45) - usunięcie wszyztkich wyrażeń zawierajacych x w celu uzyskania faktów prawdziwych na wejściu do zbioru prawdziwych faktów. Czyli np. wyliczyliśmy gdzieś wcześniej x + 5, którego mogliśmy gdzieś użyć, ale potem przypisujemy do x nową wartość, więc wcześniejsza wartość x + 5 jest już nieaktualna.

$Gen$ (też coś koło tego) - gdy np. x = p + y + z,
to wszystkie podwyrażenia p + y, p + z, p + y + z (to jakoś dziwnie się robi i te wartości mogą być gdzieś zapamiętywane) stają się dostępne, i ta funkcja generująca je wylicza.


### Przykład z wykładu
Czemu zabijamy pary, które już są na pewno martwe, np. y? w 4 i x? w 5? 
Nie wiem, ale będę robić analogicznie (a jak dojdziemy do wniosku, że tak nie ma być, to poprawimy). **Bo ogólnie zabijamy wszystkie wyrażenia związane z tymi zmiennymi, żebyśmy nie mogli użyć jakichś przestarzałych informacji(tak jak opisałem wyżej z tymi podwyrażeniami).**
![image](https://hackmd.io/_uploads/BkMtMNXR6.png)

### Wystąpienia funkcji kill() i gen()
![image](https://hackmd.io/_uploads/r1xT44QRa.png)
**w równaniach chyba tak?**
![image](https://hackmd.io/_uploads/rk1QRLX0p.png)

### Definicje gen(read) i kill(read)
![image](https://hackmd.io/_uploads/Hyj3mN7Ap.png)
**Nasze definicje:**
$gen([read(x)]^l) = \{(x,l)\}$
$kill([read(x)]^l) = \{(x,?)\} \cup \{(x, l') | B^{l'}\}$

### Algorytm wyliczania tych wartości
![image](https://hackmd.io/_uploads/HkdyQvQAT.png)



## Zadanie 4
Idę jak burza, a wy co, RPiS robicie frajerzy?
spierdalaj

![431014573_652256033669646_4125482114538093054_n](https://hackmd.io/_uploads/HkgbNrQC6.png)


### $RD_{exit}$ (zamalowane kropki)
![image](https://hackmd.io/_uploads/BJMkOVmCT.png)

### $RD_{entry}$ (puste kropki)
![image](https://hackmd.io/_uploads/rkz7uVmAp.png)

### Rozwiązanie układu
Ogólnie nie czaję clue tego zadania, chyba, że wg slides1/28 nie mogę zrobić takiej podwójnej sumy z dwóch przypadków. **możesz możesz :>>>** *:3*
**Równania**
![image](https://hackmd.io/_uploads/S1V0FNQRp.png)

**Rozwiązanie według algorytmu**
![image](https://hackmd.io/_uploads/HyJXTNX06.png)

**W rzeczywistości jednak zauważamy, że x zawsze będzie większe od 0, więc w ostatecznym wyniku nie będzie (y,4).**


## Zadanie 5
:::success
jest git? chuj wie XD czekaj zgubilem mózg
Tu Maciek z przyszłości i akceptuje to rozwiązanie.
:::
Podręcznik z odnośnikiem do tego zadania, jak komuś się nie chce szukać: https://faculty.sist.shanghaitech.edu.cn/faculty/songfu/cav/PPA.pdf strona 75 w dokumencie.
### Analiza zmiennych żywych
Teraz będziemy analizować programy pod trochę innym kątem - wcześniej interesowało nas, w którym miejscu programu była *ostatni raz* przypisywana wartość do danej zmiennej. Teraz będziemy *patrzeć w przód* - analizować, które przypisania zmiennych faktycznie mają wpływ na działanie programu.
Czyli generalnie chcemy przeanalizować, w których miejscach programu moglibyśmy spotkać takie ostrzeżenie:
![image](https://hackmd.io/_uploads/HJLuu4NRa.png)

#### **Idea i definicja**
Zmienną uważamy za **żywą**, jeśli jeszcze gdzieś jej *może* użyjemy (np. do wyliczenia innej zmiennej), zanim ją zredefiniujemy (przypiszemy jej nową wartość). *Może* w tym przypadku oznacza, że np. zostanie użyta w jakiejś gałęzi instrukcji warunkowej.
![image](https://hackmd.io/_uploads/r11w2vQ06.png)

**Przykład**
![image](https://hackmd.io/_uploads/rkgrUVNCp.png)
Ma sens - pierwsze przypisanie ```x := 2``` jest zbędne, bo przecież w 3 instrukcji redefiniujemy wartość ```x := 1```, a w 2 jej nie używamy. Po wyjściu z 3 obydwie zmienne są żywe, bo używamy ich do porównania w 4.

#### **Definicja *kill* i *gen* w analizie zmiennych żywych**
$FV(a)$ - zbiór wszystkich zmiennych występujących w wyrażeniu $a$
![image](https://hackmd.io/_uploads/SkOnwP7RT.png)
W sumie ma sens, jak popatrzymy na przykład. 
Robiąc przypisanie, "zabijamy" zmienną do której przypisujemy w tym sensie, że jej poprzednia wartość nas już nie obchodzi (czyli, jeżeli od poprzedniego przypisania nie była używana, to znaczy, że była martwa).
Za to nasze przypisanie może używać innych zmiennych, które z kolei w tamtym momencie stają się żywe, bo ich używamy.
Tzn. ```x := y + 1 ``` "zabija" starą wartość ```x```, ale sprawia, że wartość ```y``` jest "żywa", no bo właśnie w tym miejscu jej używamy.

**Przykład**
![image](https://hackmd.io/_uploads/rkO1uvmR6.png)


### Analiza programu

#### Przykład z wykładu
Zwróćmy uwagę, że tutaj równania odnoszą się do tego, co jest *przed nimi* tzn. równanie opisujące wejście do instrukcji 1, odwołuje się do równania opisującego wyjście z niej, a to opisujące wyjście z instrukcji 1 odwołuje się do wejścia do instrukcji 2. To jest ta intuicja, że do analizy zmiennych żywych czytamy program *od końca*. Dlatego też "punkt startowy" (w którym nie ma żadnej zmiennej żywej) to wyjście z ostatniej instrukcji programu.
Program:
![image](https://hackmd.io/_uploads/By7c2V4RT.png)
Układ równań:
![image](https://hackmd.io/_uploads/Hybz2NVCp.png)
Rozwiązanie:
![image](https://hackmd.io/_uploads/BJGN3V4AT.png)

#### Analiza programu z zadania 1
Program:
![image](https://hackmd.io/_uploads/HJt1GH4A6.png)
Układ równań:
![image](https://hackmd.io/_uploads/HyKKNSEAp.png)
Rozwiązanie:
![image](https://hackmd.io/_uploads/ryesVSN0p.png)
Wydaje mi się poprawne - $z$ jest żywe aż  do 4, gdzie je wykorzystujemy jedyny raz w programie, $x$ też jest żywe do wyjścia z 5 itd.


