hwechtla-tl: Suuntaamattomien verkkojen uudelleenkirjoituskieli

Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset

---

Tällaisia kieliä ei juurikaan käytetä, koska suuntaamattomista verkoista on "vain haittaa" verrattuna suunnattuihin. Yleensä, jos haluaa kuvata jotain verkkorakenteena, ei halua ottaa huomioon symmetrioita ja sitä, että jotenkin toisin päin käännettynä (toisesta näkökulmasta katsoen) verkkosi voikin tarkoittaa jotain muuta. Niinpä kaikki todella käytetyt verkkojen uudelleenkirjoituskielet ovat suunnattujen verkkojen uudelleenkirjoituskieliä. Suunnattujen verkkojen uudelleenkirjoituskieliin kuuluvat myös puiden uudelleenkirjoituskielet, jotka ovat funktionaalisia ohjelmointikieliä. (Puu on käytännössä sellainen asyklisen suunnatun verkon osa, johon kuuluvat kaikki solmut, joihin pääsee annetusta solmusta ulosmeneviä kaaria pitkin.)

Mutta, jos ei tarvitse miettiä käytännöllisyyttä, suuntaamattomien verkkojen uudelleenkirjoituskielet ovat hauskoja. Sitä paitsi suunnatun verkon voi koodata suuntaamattomaksi korvaamalla jokaisen kaaren jonkinlaisella asymmetrisella solmuyhdistelmällä, esimerkiksi

a -> b -> c -> d

a - o - o - b - o - o - c - o - o - d
     \           \           \
      o           o           o

Niinpä on olemassa mm. esoteerinen ohjelmointikieli Eodermdrome (nimi tarkoittaa tavallaan pentagrammia verkkona, http://www.esolangs.org/wiki/Eodermdrome), joka on värittämättömien suuntaamattomien verkkojen uudelleenkirjoituskieli. Uudelleenkirjoitussäännöt ovat siinä siis puhtaasti rakennemuutoksia verkossa, jossa ainoa "merkitys" on sen rakenne.

Mitä tämä tarkoittaa käytännössä? Se tarkoittaa esimerkiksi, että jos meillä on verkko

o - o - o - o
   / \ /   /
  o - o - o - o
 /       / \
o - o   o   o

+-------+    +---------+
|a - b  |    |i - a - j|  (b tuhoutuu)
|   / \ | => |   / \   |
|  c - d|    |  c - d  |  (i ja j syntyvät)
+-------+    +---------+

      o   o
       \ /                o - o - o - o
o - o - o                    / \ /   /
   / \ / \         TAI  o - o - o - o - o
  o - o - o - o            / \     / \
 /       / \              o   o   o   o
o - o   o   o

Tällaisessa kielessä on hyvin vaikeaa määrittää uudelleenkirjoitussääntöjä, jotka eivät uudelleenkirjoittaisi myös jotain, mitä käyttäjä ei halua. Lisäksi Eodermdromen syntaksi uudelleenkirjoituksille on vaikeaselkoinen, ei äärimmäisen kryptinen vaan hyvin tiivis. Yllä esitetty uudelleenkirjoitussääntö määritellään Eodermdromessa esim. ilmauksella "taika stikty" tai käyttääksemme kaavion kirjaimia, ilmauksella "abcdb iacdaj".

Olisi kuviteltavissa kaksi kieltä, joissa ei ole niin vaikeaa työskennellä: väritettyjen (labeled) suuntaamattomien graafien uudelleenkirjoituskieli, ja värittämättömien suunnattujen graafien uudelleenkirjoituskieli. Suunnittelin aikoinani ensinmainittua (työnimi oli grrr (graph reduction renderer)). Se muistuttaa aika paljon jo funktionaalista ohjelmointia, mutta on huomattavasti epämääräisempää.

Esimerkiksi, jos lukuja kuvataan sinisillä solmujonoilla, joiden päässä on punainen solmu

3               7               0

|               |               |
S - S - S - P   S - S - S - S   P
                            |
                P - S - S - S

+-----+    +-----+    +-----+    +-----+
|  +  |    |  +  |    |  x  |    |  x  |
| / \ |    | / \ |    |  |  |    |  |  |
|a   S| => |S   b|    |  +  | => |  a  |
|   / |    | \   |    | / \ |    |     |
|  b  |    |  a  |    |a   P|    |     |
+-----+    +-----+    +-----+    +-----+

Mutta juurikin, koska verkko on suuntaamaton, tarvitaan kaikenlaisia ylimääräisiä solmuja merkitsemään, mikä +-solmun ulosmenevistä kaarista tarkoittaa mitäkin... muuten uudelleenkirjoitussäännöt voivat esim. alkaa siirtää sinisiä solmuja yhteenlaskuun sieltä, mihin tulos pitäisi palauttaa tai muuta sellaista. Esim. tähän tapaan:

+-----+    +-----+    +-----+    +-----+
|  +  |    |  +  |    |  x  |    |  x  |
| / \ |    | / \ |    |  |  |    |  |  |
|1   2|    |1   2|    |  0  |    |  a  |
||   ||    ||   ||    |  |  |    |     |
|a   S| => |S   b|    |  +  | => |     |
|   / |    | \   |    | / \ |    |     |
|  b  |    |  a  |    |1   2|    |     |
+-----+    +-----+    ||   ||    +-----+
                      |a   P|
                      +-----+

Tällöin pystyy jo määrittelemään laskutoimituksen 1 + 2 + 3 verkkona

tulos - 0 - + - 1 - 0 - + - 1 - S - P
           /           /
          2 - S - S   2 - S - S - P
                 /
            P - S

tulos - S - S - S - S - S - S - P

Suuntaamattomien verkkojen uudelleenkirjoituskielten toteuttaminen on myös nihkeää samoista syistä, eli siksi, että uudelleenkirjoitussääntö voi täsmätä mihin tahansa verkon osaan "miten päin tahansa". grrr:n julkaiseminen kilpistyi siihen, ettei sille tehty toteutusta, eikä eodermdromeakaan ole toteutettu. Tässä on yksi olennainen osa uudelleenkirjoituksen toteuttamisesta, verkkokuvion sovittaminen: http://www710.univ-lyon1.fr/~csolnon/LAD.html

kategoria: ohjelmointi