3,956 Works

Capability Hardware Enhanced RISC Instructions: CHERI Instruction-Set Architecture (Version 6)

Robert N. M. Watson, Peter G. Neumann, Jonathan Woodruff, Michael Roe, Jonathan Anderson, John Baldwin, David Chisnall, Brooks Davis, Alexandre Joannou, Ben Laurie, Simon W. Moore, Steven J. Murdoch, Robert Norton, Stacey Son & Hongyan Xia
This technical report describes CHERI ISAv6, the sixth version of the Capability Hardware Enhanced RISC Instructions (CHERI) Instruction-Set Architecture (ISA) being developed by SRI International and the University of Cambridge. This design captures seven years of research, development, experimentation, refinement, formal analysis, and validation through hardware and software implementation. CHERI ISAv6 is a substantial enhancement to prior ISA versions: it introduces support for kernel-mode compartmentalization, jump-based rather than exception-based domain transition, architecture-abstracted and efficient tag...

Hierarchical statistical semantic translation and realization

Matic Horvat
Statistical machine translation (SMT) approaches extract translation knowledge automatically from parallel corpora. They additionally take advantage of monolingual text for target-side language modelling. Syntax-based SMT approaches also incorporate knowledge of source and/or target syntax by taking advantage of monolingual grammars induced from treebanks, and semantics-based SMT approaches use knowledge of source and/or target semantics in various forms. However, there has been very little research on incorporating the considerable monolingual knowledge encoded in deep, hand-built grammars...

Formal verification-driven parallelisation synthesis

Matko Botinčan
Concurrency is often an optimisation, rather than intrinsic to the functional behaviour of a program, i.e., a concurrent program is often intended to achieve the same effect of a simpler sequential counterpart, just faster. Error-free concurrent programming remains a tricky problem, beyond the capabilities of most programmers. Consequently, an attractive alternative to manually developing a concurrent program is to automatically synthesise one. This dissertation presents two novel formal verification-based methods for safely transforming a sequential...

Characterizing the impact of network latency on cloud-based applications’ performance

Diana Andreea Popescu, Noa Zilberman & Andrew W. Moore
Businesses and individuals run increasing numbers of applications in the cloud. The performance of an application running in the cloud depends on the data center conditions and upon the resources committed to an application. Small network delays may lead to a significant performance degradation, which affects both the user’s cost and the service provider’s resource usage, power consumption and data center efficiency. In this work, we quantify the effect of network latency on several typical...

Proofs for ‘Verifying Spatial Properties of Array Computations’

Dominic Orchard, Mistral Contrastin, Matthew Danish & Andrew Rice
This technical report provides accompanying proofs for the paper: Verifying Spatial Properties of Array Computations. We show three properties of the lattice model of the stencil specification language. 1) that it is sound with respect to the equational theory of region specifications; 2) that is it sound with respect to the theory of region approximation; 3) that the inference algorithm is sound. We further derive useful identities on the specification language and properties of Union...

Proceedings of the 2017 Scheme and Functional Programming Workshop

Nada Amin & François-René Rideau
This report aggregates the papers presented at the eigtheenth annual Scheme and Functional Programming Workshop, hosted on September 3rd, 2017 in Oxford, UK and co-located with the twenty-second International Conference on Functional Programming. The Scheme and Functional Programming Workshop is held every year to provide an opportunity for researchers and practitioners using Scheme and related functional programming languages like Racket, Clojure, and Lisp, to share research findings and discuss the future of the Scheme programming...

Resource allocation and job scheduling

Philip Hazel
The mechanisms for sharing the resources of the Cambridge IBM 370/165 computer system among many individual users are described. File store is treated separately from other resources such as central processor and channel time. In both cases, flexible systems that provide incentives to thrifty behaviour are used. The method of allocating resources directly to users rather than in a hierarchical manner via faculties and departments is described, and its social acceptability is discussed.

Reliable storage in a local network

Jeremy Dion
A recent development in computer science has been the advent of local computer networks, collections of autonomous computers in a small geographical area connected by a high-speed communications medium. In such a situation it is natural to specialise some of the computers to provide useful services to others in the network. These server machines can be economically advantageous if they provide shared access to expensive mechanical devices such as discs. This thesis discusses the problems...

Analysis and inference for English

Arthur William Sebright Cater

The Dialectica categories

Valeria Correa Vaz de Paiva
This work consists of two main parts. The first one, which gives it its name, presents an internal categorical version of Gödel’s “Dialectica interpretation” of higher-order arithmetic. The idea is to analyse the Dialectica interpretation using a cetegory DC where objects are relations on objects of a basic category C and maps are pairs of maps of C satisfying a pullback condition. If C is finitely complete, DC exists and has a very natural symmetric...

Formalizing abstraction mechanisms for hardware verification in higher order logic

Thomas Frederick Melham
Recent advances in microelectronics have given designers of digital hardware the potential to build devices of remarkable size and complexity. Along with this however, it becomes increasingly difficult to ensure that such systems are free from design errors, where complete simulation of even moderately sized circuits is impossible. One solution to these problems is that of hardware verification, where the functional behaviour of the hardware is described mathematically and formal proof is used to show...

Higher-order unification, polymorphism, and subsorts

Tobias Nipkow
This paper analyses the problems that arise in extending Huet’s higher-order unification algorithm from the simply typed λ-calculus to one with type variables. A simple, incomplete, but in practice very useful extension to Huet’s algorithm is discussed. This extension takes an abstract view of types. As a particular instance we explore a type system with ML-style polymorphism enriched with a notion of sorts. Sorts are partially ordered and classify types, thus giving rise to an...

Type classes and overloading resolution via order-sorted unification

Tobias Nipkow & Gregor Snelting
We present a type inference algorithm for a haskell-like language based on order-sorted unification. The language features polymorphism, overloading, type classes and multiple inheritance. Class and instance declarations give rise to an order-sorted algebra of types. Type inference esentially reduces to the Hindley/Milner algorithm where unification takes place in this order-sorted algebra of types. The theory of order-sorted unification provides simple sufficient conditions which ensure the existence of principal types. The semantics of the language...

Subtyping in Ponder
(preliminary report)

Valeria C.V. de Paiva
This note starts the formal study of the type system of the functional language Ponder. Some of the problems of proving soundness and completeness are discussed and some preliminary results, about fragments of the type system, shown. It consists of 6 sections. In section 1 we review briefly Ponder’s syntax and describe its typing system. In section 2 we consider a very restricted fragment of the language for which we can prove soundness of the...

The theory and implementation of a bidirectional question answering system

John M. Levine & Lee Fedder
This paper describes a question answering system which is a limited instance of the general bidirectional architecture suggested by Appelt (1987), The novel features of our approach include the use of a linguistically well-motivated set of functional features; a bidirectional grammar which encodes these features directly; a question answering program which uses the thematic organisation of the user’s input to construct a cooperative reply; and a tactical generation component which can be used with Montague...

Categorical combinators for the calculus of constructions

Eike Ritter

The formal verification of the Fairisle ATM switching element

Paul Curzon

A method of program refinement

Jim Grundy
A method of specifying the desired behaviour of a computer program, and of refining such specifications into imperative programs is proposed. The refinement method has been designed with the intention of being amenable to tool support, and of being applicable to real-world refinement problems. Part of the refinement method proposed involves the use of a style of transformational reasoning called ‘window inference’. Window inference is particularly powerful because it allows the information inherent in the...

What is a categorical model of intuitionistic linear logic?

G.M. Bierman

Representing higher-order logic proofs in HOL

J. von Wright

Word sense selection in texts: an integrated model

Oi Yee Kwong
Early systems for word sense disambiguation (WSD) often depended on individual tailor-made lexical resources, hand-coded with as much lexical information as needed, but of severely limited vocabulary size. Recent studies tend to extract lexical information from a variety of existing resources (e.g. machine-readable dictionaries, corpora) for broad coverage. However, this raises the issue of how to combine the information from different resources. Thus while different types of resource could make different contribution to WSD, studies...

The UDP calculus:
rigorous semantics for real networking

Andrei Serjantov, Peter Sewell & Keith Wansbrough
Network programming is notoriously hard to understand: one has to deal with a variety of protocols (IP, ICMP, UDP, TCP, etc.), concurrency, packet loss, host failure, timeouts, the complex sockets interface to the protocols, and subtle protability issues. Moreover, the behavioural properties of operating systems and the network are not well documented. A few of these issues have been addressed in the process calculus and distributed algorithm communities, but there remains a wide gulf between...

Mechanizing a theory of program composition for UNITY

Lawrence Paulson
Compositional reasoning must be better understood if non-trivial concurrent programs are to be verified. Chandy and Sanders [2000] have proposed a new approach to reasoning about composition, which Charpentier and Chandy [1999] have illustrated by developing a large example in the UNITY formalism. The present paper describes extensive experiments on mechanizing the compositionality theory and the example, using the proof tool Isabelle. Broader issues are discussed, in particular, the formalization of program states. The usual...

Dynamic provisioning of resource-assured and programmable virtual private networks

Rebecca Isaacs
Virtual Private Networks (VPNs) provide dedicated connectivity to a closed group of users on a shared network. VPNs have traditionally been deployed for reasons of economy of scale, but have either been statically defined, requiring manual configuration, or else unable to offer any quality of service (QoS) guarantees. This dissertation describes VServ, a service offering dynamic and resource-assured VPNs that can be acquired and modified on demand. In VServ, a VPN is both a subset...

Sequential program composition in UNITY

Tanja Vos & Doaitse Swierstra

Registration Year

  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015

Resource Types

  • Report


  • Open Society Foundations
  • University of Virginia
  • University of Technology of Compiègne
  • Bonn-Rhein-Sieg University of Applied Sciences
  • University of Kentucky
  • Western Sydney University
  • King's College London
  • Lyrasis
  • Institut National de la Recherche Agronomique
  • University of Strathclyde