A Partial Evaluator for A Parallel Lambda Language  

作　　者：旷海蓉 孙永强 林凯 

机构地区：[1]DepartmentofComputerScience＆Engineering,ShanghaiJiaoTongUniversity,Shanghai200030

出　　处：《Journal of Computer Science & Technology》1997年第5期441-457,共17页计算机科学技术学报（英文版）

摘　　要：This paper describes theoretical and practical aspects of a partial evaluator that treats a parallel lambda language. The parallel language presented is a combination of lambda calculus and message passing communication mechanism. This parallel language can be used to write a programming language's denotational semantics which extracts the parallelism in the program. From this denotational definition of the programming language, the partial evaluator can generate parallel compiler of the language by self application.The key technique of partial evaluation is binding time analysis that determines in advance which parts of the source program can be evaluated during partial evaluation, and which parts cannot. A binding time analysis is described based upon type inference. A new type chcode is introduced into the type system, which denotes the type of those expressions containing residual channel operations. A well-formedness criterion is given which ensures that partial evaluation not only doesn't commit type errors but also doesn't change the sequence of channel operations. Before binding time analysis, channel analysis is used to analyze the communication relationship between send and receive processes.This paper describes theoretical and practical aspects of a partial evaluator that treats a parallel lambda language. The parallel language presented is a combination of lambda calculus and message passing communication mechanism. This parallel language can be used to write a programming language's denotational semantics which extracts the parallelism in the program. From this denotational definition of the programming language, the partial evaluator can generate parallel compiler of the language by self application.The key technique of partial evaluation is binding time analysis that determines in advance which parts of the source program can be evaluated during partial evaluation, and which parts cannot. A binding time analysis is described based upon type inference. A new type chcode is introduced into the type system, which denotes the type of those expressions containing residual channel operations. A well-formedness criterion is given which ensures that partial evaluation not only doesn't commit type errors but also doesn't change the sequence of channel operations. Before binding time analysis, channel analysis is used to analyze the communication relationship between send and receive processes.

关 键 词：Partial evaluation binding time analysis parallel lambda language 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]