MetaL

Добавить ссылки
Материал из Викиучебника — открытых книг для открытого мира

metaL: гомоиконичный интерпретатор[править]

глава из сборника: Реализация языков программирования

(с) Dmitry Ponyatov <mailto:dponyatov@gmail.com>

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

Фрейм[править]

Язык metaL построен на базе фреймов Марвина Мински [minsky], которые были расширены возможностью хранить упорядоченный набор вложенных элементов -- необходимое свойство для представления программ на любых языках программирования в виде атрибутных грамматик и AST-деревьев. Внутренняя модель и семантика языка наиболее близки языку FORTH (Форт), из которого убраны все низкоуровневые элементы (прямая адресация памяти, машинные числа на стеке), и наоборот добавлены объекты как базовый элемент языка. Объектизация Форта позволяет реализовать виртуальную машину metaL на любом современном императивном языке программирования напрямую, не вводя лишние слои такие как эмуляция образа памяти, стек целых чисел и байт-код. 

class Frame:

    def __init__(self,V):

        # тэг типа/класса (необходим для лексера -- библиотека PLY)
        self.type = self.__class__.__name__.lower()

        # имя фрейма или скалярное значение (число, строка,..)
        self.val  = V

        # слоты = атрибуты = ассоциативный массив = словарь (Форт)
        self.slot = {}

        # универсальный упорядоченный контейнер = вектор = стек (Форт)
        self.nest = []
  • .type поле требуется библиотекой-генератором парсеров PLY для всех объектов, которые она может рассматривать как токены при лексическом анализе
  • .val используется как имя фрейма, или для хранения атомарных данных типа чисел и строк
  • .slot атрибуты фрейма, являются символическими ссылками на другие фреймы, и одновременно формируют ребра направленного (гипер)графа.
  • .nest хранит упорядоченный набор фреймов, и представляет одновременно стек, вектор переменной длины, и очередь

Гомоиконичные языки программирования[править]

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

В гомоиконичном языке метапрограммирование это основная методика разработки ПО, использующаяся в том числе и для расширения языка до возможностей, нужных конкретному программисту.

В качестве первого примера всегда приводится язык Лисп, который был создан для обработки данных, представленных в форме вложенных списков. Лисп-программы тоже записываются, хранятся и выполняются в виде списков; в результате получается, что программа во время работы может получить доступ к своему собственному исходному коду, а также автоматически изменять себя «на лету». Гомоиконичные языки, как правило, включают полную поддержку синтаксических макросов, позволяющие программисту определять новые синтаксические структуры, и выражать преобразования программ в компактной форме.

Текстовый дамп[править]

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

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

print(Frame('Hello World'))
print(Frame('Hello World').dump(prefix='prefix = '))

<frame:Hello World> id:7f89f8536fd0

prefix = <frame:Hello World> id:7f89f8536f60

<T:V> заголовок состоит из следующих элементов:

  • T тэг типа/класса, по идее это должна быть ссылка на класс, но из-за требований библиотеки PLY используются строки
  • V скалярное значение: имя фрейма, число, строка,..
  • prefix имя слота
  • idx целочесленный индекс фрейма в упорядоченном контейнере
  • id:hex уникальный указатель для каждого объекта в системе: позволяет отличить два разных фрейма с одинаковым типом и именем

Отрисовка гиперграфа[править]

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

from graphviz import Digraph

class Frame(Frame):
    
    ## отрисовка гиперграфа
    
    # рекурсивный обход с вызовами библиотеки graphviz
    def plot(self,dot=None,parent=None,link='',color='black'):
        
        if not dot: # в корне рекурсии необходимо инициализировать плоттер
            dot = Digraph(graph_attr={'rankdir':'LR'}) # горизонтальная ориентация
            Frame._plot = []                           # в уже отрисованные ветви не ходим
            
        # отрисовка текущего узла графа и ребра от узла-родителя / аналогично .dump/header /
        dot.node('%s'%id(self),label='%s:%s'%(self.type,self._val())) # ссылки на узлы через id()
        if parent: dot.edge('%s'%id(parent),'%s'%id(self),label='%s'%link,color=color)
            
        # останов бесконечной рекурсии при наличии циклов
        if self in Frame._plot: return dot
        else: Frame._plot.append(self)
            
        # slot{} слоты отрисовываем синими ребрами с именем слота
        for i in self.slot: dot = self.slot[i].plot(dot,parent=self,link=i,color='blue')
            
        # nest[] вложенные элементы -- зелеными ребрами с индексом
        idx = 0
        for j in self.nest: dot = j.plot(dot,parent=self,link=idx,color='green') ; idx += 1
            
        # возвращаем объект отрисовки в предыдущую ступень рекурсии
        return dot

Frame('Hello World').plot()

Операторы[править]

Для манипуляции фреймами на уровне языка реализации (Python) нам надо переопределить несколько операторов, которые мы будем использовать при комбинировании фреймов. 

class Frame(Frame):
    
    ## операторы

    # автоматическое приведение типов
    def cast(self,that): return that
    
    # ` A[key] ` получить фрейм по имени слота (Форт -- поиск/чтение из словаря)
    def __getitem__(self,key):
        return self.slot[key]
    
    # ` A[key] = B ` создать/изменить слот по имени (Форт -- запись в словарь)
    def __setitem__(self,key,that):
        self.slot[key] = self.cast(that) ; return self
    
    # ` A << B ` запись в слот по типу операнда: A[B.type] = B
    def __lshift__(self,that):
        that = self.cast(that) ; self[that.type] = that ; return self
    
    # ` A >> B ` запись в слот по значению операнда: A[B.val] = B
    def __rshift__(self,that):
        that = self.cast(that) ; self[that.val] = that ; return self
    
    # ` A // B ` затолкнуть фрейм в nest[] как в стек
    def __floordiv__(self,that):
        self.nest.append(self.cast(that)) ; return self

hello = Frame('Hello') // Frame('World')
hello['some'] = Frame('slot')
hello['self'] = hello // hello
hello << Frame('<<') ; hello >> Frame('>>')
print(hello) ; hello.plot()

<frame:Hello> id:7fb268519a90
	>> = <frame:>>> id:7fb268519470
	frame = <frame:<<> id:7fb26859c3c8
	self = <frame:Hello> id:7fb268519a90 _/
	some = <frame:slot> id:7fb268519f98
	0: <frame:World> id:7fb268519dd8
	1: <frame:Hello> id:7fb268519a90 _/

Ссылки[править]

[minsky]
Marvin Minsky A Framework for Representing Knowledge 1974
Марвин Минский Фреймы для представления знаний М.: Мир, 1979

[lutz]
Mark Lutz Programming Python, 4th Edition O'Reilly 2019
Марк Лутц Изучаем Python. Том 1 М.: Вильямс, 2019 ozon

Источник — https://ru.wikibooks.org/w/index.php?title=MetaL&oldid=158759