Алгоритмические языки METAFONT и METAPOST, пожалуй, единственные, которые имеют встроенную поддержку линейных уравнений. Числовые переменные (а также основанные на наборах чисел — координатные пары, цветовые тройки, шестёрки чисел, задающие аффинные преобразования, — все они могут получать значения не только с помощью присваивания, но и в результате их участия в линейных уравнениях.

Посмотрим, как в METAPOST решается задача об отрезках, на которые стороны $3$, $4$, $5$ треугольника делятся точками касания со вписанной окружностью:

METAPOST
numeric p, q, r;

message "В самом начале:";
show p, q, r;

p+q=3;
message "После первого уравнения:";
show p, q, r;

q+r=4;
message "После второго уравнения:";
show p, q, r;

r+p=5;
message "После третьего уравнения:";
show p, q, r;

bye.

Сохраняем текст программы в файле equations.mp и запускаем транслятор:

% mpost equations.mp
This is MetaPost, version 1.504 (kpathsea version 6.0.1)
(mpost.mp (/usr/share/texmf-dist/metapost/base/plain.mp
Preloading the plain mem file, version 1.004)) (./equations.mp
В самом начале:
>> p
>> q
>> r
После первого уравнения:
>> p
>> -p+3
>> r
После второго уравнения:
>> p
>> -p+3
>> p+1
После третьего уравнения:
>> 2
>> 1
>> 3 )
Transcript written on equations.log.

Видно, что числовые переменные могут находиться в одном из трёх состояний: полностью неопределённом (тогда команды show показывают их имена), полностью определённом (показываются числовые значения переменных). Кроме того, возможно и промежуточное состояние переменной, когда она выражена через другие полностью неопределённые переменные — тогда показывается соответствующее линейное выражение. В терминологии METAPOST структура данных, которая может быть или неопределённой, или хранить линейное выражение, в котором участвуют переменные, или хранить число, называется капсулой (capsule).

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

Нам нужен тип данных для представления в программе переменных в уравнениях. Мы могли бы назвать соответствующий класс Variable (variable — переменная), но тогда будет путаница между переменными в математике и переменными в языке программирования. Назовём этот класс Capsule.

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

Итак, придётся хранить в одном и том же объекте выражения наподобие этих: $$\begin{array}{l}x=?\text{,}\\ x=-8y+11z-w+3\text{,}\\ x=22\text{.}\end{array}$$ В линейных выражениях имеется чёткая структура: это список слагаемых, каждое из которых, за исключением последнего, является переменной (капсулой), умноженной на числовой коэффициент. Последнее слагаемое, свободный член выражения — число. Таким образом, подходящей структурой данных для линейных выражений служит массив, в котором ячейки с чётными индексами заняты коэффициентами и свободным членом. На нечётных местах располагаются капсулы. Этот массив должен иметь нечётный размер. В особом случае, когда значение капсулы полностью неизвестно, массив будет пустым — этот случай мы ни с чем не спутаем. На языке Perl значения переменной $x для приведённых выше примеров будут такими: [], [-8, $y, 11, $z, -1, $w, 3], [22], если в переменных $y, $z, $w находятся другие капсулы.

Линейное уравнение, после переноса всего в левую часть, задаётся линейным выражением — тем, что окажется в левой части. Процедура equation, обрабатывающая уравнение, будет получать в качестве параметра список, в котором чередуются числовые коэффициенты и капсулы, а завершит список свободный член.

Типичная программа equation-345.pl, решающая систему линейных уравнений $$\begin{array}{l}p+q=3\text{,}\\ q+r=4\text{,}\\ r+p=5\text{,}\end{array}$$ могла бы выглядеть так:

examples/perl/equation-345.plPerl
#!/usr/bin/perl

use warnings;
use Capsule;

my $p=Capsule->new;
my $q=Capsule->new;
my $r=Capsule->new;

Capsule::equation(1, $p, 1, $q, -3);
Capsule::equation(1, $q, 1, $r, -4);
Capsule::equation(1, $r, 1, $p, -5);

print "p=", $p->value, "\n";
print "q=", $q->value, "\n";
print "r=", $r->value, "\n";

% ./equation-345.pl
p=2
q=1
r=3

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

Линейное выражение не нуждается в упрощении, если оно

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

Рассмотрим процесс упрощения на примере линейного выражения $15a-3b+2c+6d-4$, предполагая, что $b=5a-c+d+2$, $c=7$, а переменные $a$ и $d$ полностью неизвестны.

Первый проход по списку делает подстановки тех переменных, которые не являются полностью неизвестными: $$\begin{array}{ll}\boxed{15a}-3b+2c+6d-4& \text{пропускаем}\\ 15a\boxed{-3b}+2c+6d-4& \text{подставляем}\\ 15a-3\left(5a-c+d+2\right)+2c+6d-4\\ 15a\boxed{-15a}+3c-3d+2c+6d-10& \text{пропускаем}\\ 15a-15a\boxed{+3c}-3d+2c+6d-10& \text{подставляем}\\ 15a-15a+3\cdot 7-3d+2c+6d-10\\ 15a-15a\boxed{-3d}+2c+6d+11& \text{пропускаем}\\ 15a-15a-3d\boxed{+2c}+6d+11& \text{подставляем}\\ 15a-15a-3d+2\cdot 7+6d+11\\ 15a-15a-3d\boxed{+6d}+25& \text{пропускаем}\\ 15a-15a-3d+6d+25\end{array}$$

Во втором проходе приводятся подобные слагаемые: $$\begin{array}{ll}\boxed{15a}-15a-3d+6d+25& \text{пропускаем}\\ 15a\boxed{-15a}-3d+6d+25& \text{приводим}\\ 0a\boxed{-3d}+6d+25& \text{пропускаем}\\ 0a-3d\boxed{+6d}+25& \text{приводим}\\ 0a+3d+25\end{array}$$

В третьем проходе удаляются одночлены с нулевыми коэффициентами: $$\begin{array}{ll}\boxed{0a}+3d+25& \text{удаляем}\\ \boxed{3d}+25& \text{пропускаем}\\ 3d+25\end{array}$$

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

Процедура equation получает список, представляющий линейное выражение — то самое, которое приравнивается нулю. Прежде всего выражение упрощается. После этого возможны следующие ситуации:

Разберёмся сначала со вторым, более простым случаем, когда после упрощения уравнение свелось к тривиальному $0=0$ или $a=0$, где $a$ — ненулевое число.

Уравнение $0=0$, очевидно, не добавляет никакой информации о неизвестных, и поэтому бесполезно. Такое уравнение назовём избыточным. METAPOST при появлении избыточного уравнения выдаёт предупреждение Redundant equation. По желанию можно или игнорировать избыточные уравнения, или выдавать подобное предупреждение.

Уравнение $a=0$, где $a\ne 0$, конечно же ставит крест на наших попытках определить неизвестные из линейных уравнений. Такие уравнения назовём несовместными; METAPOST откликается на их появление сообщением Inconsistent equation. Нам нет никакого смысла продолжать исполнение программы, если встретилось несовместное уравнение.

Тут однако есть проблема. Рассмотрим следующий пример:

Perl
$a=1000;
print "РАВНО!\n" if $a/333*333==$a;
print $a/333*333-$a, "\n";

Почему-то эта программа не печатает строчку РАВНО!, как можно было ожидать. Кроме того, вопреки ожиданиям, она напечатает не ноль, а что-то вроде этого:

-1.13686837721616e-13