haskell - Mitä muita tapoja voidaan käsitellä puhtaalla funktionaalisella kielellä Monadsin lisäksi?

Translate

Joten aloin kietoa pääni ympärille Monadit (käytetään Haskellissa). Olen utelias, mitä muita tapoja IO: ta tai tilaa voidaan käsitellä puhtaalla toiminnallisella kielellä (sekä teoriassa että todellisuudessa). Esimerkiksi on olemassa looginen kieli nimeltä "elohopea", joka käyttää "tehostetyyppiä". Kuinka efektien kirjoittaminen toimisi haskellin kaltaisessa ohjelmassa? Kuinka muut järjestelmät toimivat?

This question and all comments follow the "Attribution Required."

Kaikki vastaukset

Translate

Tässä on useita erilaisia kysymyksiä.

Ensimmäinen,IOjaStateovat hyvin erilaisia asioita.Stateon helppo tehdä itse: Anna vain ylimääräinen argumentti jokaiselle funktiolle ja palauta ylimääräinen tulos, ja sinulla on "tilallinen funktio"; esimerkiksi käännäa -> bosaksia -> s -> (b,s).

Tässä ei ole taikuutta:Control.Monad.Statetarjoaa kääreen, joka tekee työskentelyn lomakkeen "tilatoimintojen" kanssas -> (a,s)kätevä sekä joukko auttajatoimintoja, mutta se on se.

I / O: lla on luonteeltaan oltava jonkin verran taikuutta. Mutta Haskellissa on paljon tapoja ilmaista I / O, jotka eivät sisällä sanaa "monadi". Jos meillä olisi IO-vapaa Haskell-alaryhmä sellaisenaan, ja haluaisimme keksiä IO: n tyhjästä tietämättä mitään monadeista, voimme tehdä monia asioita.

Esimerkiksi, jos haluamme vain tulostaa stdout-tiedostoon, voimme sanoa:

type PrintOnlyIO = String

main :: PrintOnlyIO
main = "Hello world!"

Ja sitten sinulla on RTS (ajonaikainen järjestelmä), joka arvioi merkkijonon ja tulostaa sen. Tämän avulla voimme kirjoittaa minkä tahansa Haskell-ohjelman, jonka I / O koostuu kokonaan tulostuksesta standarditiedostoon.

Tämä ei kuitenkaan ole kovin hyödyllinen, koska haluamme vuorovaikutteisuutta! Joten keksimme uuden tyyppisen IO: n, joka sallii sen. Yksinkertaisin asia, joka tulee mieleen, on

type InteractIO = String -> String

main :: InteractIO
main = map toUpper

Tämän IO-lähestymistavan avulla voimme kirjoittaa minkä tahansa koodin, joka lukee stdinistä ja kirjoittaa stdoutiin (Prelude sisältää toiminnoninteract :: InteractIO -> IO ()joka muuten tekee tämän).

Tämä on paljon parempi, koska sen avulla voimme kirjoittaa interaktiivisia ohjelmia. Mutta se on silti hyvin rajoitettu verrattuna kaikkeen IO: han, jonka haluamme tehdä, ja myös melko virhealtista (jos yritämme vahingossa lukea liian pitkälle stdiniin, ohjelma vain estää, kunnes käyttäjä kirjoittaa enemmän sisään).

Haluamme pystyä tekemään enemmän kuin lukemaan stdinia ja kirjoittamaan stdoutia. Näin Haskellin varhaiset versiot tekivät I / O: n:

data Request = PutStrLn String | GetLine | Exit | ...
data Response = Success | Str String | ...
type DialogueIO = [Response] -> [Request]

main :: DialogueIO
main resps1 =
    PutStrLn "what's your name?"
  : GetLine
  : case resps1 of
        Success : Str name : resps2 ->
            PutStrLn ("hi " ++ name ++ "!")
          : Exit

Kun kirjoitammemain, saamme laiska-luettelon argumentin ja palautamme laiska-luettelon tuloksena. Palautetulla laiska-luettelolla on arvot, kutenPutStrLn sjaGetLine; saatuamme (pyyntö) -arvon voimme tutkia (vastaus) -luettelon seuraavan elementin, ja RTS järjestää sen vastaukseksi pyyntömme.

On tapoja tehdä työskentelystä tämän mekanismin kanssa mukavampaa, mutta kuten voitte kuvitella, lähestymistapa muuttuu melko hankalaksi melko nopeasti. Lisäksi se on virheiden altis samalla tavalla kuin edellinen.

Tässä on toinen lähestymistapa, joka on paljon vähemmän virhealtista ja käsitteellisesti hyvin lähellä sitä, miten Haskell IO todella käyttäytyy:

data ContIO = Exit | PutStrLn String ContIO | GetLine (String -> ContIO) | ...

main :: ContIO
main =
    PutStrLn "what's your name?" $
    GetLine $ \name ->
    PutStrLn ("hi " ++ name ++ "!") $
    Exit

Tärkeintä on, että sen sijaan, että ottaisimme "laiskan luettelon" vastauksista yhtenä suurena argumenttina pääpäässä, teemme yksittäisiä pyyntöjä, jotka hyväksyvät yhden argumentin kerrallaan.

Ohjelmamme on nyt vain tavallinen tietotyyppi - paljon kuin linkitetty luettelo, paitsi että et voi vain kulkea normaalisti: Kun RTS tulkitseemain, joskus se kohtaa arvon kutenGetLinejolla on tehtävä; sitten sen on saatava merkkijono stdiniltä RTS-taikuuden avulla ja välitettävä merkkijono funktiolle, ennen kuin se voi jatkaa. Harjoitus: Kirjoitainterpret :: ContIO -> IO ().

Huomaa, että mikään näistä toteutuksista ei sisällä "maailman ohittamista". "Maailman ohittaminen" ei oikeastaan ole sitä, miten I / O toimii Haskellissa. Varsinainen täytäntöönpanoIOtyyppi GHC sisältää sisäisen tyypin nimeltäRealWorld, mutta se on vain toteutuksen yksityiskohta.

Todellinen HaskellIOlisää tyypin parametrin, jotta voimme kirjoittaa toimintoja, jotka "tuottavat" mielivaltaisia arvoja - joten se näyttää enemmändata IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | .... Se antaa meille enemmän joustavuutta, koska voimme luoda "IOtoiminnot ", jotka tuottavat mielivaltaisia arvoja.

(Kuten Russell O'Connorhuomauttaa, tämä tyyppi on vain ilmainen monadi. Voimme kirjoittaa aMonadesimerkiksi helposti.)


Missä sitten monadit tulevat siihen? On käynyt ilmi, että emme tarvitse sitäMonadI / O: lle, emmekä tarvitseMonadvaltiolle, niin miksi me sitä tarvitsemme ollenkaan? Vastaus on, että emme. Tyyppiluokassa ei ole mitään maagistaMonad.

Kuitenkin, kun työskentelemmeIOjaState(ja luettelot ja toiminnot jaMaybeja parserit ja jatko-ohimenevä tyyli ja ...) lopulta riittävän kauan, lopulta saamme selville, että he käyttäytyvät melko samalla tavalla jollain tavalla. Saatamme kirjoittaa funktion, joka tulostaa jokaisen merkkijonon luettelossa, ja funktion, joka suorittaa jokaisen tilallisen laskennan luettelossa ja ketjuttaa tilan läpi, ja ne näyttävät hyvin samanlaisilta toisilleen.

Koska emme halua kirjoittaa paljon samankaltaisen koodin, haluamme tapan abstraktoida se;Monadosoittautuu hyväksi abstraktiksi, koska sen avulla voimme abstraktoida monia tyyppejä, jotka näyttävät hyvin erilaisilta, mutta tarjoavat silti paljon hyödyllisiä toimintoja (mukaan lukien kaikkiControl.Monad).

AnnettubindIO :: IO a -> (a -> IO b) -> IO bjareturnIO :: a -> IO a, voimme kirjoittaa mitä tahansaIOohjelma Haskellissa ajattelematta koskaan monadeja. Mutta todennäköisesti päädyimme jäljittelemään monia toimintojaControl.Monad, KutenmapMjaforeverjawhenja(>=>).

Toteuttamalla yhteinenMonadAPI, saamme käyttää täsmälleen samaa koodia työskennellessäsi IO-toimintojen kanssa kuin parsereiden ja luetteloiden kanssa. Se on oikeastaan ainoa syy, miksi meillä onMonadluokka - kaapata eri tyyppien yhtäläisyydet.

Lähde
Translate

Toinen tärkeä lähestymistapa onainutlaatuisuuden kirjoittaminen, kutenPuhdas. Lyhyt tarina on, että valtion käsitteitä (mukaan lukien reaalimaailma) voidaan käyttää vain kerran, ja toiminnot, jotka käyttävät muuttuvaa tilaa, palauttavat uuden kahvan. Tämä tarkoittaa, että ensimmäisen puhelun lähtö on toisen tulo, joka pakottaa peräkkäisen arvioinnin.

Tehosteiden kirjoittamista käytetäänOppilaiden kääntäjäHaskellille, mutta parhaan tietoni mukaan se vaatii huomattavaa kääntäjätyötä, jotta se voidaan ottaa käyttöön esimerkiksi GHC: ssä. Jätän keskustelun yksityiskohdista itseni paremmin perehtyneille.

Lähde
Translate

Ensin mikä on valtio? Se voi ilmetä muuttuvana muuttujana, jota sinulla ei ole Haskellissa. Sinulla on vain muistiviitteet (IORef, MVar, Ptr jne.) Ja IO / ST-toiminnot toimiakseen niiden perusteella.

Itse valtio voi kuitenkin olla myös puhdas. Vahvista, että tarkista Stream-tyyppi:

data Stream a = Stream a (Stream a)

Tämä on arvovirta. Vaihtoehtoinen tapa tulkita tätä tyyppiä on kuitenkin muuttuva arvo:

stepStream :: Stream a -> (a, Stream a)
stepStream (Stream x xs) = (x, xs)

Tästä tulee mielenkiintoista, kun annat kahden virran viestiä. Sitten saat automaattikategorian Auto:

newtype Auto a b = Auto (a -> (b, Auto a b))

Tämä on todellaStream, paitsi että nyt jokaisella hetkellä virta saa jonkin tyyppisen syöttöarvona. Tämä muodostaa luokan, joten yksi suoratoiston hetki voi saada arvonsa saman suoran hetkestä.

Jälleen erilainen tulkinta tästä: Sinulla on kaksi laskentaa, jotka muuttuvat ajan myötä ja annat heidän kommunikoida. Joten jokaisella laskennalla on paikallinen tila. Tässä on tyyppi, joka on isomorfinenAuto:

data LS a b =
    forall s.
    LS s ((a, s) -> (b, s))
Lähde
Translate

KatsoHaskellin historia: Laiska luokan kanssa. Siinä kuvataan kahta erilaista lähestymistapaa I / O: n tekemiseen Haskellissa ennen monadien keksimistä: jatkoa ja virtauksia.

Lähde
Translate

On olemassa toiminto, jota kutsutaan toiminnalliseksi reaktiiviseksi ohjelmoinniksi, joka edustaa ajan vaihtelevia arvoja ja / tai tapahtumavirtoja ensimmäisen luokan abstraktina. Tuore esimerkki, joka tulee mieleeni, onJalava(se on kirjoitettu Haskellissa ja sen syntaksin muoto on samanlainen kuin Haskell).

Lähde
Translate

Se ei voi olla (ei, jos "tilalla" tarkoitat "I / O: ta tai muuttuvaa muuttujan käyttäytymistä kuin menettelykielellä"). Ensinnäkin sinun on ymmärrettävä, mistä monadien käyttö muuttuviin muuttujiin tai I / O: han tulee. Yleisestä uskomuksesta huolimatta monadinen I / O ei tule Haskellin kaltaisista kielistä, vaan ML: n kaltaisista kielistä. Eugenio Moggi kehittialkuperäiset monaditopiskellessaan kategoriateorian käyttöä merkintäjärjestelmän semantiikassaepäpuhdastoiminnalliset kielet, kuten ML. Harkitse, miksi monadi (Haskellissa) voidaan luokitella kolmen ominaisuuden mukaan:

  • Niiden välillä on eroarvot(Haskellissa, tyyppia) jailmaisuja(Haskellissa, tyyppiIO a).
  • Mikä tahansa arvo voidaan muuttaa lausekkeeksi (Haskellissa muuntamallaxettäreturn x).
  • Mitä tahansa funktiota arvojen yli (lausekkeen palauttaminen) voidaan käyttää lausekkeeseen (Haskellissa laskemalla)f =<< a).

Nämä ominaisuudet ovat tietysti totta minkä tahansa epäpuhtaan toiminnallisen kielen (ainakin) denotation-semantiikan suhteen:

  • Anilmaisu, Kutenprint "Hello, world!\n", voi olla sivuvaikutuksia, mutta senarvo, kuten(), ei voi. Joten meidän on tehtävä ero näiden kahden tapauksen välillä denotation-semantiikassa.
  • Arvo, kuten3, voidaan käyttää missä tahansa lausekkeessa vaaditaan. Joten denotation-semantiikka tarvitsee toiminnon arvon muuttamiseksi lausekkeeksi.
  • Funktio ottaa arvot argumentteina (funktion muodollisilla parametreilla tiukalla kielellä ei ole sivuvaikutuksia), mutta sitä voidaan käyttää lausekkeeseen. Joten tarvitsemme tavan soveltaa arvojen (lauseketta palauttavaa) funktiota lausekkeeseen.

Niinminkä tahansaEpäpuhtaan toiminnallisen (tai menettelykielen) kielen merkintäsemantiikassa on monadin rakenne hupun alla, vaikka sitä ei nimenomaisesti käytetä kuvaamaan I / O: n toimintaa kielellä.

Entä puhtaasti toiminnalliset kielet?

I / O: n tekemiselle puhtaasti toiminnallisilla kielillä on neljä päätapaa, joista tiedän (käytännössä) (taas rajoittumme menettelytyyliin I / O; FRP on aidosti erilainen paradigma):

  • Monadinen I / O
  • Jatkoa
  • Ainutlaatuisuus / lineaariset tyypit
  • Dialogit

Monadinen I / O on ilmeinen. Jatkopohjainen I / O näyttää tältä:

main k = print "What is your name? " $
    getLine $ \ myName ->
    print ("Hello, " ++ myName ++ "\n") $
    k ()

Jokainen I / O-toiminto suorittaa 'jatkeen', suorittaa toiminnonsa ja sitten hännän kutsuu (konepellin alla) jatkamisen. Joten yllä olevassa ohjelmassa:

  • print "What is your name? "juoksu sitten
  • getLinejuoksu sitten
  • print ("Hello, " ++ myName ++ "\n")juoksu sitten
  • ksuoritetaan (mikä palauttaa ohjauksen käyttöjärjestelmään).

Jatkomonadi on ilmeinen syntaktinen parannus edellä mainittuun. Merkittävämminsemanttisesti, Näen vain kaksi tapaa tehdäI / Otodella toimivat yllä:

  • Tee I / O-toiminnoista (ja jatkoista) palautukseksi "I / O-tyyppi", joka kuvaa suoritettavan I / O-toiminnon. Nyt sinulla on I / O-monadi (jatko-monadipohjainen) ilman uuden tyyppistä kääriä.
  • Tee I / O-toiminnoista (ja jatkoista) palautteet olennaiset()ja tee I / O sivuvaikutuksena yksittäisten operaatioiden kutsumisesta (esim.print, getLine, jne.). Mutta jos lausekkeen arviointi kielelläsi (jonka oikea puolimainmääritelmä on) on sivuvaikutteinen, en pidä sitä puhtaasti toimivana.

Entä ainutlaatuisuus / lineaariset tyypit? Nämä käyttävät erityisiä 'token' -arvoja edustamaan maailman tilaa jokaisen toimenpiteen jälkeen ja pakottamaan sekvensoinnin. Koodi näyttää tältä:

main w0 = let
        w1 = print "What is your name? " w0
        (w2, myName) = getLine w1
        w3 = print $ "Hello, " ++ myName ++ "!\n"
    in w3

Lineaaristen ja ainutlaatuisuustyyppien ero on siinä, ettälineaariset tyypit, tuloksen on oltavaw3(sen on oltava tyyppiäWorld), kun taas vuonnaainutlaatuisuuden tyypit, tulos voi olla jotainw3 `seq` ()sen sijaan.w3vain on arvioitava, jotta I / O tapahtuu.

Jälleen valtion monadi on ilmeinen syntaktinen parannus edellä mainittuun. Merkittävämminsemanttisesti, sinulla on jälleen kaksi vaihtoehtoa:

  • Tee I / O-toiminnot, kutenprintjagetLine, tiukkaWorldargumentti (joten edellinen operaatio suoritetaan ensin ja sivuvaikutteinen (joten I / O tapahtuu niiden arvioinnin sivuvaikutuksena) .Jälleen, jos sinulla on arvioinnin sivuvaikutuksia, mielestäni se ei ole oikeastaan puhtaasti toimiva.
  • TeeWorldtyyppiedustaasuoritettava I / O. Tällä on sama ongelma kuin GHC: lläIOtäytäntöönpano tail-rekursiivisilla ohjelmilla. Oletetaan, että muutamme tulostamainettämain w3. Nytmainhännän kutsuu itseään. Kaikilla toiminnoilla, jotka häntä kutsutaan puhtaasti toiminnallisella kielellä, ei ole arvoa (on vain ääretön silmukka); tämä on perustiedot siitä, kuinka rekursioiden denotationinen semantiikka toimii puhtaalla kielellä. Jälleen, en pidä mitään kieltä, joka rikkoo tätä sääntöä (varsinkin "erityiselle" tietotyypilleWorld) olevan puhtaasti toimiva.

Joten, ainutlaatuisuus tai lineaariset tyypit a) tuottavat ohjelmia, jotka ovat selkeämpiä / puhtaampia, jos käärit ne valtion monadiin ja b) eivät todellakaan ole tapa tehdä I / O puhtaasti toiminnallisella kielellä.

Entä valintaikkunat? Tämä on ainoa tapa tehdä I / O (tai teknisesti muutettavissa olevat muuttujat, vaikka se onkin paljon vaikeampaa), joka todella on sekä puhtaasti toimiva että riippumaton monadeista. Se näyttää tältä:

main resps = [
    PrintReq "What is your name? ",
    GetLineReq,
    PrintReq $ "Hello, " ++ myName ++ "!\n"
  ] where
    LineResp myName = resps !! 1

Huomaat kuitenkin muutamia haittoja tästä lähestymistavasta:

  • Ei ole selvää, miten I / O-toiminnot sisällytetään tähän lähestymistapaan.
  • Sinun on käytettävä numeerista tai sijaintihakemistoa löytääksesi vastauksen, joka vastaa tiettyä pyyntöä, joka on melko hauras.
  • Ei ole mitään selvää tapaa laajentaa vastausta toimintojen yli sen vastaanottamisen jälkeen; jos tätä ohjelmaa käytetään jotenkinmyNameennen vastaavan julkaisemistagetLinepyynnöstä kääntäjä hyväksyy ohjelmasi, mutta se on umpikujassa ajon aikana.

Helppo tapa ratkaista kaikki nämä ongelmat on kietoa valintaikkunat jatkoiksi, kuten tämä:

type Cont = [Response] -> [Request]
print :: String -> Cont -> Cont
print msg k resps = PrintReq msg : case resps of
    PrintResp () : resps1 -> k resps1
getLine :: (String -> Cont) -> Cont
getLine k resps = GetLineReq : case resps of
    GetLineResp msg : resps1 -> k msg resps1

Koodi näyttää nyt identtiseltä aiemmin annetun I / O: n jatko-ohitusselvityksen koodilla. Itse asiassa valintaikkunat ovaterinomainentulostyyppi jatkoillesi jatkumispohjaisessa I / O-järjestelmässä tai jopa jatkumonadipohjaisessa yksisuuntaisessa I / O-järjestelmässä. Muuntamalla takaisin jatkoiksi, sama argumentti pätee, joten näemme, että vaikka ajonaikainen järjestelmä käyttää valintaikkunoita sisäisesti,ohjelmiapitäisi silti olla kirjoitettu tekemään I / O monadi-tyylillä.

Lähde
Translate

[...] Olen utelias, mitä muita tapoja I / O: ta tai tilaa voidaan käsitellä puhtaalla toiminnallisella kielellä (sekä teoriassa että todellisuudessa). [...]

Lisän vain siihen, mitä täällä on jo mainittu (huomaa: joillakin näistä lähestymistavoista ei näytä olevan sellaista, joten niitä on muutama"improvisoidut nimet").

Lähestymistavat vapaasti saatavilla olevilla kuvauksilla tai toteutuksilla:

  • "Ortogonaaliset direktiivit"- katsoVaihtoehtoinen lähestymistapa I / O: lleesittäjät Maarten Fokkinga ja Jan Kuper.

  • "Vaikutuksia kantavat tietorakenteet"- Merkittävä esimerkki on Unique-tyyppi, jota käytetään uusien tunnisteiden toimittamiseen GHC: ssä (katso ghc-8.6.5 / compiler / basicTypes / Unique.hs); siellä on myös muutama kirjastototeutusHakkerointi. Viittaus:

    L. Augustsson, M. Rittri ja D. Synek. Yksilöllisten nimien luomisesta. J.Funktionaalinen ohjelmointi, 4 (1): 117-123, tammikuu 1994.

  • Todistajat- katsoTodistamassa sivuvaikutuksiaesittäjä (t): Tachio Terauchi ja Alex Aiken.

  • Tarkkailijat- katsoTehtävät sovelluskielilleesittäjä (t): Vipin Swarup, Uday S.Reddy ja Evan Ireland.

Muut lähestymistavat - vain viitteet:

  • Järjestelmämerkit:

    L. Augustsson. Toiminnallinen I / O järjestelmän tunnusten avulla. PMG Memo 72, tietojenkäsittelytieteen laitos, Chalmersin teknillinen yliopisto, S-412 96 Göteborg, 1989.

  • "Efektipuut":

    Rebelsky SA (1992) I / O-puut ja interaktiivinen laiska toiminnallinen ohjelmointi. Julkaisussa: Bruynooghe M., Wirsing M. (toim.) Ohjelmointikielen toteutus ja logiikan ohjelmointi. PLILP 1992. Lecture Notes in Computer Science, osa 631. Springer, Berliini, Heidelberg.

Lähde
Kirjailijasta