1. Simple Python¶

1.1. Syntaxe¶

Nejprve zadefinujeme syntaxi našeho výpočetního modelu. Narozdíl od while-programů jsou v Pythonu důležité bílé znaky, neboť bloky v Pythonu jsou určené odsazením). Gramatika pro funkce v Simple Pythonu vypadá následovně:

• výpočetní funkce:

  def <jmeno>(<parametry>):
      <sekvence>
      return <promenna>
  

• <parametry> jsou buď prázdný řetězec, nebo posloupnost jmen <proměnných> oddělených čárkami

• <sekvence> je buď <příkaz>, nebo <sekvence> následovaná <příkazem> na novém řádku (se stejným odsazením)

• <příkaz> je buď <přiřazení> nebo <cyklus>

• <přiřazení> je jednoho z následujících tří tvarů: <proměnná> = 0, <proměnná> = <proměnná> + 1, <proměnná> = <proměnná> - 1

• <cyklus> je tvaru:

  while <test>:
      <sekvence>
  

• test je tvaru <promenna> != <promenna> nebo <promenna> > 0 (Druhý typ testu budeme potřebovat, abychom se jednoduše vyrovnali s faktem, že Python používá celočíselné odčítání, tj. výsledkem operace odčítání může být záporné číslo. Bez druhého typu testu bychom se sice zvládli vždy obejít, protože přirozené odčítání jedničky lze definovat pomocí zbylých dvou přiřazovacích příkazů (viz příklad 5 ve sbírce úloh), ale mnoho následujících úloh by se tím nepříjemně zkomplikovalo.)

Ukázka dobře utvořené funkce v Simple Pythonu:

def demo(x):
    a = 0
    b = 0
    while x != a:
        x = x - 1
        b = b + 1
        b = b + 1
    return b

1.2. Sémantika¶

Nyní definujeme sémantiku výpočetních funkcí (tj. “co počítají”). Podobně jako jazyk while-programů je Simple Python imperativní výpočetní model, základem je tedy množina proměnných \(Var\) a stav \(\sigma\), tj. funkce, která proměnným přiřazuje hodnoty (\(\sigma : Var \rightarrow \mathbb{N}\)). (Pro jednoduchost budeme sice zpočátku uvažovat jako přípustné vstupy pouze přirozená čísla, musíme však vzít v úvahu, že odčítání v Pythonu není přirozené, ale celočíselné, takže 0 - 1 = -1).

Než budete pokračovat dále, zkuste si nejprve sami rozmyslet, jak přesně definovat, co výpočetní funkce počítá (tj. to, co jsme u while-programů označovali jako sémantická funkce programu).

Lze postupovat například následovně. Nejprve zadefinujeme interpretaci jednotlivých příkazů jako funkce z množiny stavů do množiny stavů. Interpretace cyklu a přiřazovacího příkazu je téměř stejná jako u while-programů (viz učebnice, strana 13), akorát používáme celočíselné odčítání. Interpretaci sekvence získáme složením interpretací jednotlivých příkazů. Nyní můžeme definovat sémantickou funkci výpočetní funkce f, která má n pozičních parametrů označených \(p_1, \dots, p_n\) a tělo funkce tvoří sekvence S a návratový příkaz return x:

\(\varphi_f(a_1, \ldots, a_n) = [S](\sigma)(x)\) (aplikace těla funkce), pokud je \([S](\sigma)\) definováno a kde \(\sigma\) je takový stav, že \(\sigma(p_i) = a_i\) a hodnoty ostatních proměnných jsou nedefinované.

Chápete rozdíl mezi sémantickou funkcí a výpočetní funkcí? Je to dost zásadní.

Napište sémantickou funkci pro následující výpočetní funkci.

A teď naopak napište nějakou výpočetní funkci pro sémantickou funkci \(f(x, y) = x + y + 1\).

Zajímavým cvičením je dokázat, že While programy a Simple Python jsou stejně silné formalismy. (Je potřeba ukázat, že pro každý while-program existuje funkce v Pythonu se stejnou sémantikou, a naopak.)

1.3. Makropříkazy¶

Aby pro nás bylo snažší psát výpočetní funkce, můžeme zavádět (přidávat k jazyku) makropříkazy (syntaktické zkratky). Makropříkazy se skládají z označní, např. z = x a z definice, např.:

z = x + 1
z = z - 1

Ukažme si ještě makro pro přičtení hodnoty proměnné z = z + y, příp. z += y. Pro přirozené proměnné by makro mohlo vypadat následovně:

V následujících ukolech si postupně zadefinujeme běžné makropříkazy. V každé úloze můžete využívat makropříkazy definované v úlohách předchozích a můžete si také definovat další pomocná makra.

• prázdný příkaz, tedy příkaz který nevykoná nic (v kompletním Pythonu pass)
• součet (z = x + y)
• odčítání (z = x - y)
• součin (z = x * y)
• celočíselné dělení (z = x // y)
• podmíněný příkaz (if <test>: <sekvence>)

Dále napište makropříkazy pro základní typy testů. Výsledek testu by měl být 0 (nepravda) nebo 1 (pravda).

• menší než (if/while a < b: <sekvence>)
• disjunkce (if/while A or B: <sekvence>)
• konjunkce (if/while A and B: <sekvence>)
• negace (if/while not A: <sekvence>)
• rovnost (if/while a == b: <sekvence>)
• neostrá nerovnost (if/while a <= b: <sekvence>)

Využijte některý z testů pro makropříkaz cyklu s daným počtem opakování (for i in range(<n>): <sekvence>).

Na závěr si zkuste napsat pár výpočetních funkcí nad přirozenými čísly v jazyce Simple Python. Můžete využívat makra definovaná v předchozí části a případně si zadefinovat další.

• ciferný součet
• celočíselný dvojkový logaritmus (\(z = \lfloor \log_2(x) \rfloor\))