metaL

metaL

гомоиконичная система (язык) программирования

метод EDS: исполняемые структуры данных

Гомоиконичность (homoiconic) -- свойство языка программирования, когда любая программа на этом языке одновременно является данными.

В гомоиконичном языке программист не просто имеет доступ к исходному коду, но сам язык специально предусматривает средства удобной работы с частями программ во время исполнения (в рантайме).

• То есть, если вы включаете в дистрибутив вашей программы на С++ ее исходный код, вы можете работать с текстом программы как с данными, но только на уровне текстовых файлов, или используя сторонние библиотеки анализа. В самом языке С++ никаких средств чтения, модификации и генерации исходного кода нет.

• Обратно, в языке Лисп все программы представляются в виде исполняемых списков -- списки одновременно являются и представлением программы, и обычной структурой данных, для работы с которой язык специально создавался.

Чтобы использовать достоинства гомоиконичности в ваших программах на любых языках (С++/Java/C#/...), в ваши программы нужно встроить интерпретатор, который будет выполнять некоторую структуру данных как программу, и одновременно предоставлять высокоуровневые средства для ее модификации.

Совершенно не обязательно, чтобы этот интерпретатор был реализацией какого-либо скриптового языка программирования.

Скриптовые интерпретаторы, встраиваемые в программы, сейчас широко используются для предоставления пользователю возможности настраивать и расширять функционал программ без перекомпиляции. Самый известный пример -- игровые движки:

• ядро написано на С++ или любом другом языке, генерирующим высокоэффективный машинный код
• саму игру пишут на каком-нибудь скриптовом языке типа Lua, Python, JavaSript,..

Самое интересное что возможно программирование без использования языка программирования -- достаточно, чтобы в системе был интерпретатор структур данных: метод EDS -- Executable Data Structure (испольняемые структуры данных). Чтобы создать программу в такой системе, нужен любой способ, позволяющий создать в памяти исполняемую структуру данных: это может быть графическая рисовалка, парсер текстового формата, графовая база данных, или код на С++, который заставляет компилятор включить такую структуру в исполняемый файл.

Метапрограммирование

Метапрограммирование -- когда одна программа пишет/модифицирует другую программу (или саму себя).

Метапрограммирование это метод, который позволяет вам увеличивать свою эффективность как программиста за счет того, что вы расширяете язык, на котором пишете. Если вы ежедневно пишете очень похожий код, в языках, которые умеют мета (Lisp,Nim), вы можете написать небольшую программку-макрос, которая будет запускаться во время компиляции кода (Nim), и генерировать новый код по шаблону или изменять уже существующий так, как вам это нужно. Фактически, вы можете добавлять в язык те возможности, которые нужны именно вам для узкого набора задач.

Чтобы можно было пользоваться метапрограммированием в полном объеме, язык или система программирования обязательно должна быть гомоиконичной. Если вы хотите использовать этот метод с промышленными языками программирования, применение EDS-интерпретатора позволит вам быстро и удобно решать ваши задачи, заплатив за это потерями в скорости работы программ и памятью (см. интерпретатор vs компилятор в машинный код).

Представление программ

Известные формы представления программ:

• машинный код
• исходный код на некотором языке (текстовые файлы) -- все промышленные языки программирования
• списки -- язык Лисп

metaL (meta Language) предлагает еще одну форму:

• объектные графы -- metaL

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

Граф состоит из вершин -- узлов, и ребер, которые соединяют узлы между собой. Ориентированный граф -- частный случай графа, в котором для каждого ребра задано направление, и известны начальный и конечный узел.

Объект -- элемент данных, который связывает

• набор полей данных, задающих состояние объекта
• методы для работы с этими данными, и с самим объектом как с единой сущностью

Объектный граф -- структура данных, в которой

• узлами являются объекты, а
• ребра задаются как ссылки из объекта на другие объекты
  Вполне естественно, что объектный граф является направленным, и может быть циклическим (объект ссылается сам на себя)

Фрейм

Структура данных, очень похожая на объектный граф, описана в книге Марвин Мински Фреймы для представления знаний, поэтому будем такие объекты называть фреймами.

class Frame:
    def __init__(self,V):
        # метка типа/класса
        self.type = self.__class__.__name__.lower()
        # имя фрейма, или скалярное значение: число, строка,..
        self.val  = V
        # атрибуты = слоты = ассоциативный массив
        self.slot = {}
        # список = стек = очередь = вложенные элементы в AST
        self.nest = []

print( Frame('Hello World') )

<__main__.Frame object at 0x7fa2245f1358>

Каждый узел объектного графа -- универсальный контейнер данных.

• type указывает тип фрейма, который в том числе выводится пользователю. Это поле обязательно для языков, которые не поддерживают RTTI: не умеют обределять тип произвольного объекта динамически, при выполнении программы. В Python есть встроенная функция isinstance(), но поле появилось из-за требований библиотеки PLY.

• val содержит данные, которые отличают один фрейм от другого: имя фрейма, или скалярная величина.

• slot хранит именованные ссылки на другие фреймы -- задает ребра объектного графа

• nest упорядоченный контейнер данных, которого не было в оригинальных фреймах Мински, но он необходим для разбора текстовых форматов (вложенные элементы дерева разбора), и применения в качестве стека (LIFO) и очереди (FIFO)

Любой узел может хранить любые другие данные, упакованные в дополнительные поля -- достаточно отнаследовать новый класс об базового Frame.

Вывод графа фреймов в виде дерева

Для работы с деревом фреймов необходимо средство просмотра полученного объектного графа. Как вы видете выше, вывод print() совершенно неинформативен, из него нельзя понять не только состав фрейма, но даже просто его имя. Как минимум, нам нужен способ получать текстовый дамп, и еще желательно иметь способ просмотра графа в графике.

class Frame(Frame): # финт для Jupyter Notebook: наследование классом самого себя
    
    # системный метод: конвертация в строку для print() и выражений типа '%s' % frame
    def __repr__(self):
        return self.dump()
    
    # полный дамп фреймового графа в виде дерева
    def dump(self,depth=0,prefix=''):
        # сначала только заголовок, оттабулированный на глубину вложения фрейма
        tree = self._pad(depth) + self.head(prefix)
        # слоты могут ссылаться сами на себя рекурсивно,
        # чтобы не получить бесконечный дамп, уже выведенные фреймы останавливают рекурсию
        if not depth: Frame._dumped = []
        if self in Frame._dumped: return tree + ' _/'
        else: Frame._dumped.append(self)
        # выводим слоты в формате <имя> = <фрейм на который ссылаемся>
        for i in self.slot:
            tree += self.slot[i].dump(depth+1,prefix='%s = '%i)
        # вложенные элементы
        for j in self.nest:
            tree += j.dump(depth+1)
        return tree
    
    # дамп только заголовока фрейма
    def head(self,prefix=''):
        return '%s<%s:%s> @%x' % (prefix,self.type,self._val(),id(self))
    
    # отбивка на глубину вложения дерева дампа
    def _pad(self,depth):
        return '\n' + '\t' * depth
    
    # .val может быть произвольным (нестроковым) типом,
    # поэтому нужна индивидуальное преобразование в строку для разных типов чисел,..
    def _val(self):
        return str(self.val)

Frame('Hello World')

<frame:Hello World> @7fa2245f1dd8

Для пустого элементарного фрейма выводится только заголовок, начинающийся с пустой строки:

• префикс был пустым, поэтому в начале не добавляются никакие дополнительные символы
• <тип: метка типа позволяет отличить такие объекты как <integer:123> и <string:123>
• :строка> значение объекта, строка -- самый универсальный тип, который может хранить любые данные
• @DeadBeef уникальный (шестнадцатеричный) идентификатор объекта в Python, если вы создадите два фрейма с одинаковым значением, вы все равно сможете их отличить (например объект-оригинал, и его копию)

Frame(123),Frame('123') # .val назначаются разные типы, на дампе выглядит одинаково

(
 <frame:123> @7fa224608048, 
 <frame:123> @7fa2246080b8)

Frame(123),Frame(123) # два разных фрейма с одинаковым значением, отличаются по id()

(
 <frame:123> @7fa224608550, 
 <frame:123> @7fa2246085c0)

Операторы для модификации фреймов

Для конструирования и модификации объектных графов нам нужно определить несколько встроенных методов для фрейма, чтобы можно было оперировать с фреймами с помощью операторов и выражений Python:

class Frame(Frame):
    
    # return frame[key]
    def __getitem__(self,key):
        return self.slot[key]
    
    # frame[key] = that
    def __setitem__(self,key,that):
        self.slot[key] = that ; return self
    
    # frame << that -> frame[that.val] = that
    def __lshift__(self,that):
        self[that.val] = that ; return self
    
    # frame // that
    def __floordiv__(self,that):
        self.nest.append(that) ; return self

Самая простая в понимании операция -- добавить один фрейм в другой как в стек (добавить к nest[])

hello = Frame('Hello') // Frame('World') // Frame('вершина стека')
print(hello)

<frame:Hello> @7fa224608b38
	<frame:World> @7fa224608ba8
	<frame:вершина стека> @7fa224608c18

Оператор // или .push() добавляет правый операнд в левый, заталкивая его как в стек.
Оператор левоассоциативен -- выражение из нескольких подряд идущих операторов // вычисляются слева направо:

• результат вычисления -- тот же фрейм, что указан слева, с добавленными данными (return self)

hello['key'] = Frame('that') ; print(hello)
print(hello['key'])

<frame:Hello> @7fa224608b38
	key = <frame:that> @7fa224608da0
	<frame:World> @7fa224608ba8
	<frame:вершина стека> @7fa224608c18

<frame:that> @7fa224608da0

Выражение frame[key] делает поиск в frame по ключу key в таблице слотов, и возвращает тот фрейм, на кооторый указывает соответствующий слот.

Аналогично выражение frame[key] = that присваивает слоту key во фрейме frame новое значение -- фрейм that.

Ключ слота key может иметь любой тип, допустимый для словарей в Python:

hello[123] = Frame(4.56) ; print(hello,'\n')
# цикл перебора слотов
for i in hello.slot.keys(): print(i, type(i), hello[i].head(), type(hello[i].val))

<frame:Hello> @7fa224608b38
	123 = <frame:4.56> @7fa224590780
	key = <frame:that> @7fa224608da0
	<frame:World> @7fa224608ba8
	<frame:вершина стека> @7fa224608c18 

123 <class 'int'> <frame:4.56> @7fa224590780 <class 'float'>
key <class 'str'> <frame:that> @7fa224608da0 <class 'str'>

import sys
try:    hello['not_exists']
except: print(sys.exc_info())              

(<class 'KeyError'>, KeyError('not_exists',), <traceback object at 0x7fa2245f9848>)

Попытка обращения к несуществующему слоту приводит к исключению KeyError

Оператор << записывает слот, используя значение that.val как ключ:

hello << hello

<frame:Hello> @7fa224608b38
	123 = <frame:4.56> @7fa224590780
	key = <frame:that> @7fa224608da0
	Hello = <frame:Hello> @7fa224608b38 _/
	<frame:World> @7fa224608ba8
	<frame:вершина стека> @7fa224608c18

Отрисовка фреймов в виде графа

Дамп дает очень подробную информацию, но большие исполняемые структуры даже из десятков узлов уже становятся запутанными и трудными для чтения. Для визуализации в Jupyter Notebook (Python) мы можем воспользоваться graphviz

! pip install -U --force-reinstall graphviz

Collecting graphviz
  Using cached https://files.pythonhosted.org/packages/94/cd/7b37f2b658995033879719e1ea4c9f171bf7a14c16b79220bd19f9eda3fe/graphviz-0.13-py2.py3-none-any.whl
Installing collected packages: graphviz
  Found existing installation: graphviz 0.13
    Uninstalling graphviz-0.13:
      Successfully uninstalled graphviz-0.13
Successfully installed graphviz-0.13

# https://h1ros.github.io/posts/introduction-to-graphviz-in-jupyter-notebook/
# https://www.programcreek.com/python/example/104476/graphviz.Digraph
import graphviz
class Frame(Frame):
    def plot(self,dot=None,depth=0,parent=None,link='',color='black'):
        
        # на корневом узле надо создать graphiz-объект
        if not dot: dot = graphviz.Digraph(graph_attr={'rankdir':'LR'})
            
        # добавляем себя в вывод, узлы связываются только по str(id())
        # иначе два фрейма с одинаковым <T:V> слипнутся в один
        dot.node('%s'%id(self),label='%s:%s'%(self.type,self._val()))
        # если есть родительский узел-источник, рисуем ребро
        if parent:
            dot.edge('%s'%id(parent),'%s'%id(self),color=color,label='%s'%link)
            
        # блокировка бесконечной рекурсии на кольцевых ссылках аналогично dump()
        if not depth: Frame._plotted = []
        if self in Frame._plotted: return dot
        else: Frame._plotted.append(self)
            
        # ссылки слотов рисуем синим
        for i in self.slot:
            self.slot[i].plot(dot,depth+1,parent=self,link=i,color='blue')
        
        # ссылки на элементы из nest[] рисуем красным
        N=0
        for j in self.nest:
            j.plot(dot,depth+1,parent=self,link=N,color='red') ; N += 1
        
        return dot

hello = Frame('Hello') // Frame('World') // Frame('вершина стека')
hello['key'] = Frame('that')
hello << hello

hello.plot()

Примитивы

Для работы компьютера нужны какие-то базовые типы данных. Физические процессоры в большинстве умеют работать только с целыми числами ограниченного диапазона, редко -- числами с плавающей точкой (десятичными дробями). Так как мы реализуем нашу графовую виртуальную машину на высокоуровневых языках, естественно взять в качестве базовых типов данных те типы, которые уже есть в языке реализации.

class Primitive(Frame):
    def eval(self,ctx): ctx // self

Строка

Строки -- самый универсальный тип данных: с помощью сериалиазации мы можем хранить в текстовом виде все что угодно.

class String(Primitive): pass

Символ

Символ -- это некоторое уникальное имя, которое может называть другие объекты.

Символы внутреннему представлению полностью аналогичны строкам, и были введены только для того чтобы отличаться от строк в некоторых специальных случаях (символ может вычисляться в другой объект, строки вычисляются только сами в себя).

class Symbol(Primitive): pass

Числа

Для практических целей наша система должна уметь работать с целыми числами, и десятичными дробями.

Для низкоуровневого кода, и встраиваемых систем также необходима поддержка шестнадцатеричных и двоичных чисел.

Если вы много работаете с мат.вычислениями, скорее всего вы захотите добавить натуральные дроби и комплексные числа.

class Number(Primitive): pass

class Integer(Number): pass
class Hex(Integer): pass
class Bin(Integer): pass

Контейнеры

Frame является универсальным контейнером данных -- в него можно поместить любые другие данные. Если нам нужно точнее указать поведение контейнера, и его свойства, правильнее будет иметь набор нескольких контейнерных типов, широко используемых в программировании:

class Container(Frame): pass

class Vector(Container): pass
class Stack(Container): pass
class Dict(Container): pass
class Queue(Container): pass
class Set(Container): pass

GOP: графо-ориентированное программирование

https://www.quora.com/What-is-graph-oriented-programming/answer/Dmitry-Ponyatov

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

• могут быть выполнены EDS-интерпрератором, и
• могут модифицировать объектный граф системы так как нам нужно.

class Active(Frame): pass

Команды виртуальной машины

Прежде всего нам нужен способ представить произвольный код на Python в виде фреймов:

class Cmd(Active):
    def __init__(self,F):
        Active.__init__(self,F.__name__)
        # заворачиваем Python-функцию в отдельное поле
        self.fn = F
    def eval(self,ctx):
        self.fn(ctx)

Теперь мы можем заворачивать любую функцию с специальный тип фреймов:

def BYE(ctx): print(BYE,'in context',ctx.head(),': system terminated') # ; sys.exit(0)
print(Cmd(BYE))

<cmd:BYE> @7fa2245906a0

print(Cmd(sys.exit), Cmd(lambda ctx:sys.exit(0)))

<cmd:exit> @7fa2246089b0 
<cmd:<lambda>> @7fa2245a81d0

Контекст выполнения

При запуске любого выполняемого кода создается контекст исполнения -- структура данных, или область памяти компьютера, в которой исполняющийся процесс хранит информацию о своем текущем состоянии:

• точку выполнения программы
• стек: историю вызовов подпрограмм (функций), с адресами куда нужно сделать вызврат при завершении функции
• указатель на таблицу ресурсов, выделенных процессу операционной системой

В графовой машине

• каждая команда тоже должна выполняться в контексте, переданном как параметр: цель каждой команды -- его модифицировать в зависимости от того, что конкретная команда должна сделать.
• контект тоже является особым типов графа -- фреймом.

Контекст предоставляет любой команде две области памяти:

• стек, с которого команда получает параметры для своей работы, и на который кладет результат
• среду (environment) которая связывает имена переменных с их значениями

class VM(Active):
    def __lshift__(self,F):
        # умеет заворачивать Python-функцию через оператор <<
        if callable(F): return self << Cmd(F)
        else: return Frame.__lshift__(self,F)

# глобальный контекст
vm = VM('metaL')

# добавляем команду (имитации) завершения работы системы
vm << BYE

print(vm)

<vm:metaL> @7fa224590a58
	BYE = <cmd:BYE> @7fa224590278

Для запуска команды делаем выборку из глобального контекста по имени, и передаем vm как контекст для команды:

vm['BYE'].eval(vm)

<function BYE at 0x7fa2245f5598> in context <vm:metaL> @7fa224590a58 : system terminated

Hello World для компиляторщика

Для разработчиков языков программирования, "компиляторщиков", и программистов на функциональных языках аналогом программы HelloWorld является рекурсивная функция Фибоначчи:

Постановка задачи

Последовательность чисел Фибоначчи определяется формулой:

• первые два числа равны $F_0=1$, $F_1=1$
• $F_n = F_{n-1} + F_{n-2}$. То есть, следующее число получается как сумма двух предыдущих.

Лобовое решение для вычисления n-ого числа $F_n$

int fib(int n) {
    if (n < 2): return 1
    return fib(n-1) + fib(n-2)
}

Данное решение имеет экспоненциальный рост времени вычислений при увеличении $n$, так как при вычислении элементов $F_{n-1,2,..}$ все вычисления выполняются заново и рекурсивно до первых членов последовательности.

Для оптимизации с применением хвостовой рекурсии вводится служебная функция:

int _fib(int n, int acc) {
    // останов рекурсии
    if (n==0) return acc;
    // хвостовой рекурсивный вызов
    return _fib(n-1,acc*n)
}

int fib(int n) { return _fib(n,1) }

class Meta(Frame): pass

# программный модуль (единица компиляции)
class Module(Meta): pass

# переменная для модуля
fibonacci = Module("fibonacci") ; fibonacci

<module:fibonacci> @7fa2245a8160

# модуль формируют глобальные переменные
class Var(Meta): pass
# и функции
class Fn(Meta): pass

Определяем две функции

fib  = Fn('fib' ) ; fibonacci <<  fib
_fib = Fn('_fib') ; fibonacci << _fib

fibonacci

<module:fibonacci> @7fa2245a8160
	fib = <fn:fib> @7fa2245b1a20
	_fib = <fn:_fib> @7fa2245b1ac8

Для переменных и функций в Си нужно указание типов (в других языках -- системы типов это религия)

class Type(Meta): pass

int = Type('int') ; print(int)
void = Type('void') ; print(void)

<type:int> @7fa2245b1cc0

<type:void> @7fa2245b1d30

Для генерации кода из функций нам нужно указать какой тип они возвращают, и какие параметры принимают на вход:

• атрибутом ret обозначим слот возвращаемого типа
• attr указывает на сигнатуру функции: набор параметров ()
  () возвращаемый тип иногда включают, или не включают в сигнатуру

fib['ret'] = int ; _fib['ret'] = int
int_n = Var('n') ; int_n['type'] = int
fib['attr'] = int_n ; _fib['attr'] = int_n

fibonacci.plot()

Уже на этом этапе видно, что обе фунции имеют одну и ту же сигнатуру вызова.

Можно инициализировать по другому, разделяя параметры с одинаковым именем, для каждой функции:

int_n = Var('n') ; int_n['type'] = int
fib['attr'] = int_n
int_n = Var('n') ; int_n['type'] = int
_fib['attr'] = int_n

fibonacci.plot()

Так как для одного и того же параметра n мы создаем два разных экземпляра Var с одним и тем же значнием, на выводе граф имеет две ветки.

Генерация кода

Программировать в полу-визуальном стиле на графах приятно, но практические требования не позволяют использовать EDS-интерпретатор везде где хочется. Например, на встраиваемых системах у нас может просто не оказаться достаточного объема ОЗУ, даже просто чтобы разместить в нем граф программы (типичный объем ОЗУ 8-20К на всю прошивку и размещение рабочих данных).

Другая проблема -- ограничения на используемые методы программирования и языки. Вам могут просто не разрешить использовать малоизвестные техники программирования, и писать код только на одном языке (embedded C), понятный любому студенту, видевшему программы только на лабораторных работах в ВУЗе.

Генерация кода на embedded C

Хорошим решением, позволяющим обеспечить совместимость, соблюсти ограничения, и при этом не отказываться от мощных удобных технологий, может стать генерация кода на С(++). Для такой генерации нам нужно создать подмножество объектов, которые работают как компоненты выполнымых графов, но одновременно способны представить себя в виде исходного кода на выбранном языке программирования.

# язык программирования
class Lang(Meta): pass

# элемент синтаксиса языка ANSI C'89: кодо-синтезирующее дерево классов
class C89(Lang): pass

Для универсальности выбран самый старый и распространенный диалект Си, компилятор для которого можно найти для любой самой редкой или специфичной платформы. В программировании для микроконтроллеров, кроме GNU GCC, часто используют коммерческие компиляторы, иногда очень старых версий, со своим пониманием стандартов языка и т.п.

# функция
class Fn(Fn,C89): pass

Fn('main')

<fn:main> @7fa22460b278