高阶代码消除性能比较框架的设计与实现

doi:10.11772/j.issn.1001-9081.2016.09.2481

计算机应用 ›› 2016, Vol. 36 ›› Issue (9): 2481-2485.DOI: 10.11772/j.issn.1001-9081.2016.09.2481

高阶代码消除性能比较框架的设计与实现

赵迪^1,2, 华保健^1,2, 朱洪军^1,2

1. 中国科学技术大学软件学院, 合肥 230027;
2. 中国科学技术大学苏州研究院, 江苏苏州 215123

收稿日期:2016-03-07 修回日期:2016-03-25 出版日期:2016-09-10 发布日期:2016-09-08
通讯作者: 华保健
作者简介:赵迪(1988-),女,黑龙江齐齐哈尔人,硕士研究生,主要研究方向:程序设计语言;华保健(1979-),男,河北保定人,讲师,博士,主要研究方向:程序设计语言、软件安全;朱洪军(1983-),男,安徽阜阳人,讲师,硕士,主要研究方向:软件测试、移动安全。
基金资助:
国家自然科学基金青年科学基金资助项目（61202052）；苏州市科技计划应用基础研究项目（SYG201406）。

Design and implementation of performance comparing frame for higher-order code elimination

ZHAO Di^1,2, HUA Baojian^1,2, ZHU Hongjun^1,2

1. School of Software Engineering, University of Science and Technology of China, Hefei Anhui 230027, China;
2. Suzhou Institute for Advanced Study, University of Science and Technology of China, Suzhou Jiangsu 215123, China

Received:2016-03-07 Revised:2016-03-25 Online:2016-09-10 Published:2016-09-08
Supported by:
This work is partially supported by the Science Fund Program for the Youths of the National Natural Science Foundation of China (61202052), the Science and Technology Improving Program (Applied Basic Research) of Suzhou (SYG201406).

摘要/Abstract

摘要： 函数式语言编译中，闭包变换和函数消除是广泛采用的高阶代码消除方法。为了提高函数式语言的运行效率，针对函数式语言编译阶段的高阶代码消除过程对目标代码效率的影响，设计并实现了一种函数式语言编译框架。该框架采用了菱形的架构，平行地使用了闭包变换与函数消除两种高阶代码消除方法。设计了一种具有代表性的函数式语言——FUN语言，并以FUN语言为基础，给出了比较框架的一个完整实现。通过该系统，对闭包变换与函数消除的效率影响进行对比实验，选取具有典型特征的测试例，分别从生成代码的规模和运行效率方面对闭包变换与函数消除两种方法的结果进行比较。实验结果表明，与闭包变换相比，使用函数消除方式所得的目标代码量更少，最多可减少33.76%的目标代码量；并且运行效率更高，最多可提高69.51%。

关键词: 编译框架, 函数式语言, 高阶代码, 闭包变换, 函数消除

Abstract: In functional programming language compilation, closure conversion and defunctionalization are two widely used higher-order code eliminating methods. To improve the operational efficiency of functional programming languages, focusing on the higher-order code eliminating phase, a compiler frame to compare the performance of code generated by closure conversion and defunctionalization was proposed. Both closure conversion and defunctionalization were used in parallel in the comparing frame with a diamond structure. A functional programming language named FUN and a compiling system for FUN based on the comparing frame was proposed. Comparison experiments of closure conversion and defunctionalization were conducted on the proposed system by using typical use cases, and the experimental results were compared in code quantity and operation efficiency. The result suggests that compared with closure conversion, defunctionalization can produce shorter and faster target code; the amount of code can be decreased by up to 33.76% and performance can be improved by up to 69.51%.

Key words: compiler frame, functional programming language, higher-order code, closure conversion, defunctionalization

中图分类号:

TP311.5

赵迪, 华保健, 朱洪军. 高阶代码消除性能比较框架的设计与实现[J]. 计算机应用, 2016, 36(9): 2481-2485.

ZHAO Di, HUA Baojian, ZHU Hongjun. Design and implementation of performance comparing frame for higher-order code elimination[J]. Journal of Computer Applications, 2016, 36(9): 2481-2485.

参考文献

[1] HUDAK P. Conception, evolution, and application of functional programming languages [J]. ACM Computing Surveys, 1989, 21(3): 359-411.
[2] VENNERS B. Twitter on Scala [EB/OL]. [2016-01-08]. http://www.artima.com/scalazine/articles/twitter_on_scala.html.
[3] O'CONNELL A. Inside Erlang, the rare programming language behind WhatsApp's success [EB/OL]. [2016-01-08]. http://www.fastcompany.com/3026758/inside-erlang-the-rare-programming-language-behind-whatsapps-success.
[4] MENG X, BRADLEY J, YAVUZ B, et al. MLlib: machine learning in Apache Spark [EB/OL]. [2015-12-08]. http://www.jmlr.org/papers/volume17/15-237/15-237.pdf.
[5] KRILL P. Microsoft to big data programmers: try F# [EB/OL]. [2015-11-22]. http://www.infoworld.com/article/2613049/development-tools/article.html.
[6] TRELFORD P. Learning with F# [C]// CUFP '07: Proceedings of the 4th ACM SIGPLAN Workshop on Commercial Users of Functional Programming. New York: ACM, 2007: Article No. 7.
[7] ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al. Spark: cluster computing with working sets [C]// Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. Berkeley, CA: USENIX Association, 2010: 10.
[8] CEJTIN H, JAGANNATHAN S, WEEKS S. Flow-directed closure conversion for typed languages [C]// ESOP '00: Proceedings of the 9th European Symposium on Programming Languages and Systems. London: Springer, 2000: 56-71.
[9] EISENBERG R A, STOLAREK J. Promoting functions to type families in Haskell [C]// Haskell '14: Proceedings of the 2014 ACM SIGPLAN Symposium on Haskell. New York: ACM, 2014: 95-106.
[10] KUAN G, MACQUEEN D. Engineering higher-order modules in SML/NJ [C]// Proceedings of the 21st International Conference on Implementation and Application of Functional Languages. Berlin: Springer, 2009: 218-235.
[11] LANDIN P J. The mechanical evaluation of expressions [J]. Computer Journal, 1964, 6(4): 308-320.
[12] DANVY O, NIELSEN L R. Defunctionalization at work [C]// Proceedings of the 3rd ACM SIGPLAN international Conference on Principles and Practice of Declarative Programming. New York: ACM, 2001: 162-174.
[13] HANSEN M R, RISCHEL H. Functional Programming Using F# [M]. Cambridge: Cambridge University Press, 2013.
[14] APPEL A W, JIM T. Continuation-passing, closure-passing style [C]// Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. New York: ACM, 1989: 293-302.
[15] MORRISETT G, WALKER D, CRARY K, et al. From system F to typed assembly language [J]. ACM Transactions on Programming Languages and Systems, 1999, 21(3): 527-568.
[16] PERCONTI J T, AHMED A. Verifying an open compiler using multi-language semantics [M]// SHAO Z. Programming Languages and Systems, LNCS 8410. Berlin: Springer, 2014: 128-148.
[17] REYNOLDS J C. Definitional interpreters for higher-order programming languages [J]. Higher-Order and Symbolic Computation, 1998, 11(4): 363-397.
[18] FOURTOUNIS G, PAPASPYROU N S. Supporting separate compilation in a defunctionalizing compiler [EB/OL]. [2015-12-05]. http://www.softlab.ntua.gr/~gfour/files/slate-2013.pdf.
[19] BELL J M, BELLEGARDE F, HOOK J. Type-driven defunctionalization [C]// Proceedings of the 2nd ACM SIGPLAN International Conference on Functional Programming. New York: ACM, 1997: 25-37.
[20] APPEL A W. Compiling with Continuations [M]. New York: Cambridge University Press, 1992: 1-64.

高阶代码消除性能比较框架的设计与实现

Design and implementation of performance comparing frame for higher-order code elimination

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics