Меню
Публикации
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2021-21-5-720-726
УДК 004.421.2:519.17 004.657
Обобщенное программирование с комбинаторами и объектами
Читать статью полностью
Язык статьи - русский
Ссылка для цитирования:
Аннотация
Ссылка для цитирования:
Косарев Д.С., Булычев Д.Ю. Обобщенное программирование с комбинаторами и объектами // Научно-технический вестник информационных технологий, механики и оптики. 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.