CLU példaprogramok

A CLU igen hatékony eszköze, hogy típuskonstrukciókat lehet készíteni. Ez a példa egy rekurzióra épített fa típust valósít meg. A rekurzió abban nyilvánul meg, hogy a típus egyszerre reprezentál egy csomópontot és az alatta található részfát, egy teljes fa és a részfái között nincs semmi különbség csak az, hogy a gyökérnek nincs szülője. A megvalósítás rekurzív típusdefiníciót és rekurzív eljáráshívásokat használ.

Az ilyen típusú (mutable) változók a fák egy-egy csomópontjára mutatnak, több változó is mutathat egy csomópontra, vagy egy fának más-más csomópontjaira. Bármennyi fát készíthetünk a new eljárással és ezek a fák összekapcsolhatók, vagy szétvághatók. Ha egy fáról "levesszük" az összes hivatkozást, akkor nincs mód arra, hogy újra hivatkozzunk rá. Ekkor az adott fa elveszett a program számára (a CLU-ban nincs destruktor, ez a módja, hogy eldobjunk egy objektumot - ezután a szemétgyűjtő fogja kitörölni). Ebben a típusban nincs üres fa (null pointer), azt a fát nevezzük üresnek, amelyik csak egy csomópontból áll. (A CLU egyáltalán nem ismeri az üres hivatkozás (null pointer) fogalmát, mivel pointer típusa sincs. Minden változó egy létező objektumra mutat, kivéve, ha még nem kapott értéket, de ekkor a ráhivatkozás mindig futási hibát okoz.)

A típusban a gyerekek között nincs semmilyen kapcsolat (pl. sorrend), az egyetlen reláció a szülő-gyerek reláció, az összes funkció ennek a relációnak a kiterjesztése. (Ennek következménye, hogy pl. nincs "i. gyerek" eljárás, csak "gyerekek" eljárás - ez egy iteráció). A típus a szülő-gyerek reláció absztrakciója. (Tulajdonképpen ez nem is fa, hanem fenyő, azaz irányított fa.) Viszonylag könnyen módosítható lehetne ez a típus, hogy irányított, körmentes gráfot valósítson meg, csak azt kell megengedni, hogy egy csomópontnak több szülője is lehessen. Ez a típus a parciális rendezési reláció absztrakciója lenne.

A megvalósított típus mutable. (Ez abból adódik, hogy a reprezentáció típusa is mutable.) A beépített összetett típusoknak van mutable és immutable változata is, de én személy szerint nem látom értelmét, hogy ennek a típusnak is legyen immutable változata. Ugyanis kihasználjuk azt, hogy ugyanarra a fa objektumra egyszerre több hivatkozás is történhet. Ha ez immutable típus lenne, akkor minden részfára való hivatkozás az adott részfából készített másolatot eredményezne. Ráadásul, a szerkezetéből adódóan, minden részfa tárolná a szülőjének a részfáját is, meg a szülője szülőjének a részfáját, stb. egészen a gyökérig. A szülő és a gyerek részfája is független lenne egymástól, azaz az első konstruktor művelet után már nem is felelnének meg egymásnak. A heterogén (félig mutable, félig immutable típus) sem megoldás - ez valójában immutable csomópontokat jelentene, melyeket "dinamikusan" kötünk egymáshoz -, mivel egy csomópont értékadás után a csomópont megduplázódik, így  a szülőjének megduplázódik az adott gyereke, a gyerekeknek pedig két szülője lenne, ami valójában az invariáns megsérülését jelentené. Valószínű, hogy egy immutable fa típust inkább úgy kellene megvalósítani, hogy a "fa" és "csomópont" fogalmakat ketté kellene választani - két típusra. Ez viszont nem a fenti mutable fa típus immutable változata lenne.

A megvalósítás tartalmaz egy szintaktikus cukor túlterhelést (overloading). Azzal, hogy az érték beírására és kiolvasására egy csomópontból a set_value és get_value neveket adtuk, a szintaktikus cukrok természete miatt használhatjuk a tree.value := elem és elem := tree.value formákat. Ezek eredetileg a record típushoz tartozó szintaktikus cukrok voltak. (Ezt lehetett volna fokozni (pl. tree.parent, tree.size, tree.move_to := ptree (!), stb.), de beértük ennyivel. Az új cukor egyébként is lehetővé teszi a tree!parent, tree!size, tree!move_to(ptree) hivatozásokat.)

A generáló típusnak (a fa csomópontjaiban található értékek) az egyetlen megszorítása, hogy legyen equal eljárása (függvénye). Ez akkor jelenthet gondot, ha itt saját típuskonstrukciót akarunk használni. Általában minden típushoz "illik" elkészíteni az equal, similar, copy standard eljárásokat, melyekkel minden beépített típus rendelkezik. Ezt az equal eljárást használja a similar és a search eljárás annak eldöntésére, hogy két érték egyenlő-e. Mutable típusoknál ez azt jelenti, hogy a két érték azonos objektum, immutable típusoknál azt jelenti, hogy a két érték egyenlő. (Persze az equal megvalósításakor más szemantikát is kaphat, de célszerű megtartani az eredeti jelentését.)

A copy eljárás csak a fa-struktúrát duplikálja, az abban levő értékeket mutable esetén nem, immutable esetén igen. Ebből adódik, hogy ha a generáló típus mutable, akkor a másolat példány csomópontjaiban az értékek egyszerre változnak a másolt példány értékeivel, míg a fa-struktúrájuk független egymástól. Ha mutable generáló típussal teljes másolatot akarunk készíteni egy fáról, akkor a másolat példányon végigfutó iterációban minden egyes értékről másolatot kell készítenünk a generáló típus copy eljárásával (ha van) - de ez könnyen megoldható az iteráció miatt. (A sok "ha" miatt nem volt érdemes beépíteni egy ezt elvégző copy2 eljárást - ugyanis a generáló típust meg kellett volna szorítani egy copy eljárással is. Eddig még csak-csak rendben volna, de mi van akkor, ha a generáló típusnak is van egy ugyanilyen copy2 eljárása, akkor kellene egy copy3 ... - határ a csillagos ég.) A copy2 eljárásra a végén van egy példa.

A típus tartalmaz egy invariant nevű, invariáns ellenőrző eljárást (nincs visszaadott érték). A CLU-ban nincsenek típushelyességet támogató eszközök, ez az eljárás ennek a hiányosságnak a pótlásához próbál módszert adni. Tetszőleges helyen elhelyezve egy ilyen eljáráshívást - egy fa típusú paramétere van -, az adott fán invariáns ellenőrzést végez, és normális esetben a program ezután tovább fut (célszerű ezt egy konstruktor hívás után elhelyezni). Ha hibát talál, akkor egy paraméteres kivételt vált ki, ha ez nincs lekezelve, akkor a program futása megszakad. Ez az ellenőrzési modell a "hívó által vezérelt" ellenőrzést valósít meg, teszteléskor is így használatos (ellentétben pl. a fordítási direktívákkal). A modell hasznosnak látszik párhuzamos fejlesztéseknél, ha gyanú esetén nem a program íróját kell megkeresnünk, hanem az előre elkészített invariáns ellenőrzést használhatjuk - vita esetén egyfajta bizonyíték is lehet, persze az invariáns ellenőrző is lehet hibás. (Már maga az invariáns ellenőrző elkészítése is jelezheti a típuskészítő szándékának komolyságát, ill. a megvalósított típus értékét.) Az invariant normális lefutása nem garantálja azt, hogy az előtte elvégzett konstruktor helyesen futott le, csak azt, hogy nem rontotta el az invariánst. (Ebben a típusban az előfeltétel ellenőrzést elvégzik a kivételkezelő részek.)

Egy rekurzív fa:  (CLU forrás. tree.clu)

% Egy rekurziv fa tipus

tree_type =  cluster [elem_type : type] is

  %%%%% Konstruktorok

  new,              % Letrehoz egy ures fat, gyoker van es van erteke
  new_child,        % Letrehoz egy gyereket, ertek van benne
  insert_to,        % Beilleszt egy reszfat egy csomopont ala
                    % (csak gyoker lehet, es nem illeszthet a sajat fajaba)
  extract,          % Kiemel egy reszfat a szuloje alol (csak gyerek lehet)
  move_to,          % Atvisz egy reszfat egy csomopont ala
                    % (nem illeszthet a sajat fajaba)
  set_value,        % A csomopont ertekenek felulirasa (tree.value := elem)

  %%%%% Fuggvenyek/iteraciok

  get_value,        % A csomopont erteke (elem := tree.value)
  is_root,          % Igaz, ha a csomopont gyoker
  root,             % A csomopont gyokere/faja
  is_parent_of,     % Igaz, ha a csomopont szuloje a masiknak
  parent,           % A csomopont szuloje/annak reszfaja (csak gyerek lehet)
  level,            % A csomopont szintje a fajaban/oseinek szama
  is_ancestor_of,   % Igaz, ha a csomopont ose a masiknak
  ancestors,        % A csomopont osei - iteracio
  is_empty,         % Igaz, ha a reszfa ures/csak gyoker/nincsenek gyerekei
  child_no,         % Csomopont gyerekeinek szama
  is_child_of,      % Igaz, ha a csomopont gyereke a masiknak
  children,         % Csomopont gyerekei/reszfai - iteracio
  size,             % Reszfa merete/csomopontok szama
  is_descendant_of, % Igaz, ha a csomopont utodja a masiknak      
  in_order,         % Reszfa csomopontjai in order bejarasban - iteracio
  pre_order,        % Reszfa csomopontjai pre order bejarasban - iteracio
  search,           % Egy ertek megkeresese a faban
  search_all,       % Egy ertek minden elofordulasanak megkeresese a faban
  search_by,        % Csomopontok, melyek teljesitik a feltetelt - iteracio

  %%%%% Standard muveletek

  equal, similar, copy,

  %%%%% Invarians teszteleshez

  invariant

  % A generalo tipusnak rendelkeznie kell egy equal (=) muvelettel
  % Erre csak a search es similar fuggvenyeknek van szuksege

  where elem_type has equal : proctype (elem_type, elem_type) returns (bool)

  %%%%% Reprezentacio

  rep = record[value : elem_type, parent, children : array[this]]
  this = tree_type[elem_type]

  %%%%% Konstruktorok

  % Letrehoz egy v gyokeru ures fat

  new = proc (v : elem_type) returns (this)

    return (up(rep${value : v,
                    parent : array[this]$new(),
                    children : array[this]$new()}))

  end new

  % Letrehoz egy v gyereket egy csomopont ala,
  % ezutan nem lesz ures, de a gyerek ures lesz

  new_child = proc (tree : this, v : elem_type) returns (this)

    tc : this := this$new(v)
    tc!insert_to(tree)
    return (tc)

  end new_child

  % A csomopont beillesztese a masik csomopont ala, ezzel gyerek lesz

  insert_to = proc (tree, ptree : this) signals (no_root, own_tree)

    if ~tree!is_root then signal no_root end
    if tree!is_ancestor_of(ptree) then signal own_tree end

    down(ptree).children!addh(tree)
    down(tree).parent!addh(ptree)

  end insert_to

  % A csomopont kivetele a szuloje alol, ezzel gyoker lesz

  extract = proc (tree : this) signals (is_root, bad_struct)

    if tree!is_root then signal is_root end

    ptree : this := tree!parent
    i : int := 1
    while i <= ptree!child_no cand ~down(ptree).children[i] = tree do
      i := i + 1
    end %while

    if i > ptree!child_no then signal bad_struct end

    while i < ptree!child_no do
      down(ptree).children[i] := down(ptree).children[i + 1]
      i := i + 1
    end %while
    ptree := down(ptree).children!remh
    ptree := down(tree).parent!remh

  end extract

  % A csomopont kivetele a szuloje alol, ha van,
  % es beillesztese a masik csomopont ala, ezzel gyerek lesz

  move_to = proc (tree, ptree : this) signals (own_tree)

    if tree!is_ancestor_of(ptree) then signal own_tree end

    if ~tree!is_root then
      tree!extract
    end %if
    tree!insert_to(ptree)

  end move_to

  % A csomopont ertekenek felulirasa

  set_value = proc (tree : this, e : elem_type)

    down(tree).value := e

  end set_value

  %%%%% Fuggvenyek/iteraciok

  % A csomopont erteke

  get_value = proc (tree : this) returns (elem_type)

    return (down(tree).value)

  end get_value

  % Ez a csomopont a gyoker?

  is_root = proc (tree : this) returns ( bool )

    return (down(tree).parent!empty)

  end is_root

  % A csomopont gyokere

  root = proc (tree : this) returns (this)

    t : this := tree
    while ~t!is_root do
      t := t!parent
    end %while
    return (t)

  end root

  % Ez a csomopont a szuloje a masiknak?

  is_parent_of = proc (tree, ctree : this) returns ( bool )

    return (~ctree!is_root cand tree = ctree!parent)

  end is_parent_of

  % A csomopont szuloje

  parent = proc (tree : this) returns (this) signals (is_root)

    if tree!is_root then signal is_root end

    return (down(tree).parent!top)

  end parent

  % A csomopont szintje a fajaban

  level = proc (tree : this) returns (int)

    l : int := 0
    for t : this in tree!ancestors do
      l := l + 1
    end %for
    return (l)

  end level

  % Ez a csomopont az ose a masiknak?

  is_ancestor_of = proc (tree, ctree : this) returns ( bool )

    for t : this in ctree!ancestors do
      if tree = t then
        return (true)
      end %if
    end %for
    return (false)

  end is_ancestor_of

  % A csomopont osei

  ancestors = iter (tree : this) yields (this)

    t : this := tree
    while ~t!is_root do
      t := t!parent
      yield (t)
    end %while

  end ancestors

  % A csomopontnak nincs gyereke?

  is_empty = proc (tree : this) returns (bool)

    return (down(tree).children!empty)

  end is_empty

  % A csomopont gyerekeinek szama

  child_no = proc (tree : this) returns (int)

    return (down(tree).children!size)

  end child_no

  % Ez a csomopont a gyereke a masiknak?

  is_child_of = proc (tree, ptree : this) returns ( bool )

    return (ptree!is_parent_of(tree))

  end is_child_of

  % A csomopont gyerekei

  children = iter (tree : this) yields (this)

    for t : this in down(tree).children!elements do
      yield (t)
    end %for

  end children

  % A csomopont reszfajanak merete

  size = proc (tree : this) returns (int)

    s : int := 1
    for t : this in tree!children do
      s := s + t!size
    end %for
    return (s)

  end size

  % Ez a csomopont az utodja a masiknak?

  is_descendant_of = proc (tree, ptree : this) returns ( bool )

    return (ptree!is_ancestor_of(tree))

  end is_descendant_of

  % A reszfa csomopontjai - in order

  in_order = iter (tree : this) yields (this)

    for t : this in tree!children do
      for tc : this in t!in_order do
        yield (tc)
      end %for
    end %for
    yield (tree)

  end in_order

  % A reszfa csomopontjai - pre order

  pre_order = iter (tree : this) yields (this)

    yield (tree)
    for t : this in tree!children do
      for tc : this in t!pre_order do
        yield (tc)
      end %for
    end %for

  end pre_order

  % Egy ertek megkeresese a faban

  search = proc (tree : this, v : elem_type) returns (this, bool)

    for t : this in tree!pre_order do
      if t.value = v then
        return (t, true)
      end %if
    end %for
    return (tree, false)

  end search

  % Egy ertek minden elofordulasanak megkeresese a faban

  search_all = iter (tree : this, v : elem_type) yields (this)

    for t : this in tree!pre_order do
      if t.value = v then
        yield (t)
      end %if
    end %for

  end search_all

  % Csomopontok, melyek teljesitik a feltetelt

  search_by = iter (tree : this, exp : proctype (this) returns (bool))
              yields (this)

    for t : this in tree!pre_order do
      if exp(t) then
        yield (t)
      end %if
    end %for

  end search_by

  %%%%% Standard muveletek

  % Igaz ha ugyanarra az objektumra mutatnak

  equal = proc (tree1, tree2 : this) returns (bool)

    return (down(tree1) = down(tree2))

  end equal

  % Igaz, ha szerkezetuk megegyezik es ugyanazokra az elemekre mutatnak

  similar = proc (tree1, tree2 : this) returns (bool)
    e1, e2 : int

    if tree1.value ~= tree2.value then return (false) end
    if tree1!child_no ~= tree2!child_no then return (false) end

    for t1 : this in tree1!children do
      e2 := 0
      for t2 : this in tree2!children do
        e2 := e2 + x(similar(t1, t2))
      end %for
      if e2 < 1 then
        return (false)
      end
      e1 := 0
      for t2 : this in tree1!children do
        e1 := e1 + x(similar(t1, t2))
      end %for
      if e1 ~= e2 then
        return (false)
      end
    end %for
    return (true)

  end similar

  % Keszit egy masolatot a szerkezetrol, az elemekrol nem

  copy = proc (tree : this) returns (this)

    t : this := this$new(tree.value)
    for tc : this in tree!children do
      tc!copy!insert_to(t)
    end %for
    return (t)

  end copy

  % Invarians ellenorzese a csomopontot tartalmazo fara
  % Nem tartalmaz megvalositott eljarasokat!

  invariant = proc (tree : this) signals (bad_struct(this, this, string))

    check_tree(check_ancestors(tree)) resignal bad_struct

  end invariant

  % Osok ellenorzese - a gyokeret adja vissza
  % Csak annyit ellenoriz, hogy a gyokerbol van-e hivatkozas ra,
  % s igy a teljes fa ellenorzese eljut majd hozza is

  check_ancestors = proc (tree : this)
                    signals (bad_struct(this, this, string))

    if down(tree).parent!empty then
      return (tree)
    end %if
    for t : this in down(down(tree).parent!top).children!elements do
      if down(t) = down(tree) then
        return (check_ancestors(down(tree).parent!top)) resignal bad_struct
      end %if
    end %for

    signal bad_struct(tree!parent, tree, "missing child in parent")

  end check_ancestors

  % Gyerekek ellenorzese
  % Reszletes ellenorzes

  check_tree = proc (tree : this) signals (bad_struct(this, this, string))
    tl : array[this]
    e : int

    tl := down(tree).parent
    if tl!low ~= 1 cor tl!high < 0 cor tl!high > 1 then
      signal bad_struct(tree, tree, "invalid parent list index")
    end %if 
    tl := down(tree).children
    if tl!low ~= 1 cor tl!high < 0 then
      signal bad_struct(tree, tree, "invalid children list index")
    end %if 
    for t1 : this in down(tree).children!elements do
      if down(t1).parent!empty cor
         down(down(t1).parent!top) ~= down(tree) then
        signal bad_struct(tree, t1, "invalid parent in child")
      end %if
      e := 0
      for t2 : this in down(tree).children!elements do
        e := e + x(down(t1) = down(t2))
      end %for
      if e ~= 1 then
        signal bad_struct(tree, t1, "multiplicated child in parent")
      end %if
      check_tree(t1) resignal bad_struct
    end %for

  end check_tree

  % Logikai ertek karakterisztikus fuggvenye
  % Csak belso hasznalatra

  x = proc (b : bool) returns (int)
    if b then
      return (1)
    else
      return (0)
    end %if
  end x

end tree_type

Az eljárások részletes magyarázatát nélkülözzük, az eljárások rövidek és "magukért beszélnek". A szintaktikai sajátosságok az előző két példában láthatók, talán csak annyit, hogy a down() konverziós függvény - csak fordítási időben érvényesül, a kódba nem épül be - lehetővé teszi, hogy az aktuális típusra (itt. This) úgy hivatkozzunk, mintha a reprezentáció típusa lenne (Rep) és használhassuk annak eljárásait. Hasonlóan az up() lehetővé teszi, hogy a Rep típusra úgy hivatkozzunk, mintha This típus lenne. (This a Tree_Type[Elem_Type] rövidített neve.)

A search eljárásnak (CLU-ban az eljárásokat és függvényeket egységesen eljárásnak nevezzük) két visszaadott értéke is van. Ezt az értékadás művelet segítségével fogadhatjuk (máshogy nem):

...
tree, ftree : tree[string]
found : bool
...
ftree, found := tree!search("valami")
if found then
  ...
end %if
...

ugyanezt meg lehet oldani found nélkül is a  típusmegvalósítás módosításával, csak a második visszaadott értéket kell törölni: (nincs tesztelve)

...
tree, ftree : tree[string]
found : bool
...
ftree := tree!search("valami")
if ftree.value = "valami" then
  ...
end %if
...

A search_by eljárásnak van egy eljárás típusú paramétere. A CLU sajátossága, hogy az eljárásokat pontosan úgy kezeli, mint a többi objektumot, van típusa, lehetnek változói, a változóknak van értékadás művelete, átadható paraméterként és lényegében egy művelete van, el lehet indítani - szükség szerint paraméterezve.

A copy2 eljárásra egy példa, ennek csak akkor van értelme, ha a generáló típus mutable (immutable esetén már az első copy-nál másolat keletkezik): (nincs tesztelve)

copy_tree = proc (tree : my_tree) return (my_tree)
  tree2 : my_tree := tree!copy
  for t : my_tree in tree2!pre_order do
    tree2.value := tree2.value!copy
  end %for
  return (tree2)
end copy_tree

Az invariant eljárást nem a típus programjaiba helyezzük, hanem a külső hivatkozások - elsősorban a konstruktor eljáráshívások - után. Az invariant használatára példa:

...
ptree := tree!parent
tree!extract
tree!invariant
ptree!invariant
...

illetve

t!invariant
  except when bad_struct(ptree, tree : my_tree, mess : string):
    output!putl(" T's structure is damaged!")
    output!putl("   Parent : " || ptree.value)
    output!putl("   Child  : " || tree.value)
    output!putl("   Message: " || mess)
    signal failure
  end

A csomagban van egy egyszerű program, mely ennek a típusnak az eljárásait teszteli le. (CLU forrás: treetest.clu) Ebben látható a típus használatának módja.

Fordítása:

>clu2c tree treetest
>clulink -o treetest tree.c treetest.c
>treetest