Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
(nettipäiväkirja 26.01.2018) Tajusin juuri, että on oikeastaan tosi sääli, ettei ole juuri ollenkaan esimerkkejä ohjelmista, jotka on kirjoitettu merkkijonojen uudelleenkirjoitusjärjestelmillä (Semi-Thue-järjestelmillä). No, tässä on yksi esimerkki, binäärilukujen yhteenlasku. Sen voi tietenkin kirjoittaa tosi monella muullakin tavalla. Syötteeksi annetaan esimerkiksi merkkijono "plus(11,11)" ja tuloksena on merkkijono "110".
Käytän uudelleenkirjoittamiseen Unixin sed-komentoa, jotta uudelleenkirjoitusjärjestelmä on helposti ajettavissa, mutta siinä ei käytetä mitään säännöllisten lausekkeiden erikoismerkkejä vaan kaikki uudelleenkirjoitussäännöt ovat puhtaasti vakiomerkkijonosta vakiomerkkijonolle. Yritin vielä huvin vuoksi tehdä ohjelmasta mahdollisimman epädeterministisen eli laskenta voi edetä vaikka millaisten välitilojen kautta mutta tuottaa aina saman tuloksen.
#!/bin/sed -f : start s/plus(0/plus(/p s/,0/,/p s/0,/,(0)/p s/1,/,(1)/p s/(0)00/0(0)0/p s/(0)01/0(0)1/p s/(0)10/1(0)0/p s/(0)11/1(0)1/p s/(1)00/0(1)0/p s/(1)01/0(1)1/p s/(1)10/1(1)0/p s/(1)11/1(1)1/p s/(0))/)0/p s/(1))/)1/p s/plus(,0/0plus(,/p s/plus(,1/1plus(,/p s/plus(,)//p s/(0)0)/)0/p s/(0)1)/)1/p s/(1)0)/)1/p s/(1)1)/)C/p s/0C/10/p s/1C/C0/p t start
Esimerkki laskennasta:
plus(plus(100,0010001),11) plus(plus(100,010001),11) plus(plus(10,(0)010001),11) plus(plus(10,0(0)10001),11) plus(plus(10,01(0)0001),11) plus(plus(10,1(0)0001),11) plus(plus(1,(0)1(0)0001),11) plus(plus(,(1)(0)1(0)0001),11) plus(plus(,(1)(0)10(0)001),11) plus(plus(,(1)1(0)0(0)001),11) plus(plus(,(1)1(0)00(0)01),11) plus(plus(,(1)1(0)000(0)1),11) plus(plus(,(1)1(0)000)1,11) plus(plus(,(1)1(0)000),(1)11) plus(plus(,(1)10(0)00),(1)11) plus(plus(,1(1)0(0)00),(1)11) plus(plus(,1(1)0(0)00),1(1)1) plus(1plus(,(1)0(0)00),1(1)1) plus(1plus(,(1)0(0)00),1)C plus(1plus(,(1)00(0)0),1)C plus(1plus(,0(1)0(0)0),1)C plus(10plus(,(1)0(0)0),1)C plus(10plus(,(1)0)0,1)C plus(10plus(,)10,1)C plus(10plus(,)1,(0)1)C plus(10plus(,),(1)(0)1)C plus(10,(1)(0)1)C plus(10,(1))1C plus(10,(1))C0 plus(1,(0)(1))C0 plus(,(1)(0)(1))C0 plus(,(1)(0))1C0 plus(,(1)(0))C00 plus(,(1))0C00 plus(,)10C00 10C00 11000
Kuten huomaatte, suurin osa ajasta (ja ohjelmastakin) menee siihen, että bitit saadaan oikeaan järjestykseen, eli yhtä merkitsevät vierekkäin. Varsinainen yhteenlasku on helppoa, ja on toteutettu ohjelman kahdella viimeisellä säännöllä (ja tavallaan myös niitä edeltävillä neljällä, jotka yhdistelevät kahdesta eri numerosta tulevat bitit).