Генеративне та багатоетапне програмування. Lightweight Modular Staging



Дана стаття пропонує дослідження методів таінструментів, що дозволять використовувати функціональні мови програмування високого рівня у сфері системного програмування, де ефективність роботи програми є дуже важливою.

Одним з шляхів досягнення даної мети є використання підходу генеративного програмування і сучасної техніки під назвою Light-weight Modular Staging.

Ключові слова: генеративне програмування, мультиетапне програмування, Scala, Light-weight Modular Staging, мета-програмування.

Generative and Multi-staged Programming. Lightweight Modular Staging

Veres D.S., student at National Technical University of Ukraine “Kyiv Polytechnic Institute”, FICT Ukraine, Kyiv

This article presents a study of methods and tools that can allow to use high-level functional programming languages in a field of systems-level programming, where every drop of performance matters.

One of the ways to achieve our goal is to use the approach of generative programming and modern technique called Light-weight Modular Staging.

Keywords: generative programming, multi-staged programming, Scala, Light-weight Modular Staging, meta-programming

Генеративне та багатоетапне програмування

Одною з найбільших проблем в розробці програмного забезпечення на сьогоднішній день є те, що продуктивність програмного забезпечення все більше і більше розходиться з продуктивністю програміста. Ця проблема посилюється цілою низкою тенденцій:

  1. Тактова частота процесора більше не подвоюється кожних 18 місяців. Замість цього, апаратні частини сучасних комп’ютерів стають все більш паралельними та розподіленими. Програмісти повинні використовувати різноманітні моделі низькорівневого програмування, щоб найкращим чином використовувати наявні апаратні ресурси.

  2. Мови програмування і методології розробки приділяють все більше уваги абстракції та узагальненню, що дозволяє програмістам створювати великі системи з простих, але універсальних частин. Через це, компілювання програм на мовах високого рівня у ефективний код є принципово важким завданням, оскільки компілятори не мають можливості оптимізувати предметно-специфічні операції.

  3. З рухом в сторону “великих даних” та високих навантажень, поширення мобільних пристроїв та вбудованих систем, зростає попит на високоефективне програмне забезпечення.

Ці тенденції змушують команди розробників програмного забезпечення, вкладати великі ресурсив оптимізацію свого коду. З точки зору розробки програмного забезпечення, це бентежить, тому що ручна оптимізація вимагає, щоб програмісти, по суті, відмовились від усіх найкращих практик і переваг високорівневого програмування, таких як використання абстракцій, спільності і модульності. Програми, оптимізовані вручну важко читати, важко підтримувати, важко тестувати і, таким чином, зростає ймовірність, виникнення помилок і вразливостей в системі.

Альтернативою до даного підходу є створення генераторів програм – програм, які після запуску повертають програмний код як вихідну інформацію. Генератор програм може виконувати будь-які обчислення під час створення коду цільової програми, по цій причині, код такої програми може бути дуже ефективним.

Генеративне програмування, як підрозділ мета-програмування, описує практичні аспекти створення програм, які генерують інші програми під час свого виконання.

Підхід етапного (staged) або мульти-етапного (multi-staged) програмування описує ідею поділу обчислювального процесу на різні явні етапи, тобто програма поточного рівня генерує код, який буде оброблений на наступному етапі. Дана концепція описана у [1], її автори помітили, що виконання багатьох програм може бути розділено на етапи за частотою виконання, або за наявністю потрібної для виконання інформації. Підхід мультиетапного програмування (Multi-stageProgramming), запропонований Taha іSheard [2], робить дані етапи явними та дозволяє програмістам відкласти виконання визначених виразів мови програмування до певного етапу. Для цього вони запропонували мову програмування MetaML, яка використовує оператори цитування, що є дуже схожими на макроси мов Lisp та Scheme.

Етапний підхід зазвичай використовується як метод генерування програм. Виконання багатоетапної програми дозволить отримати об’єктну програму, яка може бути скомпільована та виконана на потрібному наборі даних. Даний підхід використовується для спрощення як процесу генерації програми, так і для спрощення трансформацій.

Генеративне програмування дозволяє користуватись рядом цікавих шаблонів програмування. До них відносять mixed-stage типи даних, що містять як статичні, так і динамічні частини. Іншим шаблоном є спеціалізація згенерованого коду засновуючись на статично доступній інформації.

Lightweight modular staging

Lightweight modular staging (LMS) [3] – це сучасна техніка мульти-етапного програмування, що базується на типах: замість використання синтаксичного цитування (як у MetaML), дана техніка використовує потужну систему типів мови Scala для визначення виразів на наступних етапах. В той час, як будь-який звичайний Scala вираз з типом Int, String чи в загальному T виконується нормально, LMS використовує спеціальний конструктор типів Rep[T], особливістю якого є те, що всі операції над об’єктами типів Rep[Int], Rep[String] чи Rep[T] згенерують код, який виконає дані операції пізніше.

Ось простий приклад використання LMS:

У наведеному прикладі створюється об’єкт LMS_Driver. В середині даного об’єкта можна використовувати Rep типи та відповідні їм специфічні операції. Метод snippet є головним методом даного об’єкта (аналог метода/функції main у більшості C-подібних мовах програмування). Функція test виконає функцію snippet з заданим символьним вхідним параметром. Цей виклик дасть можливість провести повне рекурсивне обчислення функції power (оскільки вона є функцією поточного етапу) та запише індивідуальні вирази у вирази у вигляді проміжного представлення (intermediate representation) по мірі знаходження їх у коді. По виході з функції snippet, драйвер зкомпілює згенерований код і завантажить його у програму. Вихідний згенерований код буде мати наступний вигляд:

Виконані перетворення автоматично очищені від типізації: в описі функції power, лише змінна b є динамічною (тип Rep[Int]), всі інші частини програми обробляються статично на на етапі генерації коду. Далі, вираз test(4)виконує згенерований код та повертає результат 1024.

Внутрішня будова LMS.

Техніку LMS називають легкою (lightweight), оскільки вона реалізовується у вигляді бібліотеки та не є невід’ємною частиною мови програмування. Її називають модульною (modular) тому, що вона надає свободу у визначенні доступних операцій для роботи з Rep[T] значеннями. Для клієнтського коду, LMS надає абстрактні інтерфейси, які розширяють вибрану функціональність типу T до роботи з типом Rep[T]:

Всередині, даний інтерфейс створює проміжне представлення (intermediate representation - IR) над яким можна проводити перетворення та з рештою з його допомогою згенерувати фінальний код.

Дану структуру також можна розглядати як методи поверхневого або глибокого влаштовування об’єктів мови проміжного представлення[3]. Наприклад, такі методи як infix_+ можуть слугувати розумними конструкторами, які виконують певні оптимізації коду на льоту під час генерування проміжного представлення [4]. Використання даного підходу та певні налаштування компілятора мови Scala, дає можливість перенести стандартні для мови умовні оператори чи присвоєння змінних у проміжне представлення, за допомогою їх перевизначення у виклики методів [5].

Висновки

В даній роботі описані методи досягнення “абстрації без нарікань” (“abstraction without regret”): отримання високої ефективності роботи програм використовуючи код високого рівня.

Загалом, описані техніки дають можливість використовувати мови програмування високого рівня для створення швидкого та ефективного коду, хоча це і здавалось неможливим ще кілька років тому.

Дана стаття демонструє що LMS та Scala є хорошим вибором для досягнення такої мети, проте близькі результати можна отримати використовуючи й інші мови.

В той час, як уже існує багато шаблонів, які можуть використовуватись у генеративному програмуванні (використання функцій вищого порядку для композиції фрагментів коду, об’єкти та класи для опису багатоетапних структур даних та модульності під час генерації коду), дана галузь знаходиться лише у періоді становлення та відчуває брак нових технік програмування.

Джерела

  1. U. Jørring and W. L. Scherlis. Compilers and staging transformations. In POPL, 1986.

  2. W. Taha and T. Sheard. Metaml andmulti-stage programming with explicit annotations. Theor. Comput. Sci.,248(1-2):211–242, 2000

  3. J. Svenningsson and E. Axelsson. Combining deep and shallow embedding for EDSL. In TFP, 2012

  4. Z. DeVito, J. Hegarty, A. Aiken, P. Hanrahan, and J. Vitek. Terra: a multi-stage language for high-performance computing. In PLDI, 2013.

  5. T. Rompf, N. Amin, A. Moors, P.Haller, and M. Odersky. Scalavirtualized: Linguistic reuse for deep embeddings. Higher-Order and Symbolic Computation (Special issue for PEPM’12).
  • Рецензент: к.т.н., доц. каф. ТК НТУУ "КПІ" Остапенко К.Б.
May 24, 2016