TreeDL: a language for description of graph structures and operations on them

Authors

  • A.V. Demakov Ivannikov Institute for System Programming of RAS (ISP RAS)

Keywords:

графы программ, объектно-ориентированные языки программирования, структура графа, инструментальные средства, базы данных, объектные модели

Abstract

Some methods of graph representation and processing in object-oriented languages are considered. Desirable features and a tool support of a language for description of graph structures and operations on them are analyzed. The TreeDL language having these features is described and compared with other approaches.

Author Biography

A.V. Demakov

References

  1. Кнут Д. Искусство программирования. 1. Основные алгоритмы. М.: Вильямс, 2000.
  2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Вильямс, 2001.
  3. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ- Петербург, 2003.
  4. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.
  5. Дистель Р. Теория графов. Новосибирск: Изд-во ИМ СО РАН, 2002.
  6. Gosling J., Joy B., Steele G., Bracha G. The Java愦灭;circTM language specification. Reading: Addison-Wesley, 2005.
  7. Standard ECMA-334 C# Language Specification. Third edition. June 2005 // (http://www.ecma-international.org/ publications/standards/Ecma-334.htm).
  8. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: Бином, 2001.
  9. Мейер Б. Объектно-ориентированное конструирование программных систем. М.: Интуит.ру, 2005.
  10. Грэхем И. Объектно-ориентированные методы. Принципы и практика. М.: Вильямс, 2004.
  11. Влиссидес Дж., Джонсон Р., Хелм Р., Гамма Э. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2003.
  12. Ingalls D.H. H. A simple technique for handling multiple polymorphism // Proc. of the ACM Conference on Object- Oriented Programming Systems, Languages and Applications (OOPSLA’86). Portland, 1986 // (http://portal.acm.org/citation.cfm?id=28732).
  13. Visser J. Visitor combination and traversal control // OOPSLA’01. Tampa, 2001 // (http://portal.acm.org/citation.cfm?id=504302).
  14. Fahndrich M.K., Leino R.M. Declaring and checking non-null types in an object-oriented language // OOPSLA’03. Anaheim: 2003 (http://research.microsoft.com/ leino/papers/krml109.pdf).
  15. Birka A., Ernst M.D. A practical type system and language for reference immutability // OOPSLA’04. Vancouver, 愦灭;percent British Columbia, Canada, 2004 (http://www.sct.ethz.ch/teaching/ws2004/semspecver/papers/ernst-ref-immutability- oopsla2004.pdf).
  16. Tschantz M.S., Ernst M.D. Javari: Adding reference immutability to Java // OOPSLA’05. San Diego, 2005 // 愦灭;percent California, USA, 2005 // (http://pag.csail.mit.edu/ mernst/pubs/ref-immutability-oopsla2005.pdf).
  17. Mugridge W.B., Hamer J., Hosking J.G. Multimethods in a statically-typed programming language // OOPSLA’91. New York, 愦灭;percentNY, 1991 (http://portal.acm.org/citation.cfm?id=679202).
  18. Chambers C., Leavens G.T. Typechecking and modules for multimethods // OOPSLA’94. Portland, 1994 // (ftp://ftp.cs.washington.edu/homes/chambers/mmtc.ps.Z).
  19. Millstein T., Chambers C. Modular statically typed multimethods // ECOOP’99. Lisbon, 1999 // 愦灭;percentPortugal, 1999 (http://www.ifs.uni-linz.ac.at/ ecoop/cd/papers/1628/16280279.pdf).
  20. Gabriel R.P., DeMichiel L. The Common Lisp Object System: An overview // ECOOP’87. Paris, 1987.
  21. Chambers C. Object-oriented multimethods in Cecil // ECOOP’92. Utrecht, 1992 // 愦灭;percentThe Netherlands, 1992. // (ftp://ftp.cs.washington.edu/homes/chambers/cecil-oo-mm.ps.Z).
  22. The MultiJava Project (http://multijava.sourceforge.net).
  23. The Nice programming language (http://nice.sourceforge.net).
  24. Ernst E. Family polymorphism // 愦灭;percentIn Jorgen Lindskov Knudsen, editor, ECOOP 2001-Object-Oriented Programming. Heidelberg: Springer-Verlag, 2001. 303-326 (http://portal.acm.org/citation.cfm?id=680013).
  25. Bruce K.B. Some challenging typing issues in object-oriented languages // Electronic Notes in Theoretical Computer Science, 2003 愦灭;percentT. 82(8). (http://citeseer.ist.psu.edu/bruce03some.html).
  26. Jolly P., Drossopoulou S., Anderson C., Ostermann K. Simple dependent types: Concord (FTfJP accepted version). April 2004 // (http://myitcv.org.uk/papers/concord04.html, http://citeseer.ist.psu.edu/article/jolly04simple.html).
  27. Nystrom N., Chong S., Myers A.C. Scalable extensibility via nested inheritance // OOPSLA’04. Vancouver, 2004 愦灭;percent British Columbia, Canada, 2004. (http://citeseer.ist.psu.edu/nystrom04scalable.html).
  28. Фаулер М. Рефакторинг: улучшение существующего кода. СПб.: Символ-плюс, 2005.
  29. Eclipse platform (http://eclipse.org).
  30. Walters H.R., Kamperman J.F. Th., Dinesh T.B. An extensible language for the generation of parallel data manipulation and control packages. Report CS-R9575. CWI SMC. Amsterdam, 1995 // (http://www.cwi.nl/ftp/CWIreports/AP/CS- R9575.ps.Z).
  31. Системы автоматизации производства и их интеграция. Представление данных об изделии и обмен этими данными. Часть 11. Методы описания. Справочное руководство по языку EXPRESS / Государственный стандарт РФ ГОСТ РИСО 10303-11-2000.
  32. ANTLR: ANother Tool for Language Recognition (http://www.antlr.org).
  33. Weatherley R. Treecc: An aspect-oriented approach to writing compilers // Free Software Magazine. Issue 2. 2001. (http://www.southern-storm.com.au/treecc.html).
  34. Демаков А. Исполнимое подмножество языка спецификации и его трансляция // Приложения системного программирования: Вопросы кибернетики. Научный совет по комплексной проблеме «Кибернетика» РАН. М., 1998. Вып. 4. 17-28.
  35. Bourdonov I.B., Demakov A.V., Jarov A.A., Kossatchev A.S., Kuliamin V.V., Petrenko A.K., Zelenov S.V. Java specification extension for automated test development // Proc. of PSI’01. Berlin: Springer-Verlag, 2001. 301-307.
  36. Демаков А. Применение технологии UniTesK для тестирования NET-компонентов // Труды конференции «Технологии Microsoft в научных исследованиях и высшем образовании». М., 2003.
  37. Зеленов С.В., Зеленова С.А., Косачев А.С., Петренко А.К. Генерация тестов для компиляторов и других текстовых процессоров // Программирование. 29, № 2. 2003. 59-69.
  38. Kuliamin V., Petrenko A.K. Applying model based testing in different contexts // Proc. of Seminar on Perspectives on Model Based Testing. Dagstuhl, 2004. 愦灭;percent Germany, September 2004.
  39. Архипова М. Генерация тестов для семантических анализаторов. Препринт ИСП РАН № 9. M., 2005.
  40. Демаков А. Язык описания абстрактного синтаксиса TreeDL и его использование. Препринт ИСП РАН № 17. M., 2006.
  41. Проект TreeDL (http://treedl.sourceforge.net).

Published

27-11-2006

How to Cite

Демаков А. TreeDL: A Language for Description of Graph Structures and Operations on Them // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2006. 7. 117-127

Issue

Section

Section 2. Programming