Beyond Polarity: Towards A Multi-Discipline Intermediate Language with Sharing

Add to your list(s) Download to your calendar using vCal

• Paul Downen, University of Oregon
• Tuesday 11 September 2018, 14:00-15:00
• FW26.

If you have a question about this talk, please contact Victor Gomes.

Finding a universal intermediate language suitable for compiling and optimizing both strict and lazy functional programs has been a long-sought holy grail for compiler writers. There have been several distinct approaches to designing a core language that’s expressive enough to do the job, including continuation-passing style (CPS), monadic, and adjunctive languages. Each of these three styles gives the program explicit control over evaluation order. In the most extreme case, adjunctive languages, in the form of either call-by-push-value or polarity, contain both call-by-value and call-by-name fragments. This split creates a hybrid language which can faithfully represent complex types of program structures in terms of simple parts.

However, the polarized dichotomy between call-by-value and call-by-name programs is, by definition, binary and leaves out any other possibility. For example, in practice lazy functional languages are implemented efficiently using a third option, call-by-need evaluation, which shares the work done while executing a program so that answers do not need to be recomputed more than once. This talk will discuss how to go beyond the binary polarity to include three (or more) basic evaluation mechanisms, called disciplines. Multi-discipline evaluation enriches adjunctive languages with an explicit notion of sharing in order to serve as a practical core language for both strict and lazy functional programs.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• FW26
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.