Sammanfattning av denna webbsida: I detta kapitel undersöker vi hur (Typ-2) beräkningsbara distributioner kan användas för att ge både distributions- och (algoritmiska) provtagningssemantik till probabilistiska program med kontinuerliga distributioner. I detta syfte skissar vi först en kodning av beräkningsbara distributioner i ett fragment av Haskell. Därefter visar vi hur topologiska domäner kan användas för att modellera det resulterande PCF-liknande språket. Hela tiden hoppas vi att betona kopplingen mellan ett sådant tillvägagångssätt och vanlig programmering. Semantik, komputerbara distributioner, topologiska domäner Probabilistiska program uppvisar en spänning mellan det kontinuerliga och det diskreta. Å ena sidan är vi intresserade av att använda probabilistiska program för att modellera naturliga fenomen-fenomen som ofta modelleras väl med reals och kontinuerliga distributioner (t.ex., som i fysik och biologi). Å andra sidan är vi också bundna av den fundamentalt diskreta karaktären av beräkning, som begränsar hur vi kan (1) representera modeller som program och sedan (2) beräkna resultaten av frågor på modellen. Syftet med detta kapitel 123 är att hålla denna spänning i förgrunden genom att använda begreppet en beräkningsbar 1 Detta kapitel innehåller material från Huang (2017) och Huang och Morrisett (2016 Huang, Morrisett och Spitters distribution som en lins genom vilken man kan förstå probabilistiska program. Vi organiserar vår utforskning via en rad frågor. i) Vad är en beräkningsbar fördelning (avsnitt 2)? För det första granskar vi typ 2-beräkning (t.ex., se Weihrauch (2000)) och hur det gäller reals och kontinuerliga distributioner. Tanken på hög nivå är att representera continuumized objekt som en sekvens av diskret approximationer som konvergerar till lämpligt objekt i stället för att abstraktera representationen av ett sådant objekt. ii) Hur genomför vi kontinuerliga distributioner som bibliotek i ett allmänt programmeringsspråk (avsnitt 3)? Efter att vi har sett den grundläggande idén bakom typ 2 beräkningsbarhet, vi skissar en implementering i Haskell som inte använder reals eller kontinuerliga distributioner som black-box primitiver. iii) Vilka matematiska strukturer kan vi använda för att modellera ett sådant bibliotek (avsnitt 4)? Vårt nästa steg är att hitta matematiska strukturer som kan användas för att troget modellera genomförandet. Här kommer vi att se att topologiska domäner (t.ex., se Battenfeld et al. (2007) ; Battenfeld (2008)) är ett alternativ till traditionella strukturer (dvs. fullständiga partiella beställningar, förkortade CPO) som kan användas för att modellera PCF-liknande språk. Topological domäner fånga typ-2 beräkningsbarhet och är också kopplade till realiserbarhet (t.ex., se Streicher (2008)), en tolkning av konstruktiv matematik. iv) Hur ser semantik för ett kärnspråk ut (avsnitt 5)? I detta avsnitt gör vi kopplingen mellan implementeringen och matematiken mer konkret genom att ge semantik till en kärna PCF-liknande språk utvidgas med reals och kontinuerliga distributioner som kallas λ CD. λ-cd stöder också distributioner på valfritt utrymme. Detta innebär att λ-cd inte (i allmänhet) har distributioner på funktionsrymder, även om språket i sig innehåller funktioner med högre ordning. Vi ger både (algoritmisk) provtagning och distributionssemantik till λ CD. v) Vilka konsekvenser får det att man tar en beräkningsbar ståndpunkt för Bayesian inference (avsnitt 6)? Kanske överraskande, åtminstone för dem som använder Bayesian inference i praktiken, kan det visas att konditionering inte kan beräknas; se Ackerman et al. (2011)............................................................................................. Därför finns det en mening i vilken ett "Turing-fullständigt" probabilistiskt programmeringsspråk inte kan stödja villkorliga frågor för varje uttrycklig probabilistisk modell. Lyckligtvis stöter vi inte på dessa patologier i praktiken och kan återställa konditioneringen i tillräckligt allmänna miljöer. Under hela detta kapitel hoppas vi kunna göra kopplingen mellan en semantik baserad på typ 2-beräkning och vanlig programmering. En tillämpning av Computable Distributions. ... Vad är en beräkningsbar distribution? En metod för att studera beräkningsbarhet är baserad på Turing maskiner (t.ex., se Sipser (2012). Enligt detta tillvägagångssätt definierar vi (1) en maskinmodell (dvs. Turingmaskinen) och (2) förhållanden under vilka maskinmodellen sägs beräkna. Mer konkret, en Turing maskin sägs beräkna en (partiell) funktion f :  på ett indataband, där är en ändlig uppsättning och * = {a 0.... a n..., 0 ≤ i ≤ n} är samling av ord som består av tecken från.... Denna definition av beräkningsbarhet visar att traditionell beräkning i grunden är diskret. Vi kan se detta direkt i definitionen av en beräkningsbar funktion (med typ  till *  på * * ), som kartlägger element av en diskret domän (dvs. en uppsättning finita ord * ) till element av en diskret codomain (dvs, en uppsättning finita ord * igen). Eftersom "* är räknebart, kan det inte sättas i bijection med reals R; därför kan vi inte koda alla reals på en Turing maskin. En omedelbar fråga som detta belyser för probabilistiska program är hur vi ska hantera reals och kontinuerliga distributioner samtidigt som anslutningen tillbaka till beräkning. En pragmatisk lösning på detta är att använda flyttal aritmetik, d.v.s. diskretisera och finita reals. Ur detta perspektiv kan vi modellera semantiken hos probabilistiska program med hjälp av flyttalsiffror och finitt understödda diskreta fördelningar (på flottor) så att semantikerna mer troget modellerar ett faktiskt genomförande. Ändå offrar vi korrespondensen mellan programmet och matematiken som vi använder på blyertspapper. Ett alternativ till situationen ovan är att generalisera begreppet beräkningsbarhet till kontinuumstora uppsättningar på ett sådant sätt att beräkningarna fortfarande är fysiskt genomförbara. Type-Two Theory of Effectivity Weihrauch (2000) (TTE) ändrar de förhållanden under vilka en maskin sägs beräkna ett svar men behåller maskinen modellen som är. I denna inställning, en maskin sägs beräkna en funktion f :  på ett indataband, om det kan skriva något första segment av f (w)  på utdatabandet i ändlig tid som ges w  på ett indataband, där  på ett indataband, där  ska = {a 0 a 1...  och a i..., i N} är den uppsättning strömmar som består av symboler från den ändliga uppsättningen  på. Setet har kontinuum kardinalitet, och kan därför representera reals och en klass av distributioner (avsnitt 2.2). När vi repre-4 Huang, Morrisett och Spitters skickat continuum-stora objekt på en maskin, har vi en väg för att studera vilka funktioner som kan beräknas. Istället för att använda en betongmaskinmodell kan vi abstraktera själva maskinen med hjälp av strukturen hos en partiell kombinatoralgebra (PCA). En PCA består av en underliggande uppsättning X och en partiell applikation funktion · : X ×X X omfattas av vissa lagar som säkerställer kombinatorisk fullständighet, d.v.s. att en PCA kan simulera otypade lambda kalkyl. Därför kan vi tänka på en PCA som en algebraisk ta på substitution. En realistisk tolkning av konstruktiv matematik använder en PCA för att förverkliga vittnen (avsnitt 4.4). Vi får vanlig typ-1 beräkningsbarhet genom att instantera en PCA över de naturliga N; den partiella applikationsfunktionen för en PCA · : N  på N kan definieras för att simulera beräkningen av partiella rekursiva funktioner. I förlängningen får vi en maskin av typ 2 genom att instantera en PCA över Baire utrymme B = N → N; partiell applikation funktion av en PCA · : (N → N)  på (N → N) kan definieras för att simulera beräkningen över strömmar av naturliga. Typ 2-kvalificeraren refererar till det faktum att indata kodas av N → N. Under resten av kapitlet, kommer vi att förkorta Typ-2 beräkningsbar som beräkningsbar 4 och använda (Type-2) beräkningsbar för betoning. Vi granskar nu beräknade reals och distributioner. Computability och reals Intuitivt kan vi representera en verklig på en maskin genom att koda sin binära expansion. Mer formellt representerar vi en riktig x  på en maskin genom att koda en snabb Cauchy sekvens av rationella som konvergerar till x. Kom ihåg att en sekvens (q n ) n till N är Cauchy om för varje  till > 0, det finns en N sådan att  tillq n − q m  till <  till varje n, m > N. Således, elementen i en Cauchy sekvens blir närmare och närmare varandra när vi passerar sekvensen. När "q n" – q n+1 – < 2 – n för alla n, kallar vi (q n ) n på en snabb Cauchy-sekvens. Därför, representationen av en verklig som en snabb Cauchy sekvens väcker tanken på att räkna upp sin binära expansion. En riktig x R kan beräknas om vi kan räkna (uniformly i en uppräkning av rationella) en snabb Cauchy sekvens som konvergerar till x. Som ett exempel på en beräkningsbar verklig, överväga två möjliga konvergerande sekvenser till det verkliga antalet 0 nedan. 0 = lim n→∞ x n där x n = 0 för n  på N (konstant) 0 = lim n→∞ y n där y n = 1 (−2) n+1 för n  på N (krossning) 4 Utjämning i vanlig bemärkelse avser typ 1-beräkningsbarhet. En tillämpning av Computable Distributions. ... Eftersom 0 i sig är också ett rationellt tal, kan vi helt enkelt representera det som en konstant 0 sekvens ges av (x n ) n till N. Vi kan också representera 0 som sekvensen (y n ) n till N, där sekvensen hoppar fram och tillbaka mellan positiva och negativa fraktionerade krafter av två som det konvergerar mot 0. En funktion f : R → R kan beräknas om en (snabb Cauchy) sekvens konvergerar till x  på R, det finns en algoritm som ger en (snabb Cauchy) sekvens konvergerar till f (x). Till exempel funktionen + 0 : R → R som lägger till 0 är beräkningsbar eftersom en algoritm kan få en (snabb Cauchy) utgångssekvens genom att lägga till (snabb Cauchy) ingångssekvensen element-wise till en (snabb Cauchy) sekvens av 0. Vi betonar att algoritmen måste fungera generiskt för alla indata (snabb Cauchy) sekvens. Detta krav innebär att vissa funktioner inte kan beräknas. Till exempel, anser funktionen = 0 : R → {t, f } ({t, f } är uppsättningen booleaner), att tester om inmatningen är lika med 0 eller inte. Intuitivt, denna funktion är inte beräkningsbar eftersom vi måste kontrollera hela indatasekvensen. För att till exempel kontrollera att den konstanta sekvensen är likvärdig med thrashing-sekvensen, måste vi kontrollera helheten av båda sekvenserna, vilket inte kan göras i ändlig tid. Beräknade metriska utrymmen Topologiska utrymmen gör det möjligt för oss att bygga en mer allmän uppfattning om beräkningsbarhet på ett utrymme. I syfte att införa reals och fördelningar, anser vi topologiska utrymmen med en uppfattning om avstånd, dvs. metriska utrymmen. Som en påminnelse, ett metriska utrymme (X, d) är en uppsättning X utrustad med en metriska d : X × X → R. En metriska inducerar en samling av uppsättningar som kallas (öppna) bollar, där en boll centrerad vid c X med radien r  på R är uppsättningen av punkter inom r av c, dvs., B(c, r) = {x  på X  på d(c, x) < r}. Topologin O(X) associerad med ett metriska utrymme X är den som induceras av samlingen av bollar. Därför ger de öppna bollarna i ett metriska utrymme ett begrepp om avstånd utöver att ge ett begrepp om approximation.  Cantor topologi är av formen a 1 a 2... a n 2  på, där a i  på 2 (2 = {0, 1}) för 1 ≤ i ≤ n. Det vill säga grundläggande öppna uppsättningar av Cantor utrymme fixa finita prefix. Ett beräkningsbart metriska utrymme ställer ytterligare villkor på ett metriska utrymme så att en maskin successivt kan räkna upp mer exakta approximationer (enligt metriska) av en punkt i det metriska utrymmet. Vi behöver ytterligare två definitioner innan vi kan ange definitionen. För det första, vi säger S är tät i X om för varje x X X, Det finns en sekvens (s n ) N som konvergerar till x, där s n  på S för varje n. Second, Vi säger att (X, d) är komplett om varje Cauchy sekvens som består av element från X också konvergerar till en punkt i X.. En beräkningsbar metriska utrymme är en tuple (X, d, S) sådan att (1) (X, d) är en komplett metriska utrymme, (2) S är en räkningsbar, Enumerable, och tät delmängd, och (3) är en beräkningsbar metriska utrymme för reals där vi använder rationella Q som approximaterande element. Observera att vi på motsvarande sätt kan använda dyadiska rationaliteter som approximerande element istället för Q. Computability och distributioner En fördelning över det beräkningsbara metriska utrymmet (X, d, S) kan formuleras som en punkt i det beräkningsbara metriska utrymmet där M(X) är uppsättningen av Borel sannolikhetsmått på ett beräkningsbart metriska utrymme (X, d, S), d ρ är Prokhorov metriska (se (Hoyrup och Rojas, 2009, Defen. Kommissionen ska anta delegerade akter i enlighet med artikel 290 i EUF-fördraget i enlighet med artikel 290 i fördraget om Europeiska unionens funktionssätt (EUF-fördraget) för att anta delegerade akter i enlighet med artikel 290 i fördraget om Europeiska unionens funktionssätt med avseende på Europaparlamentets och rådets förordning (EU) nr 182/2011 om fastställande av allmänna regler och principer för medlemsstaternas kontroll av kommissionens genomförande av Europaparlamentets och rådets förordning (EU) nr 182/2011 vad gäller tillämpningen av Europaparlamentets och rådets förordningar (EU) nr 182/2011, (EU) nr 182/2011 och om upphävande av Europaparlamentets och rådets förordning (EU) nr 182/2011 och av Europaparlamentets och rådets förordning (EU) nr 182/2011 och om upphävande av Europaparlamentets och rådets förordning (EU) nr 182/2011 och rådets förordning (EU) nr 182/2011 och om upphävande av Europaparlamentets och rådets förordning (EU) nr 182/2011.)), och D(S) är den klass av distributioner med ändligt stöd på idealiska punkter S och rationella massor (se (Hoyrup och Rojas, 2009, Prop. (se avsnitt 4.1.1). Prokhorov metrisk definieras som: där man kan kontrollera att sekvensen nedan konvergerar (med avseende på Prokhorov metrisk) till (standard) enhetlig fördelning U (0, 1). Således kan en enhetlig fördelning ses som gränsen för en sekvens av allt finare diskreta, enhetliga fördelningar. Som med en beräkningsbar real, En tillämpning av Computable Distributions. .. vi säger att en distribution μ  på M(X) är beräkningsbar om vi kan räkna (uniformly i en uppräkning av en bas och rationella) en snabb Cauchy sekvens som konvergerar till μ. Även om idén om en (computable) distribution som en (computable) punkt är ganska intuitiv för standard enhetlig distribution, kan det vara mindre insiktsfull för mer komplicerade distributioner. Alternativt kan vi tänka oss en fördelning på ett beräkningsbart metriska utrymme (X, d, S) i form av provtagning, d.v.s. som en (Typ-2) beräkningsbar funktion 2. För att göra detta mer konkret skisserar vi en algoritm som tar prover från standarduniformen. Tanken är att generera ett värde som kan ifrågasättas för mer precision istället för ett prov x i sin helhet. Således kommer en provtagningsalgoritm interleave flipping mynt med att mata ut ett element till önskad precision, så att sekvensen av utgångar (s n ) n till N konvergerar till ett prov. Till exempel, en binär siffra av precision för en standard uniform motsvarar erhålla punkt 1/2 eftersom det är inom 1/2 av någon punkt i enhetsintervall. Kräva en annan siffra av precision ger antingen 1/4 eller 3/4 enligt resultatet av en rättvis myntflip. Detta kodas nedan med hjälp av funktionen bisect, som rekursivt bisects ett intervall n gånger, börjar med (0, 1), med hjälp av den slumpmässiga bit-stream u för att välja vilket intervall att rekursera på. Enhetlig λu. λn. Vad är det för fel på dig? bisect u 0 1 n I gränsen får vi en enda punkt som motsvarar provet. Provtagningsvyn är (utjämningsbart) likvärdig med synen på en beräkningsbar fördelning som en punkt i ett lämpligt beräkningsbart metriska utrymme. För att ange likvärdigheten behöver vi några definitioner. Ett beräkningsbart sannolikhetsutrymme (Hoyrup och Rojas, 2009, Def. 5.0.1) (X, μ) är ett par där X är ett beräkningsbart metriska utrymme och μ är en beräkningsbar fördelning. Vi kallar en distribution μ på X samplable om det finns en beräkningsbar funktion s : (2  på, μ iid ) (X, μ) sådan att s är beräkningsbar på dom(s) av fullt mått och mäter-bevarande.  Proposition 1.6 ger därför den beräkningsbara analogen av sannolikheten integral transform och omvänd transform från statistik. 8 Huang, Morrisett och Spitters Hur implementerar vi kontinuerliga distributioner som bibliotek i ett allmänt programmeringsspråk? Vårt mål i detta avsnitt är att översätta begreppen om reals och distributioner som vi såg tidigare i Avsnitt 2 till kod. I detta syfte skissar vi ett Haskellbibliotek (Figur 1 ) som kodar reals och provtagningsvyn av distributioner. 5 Vi betonar att biblioteket inte tar reals eller kontinuerliga distributioner som black-box primitiva. Modulen CaLib ger abstraktioner för att uttrycka element som en sekvens av approximationer i ett beräkningsbart metriska utrymme. Typ Ca τ modellerar ett element av en beräkningsbar metriska utrymme och kan läsas som en approximation genom en sekvens av värden av typ τ. Till exempel, en verklig kan ges typen Real Ca Rat, vilket innebär att det är en sekvens av rationella som konvergerar till en verklig. Vi bildar värden av typ Ca τ med hjälp av mkApprox, vilket kräver att vi kontrollerar att funktionen vi tvingar beskriver en snabb Cauchy sekvens, och projicera ut approximationer med nthApprox. För att bilda Ca τ, bör värden av typ τ stödja de åtgärder som krävs för en beräkningsbar metriska utrymme. Vi kan ange vilka operationer som krävs med Haskells typklassmekanism. När vi genomför en instans av CMetrizable τ, Vi bör kontrollera att genomförandet av enum räknar upp en tät delmängd och metriska beräknar en metrisk som en beräkningsbar metriska utrymme kräver (se avsnitt 2.2). Nedan ger vi ett exempel på Ca Rat för beräkningsbara reals. I n s t a n c e C M e t r i z a b l e Rat where enum = 0 : Denna instans räknar upp de dyadiska rationella (krafter 2), som är en tät delmängd av reals. Observera att det finns många andra val här för den täta uppräkningen. 6 I detta fall kan vi faktiskt beräkna metriska som 5 Koden finns på https://github.com/danehuang/cdist-sketch. 6 Algoritmer som fungerar på beräkningsbara metriska mellanslag beräkna genom uppräkning så algoritmen är känslig för valet av uppräkning. En tillämpning av Computable Distributions. ... en dyadisk rationell, medan en beräkningsbar mätare kräver det svagare villkoret att vi kan beräkna metriska som en beräkningsbar verklig. Därefter kan vi använda modulen CaLib för att genomföra beräkningsbara operationer på vanliga typer. Till exempel, ett bibliotek för beräkningsbara reals kommer att innehålla CMetrizable τ instans implementation ovan och andra beräkningsbara funktioner. Vissa operationer är dock inte realistiska (t.ex., jämlikhet av reals) och så denna modul innehåller inte alla operationer som man kan vilja utföra på reals (t.ex., jämställdhet definieras på flottor). Modulen CompDistLib innehåller implementering av distributioner. En sampler Samp α är en funktion från en bitström (dvs RandBits representerade isomorphiskt som Nat -> Bool istället för [Bool]) till värden av typ α. typ R a n d B i t s = Nat -> Bool n e w t y p e Samp a = Samp { g e t S a m p ::: R a n d B i t s -> a } Vi kan implementera en instans av provtagningsmonaden enligt nedan. ............................................................................................................. (par (g e t S a m p s. fst) snd)....................................................................................................... split ) där par f g =\ x -> ( f x, g x ) split = par även udda även u = (\ n -> u (2 * n ) ) udda u = (\ n -> u (2 * n + 1) ) Som förväntat motsvarar avkastning en konstant sampler (konst) som ignorerar dess indata slumpmässighet. Bandet operatör >>= motsvarar en sammansättning av samplorer; vi först dela (splitta) indata slumpmässighet i två oberoende strömmar (via jämna och udda), använda en för att ta prov från s, och fortsätta med den andra i f. Modulen CompDistLib ger funktionen mkSamp för att tvinga en godtycklig Haskell funktion av lämplig typ till ett värde av typ Samp α. Vi bör ringa mkSamp endast på provtagningsfunktioner som realiserar (Typ-2) beräkningsbara provtagningsalgoritmer. Vi kodar nu diskreta och kontinuerliga distributioner med hjälp av de konstruktioner som tillhandahålls av biblioteket. Dessa exempel visar hur välbekanta distributioner som används i probabilistisk modellering kan kodas på ett beräkningsbart sätt (Type-2). När vi går igenom exemplen, kommer vi att stöta på några semantiska frågor som vi skulle vilja att en betecknande semantik av probabilistiska program att hantera. Vi kommer att flagga dessa i kursiv stil och återbesök dem efter införandet av en semantik för probabilistiska program (avsnitt 5). En tillämpning av Computable Distributions. .. Diskret distribution Diskreta distributioner är mycket enklare jämfört med kontinuerlig distribution. Men när man parar ihop sig med rekursion uppstår ändå semantiska problem. Betrakta till exempel kodning av en geometrisk fördelning med bias 1/2, som returnerar antalet rättvisa Bernoulli prövningar tills en framgång. Distributionen stdBernoulli betecknar en Bernoulli fördelning med partisk 1/2. En möjlighet, även om det inträffar med noll sannolikhet, är att dragningen från stdBernoulli alltid är falsk. Följaktligen avviker stdGeometric med sannolikhet noll. En semantik bör klargöra kriteriet för divergens och visa att denna rekursiva kodning faktiskt betecknar en geometrisk fördelning. Kontinuerliga distributioner Nästa, vi fyller i skissen av den standard enhetlig distribution vi presenterade tidigare. Som en påminnelse måste vi omvandla en slumpmässig bit-ström till en sekvens av (dyadiska) rationella approximationer. Funktionen bisect upprepade gånger bisects ett intervall som anges av (l, r). Genom konstruktion producerar provtagaren en sekvens av dyadiska rationella metoder. Vi kan se att denna provtagningsfunktion är jämnt fördelad eftersom den inverterar den binära expansion som anges av den jämnt fördelade ingång bit-ström. När vi väl har den enhetliga standardfördelningen kan vi koda andra primitiva fördelningar (t.ex. normala, exponentiella etc.) som omvandlingar av den enhetliga fördelningen som i standardstatistik med retur och bindning. Till exempel ger vi en kodning av den normala standarddistributionen med hjälp av Marsaglias polaromvandling. Fördelningsuniform (−1) 1 är den enhetliga fördelningen på intervallet (−1, 1) och kan kodas genom att flytta och skala en dragning från stdUniform. En subtil fråga här gäller semantiken i <. Som en påminnelse är jämlikhet på reals inte avgörande. Följaktligen, även om vi har använt < vid typen Real → Real → Bool i exemplet, kan det inte ha standard semantik att bestämma mellan < och ≥. Singular distribution Nästa, vi ger en kodning av Cantor distributionen. Cantor distributionen är singular så det är inte en blandning av en diskret komponent och en komponent med en densitet. Kanske överraskande, denna distribution är beräkningsbar. Distributionen kan definieras rekursivt. Det börjar genom att trisektera enhetsintervallet och placera halva massan på det vänstra och den andra halvan på det högra intervallet, vilket inte lämnar någon massa för mitten, fortsätter på samma sätt med varje återstående intervall som har positiv sannolikhet. Vi kan koda Cantor-distributionen genom att direkt omvandla en slumpmässig bitström till en sekvens av approximationer. Provtagningsalgoritmen håller reda på vilket intervall den för närvarande anges av vänster och höger. Om den aktuella biten är 1, vi trisect den vänstra intervallet. Annars trisectar vi det högra intervallet. Antalet trisektioner begränsas av den precision vi vill generera provet till. Avgörande, kodningen använder sig av idén att generera ett prov till godtycklig noggrannhet med hjälp av en representation i stället för provet i sin helhet. där bot = bot I termen botSamp, definierar vi en oändlig loop vid typen av samplers. Intuitivt motsvarar detta fallet där vi misslyckas med att tillhandahålla en provtagare, d.v.s. ett fel på värsta möjliga sätt. I termen botSampBot producerar vi en provtagare som alltid misslyckas med att returnera ett prov. Med andra ord tillhandahåller vi en provtagare som är bristfällig på värsta möjliga sätt. Vi kan försöka att observera skillnaderna i genomförandet (om sådana finns). Om vi kör termen alltidDiv till vänster, kommer vi att se att programmet alltid skiljer sig. När vi kör termen aldrigDiv till höger, kommer vi att dra från sampler botSampBot men kassera resultatet. På grund av Haskells lata semantik ignoreras denna beräkning och hela termen beter sig som en enhetlig standardfördelning. Vi skulle vilja att en betecknande semantik reflekterade skillnaderna i det operativa beteendet mellan dessa två termer. Observera att lathet gör att vi kan resonera om fördelningar ekvationellt. Vi avslutar med att överväga skillnaden mellan en provtagning och distributionstolkning av probabilistiska program. Nedan ger vi likvärdiga kodningar av distributioner genom att pendla ordningen av provtagning från oberoende distributioner, men lämnar allt annat fast. Ur ett provtagningsperspektiv är de två fördelningarna inte helt likvärdiga eftersom strömmen av slumpmässiga bitar konsumeras i en annan ordning; följaktligen kan de prover som produceras av myNormal och myNormal' vara olika. Så även om en provtagning semantik är lätt att genomföra, skulle vi också vilja ha en distributionssemantik för att möjliggöra resonemang om fördelning ekvivalensen av program. Till exempel skulle detta göra det möjligt för oss att resonera Huang, Morrisett och Spitters att två olika provtagningsalgoritmer för samma distribution är likvärdiga. Implementationen vi skissade ovan är ett bevis på koncept som visar att vi kan förverkliga gränssnittet genom att implementera beräkningsbara distributioner och operationer på dem som Haskell kod. Vi noterar att det finns flera tillvägagångssätt för att koda upp typ 2-beräkning som bibliotek. Ett framträdande alternativ ges av den syntetiska topologin Escardó (2004), som förutsätter att funktionsutrymmet i det programmeringsspråk som används för att koda upp topologiska resultat är kontinuerligt och härleder begreppet en öppen uppsättning. För de inställningar som beräkningsbara metriska utrymmen som vi främst kommer att arbeta med i praktiken, kan en sådan allmän strategi hjälpa oss att strukturera genomförandet, men kommer inte nödvändigtvis att hjälpa oss med att förstå konkreta exempel. En annan brist i biblioteket, och implementationer av typ 2 beräkningsbarhet mer allmänt, är effektivitet. Vi avser att presentera biblioteket som ett sätt att skissa sambandet mellan beräkningen och matematiken. I praktiken finns det fortfarande skäl att använda flyttalsaritmetik. Först, inference algoritmer är beräkningsintensiva, även om verksamheten på reals och distributioner är konstant-tid, så man är villig att göra kompromisser för effektivitet. För det andra är det inte nödvändigt att beräkna svaren på godtycklig noggrannhet för de flesta tillämpningar. Särskilt, de flesta inference algoritmer redan gör approximationer eftersom lösningarna på många intressanta modeller är analytiskt intractable. Det finns alltså fortfarande (stora) skillnader i praktiken mellan semantik och genomförande. För idéer om hur man kan genomföra typ 2-kalkyler effektivt hänvisar vi läsaren till Bauer och Kavkler (2008) och Lambov (2007). Slutligen, i vår beskrivning av biblioteket, har vi undvikit en viktig detalj. En beräkningsbar funktion som vi behöver koda är modulen för en beräkningsbar funktion mellan beräkningsbara metriska utrymmen. Modulen g : är en funktion som beräknar antalet indata approximationer som förbrukas för att producera en uteffekt approximation till en specificerad precision. Till exempel, om algoritmen realiserar f tittar på n+1) och (s X im ) m till N → x, då modulen g (f ) (n) är 42. Inom en maskinmodell kan man helt enkelt "titta på tejpen och huvudets placering" för att få modulen. Man kan dock visa att kontinuitetsmodulen inte är exAn Application of Computable Distributions. ... tryckbart på ett funktionellt extensivt språk. Detta följer i huvudsak av det faktum att modulerna för två extensivt likvärdiga funktioner kanske inte är likvärdiga. Vi kan använda Haskells otydliga undantagsmekanism (se Peyton Jones et al. (1999) ), en oren egenskap, på ett begränsat sätt för att uttrycka modulen. 7 Vilka matematiska strukturer kan vi använda för att modellera ett sådant bibliotek? Nu när vi har sett att vi kan implementera reals och kontinuerliga distributioner i kod, är vår nästa uppgift att hitta matematiska strukturer som kan användas för att modellera genomförandet. Genom att göra detta kommer vi att sätta upp oss själva för att ge denotationssemantik till probabilistiska program (avsnitt 5) under den ytterligare begränsning som modellen tar hänsyn till. I detta syfte granskar vi topologiska domäner (avsnitt 4.1), ett alternativ till traditionell domänteori som dessutom stöder (Typ-2) beräkningsbarhet. Topological domäner har den struktur som krävs för att tolka PCF-liknande språk, och kan därför utgöra grunden för en semantik för dessa språk. Vår nästa uppgift är att hitta topologiska domäner som motsvarar distributioner på ett visst utrymme. Vi gör detta för en provtagningsvy (avsnitt 4.2) och en fördelningsvy (avsnitt 4.3) baserad på värderingar, en topologisk variant av ett mått. Vi konstruerar också en sannolikhetsmonad Giry (1982) så att vi kan modellera den monadiska implementeringen av distributioner i biblioteket. Slutligen sätter vi det tillvägagångssätt som föreslås här, som betonar (typ 2) beräkningsbarhet, i perspektiv. För det första undersöker vi en alternativ metod för att fånga (typ-2) beräkningsbarhet a la realizability (avsnitt 4.4). Grovt taget kan vi se en konstruktiv logik som ett "programmeringsspråk" som vi kan använda för att programmera beräkningsbara distributioner. Vi avslutar (avsnitt 4.5) genom att kortfattat granska alternativa strukturer som kan användas för att modellera semantiken i probabilistiska program. I detta avsnitt granskar vi topologiska domäner. Till skillnad från en CPO, en topologisk domän i allmänhet inte bär Scott topologi, och därför, anser inte den partiella ordningen primär. I stället börjar topologiska domäner med topologin som primär och härleder ordningen. För en fullständig behandling hänvisar vi läsaren till Battenfeld (2008) och referenser inom (t.ex., (2006, 2007)). I detta syfte kommer vi att följa översikten över Battenfeld et al. (2007) att introducera de viktigaste idéerna, som konstruerar topologiska domäner i två steg genom att 1) koppla ihop beräkningsbarhet med topologi och 2) relatera topologi till ordning. De flesta av denna översikt kan skummas efter en första läsning, även om exemplen kommer att vara till hjälp. I slutändan kommer vi att sammanfatta den relevanta struktur som gör topologiska domäner bra kandidater för modellering av probabilistiska program. I Avsnitt 5 kommer vi att använda denna struktur för att ge semantik till ett kärnspråk. Computability to topology Topological domain theory börjar med observationen att topological spaces ger en bra modell av datatyper. Kort sagt, en punkt i ett topologiskt utrymme motsvarar en invånare i en datatyp och de öppna uppsättningarna i topologin beskriver de observerbara egenskaperna hos punkter. Följaktligen kan man testa om en invånare i en datatyp uppfyller en observerbar egenskap genom att utföra en (potentiellt avvikande) beräkning som testar om punkten finns i en öppen uppsättning. För att använda sig av denna observation bygger topologisk domänteori av Cartesian closed kategori av qcb 0 mellanslag 8 (t.ex. se Escardó et al. (2004)), en underkategori av topologiska utrymmen som gör kopplingen mellan beräkning och topologi exakt. Det är bra att introducera en qcb 0 utrymme genom ett representerat utrymme som börjar med idén att realisera beräkningar på en maskinmodell innan du lägger tillbaka den topologiska strukturen. Derivat – Säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning, säkringsredovisning och säkringsredovisning. Ett representerat utrymme (X, δ X ) är ett par av en uppsättning X med en partiell surjektiv funktion δ X : 2  på X kallas en representation. Vi kallar p 2 för x när δ X (p) = x. Således kodar ett namn ett element av basen uppsättningen X som en bit-ström som i sin tur kan beräknas på av en Turing maskin. En realiserare för en funktion f : representerade mellanslag kallas beräkningsbar om den har en beräkningsbar realiserare. Det kallas kontinuerlig om det har en kontinuerlig realiserare (med avseende på Cantor topologi). Unfolding definitionen av kontinuitet av en (partiell) funktion f : 2  på Cantor utrymme visar att det kodar en ändlig prefix egenskap-detta innebär att en maskin kan beräkna f (p) till godtycklig precision efter att ha konsumerat en ändlig mängd bitar av p i ändlig tid när f är kontinuerlig. För att kunna relatera maskinmodellvyn till en topologi så att vi kan definiera ett qcb 0 utrymme, behöver vi en uppfattning om en godtagbar representation. En representation av X är tillåten om 8 qcb 0 står för en T 0-kvot av ett räknat baserat utrymme för någon annan representation δ ′ X av X. En tillämpning av Computable Distributions. ... identifieringsfunktionen på X har en kontinuerlig realiserare (Battenfeld et al., 2007, Defen. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. I denna förordning gäller följande definitioner: En qcb 0 utrymme är ett representerat utrymme (X, δ X ) med tillåtlig representation δ X. Topologin är den quotient topologin (eller den slutliga topologin) som induceras av representationen δ X. Om X och Y är qcb 0 utrymmen, då topologiskt kontinuerliga funktioner mellan dem sammanfaller med dem som har kontinuerliga realiserare (Battenfeld et al., 2007, Cor. 3.13), vilket ger samma karakterisering som ett tillåtligt representerat utrymme. Vi ger två exempel på qcb 0 mellanslag för att illustrera motsvarande insikter och topologier. Exempel 1.9. (S, δ S ) är ett qcb 0 utrymme. Den har underliggande uppsättningen S = {-, -) och representationen δ S (-) = 0 och δ S (-) = p för p = 0 -. I synnerhet, Detta kodar begreppet semi-defidability-en Turing maskin semi-decides som ett förslag innehar (kodas som...) endast om det så småningom ger en icke-noll bit. Utrymmet S är känt som Sierpinski utrymme, som har öppna uppsättningar {∅, {-}, {-, -}}. Exempel 1.10. Låta (X, d, S) vara ett beräkningsbart metriska utrymme. Sedan, (X, δ Metric ) är en qcb 0 utrymme med tillåten representation δ metrisk som använder snabba Cauchy sekvenser som namn. Mer konkret, (δ Q (w n )) n en → δ metrisk (p) när δ(p) = w 1, w 2,..... Som ett specialfall, (R, δ R ) är ett representerat utrymme, där δ R är en representation som använder snabba Cauchy sekvenser av rationella som namn. Topologi att beställa Nästa bit av struktur topologisk domänteori innebär är den ordning-teoretiska aspekten. Tanken är att använda standardtolkningen av rekursiva funktioner som den minst övre gränsen i en stigande kedja av de ungefärliga funktioner som erhålls genom veckling. Eftersom topologisk domänteori tar topologin som primär och ordningen som sekundär, kräver denna uppgift ytterligare arbete. Kom ihåg att vi kan konvertera ett topologiskt utrymme till en förbeställd uppsättning via specialiseringen förordning, som beställer x  på y om varje öppen uppsättning som innehåller x också innehåller y. Vi skriver S för att omvandla ett topologiskt utrymme till en förbeställd uppsättning. Intuitivt, x Om x innehåller mindre information än y. För ett metriska utrymme kan vi alltid hitta en öppen boll som skiljer två olika punkter x och y (eftersom avståndet mellan två olika punkter är positivt). Därför ger specialiseringen förordningen av ett metriska utrymme alltid den diskreta ordningen (dvs. informationsbeställning), och därmed degenererat, en CPO. Huang, Morrisett och Spitters en topologisk predomän om varje stigande kedja (x i ) i.N (med avseende på specialiseringen preordern) har en övre gräns x sådan att (x i ) i.N → x (med avseende på dess topologi). Således ser vi i definitionen att en topologisk predomän (1) bygger av en qcb 0 utrymme och (2) säkerställer att minst övre gränser för ökande kedjor finns. Det tidigare tillståndet ger topologin och teorin om effektivitet medan det senare villkoret förbereder för modellering av minst fasta punkter. Följande ger en användbar karakterisering av qcb 0 mellanslag som relaterar topologin tillbaka till ordningen. Därför ser vi att Scott topologin i allmänhet är finare än topologin som förknippas med en topologisk predomän. Jämfört med standarddomänteorin kallas en topologisk predomän en topologisk domän om den har minst element, skriven, under sin specialiseringsordning (Battenfeld et al., 2007, Defen. 5,6), särskilt artikel 2.1 a, b, c, d, d, d, d, e, f, e, f, f, e, f, f, f, e, f, f, f, e, f, f, f, e, f, f, f, f, e, f, f, f, f, f, f, f, e, f, f, f, f, e, f, f, f, e, f, f, e, f, f, f, e, f, f, f, e, f, f, f, e, f, f, f, f, f, e, f, f, f, e, f, f, e, f, f, e, f, f, e, f, f, f, f, e, f, f, f, f, u, f, f, f, u, f, f, l, u, u, f, u, u, f, f, i, u, u, u, u, u, u, u, u, u, f, f, f, u, f, f, f, f, f, u, u, f, f, f, f, u. Vi tittar närmare på förhållandet mellan ordning och topologi genom en rad exempel nedan. Exempel 1.14. Betrakta den diskreta CPO (N,  till diskret ) med diskreta beställningen  på diskret, (dvs, n  på diskret m om n = m). Scott topologin på denna CPO ger den diskreta topologin, d.v.s., O(N) = {{n} N}. Specialiseringen preorder tillämpas på den resulterande topologin ger tillbaka den ursprungliga CPO. Därför ser vi dessutom att den topologiska predomänen sammanfaller med CPO. I de två exemplen ovan såg vi fall där ordningen och topologin sammanfaller. I de två följande exemplen kommer vi att se fall där de skiljer sig åt, vilket belyser skillnader mellan CPO och topologiska (pre)domäner. En tillämpning av Computable Distributions. .. Byggverksamhet, 1994, pg. 46), senast ändrad genom förordning (EG) nr 765/2008.) Symbolen anger att kategorin är stängd under denna konstruktion och symbolen + indikerar dessutom att den motsvarar lämplig kategorisk konstruktion. Exempel 1.16. Realsen R med Euclidean topologi är ett metriska utrymme, och därmed, specialiseringen preorder ger en diskret CPO (R,  till diskret ). Scott topologin för den resulterande diskreta CPO är dock den diskreta topologin. Därför sammanfaller inte topologierna. Exempel 1.17. Scott kontinuerliga funktioner R  på CPO R innehåller alla funktioner, vilket skiljer sig från utrymmet för kontinuerliga funktioner R  på TD R mellan topologiska predomäner. Vi kommer att subskriptera funktionsutrymme med lämplig kategori när det inte framgår från sammanhang vilka funktionsutrymme vi hänvisar till, som i detta exempel. Det sista exemplet gäller modellering av divergens på reals. Exempel 1.18. De partiella realsR (t.ex., se Escardó (1996) ) kan modelleras som (stängda) intervall [l, u] beställs genom omvänd inkludering där l är en lägre real och a u är en övre real. Subrymden av de maximala elementen ger den välkända Euclidean topologin. Observera attR = R  till. Kategorisk struktur Vi avslutar med att sammanfatta den kategoriska strukturen av topologiska domäner (Figur 2 ) som gäller för att ge semantik till probabilistiska program. I korthet har topologiska (pre)domäner i stort sett samma kategoriska struktur som sina motsvarigheter i CPO. Därför kommer vi att kunna ge semantik till programmeringsspråk som använder topologiska domäner på ungefär samma sätt som vi använder CPO. De relevanta kategorierna inkluderar TP (topologiska predomäner och kontinuerliga funktioner), 9 TD (topologiska domäner och kontinuerliga funktioner), 10 och 9 TP är ett fullständigt reflekterande exponentiellt ideal för QCB (kategori med qcb 0 utrymmen som objekt och kontinuerliga funktioner som morfismer) (Battenfeld et al., 2007, Thm. 5, 5) och av följande skäl: 10 TD är en exponentiell ideal av QCB och är stängd under räknabara produkter i QCB (Battenfeld et al., 2007, Thm. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Huang, Morrisett och Spitters TD! (topologiska domäner och strikta kontinuerliga funktioner). 11 Vi kommer att använda notationen nedan för kategoriska konstruktioner med vanliga semantik.  Vi har också de vanliga härledda funktioner med den förväntade semantik för, och uncurrying uncurry : (D  och E) (D × E) (och currying). 13 Som en påminnelse omvandlar biblioteket implementationen en inmatning bit-ström till ett prov i önskat utrymme. Därför börjar vi med att koda provtagning genomförande av distributioner från biblioteket som en topologisk domän. Definiera en (endo)functor S som skickar en topologisk predomain D till en sampler på D och en morfism till en som komponerar med den underliggande sampler. Sedan är den topologiska domänen S(D) en provtagare som producerar värden i den upplyfta topologiska domänen D. Vi skriver "(f) för att indikera tillämpningen av hissen functor" till en morfism f. Proposition 1.19. Den functor S definieras som väldefinierad, där 2 är den topologiska predomänen utrustad med Cantor topologi. Det minsta elementet är en som kartlägger alla bit-streams till. Nästa, vi definierar 11 TD! (1) är till stor del komplett (gränsvärden ärvda från QCB), (2) har räknabara samprodukter, och (3)  till och (med S som enhet) ger symmetri monoidal sluten struktur på TD! (Battenfeld m.fl., 2007, Thm. 6.1, Thm. 6.2, Försl. till förordn. 6.4). 12 En krossad produkt D E identifierar det minsta elementet av D med det minsta elementet av E. 13 Vi inkluderar summor (D + E) och sammanslagna belopp (D  på E) för fullständighet. Liknar en krossad produkt, en sammanslagen summa D  på E identifierar det minsta elementet av D med det minsta elementet av E. En tillämpning av Computable Distributions. ........................................................................................................ Den första åtgärden skapar en sampler som ignorerar sin input bit-randomness och alltid returnerar d. I definitionen använder vi en funktion const : Den andra åtgärden delar en input bit-stream u i bit-strömmar indexeras av jämna index u e och udda index u o. Observera att om u är en sekvens av oberoende och identiskt fördelade bitar, då både u e och u o kommer också att vara. Den tredje operationssekvensen är två provtagare. Det delar input bit-randomness och kör sampler s på en av de bit-strömmar som erhålls genom att dela för att producera ett värde. Detta värde matas till f, som i sin tur producerar en sampler som körs på den andra bit-stream erhålls genom delning. Vårt mål är nu koda distributioner inom ramen för topologiska domäner. När vi har gjort det kan vi tolka distributionstermer i biblioteket som element i den lämpliga topologiska domänen. Den relevanta idén är begreppet värdering. Värderingar och mått En värdering delar många av samma egenskaper som ett mått och kan därför ses som en topologisk variation av fördelningen. En viktig skillnad mellan värderingar och åtgärder är att värderingen inte är nödvändig för att uppfylla den anmärkningsvärda additionaliteten. Räknabar additionalitet 22 Huang, Morrisett och Spitters är kanske ett av de viktigaste inslagen i en åtgärd. Vi kan rätta till denna situation för värderingar genom att begränsa oss till de kontinuerliga värderingarna. Som en påminnelse kallas en värdering mot (=-kontinuerlig) om vs (N-V n ) = sup n-N vs(V n ) för (V n ) n-N en ökande sekvens av öppna. Därför, den räknebara additiviteten av μ kodar den oavbrutna egenskapen. Viktigt, notera att varje Borel mått μ kan begränsas till lattice av öppna, skriftlig μ och O(X), vilket resulterar i en kontinuerlig värdering. Varje Borel åtgärd μ på X kan begränsas till en kontinuerlig (Schröder, 2007, Sec. Europaparlamentets och rådets förordning (EU, Euratom) nr 966/2012 av den 25 oktober 2012 om finansiella regler för unionens allmänna budget och om upphävande av rådets förordning (EG, Euratom) nr 1605/2002 (EUT L 298, 26.10.2012, s. 1). Dessutom är μ unikt bestäms av sin restriktion till öppningarna μ och O(X). 14 Med andra ord kan vi identifiera distributioner på topologiska utrymmen med kontinuerliga värderingar. Förekomsten av topologisk och ordningsteoretisk struktur föreslår två strategier för att koda värderingar som topologiska domäner. I det första tillvägagångssättet skulle vi ta en insiktsfull ståndpunkt eftersom varje topologisk domän också är ett qcb 0 utrymme. Enligt detta tillvägagångssätt skulle vi (1) (ii) C (X, S)  och = O (X) när X är ett godtagbart representerat utrymme. 15 Nästa förslag visar att de realiserande och ordningsteoretiska åsikterna är likvärdiga under det ytterligare antagandet att basens topologiska utrymme är räknat baserat. Förslag 1.22. Låt (X, O(X)) vara ett räknat baserat topologiskt utrymme. Förslag 1.22 ger tre likvärdiga vyer av en värdering som 1) en kontinuerlig CPO-funktion, 2) en kontinuerlig karta mellan representerade utrymmen och 3) en kontinuerlig funktion mellan topologiska domäner. View (2) indikerar att det finns en tillhörande teori om effektivitet på värderingar. Vi kommer att använda denna syn för att ge semantik till probabilistiska program. Integration I likhet med hur man kan integrera en mätbar funktion med avseende på en åtgärd kan man integrera en lägre semikontinuerlig funktion med avseende på en värdering. Låt X vara ett representerat utrymme och μ  på M 1 (X), där M 1 (X) är samlingen av Borel åtgärder på X som har totalt mått 1. Förslag 1.23. Integralen av en lägre semikontinuerlig funktion f  på C (X, [0, 1] < ) med avseende på ett Borelmått μ är lägre semikontinuerlig (se (Schröder, 2007, Prop. 3 och 6.6). I själva verket är det ännu lägre semi-computable (se (Schröder, 2007, Prop. 3.6) och (Hoyrup och Rojas, 2009, prop. 4.3 Integralen definieras på ett liknande sätt som Lebesgue integralen, dvs. som gränsen för stegfunktioner på öppnas i stället för mätbara uppsättningar. Integralen har många av samma egenskaper, inklusive Fubini och monoton konvergens. 15 Den andra punkten ska läggas till (Schröder, 2007, Thm. Detta anslag är avsett att täcka utgifter för studier, möten med experter, möten med experter, möten med experter, möten med experter, möten med experter, möten med experter, möten med experter, möten med experter, möten med experter och experter samt andra administrativa utgifter. 16 Den första punkten är tillagd (Schröder, 2007, Sec. 3.1, Thm 3.5, Cor. 3 och 5. 5) För den andra punkten, kom ihåg att varje kontinuerlig spets CPO med sin Scott topologi sammanfaller med en topologisk domän Battenfeld et al. (2007)............................................................................................. Det minsta elementet är den värdering som kartlägger varje öppen uppsättning till 0. 24 Sannolikhet monad Slutligen kombinerar vi resultaten om värderingar och integration för att definiera en sannolikhet monad. Vi börjar med konstruktioner för en provtagningstolkning. Definiera (endo)functor P på räknat baserade topologiska predomäner som skickar ett objekt D till utrymmet för värderingar på D och en morfism till en som beräknar framdrivningen. Förslag 1.24. Den functor P definieras som väldefinierad. Det är enkelt att kontrollera att P är en functor. Vi kan konstruera en sannolikhetsmonad med hjälp av functor P. Proposition 1.25. Trippeln (P, η,  på) är en monad, där det är till stor del enkelt att kontrollera att (P, η,  på) är en monad. När det gäller bindning kan vi kontrollera att identiteter som involverar integraler innehar via standardargument (t.ex. Jones (1989)). Avsnitten 4.1, 4.2 och 4.3 tillsammans ger tillräckligt med struktur för att ge semantik till probabilistiska program. Men innan vi ser semantiken i aktion i ett kärnspråk (avsnitt 5) utforskar vi en annan metod för (Typ-2) beräkning baserad på realiserbarhet. Som en påminnelse kan vi använda en betongmaskinmodell (dvs. en Turingmaskin) eller använda en abstrakt maskin (dvs. en PCA) för att uttrycka typ 2-beräkning. Vi har i stor utsträckning följt det tidigare tillvägagångssättet i hela detta kapitel. I detta avsnitt kommer vi att överväga det senare tillvägagångssättet. Det främsta skälet till att göra det är att vi kommer att få ett annat perspektiv på beräkningsbarhet (dvs. förutom de topologiska och ordningsteoretiska) som ger en konstruktiv syn. I synnerhet kommer vi att få en annan syn på vad det innebär att "programmera" en beräkningsbar distribution. Dessutom är det också möjligt att ge semantik till programmeringsspråk direkt med hjälp av realiserbara tillvägagångssätt (t.ex., se Longley (1995 ). Därför kommer vi en tillämpning av Computable Distributions. ... få en annan metod för att ge semantik utöver den traditionella ordningsteoretiska. I resten av detta avsnitt är vårt mål att visa att de basutrymmen och konstruktioner som är användbara för att ge semantik till probabilistiska program med kontinuerliga distributioner kan förverkligas på lämpligt sätt. Översikt Frasen vi tänker på är: "Komputabilitet är den realistiska tolkningen av konstruktiv matematik" Bauer (2005). Tanken på hög nivå är att koda kända matematiska objekt i en lämplig logik och härleda beräkningsbarhet som en följd av att ha en ljudtolkning. Programmering av matematiska utrymmen och deras operationer kommer då att motsvara kodning av utrymmet och deras operationer i logiken. (Logic) Logiken för vår inställning är elementär analys (t.ex., se (Lietz, 2004, Sec. 1.3.3)), som kallas EL. EL utökar en intuitionistisk grundlogik med (1) Heyting aritmetik, (2) en sort för Baire utrymme Baire för att koda kontinuum-stora objekt, och (3) primitiv-recursion och associerade operatörer. (Semantik) Semantiken för denna inställning inkluderar kategorin Asm(K 2 ) av sammansättningar över Kleenes andra algebra K 2 (dvs. en PCA över Baire utrymme) och hela underkategori Mod(K 2 ) av blygsamma uppsättningar över K 2. För mer information om sammankomster och blygsamma uppsättningar hänvisar vi läsaren till relevant litteratur (t.ex. Streicher (2008); Bauer (2000a); Birkedal (1999) ). För våra syften räcker det att komma ihåg att en blygsam uppsättning kan identifieras med ett representerat utrymme och att en samling är ett representerat utrymme med en multi-representation. Därför, blygsamma uppsättningar modell data-typer och sammansättningar modell intuitionistisk logik. Eftersom vi tar en konstruktiv utsiktspunkt måste vi kontrollera att semantiken som framkallas av de relevanta kodningarna av välkända matematiska objekt i logiken sammanfaller med den vanliga tolkningen. För våra syften innebär detta att kontrollera att kodning av objekt som reals och distributioner i EL producerar den förväntade semantiken. I detta syfte, kom ihåg att vi kan associera en teori om effektivitet med ett utrymme genom att definiera det som en kvot av Baire utrymme B  på ett partiellt ekvivalens förhållande (PER). En quotient av en PER gör att vi kan bygga quotienter och undergrupper av Baire utrymme på en gång. Vi erinrar oss de villkor som krävs i relationen för att den konstruktiva kodningen ska sammanfalla med den klassiska tolkningen nedan. Definition 1.26 (Lietz, 2004, prop. (se avsnitt 3.3.2). Vi skriver "* om (RF konservativ klass)  på CC (rf ), dvs., tidigare är nästan negativa. Förslag 1.27 (Lietz, 2004, prop. (se avsnitt 3.3.2). Om  till *, Då tolkningarna av B  på kategorierna Asm(K 2 ) och Asm t (K 2 ) (dvs, sanningen eller klassisk tolkning) ger kalkylabelt likvärdiga strukturer realiserbarhet. Kodningar Innan vi går vidare till kodningarna av uppsättningarna av intresse i EL, definierar vi två uppräkningar som kommer att vara användbara för att konstruera kodningarna. Låta π 1 n, m = n och π 2 n, m = m så att de är parning funktioner på naturals (t.ex., Cantor parning funktion). Vi överbelastar också notation α, β till par α  på B och β på B. Med ord kan vi tänka på ett heltal som en skillnad på två naturals. Vi skriver Int för att hänvisa till uppräkning på N × N. (Rationals) Koda rationella som var p, q = Q s, t om p · t = s · q (t.ex., som i (Bauer, 2000a, Sec. 5, 5) och 5, 5). Med ord kan vi tänka på en rationell som ett förhållande av ett heltal och en icke-negativ natur. Vi skriver Rat för att hänvisa till uppräkningen på Z×(N\{0}). Vi skriver ≤ Q och < Q för att implementera ≤ respektive < på rationella. 17 (Icke-negativa rationella) Koda icke-negativa rationella likheter med rationella, där vi ersätter Z med N. Vi skriver NnRat för att hänvisa till uppräkning på N × (N\{0}). Vi skriver < Q + för att genomföra < på de icke-negativa rationella. 17 Observera att vi har den p, q < s, t om p · t < s · q (t.ex., som i (Bauer, 2000a, Sec. 5, 5) och 5, 5).
I själva verket har Ref redan föreslagit den som grund för den statistiska probabilistiska programplaneringen.
An Application of Computable Distributions to the Semantics of Probabilistic Programs
{'venue': 'Foundations of Probabilistic Programming, ed. Gilles Barthe, Joost-Pieter Katoen&Alexandra Silva, Cambridge University Press, 2020', 'journal': None, 'mag_field_of_study': ['Computer Science']}