Static program analysis is a powerful technique for maintaining software, withapplications such as compiler optimizations, code refactoring, and bug finding.Static analyzers are typically implemented in general-purpose programminglanguages, such as C++ and Java; however, these analyzers are complex andoften difficult to understand and maintain. An alternate approach is to useDatalog, a declarative language. Implementors can express analysis constraintsdeclaratively, which makes it easier to understand and ensure correctness of theanalysis. Furthermore, the declarative nature of the analysis allows multiple,independent analyses to be easily combined.Flix is a programming language for static analysis, consisting of a logiclanguage and a functional language. The logic language is inspired byDatalog, but supports user-defined lattices. The functional language allowsimplementors to write functions, something which is not supported in Datalog.These two extensions, user-defined lattices and functions, allow Flix tosupport analyses that cannot be expressed by Datalog, such as a constantpropagation analysis. Datalog is limited to constraints on relations, andalthough it can simulate finite lattices, it cannot express lattices over aninfinite domain. Finally, another advantage of Flix is that it supportsinteroperability with existing tools written in general-purpose programminglanguages.This thesis discusses the implementation of the Flix functional language,which involves abstract syntax tree transformations, an interpreter back-end,and a code generator back-end. The implementation must support a number ofinteresting language features, such as pattern matching, first-class functions,and interoperability.The thesis also evaluates the implementation, comparing the interpreter and codegenerator back-ends in terms of correctness and performance. The performancebenchmarks include purely functional programs (such as an N-body simulation),programs that involve both the logic and functional languages (such as matrixmultiplication), and a real-world static analysis (the Strong Update analysis).Additionally, for the purely functional benchmarks, the performance of Flixis compared to C++, Java, Scala, and Ruby.In general, the performance of compiled Flix code is significantly fasterthan interpreted Flix code. This applies to all the purely functionalbenchmarks, as well as benchmarks that spend most of the time in the functionallanguage, rather than the logic language. Furthermore, for purely functionalcode, the performance of compiled Flix is often comparable to Java and Scala.
PDF
download
878987797
028-85220240
