TREEDL: язык описания графовых структур данных и операций над ними

Авторы

  • А.В. Демаков Институт системного программирования имени В.П. Иванникова РАН (ИСП РАН)

Ключевые слова:

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

Аннотация

Рассматриваются методы представления и обработки графов в программах на объектно-ориентированных языках программирования. Анализируются основные возможности специализированного языка описания структуры графов и его инструментальной поддержки. Описывается язык TreeDL, обладающий такими возможностями. Предлагаемое решение сравнивается с другими средствами описания структуры графов.

Автор

А.В. Демаков

Институт системного программирования имени В.П. Иванникова РАН (ИСП РАН)
ул. А. Солженицына, 25, 109004, Москва

Библиографические ссылки

  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).
Новые вычислительные технологии

Загрузки

Опубликован

27-11-2006

Как цитировать

Демаков А. TREEDL: язык описания графовых структур данных и операций над ними // Вычислительные методы и программирование. 2006. 7. 117-127

Выпуск

Том 7 (2006): Выпуск 4.

Раздел

Раздел 2. Программирование