Journal influence
Bookmark
Next issue
Abstract:
Аннотация:
Author: () - | |
Keywords: , c#, object(oriented programming, , |
|
Comments: 1 Page views: 13908 |
Print version Full issue in PDF (4.72Mb) |
Для самых разных задач часто используемые модули можно оформить в отдельные библиотеки. Повторное использование таких библиотек заметно повышает как эффективность программирования, так и последующее сопровождение исходного кода. Отдельные модули можно отлаживать и оптимизировать независимо от кода основной программы, что повышает надежность и производительность программ. В настоящее время наиболее широко распространены объектно-ориентированные языки программирования. Поэтому библиотеки стандартных подпрограмм часто оформляются в виде классов. В некоторых случаях использование классов может заметно сказаться на производительности программ. Например, в случае численных расчетов затраты на обработку объектов оказываются достаточно большими [1]. Для широкого использования объектно-ориентированных языков в численных расчетах необходимы средства преобразования программ, которые позволяют преобразовывать высокоуровневые объектно-ориентированные программы в низкоуровневые императивные. Для таких преобразований можно использовать метод частичных вычислений [2], адаптированный для объектно-ориентированных программ [3]. На основе метода частичных вычислений создан специализатор CILPE [4], способный выполнять описанные преобразования [5]. Частичные вычисления Оптимизация программ на основе использования априорной информации о значении части переменных называется специализацией. Рассмотрим программу f(x, y) от двух аргументов x и y и значение одного из ее аргументов x=a. Результатом специализации программы f(x, y) по известному аргументу x=a является новая программа одного аргумента g(y), обладающая следующим свойством: f(a, y)=g(y) для любого y. Одним из широко используемых методов специализации является метод частичных вычислений (Partial Evaluation, PE) [2]. Данный метод заключается в получении более эффективного кода на основе использования априорной информации о части аргументов и однократного выполнения той части кода, которая зависит только от известной части аргументов. В процессе частичных вычислений операции над известными данными исполняются, а над неизвестными переносятся в остаточную программу. Остаточная программа зависит только от неизвестной (на стадии специализации) части аргументов и будет исполняться только тогда, когда значения этих аргументов станут известны. Цель частичных вычислений – генерация остаточной программы. Метод частичных вычислений основан на разделении операций и других программных конструкций на статические (S) и динамические (D). (При этом понятие «статические операции и конструкции» не следует путать с понятием «статические методы и классы», static, которое используется в объектно-ориентированных языках программирования, например, C# и Java.) Статические операции будут выполнены во время специализации программы, а динамические перейдут в остаточную программу. Часть метода специализации, отвечающая за разделение операций и данных, называется анализом времен связывания (Binding Time Analysis, BTA, BT-анализ) (см. рис.). Вторая часть метода специализации, отвечающая за вычисление статической части программы и выделение динамической части в отдельную программу, называется генератором остаточной программы (Residual Program Generator, RPG). В этой части, собственно, и происходят частичные вычисления. Метод частичных вычислений хорошо развит для функциональных языков [2]. Для объектно-ориентированных языков существуют специализаторы, основанные на методе частичных вычислений [3]. Но они, в отличие от специализатора CILPE, не решают в полной мере задачу по преобразованию объектно-ориентированных программ в императивные. Специализатор CILPE На основе метода частичных вычислений создан специализатор CILPE [4] для внутреннего языка Common Intermediate Language (CIL) платформы Microsoft.NET. Язык CIL является объектно-ориентированным стековым языком. Он не предназначен для ручного написания программ. Но все языки платформы Microsoft.NET, такие как C#, J#, SML.NET, компилируются в язык CIL. Наличие единого внутреннего языка позволяет реализовать специализатор только для этого языка, а затем использовать его для специализации программ, написанных на различных языках программирования. Основным языком платформы Microsoft.NET является высокоуровневый объектно-ориентированный язык C#. Язык CIL, хотя и не обладает всеми выразительными средствами языка C#, поддерживает все его понятия. Это позволяет обрабатывать результат компиляции программ с языка C# на язык CIL без потери необходимой для специализатора информации о программе. Специализатор CILPE поддерживает ограниченное, но широко используемое подмножество операций языка CIL. Не поддерживаются только исключения, передача аргументов по ссылке и структуры. Специализатор CILPE разрабатывался с учетом особенностей объектно-ориентированных языков [3]. В результате специализатор CILPE способен выполнить операции над объектами или массивами, создание и использование которых прослеживается во время специализации программы [5]. Во многих случаях в результате специализации получается программа, в которой отсутствуют объекты, то есть происходит преобразование объектно-ориентированной программы в императивную. Используемые в специализаторе CILPE техники и идеи могут быть легко адаптированы для других объектно-ориентированных языков, например, для языка Java Byte Code (JBC) платформы Java. Пример исходной программы Рассмотрим пример из работы [1], демонстрирующий задержанные вычисления над массивами. При реализации идеи задержанных вычислений порождается много вспомогательных объектов. Специализатор CILPE на основе частичных вычислений успешно выполняет все операции над такими объектами. В результате получаем программу в виде одного цикла без объектов. Пример также демонстрирует, что при использовании специализатора нужно развивать новые нетривиальные приемы программирования, которые позволяют сочетать удобства компонентного программирования с высокой эффективностью результирующей программы. Рассмотрим программу на языке C#, в которой поэлементно перемножаются два массива и к результату прибавляется третий: … // w=x+y*z for (int i=0; i w[i]=x[i]+y[i]*z[i]; … При программировании на императивном языке явно указываются операции, которые необходимо выполнить с каждым элементом массива. В реальных программах циклы по элементам массива могут занимать значительную часть программы. Использование классов на объектно-ориентированным языке C# позволяет записать операции над массивами, не обращаясь явно к элементам массивов: … // w=x+y*z w.Assign(x.Plus(y.Times(z))); … Для описания операций в таком виде используем абстрактный класс Expr, описывающий интерфейс доступа к элементам массива – метод Get. А также методы Plus и Times для поэлементного сложения и произведения массивов: abstract class Expr { [Inline] public Expr () {} [Inline] public abstract double Get (int i); [Inline] public Expr Plus (Expr e) { return new BinaryOpExpr(this,e,new Plus()); } [Inline] public Expr Times (Expr e) { return new BinaryOpExpr(this,e,new Times()); } } Атрибут метода [Inline] в описании классов показывает специализатору CILPE, что данный метод должен быть раскрыт. То есть вместо вызова метода необходимо подставить его тело. Для представления массива языка C# в виде наследника класса Expr определим производный класс Array. Его конструктор описывает создание массива, а метод Get обращение к элементам массива: class Array : Expr { double[] data; [Inline] public Array (int n) { this.data = new double[n]; } [Inline] public override double Get (int i) { return data[i]; } private static int D (int n) { return n; } [Inline] public void Assign (Expr e) { for (int i = D(0); i < data.Length; i++) data[i] = e[i]; } } Для присваивания значения элементам массива используется метод Assign. В нем описан цикл копирования значений из элементов аргумента в элементы массива. Отметим, что это единственный метод, в котором описан такого рода цикл. В дальнейшем при использовании классов Expr и Array такие циклы описывать не приходится. Следует обратить внимание на методы Plus и Times класса Expr. Они предназначены для поэлементного сложения и умножения массивов. Но вместо явного вычисления, что потребовало бы заведения дополнительного массива для промежуточного результата, создается объект класса BinaryOpExpr, описывающий необходимые действия над элементами массива. То есть вместо того чтобы в этом методе непосредственно вычислять массив, операция над массивами запоминается и будет выполнена при обращении к элементам массива-результата. Для этого используется класс BinaryOpExpr. Он хранит в себе два объекта класса Expr и операцию, которую необходимо произвести с элементами этих массивов, – элемент класса BinaryOp: class BinaryOpExpr : Expr { Expr a, b; BinaryOp op; [Inline] public BinaryOpExpr (Expr a, Expr b, BinaryOp op) {this.a = a; this.b = b; this.op = op;} [Inline] public override double Get (int i) { return op.Apply(a.Get(i), b.Get(i)); } } Для описания операций над элементами массивов используется абстрактный класс BinaryOp. В данном классе определен единственный метод Apply – операция над двумя числами. А сами операции описываются классами Plus и Times – сложения и умножения соответственно: abstract class BinaryOp { [Inline] public abstract double Apply (double x, double y); } class Plus : BinaryOp { [Inline] public abstract double Apply (double x, double y) { return x + y; } } class Times : BinaryOp { [Inline] public abstract double Apply (double x, double y) { return x * y; } } Специализация примера Допустим, что в теле программы используются описанные классы для вычисления поэлементного произведения двух массивов и суммирование с третьим; w, x, y, z – объекты класса Array, объявленные по исходной программе. Часть исходной программы на языке C#: … // w=x+y*z w.Assign(x.Plus(y.Times(z))); … Методы Plus и Times не производят вычисления, они порождают объекты, описывающие необходимые операции с элементами массивов. Затем в методе Assign созданные объекты используются и никуда более не передаются. В реальных вычислительных программах таких промежуточных объектов может быть очень много. Их создание и обработка могут заметно сказаться на производительности программы. Поэтому нужен механизм, позволяющий преобразовывать эти программы в программы без создания промежуточных объектов. Таким механизмом является специализатор CILPE, использующий метод частичных вычислений. При специализации программы указанный ранее участок кода преобразуется специализатором CILPE в цикл на стековом языке CIL. Для читаемости приведем его эквивалент на языке C#: … // w=x+y*z for (int i=0; i w[i]=x[i]+y[i]*z[i]; … В результате специализации переменные w, x, y, z – уже не объекты класса Array, а массивы языка C#. Специализатор CILPE полностью выполнил операции над объектами классов BinaryOp, Plus, Times, Expr, Array и BinaryOnExpr, и в остаточной программе от них не осталось и следа. Таким образом, в результате специализации получилась императивная программа. Вышеописанный пример показывает, что использование объектно-ориентированного языка и специализатора, основанного на частичных вычислениях, например, языка C# и специализатора CILPE, позволяет эффективно программировать вычислительные задачи. При использовании объектов программа получается более короткой и выразительной, что сокращает время ее разработки и упрощает отладку. В то же время после специализации исходной программы получается программа, по эффективности сравнимая с императивной. Для достижения уровня специализации, требуемого в таких задачах, разработанный специализатор CILPE обладает поливариантностью по коду, по переменным, по методам и по классам, обрабатывает изменяемые объекты и массивы [5]. По перечисленным свойствам специализатор CILPE превосходит известные специализаторы для объектно-ориентированных языков [4]. Литература 1. Todd L. Veldhuizen. Just When You Thought Your Little Language Was Safe: «Expression Templates» in Java. // G. Butler and S. Jarzabek (Eds.): GCSE 2000, LNCS 2177, pp.188–200, 2001. Springer-Verlag Berlin Heidelberg, 2001. URL: Ошибка! Недопустимый объект гиперссылки. (дата обращения: 06.04.2009). 2. Jones N.D., Gomard C.K., Sestoft P. Partial Evaluation and Automatic Compiler Generation // C.A.R. Hoare Series, Prentice-Hall, 1993. 3. Климов Ю.А. Особенности применения метода частичных вычислений к специализации программ на объектно-ориентированных языках // Препр. ИПМ им. М.В. Келдыша. 2008. № 12. 27 с. URL: http://library.keldysh.ru/preprint. asp?id=2008-12 (дата обращения: 06.04.2009). 4. Partial Evaluation for Common Intermediate Language / A.M. Chepovsky [et al.] // M. Broy and A.V. Zamulin (Eds.): PSI 2003, LNCS 2890, pp. 171–177, 2003. Springer-Verlag Berlin Heidelberg, 2003. URL: www.springerlink.com/content/ r4rr30ajjn449q1a/ (дата обращения: 06.04.2009). 5. Климов Ю.А. Возможности специализатора CILPE и примеры его применения к программам на объектно-ориентированных языках // Препр. ИПМ им. М.В. Келдыша. 2008. № 30. 28 с. URL: http://library.keldysh.ru/preprint. asp?id=2008-30 (дата обращения: 06.04.2009). |
Permanent link: http://swsys.ru/index.php?page=article&id=2251&lang=&lang=&like=1&lang=en |
Print version Full issue in PDF (4.72Mb) |
The article was published in issue no. № 2, 2009 | Print version with comments |
Perhaps, you might be interested in the following articles of similar topics:
- Каркасная библиотека классов для объектно-ориентированного проектирования
- Реализация метаязыковой абстракции для поддержки ООП средствами языка Си
- Оптимальное управление с обратной связью одним классом нелинейных систем по квадратичному критерию
- Программная реализация метода автоматизированного проектирования фюзеляжа воздушного судна с помощью объектно-ориентированных технологий
- Автоматизированная система поддержки принятия решений для прогнозирования процессов рассеивания химически опасных веществ
Back to the list of articles
Comments
author: Виктория [2009-08-19 14:24:29]Было интересно узнать про объектно-ориентированные языки программирования.
Оценка пользователя: 10 баллов