Open AccessFlow Analysis of Lambda Expressions
Author(s) -
Neil D. Jones
Publication year - 1981
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v10i128.7404
Subject(s) - lambda , interpreter , flow (mathematics) , point (geometry) , set (abstract data type) , church encoding , mathematics , value (mathematics) , static analysis , lambda calculus , computer science , expression (computer science) , typed lambda calculus , calculus (dental) , programming language , discrete mathematics , simply typed lambda calculus , physics , geometry , statistics , medicine , dentistry , optics
We describe a method to analyze the data and control flow during mechanical evaluation of lambda expressions. The method produces a finite approximate description of the set of all states entered by a call-by-value lambda-calculus interpreter; a similar approach can easily be seen to work for call-by-name. A proof is given that the approximation is ''safe'' i.e. that it includes descriptions of every intermediate lambda-expression which occurs in the evaluation. From a programming languages point of view the method extends previously developed interprocedural analysis methods to include both local and global variables, call-by-name or call-by-value parameter transmission and the use of procedures both as arguments to other procedures and as the results returned by them.