Keskustelu: Koodit: QB: Funktionaalinen ohjelmointi

Jo nimi funktionaalinen ohjelmointi viittaa siihen, että funktiot liittyvät jollain tavalla asiaan. Näin todellakin on, sillä puhdasoppisessa funktionaalisessa ohjelmoinnissa funktiot ovat korvanneet sellaiset tutut ohjelmointikeinot kuin muuttujat ja silmukat. Tavoitteena on, että ohjelman suoritus vastaa jonkin funktion arvon laskemista. QBasic ei ole varsinaisesti funktionaalinen ohjelmointikieli, mutta silläkin pystyy tutustumaan funktionaalisen ohjelmoinnin saloihin.

Aluksi saattaa tuntua, että pelkillä funktioilla ei saa kovin häävejä ohjelmia aikaan. Tavallisissa ohjelmissahan esiintyy yhtenään muuttujia ja silmukoita, ja nyt niistä kaikista pitäisi luopua. Mutta kun tarkemmin tutkii funktioiden olemusta, niistä paljastuu yllättäviä voimavaroja. Itse asiassa funktionaalinen ohjelmointi pystyy kaikkeen samaan kuin tavallinen (imperatiivinen) ohjelmointikin. Lisäksi funktionaalisuus ei ole pelkkä ohjelmointia hankaloittava riippakivi, vaan siitä voi olla myös hyötyä ohjelmoijalle.

Funktionaalinen QBasic

QBasicissa voi määritellä funktioita, jotka voivat kutsua toisiaan rekursiivisesti, mikä on hyvä lähtökohta. Lisäksi käytössä on joukko valmiita funktioita (esim. VAL, ABS ja MID$). Myös laskutoimituksia (esim. +, * ja XOR) voi ajatella funktioina. Niissä ainoastaan funktion nimi sijoitetaan funktion parametrien väliin. Funktiot voisi jopa määritellä uudestaan tähän tapaan:

FUNCTION PLUS& (a&, b&)
   PLUS& = a& + b&
END FUNCTION

' seuraavat rivit tarkoittavat samaa
PRINT 1 + 2
PRINT PLUS(1, 2)

Tässä ei olisi kuitenkaan mainittavasti järkeä, koska vanha merkintä on lyhyempi ja luettavampi.

Funktionaalinen ohjelmointi ei salli muuttujia eikä silmukoita, mutta ehtolause ei ole pannassa. QBasicin IF-lause ei kuitenkaan näytä päältä päin funktiolta. Määritellään sen vuoksi JOS-funktio ja muutama vakio selventämään funktion toimintaa:

CONST NIIN = 0
CONST MUUTEN = 0

FUNCTION JOS& (ehto&, turha1%, tulos1&, turha2%, tulos2&)
    IF ehto& THEN JOS& = tulos1& ELSE JOS& = tulos2&
END FUNCTION

Nyt on käytössä funktio, jonka sisälle on piilotettu ehtolause:

PRINT JOS(3 > 2, NIIN, 7, MUUTEN, 2)

Tämä funktiokutsu tarkoittaa yksinkertaisesti: jos ehto 3 > 2 on tosi, palautetaan luku 7, muuten palautetaan luku 2. Tässä tapauksessa JOS-funktio palauttaa siis arvon 7, joka myös tulostetaan. Tämä funktio pääsee oikeuksiinsa, kun se liittyy johonkin laajempaan funktioon. Funktion käyttö yksinään tuntuu hieman hassulta, varsinkin, jos ehdon tulos on valmiiksi tiedossa.

Tässä vaiheessa alkaa paljastua yksi funktionaalisen ohjelmoinnin eduista. Kun funktion nimen ja parametrien nimet valitsee hyvin sekä jakaa tehtävän tarvittaessa monen pienen funktion vastuulle, funktiosta näkee usein selvästi, että se tekee juuri halutun asian. Toisin on muuttujien ja silmukoiden kanssa, joiden muodostaman sekasotkun perusteella harva pystyy vannomaan, että ohjelma toimii oikein kaikissa tapauksissa.

Esimerkeistä

Esimerkeissä on neljä varsinaista funktiota: KERTOMA laskee luvun kertoman, FIBO laskee annetun Fibonaccin luvun, TOISINPAIN kääntää merkkijonon toisinpäin ja ONKOPALINDROMI ilmoittaa, onko merkkijono palindromi. Lisäksi ohjelmaan kuuluu joukko pienempiä apufunktioita.

Palindromin tarkastusta lukuun ottamatta yllä mainitut funktiot käyttävät hyväkseen rekursiota, joka kuuluukin funktionaalisen ohjelmoinnin peruspilareihin. Kertoman ja Fibonaccin lukujen laskeminen rekursiolla lienee tuttua, mutta hieman erikoisempi sovellus on merkkijonon kääntäminen. Siinä yhdistetään rekursiivisesti käännetty merkkijonon loppuosa sekä merkkijonon ensimmäinen merkki. Rekursion avulla voikin toteuttaa toiminnot, joihin tavallisessa ohjelmoinnissa käytetään silmukoita.

Käytännössä funktionaalista ohjelmointia QBasicilla rajoittaa pinomuisti, johon sisäkkäin kutsuttujen funktioiden tiedot täytyy tallentaa. Ilmoitus "Out of stack space" saattaa tulla hyvinkin tutuksi monimutkaisia funktioita kokeillessa. Lisäksi rekursiivisten funktioiden alkuun täytyy kirjoittaa ylimääräinen IF-tarkistus keskeyttämään rekursio tarvittaessa, koska JOS-funktion kaikkien parametrien arvo yritetään selvittää ehdosta riippumatta.

Jos innostut ohjelmoimaan funktionaalisesti QBasicilla, laita toki näkyviin omia aikaansaannoksiasi kommentteihin!

CONST NIIN = 0
CONST MUUTEN = 0
CONST JA = 0
CONST EI = 0
CONST KYLLA = 1

PRINT KERTOMA(3) ' 6
PRINT KERTOMA(5) ' 120
PRINT KERTOMA(9) ' 362880

PRINT

PRINT FIBO(8) ' 21
PRINT FIBO(9) ' 34
PRINT FIBO(10) ' 55
PRINT FIBO(25) ' 75025

PRINT

PRINT TOISINPAIN("abc")
PRINT TOISINPAIN("ohjelmointiputka")
PRINT TOISINPAIN(TOISINPAIN("ohjelmointiputka"))

PRINT

PRINT ONKOPALINDROMI("ohjelmointiputka")
PRINT ONKOPALINDROMI("saippuakauppias")

FUNCTION ALOITUSMERKKI$ (mjono$)
    ALOITUSMERKKI$ = LEFT$(mjono$, 1)
END FUNCTION

FUNCTION FIBO& (luku&)
    IF luku& < 0 THEN EXIT FUNCTION
    FIBO& = JOS(luku& < 2, NIIN, luku&, MUUTEN, FIBO&(luku& - 2) + FIBO&(luku& - 1))
END FUNCTION

FUNCTION JO$ (ehto&, turha1%, mjono1$, turha2%, mjono2$)
    IF ehto& THEN JO$ = mjono1$ ELSE JO$ = mjono2$
END FUNCTION

FUNCTION JOS& (ehto&, turha1%, tulos1&, turha2%, tulos2&)
    IF ehto& THEN JOS& = tulos1& ELSE JOS& = tulos2&
END FUNCTION

FUNCTION KERTOMA& (luku&)
    IF luku& < 0 THEN EXIT FUNCTION
    KERTOMA = JOS(luku& = 1, NIIN, 1, MUUTEN, KERTOMA(luku& - 1) * luku&)
END FUNCTION

FUNCTION LOPPUOSA$ (mjono$)
    LOPPUOSA$ = MID$(mjono$, 2)
END FUNCTION

FUNCTION ONKOPALINDROMI& (merkkijono$)
    ONKOPALINDROMI& = JOS(merkkijono$ = TOISINPAIN(merkkijono$), NIIN, KYLLA, MUUTEN, EI)
END FUNCTION

FUNCTION PERAKKAIN$ (mjono1$, turha%, mjono2$)
    PERAKKAIN$ = mjono1$ + mjono2$
END FUNCTION

FUNCTION TOISINPAIN$ (merkkijono$)
    IF merkkijono$ = "" THEN EXIT FUNCTION
    TOISINPAIN$ = JO$(YKSIMERKKINEN(merkkijono$), NIIN, merkkijono$, MUUTEN, PERAKKAIN(TOISINPAIN(LOPPUOSA(merkkijono$)), JA, ALOITUSMERKKI(merkkijono$)))
END FUNCTION

FUNCTION YKSIMERKKINEN& (mjono$)
    YKSIMERKKINEN& = (LEN(mjono$) = 1)
END FUNCTION

Voi hemmetti sun kans :D

Tätä QBasic-koodia oli paljon helpompi ymmärtää kuin sitä tavallista. :)

ei täs oo hevon vitun järkee

onks tollastakin koodii olemas?:)vähän oudon näköst...

mut varmaan toimii ihan kivasti

Onko putkalla paljonkin kävijöitä, jotka osaavat pelkästään QBasicia? Se selittäisi moisen kielivalinnan.

Vastaavia funktioita Haskellilla ("pointless"-tyyliin):

fibo :: Int -> Integer
fibo = (fibo' !!)
       where fibo' = 0 : 1 : zipWith (+) fibo' (tail fibo')

onkoPalindromi :: String -> Bool
onkoPalindromi = s (==) toisinpain
                 where s f g x = f x (g x)

toisinpain :: String -> String
toisinpain = foldl (flip (:)) []

yksimerkkinen :: String -> Bool
yksimerkkinen = (==1) . length
           -- = null . tail

Onko pointless-tyylillä jotain tekemistä point free -tyylin kanssa :-?

Näinkin voi tehdä:

fibo' = fix ((0:) . scanl (+) 1)

s = (((. head . uncurry zip . splitAt 1 . repeat) . uncurry) .) . (.) . flip

Tuon jälkimmäisen on löytänyt Oleg Kiselyov. Ks.
http://okmij.org/ftp/Haskell/types.html

Yleiseksi tiedoksi muuten, että tuo s on SKI-kalkyylistä (kaikkihan sitä osaa ^^) tuttu S-kombinaattori. Kun siihen yhdistetaan K-kombinaattori, saadaankin jo turing-täydellinen systeemi. I-kombinaattori on tunnetusti helppo määritellä esim. muodossa SKK .

Tästä saakin sitten sopivan aasinsillan Lazy K -ohjelmointikieleen:

http://homepages.cwi.nl/~tromp/cl/lazy-k.html

Tämä niille, joille Brainf*ckin kahdeksan (oliko?) operaation määrä on liikaa, tai BF:n imperatiivinen luonne aiheuttaa hankaluuksia ohjelmien todistamisessa oikeaksi. Ei tarvita kuin S, K ja sulut ryhmittelyä varten. Vain raa'an binäärikoodin tekeminen käsin on enää tätä yksinkertaisempaa :-)

Palataan nyt QBasic-aiheesiin. Antti, saisiko ON muuttuja GOSUB -rakenteilla simuloitua lambda-abstraktioita? Jos saa & vielä kun teet monadit QBasicciin, niin vaihdan Haskellista heti!!!1 succ 0

(Anteeksi, jos jotakuta ihmetytti mun jutut. Me haskellistit saamme pillereitä näihin vaivoihin, mutta viime viikon lähetys oli vajaa.)

Kopeekka kirjoitti:

Onko pointless-tyylillä jotain tekemistä point free -tyylin kanssa :-?

Sama asia kyseessä, point free on se oikea termi (J:ssä tacit), mutta joskus olen kuullut huumorimielessä käytettävän pointless:ia.

Kopeekka kirjoitti:

Näinkin voi tehdä:

fibo' = fix ((0:) . scanl (+) 1)

Meni vähän aikaa tuon ymmärtämiseen; en ole vielä paljoa käyttänyt Haskellia. Aika ovela.

Voiko QBasicissa muuten tallentaa funktioita muuttujiin/antaa parametreinä toisille funktioille? Eli onko mahdollista toteuttaa map, filter, fold, yms.?