Обобщенное программирование с комбинаторами и объектами 

Косарев Д.С., Булычев Д.Ю. Обобщенное программирование с комбинаторами и объектами // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21, № 5. С. 720–726. doi: 10.17586/2226-1494-2021-21-5-720-72

Предмет исследования. В функциональных языках программирования (например, OCaml, Haskell) распространен подход под названием «обобщенное программирование». Его сущность состоит в автоматическом построении на этапе компиляции программ некоторого кода, который выполняет преобразования значений указанного в программе типа данных. Традиционно построенные преобразования представляются с помощью функций, реализующих алгоритм преобразования. Из функций-преобразований и пользовательских функций можно получать новые преобразования с помощью композиции. Недостатком реализации преобразований с помощью функций является монолитность этих функций — невозможно изменить поведение уже объявленной функции. Если построить подходящее преобразование не представляется возможным, программист вынужден написать преобразование вручную и без переиспользования имеющегося кода, что приводит к большим затратам труда. В работе предложено автоматически строить преобразования так, чтобы их можно было изменять после объявления. Метод. Следуя парадигме объектно-ориентированного программирования, предложено хранить преобразования не как функции, а как объекты. Вместо вызова функции вызываются методы соответствующего объекта. Реализация преобразования разбивается на несколько методов объекта. Поддерживается расширение объектов новыми методами, изменение реализации уже имеющихся методов, и за счет этого возможна модификация автоматически построенных преобразований. Основные результаты. В работе предложен способ представления преобразований с помощью объектно-ориентированных возможностей языка OCaml. Объекты-преобразования имеют столько же методов, сколько альтернатив в объявлении типа входных данных преобразования. Такое количество методов позволяет реализовать достаточно разнообразные преобразования. В работе рассмотрено, в каких случаях большее количество методов нежелательно. Метод применим к полиморфным вариантным типам языка OCaml, которые не поддерживаются другими подходами по построению расширяемых преобразований. Практическая значимость. Подход не привязан к конкретной предметной области и позволяет использовать расширяемые преобразования в языке OCaml для произвольных программ, а также может быть перенесен на другие функциональные языки с поддержкой объектно-ориентированного программирования.

1. Gibbons J. Datatype-generic programming // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2007. V. 4719. P. 1–71. https://doi.org/10.1007/978-3-540-76786-2_1

2. Pottier F. Visitors unchained // Proceedings of the ACM on Programming Languages. 2017. V. 1. P. 1–28. https://doi.org/10.1145/3110272

3. Meijer E., Fokkinga M., Paterson R. Functional programming with bananas, lenses, envelopes and barbed wire // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1991. V. 523. P. 124–144. https://doi.org/10.1007/3540543961_7

4. Knuth D.E. Semantics of context-free languages // Mathematical Systems Theory. 1968. V. 2. N 2. P. 127–145. https://doi.org/10.1007/BF01692511

5. Rendel T., Brachthauser J.I., Ostermann K. From object algebras to attribute grammars // ACM SIGPLAN Notices. 2014. V. 49. N 10. P. 377–395. https://doi.org/10.1145/2714064.2660237

6. Viera M., Swierstra S.D., Swierstra W. Attribute grammars fly first-class: how to do aspect oriented  programming in haskell // ACM SIGPLAN Notices. 2009. V. 44. N 9. P. 245–256. https://doi.org/10.1145/1631687.1596586

7. Garrigue J. Programming with Polymorphic Variants // Proc. ACM SIGPLAN Workshop on ML. 1998.

8. Garrigue J. Code reuse through polymorphic variants // Proc. Workshop on Foundations of Software Engineering. 2000.

9. Jones S.P., Vytiniotis D., Weirich S., Washburn G. Simple unification-based type inference for GADTs // ACM SIGPLAN Notices. 2006. V. 41. N 9. P. 50–61. https://doi.org/10.1145/1160074.1159811

10. Kosarev D., Boulytchev D. Typed embedding of a relational language in OCaml // Electronic Proceedings in Theoretical Computer Science, EPTCS. 2018. V. 285. P. 1–22. https://doi.org/10.4204/eptcs.285.1

11. Wadler P. The Expression Problem [Электронный ресурс]. URL: https://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt, свободный. Яз. англ. (дата обращения: 26.07.2021).

12. Yallop J. Staged generic programming // Proc. of the ACM on Programming Languages. 2017. V. 1. P. 1–29. https://doi.org/10.1145/3110273

13. Lämmel R., Jones S.P. Scrap your boilerplate: A practical design pattern for generic programming // ACM SIGPLAN Notices. 2003. V. 38. N 3. P. 26–37. https://doi.org/10.1145/640136.604179

14. Lämmel R., Jones S.P. Scrap more boilerplate: Reflection, zips, and generalised casts // ACM SIGPLAN Notices. 2004. V. 39. N 9. P. 244–255. https://doi.org/10.1145/1016850.1016883

15. Boulytchev D., Mechtaev S. Efficiently Scrapping Boilerplate Code in OCaml // Workshop on ML. 2011.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License