Keskustelu: Yleinen keskustelu: Todistustehtävä C-kääntäjän toiminnasta

Kaverini suositteli, että ohjelmoinnissa funktioiden tulisi mahtua kokonaan kuvaruudulle. Onko seuraava asia helppo todistaa, vai pitääkö tuntea kääntäjien lähdekoodi?

Kaikki tietokoneohjelmat voidaan tehdä sellaisilla C-ohjelmilla, joissa funktion rivit ovat korkeintaan 90 merkkiä pitkiä ja funktiot enintään 34 riviä.

Toisaalta en tiedä, onko tuo neuvo aina hyvä, kun olen kuullut, että esimerkiksi koodiin upotetut SQL-lauseet voivat olla yli kuvaruudun mittaisia.

Todistukseen riittää näyttää, että minkä tahansa C-funktion voi muuttaa joukoksi funktioita, joissa on enintään 34 riviä ja jokaisen rivin pituus on enintään 90 merkkiä.

Jos funktiossa on liikaa rivejä, sen voi jakaa lyhyemmiksi funktioiksi, joita alkuperäinen funktio kutsuu. Tässä ei ole siis ongelmaa.

Jos funktion rivi on liian pitkä, sen voi taas jakaa usealle riville, koska C:ssä saa valita vapaasti, missä kohdissa on rivinvaihtoja. Jos funktion tai muuttujan nimi on liian pitkä, sen voi lyhentää.

Mistähän nuo lukumäärät 90 ja 34 tulevat? Ne kuulostavat melko mielivaltaisilta.

Antti Laaksonen kirjoitti:

Jos funktion rivi on liian pitkä, sen voi taas jakaa usealle riville, koska C:ssä saa valita vapaasti, missä kohdissa on rivinvaihtoja.

Tätäpä on muistanutkaan.

Antti Laaksonen kirjoitti:

Mistähän nuo lukumäärät 90 ja 34 tulevat? Ne kuulostavat melko mielivaltaisilta.

Läppärini tekstieditoriin ja näyttööni mahtuu 34x90 tekstialue, ainakin tehdasasetuksilla.

Jaska kirjoitti:

Kaverini suositteli, että ohjelmoinnissa funktioiden tulisi mahtua kokonaan kuvaruudulle. – – Läppärini tekstieditoriin ja näyttööni mahtuu 34x90 tekstialue, ainakin tehdasasetuksilla.

Yleisemmin tunnetussa muodossa (esim. Linux kernel coding style) ohje on viitannut vanhanaikaiseen 25 rivin ja 80 sarakkeen kokoiseen tekstitilaan. On kuitenkin ihan turha saivarrella siitä, montako merkkiä ruudulle mahtuu ja saako fonttia vaihtaa tai meneekö funktio jopa pari riviä ruudun yli, koska se ei ole neuvon pääasia.

Koodia on helpompi ymmärtää ja siitä myös tulee yleensä selvempää, kun yksi funktio tekee yhden järkevän asian. Käytännössä useimmat yli 20-riviset funktiot voi helposti jakaa pienempiin loogisiin osiin. Samalla kommenttien tarve vähenee: kun funktiossa tee_X on koodi ABC, kuka tahansa ymmärtää jo ilman kommentteja, että koodi ABC tekee asian X.

Jaska kirjoitti:

Toisaalta en tiedä, onko tuo neuvo aina hyvä, kun olen kuullut, että esimerkiksi koodiin upotetut SQL-lauseet voivat olla yli kuvaruudun mittaisia.

Esimerkiksi pitkät SQL-kyselyt eivät minusta kuulu välttämättä funktion rivimääräiseen sisältöön, ja muutenkin ne on usein selvempää tallentaa vaikka vakioina funktion alkuun tai sen ulkopuolelle.

Jaska kirjoitti:

[Väite:] Kaikki tietokoneohjelmat voidaan tehdä sellaisilla C-ohjelmilla, joissa funktion rivit ovat korkeintaan 90 merkkiä pitkiä ja funktiot enintään 34 riviä

Tavallaan väite pitää paikkansa, koska funktioiden ulkopuolelle voi kirjoittaa paljon dataa ja rajallisen mittaisilla funktioilla voi toteuttaa vaikka kääntäjän, joka tekee tuosta datasta uuden ohjelman.

Jos ei sallita tällaista huijausta vaan vaaditaan, että kaikki ohjelman toimintaan vaikuttava koodi ja data on funktioiden sisällä, väitteen voi taas helposti todeta teoriassa vääräksi. C-kieli sisältää rajallisesti eri rakenteita, joten erilaisia määrätyn mittaisia funktioita on rajallinen määrä. Erilaisia ohjelmia on kuitenkin loputtomasti: ohjelma voi tulostaa "a", "aa", "aaa" jne.

Toisaalta ääretön määrä ohjelmia tarkoittaa, että jokin niistä vie äärettömästi tallennustilaa, jolloin sitä ei voi käytännössä olla olemassa.

Metabolix kirjoitti:

C-kieli sisältää rajallisesti eri rakenteita, joten erilaisia määrätyn mittaisia funktioita on rajallinen määrä. Erilaisia ohjelmia on kuitenkin loputtomasti: ohjelma voi tulostaa "a", "aa", "aaa" jne.

Tämä ei haittaa, koska ohjelmassa saa olla monta funktiota. Millä tahansa n:llä voidaan tehdä C-ohjelma, joka tulostaa n a-kirjainta ja jokaisessa funktiossa on vain muutama rivi. Esimerkiksi 5 a-kirjaimen tulostus:

void tulosta1a() {
    printf("a");
}

void tulosta2a() {
    printf("a");
    tulosta1a();
}

void tulosta3a() {
    printf("a");
    tulosta2a();
}

void tulosta4a() {
    printf("a");
    tulosta3a();
}

void tulosta5a() {
    printf("a");
    tulosta4a();
}

Sen sijaan ongelmaksi tulee jossain vaiheessa, että funktion nimestä tulee liian pitkä.

Metabolix kirjoitti:

Toisaalta ääretön määrä ohjelmia tarkoittaa, että jokin niistä vie äärettömästi tallennustilaa, jolloin sitä ei voi käytännössä olla olemassa.

Mitä tarkoitat? Yllä olevalla tavalla saadaan ääretön määrä erilaisia ohjelmia, mutta yksikään niistä ei vie äärettömästi tallennustilaa.

Metabolix kirjoitti:

Jaska kirjoitti:

[Väite:] Kaikki tietokoneohjelmat voidaan tehdä sellaisilla C-ohjelmilla, joissa funktion rivit ovat korkeintaan 90 merkkiä pitkiä ja funktiot enintään 34 riviä

Tavallaan väite pitää paikkansa, koska funktioiden ulkopuolelle voi kirjoittaa paljon dataa ja rajallisen mittaisilla funktioilla voi toteuttaa vaikka kääntäjän, joka tekee tuosta datasta uuden ohjelman.

Jos ei sallita tällaista huijausta vaan vaaditaan, että kaikki ohjelman toimintaan vaikuttava koodi ja data on funktioiden sisällä, väitteen voi taas helposti todeta teoriassa vääräksi. C-kieli sisältää rajallisesti eri rakenteita, joten erilaisia määrätyn mittaisia funktioita on rajallinen määrä. Erilaisia ohjelmia on kuitenkin loputtomasti: ohjelma voi tulostaa "a", "aa", "aaa" jne.

Varmaan tässä yhteydessä pitäisi määritellä "tietokoneohjelma" tarkemmin ennen kuin väitteeseen otetaan kantaa. Jotenkin tuntuu, että alkuperäinen kysyjä tarkoitti enemmänkin käytännön ohjelmia (joiden tulee aina mahtua rajattuun muistiavaruuteen ja joita siten on rajallinen määrä) kuin esimerkiksi sitä, voidaanko C-kieltä käyttäen konstruoida (numeroituvasti) ääretön määrä erilaisia ohjelmia, joista kaikki eivät tule mahtumaan esimerkiksi etukäteen kiinnitettyyn 64-bittiseen muistiavaruuteen.

Antti Laaksonen kirjoitti:

Todistukseen riittää näyttää, että minkä tahansa C-funktion voi muuttaa joukoksi funktioita, joissa on enintään 34 riviä ja jokaisen rivin pituus on enintään 90 merkkiä.

Itseasiassa tuo ei riitä. Tuo riittää vain siihen, että minkä tahansa C-ohjelman voi muuttaa speksien rajoihin mahtuvaksi C-ohjelmaksi. Mutta tuo ei ota kantaa siihen, voidaanko kaikki tietokoneohjelmat (miten ne sitten määritelläänkään) muuttaa ensin C-ohjelmiksi.

Käytännössä kai voidaan sanoa, että kaikkia tietokoneohjelmia ei voida toteuttaa C-kielellä. Mielestäni tämän voi nähdä siten, että esimerkiksi kaikille alustoille ei välttämättä ole edes tarjolla C-kääntäjää (tällainen voisi olla vaikka joku harvinainen sulautettu järjestelmä), tai vaikkapa siten, että standardilla C-kielellä ei ole mahdollista suorittaa prosessorin tarjoamia kaikkia käskyjä. Esimerkiksi C-kieli ei sinällään tarjoa mahdollisuutta vaikkapa SSE-käskyjen suorittamiseen, vaikka useat kääntäjät tarjoavatkin mahdollisuuden niiden käyttämiseen esimerkiksi erilaisten intrinsincien ja inline assembler -syntaksin avulla. Tuolloin voitaneen periaatteessa sanoa, että SSE-optimoitujen ohjelmien tekeminen ei suoraan pelkkää C-kieltä käyttäen onnistu?

Epsilon kirjoitti:

Varmaan tässä yhteydessä pitäisi määritellä "tietokoneohjelma" tarkemmin ennen kuin väitteeseen otetaan kantaa.

Niinpäs täytyykin, se jäi multa miettimättä. Ajattelin ensiksi jonkinnäköistä C:llä tehtyä simulaattoria Turingin koneesta, mutta todistus taitaakin kaatua siihen, että C:llä tehdyt ohjelmat ovat äärellisen pituisia. Samoin äärelliset automaatitkin voivat tarvita niin monta muuttujaa ja niin pitkiä muuttujan nimiä, että homma ei toimi käytännössä.

Antti Laaksonen kirjoitti:

Millä tahansa n:llä voidaan tehdä C-ohjelma, joka tulostaa n a-kirjainta ja jokaisessa funktiossa on vain muutama rivi. – – Sen sijaan ongelmaksi tulee jossain vaiheessa, että funktion nimestä tulee liian pitkä.

Kumosit hienosti itse oman väitteesi. Kun funktion nimi on koko ruudun mittainen, sitä ei voi kutsua, koska kutsuvasta funktiosta tulisi liian pitkä.

Kun ruudun koko on 34x90 merkkiä ja käytössä on ASCII-merkistö, erilaisia ruudun sisältöjä eli mahdollisia funktioita on 128^(34*90) = 2^21420. Näistä voidaan muodostaa 2^(2^21420) erilaista funktiokokoelmaa. Jos mikä tahansa kokoelman funktioista voi olla ohjelman aloituskohta, yläraja erilaisten ohjelmien määrälle on 2^(2^21420) * 2^21420. (Tuloksessa on 3,5 * 10^6447 numeroa.)

Oikeasti erilaisia ohjelmia saadaan paljon vähemmän, koska noista 2^21420 "funktiosta" vain pieni osa on toimivaa C:tä, toiminnaltaan sama funktio toistuu monta kertaa (aakkosten eri permutaatiot, välit, kommentit), vain murto-osa kelpaa ohjelman aloituskohdaksi ja niin edelleen.

Antti Laaksonen kirjoitti:

Yllä olevalla tavalla saadaan ääretön määrä erilaisia ohjelmia, mutta yksikään niistä ei vie äärettömästi tallennustilaa.

Sorruin kansankieliseen ilmaukseen. Tarkennus: Kun a-kirjainten määrä lähestyy ääretöntä, tuolla tavalla muodostetun ohjelman pituus lähestyy ääretöntä. Kansankielisesti voidaan silloin sanoa, että kun a-kirjaimia on äärettömästi, myös ohjelmasta tulee äärettömän pitkä.

Jaska kirjoitti:

Kysytään vaikka, että jos meille annetaan kiinnitetty luonnollinen luku n, niin voidaanko jokainen n-tilainen (äärellinen) automaatti simuloida sellaisella C-kielisellä ohjelmalla, että sen funktiot mahtuvat 34x90 merkin kuvaruudulle?

Minusta tämä on entistä huonompi kysymys, koska deterministisen äärellisen automaatin yleispätevä toteutus sinänsä vaatii hyvin vähän koodia ja itse automaatin voi tallentaa erilliseen tiedostoon, jolloin automaatin kokoa rajoittaa lähinnä tallennustila.