Decrypting Local Type Inference

Statically typed languages verify programs at compile-time. As a result many programming mistakes are detected at an early stage of development. A programmer does not have to specify types for every single term manually, however. Many programming languages can reconstruct a termâs type using type inference algorithms. While helpful, programmers often find it hard to comprehend the choice of typing decisions that led to the derived type for a term. A particularly serious consequence is that the reporting of type errors yields cryptic messages and misleading program locations. In this thesis we propose a novel approach to explaining type checking decisions by exploring fragments of type derivation trees. Our approach applies to programming languages that use local type inference: typing decisions are made locally and the type information is only propagated between the adjacent AST nodes. We design an algorithm that backtracks through the nodes of type derivation trees in order to discover the typing decisions that introduce the types for the first time during the type inference process. Our algorithm has two properties: - it is type-driven, meaning that we only visit the nodes and their respective typing decisions if they participated in the inference of a type. - it is autonomous, meaning that it does not require any user-input in its operation. These properties allow us to identify the complete and precise set of locations defining the source of a type; previous work mostly focussed on heuristics or used approximations for locating the cause of an error. Our algorithm is not tied to a particular implementation of a type checker: our type derivation trees can be reconstructed from a pre-existing type checker without modifying its internal logic or affecting its regular compilation times. It therefore readily applies to existing programs: we can not only provide improved feedback for them, we also expose limitations of local type inference algorithms and their implementations, without artificially limiting the language features. We implement our type debugging algorithm on top of Scalaâs type checker. Our analysis applies to a range of erroneous scenarios. It provides better error locations than the standard type error reporter of the Scala compiler. This type debugging analysis is just a starting point from which many interesting and useful applications around type debugging can be built: - we implement an interactive type debugger that guides the users through the decisions of local type inference for erroneous and error-free programs alike. - with precise and minimal source code locations we can also offer surgical-level code modifications that fix for example the limitations of local type inference. - we open the door for programmatically defined, application-specific error feedback or corrections. To the best of our knowledge this thesis is the first to address the problem of type errors for programming languages that use local type inference. Current trends suggest that this scheme is gaining in popularity with mainstream languages other than Scala.

Programming language abstractions for mobile code

Stéphane Micheloud

Scala is a general-purpose programming language developed at EPFL. It combines the most important concepts found in object-oriented and functional languages. Scala is a statically typed language; in particular it features an advanced type system and supports local type inference. Furthermore it integrates well with the Java and .net platforms: their libraries are accessible without glue code and the Scala compiler generates code for both execution environments. The Scala programming language has several features that make it desirable as a language for distributed application programming. In particular, it supports first-class functions which are useful in relation with the notions of distributed scope and code mobility. In that context, the missing support for run-time types is one important drawback of the Java run-time environment as a target platform. This thesis focuses on the realisation of a new concept combining essential notions from the functional and distributed programming and implying the extension of the notion of lexical scoping to the distributed context. In short, we claim that the notion of lambda abstraction provides an elegant way for dealing with the dynamic rebinding of local references in a distributed execution environment. The key ideas exposed in this research work have been implemented in our Scala compiler. This helped us to evaluate the used techniques, in particular their impact on the reliability and the performance of distributed programs. So far, most research works related to the present subject have focused on functional programming languages, in particular on the ML language family.

EPFL2009

Compiling scala for the Java virtual machine

Michel Schinz

Scala is a new programming language developed at EPFL and incorporating the most important concepts of object-oriented and functional languages. It aims at integrating well with the Java and .NET platforms: their respective libraries are accessible without glue code, and the compiler can produce programs for both virtual machines. This thesis focuses on the compilation of two important concepts of Scala : mixin inheritance and run time types. The compilation techniques are presented in the context of the Java virtual machine, but could be adapted easily to other similar environments. Mixin inheritance is a relatively recent form of inheritance, offering new capabilities compared to single inheritance, without the complexity of multiple inheritance. We propose two implementation techniques for mixin inheritance: code copying and delegation. The implementation used in the Scala compiler is then presented and justified. Run time types make it possible for a program to examine the type of its values during execution. This possibility is interesting in itself, offering new capabilities to the programmer. Furthermore, run time types are also required to implement other high level concepts, like pattern matching, type-safe serialisation and reflection. We propose an implementation technique based on the representation of types as values, and show how to use the run time types of the underlying virtual machine to implement those of Scala. The techniques presented in this thesis have been implemented in our Scala compiler, scalac. This enabled us to evaluate these techniques, in particular their impact on the performances of programs. This evaluation was performed on several real, non-trivial programs.

EPFL2005

Learning continuous-time working memory tasks with on-policy neural reinforcement learning

Davide Zambrano

An animals' ability to learn how to make decisions based on sensory evidence is often well described by Reinforcement Learning (RL) frameworks. These frameworks, however, typically apply to event-based representations and lack the explicit and fine-grained notion of time needed to study psychophysically relevant measures like reaction times and psychometric curves. Here, we develop and use a biologically plausible continuous-time RL scheme of CT-AuGMEnT (Continuous-Time Attention-Gated MEmory Tagging) to study these behavioural quantities. We show how CT-AuGMEnT implements on-policy SARSA learning as a biologically plausible form of reinforcement learning with working memory units using 'attentional' feedback. We show that the CT-AuGMEnT model efficiently learns tasks in continuous time and can learn to accumulate relevant evidence through time. This allows the model to link task difficulty to psychophysical measurements such as accuracy and reaction-times. We further show how the implementation of a separate accessory network for feedback allows the model to learn continuously, also in case of significant transmission delays between the network's feedforward and feedback layers and even when the accessory network is randomly initialized. Our results demonstrate that CTAuGMEnT represents a fully time-continuous biologically plausible end-to-end RL model for learning to integrate evidence and make decisions. (c) 2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

2021