Vi definierar ett begrepp om stabil och mätbar karta mellan koner utrustade med mätbarhet tester och visar att det bildar en cpo-berikad cartesian sluten kategori. Denna kategori ger en definitionsmodell av en förlängning av PCF som stöder de viktigaste primitiverna i probabilistisk funktionell programmering, såsom kontinuerliga och diskreta probabilistiska distributioner, provtagning, konditionering och fullständig rekursion. Vi bevisar att denna modell är sund och tillräcklig med avseende på en call-by-name operational semantics och ger några exempel på dess utsmyckningar. Panangaden [1999] omramade Kozens arbete i en kategorisk miljö med hjälp av kategorin Kern för stokastiska kärnor. Denna kategori har presenterats som kategorin Kleisli i den så kallade Girys monad [Giry 1982] över kategorin Meas av mätbara utrymmen och mätbara funktioner. Man kan exakt ange frågan om högre ordertyper inom denna ram - både Meas och Kern är kartesiska kategorier men inte stängda. Strävan efter en formell syntaktisk semantik av högre ordning probabilistisk programmering hade större framgång. Vi nämner särskilt Park et al. [2008] och föreslår ett probabilistiskt funktionellt språk λ  på grundval av provtagningsfunktioner. Detta språk har en typ R av sub-probabilistiska fördelningar över den uppsättning av reella tal 1, dvs.. mäter över Lebesgue σ -algebra på R med total massa som högst 1. Med hjälp av de vanliga funktionella primitiverna (särskilt rekursion) tillsammans med den enhetliga fördelningen över [0, 1] och en provtagningskonstruktion kodar författarna olika metoder för att generera distributioner (som omvänd omvandlingsmetod och avstötningsprovtagning) och beräkningsegenskaper om dem (såsom approximationer för förväntade värden, varianser, etc). Det fantastiska draget i λ  på är dess rika uttrycksfullhet som bevittnas av antalet exempel och tillämpningar som beskrivs i [Park et al. 2008], visar relevansen av det funktionella paradigmet för probabilistisk programmering. Fram tills nu, saknade λ  påskrift modell, [Park et al. 2008] skissar endast en operationell semantik. I synnerhet följer korrekturbeviset för kodningarna ett syntaktiskt resonemang som inte är kompositionellt. Vårt papper fyller denna lucka, vilket ger en betecknande modell till en variant av λ. Som en biprodukt kan vi kontrollera programkorrekturen på ett rakt sätt genom att tillämpa standardlagarna för kalkyl (Exempel 7.3.7.4), även för rekursiva program (Exempel 7.9). Denna metod motiveras av Adekvacy Theorem 7.12 som anger överensstämmelse mellan den operativa och den dennotationala semantiken. Om vi begränsar språket till countable data typer (som booleaner och naturliga tal, exklusive de verkliga talen), då situationen är mycket enklare. I själva verket är all fördelning över en räknebar uppsättning diskret, dvs.. Det kan beskrivas som en linjär kombination av dess möjliga utfall och det finns inget behov av ett begrepp om mätbart utrymme. I tidigare artiklar [Ehrhard et al. , 2014 Ehrhard och Tasson 2016], Vi har visat att kategorin PCoh! av probabilistiska sammanhållningsutrymmen och hela funktioner ger fullt abstrakta denotationsmodeller av funktionella språk som utvidgas med en slumpmässig naturlig talgenerator. Huvudsyftet med detta arbete är att generalisera dessa modeller för att redogöra för kontinuerliga datatyper också. Den största svårigheten för en sådan generalisering är att ett probabilistiskt sammanhållningsutrymme definieras med avseende på en sorts kanonisk bas (s.k. web) som på marknivå motsvarar de möjliga proven på en distribution. För kontinuerliga datatyper bör dessa nät ersättas med mätbara mellanslag, och sedan fastnar man på den redan nämnda omöjligheten att associera ett mätbart utrymme med en funktionell typ - både Meas och Kern är inte cartesian stängd. Vår lösning är att ersätta probabilistiska sammanhang med koner [Andô 1962], som redan används av Selinger [2004], vilket möjliggör en axiomatisk presentation som inte hänvisar till en webb. En kon liknar en normerad vektorrymd, men med icke-negativa riktiga skalar (Definition 4.1). Varje probabilistiskt sammanhållningsutrymme kan ses som en kon (Exempel 4.4) såväl som det inställda Meas(X ) av alla avgränsade åtgärder över ett mätbart utrymme X (Exempel 4.6). I synnerhet konen Meas(R) i samband med Lebesgue σ -algebra på R kommer att vara vår tolkning av marken typ R. Vad om funktionella typer, t.ex.. R → R? Från och med den 1 januari 2006 till och med den 31 december 2006 Selinger [2004] studerade begreppet Scott kontinuerliga kartor mellan koner, dvs. monotona icke-decreasing avgränsade kartor som pendlar med lub av icke-decreasing sekvenser 2. Setet av dessa funktioner bildar också en kon med algebraic 1 i [Park et al. 2008 ] R är skrivet på riktigt. Man bör överväga sub-probabilistiska distributioner eftersom programutvärderingen kan skilja sig åt. 2 Faktiskt, Selinger anser lubbar av riktade uppsättningar, men icke-decreasing kedjor är tillräckligt för våra syften. Dessutom, eftersom vi behöver använda monoton konvergens teorem för att garantera mätbarheten av dessa glidmedel i funktion 4 Man kan mycket väl definiera kategorin av avgränsade kärnor också, men detta används inte i detta dokument. 5 Kern har verkligen kartesiska produkter, men vi kommer inte att använda dem.
REF gav en lämplig semantik för en call-by-name PCF med kontinuerlig probabilistic val.
Measurable cones and stable, measurable functions: a model for probabilistic higher-order programming
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}