3 Ukazni programski jezik

V prejšnji lekciji smo spoznali aritmetične izraze s spremenljivkami. Spremenljivke smo obravnavali po mačehovsko, saj se jim ni dalo nastavljati vrednosti in ni bilo možno definirati novih spremenljivk.

V tej lekciji bomo spoznali ukazni programski jezik, ki ima prave spremenljivke, pogojne stavke in zanke. Po vrsti bomo obravnavali:

• sintaksa jezika

• operacijska semantika – kako se jezik izvaja

• ekvivalenca programov – kaj pomeni, da sta dva programa ekvivalentna?

• denotacijska semantika - kaj je matematični pomen programa?

• prevajalnik v strojno kodo

3.1Sintaksa¶

V prejšnji lekciji smo spoznali aritmetične izraze. Dodali bomo še boolove izraze in ukaze. Podajmo abstraktna sintaksa jezika:

⟨aritmetični-izraz⟩ ::=
  ⟨spremenljivka⟩ |
  ⟨številka⟩ |
  ⟨aritmetični-izraz⟩ + ⟨aritmetični-izraz⟩ |
  ⟨aritmetični-izraz⟩ * ⟨aritmetični-izraz⟩

⟨boolov-izraz⟩ ::=
   true | false |
   ⟨aritmetični-izraz⟩ = ⟨aritmetični-izraz⟩ |
   ⟨aritmetični-izraz⟩ < ⟨aritmetični-izraz⟩ |
   ⟨boolov-izraz⟩ and ⟨boolov-izraz⟩ |
   ⟨boolov-izraz⟩ or ⟨boolov-izraz⟩ |
   not ⟨boolov-izraz⟩

⟨ukaz⟩ ::=
   skip |
   ⟨spremenljivka⟩ := ⟨aritmetični-izraz⟩ |
   ⟨ukaz⟩ ; ⟨ukaz⟩ |
   while ⟨boolov-izraz⟩ do ⟨ukaz⟩ done |
   if ⟨boolov-izraz⟩ then ⟨ukaz⟩ else ⟨ukaz⟩ end

Da bi iz zgornjih pravil dobili konkretno sintakso, moramo podati še informacijo o prioriteti in asociativnosti operatorjev. Naštejmo operatorje od nižje do višje prioritete:

• ; (levo)

• or (levo)

• and (levo)

• not

• <, =

• + (levo)

• * (levo)

Na primer, or je levo asociativen in ima prednost pred ;. To še vedno ni dovolj za povsem konkretno sintakso, na primer, dodati bi morali še pravila za pisanje oklepajev in pojasniti, kako se naredi leksikalno analizo (kakšna so pravila za presledke, nove vrste, komentarje ipd.)

Tu in v nadaljevanju se ne bomo preveč posvečali podrobnostim konkretne sintakse. To ne pomeni, da je konkretna sintaksa nepomembna v praksi; navsezadnje so se pripravljeni programerji skregati že zaradi zamikanja kode. V zvezi s tem omenimo Wadlerjev zakon. Priporočamo tudi, da si lahko ogleda implementacijo sintakse jezika comm v PL Zoo.

3.2Operacijska semantika¶

Sedaj nadgradimo operacijsko semantiko izrazov še s pravili za boolove izraze in ukaze. Še vedno imamo okolje η, ki spremenljivkam priredi njihove vrednosti, na primer

η = [x ↦ 4, y ↦ 10, u ↦ 1]

V našem jeziku bomo spremenljivke vedno hranile samo cela števila. Ker jim bomo tudi nastavljali vrednosti, potrebujemo ustrezno operacijo, s katero to naredimo. Če je η okolje, x spremenljivka in n celo število, potem zapis

η [x ↦ n]

pomeni okolje η, v katerem je vrednost x nastavljena na n.

3.2.1Operacijska semantika aritmetičnih in boolovih izrazov¶

Pravila za aritmetične izraze smo že spoznali zapišimo jih še enkrat:

—————————-
η | n ↪ n


 η(x) = n
————————––
η | x ↪ n

η | e₁ ↪ n₁     η | e₂ ↪ n₂
———————————————————————–———
 η | e₁ + e₂ ↪ n₁ + n₂


η | e₁ ↪ n₁     η | e₂ ↪ n₂
———————————————————————–———
 η | e₁ - e₂ ↪ n₁ - n₂


η | e₁ ↪ n₁     η | e₂ ↪ n₂
———————————————————————–———
 η | e₁ * e₂ ↪ n₁ · n₂

Tudi Boolovi izrazi ne predstavljajo večje težave:

————————————————
 η | true ↪ true


————————————————–
η | false ↪ false


   η | b ↪ false
 ————————-––-—————
 η | not b ↪ true


    η | b ↪ true
 —————————————————–
 η | not b ↪ false


     η | b₁ ↪ false
———————————-–—————————–
 η | b₁ and b₂ ↪ false


 η | b₁ ↪ true     η | b₂ ↪ v₂
––———————————————————————————–
     η | b₁ and b₂ ↪ v₂


   η | b₁ ↪ true
————————————————————–
 η | b₁ or b₂ ↪ true


η | b₁ ↪ false     η | b₂ ↪ v₂
—————————————————————————————–
     η | b₁ or b₂ ↪ v₂


η | e₁ ↪ n₁    η | e₂ ↪ n₂     n₁ < n₂
————————————————————–—————————————————
        η | e₁ < e₂ ↪ true


η | e₁ ↪ n₁   η | e₂ ↪ n₂    n₁ ≥ n₂
————————————————————–———————————————
      η | e₁ < e₂ ↪ false

Ko računamo boolove vrednosti, imamo pri računanju b₁ and b₂ izbiro:

1. Polno vrednotenje: (angl. complete evaluation): vedno izračunamo b₁ in b₂ in nato vrednost b₁ and b₂

2. Kratkostično vrednotenje (angl. short-circuit evaluation): najprej izračunamo samo b₁. Če dobimo false, je vrednost b₁ and b₂ enaka false ne glede na b₂, zato ga ne izračunamo. Če je vrednost b₁ enaka true, izračunamo še b₂.

Zgoraj smo uporabili kratkostično vrednotenje.

3.2.2Operacijska semantika ukazov¶

Semantika malih korakov za ukaze je podana z relacijo

(η, c) ↦ (η', c')

ki jo preberemo: »v okolju η ukaz c v enem koraku spremeni okolje v η' in se nadaljuje z ukazom c'«.

Relacija je določena z naslednjimi pravili:

       η | e ↪ n
————————————––—————————–––––––––
(η, (x := e))  ↦  (η[x↦n], skip)


       (η, c₁) ↦ (η', c₁')
—————————————––—————————–——————————
(η, (c₁ ; c₂))  ↦  (η', (c₁' ; c₂))


———————————————––—————————–——————————
   (η, (skip ; c₂))  ↦  (η, c₂)


             η | b ↪ true
———————————————————————–—————————————————
(η, (if b then c₁ else c₂ end)) ↦ (η, c₁)


             η | b ↪ false
———————————————————————–—————————————————
(η, (if b then c₁ else c₂ end)) ↦ (η, c₂)


      η | b ↪ false
———————————––—————————–—————————————
(η, (while b do c done)) ↦ (η, skip)


                      η | b ↪ true
—————————————––—————————–—————————–——————————————————————-
 (η, (while b do c done))  ↦ (η, (c ; while b do c done))

Pravila določajo, kako se ukaz c₁ v okolju η₁ izvaja kot zaporedje korakov

(η₁, c₁) ↦ (η₂, c₂) ↦ (η₃, c₃) ↦ ⋯

Zaporedje se lahko nadaljuje v nedogled ali pa se ustavi pri ukazu skip, saj je to edini ukaz, ki nima naslednjega koraka.

3.3Ekvivalenca programov¶

Pravimo, da sta dva ukaza ekvivalentna, če se v vseh pogledih obnašata enako. To pomeni, da lahko vedno enega zamenjamo z drugim. Kako bi to razložili natančneje?

Najprej definiramo evalvacijski kontekst, to je del programske kode z »luknjo«, v katero lahko vstavimo kodo, označimo ga z C[ ], kjer [ ] predstavlja luknjo. Če v C[ ] vstavimo kodo A, dobimo kodo C[A].

3.4Denotacijska semantika¶

Denotacijski semantiki se bomo posvetili na kratko, s preprostimi zgledi, saj bi natančna obravnava zahtevala več časa.

Osnovno vprašanje, na katerega odgovarja denotacijska semantika je: »Kaj je matematični pomen programa?« Na primer, pomen izraza 3 * (6 + 8) je celo število 42, matematični pomen Python funkcije

def fakt(n):
   if n == 0:
      return 1
   else:
      return n * fakt(n-1)

je matematična funkcija n ↦ n!, itn.

Ukaz c v našem programskem jeziku prav tako predstavlja funkcijo, ki sprejme okolje in vrne okolje. Na primer,

x := x + 1 ;
y := 10

predstavlja funkcijo, ki okolje [x ↦ a, y ↦ b] preslika v okolje [x ↦ a+1, y ↦ 10]. Ukaz

i := 1 ;
s := 0 ;
while i < n do
  s := s + i ;
  i := i + 1
done

predstavlja funkcijo, ki sprejme okolje [i ↦ a, s ↦ b, n ↦ c] takole:

• če je c ≤ 0, je vrednost funkcije [i ↦ 1, s ↦ 0, n ↦ c]

• če je c > 0, je vrednost funkcije [i ↦ c, s ↦ c·(c-1)/2, n ↦ c]

Funkcija, ki jo računa ukaz, je lahko delna, kar pomeni, da njena vrednost ni nujno definirana. Ukaz

while not (i = 100) do
  i := i + 1
done

predstavlja funkcijo, ki sprejme okolje [i ↦ a] in

• če je a > 100, je vrednost funkcije nedefinirana (ker se zanka nikoli ne konča)

• če je a ≤ 100, je vrednost funkcije okolje [i ↦ 100].

3.5Prevajalnik¶

Implementirajmo prevajalnik za ukazni programski jezik. Zlgedovali se bomo po prevajalniku za comm v Programming Languages Zoo, ki je razširitev ukaznega jezika, ki smo ga obravnavali do sedaj.

Jezik comm podpira:

• aritmetične in boolove izraze

• spremenljivke

  • deklaracija nove lokalne spremenljivke new x := e in c

  • nastavljanje vrednosti x := e

• pogojni stavek if b then c₁ else c₂ done

• zanka while b do c done

• ukaz skip

• sestavljeni ukaz c₁ ; c₂

• ukaz print e

Ukaz print e ni presenetljiv, saj le na zaslon izpiše vrednost izraza e.

Bolj zanimiv je ukaz new x := e in c, s katerim deklariramo spremenljivko x z začetno vrednostjo e, ki je veljavna v ukazu c. Na primer, ukaz

new i := 1 in
new s := 0 in
  while i < 100 do
    new j := i * s in
    i := i + 1 ;
    s := s + j
  done

bi v Javi zapisali kot blok

{
   int i = 1 ;
   int s = 0 ;
   while (i < 100) {
      int j = i * s ;
      i = i + 1 ;
      s = s + j
   }
}

3.5.1Strojni jezik¶

Ukaze bomo prevajali v strojni jezik za preprost procesor. Vsa aritmetična in logična obdelava podatkov poteka na skladu, trajnejše vrednosti so v RAM-u, potek izvajanja pa vodi števec ukazov.

Arhitektura stroja sestoji iz:

• Program: tabela ukazov, ki naj jih stroj izvaja (opisani so spodaj)

• Pomnilnik RAM: tabela celih števil (int), dostop po indeksih

• Števec ukazov (cp): indeks trenutno izvajajočega se ukaza v programu.

• Kazalec na sklad (sp): sklad je shranjen v RAM in raste navzdol. Vrh sklada je na naslovu, na katerega kaže sp.

• Logične vrednosti: 0 pomeni neresnica, vsak neničelni int pomeni resnica.

• Vhod/izhod: ukaz PRINT izpiše celo število z vrha sklada.

Ob inicializaciji: RAM je zapolnjen z ničlami, pc = 0, sp = ram_size - 1. Sklad je torej sprva prazen.

Stroj izvaja program v zanki: prebere navodilo na naslovu pc, ga izvede, nato se pc običajno poveča za 1. Izjema so skoki:

• relativni skoki (JMP k, JMPZ k) popravijo pc z relatvnim odmikom k, nato glavni cikel pc še poveča za 1. Efektivni cilj izvedenega skoka je zato pc + k + 1 glede na začetni pc ukaza skoka.

• JMPZ pred odločitvijo porabi (pop) vrh sklada in skoči le, če je ta vrednost 0.

Vsi aritmetični in logični ukazi delujejo na vrhu sklada. Binarne operacije vedno vzamejo najprej y = pop, nato x = pop, izračunajo rezultat x ∘ y in ga potisnejo nazaj (push). Unarne operacije vzamejo en pop in vrnejo en push.

Ukazni nabor stroja:

• NOOP — ne naredi ničesar (niti sklada niti pc ne spremeni).

• SET k — vzemi a = pop in zapiši a v RAM na naslov k.

• GET k — preberi RAM na naslovu k in prebrano potisni na sklad.

• PUSH c — potisni celoštevilsko konstanto c na sklad.

• ADD — x + y.

• SUB — x - y.

• MUL — x * y.

• DIV — x / y; če je y = 0, sproži napako division by zero.

• MOD — x mod y; če je y = 0, sproži napako division by zero.

• EQ — vrne 1, če x = y, sicer 0.

• LT — vrne 1, če x < y, sicer 0.

• AND — logična konjunkcija: 1 iff (x ≠ 0 in y ≠ 0), sicer 0.

• OR — logična disjunkcija: 1 iff (x ≠ 0 ali y ≠ 0), sicer 0.

• NOT — logična negacija vrha sklada: neničelen → 0, 0 → 1.

• JMP k — relativni skok z odmikom k (glej razdelek o skokih).

• JMPZ k — relativni pogojni skok: vzemi a = pop; če je a = 0, skoči z odmikom k.

• PRINT — a = pop; izpiši a na standardni izhod.

Stroj lahko med izvajanjem sproži izjemo:

• Illegal_address — poskus branja ali pisanja izven meja RAM-a.

• Zero_division — deljenje ali ostanek z ničelnim deliteljem (DIV, MOD).

• Illegal_instruction — rezervirano za neveljavna navodila (v dani različici je definirano, a se ne sproža).

Opomba: model je namerno minimalen — ni preverjanja prepolnitve/podpraznjenja sklada (push/pop lahko trčita izven dovoljenega območja RAM-a, kar se izrazi kot Illegal_address).

3.5.2Kako deluje prevajanje¶

Kako točno deluje prevajalnik, je razvidno iz implementacije v OCamlu. Tu je kratek besedni opis.

Prevajalnik pretvori izvorni program v zaporedje strojnih ukazov. Pri tem vodi kontekst spremenljivk (seznam trenutno veljavnih imen), ki vsako spremenljivko preslika v lokacijo v RAM-u po načelu de Bruijnovih nivojev: prva deklaracija je na lokaciji 0, naslednja na 1, itn. Tako lahko ukaz let novi spremenljivki dodeli naslednjo lokacijo, := pa preprosto naslovi že dodeljeno lokacijo.

Aritmetične in logične izraze prevajalnik prevede tako, da se izračunajo na skladu: najprej izračuna levi in desni podizraz (vsak potiska vrednosti na sklad), nato doda eno samo navodilo za operacijo. Boolovi vezniki so prevedeni s polnim vrednotenjem (niso kratkostični). Zaporedje ukazov prevede tako, da stakne skupaj prevode posameznih ukazov.

Pogojni stavek if se prevede v izračun pogoja, pogojni skok čez vejo then, veja then s skokom čez vejo else in nazadnje veja else. Zanka while se prevede v test na začetku zanke, pogojni skok če telo zanke, nato telo zanke in na koncu negativen relativni skok nazaj na test.

3.5.3Implementacija v OCamlu¶

Podrobneje si oglejmo implementacijo comm v OCAmlu:

• abstraktna sintaksa je definirana s podatkovnimi tipi v syntax.ml

• konkretna sintaksa je opisana v lexer.mll in parser.mly; uporabimo generator parserjev Menhir

• preprost simulator procesorja z RAM in skladom najdemo v machine.ml

• prevajalnik iz comm v strojni jezik je v compile.ml

• glavni program je v comm.ml

Prevajalnik neposredno pretvori program v strojno kodo, ker je comm zelo preprost jezik. Prevajanje pravih programskih jezikov poteka preko več stopenj, z vmesnimi jeziki. Vsak naslednji jezik je nekoliko bolj preprost in bližje strojni kodi.

3.5.4Primeri¶

Na primerih preizkusimo, kako se prevajajo programi in kako hitro delujejo.

comm:

# Print the sum of prime numbers up to n
new n := 1000000 in
print n ;
new s := 0 in
new k := 2 in
while k < n do
  new i := 2 in
  new isPrime := 1 in # 1 = true, 0 = false
  while isPrime = 1 and i * i < k + 1 do
    if k % i = 0 then isPrime := 0 else skip end ;
    i := i + 1
  done ;
  if isPrime = 1 then s := s + k else skip end ;
  k := k + 1
done ;
print s

Python:

# The sum of primes below n
n = 1000000
print(n)
s = 0
k = 2
while k < n:
  i = 2
  isPrime = True
  while isPrime and i * i < k + 1:
    if k % i == 0:
        isPrime = False
    else:
        pass
    i = i + 1
  if isPrime:
      s = s + k
  else:
      pass
  k = k + 1
print(s)

C:

#include <stdio.h>

int main() {
  /* The sum of primes below n */
  const long n = 1000000 ;
  printf("%ld\n", n);
  long s = 0 ;
  long k = 2 ;
  int i ;
  int isPrime ;
  while (k < n) {
    i = 2 ;
    isPrime = 1 ;
    while ((isPrime == 1) && (i * i < k + 1)) {
        if (k % i == 0) {
          isPrime = 0 ;
        } else { }
        i = i + 1 ;
    }
    if (isPrime == 1) {
      s = s + k;
    }
    else { }
    k = k + 1 ;
  }
  printf("%ld\n", s);
}

Rezultati zelo nestrokovno izvedene meritve, ki ji ne moremo zaupati: