Суперкомпиляция функций высших порядков
Автор: Ключников Илья Григорьевич
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Статья в выпуске: 3 (3) т.1, 2010 года.
Бесплатный доступ
В работе описана внутренняя структура экспериментального суперкомпилятора HOSC. Дано полное описание всех существенных понятий и алгоритмов суперкомпилятора, работающего с функциональным языком высшего порядка (подмножеством языка Haskell). Особое внимание уделяется проблемам связанным с обобщением и отношением гомеоморфного вложения для выражений со связанными переменными.
Суперкомпиляция, анализ программ, функциональное программирование
Короткий адрес: https://sciup.org/14335882
IDR: 14335882
Higher-order supercompilation
The paper describes the internal structure of HOSC, an experimental supercompiler dealing with programs written in a higher-order functional language (a subset of Haskell). A detailed and formal account is given of the concepts and algorithms the supercompiler is based upon. Particular attention is paid to the problems related to generalization and homeomorphic embedding of expressions with bound variables.
Список литературы Суперкомпиляция функций высших порядков
- Абрамов С. М., Метавычисления и их применение, Наука. Физматлит, 1995
- Абрамов С. М., Пармёнова Л. В., Метавычисления и их применение. Суперкомпиляция, Университет города Переславля, 2006
- Barendregt H.P., The lambda calculus: its syntax and semantics, North-Holland, 1984
- Bolingbroke M., Peyton Jones S., "Supercompilation by Evaluation", Haskell 2010 Symposium, 2010
- Damas L., Milner R., "Principal type-schemes for functional programs", Proceedings of the 9th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1982, 207-212
- The GHC Team Haskell 2010 Language Report, http://haskell.org/definition/haskell2010.pdf, 2010
- Johnsson T., "Lambda lifting: Transforming programs to recursive equations", Functional Programming Languages and Computer Architecture, LNCS, 201, Springer, 1985, 190-203
- Jonsson P. A., Nordlander J., "Positive Supercompilation for a higher order callbyvalue language", IFL 2007, 2007, 441-456
- Klyuchnikov I., Supercompiler HOSC 1.0: under the hood, Preprint № 63, Keldysh Institute of Applied Mathematics, Moscow, 2009
- Klyuchnikov I., Supercompiler HOSC: proof of correctness, Preprint № 31, Keldysh Institute of Applied Mathematics, Moscow, 2010
- Klyuchnikov I., Supercompiler HOSC 1.1: proof of termination, Preprint № 21, Keldysh Institute of Applied Mathematics, Moscow, 2010
- Klyuchnikov I., Romanenko S., "Proving the Equivalence of Higher-Order Terms by Means of Supercompilation", Perspectives of Systems Informatics, LNCS, 5947, Springer, 2010, 193-205
- Klyuchnikov I., Romanenko S., "SPSC: a Simple Supercompiler in Scala", PU'09, International Workshop on Program Understanding, 2009
- Klyuchnikov I., Romanenko S., "Towards Higher-Level Supercompilation", Second International Workshop on Metacomputation in Russia, 2010
- Nemytykh A.P., "The supercompiler SCP4: general structure", PSI 2003, LNCS, 2890, Springer, 2003, 162-170
- Mitchell N., Runciman C., "A Supercompiler for Core Haskell", Implementation and Application of Functional Languages, LNCS, 5083, Springer, 2008, 147-164
- Mitchell N., "Rethinking Supercompilation", ICFP 2010, 2010
- Peyton Jones S., The Implementation of Functional Programming Languages, Prentice-Hall Inc., 1987
- Sands D., "Total correctness by local improvement in the transformation of functional programs", ACM Trans. Program. Lang. Syst., 18:2 (1996), 175-234
- Sorensen M. H., Turchin's Supercompiler Revisited: an Operational Theory of Positive Information Propagation, Master's thesis, 1994
- Sorensen M. H., Gl?uck R., "An algorithm of generalization in positive supercompilation", Logic Programming, The 1995 International Symposium, ed. Lloyd J. W., 1995, 465-479
- Sorensen M. H., Gl?uck R., Jones N. D., "A Positive Supercompiler", Journal of Functional Programming, 6:6 (1996), 811-838
- Sorensen M. H., Gl?uck R., "Introduction to Supercompilation", Partial Evaluation. Practice and Theory, LNCS, 1706, Springer, 1998, 246-270
- Turchin V. F., "The concept of a supercompiler", ACM Transactions on Programming Languages and Systems (TOPLAS), 8:3 (1986), 292-325
- Turchin V. F., "The algorithm of generalization in the supercompiler", Partial Evaluation and Mixed Computation, Proceedings of the IFIP TC2 Workshop, 1988
