Proceedings of the 17th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2022F212

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 515–519 (2022)

Full text

Abstract. A channel is an abstract data structure which allows for passing messages from one process to another one. We propose several variants of OCCAM, a minimalistic programming language in which a program consists only of processes and channels. The variants differ in how channels are accessed by processes. We prove that all these variants are equally expressive, i.e. an arbitrary OCCAM program can be simulated in any of the variants and the other way around. A particularly interesting variant is to assign exactly one channel to each parallel process. This makes the concept of channels redundant provided that the parallel processes are named. The simulation techniques can be applied to a variety of abstract models and practical systems.

References

1. C. A. R. Hoare, Communicating Sequential Processes. Prentice Hall, 1985.
2. R. Milner, “Elements of interaction,” Communications of the ACM, vol. 36, no. 1, pp. 70–89, 1993, Turing Award lecture.
3. M. Ahuja, A. D. Kshemkalyani, and T. Carlson, “A basic unit of computation in distributed systems,” in International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society, 1990. http://dx.doi.org/10.1109/ICDCS.1990.89327 pp. 12–19.
4. J. Biernacki, “Alvis models of safety critical systems state-base verification with nuXmv,” in FedCSIS, ser. Annals of Computer Science and Information Systems, vol. 8. IEEE, 2016. http://dx.doi.org/0.15439/2016F264 pp. 1701–1708.
5. SGS Thomson Ltd., Occam 2.1 Reference Manual. Prentice Hall, 1988.
6. A. Ripke, A. A. Allen, R. Alastair, and Y. Feng, “Distributed computing using channel communications in Java,” in Communicating Process Architectures 2000. IOS Press, 2000, pp. 49–62.
7. P. H. Welch and F. R. M. Barnes, “Communicating mobile processes: Introducing OCCAM-π,” in Communicating Sequential Processes, ser. LNCS. Springer, 2005, vol. 3525, pp. 712–713.
8. N. C. C. Brown, “Rain: A new concurrent process-oriented programming language,” in Communicating Process Architectures. IOS Press, 2006, pp. 237–251.
9. R. Loogen, “Eden—parallel functional programming with Haskell,” in Central European Functional Programming School, (CEFP), Budapest, Hungary, ser. LNCS, vol. 7241. Springer, 2011. http://dx.doi.org/10.1007/978-3-642-32096-5_4 pp. 142–206.
10. G. D’Angelo, S. Ferretti, and M. Marzolla, “Time warp on the Go,” in Proc. of the International ICST Conference on Simulation Tools and Techniques, ser. SIMUTOOLS ’12. ICST, Brussels, Belgium, 2012. http://dx.doi.org/10.5555/2263019.2263057 pp. 242–248.
11. M. W. Heath, W. P. Burleson, and I. G. Harris, “Synchro-tokens: A deterministic GALS methodology for chip-level debug and test,” IEEE Transactions on Computers, vol. 54, no. 12, pp. 1532–1546, 2005. http://dx.doi.org/http://doi.ieeecomputersociety.org/10.1109/TC.2005.203
12. M. A. Rahimian, S. Mohammadi, and M. Fattah, “A high-throughput, metastability-free GALS channel based on pausible clock method,” in Asia Symposium on Quality Electronic Design. IEEE, 2010. doi: 10.1109/ASQED.2010.5548259 pp. 294–300.
13. P. Hajder, L. Rauch, M. Nycz, and M. Hajder, “A heterogeneous parallel processing system based on virtual multi-bus connection network,” in FedCSIS (Position Papers), ser. Annals of Computer Science and Information Systems, vol. 19, 2019. http://dx.doi.org/10.15439/2019F356 pp. 9–17.
14. ISO/IEC 9945-1: 1990 Information Technology. Portable Operating System Interface (POSIX), Part 1: System Application Program Interface.
15. J. Galletly, OCCAM 2. Including OCCAM 2.1. UCL Press, 1996.
16. A. W. Roscoe, “Denotational semantics for OCCAM,” in Seminar on Concurrency, Carnegie-Mellon University. London, UK: Springer, 1985, pp. 306–329.
17. A. Eliëns, “Semantics for OCCAM,” Centre for Mathematics and Computer Science (CWI), Amsterdam, Tech. Rep. 6255, 1986.
18. Y. Gurevich and L. S. Moss, “Algebraic operational semantics and OCCAM,” in Proceedings of the 3rd Workshop on Computater Science Logic, ser. CSL ’89. London, UK: Springer, 1990. http://dx.doi.org/10.1007/3-540-52753-2_39 pp. 176–192.
19. A. W. Roscoe, M. H. Goldsmith, and B. G. O. Scott, “Denotational semantics for OCCAM 2, part 1,” Transputer Communications, vol. 1, pp. 65–91, 1994.
20. ——, “Denotational semantics for OCCAM 2, part 2,” Transputer Communications, vol. 2, pp. 25–67, 1994.
21. MPI Forum, MPI-4.0. HLRS, 2021.
22. F. Cesarini and S. Thompson, ERLANG Programming. O’Reilly, 2009.
23. D. Wyatt, Akka Concurrency. Artima Incorporation, 2013.
24. I. Graham and T. King, The Transputer Handbook. Prentice Hall, 1990.
25. S. Fowler, S. Lindley, and P. Wadler, “Mixing metaphors: Actors as channels and channels as actors,” in 31st European Conference on Object-Oriented Programming, ECOOP 2017, Barcelona, Spain, ser. LIPIcs, vol. 74. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2017. http://dx.doi.org/10.4230/LIPIcs.ECOOP.2017.11 pp. 11:1–11:28.
26. C. Hewitt, P. Bishop, and R. Steiger, “A universal modular actor formalism for artificial intelligence,” in Proceedings of the 3rd International Joint Conference on Artificial Intelligence, ser. IJCAI’73. Morgan Kaufmann, 1973, pp. 235–245.