Functional Implementation of Multiple Traversals Program with Attribute Grammars in Scala

  • Georges Edouard Kouamou National Advanced School of Engineering, University of Yaoundé 1, Cameroon;
  • Thierry Nenkam Faculty of science, University of Dschang, Cameroon;
  • Bernard Talla Fotsing FOTSO Victor University Institute of Technology, University of Dschang, Cameroon;
Keywords: attribute grammars, functional programming, multi traversal program, Scala


Attribute grammars are a powerful specification paradigm for many language processing tasks, particularly the semantic analysis of programming languages. To functionally evaluate attributes grammar in Scala, the studies to date combine Scala with Kiama. Another study relies on object algebra, is implemented in Scala but with multiple evaluation of attributes. The purpose of this study is to use only the Scala language, in order to provide a solution to the multiple traversals of derivation trees. This approach extends the object algebra with the visit-sequences which let us increase the number of folding, thus avoid the multiple evaluation of some attributes, and the result obtained from this experience gives way to the functional modeling of interactive systems. The illustration is made on the Repmin problem.


(1) Knuth, D. E., Semantics of Context-Free Languages. Technical Report, California Institute of Technology, 1968.

(2) Paakki, J., Attribute grammar paradigms - a high-level methodology in language implementation. ACM Computing Surveys, 1995. 2(27): p. 196-255.

(3) Badouel, E., L. Hélouët, G.E. Kouamou, C Morvan and R. F. Nsaibirni, Active workspaces: distributed collaborative systems based on guarded attribute grammars. ACM SIGAPP Applied Computing Review, 2015. 15(3): p. 6-34.

(4) Joao S., Purely Functional Implementation of Attribute Grammars. PhD Thesis, 1999. University of Utrecht.

(5) Hutton G., Programming in Haskell. 2nd Edition, Cambridge University Press, 2016. ISBN 978-1316626221.

(6) Sloane, A. and M. Roberts, A pure embedding of attribute grammars. Science of Computer Programming, 2011.

(7) Bruno, O. and R. W., Cook, Extensibility for the Masses Practical Extensibility with Object Algebras. In Object Oriented Programming, 2012. Proceedings. European Conference on, Springer LNCS 7313. p. 2-27.

(8) Rendel, T., J. I. Brachthauser and K. Ostermann, From Object Algebras to Attribute Grammars. In OOPSLA’14, 2014.

(9) Johnson, T. Attribute grammars as a functional programming paradigm. Functional Programming Languages and Computer Architecture,

Ed. FPCA, vol. 274, p. 154-173, Springer LNCS, 1987.

(10) Bruno, O., A. Loh and R. W. Cook, Feature-Oriented Programming with Object Algebras. In Object-Oriented Programming, 2013. Proceedings. European Conference on, Springer LNCS 7920.

(11) Gamma, E., R. Helm, R. Johnson and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software. 1994. Addison-Wesley (USA).

(12) Bird R. S., Using Circular Programs to Eliminate Multiple Traversals of Data. Acta Informatica, 1984. 21: p. 239-250.

How to Cite
Kouamou, G. E., Nenkam, T., & Fotsing, B. T. (2017). Functional Implementation of Multiple Traversals Program with Attribute Grammars in Scala. Transactions on Machine Learning and Artificial Intelligence, 5(3), 43.