The proof assistant Lean has support for abstract polynomials, but this is not necessarily the same as support for computations with polynomials. Lean is also a functional programming language, so it should be possibl...
详细信息
By boosting computer processing capability, quantum computing will transform digital usage in the upcoming years. The development of the quantum computer and the advancement to the several thousand Qubits involved in ...
详细信息
Many programs which solve complicated problems can be seen as inversions of other, much simpler, programs. One particular example is transforming verifiers into solvers, which can be achieved with low effort by implem...
详细信息
When working in optimisation or privacy protection, one may need to estimate the sensitivity of computer programs, i.e., the maximum multiplicative increase in the distance between two inputs and the corresponding two...
详细信息
Typical hardware description languages, such as Verilog and VHDL, are low-level declarative languages with little room for flexibility. Extending, verifying, or reinterpreting programs in these languages is typically ...
详细信息
ISBN:
(纸本)9798400700439
Typical hardware description languages, such as Verilog and VHDL, are low-level declarative languages with little room for flexibility. Extending, verifying, or reinterpreting programs in these languages is typically done with external tools and at great cost. This paper presents an implementation of a relational hardware description language, Ruby, in the programming language and proof assistant Agda. Using our system, an engineer can easily write, compile, simulate, and verify new designs. The language is modular, allowing for new constructs and libraries to be added easily, and supports formal reasoning about circuit transformations. Symbolic simulation and compilation to a netlist format are also provided. We demonstrate our tool by designing, compiling, and simulating a priority queue design, and showcase how equational reasoning can be used to prove properties of circuits.
We present a hardware implementation of the high-level multi-paradigm language OCAML using a declarative language called Eclat. Eclat is tailored for programming reactive hardware applications mixing interaction with ...
详细信息
ISBN:
(纸本)9783031520372;9783031520389
We present a hardware implementation of the high-level multi-paradigm language OCAML using a declarative language called Eclat. Eclat is tailored for programming reactive hardware applications mixing interaction with physical devices and long-running computations. It is compiled to synthesizable hardware descriptions for configuring Field Programmable Gate Arrays (FPGAs). We have implemented the OCAML Virtual Machine as an Eclat function to execute complex computations (programmed in OCAML) in reactive applications (programmed in Eclat). This implementation comprises a bytecode interpreter and a runtime system with automatic memory management. The OCAML programmers can customize this runtime by defining external Eclat functions, i.e., hardware accelerators.
Adjoint logic is a general approach to combining multiple logics with different structural properties, including linear, affine, strict, and (ordinary) intuitionistic logics, where each proposition has an intrinsic mo...
详细信息
Synthetic Separation Logic (SSL) is a formalism that powers SuSLik, the state-of-the-art approach for the deductive synthesis of provably-correct programs in C-like languages that manipulate heap-based linked data str...
详细信息
This paper presents stableKanren, a miniKanren extension with normal logic programming support under stable model semantics. MiniKanren is a relational programming solver implemented atop Scheme via shallow embedding,...
详细信息
ISBN:
(纸本)9798400708121
This paper presents stableKanren, a miniKanren extension with normal logic programming support under stable model semantics. MiniKanren is a relational programming solver implemented atop Scheme via shallow embedding, which means the predicate in each rule is encoded as a goal function directly. The solver utilizes the pattern matching macro in Scheme to transform the input goal function and form a static search stream through continuations to achieve the essential features, resolution and unification, in Prolog. However, the static stream only works on monotonic reasoning. Even though the core miniKanren is designed to be easily modified and extended with new features, none of the existing extensions support solving normal logic programs. Also, no normal logic program solvers are based on a functional programming language. We identify and categorize the roles of resolution and unification in top-down solving. And we realize that a dynamic search stream is needed to support non-monotonic reasoning. So we evolve both resolution and unification with new roles, and we exploit the advantages of using macros and continuations further to weave the information generated during runtime into future streams dynamically. We create multiple innovative macros to compile the normal logic program into a program with its complement form, obtain the domain of a variable under different contexts, and generate the new search stream during solving. And we use the coinductive resolution to handle the loop in the normal logic program. In future work, we plan to apply bottom-up optimization to improve our top-down system performance and support various input rules.
BSML is a pure functional library for the multi-paradigm language OCaml. BSML embodies the principles of the Bulk Synchronous Parallel (BSP) model, a model of scalable parallel computing. We propose a formalization of...
详细信息
ISBN:
(纸本)9783031471148;9783031471155
BSML is a pure functional library for the multi-paradigm language OCaml. BSML embodies the principles of the Bulk Synchronous Parallel (BSP) model, a model of scalable parallel computing. We propose a formalization of BSML primitives with WhyML, the specification language of Why3 and specify and prove the correctness of most of the BSML standard library. Finally, we develop and verify the correctness of a small BSML application.
暂无评论