SPLASH 2020
Sun 15 - Sat 21 November 2020 Online Conference
Wed 18 Nov 2020 15:00 - 15:20 at SPLASH-IV - Design Chair(s): Luke Church

Any algorithmic problem faced by application programmers in the wild can in principle be solved using a Turing incomplete programming language. [Rice 1953] suggests that Turing completeness bears a heavy price, fundamentally limiting the ability of automatic assistants to help programmers be more productive, create less bugs and write safer software. Nevertheless, no widespread programming language is Turing incomplete. While there are some strongly-normalizing dependently typed languages, they require in-depth academic knowledge and currently lack affordances for practical application development. We contend that the pervasive choice of Turing completeness across programming languages has been driven by ill-placed expediency rather than necessity. In particular, loops and recursion are common ”Turing-traps”: Sources of Turing completeness, whether accidental or intentional. We present an approach to eliminating Turing-traps during the language design process, with several examples suitable for non-academic languages. Designers of modern practical programming languages should strongly consider evading Turing completeness and enabling better verification, security, automated testing and distributed computing.

Wed 18 Nov

Displayed time zone: Central Time (US & Canada) change

15:00 - 16:20
DesignHATRA at SPLASH-IV
Chair(s): Luke Church University of Cambridge
15:00
20m
Talk
Programming languages shouldn't and needn't be Turing complete
HATRA
Pre-print
15:20
20m
Talk
User-Centered Programming Language Design: A Course-Based Case Study
HATRA
Michael Coblenz University of Maryland at College Park, Ariel Davis Carnegie Mellon University, Megan Hofmann Carnegie Mellon University, Vivian Huang Carnegie Mellon University, Siyue Jin Carnegie Mellon University, Max Krieger , Kyle Liang Carnegie Mellon University, Brian Wei Carnegie Mellon University, Mengchen Sam Yong Carnegie Mellon University, Jonathan Aldrich Carnegie Mellon University
Link to publication
15:40
20m
Meeting
Day 1 Discussion
HATRA