Картинки из квадратов \ Презентация \ У нас, советских, собственная гордость, и наш комбинатор -- это B! \

12.8.2. Размеченные деревья и отвечающие им паттерны типов деятельности

 
Начало см. здесь.
Можно сделать предположение, что паттерн полного бинарного дерева, будучи сам по себе некоторой абстрактной математической конструкцией, обладает вместе с тем значительной "моделирующей силой". И что он существует очень давно (существует столько, сколько существует сама математика). Поэтому этот универсальный, вневременной и внепространственный паттерн очень выгодно изучать. Ведь он не устареет никогда: был, есть и будет.
Ниже я хочу обосновать, что изучение этого древовидного паттерна можно естественным образом проводить в рамках УСК, который и задумывался его создателем для описания некоторой "универсальной модели мира". Причем можно будет задействовать самые элементарные фрагменты УСК, начиная с Базового УСК степени 2.

2. Простейший случай Базового УСК степени 2
"Реальная" цепочка из Базового УСК степени 2 ассоциируется с определенным образом размеченным полным бинарным деревом следующим образом:
Это размеченное дерево имеет очевидную и интуитивно хорошо понятную "автоматную" интерпретацию. "Функциональная" цепочка из Базового УСК степени 2 ассоциируется с полным бинарным деревом, которое размечено уже несколько по другому:
Здесь метками дуг являются символы эндоморфизмов φV и φH, смысл которых разъясняется здесь: http://dxdy.ru/topic94428-780.html (постинг от 24.12.2016 на странице по указанной ссылке). Также метки вершин на втором уровне этого размеченного дерева расположены несколько в ином порядке по сравнению с размеченным деревом, приведенным выше.
"Реальная" цепочка описывает простую деятельность, заключающуюся в прямолинейном, без прерываний, движении от корня дерева к его некоторому листу. Тогда как "Функциональная" цепочка описывает более сложную деятельность, когда при движении от корня дерева к его некоторому листу возникает прерывание, которое нужно правильно обработать. В целом ситуация хорошо описывается словами из Ахо-Хопкрофта-Ульмана: Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке.
Чтобы сделать эти интуиции более понятными, применим и для простейшего случая Базового УСК степени 2 методологию типизации универсума и типизации языка, которая для общего случая Базового УСК степени n была намечена здесь:
... В основе этих теорий лежат две идеи: типизация универсума и типизация языка. Смысл первой в том, что интуитивно обозримый универсум должен строиться обозримыми шагами, исходя из (одного или нескольких) базисных типов (классов) объектов, и на каждом шаге построения строительным материалом для новых типов служат типы, полученные на предыдущих шагах.
Суть второй идеи в том, что эта иерархия типов должна явно выражаться в (формальном) языке, на котором формулируются утверждения рассматриваемой теории, т. е. типы должны явно приписываться переменным, константам и другим правильно построенным выражениям этого языка.
Реализация этой идеи для Базового УСК степени 2 была начата мною здесь. Там базовые типы названы "базовыми категориями", а их отражение в формальном языке — "категорными именами". Теперь продолжим реализацию этой идеи для Базового УСК степени 2, введя в рассмотрение наряду с "реальной" цепочкой также еще и "функциональную" цепочку . Эти две цепочки связаны между собой важной связью, называемой "законом (или правилом) транспозиции".

3. Рассмотрение цепочек Базового УСК степени 2
с использованием типовых переменных
"Реальная цепочка" из Базового УСК степени 2 будет записываться с использованием типовых переменных следующим образом:
Интуитивный смысл типов, которые приписываются здесь переменным реальной цепочки, определяется интуитивным смыслом локусных имен из рассмотренного ранее исчисления локализованных цепочек. Эта типизированная реальная цепочка ассоциируется с размеченным полным бинарным деревом так:
Конкретные деятельности, соответствующие данному паттерну "реального" типа деятельности, можно изобразить на понятных картинках.
"Функциональная цепочка" из Базового УСК степени 2 будет записываться с использованием типовых переменных следующим образом:
Она ассоциируется с размеченным полным бинарным деревом так:
Здесь уже в самом простейшем виде реализуется случай, описанный у Хиндли: Их (лямбда-исчисления и комбинаторной логики) главная особенность заключается в том, что они являются языками высших порядков, входные и выходные значения которых также могут быть операторами.
Как уже отмечалось, Универсальный Семантический Код (УСК) является системой до некоторой степени похожей на комбинаторную логику. В частности, символ "звездочка" в цепочках УСК-4 обозначает операцию "действия", по своему смыслу аналогичную операции аппликации в комбинаторной логике.