# [Zap 2010-01-29] - Subtyping

<{ForumPost(poster="kukmuk", timestamp=2010-01-29 13:58:24)}>
**Ukol**  
Najdete spolecneho predka zinstanciovanych typu.  
  
**Zadani**  
Na zacatku obdrzi vas program jako argument soubor s definicemi typu. Takova definice vypada napriklad takto:  
T1 x y => T0 x y y  
Kde T1 a T0 jsou nazvy typu, x a y jsou formalni nazvy parametru. Predchozi zapis rika, ze definujeme  typ T1 (odvozeny z T0) s parametry x a y. Parametr x se mapuje na prvni parametr typu T0. Parametr y se mapuje na druhy i treti parametr typu T0.  
Zakladnim typem (nema zadny parametr) je typ S. Kazdy jiny typ je jeho vzdalenym potomkem.  
Je pouze jednoducha dedicnost.  
Soubor s definicemi muze vypadat napriklad takto.

    T1 a => S
    T2 x y => T1 y
    T3 a b c => T1 b
    T4 u v w => T2 w u
    T5 x => T2 x x
    

Predchozi definice typu je korektni, nebot

*  Typy maji tvar \[A-Z]\[a-zA-Z0-9_]
*  Parametry maj tvar \[a-z]\[a-zA-Z0-9_]
*  Kazdy typ je odvozen z jiz definovaneho typu (typ S je pred definovany)
*  Odvozeny typ namapoval sve formalni parametry na vsechny formalni parametry predka.

Pozorovani: Neni mozne vytvorit typ, ktery nema parametry, jako potomka typu s parametry. Nemelo by se co mapovat na predkovy parametry.  
  
Stromovy zapis predchoziho soubor definic je:

           S
           |
          T1
        /    \
       T2     T3
      /  \
    T4   T5
    

  
Pote program bude cist standradni vstup. Na nej budou chodit dvojice typu (kazda na jednom radku) s dosazenymi parametry. Po te nasleduje prazdna radka a pak dalsi dotaz nebo EOF.  
Korekti uzivatelsky vstup muze vypadat asledovne:

    T1 z
    T5 q
    
    T5 f
    T4 f m f
    
    

Na to by mel program odpovedet

    S
    T2 f f
    

Tedy pote co je typum predan seznam skutecnych parametru, tyto parametry probublaji jejich predky. Tak dostaneme zinstanciovany typ.  
Napriklad T5 f ma svoji vyvozovaci vetev:  
S -> T1 f -> T2 f f -> T5 f  
Pro T4 f m f  
S -> T1 f -> T2 f f -> T4 f m f  
  
Takze jejich spolecny predchudce je T2 f m f (musi se shodovat jak nazev typu tak skutecne (dosazene) parametry).  
  
  
  
Cas byl 3:20, protoze pak byla pisemka odpoledni skupiny.  
Me se to povedlo, prede mnou jeste 2 lidem. Pak uz ale byl brzo konec, takze myslim, ze o mnoho vic nas nebylo  :? .  
  
Hodne stesti!!!
<{/ForumPost}>

<{ForumPost(poster="blabla", timestamp=2010-01-29 14:10:30)}>
no, momentalne sedim v labe, zapoctovka mi mala zacat o 14 00 ale predchadzajuca skupina este stale pise:D zevraj do 14:30
<{/ForumPost}>

<{ForumPost(poster="vexis", timestamp=2010-01-30 11:29:33)}>
No o moc vic ne, ja sem treba ztratil hrozne moc casu na kontrole vstupu, tam musel clovek kontrolovat vsechno.
<{/ForumPost}>