Разметка неразменных аргументов для прогонки

[Mazdaywik]

ВНИМАНИЕ! Исходная постановка задачи со временем потеряла актуальность на 60 %. Неактуальный кусок я завернул в складку. Наиболее точная постановка задачи сейчас — в комментарии #231 (comment).

Неактуальный кусок свёрнут

Цель

Размечать сужаемые и несужаемые аргументы для прогоняемых функций шаблоном, аналогичным шаблону $SPEC.

Мотивация

Я переписывался по почте с @ArkadyKlimov и в ходе переписки у нас сформировалась идея о более тонком управлении прогонкой и встраиванием.

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

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

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

refal-5-lambda/src/srlib/common/LibraryEx.refi

Lines 4 to 17 in 4ed95a0

	/**
	<Apply t.Closure e.Arg> == e.Res
	t.Closure ::=
	s.FUNCTION
	| (t.Closure e.Bounded)
	e.Arg, e.Res, e.Bounded ::= e.AnyExpr
	*/
	Apply {
	s.Fn e.Argument = <s.Fn e.Argument>;
	(t.Closure e.Bounded) e.Argument
	= <Apply t.Closure e.Bounded e.Argument>;
	}

Прогонка с расщеплениями Apply будет выполняться бесконечно, причём там, где это совершенно избыточно. Например, в функции Map, где она вызывается с термом общего вида. Там её вообще не надо оптимизировать.

Но есть интересные функции, которые не ложатся в это прокрустово ложе. Например, OneOf:

OneOf {
  t.SearchFor t.SearchFor e.Set = True;
  t.SearchFor t.Other e.Set = <OneOf t.SearchFor e.Set>;
  t.SearchFor /* пусто */ = False;
}

Если эту функцию пометить как $DRIVE, то вызов <OneOf s.X Foo Bar Baz> прогонится замечательно. Но с другой стороны, вызов <OneOf s.X Foo e.Bar Baz> приведёт к зацикливанию.

Что делать?

Формат функции OneOf такой:

<OneOf t.SearchFor e.Set>

Рекурсивный вызов во втором предложении применяется к части аргумента e.Set из-за чего происходит зацикливание. Следовательно, для (e-)переменных, попадающих в аргумент e.Set, сужение разумно запретить. Аргумент t.SearchFor сужается только в точке выхода из рекурсии (повторная переменная), на остальных он передаётся как есть. А для нерекурсивных вызовов сужение безопасно.

Таким образом, для параметра e.Set прогонка должна вести себя как $INLINE, для t.SearchFor — как $DRIVE.

Есть случай, когда прогонка некоторых переменных запрещена, поскольку физически невозможна — для «неразменных» переменных, которыми заменяют вызовы функций при попытке прогонки вызова с активным аргументом (#230).

Здесь (e-)переменные в e.Set прогонять нельзя, поскольку это небезопасно — приведёт к зацикливанию.

Таким образом, приходим к тому, что для обеспечения безопасности (терминируемости) прогонки нужно размечать переменные в аргументах как разменные и неразменные. Если прогонка требует сужения неразменной переменной, данный вызов просто считается не подлежащим оптимизации. Функции, помеченные как $DRIVE и $INLINE становятся просто частными случаями: у первых все переменные разменные, у вторых — все неразменные.

Реализация

Предлагается добавить шаблоны следующего вида

$DRIVE FuncName шаблон;

где шаблон — жёсткое выражение. Индексы переменных в шаблоне роли не играют, за исключением первого знака их индекса. Если он является заглавной буквой, то параметр считается «разменным», если со строчной буквы, прочерка, дефиса или цифры — «неразменным».

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

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

Побочный эффект и связи с другими задачами

Во-первых, механизм пометки переменных как неразменных необходим в задаче #230. Поэтому достаточно просто строить множество неразменных переменных, которое является объединением переменных для вложенных вызовов и переменных, попавших под маску.

Во-вторых, неразменные переменные возникают в предложениях с условиями (они сейчас не оптимизируются). Если в вызове функции участвуют переменные как из образца предложения, так и из образца предшествующего условия, то первые переменные сужать можно (если они, конечно, из жёсткого образца образца-L-выражения), а вторые — нельзя. Реализация: в «мешок неразменных переменных» добавляются переменные из условий.

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

$DRIVE F;

F {
  A = 1; B = 2; C = 3;
}

G {
  e.B s.A e.D = e.B <F s.A> e.D;
}

H {
  s.A e.B s.A e.D = e.B <F s.A> e.D;
}

В функции G выполнять прогонку нельзя, поскольку это изменит поведение функции:

G′ {
  e.B A e.D = e.B 1 e.D;
  e.B B e.D = e.B 2 e.D;
  e.B C e.D = e.B 3 e.D;
}

Вызов <G (()) (Z) B (Y) A ((X))> даст (()) (Z) 2 (Y) A ((X)), вызов G′ от того же аргумента — (()) (Z) B (Y) 1 ((X)), а оптимизация должна сохранять семантику.

Напротив, прогонка функции H будет полностью безопасной:

H′ {
  A e.B A e.D = e.B 1 e.D;
  B e.B B e.D = e.B 2 e.D;
  C e.B C e.D = e.B 3 e.D;
}

Не существует такого аргумента, где функции H и H′ давали бы разный результат.

Почему? Потому что в G переменная s.A получает своё значение внутри цикла удлинения открытой переменной, в функции H — до цикла.

Если образец содержит не открытую, а повторную e- или t-переменную, то прогонка поведение менять не будет. Однако, может пострадать быстродействие программы — повторная переменная будет сравниваться многократно. Но и для образцов с повторными переменными можно выделять набор переменных, сужения которых не ухудшают быстродействие. Причём аналогичным образом — переменные должны означиваться до сопоставлений с повторными переменными.

Очевидно, в случаях не-L-образцов точно также из образца извлекается набор переменных, по которым сужения делать нельзя — «неразменных» переменных.

БОЛЬШЕ AD HOC’А ДЛЯ БОГА AD HOC’А!

[Mazdaywik]

@TonitaN, ты хорошо разбираешься в прогонке с образцами общего вида. Тебе есть чего-нибудь добавить интересного к приведённым выше рассуждениям?

[Mazdaywik]

Задача вполне пригодна для курсовой работы по компиляторам. Причём целиком — не только шаблон, но и описанное в разделе «Побочный эффект…».

[Mazdaywik]

Задача #230 — естественная подзадача этой задачи.

[Mazdaywik]

Задача не была выбрана в качестве курсовой.

[Mazdaywik]

Задача не была выбрана в качестве ВКР.

[Mazdaywik]

Неразменные переменные и не-L-образцы

С прогонкой для не-L-образцов тоже всё непросто. В примере из постановки задачи всё красиво:

$DRIVE F;

F {
  A = 1; B = 2; C = 3;
}

…

H {
  s.A e.B s.A e.D = e.B <F s.A> e.D;
}
  ↓   ↓   ↓   ↓   ↓   ↓   ↓

H′ {
  A e.B A e.D = e.B 1 e.D;
  B e.B B e.D = e.B 2 e.D;
  C e.B C e.D = e.B 3 e.D;
}

А вот пример, где всё некрасиво:

$DRIVE Fa;

Fa {
  A = AA;
  s.X = (s.X);
}

Test {
  s.P  e._ s.P e._ = Found <Fa s.P>;
  s.P e._ = NotFound;
}

Прогонка нам даст

Test {
  A e._ A e._ = Found AA;
  s.P e._ s.P e._ = Found (s.P);
  s.P e._ = NotFound;
}

Что получится для вызова <Test A 1 2 3 4 5 6 … 97 98 99 100>? Получится два по открытой переменной. Сначала не сопоставится образец с первым предложением. Потом со вторым.

Можно привести пример, что для однозначных образцов с повторными t-, e-переменными прогонка тоже приведёт к потере производительности.

Поэтому неразменные переменные сами по себе никак не помогают прогонке с не-L-образцами.

[Mazdaywik]

Задача #314 подразумевает отказ от точной разметки $DRIVE/$INLINE, в том числе и отказ от шаблона неразменных аргументов. Поэтому синтаксис

$DRIVE 〈имя〉 〈шаблон〉;

уходит в утиль. Прогоняемая функция с шаблоном есть вариант встраиваемой функции.

Если функция пригодна для встраивания (в том числе и «смешанного» с шаблоном неразменных переменных), то её расширенная специализация (#251) построит конечный набор экземпляров, часть из которых можно будет затем прогнать. Поэтому при решении #314 и #251 шаблон неразменных переменных становится избыточен.

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

[Mazdaywik]

Задача пригодна для курсовой работы.

[Mazdaywik]

На самом деле, здесь всё не так просто. И, если разобраться, эта задача — частный случай задачи #283.

Если имеем L-образец с условиями, то прогонять нужно как в #283 — между новыми предложениями нужно будет добавлять предложения перехода на хвост. «Разменными» переменными будут только предложения из образца, но не предложения из условий.

Если мы имеем не-L-образец, но образец мы можем представить как пару наиболее сложного L-образца и набора сужений, переводящих его в исходный образец. Можем заменить исходный образец на L-образец, а сужения представить как условия-сужения при нём. Задача сводится к предыдущей (L-образец с условиями). В актуальной реализации преобразование сужений в условия не оптимально, т.к. требуется копировать значения. Но с оптимизацией #257 это проблемой не будет. К тому же такое преобразование можно делать виртуальные.

В примере выше получится так:

$DRIVE Fa;

Fa {
  A = AA;
  s.X = (s.X);
}

Test {
  s.P e._ s.P e._ = Found <Fa s.P>;
  s.P e._ = NotFound;
}

Преобразуем Test в L-образец с условием:

Test {
  s.P e.1, e.1 : e._ s.P e._ = Found <Fa s.P>;
  s.P e._ = NotFound;
}

Прогоняем:

Test {
  A e.1, e.1 : e._ A e._ = Found AA;
  A e.1 = <Test*1 A e.1>;
  s.X e.1, e.1 : e._ s.X e._ = Found (s.X);
  s.X e.1 = <Test*1 s.X e.1>;
  s.P e._ = NotFound;
}

Test*1 {
  s.P e._ = NotFound;
}

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

Поскольку преобразования виртуальные, результат будет такой:

Test {
  A e._ A e._ = Found AA;
  A e.1 = <Test*1 A e.1>;
  s.X e._ s.X e._ = Found (s.X);
  s.X e.1 = <Test*1 s.X e.1>;
  s.P e._ = NotFound;
}

Результат эффективный. Но вообще, эта задача должна быть частью #283.

[Mazdaywik]

В свете вышеизложенного + #283 (comment) задача уходит на ВКР как существенно перекрывающаяся с #283.

[Mazdaywik]

@torrentino555 ушёл к другому научному руководителю, тема на ВКР не выбрана.