Search

Deductive software verification is used to prove correctness of programs with respect to contracts. Contracts are commonly expressed on procedures of a program using Hoare logic. Such contracts consist of a precondition, specifying a condition that must hold before the procedure is executed, and a postcondition which specifies what is guaranteed in return. A contract can be considered an agreement between the user of a procedure and its developer. It is important that the process of verifying that the procedures of a program satisfy their respective contracts is scalable. Scalability can be achieved by making sure verification is procedure-modular, which means that every procedure call can be replaced by the contract of the called procedure directly instead of being evaluated. The axioms of Hoare logic makes it a good basis for procedure-modular reasoning. But Hoare logic is not well-suited for reasoning about a procedure’s behaviour over a sequence of states. The stated questions are how a contract language for specifying such temporal properties can be designed, and how a procedure can be verified to satisfy contracts expressed in such a contract language in a procedure-modular way. To answer the question, a simple programming language with procedures is presented first. The intent is that contracts are expressed on programs written in this programming language. Two contract languages are presented. It is shown how contracts can be formulated in these languages to specify temporal properties of procedures, and how procedures can be verified to satisfy such temporal contracts. The first contract language is limited in terms of its expressivity, but its contracts can be automatically verified. The second language can be used to express more complex properties, but its verification problem turns out to be undecidable. Alternative approaches to its verification problem are discussed., Deduktiv mjukvaruverifikation används för att bevisa korrekthet av program med avseende på kontrakt. Kontrakt uttrycks ofta på procedurer i ett program med användning av Hoare-logik. Sådana kontrakt består av ett förvillkor som specificerar ett villkor som måste gälla innan proceduren exekveras och ett eftervillkor som uttrycker vad som garanteras i gengäld. Ett kontrakt kan ses som en överenskommelse mellan användaren av en procedur och dess utvecklare. Det är viktigt att det på ett skalbart sätt går att verifiera att procedurer i ett program uppfyller deras respektive kontrakt. Skalbarhet kan uppnås genom att se till att verifikationen är procedur-modulär, vilket innebär att varje proceduranrop direkt ersätts med kontraktet som tillhör den anropade proceduren i stället för att proceduranropet utvärderas. Hoare-logikens axiom gör den till en bra grund för procedur-modulära resonemang. Men Hoare-logik är inte välanpassad för att resonera kring en procedurs beteende under en sekvens av tillstånd. Frågorna som ställs är hur ett kontraktspråk för att specificera sådana temporala egenskaper kan utformas samt hur en procedur kan verifieras att uppfylla kontrakt uttryckta i ett sådant kontraktspråk på ett procedur-modulärt sätt. För att besvara frågan presenteras först ett enkelt programmeringsspråk med procedurer. Syftet är att kontrakt uttrycks på program skrivna i detta programspråk. Två kontraktspråk presenteras. Det visas hur kontrakt kan formuleras i dessa språk för att specificera temporala egenskaper av procedurer samt hur procedurer kan verifieras att uppfylla sådana temporala kontrakt. Det första kontraktspråket är begränsat med avseende på dess uttrycksfullhet, men dess kontrakt kan automatiskt verifieras. Det andra språket kan användas för att uttrycka mer komplicerade egenskaper, men dess verifikationsproblem visar sig vara oavgörbart. Alternativa tillvägagångssätt för att hantera dess verifikationsproblem diskuteras.

One of the best compression algorithms to date in terms of compression ratio is PAQ8L. This thesis shows how PAQ8L can be used to predict moves in a four by four variant of tic-tac-toe. We define three agents to benchmark the performance of PAQ8L. The first agent is based on memorization, the second makes random guesses and the third uses PAQ8L to predict moves. The PAQ8L agent outperforms the other two agents in terms of prediction accuracy, but uses significantly more time and memory., En av de bästa kompressionsalgoritmerna idag med hänsyn till kompressionsgrad är PAQ8L. Den här avhandlingen visar hur PAQ8L kan användas för att förutsäga drag i en fyra gånger fyra variant av luffarschack.Vi definierar tre agenter för att utvärdera PAQ8L. Den första agenten är baserad på memorering, den andra gör slumpmässiga gissningar och den tredje använder PAQ8L för att förutsäga drag. Precisionen hos agenten baserad på PAQ8L överträffar precisionen hos de övriga agenterna. Däremot använder den betydligt mer tid och minne.

Probabilistic programming languages (PPLs) make encoding and automatically solving statistical inference problems relatively easy by separating models from the inference algorithm. A popular choice for solving inference problems is to use Monte Carlo inference algorithms. For higher-order functional PPLs, these inference algorithms rely on execution suspension to perform inference, most often enabled through a full continuation-passing style (CPS) transformation. However, standard CPS transformations for PPL compilers introduce significant overhead, a problem the community has generally overlooked. State-of-the-art solutions either perform complete CPS transformations with performance penalties due to unnecessary closure allocations or use efficient, but complex, low-level solutions that are often not available in high-level languages. In contrast to prior work, we develop a new approach that is both efficient and easy to implement using higher-order languages. Specifically, we design a novel static suspension analysis technique that determines the parts of a program that require suspension, given a particular inference algorithm. The analysis result allows selectively CPS transforming the program only where necessary. We formally prove the correctness of the suspension analysis and implement both the suspension analysis and selective CPS transformation in the Miking CorePPL compiler. We evaluate the implementation for a large number of Monte Carlo inference algorithms on real-world models from phylogenetics, epidemiology, and topic modeling. The evaluation results demonstrate significant improvements across all models and inference algorithms., QC 20230227

Probabilistic programming languages (PPLs) make encoding and automatically solving statistical inference problems relatively easy by separating models from the inference algorithm. A popular choice for solving inference problems is to use Monte Carlo inference algorithms. For higher-order functional PPLs, these inference algorithms rely on execution suspension to perform inference, most often enabled through a full continuation-passing style (CPS) transformation. However, standard CPS transformations for PPL compilers introduce significant overhead, a problem the community has generally overlooked. State-of-the-art solutions either perform complete CPS transformations with performance penalties due to unnecessary closure allocations or use efficient, but complex, low-level solutions that are often not available in high-level languages. In contrast to prior work, we develop a new approach that is both efficient and easy to implement using higher-order languages. Specifically, we design a novel static suspension analysis technique that determines the parts of a program that require suspension, given a particular inference algorithm. The analysis result allows selectively CPS transforming the program only where necessary. We formally prove the correctness of the suspension analysis and implement both the suspension analysis and selective CPS transformation in the Miking CorePPL compiler. We evaluate the implementation for a large number of Monte Carlo inference algorithms on real-world models from phylogenetics, epidemiology, and topic modeling. The evaluation results demonstrate significant improvements across all models and inference algorithms., QC 20230227

Probabilistic programming languages (PPLs) make encoding and automatically solving statistical inference problems relatively easy by separating models from the inference algorithm. A popular choice for solving inference problems is to use Monte Carlo inference algorithms. For higher-order functional PPLs, these inference algorithms rely on execution suspension to perform inference, most often enabled through a full continuation-passing style (CPS) transformation. However, standard CPS transformations for PPL compilers introduce significant overhead, a problem the community has generally overlooked. State-of-the-art solutions either perform complete CPS transformations with performance penalties due to unnecessary closure allocations or use efficient, but complex, low-level solutions that are often not available in high-level languages. In contrast to prior work, we develop a new approach that is both efficient and easy to implement using higher-order languages. Specifically, we design a novel static suspension analysis technique that determines the parts of a program that require suspension, given a particular inference algorithm. The analysis result allows selectively CPS transforming the program only where necessary. We formally prove the correctness of the suspension analysis and implement both the suspension analysis and selective CPS transformation in the Miking CorePPL compiler. We evaluate the implementation for a large number of Monte Carlo inference algorithms on real-world models from phylogenetics, epidemiology, and topic modeling. The evaluation results demonstrate significant improvements across all models and inference algorithms., QC 20230227

Probabilistic programming languages (PPLs) make encoding and automatically solving statistical inference problems relatively easy by separating models from the inference algorithm. A popular choice for solving inference problems is to use Monte Carlo inference algorithms. For higher-order functional PPLs, these inference algorithms rely on execution suspension to perform inference, most often enabled through a full continuation-passing style (CPS) transformation. However, standard CPS transformations for PPL compilers introduce significant overhead, a problem the community has generally overlooked. State-of-the-art solutions either perform complete CPS transformations with performance penalties due to unnecessary closure allocations or use efficient, but complex, low-level solutions that are often not available in high-level languages. In contrast to prior work, we develop a new approach that is both efficient and easy to implement using higher-order languages. Specifically, we design a novel static suspension analysis technique that determines the parts of a program that require suspension, given a particular inference algorithm. The analysis result allows selectively CPS transforming the program only where necessary. We formally prove the correctness of the suspension analysis and implement both the suspension analysis and selective CPS transformation in the Miking CorePPL compiler. We evaluate the implementation for a large number of Monte Carlo inference algorithms on real-world models from phylogenetics, epidemiology, and topic modeling. The evaluation results demonstrate significant improvements across all models and inference algorithms., QC 20230227

Probabilistic programming languages (PPLs) make encoding and automatically solving statistical inference problems relatively easy by separating models from the inference algorithm. A popular choice for solving inference problems is to use Monte Carlo inference algorithms. For higher-order functional PPLs, these inference algorithms rely on execution suspension to perform inference, most often enabled through a full continuation-passing style (CPS) transformation. However, standard CPS transformations for PPL compilers introduce significant overhead, a problem the community has generally overlooked. State-of-the-art solutions either perform complete CPS transformations with performance penalties due to unnecessary closure allocations or use efficient, but complex, low-level solutions that are often not available in high-level languages. In contrast to prior work, we develop a new approach that is both efficient and easy to implement using higher-order languages. Specifically, we design a novel static suspension analysis technique that determines the parts of a program that require suspension, given a particular inference algorithm. The analysis result allows selectively CPS transforming the program only where necessary. We formally prove the correctness of the suspension analysis and implement both the suspension analysis and selective CPS transformation in the Miking CorePPL compiler. We evaluate the implementation for a large number of Monte Carlo inference algorithms on real-world models from phylogenetics, epidemiology, and topic modeling. The evaluation results demonstrate significant improvements across all models and inference algorithms., QC 20230227