Magnus Madsen

I am an assistant professor at the Department of Computer Science at Aarhus University. I was previously assistant professor at Aalborg University. Before that, I was a postdoctoral researcher at the University of Waterloo in the Programming Languages Group under the supervision of Ondřej Lhoták. I received my PhD from Aarhus University for the thesis Static Analysis of Dynamic Languages. My thesis adviser was Anders Møller.

My full curriculum vitae (typically outdated). My Google Scholar. My DBLP. My GitHub.

My email is my first name at cs.aau.dk.

My primary research interests are in programming language design, compilers, and program analysis.

Research Projects

The Flix Language and Compiler

Flix is a statically typed functional- and logic programming language inspired by Scala, OCaml, F#, Haskell, and Datalog. The syntax of Flix resembles Scala and Datalog. The type system supports local type inference and is based on Hindley-Milner. Flix runs on the Java Virtual Machine and compiles directly to JVM bytecode.

Flix supports hybrid functional and logic programming featuring a built-in fixed point engine based on semi-naive evaluation. The functional and logic languages can be used independently, if so desired. For example, a Flix program can be purely functional, or Flix can be used as a standalone Datalog engine.

Papers related to this line of research include:

Peer-Reviewed Publications

  • Implicit Parameters for Logic Programming (PPDP '18)

    Magnus Madsen, Ondřej Lhoták

    Implicit parameters allow programmers to omit certain arguments from function calls and have them automatically inferred by the compiler based on their types. At every call site, the compiler determines the values of the implicit parameters based on their declared types and the bindings currently in implicit scope. The programmer controls this mechanism in two ways: by adding bindings to the implicit scope, or by explicitly providing the implicit parameters for the function call

    Implicit parameters are known from functional and object- oriented languages such as Haskell and Scala. In recent years, more languages have added support for implicit parameters, including Agda, Coq, and Idris. Implicit parameters have played an impressive role as the foundation for a broad range of language features such as type classes, capability and effect systems, software transactional memory, macros, and more.

    In this paper, we propose a design of implicit parameters for typed Horn clause based logic programming languages, such as Datalog and Prolog. We illustrate the usefulness of implicit parameters and show how they support logic programming in the large. We explore some of the differences that arise between implicit parameters in functional languages and in logic languages.

    Paper BibTex
  • Safe and Sound Program Analysis with Flix (ISSTA '18)

    Magnus Madsen, Ondřej Lhoták

    Program development tools such as bug finders, build automation tools, compilers, debuggers, integrated development environments, and refactoring tools increasingly rely on static analysis techniques to reason about program behavior. Implementing such static analysis tools is a complex and difficult task with concerns about safety and soundness. Safety guarantees that the fixed point computation – inherent in most static analyses – converges and ultimately terminates with a deterministic result. Soundness guarantees that the computed result over-approximates the concrete behavior of the program under analysis. But how do we know if we can trust the result of the static analysis itself? Who will guard the guards?

    In this paper, we propose the use of automatic program verification techniques based on symbolic execution and SMT solvers to verify the correctness of the abstract domains used in static analysis tools. We implement a verification toolchain for Flix, a functional and logic programming language tailored for the implementation of static analyses. We apply this toolchain to several abstract domains. The experimental results show that we are able to prove 99.5% and 96.3% of the required safety and soundness properties, respectively.

    Paper BibTex
  • Tail Call Elimination and Data Representation for Functional Languages on the Java Virtual Machine (CC '18)

    Magnus Madsen, Ramin Zarifi, Ondřej Lhoták

    The Java Virtual Machine (JVM) offers an attractive runtime environment for programming language implementors. The JVM has a simple bytecode format, excellent performance, multiple state-of-the art garbage collectors, robust backwards compatibility, and it runs on almost all platforms. Further, the Java ecosystem grants access to a plethora of libraries and tooling, including debuggers and profilers.

    Yet, the JVM was originally designed for Java, and its representation of code and data may cause difficulties for other languages. In this paper, we discuss how to efficiently implement functional languages on the JVM. We focus on two overall challenges: (a) how to efficiently represent algebraic data types in the presence of tags and tuples, option types, newtypes, and parametric polymorphism, and (b) how to support full tail call elimination on the JVM.

    We present two technical contributions: A fused representation of tags and tuples and a full tail call elimination strategy that is thread-safe. We implement these techniques in the Flix language and evaluate their performance.

    Paper BibTex
  • A Model for Reasoning About JavaScript Promises (OOPSLA '17)

    Magnus Madsen, Ondřej Lhoták, Frank Tip

    In JavaScript programs, asynchrony arises in situations such as web-based user-interfaces, communicating with servers through HTTP requests, and non-blocking I/O. Event-based programming is the most popular approach for managing asynchrony, but suffers from problems such as lost events and event races, and results in code that is hard to understand and debug. Recently, ECMAScript 6 has added support for promises, an alternative mechanism for managing asynchrony that enables programmers to chain asynchronous computations while supporting proper error handling. However, promises are complex and error-prone in their own right, so programmers would benefit from techniques that can reason about the correctness of promise-based code.

    Since the ECMAScript 6 specification is informal and intended for implementers of JavaScript engines, it does not provide a suitable basis for formal reasoning. This paper presents lambda_p, a core calculus that captures the essence of ECMAScript 6 promises. Based on lambda_p, we introduce the promise graph, a program representation that can assist programmers with debugging of promise-based code. We then report on a case study in which we investigate how the promise graph can be helpful for debugging errors related to promises in code fragments posted to the StackOverflow website.

    Paper BibTex
  • From Datalog to Flix: A Declarative Language for Fixed Points on Lattices (PLDI '16)

    Magnus Madsen, Ming-Ho Yee, Ondřej Lhoták

    We present Flix, a declarative programming language for specifying and solving least fixed point problems, particularly static program analyses. Flix is inspired by Datalog and extends it with lattices and monotone functions. Using Flix, implementors of static analyses can express a broader range of analyses than is currently possible in pure Datalog, while retaining its familiar rule-based syntax.

    We define a model-theoretic semantics of Flix asa natural extension of the Datalog semantics. This semantics captures the declarative meaning of Flix programs without imposing any specific evaluation strategy. An efficient strategy is semi-naive evaluation which we adapt for Flix. We have implemented a compiler and runtime for Flix, and used it to express several well-known static analyses, including the IFDS and IDE algorithms. The declarative nature of Flix clearly exposes the similarity between these two algorithms.

    Paper BibTex Website
  • Feedback-Directed Instrumentation for Deployed JavaScript Applications (ICSE '16)

    Magnus Madsen, Frank Tip, Esben Andreasen, Koushik Sen, Anders Møller

    Many bugs in JavaScript applications manifest themselves as objects that have incorrect property values when a failure occurs. For this type of error, stack traces and log files are often insufficient for diagnosing problems. In such cases, it is helpful for developers to know the control flow path from the creation of an object to a crashing statement. Such crash paths are useful for understanding where the object originated and whether any properties of the object were corrupted since its creation.

    We present a feedback-directed instrumentation technique for computing crash paths that allows the instrumentation overhead to be distributed over a crowd of users and to reduce it for users who do not encounter the crash. We implemented our technique in a tool, Crowdie, and evaluated it on 10 real-world issues for which error messages and stack traces are insufficient to isolate the problem. Our results show that feedback-directed instrumentation requires 5% to 25% of the program to be instrumented, that the same crash must be observed 3 to 10 times to discover the crash path, and that feedback-directed instrumentation typically slows down execution by a factor 2x–9x compared to 8x–90x for an approach where applications are fully instrumented.

    Paper BibTex
  • Static Analysis of Event-Driven Node.js JavaScript Applications (OOPSLA '15)

    Magnus Madsen, Frank Tip, Ondřej Lhoták

    Many JavaScript programs are written in an event-driven style. In particular, in server-side Node.js applications, operations involving sockets, streams, and files are typically performed in an asynchronous manner, where the execution of listeners is triggered by events. Several types of programming errors are specific to such event-based programs (e.g., unhandled events, and listeners that are registered too late). We present the event-based call graph, a program representation that can be used to detect bugs related to event handling. We have designed and implemented three analyses for constructing event-based call graphs. Our results show that these analyses are capable of detecting problems reported on StackOverflow. Moreover, we show that the number of false positives reported by the analysis on a suite of small Node.js applications is manageable.

    Paper BibTex
  • Sparse Dataflow Analysis with Pointers and Reachability (SAS '14)

    Magnus Madsen, Anders Møller

    Many static analyzers exploit sparseness techniques to reduce the amount of information being propagated and stored during analysis. Although several variations are described in the literature, no existing technique is suitable for analyzing JavaScript code. In this paper, we point out the need for a sparse analysis framework that supports pointers and reachability. We present such a framework, which uses static single assignment form for heap addresses and computes def-use information on-the-fly. We also show that essential information about dominating definitions can be maintained efficiently using quadtrees. The framework is presented as a systematic modification of a traditional dataflow analysis algorithm.

    Our experimental results demonstrate the effectiveness of the technique for a suite of JavaScript programs. By also comparing the performance with an idealized staged approach that computes pointer information with a pre-analysis, we show that the cost of computing def-use information on-the-fly is remarkably small.

    Paper BibTex
  • String Analysis for Dynamic Field Access (CC '14)

    Magnus Madsen, Esben Andreasen

    In JavaScript, and scripting languages in general, dynamic field access is a commonly used feature. Unfortunately, current static analysis tools either completely ignore dynamic field access or use overly conservative approximations that lead to poor precision and scalability. We present new string domains to reason about dynamic field access in a static analysis tool. A key feature of the domains is that the equal, concatenate and join operations take O(1) time.

    Experimental evaluation on four common JavaScript libraries, including jQuery and Prototype, shows that traditional string domains are insufficient. For instance, the commonly used constant string domain can only ensure that at most 21% dynamic field accesses are without false positives. In contrast, our string domain H ensures no false positives for up to 90% of all dynamic field accesses.

    We demonstrate that a dataflow analysis equipped with the H domain gains significant precision resulting in an analysis speedup of more than 1.5x for 7 out of 10 benchmark programs.

    Paper BibTex
  • Practical Static Analysis of JavaScript Applications in the Presence of Frameworks and Libraries (FSE/ESEC '13)

    Magnus Madsen, Benjamin Livshits, Michael Fanning

    JavaScript is a language that is widely-used for both web- based and standalone applications such as those in the Windows 8 operating system. Analysis of JavaScript has long been known to be challenging due to the language’s dynamic nature. On top of that, most JavaScript applications rely on large and complex libraries and frameworks, often written in a combination of JavaScript and native code such as C and C++. Stubs have been commonly employed as a partial specification mechanism to address the library problem; alas, they are tedious and error-prone.

    However, the manner in which library code is used within applications often sheds light on what library APIs return or pass into callbacks declared within the application. In this paper, we propose a technique which combines pointer analysis with a novel use analysis to handle many challenges posed by large JavaScript libraries. Our techniques have been implemented and empirically validated on a set of 25 Windows 8 JavaScript applications, averaging 1,587 lines of code, together with about 30,000 lines of library code, demonstrating a combination of scalability and precision

    Paper BibTex
  • Modeling the HTML DOM and Browser API in Static Analysis of JavaScript Web Applications (FSE/ESEC '11)

    Simon Holm Jensen, Magnus Madsen, Anders Møller

    Developers of JavaScript web applications have little tool support for catching errors early in development. In comparison, an abundance of tools exist for statically typed languages, including sophisticated integrated development environments and specialized static analyses. Transferring such technologies to the domain of JavaScript web applications is challenging. In this paper, we discuss the challenges, which include the dynamic aspects of JavaScript and the complex interactions between JavaScript, HTML, and the browser. From this, we present the first static analysis that is capable of reasoning about the flow of control and data in modern JavaScript applications that interact with the HTML DOM and browser API.

    One application of such a static analysis is to detect type- related and dataflow-related programming errors. We report on experiments with a range of modern web applications, including Chrome Experiments and IE Test Drive applications, to measure the precision and performance of the technique. The experiments indicate that the analysis is able to show absence of errors related to missing object properties and to identify dead and unreachable code. By measuring the precision of the types inferred for object properties, the analysis is precise enough to show that most expressions have unique types. By also producing precise call graphs, the analysis additionally shows that most invocations in the programs are monomorphic. We furthermore study the usefulness of the analysis to detect spelling errors in the code. Despite the encouraging results, not all problems are solved and some of the experiments indicate a potential for improvement, which allows us to identify central remaining challenges and outline directions for future work.

    Paper BibTex

Workshop and Other Publications

  • Programming a Dataflow Analysis in Flix (TAPAS '16)

    Magnus Madsen, Ming-Ho Yee, Ondřej Lhoták

    Flix is a logic and functional language designed for the implementation of static analysis tools. Flix is inspired by Datalog and extends it with user-defined lattices as well as monotone filter and transfer functions. In recent work, Flix has been used to express several analyses, including the Strong Update analysis, and the IFDS and IDE algorithms

    Paper BibTex