Reading list

 

Kevin Doran wrote to me requesting a reading list on logic. He recommends an introductory guide to logic by Peter Smith. Smith's appendix lists several textbooks on logic, but misses my two favourites.

• Jean-Yves Girard, Yves Lafont, and Paul Taylor. Proofs and Types. CUP, 1989. The master logician (discoverer of System F and linear logic), aided by two superb computer scientists, covers the basics. Explains additive and multiplicative proof rules, and the fundamentals of propositions as types.
  
• Jean van Heijenoort, From Frege to Gödel A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, 1967. My favourite entry is the correspondence between Russell and Frege---it is only a few pages long and so a quick read; don't skip van Heijenoort's introduction. See also Anita Feferman's biography of van Heijenoort, who lived quite a life: he served as Trotsky's secretary and was shot to death by a jealous lover.
  
  

PhD position in Certifying Compilation of Smart Contracts

Wouter Swierstra at Utrecht and my IOHK colleague Manuel Chakravarty are looking for someone to undertake a PhD to build a certifying compiler for our smart contract language, Plutus.

This project aims to develop a certifying compiler for Plutus Tx, a subset of the purely functional language Haskell that is used to implement smart contracts for the Cardano blockchain. The Plutus smart contract framework is being developed by IOHK for Cardano and the present project is a joint effort of IOHK and Utrecht University. The Plutus Tx compiler is based on the GHC Haskell compiler and adds a translation step from GHC Core to a minimal lambda calculus. Programmes in this lambda calculus are executed during transaction validation in a sandboxed execution environment in a manner that is crucial to the security of the blockchain. The aim of this project is to formalise the semantics of the languages involved in a proof assistant such as Coq, to reason about the transformation and optimisation steps that the compiler performs, and finally, to generate a proof object certifying the correctness of the generated code together with that code.

Programming Languages for Trustworthy Systems

The University of Edinburgh seeks to appoint a Lecturer/Senior Lecturer/Reader in Programming Languages for Trustworthy Systems.  An ideal candidate will be able to contribute and complement the expertise of the Programming Languages & Foundations Group which is part of the Laboratory for Foundations of Computer Science (LFCS).

The successful candidate will have a PhD, an established research agenda and the enthusiasm and ability to undertake original research, to lead a research group, and to engage with teaching and academic supervision, with expertise in at least one of the following:

• Practical systems verification: e.g. for operating systems, databases, compilers, distributed systems
• Language-based verification: static analysis, verified systems / smart contract programming, types, SAT/SMT solving
• Engineering trustworthy software: automated/property-based testing, bug finding, dynamic instrumentation, runtime verification

We are seeking current and future leaders in the field.

Applications from individuals from underrepresented groups in Computer Science are encouraged.

Appointment will be full-time and open-ended.

The post is situated in the Laboratory for Foundations of Computer Science, the Institute in which the School's expertise in functional programming, logic and semantics, and theoretical computer science is concentrated.  Collaboration relating to PL across the School is encouraged and supported by the School's Programming Languages Research Programme, to which the successful applicant will be encouraged to contribute. Applicants whose PL-related research aligns well with particular strengths of the School, such as machine learning, AI, robotics, compilers, systems, and security, are encouraged to apply and highlight these areas of alignment.  

All applications must contain the following supporting documents:

• Teaching statement outlining teaching philosophy, interests and plans

• Research statement outlining the candidate’s research vision and future plans

• Full CV (resume) and publication list

The University job posting and submission site, including detailed application instructions, is at this link:

https://www.vacancies.ed.ac.uk/pls/corehrrecruit/erq_jobspec_version_4.jobspec?p_id=050700

Applications close at 5pm GMT on January 31, 2020. This deadline is firm, so applicants are exhorted to begin their applications in advance.

Shortlisting for this post is due early February with interview dates for this post expected to fall in early April 2020. Feedback will only be provided to interviewed candidates. References will be sought for all shortlisted candidates. Please indicate on your application form if you are happy for your referees to be contacted.

Informal enquiries may be addressed to Prof Philip Wadler (wadler@inf.ed.ac.uk).

Lecturer Grade: UE08 (£41,526 - £49,553) 

Senior Lecturer or Reader Grade: UE09 (£52,559 - £59,135)

The School is advertising a number of positions, including this one, as described here:

https://www.ed.ac.uk/informatics/about/work-with-us/vacancies/academic-recruitment

About the Laboratory for Foundations of Computer Science

As one of the largest Institutes in the School of Informatics, and one of the largest theory research groups in the world, the Laboratory for Foundations of Computer Science combines expertise in all aspects of theoretical computer science, including algorithms and complexity, cryptography, database theory, logic and semantics, and quantum computing. The Programming Languages and Foundations group includes over 25 students, researchers and academic staff, working on functional programming, types, verification, semantics, software engineering, language-based security and new programming models. Past contributions to programming languages research originating at LFCS include Standard ML, the Edinburgh Logical Framework, models of concurrency such as the pi-calculus, and foundational semantic models of effects in programming languages, based on monads and more recently algebraic effects and handlers.

About the School of Informatics and University of Edinburgh

The School of Informatics at the University of Edinburgh is one of the largest in Europe, with more than 120 academic staff and a total of over 500 post-doctoral researchers, research students and support staff. Informatics at Edinburgh rated highest on Research Power in the most recent Research Excellence Framework. The School has strong links with industry, with dedicated business incubator space and well-established enterprise and business development programmes. The School of Informatics has recently established the Bayes Centre for Data Technology, which provide a locus for fruitful multi-disciplinary work, including a range of companies collocated in it. The School holds a Silver Athena SWAN award in recognition of our commitment to advance the representation of women in science, mathematics, engineering and technology. We are also Stonewall Scotland Diversity Champions actively promoting LGBT equality.

How Amazon Web Services Uses Formal Methods

How Amazon Web Services Uses Formal Methods by Newcombe et al, appeared in Communications of the ACM in April 2015. It describes the use of Leslie Lamport's TLA+ (Temporal Logic of Actions) to refine the design of web services such as Dynamo DB and S3. (S3 stored 2 billion objects and handled 1.1 million transaction per second back in 2013.) Thanks to Jessica Kerr for pointing me to this paper after an interview for the podcast Greater Than Code.

We find a major benefit of having a precise, testable model of the core system is that we can quickly verify that even deep changes are safe or learn they are unsafe without doing harm. In several cases, we have prevented subtle but serious bugs from reaching production. In other cases we have been able to make innovative performance optimizations (such as removing or narrowing locks or weakening constraints on message ordering) we would not have dared to do without having model-checked those changes. A precise, testable description of a system becomes a what-if tool for designs, analogous to how spreadsheets are a what-if tool for financial models. We find that using such a tool to explore the behavior of the system can improve the designer’s understanding of the system.