Mono-variant demand-driven set-based analysis for ML programs

Abstract

In this thesis, we present a mono-variant demand-driven set-based analysis which solves only those constraints affecting subset of program points one wants to analyze. We separate the analysis into two directions: forward to know which values flow into a given point, and backward to know which program points that a given value into. We prove that for interested program points, our analysis gives exactly same results as whole program set-based analysis. We apply our analysis to check ML pattern matching based on approximated runtime values. We report the performance of our analysis as percentage of constraints solved compared with whole program analysis. Experimental results are not much satisfactory both in the accuracy of mono-variant set-based analysis and in the efficiency of demand-driven approach. We discuss that poly-variance can improve both the accuracy and the efficiency.