Мета-Переводчики: реальность или фантастика?

Сложный

21 мин

1.9K

Программирование*Математика*Изучение языков

Туториал

Преамбула

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

Вот уже ~10,5 лет я работаю над проектом Мета-Переводчика. Да, это, возможно, прозвучит слишком грандиозно, но я заявляю, что все эти годы развивалась теория перевода с "человеческого языка" на компьютерный (подробно о понятии "Языка" - ниже). Но не спешите сразу ставить крест на этих стараниях и говорить о сложности GPT! Дочитайте статью до конца! Строго говоря, GPT и Мета-Переводчик - это взаимо-перпендикулярные вещи. Чтобы сбавить амбициозность, скажу, что все дело в определениях - что именно мы считаем "Языком".

Имеется в виду не просто естественный язык или Язык Программирования (ЯП), - рассматривается лишь их обобщенная модель (почти как в Теории Автоматов и грамматик). Поэтому речь не идет о магическом превращении воды в вино и всякой фразы со сложными речевыми оборотами в идеально реализованный код. Мета-Переводчик - это метод универсального перевода с математического языка на математический язык (определения ниже).

Сколько я занимаюсь этим проектом, столько убеждаюсь, что при его презентации зрители начинают ожидать от Мета-Переводчика чего-то такого, чем он на самом деле не является (хотя иногда это наоборот играет на руку). Ведь и правда, при словах "переводчик с человеческого языка на компьютерный" проще всего представить себе какую-то магическую машину, после чего уже практически невозможно поверить в её реализуемость. На деле задача звучит куда уже. Возможно, вина этой иллюзорности первого восприятия, - в моей непоследовательности при описании сути проекта, и мне следует начинать делать это с других позиций. Эта статья - очередная попытка это сделать. Если вам покажется, что это так, и вы знаете, как это сделать лучше - пишите в комментарии.

Зачем я пишу эту статью?

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

Во-вторых, все с той же целью, с которой я пишу большинство своих статей на Хабре - не только "себя показать", но и "на других посмотреть". Даже из полного разгрома статей я стараюсь извлекать пользу.

Да, я знаю, что 10 лет - это большой срок. И да, звучит очень самонадеянно, что вот уже 10 лет у меня нет полностью окончательно готового кода. Но не смотря на все это, я очень надеюсь на здравую критику, а не что-то в духе "ты вообще не понимаешь, как это работает, это неподъемная задача" еще перед тем, как вы дочитаете статью до конца. Если у вас есть такое желание, прошу - проходите мимо. Если же у вас есть опыт, которым вы можете поделиться, - делитесь и приводите ссылки. Для меня это важно, так как я стараюсь собрать максимум информации.

Я регулярно являюсь свидетелем вечного спора: кто должен опустошать свою чашу: я, как разработчик, или те, кто подключаются к проекту? С моей стороны это нужно, чтобы в моей речи не было чего-то типа "моя технология не имеет ничего общего со всеми этими вашими". Со стороны приходящих - чтобы не отвергать новую технологию с первого же громкого слова. В идеале процесс опустошения должен быть взаимным, но на практике, сколько я наблюдаю, процесс скорее взаимообратный. Каждый стремиться быть понятым и исключительно со своим, что в результате не приводит ровно не к чему.

Собственно, поэтому я и взялся писать эту статью - чтобы окончательно подвести черту в этом споре.

Разумеется, я не против опустошать свою чашу, и занимаюсь этим не первый год. Долгое время я штудировал книги по компиляторам, пока не понял, что копаю не в ту сторону (тоже результат!) - Мета-Переводчик - это не ЯП. А также это не нейронная сеть и не переводчик с одного естественного языка на другой. Опять же, теперь мне не вполне ясно, куда копать дальше, - еще одна причина написать на Хабр.

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

Об аналогах

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

Забегая вперед, я буду рассматривать лишь биективный перевод (см. далее). По сути это значит, что каждой фразе на языке обязательно соответствует одна и только одна фраза на языке (другие варианты тоже рассмотрим, но вскользь). И теперь, когда я произнес слово "биекция" (проще говоря, о взаимо-однозначном соответствии), уместно провести аналогию: использовать GPT, равно как и другие нейросети, кошек ли от собак они отличают или что-то еще, сродни выстрелу шрапнели. Абы какая попадет? (может даже, и не одна) К слову, в математике даже есть метод интегрирования площади по вероятности случайного её заполнения точками, и наоборот.

Моя же технология сродни выстрелу из снайперской винтовки. Но!

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

Имеет место завершить мысль цитатой Яна Ле Куна:

,,Пытаться построить интеллектуальные машины путём масштабирования языковых моделей — всё равно что строить высотные самолёты для полёта на Луну. Вы можете побить рекорды высоты, но полёт на Луну потребует совершенно другого подхода"

Именно поэтому я и работаю над своим решением.

К слову, я уже писал статью о нотациях и моделях с Машинами Тьюринга, данными которой буду пользоваться ниже.

Задача

Перед пониманием Мета, определим сначала, что такое сам переводчик. А для него надо дать определение Языку, а также его фразам. Понятие Языка можно взять из Теории Автоматов со всяческими множествами терминальных и нетерминальных символах, но мы максимально упростим этот момент:

Пусть фраза $P(A)\in L$ на Языке - некоторая последовательность из символов $\alpha_i \in A$ некоторого алфавита (обычно конечного) некоторой длины (в общем случае не обязательно конечной - в этом случае мы жертвуем лишь фактом завершения моего алгоритма).
$P(A)=\bigcup_{i=1}^{N\le\infty}(\alpha_i\in A\subset \mathrm{N})$
Пусть Язык - это такое множество фраз $P(A) \in L$ , которые принадлежат Языку по тем или иным причинам (задано вручную ли или правилами)
$L=\bigcup_{i=1}^{N\le\infty}P_{i}(A)$
Пусть есть Язык и Язык . Как множества они могут быть разного размера ( $|X|\neq |Y|$ ), но мы ограничимся одинаковым. Равные по числу фраз Языки могут быть трех типов. Не мудрствуя лукаво, так и станем их называть:
-Сюръективные
-Инъективные
-Биективные
Биективность Языков означает обязательную возможность построения соответствия каждой фразе Языка одной и только одной фразы Языка . Такое построение может быть не одно. Для того, чтобы увидеть все такие построения, достаточно построить табличку $X\times Y$ (Декартово произведение двух множеств). Технически, раз нам точно известна равномощность и, можно было бы записать $X\times Y = X \times X = Y\times Y$ , но я буду писать именно $X\times Y$ , чтобы помнить, о каких именно множествах (Языках) мы говорим.
Далее нас будет интересовать лишь последний пункт - равномощные и биективные Языки. Хотя, да, конечно, справедливости ради, стоит рассмотреть и первые два случая (не взаимо-однозначные построения соответствий), но сегодня я этого делать не буду.
Переводчик с Языка на Язык - это такой набор правил , который по одному и тому же алгоритму переводит (приводит соответствие) каждую фразу Языка на соответствующую в . При этом в дальнейшем мы будем считать обязательным условием, что множество правил всегда конечно, а множества фраз в и могут быть бесконечными.
$T(X,Y) = \bigcup_{i=1}^{N<\infty}(R_i\in X\times Y)$
Рассмотрим множество всех возможных Языков . Разобьем их на все возможные пары $L'\times L'$ . Для каждой из них требуется построить метод перевода . Прошу не забывать, что в этой табличке также встречаются "самопереводы", то есть перевод с языка на самого себя (главная диагональ). Впрочем, в их случае переводчик вырождается в тривиальные повторы каждой фразы.
Теперь рассмотрим все такие переводчики (очевидно, их бесконечное число). Важно!: каждый переводчик является конечным, и, что куда более важно, универсальным - то есть каждая фраза переводится одним и тем же набором правил. Если нам удалось определить Алгоритм, задающий любой переводчики по одному и тому же методу, то есть ко вполне бездумному алгоритму, нам удалось построить Мета-Переводчик . Это и есть основная задача:
$M=\bigcup_{i=1}^{|L'|^2=|L'\times L'|}\bigg((T_i\in (L'^{\text{ }\times2}=L'\times L')\bigg)$
Напомню, что о нотации, в которой написаны формулы выше, можно прочесть в моей предыдущей статье. Я имею в виду эти интересные виражи со знаком внутри . Также напоминаю, что все такие формулы заменяют программный код и эта нотация столь гибка, что можно даже описать Машину Тьюринга!

Теоретическое мат.-решение

Нам потребуется следующий инструментарий:

"переставлялка"
дополнение контекста
исключение контекста
"клонирование подстрок"
"деклонирование подстрок"
"контексто-сжималка"
"контексто-разжималка"

Я не гарантирую абсолютно, что такого инструментария хватает для того, чтобы создать Мета-Переводчик, тем не менее, интуитивно мне кажется, что это так. Разумеется, это требует строгого доказательства, но пока позвольте ограничиться лишь описанием моего решения.

Для примеров возьмем практическую задачу, которую в том числе можно решать при помощи Мета-Переводчика - преобразование математических выражений. Преобразование может происходить не за один шаг, то есть между Языками и могут быть другие "переходные".

Условимся о синтаксисе примеров: я буду приводить этапы преобразования-отладки фраз - самая первая - на Языке , самая последняя - на .

Итак, самый основной трюк - "перетасовка" ("переставлялка"):

3=5-y
y=5-3

Здесь одни и те же части строки - числа и переменная - встречаются в первой и в последней её версии в разных местах - их "перетасовали".

Сразу приведем пример дополнения и исключения контекста:

-y+3=5
y-3=-5

Здесь основные составляющие строки остались на своих же местах, но некоторые подстроки появились или исчезли. Так знак между и заменился на , и (что не мало важно!) знак перед заменился на пустую строку, а пустая строка перед заменилась на знак . Поэтому важно понимать, что правила нашего Переводчика могут пользоваться Алфавитом, одним из символов которого может быть пустая строка.

Перетасовка может "клонировать" подстроки:

y=3*4
y=3+3+3+3

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

Или же мы можем наоборот "деклонировать":

y=3+3+3+3
y=3*4

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

Отмечу также, что "клонирование" и "деклонирование" могут сопровождаться друг другом одновременно. Сейчас будет немного сложный для понимания пример, если вы не знакомы с темой вот этой моей статьи (сама статья скорее обзорная, чем методологическая). Одновременное "клонирование" и "деклонирование" подстрок можно хорошо видеть в преобразовании A- и B-частей двух коммутаторов для кубика Рубика 3х3х3:

[M2,U2]
M2 U2 M2 U2
[U2,M2]

Здесь коммутатор разлагается на составляющие ("клонирование"), после чего они объединяются иначе (работает "переставлялка") и сокращаются ("деклонирование") в иной столь же короткий коммутатор.

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

Точно таким же трюком "клонирования-деклонирования" можно, например, доказать ассоциативность некоторых объектов - например матриц:.

Прошу заметить: доказательство будет строго алгоритмическим, а значит, годным и для шаблонного доказательства и некоторых других Теорем! Это решает ту проблему, что часто доказательства в математике используют непредсказуемые "финты ушами" - вроде замены переменной, доказательства от обратного или по индукции. Ведь и правда, при таких видах доказательства требуется сначала "догадаться" до решения, далее предположить, что решение корректное и уже после этого попытаться его доказать. Мета-переводчик же можно обучить перебирать эти методы, но невозможно обучить "догадываться" до решения. В этом и плюс и минус: минус - в том, что некоторые Теоремы останутся для Мета-переводчика непостижимыми и нужны иные методы решений. Плюс - в том, что многие другие доказательства можно будет проводить вполне бездумно, по шаблону. Возможно даже, среди последних Теорем окажутся и те, которые до сих пор еще не доказаны по тем или иным причинам!

Остается разобрать два последних инструмента: "контексто-сжималка" и "контексто-разжималка".

Первое создано для объединения некоторых подпоследовательностей (в том числе бесконечных) в другие (конечные). По сути "контексто-сжималка" - это переменная-название некоторой подстроки, более короткое, чем сама эта подстрока. Второе же разжимает контекст после того, как его "перетасовали". Рабочая схема такая:

сжать
переставить
разжать

Таким образом, полезное свойство "сжималок" - ускорение процесса перевода за счет того, что переставляются более короткие подстроки.

Рассмотрим комбинированный пример из совокупности "контексто-сжималок/разжималок" и "переставлялки":

12 + 12
...
number + number
2*number
2*12

Этот пример отличается от первого примера "переставлялки" тем, что переставляются не единичные символы, а объединенные в своего рода "нетерминал" (см. теорию Автоматов).

Реализация

ПАРУ СЛОВ О ТЕХНОЛОГИИ И ПРОТОТИПАХ:

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

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

Нам потребуются 4 вида карточек:

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

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

Визуально работу алгоритма с карточками можно представить как зацикленный алгоритм из двух пунктов:

Разбиение строки на подстроки, как бы наложение на них карточек, которые отпечатывают и копируют на себя, как переводная картинка, то, что написано под каждой из них
Переворот всех карточек на обратную сторону и возврат к п.1

Проблема останова алгоритма на данном этапе развития теории проекта все еще представляет опасность. Я перепробовал и продолжаю пробовать, (прямо как Эдисон:-), огромное число разных версий алгоритма, и в разных его версиях эта проблема "играет" по своему. Ударяясь чуть глубже в технологию, скажу, что это может зависеть, например, от порядка выполнения пунктов выше: либо мы сначала разбиваем всю строку от начала до конца на "карточки" и затем производим все замены (переворачиваем карты), либо выполняем замены сразу в процессе разбиения строки на подстроки - нашли карточку - тут же перевернули. Это еще не все - в этом случае после переворота мы можем вернуть бегунок в начало строки или продолжить алгоритм до конца строки, но и это еще не все! Далее либо остановиться, либо начать еще раз с начала. Критерий останова циклов пробега по строке в этом случае тоже варьируется. Как показала многолетняя практика, первый вариант порождает, пожалуй, максимальное число проблем. Хотя, все может быть, и именно этот вариант может навести в правильное русло...

На самом же деле максимально рабочий алгоритм оказывается весьма сложнее для приведения его полностью здесь и заключается примерно в том, что надо искать карточки

по близости вхождения
по его (вхождения) длине

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

О ПРАВИЛАХ:

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

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

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

Приведем простой пример (пишу фразы на Языке слева от $\to$ и на Языке - справа):

0 -> 1
1 -> 2
2 -> 3
...

Это простейший и наглядный пример перевода бесконечного числа фраз через конечное число правил, а точнее, всего с одним:

$R_0=\bigg(P_Y(\alpha)=P_X(\alpha)+1\bigg)$

Это правило следует читать так: нулевое и единственное правило заключается в том, чтобы к фразе из Языка прибавить единичку и получить тем самым фразу на Языке . Напомню о том, что прочесть про этот хитрый вираж с внутри можно тут. Этот трюк позволяет записывать формулы более лаконично, я уж молчу о разнице длины неформального словесного определения и математического.

НЕСКОЛЬКО "НАУЧНЫХ МЕТАФОР":

Сравнение:
Переводчик можно условно назвать "обратным автоматом".

Пояснение:

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

Сравнение:
Если переводчик можно назвать "обратным автоматам", то карточки с правилами очень похожи на "обратный словарь".

Пояснение:

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

Сравнение:
Если переводчик - это "обратный автомат", а сама карта - это "обратный словарь", то имя любой карточки - и есть та самая часть "переставлялки", которую мы сравнивали с нетерминалом.

Пояснение:

Именно поэтому имена карт никак не проецируются внутрь обрабатываемой фразы, - так как нетерминал - абстракция кода.

ПРИМЕРЫ:

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

Напомню, что их вид определяется переводчиком автоматически.

И снова условимся о синтаксисе примеров: часть строки в коде до знака - имя карточки ("нетерминал"), а все после в $[ квадратных \text{ } скобках ]$ - значения через запятую.

Обычная карточка - это правило вида "имя": "значение":

digit = [1,2,3,4,5,6,7,8,9,0]

Обычную карточку переводчик автоматически распознает по тому её свойству, что ни её имя не встречается ни в одном значении, ни, наоборот, никакое значение на входит в имя.

Таким образом мы можем преобразовать любую цифру в некую переменную типа "digit" (цифра, пока не число!).

Самоссылка позволяет объединять подпоследовательность любой длины до карточки с одним конечным именем.

number = [digit digit, numbеr digit, digit number, number number]

Самоссылка распознается по тому свойству, что её имя входит в одно или несколько значений. То есть такая карточка как бы ссылается на саму себя - потому и самоссылка.

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

Здесь мы как раз касаемся того опустошения чаш, о котором шла речь в начале статьи: здесь нет никакого ухода в право- или левостороннюю рекурсию! Это совершенно не та технология, хотя с первого взгляда и похожая (даром, что "нетерминалы").

Упрощенный пример случая, который мы разбирали выше

12 + 12
digit2 + 12
...
digit digit + digit digit
...
number + number
...

Шаблоны - это карточки, в которых используются наши "нетерминалы" и которые перетасовываются от фразы на одном Языке к другому. Также может работать "клонирование-деклонирование" и может дополняться или исключаться контекст.

Пример:

2*number = number + number

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

Шаблон распознается автоматически при соблюдении условия: и в правой, и в левой части есть один и тот же "нетерминал".

В рамках одного шаблона может быть использовано неограниченное конечное количество разных "нетерминалов". Вот пример чуть сложнее - два разных "нетерминала": и :

2*(number+word) = number + number + word + word

Важно!, что, если number или word внутри правила - не имена карточек, то есть не "нетерминалы", то эти вхождения в шаблон - не более, чем просто набор символов. Настоящая магия произойдет лишь в обратном случае.

А конкретно магия будет такой:

ПРАВИЛА:
digit = [1,2,3]
number = [digit digit, number digit]
2*number = number + number

ПРЕОБРАЗОВАНИЕ СТРОК:
123 + 123 
... 
digit digit digit + digit digit digit
...
number + number
2*number
2*123 //!!!

Магия заключается в том, что контексто-разжималка, встроенная в алгоритм переводчика, в конце всех замен возвращает контекст - первоначальные значения, скрывающиеся за именами "нетерминалов". Но только в том случае, когда все эти значения-контексты под всеми одинаковыми "нетерминалами" одинаковы! Если же встречается иное значение под "нетерминалом" хотя бы в одном месте, переводчик обязан сообщить о коллизии и выкатить лог с ошибкой.

Наглядный пример коллизии с теми же правилами, что и выше:

12 + 21 //!!!
digit2 + 21
...
digit digit + digit digit
...
number + number
2*number
2*??? //на что менять: на 12 или 21?..

И наконец, айдишники (идентификаторы).

Айдишник осуществляет дополнение к "перетасовке".

Рассмотрим такую ситуацию: у нас есть два "нетерминала"и два его значения: и . Пусть нам хочется свапнуть эти подстроки, но при этом быть полностью уверенными в том, что обе из них являются, а не чем-то еще (например, ). Как нам это сделать?

ПОПЫТКА 1:
number + number

ПОПЫТКА 2:
number1 + number2

ПОПЫТКА 3:
number1 = digit digit
number2 = digit digit

Первая попытка, очевидно, не может помочь ничем - оба ни чем не различимы, а значит, при попытке запихнуть в них два разных числа и , по тому же принципу, на последнем этапе перевода - разжимании - получим коллизию. Значит нам надо научиться как-то нумеровать "нетерминалы" без потери их определений.

Делать это, как в попытке 2, тоже нельзя - ведь тогда "нетерминалом" останутся , а и будут распознаваться как контекст.

Еще можно попробовать (попытка 3) построить сюръективное правило (попытка 3). Мы как бы говорим "а еще идущие подряд цифры $digit \text{ } digit$ - это не только - но и !" Но тогда мы рискуем получить ошибку, по-хорошему, еще до запуска переводчика - так как при его запуске станет неясно, на какой из двух "нетерминалов" нам заменять $digit \text{ } digit$ - на или на? По-хорошему, переводчик должен отлаживать проблему останова сам, до запуска, но это не всегда возможно...

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

Синтаксис айдишника представлен ниже:

Переменная-счетчик для айдишника:
number = i

Задача айдишника тут:
number_i = number

Шаблон:
number_1 + number_2 = number_2 + number_1

Первым делом мы объявляем переменную-счетчик, говоря, что она является . Далее создаем сам айдишник и объявляем, что "нетерминал" с последующим после него индексом - это тоже "нетерминал" . При этом единственное телодвижение, которое необходимо совершить, чтобы переводчик понял, что данное правило - айдишник, а не очень похожая на него по синтаксису самоссылка, - это переставить местами части правила. Чуть подробнее: в самоссылке её имя встречается в значениях (потому и самоссылка - она ссылается на саму себя), а в айдишнике все наоборот - значение полностью входит в имя.

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

На данный момент это порождает огромнейшую проблему. Так как при удалении всего одной карточки, например,

number = [1,2,3,4,5,6,7,8,9,0]

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

2*number = number + number

или айдишник

number_1 + number_2 = number_2 + number_1

могут перестать быть шаблоном и айдишником из-за того, что теперь их подстрока перестает быть "нетерминалом". Сейчас я предпочитаю решать эту проблему тематическим объединением карточек в небольшие библиотеки.

Но если все хорошо, переводчик может убедиться в том, что подпоследовательности и является при том, что переводчик "помнит", что эти имели разные индексы, а значит не обязательно должны содержать одинаковые числа.

И о, ура, теперь мы можем свапнуть два числа без коллизий! (а также мы можем делать любые другие безнаказанно страшные комбинированные преобразования).

КРИТЕРИЙ ЗАВЕРШЕННОСТИ МЕТА-ПЕРЕВОДЧИКА

Разумеется, следует задаться вопросом, как убедиться в работоспособности переводчика? Как быть уверенным, что он переводит с любого мат.-языка на любой аналогичный? Долгое время я считал, что для этого надо строить аналог Машины Тьюринга, как и в случае с большинством ЯП (проверка Тьюринг-полноты), но в нашем случае это, к сожалению не сработает. Не сработает именно потому, что разрабатываемый математический переводчик - это не нейронная сеть, не некий вспомогательный язык программирования (как я долго ошибочно считал) и не переводчик с одного естественного языка на другой.

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

Поэтому нам нужен какой-то новаторский метод оценки степени завершенности Мета-переводчика, и, если честно, я до сих пор пока радикально не сдвинулся в этом вопросе... Поэтому, строго говоря, я не могу быть до конца уверенным, что проект Мета-переводчика вообще исполним в полной мере. Хотя строить отдельные переводчики с конкретного Языка на конкретный Язык у меня получается достаточно хорошо.

Практическая польза

Мета-переводчик особенно полезен в том числе в алгебре. Давайте вспомним то, с чего мы начинали - определение фразы на Языке:

Фраза Языка - это некоторая последовательность символов некоторого алфавита.

При этом и алфавит, и сама фраза могут быть бесконечными. Я приведу 4 примера, где именно этот трюк может сильно пригодиться. Помимо этого будут еще примеры.

Да, возможно, я не скажу ничего принципиально нового и не выдам революционный метод доказательств, как Леонард Эйлер, но, как минимум, эти примеры позволят вам посмотреть на уже известные в математике формулы под другим углом.

Факториал и похожие комбинаторные базовые функции.
Например, можно посчитать количество ориентаций обычного кубика Рубика в пространстве:
Ориентируем вверх некую грань. Всего 6 вариантов. Далее прибьем гвоздями к пространству соседнюю к ней. Таких 4, так как нижняя грань всего будет оставаться снизу.
Можно рассмотреть более сложные примеры - скажем, число ориентаций в пространстве для додекаэдра или икосаэдра. Здесь нам поможет построение фразы некоторой длины из алфавита, состоящего из обозначений всех граней. При этом на эту фразу накладываются некоторые ограничения - а именно невозможность использовать некоторые символы в некоторых случаях. Так для факториала нельзя использовать повторно уже использованные символы. Для примера с ориентацией правильного политопа ограничения будут посложнее.
Сумма натурального ряда $\mathrm{N}$ .
Да, это звучит несколько парадоксально, но эта сумма $=-\frac{1}{12}$ . Если не верите, поищите во всемирной сети, об этом довольно много разных объяснялок. Но как именно тут применять силу Мета-переводчиика?
Зададим бесконечный алфавит из всех натуральных чисел. Тогда каждое слагаемое этого ряда является символом данного алфавита (- это тоже один символ). И о чудо! Теперь у нас в руках вся мощь Мета-переводчика: например, можно использовать "переставлялочку", группировать символы, далее менять группировку и получать новый ответ. Такими преобразованиями и можно доказать эту теорему. Еще раз напоминаю об автоматизации таких доказательств - переводчику не надо ни до чего "догадываться".
Но есть еще один трюк, который мы только что провернули, и который сильно пригодится нам далее: чтобы задать бесконечный алфавит, мы построим дополнительный Язык-утилиту с единственным рекуррентным правилом, задающем весь натуральный ряд.
Бином Ньютона. Напомню формулу:
$(a+b)^n = \sum_{i=1}^{n}C_n^i*a^{n-i}*b^i$
В данном случае применяется комбинаторная функция "сочетания" или, говоря иначе, "биномиальный коэффициент". Если построить все значения этой комбинаторной функции (коэффициенты бинома), можно легко получить треугольник Паскаля:
И снова, мы можем использовать Язык-утилиту для того, чтобы построить бесконечное множество чисел треугольника Паскаля, чтобы объявить их все символами алфавита для перевода фразы в конкретное значение фразы
$\sum_{i=1}^{n}C_n^i*a^{n-i}*b^i$
для конкретного .
И наконец, самый красивый пример: полином Белла. Это такое расширение бинома Ньютона, только не для двух (бином) букв-переменных под степенью, - а для произвольного числа таких переменных.
Позвольте я немножко похулиганю и скопирую текст из википедии (ссылки ниже).
${\displaystyle B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}=$
$\sum {n! \over j_{1}!j_{2}!\cdots j_{n-k+1}!}\left({x_{1} \over 1!}\right)^{j_{1}}\left({x_{2} \over 2!}\right)^{j_{2}}\cdots \left({x_{n-k+1} \over (n-k+1)!}\right)^{j_{n-k+1}}$
где сумма берётся по всем последовательностям j₁, j₂, j₃, ..., j_n₋_k₊₁ неотрицательных целых чисел таким, что
$j_{1}+j_{2}+\cdots =k$ и $j_{1}+2j_{2}+3j_{3}+\cdots =n$ .
Конец цитаты.
Простыми словами: технически полином Белла отличается лишь методом составления мономов (одночленов, слагаемых). А именно первая роль в этом мономе будет за мультиномиальным коэффициентом, то есть эдаким расширением сочетания . Вторая же роль - это некое шаманство с изначальными переменными. Надеюсь, вы уже понимаете, к чему я клоню? Одни и те же переменные есть ( $x_1, x_2 ... x_{n-k+1}$ ) в разном количестве по разные части от знака . А значит, эта формула рождается через шаблонные "переставлялки", а также дополнениями и исключениями контекста.
Но помимо всего прочего, главная прелесть метода получения этой формулы с помощью Мета-переводчика - это снова и снова тот же трюк: мы можем задать Язык-утилиту, заполняющего бесконечный алфавит мультиномиальными коэффициентами, после чего смело подставлять их в "первую роль" монома.
Также можно задавать, в том числе, числа Белла или числа Стерлинга первого и второго рода.
Помимо всего прочего, я еще не упомянул, что такому переводчику все равно, какими символами вы запишите "терминалы" и "нетерминалы". Вы вполне можете заменить их на человеческие слова - хоть по-русски, хоть по-китайски, но алгоритм останется неизменным.
Что в свою очередь значит, что Мета-переводчик можно обучить переводить некоторые шаблонные условия школьных задач, например, в текст мат.-решения или даже программу. Так что фраза, написанная мной в самом начале на самом деле звучит не совсем верно - все же речь идет о превращении воды в вино, но только в маленьких масштабах. Зависит лишь от числа шаблонов, которые вы загружаете в переводчик. Отмечу, что проблема перестановки двух случайных слов в русском условии задачи таким образом, что это все еще звучит грамотно для нас, людей, может привести в ступор переводчика.

Итог

Следует еще раз отметить, что Мета-переводчик (как и просто переводчик, каким мы его здесь рассматривали) - это не ЯП, не нейросетка и не переводчик в лингвистическом смысле. Следует также еще раз отметить, что строящаяся теория (Мета-)переводчика радикально отличается от технологии GPT и его аналогов (еще раз вспоминаем наглядный пример со шрапнелью и снайперской винтовкой)

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

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

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

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

Ссылки

О математике из статьи:
О полиномах
Бином Ньютона
Биномиальный коэффициент
Числа Стерлинга 1 рода
Числа Стерлинга 2 рода
Числа Белла
Мультиномиальный коэффициент
Полином Белла

О ЯП:

Иерархия грамматик по Хомскому
Теория Автоматов

Книги на тему:

Александр Попа - "Lisp Жемчужины программирования 2018"
Альфред Ахо, Рави Сети, Джеффри Ульман, Моника Лам - "Компиляторы. Принципы, технологии, инструменты" [2018]
Лео Броуди - "Способ мышления - ФОРТ Язык и философия для решения задач"
Мозговой Михаил Владимирович - "Классика программирования алгоритмы языки автоматы компиляторы Практический подход"
Стивен Сол Скиена - "Алгоритмы Руководство по разработке"
Молдованова Ольга Владимировна - "Языки Программирования и методы трансляции"
Свердлов Сергей Залманович - "Языки Программирования и методы трансляции"
Джон Хопкрофт, Раджив Мотвани, Джефри Ульман - "Введение в теорию автоматов, языков и вычислений "
Robert Nystrom - "crafting interpretes"

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Мета-переводчик возможен?

83.33% нет5

16.67% да1

Проголосовали 6 пользователей. Воздержались 2 пользователя.

Теги:

Хабы:

Мета-Переводчики: реальность или фантастика?

Преамбула

Зачем я пишу эту статью?

Об аналогах

Задача

Теоретическое мат.-решение

Реализация

Практическая польза

Итог

Ссылки

Публикации

Истории

Ближайшие события