Преобразование типизированных функций в реляционную форму
https://doi.org/10.15514/ISPRAS-2018-30(2)-3
Аннотация
Реляционное программирование является подходом, позволяющим исполнять программы в различных "направлениях" для получения различных сценариев поведения по одной реляционной спецификации. В данной статье рассмотрена задача автоматического преобразования функциональных программ в реляционные. Представлен метод преобразования типизированных функций в реляционную форму, а также доказательство его статической и динамической корректности. Также в статье обсуждаются ограничения предложенного метода, представлена реализация метода для подмножества языка OCaml и проведена оценка эффективности метода на ряде реалистичных примеров.
Об авторах
П. А. Лозов
Санкт-Петербургский государственный университет
Россия
Россия
Д. Ю. Булычев
Санкт-Петербургский государственный университет
Россия
Россия
Список литературы
1. Friedman D. P., E.Byrd W., Kiselyov O. The Reasoned Schemer. MIT Press, 2005.
2. Язык Mercury. URL: https://mercurylang.org (дата обращения 09.04.2018).
3. Язык Curry. URL: http://www-ps.informatik.uni-kiel.de/currywiki (дата обращения 09.04.2018).
4. Язык miniKanren. URL: http://minikanren.org (дата обращения 09.04.2018).
5. Hemann J., Friedman D. P. µKanren: A Minimal Core for Relational Programming. Workshop on Scheme and Functional Programming, 2013.
6. Byrd W. E. Relational Programming in miniKanren: Techniques, Applications, and Implementations. Ph.D. thesis, Indiana University, Bloomington, 2009.
7. Pierce B. Types and Programming Languages. MIT Press, 2002.
8. Кознов Д. В. Методология и инструментарий предметно-ориентированного моделирования. Диссертация на соискание учёной степени доктора технических наук, СПбГУ, 2016.
9. Ольхович Л., Кознов Д. Метод автоматической валидации UML-спецификаций на основе OCL. Программирование, 2003, том 29, № 6, стр. 44–50.
10. Терехов А.Н., Романовский К.Ю., Кознов Д.В., Долгов П.С., Иванов А.Н.. RTST++: методология и CASE-средство для разработки информационных систем и программного обеспечения для систем реального времени. Программирование, 1999, том 25, № 5.
11. Codognet P., Diaz D. WAMCC: Compiling Prolog to C. The MIT Press, 1995, pp. 317–331.
12. Henderson F., Somogyi Z. Compiling mercury to high-level C code. In Computational Complexity, 2002, pp. 197–212.
13. Banbara M., Tamura N., Inoue K. Prolog Cafe: A prolog to Java translator system. Lecture Notes in Computer Science, vol. 4369, 2006, pp. 1–11.
14. G´omez-Zamalloa M., Albert E., Puebla G. Decompilation of Java bytecode to Prolog by partial evaluation. Information and Software Technology, 2009, vol. 51, № 10, pp. 1409–1427.
15. Calejo M. InterProlog: Towards a Declarative Embedding of Logic Programming in Java. JELIA 2004: Logics in Artificial Intelligence, pp. 714-717.
16. J. Cook J. P#: A concurrent Prolog for the .NET framework. Software Practice and Experience, vol. 34. № 9, 2004, pp. 815-845.
17. Byrd W. E., Holk E., Friedman D. P. miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl), Workshop on Scheme and Functional Programming, 2012.
18. Kosarev D., Boulytchev D. Typed Embedding of a Relational Language in OCaml. ACM SIGPLAN Workshop on ML, 2016.
19. Язык OCanren. URL: http://github.com/dboulytchev/ocanren (дата обращения 09.04.2018).
20. Alvis C. E., Willcock J. J., Byrd W. E. cKanren: miniKanren with Constraints, Workshop on Scheme and Functional Programming, 2011.
21. Byrd W. E., Ballantyne M., Rosenblatt G., Might M. A Unified Approach to Solving Seven Programming Problems (Functional Pearl). Proc. ACM Program. Lang, 2017, vol. 1, ICFP, pp. 8:1–8:26.
22. Barendregt H. Lambda Calculi with Types. Handbook of Logic in Computer Science, Volume II, Oxford University Press, 1993.
Рецензия
Для цитирования:
Лозов П.А., Булычев Д.Ю. Преобразование типизированных функций в реляционную форму. Труды Института системного программирования РАН. 2018;30(2):45-64. https://doi.org/10.15514/ISPRAS-2018-30(2)-3
For citation:
Lozov P., Boulytchev D. Conversion Typed Functions into Relational Form. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(2):45-64. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(2)-3
Послать статью по эл. почте 