Interpretando Efeitos Algébricos por Meio de Mônadas
Resumo
Kelsey demonstrou que a forma de atribuição estática única, comumente utilizada como uma linguagem intermediária para a implementação de otimizadores de código em compiladores de linguagens imperativas, pode ser caracterizada como uma linguagem funcional. Isso ocorre porque a mutabilidade local é eliminada por meio da criação de novas variáveis, e o fluxo de controle pode ser traduzido em abstrações lambda. A tradução dessa representação intermediária para a forma A-normal, frequentemente utilizada em compiladores para linguagens funcionais, é relativamente direta. Rigon et al. exploram essa característica, propondo um sistema que infere tipos e efeitos para uma linguagem com mecanismos de controle de fluxo similares aos de linguagens imperativas. Este trabalho expande essa proposta ao introduzir a tradução da representação intermediária na forma A-normal com efeitos algébricos para uma representação que lida com efeitos por meio de mônadas, onde a combinação de vários efeitos em uma mônada é representada por mônadas livres. Como resultado, é demonstrada a geração de código executável em linguagem Haskell, oferecendo indiretamente um meio simples para a definição de uma semântica para a forma de atribuição estática única.
Referências
Andrej Bauer and Matija Pretnar. 2015. Programming with algebraic effects and handlers. Journal of logical and algebraic methods in programming 84, 1 (2015), 108–123.
Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. 1991. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst. 13, 4 (Oct. 1991), 451–490. DOI: 10.1145/115372.115320
Cormac Flanagan, Amr Sabry, Bruce F Duba, and Matthias Felleisen. 1993. The essence of compiling with continuations. ACM Sigplan Notices 28, 6 (1993), 237–247.
David K. Gifford and John M. Lucassen. 1986. Integrating functional and imperative programming. In Proceedings of the 1986 ACM Conference on LISP and Functional Programming (Cambridge, Massachusetts, USA) (LFP ’86). Association for Computing Machinery, New York, NY, USA, 28–38. DOI: 10.1145/319838.319848
Richard A. Kelsey. 1995. A correspondence between continuation passing style and static single assignment form. In Papers from the 1995 ACM SIGPLAN Workshop on Intermediate Representations (San Francisco, California, USA) (IR ’95). Association for Computing Machinery, New York, NY, USA, 13–22. DOI: 10.1145/202529.202532
Oleg Kiselyov and Hiromi Ishii. 2015. Freer monads, more extensible effects. ACM SIGPLAN Notices 50, 12 (2015), 94–105.
Oleg Kiselyov, Amr Sabry, and Cameron Swords. 2013. Extensible effects: an alternative to monad transformers. ACM SIGPLAN Notices 48, 12 (2013), 59–70.
Daan Leijen. 2014. Koka: Programming with Row Polymorphic Effect Types. Electronic Proceedings in Theoretical Computer Science 153 (June 2014), 100–126. DOI: 10.4204/eptcs.153.8
Daan Leijen. 2016. Algebraic effects for functional programming. Technical Report. Technical Report. MSR-TR-2016-29. Microsoft Research technical report.
Sheng Liang, Paul Hudak, and Mark Jones. 1995. Monad transformers and modular interpreters. In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (San Francisco, California, USA) (POPL ’95). Association for Computing Machinery, New York, NY, USA, 333–343. DOI: 10.1145/199448.199528
J. M. Lucassen and D. K. Gifford. 1988. Polymorphic effect systems. In Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (San Diego, California, USA) (POPL ’88). Association for Computing Machinery, New York, NY, USA, 47–57. DOI: 10.1145/73560.73564
Christoph Lüth and Neil Ghani. 2002. Composing monads using coproducts. ACM SIGPLAN Notices 37, 9 (2002), 133–144.
E. Moggi. 1989. Computational lambda-calculus and monads. In Proceedings of the Fourth Annual Symposium on Logic in Computer Science. IEEE Press, Pacific Grove, California, USA, 14–23.
Eugenio Moggi. 1991. Notions of computation and monads. Information and computation 93, 1 (1991), 55–92.
Gordon D. Plotkin. 1975. Call-by-name, call-by-value and the 𝜆-calculus. Theoretical computer science 1, 2 (1975), 125–159.
Leonardo Filipe Rigon, Paulo Torrens, and Cristiano Vasconcellos. 2020. Inferring types and effects via static single assignment. In Proceedings of the 35th Annual ACM Symposium on Applied Computing (Brno, Czech Republic) (SAC ’20). Association for Computing Machinery, New York, NY, USA, 1314–1321. DOI: 10.1145/3341105.3373888
Amr Sabry and Matthias Felleisen. 1992. Reasoning about programs in continuation-passing style.. In Proceedings of the 1992 ACM Conference on LISP and Functional Programming (San Francisco, California, USA) (LFP ’92). Association for Computing Machinery, New York, NY, USA, 288–298. DOI: 10.1145/141471.141563
Wouter Swierstra. 2008. Data types à la carte. Journal of functional programming 18, 4 (2008), 423–436.
Niki Vazou and Daan Leijen. 2016. From Monads to Effects and Back. In Practical Aspects of Declarative Languages, Marco Gavanelli and John Reppy (Eds.). Springer International Publishing, Cham, 169–186.
Philip Wadler. 1995. Monads for functional programming. In Advanced Functional Programming, Johan Jeuring and Erik Meijer (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 24–52.
