Preview

Труды Института системного программирования РАН

Расширенный поиск

Преобразование типизированных функций в реляционную форму

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.Yu. 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

Просмотров: 131


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)