Vaje 2

Ukazni programski jezik

V teh vajah obravnavamo kodo, ki sestoji samo iz majhnega delčka jave:

• osnovnih aritmetičnih in boolovih izrazov
• ukaza print(e), ki je okrajšava za System.out.print(e)
• prireditvenega stavka x = e
• zaporedja ukazov A ; B
• pogojnega stavka if (P) { A } else { B }
• in zanke while (P) { A } ter ukaza break

Pretvorba zanke for v zanko while

Lahko bi dodali zanko for, a je pravzaprav ne potrebujemo. Kako bi zanko

for (A; P; C) {
    B;
}

predelali v ekvivalentno kodo, ki uporablja samo while?

Pretvorba zanke do v zanko while

V while predelajte še zanko do:

do {
  A;
} while (P);

Odstranjevanje mrtve kode

Mrtva koda (angl. dead code) je del kode, za katerega zagotovo vemo, da se ne bo izvedel. Tako kodo lahko brez škode odstranimo. Nekaj primerov odstranjevanja mrtve kode:

• Če vemo, da pogoj P v if (P) { A } else { B } zagotovo velja, potem se B ne izvede, zato lahko pogojni stavek poenostavimo v P ; A. Če nadalje vemo še, da P ne bo sprožil izjeme (zaradi deljenja z 0), potem lahko poenostavimo kar v A.
• Če se v A ; B ukaz A nikoli ne konča, se B ne bo izvedel in ga lahko odstranimo.
• Če ob vstopu v while (P) { A } pogoj P ne velja, se zanka sploh ne izvede in jo lahko odstranimo.

Primer 1

Odstranite mrtvo kodo v programu

print("Kdor to bere je ");
a = 3;
if (a * a < 10) {
    print("mula");
} else {
    print("osel");
}

Preveri ali GNU C prevajalnik ali zna odstaraniti mrtvo kodo. Lahko uporabiš https://godbolt.org/ (https://godbolt.org/z/hEhrovcqb). Lahko pa tudi uporabiš kar neposredno program gcc:

$ gcc primer1.c -S -O0 -o primer1-brez-oprimizacij.s
$ gcc primer1.c -S -O3 -o primer1.s
$ diff --color -y primer1-brez-oprimizacij.s primer1.s

// datoteka primer1.c
#include <stdio.h>
int primer1() {
    printf("Kdor to bere je ");
    int a = 3;
    if (a * a < 10) {
        printf("mula");
    } else {
        printf("osel");
    }
}

Primer 2

Odstranite mrtvo kodo v programu, kjer ima n neznano celoštevilsko vrednost:

k = n + (n - 1);
if (k % 2 == 0) {
    print("foo");
} else {
    print("bar");
}
m = k * (-k);
while (m > 0) {
    m = m - 1;
    print(m);
}

Še isto v C-ju (https://godbolt.org/z/ErPhv77o9).

#include <stdio.h>
int primer2(int n) {
    int k = n + (n - 1);
    if (k % 2 == 0) {
        printf("foo");
    } else {
        printf("bar");
    }
    int m = k * (-k);
    while (m > 0) {
        m = m - 1;
        printf("%d", m);
    }
}

Primer 3

Odstranite mrtvo kodo v programu:

i = 0;
while (i < 100) {
    if (i % 2 == 0) {
        p = i * (i - 1) * (i - 2);
    } else {
        p = i * (i + 1) * (i + 2);
    }

    if (p % 3 == 0) {
        break;
    } else { }
    i = i + 1;
}

if (i >= 100) {
    print("ni zanimivih števil");
} else {
    print("našel sem zanimivo število " + i);
}

Še isto v C-ju (https://godbolt.org/z/8Ycorq1Kj).

#include <stdio.h>
int primer3() {
    int i = 0;
    while (i < 100) {
        int p;
        if (i % 2 == 0) {
            p = i * (i - 1) * (i - 2);
        } else {
            p = i * (i + 1) * (i + 2);
        }

        if (p % 3 == 0) {
            break;
        } else { }
        i = i + 1;
    }

    if (i >= 100) {
        printf("ni zanimivih števil");
    } else {
        printf("našel sem zanimivo število %d", i);
    }
}

Primer 4

Odstranite mrtvo kodo v programu:

s = 0;
i = 0;
while (i < 100) {
    s = s + i;
}
print(s);

Še isto v C-ju (https://godbolt.org/z/PEMTcGTaa).

#include <stdio.h>
int primer4() {
    int s = 0;
    int i = 0;
    while (i < 100) {
        s = s + i;
    }
    printf("%d", s);
}

Program, ki odstranja mrtvo kodo

V tej nalogi dodamo še uporabo tabel in funkcij. Dobri prevajalniki se trudijo odstraniti čim več mrtve kode.

Ali lahko implementiramo program, ki vedno odstrani vso mrtvo kodo?

Uporabi znanje iz teorije izračunljivosti in naslednjo opazko: če se v programu

A ;
B

ukaz A nikoli ne konča (se zacikla), potem je B mrtva koda.

Odstranjevanje ukaza break

V tej nalogi bomo ugotovili, da se lahko ukaza break znebimo. Najprej naredimo nekaj primerov.

Primer 1

Naslednjo kodo predelajte v enakovredno kodo, ki ne uporablja ukaza break, pri čemer ima n neznano celoštevilsko vrednost:

while (n > 0) {
    digit = n % 10;
    if (digit == 7) {
        print(n + " vsebuje števko 7");
        break;
    } else { }
    n = n / 10;
}

Primer 2

Naslednjo kodo predelajte v enakovredno kodo, ki ne uporablja ukaza break.

// najdi najmanjše popolno število
n = 1;
while (true) {
    d = 1;
    vsota = 0; // vsota deliteljev števila n
    while (d < n) {
        if (n % d == 0) {
            vsota = vsota + d;
        } else { }
        if (vsota > n) {
            break;
        } else { }
        d = d + 1;
    }
    if (vsota == n) {
        break;
    } else { }
    print(n + " ni popolno število");
    n = n + 1;
}
print("našel popolno število: " + n);

Splošni postopek

Opišite splošni postopek za odstranjevanje ukaza break. Na papirju definirajte funkcijo UNBREAK, ki sprejme program in vrne enakovredni program brez ukaza break. Funkcija je rekurzivna.

Izboljšava splošnega postopka

Izboljšajte UNBREAK tako, da ne bo po nepotrebnem spreminjal kode.