On representation of simulation time in functional programming style
https://doi.org/10.15514/ISPRAS-2018-30(6)-20
Abstract
Functional programming plays the big role in the modern computer science and its importance is growing. This is not accidential: this approach helps to create better and more reliable software that is easy to reason about (both manually and automatically). However, these techniques are hardly used in the field of tools helping designing and modeling mission-critical systems. In this paper, we are trying to apply some nice techniques of functional programming to create a modeling system, in particular a simulation system for analysis of temporal behavioural properties of mission-critical systems. As a first step, we designed a representation of simulation time in terms of abstractions used in functional programming and tried to study its compositionability properties.
About the Authors
D. V. Buzdalov
V.P.Ivannikov Institute for system programming, Russian Academy of Sciences
Russian Federation
Russian Federation
A. K. Petrenko
V.P.Ivannikov Institute for system programming, Russian Academy of Sciences; Moscow State University named after M. V. Lomonosov; National research University “Higher school of economics”
Russian Federation
Russian Federation
A. V. Khoroshilov
V.P.Ivannikov Institute for system programming, Russian Academy of Sciences; Moscow Institute of physics and technology (State University); Moscow State University named after M. V. Lomonosov; National research University “Higher school of economics”
Russian Federation
Russian Federation
References
1. [15] Oleg Kiselyov, Amr Sabry, Cameron Swords. Extensible Effects: An Alternative to Monad Transformers. In Proc. of the 2013 ACM SIGPLAN Symposium on Haskell, 2013, pp. 59-70
2. [1] Denis Buzdalov, Alexey Khoroshilov. A Discrete-Event Simulator for Early Validation of Avionics Systems. In Proc. of the First International Workshop on Architecture Centric Virtual Integration co-located with the 17th International Conference on Model Driven Engineering Languages and Systems (MoDELS 2014), 2014, CEUR Workshop Proceedings, vol. 1233,
3. [16] Oleg Kiselyov, Hiromi Ishii. Freer Monads, More Extensible Effects. In Proc. of the 2015 ACM SIGPLAN symposium on Haskell, 2015, pp. 94-105
4. [2] Denis Buzdalov. Simulation of AADL models with software-in-the-loop execution. ACM SIGAda Ada Letters, vol. 36, issue 2, December 2016, pp. 49-53
5. [17] Oleg Kiselyov. Typed Tagless Final Interpreters. Lecture Notes in Computer Science, vol 7470, 2012, pp. 130-174
6. [3] John Hughes. Why functional programming matters. PMG-40, Chalmers University of Technology, Goteborg, Sweden, 1984. Available at: http://www.cse.chalmers.se/~rjmh/Papers/whyfp.pdf, accessed 18.12.2018
7. [18] Noel Welsh. Uniting Church and State: FP and OO Together. Scala Days conference, Copenhagen, 2017. Available at: https://www.youtube.com/watch?v=IO5MD62dQbI, accessed 18.12.2018
8. [4] Simon Peyton Jones. Functional programming languages as a software engineering tool. In Embedded Systems. Lecture Notes in Computer Science, vol 284, 1986, pp 153-173
9. [19] Oleg Nizhnikov. Modern functional programming with Tagless Final. Joker 2018 Conference, Saint-Petersburg (in Russian). Available at: https://www.youtube.com/watch?v=sWEtnq0ReZA, accessed 18.12.2018
10. [20] Rúnar Bjarnason. Introduction to the Unison programming language. Lambda World 2018 conference, Living Computer Museum, Seattle, 18 september 2018. Available at: https://www.youtube.com/watch?v=rp_Eild1aq8, accessed 18.12.2018
11. [5] Simon Peyton Jones, Philip Wadler. Imperative functional programming. In Proc. of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of programming languages, 1993, pp. 71-84.
12. [21] John Hughes.Generalising monads to arrows. Science of Computer Programming, vol. 37, issues 1–3, May 2000, pp. 67–111
13. [6] The IO Monad for Scala. Available at: https://typelevel.org/cats-effect/, accessed 18.12.2018
14. [22] John Hughes. Programming with Arrows. In Advanced Functional Programming, 2004, pp. 73-129
15. [7] Monix library, Task monad. Available at: https://monix.io/docs/3x/eval/task.html https://typelevel.org/cats-effect/, accessed 18.12.2018
16. [23] Sam Lindley, Philip Wadler, Jeremy Yallop. Idioms are Oblivious, Arrows are Meticulous, Monads are Promiscuous. Electronic Notes in Theoretical Computer Science, vol. 229, issue 5, 2011, pp. 97–117
17. [8] ZIO, Scala-library for asynchronous and concurrent programming, IO monad. Available at: https://scalaz.github.io/scalaz-zio/datatypes/io.html, accessed 18.12.2018
18. [24] Yuriy Polyulya, Functional programming with arrows. Scala Days conference, 2015, Amsterdam. Available at: https://www.youtube.com/watch?v=ZfAgvAIoUEY, accessed18.12.2018
19. [9] Eugenio Moggi. Notions of computation and monads. Information and Computation, vol. 93, issue 1, July 1991, pp. 55-92
20. [25] Julien Richard Foy, Do it with (free?) arrows! Typelevel Summit Copenhagen, June 2017. Available at: https://www.youtube.com/watch?v=PWBTOhMemxQ, accessed 18.12.2018
21. [10] Philip Wadler. Comprehending Monads. Mathematical Structures in Computer Science, vol 2, issue 4, Cambridge University Press, 1992, pp. 461–493
22. [26] John A De Goes. Blazing Fast, Pure Effects without Monads. LambdaConf conference, Boulder, CO, USA, June 2018. Available at: https://www.youtube.com/watch?v=L8AEj6IRNEE, accessed 18.12.2018
23. [11] Conor McBride, Ross Paterson. Applicative programming with effects. Journal of Functional Programming, vol. 18, issue 1, 2008, pp. 1-13
24. [27] Parallel typeclass, cats library. Available at: https://typelevel.org/cats/typeclasses/parallel.html, accessed 18.12.2018
25. [12] Oleg Kiselyov. Having an Effect. Presentation at the Seminar at the Institute of Information Science, Academia Sinica, Taipei, Taiwan, December 2, 2016. Available at: http://okmij.org/ftp/Computation/having-effect.html, accessed 18.12.2018
26. [28] George Leontiev, There’s a prolog in your scala. ScalaIO conference, Paris, France, October 2014. Available at: https://www.youtube.com/watch?v=iYCR2wzfdUs, accessed18.12.2018
27. [13] Guy L. Steele Jr. Building interpreters by composing monads. In Proc. of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of programming languages (POPL ’94), 1994, pp. 472–492
28. [29] A.M. Troitskiy, D.V. Buzdalov. A static approach to estimation of execution time of components in AADL models. Trudy ISP RAN/Proc. ISP RAS, vol. 28, issue 2, 2016, pp. 157-172, doi: 10.15514/ISPRAS-2016-28(2)-10
29. [14] Sheng Liang, Paul Hudak, Mark Jonest. Monad Transformers and Modular Interpreters. In Proc. of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’95), 1995, pp. 333-343
30. [30] Nada Amin, Tiark Rompf, Martin Odersky. Foundations of Path-Dependent Types. In Proc. of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, 2014, pp. 233-249
31. [15] Oleg Kiselyov, Amr Sabry, Cameron Swords. Extensible Effects: An Alternative to Monad Transformers. In Proc. of the 2013 ACM SIGPLAN Symposium on Haskell, 2013, pp. 59-70
32. [16] Oleg Kiselyov, Hiromi Ishii. Freer Monads, More Extensible Effects. In Proc. of the 2015 ACM SIGPLAN symposium on Haskell, 2015, pp. 94-105
33. [17] Oleg Kiselyov. Typed Tagless Final Interpreters. Lecture Notes in Computer Science, vol 7470, 2012, pp. 130-174
34. [18] Noel Welsh. Uniting Church and State: FP and OO Together. Scala Days conference, Copenhagen, 2017. Available at: https://www.youtube.com/watch?v=IO5MD62dQbI, accessed 18.12.2018
35. [19] Oleg Nizhnikov. Modern functional programming with Tagless Final. Joker 2018 Conference, Saint-Petersburg (in Russian). Available at: https://www.youtube.com/watch?v=sWEtnq0ReZA, accessed 18.12.2018
36. [20] Rúnar Bjarnason. Introduction to the Unison programming language. Lambda World 2018 conference, Living Computer Museum, Seattle, 18 september 2018. Available at: https://www.youtube.com/watch?v=rp_Eild1aq8, accessed 18.12.2018
37. [21] John Hughes.Generalising monads to arrows. Science of Computer Programming, vol. 37, issues 1–3, May 2000, pp. 67–111
38. [22] John Hughes. Programming with Arrows. In Advanced Functional Programming, 2004, pp. 73-129
39. [23] Sam Lindley, Philip Wadler, Jeremy Yallop. Idioms are Oblivious, Arrows are Meticulous, Monads are Promiscuous. Electronic Notes in Theoretical Computer Science, vol. 229, issue 5, 2011, pp. 97–117
40. [24] Yuriy Polyulya, Functional programming with arrows. Scala Days conference, 2015, Amsterdam. Available at: https://www.youtube.com/watch?v=ZfAgvAIoUEY, accessed18.12.2018
41. [25] Julien Richard Foy, Do it with (free?) arrows! Typelevel Summit Copenhagen, June 2017. Available at: https://www.youtube.com/watch?v=PWBTOhMemxQ, accessed 18.12.2018
42. [26] John A De Goes. Blazing Fast, Pure Effects without Monads. LambdaConf conference, Boulder, CO, USA, June 2018. Available at: https://www.youtube.com/watch?v=L8AEj6IRNEE, accessed 18.12.2018
43. [27] Parallel typeclass, cats library. Available at: https://typelevel.org/cats/typeclasses/parallel.html, accessed 18.12.2018
44. [28] George Leontiev, There’s a prolog in your scala. ScalaIO conference, Paris, France, October 2014. Available at: https://www.youtube.com/watch?v=iYCR2wzfdUs, accessed18.12.2018
45. [29] A.M. Troitskiy, D.V. Buzdalov. A static approach to estimation of execution time of components in AADL models. Trudy ISP RAN/Proc. ISP RAS, vol. 28, issue 2, 2016, pp. 157-172, doi: 10.15514/ISPRAS-2016-28(2)-10
46. [30] Nada Amin, Tiark Rompf, Martin Odersky. Foundations of Path-Dependent Types. In Proc. of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, 2014, pp. 233-249
Review
For citations:
Buzdalov D.V., Petrenko A.K., Khoroshilov A.V. On representation of simulation time in functional programming style. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(6):341-366. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(6)-20
Email this article 