В 1994 году автор попытался разобраться в том, как работает компилятор и написать такую программу. Вопрос о входном языке не был главным и на том уровне понимания не мог быть разумно решен. Но что-то решить было необходимо и было подготовлено очень короткое словесное описание. Формальное описание отсутствовало, но для ручного написания компилятора оно и не требовалось.
Через год была предпринята еще одна попытка, вопрос о входном языке опять рассматривался и было подготовлено новое описание, также короткое. Большую его часть занимали рисунки различных ссылочных структур - ссылок на объект, на массив объектов, на массив ссылок и т.п.
Позже автор несколько раз возвращался к этим вопросам. В 2001 году было реализовано объектное расширение, в 2003 году компилятор был полностью переписан, но язык существенных изменений не претерпел (точнее, он уменьшился - не были реализованы работа с вещественными числами и объектное расширение). В 2005 году из языка было выделено очень ограниченное подмножество и реализован соответствующий компилятор. В это время появилось формальное описание языка, сделано оно было по настоянию редактора журнала "Мир ПК", в котором компилятор был опубликован. В 2008 году описание пригодилось - был написан почти такой же маленький таблично-управляемый компилятор. Не понимаю, почему в соответствующих учебниках нет такого примера.
Устройство компилятора больше не тайна и можно попытаться критически рассмотреть его входной язык. По-крайней мере некоторые его аспекты.
Ссылка в Context-е похожа на указатель в языке C и предназначена для тех же целей, в частности, для передачи параметров функциям и для реализации строк. Ссылка является адресом объекта и одномерного массива объектов, спрособа различать эти две вещи нет. Например, если функция F имеет строковый параметр:
void F(char @P)
...
end
ничто не мешает передать ей ссылку на единственный символ
begin
char C;
F (@C);
end
Если функция модифицирует переданную строку или если она использует предположение о наличии символа конца строки (#0), результат ее работы предсказать сложно.
Возможно, для решения задач системного программирования многомерные массивы и не нужны, но для решения задач моделирования физических процессов их отсутствие создает большие неудобства. Многомерный массив может быть объявлен в программе и использован там, где он объявлен, но вот передать его для обработки какой-либо функции нельзя. Поэтому полезность многомерных массивов в языке Context невелика и если бы их не было совсем, их можно было бы имитировать другими средствами. Например, комбинируя одномерные массивы и структуры:
define N 10
struct ROW
real Row[N];
end
ROW Matrix[N];
begin
int J := 1;
int K := 2;
Matrix[J].Row[K] := 0.0; // Matrix[J][K] := 0.0;
end
Каждое обращение к элементу массива требует написания лишних символов .Row, и способа создания
универсальных функций, работающих с массивами различного размера не дает. В частности, создать функцию, решающую
систему из неопределенного заранее числа N линейных уравнений нельзя.
Многомерный массив можно имитировать с помощью одномерного и явного вычисления смещения:
void DoSome(int N; real @PM)
int J := 1;
int K := 2;
PM[N*J+K] := 0.0; // PM[J][K] := 0.0;
end
define N 10
real Matrix[N*N];
begin
DoSome(N, @Matrix);
end
Это решение позволяет создавать создавать универсальные функции, работающие с массивами различного размера, но оно еще менее удобно чем предыдущее.
Наконец, можно использовать ссылки второго порядка (для массивов болшей размерности - ссылки более высоких порядков):
void DoSome(int N; real @@PM)
int J := 1;
int K := 2;
PM[J][K] := 0.0;
end
define N 10
struct ROW
real Row[N];
end
ROW Matrix[N];
real @PV [N]; // Массив ссылок на массивы чисел
real @@PM;
begin
int I := 0; // Инициализация
while I < N do
@PV[I] := @Matrix[I].Row;
inc I;
end
@@PM := @@PV;
DoSome(N, @@PM);
end
Этот вариант не требует написания лишних символов и позволяет создавать универсальные функции, но он требует наличия дополнительных структур данных и сложной для понимания инициализации. Размер массива должен явно передаваться функциям обработки, что также является источником ошибок.
Точно такая же проблема существует в языке C:
#define N 3
void DoSome(int N, double **PM)
{
int J = 1;
int K = 2;
PM [J][K] = 0.0;
}
struct ROW
{
double Row[N];
};
struct ROW Matrix[N];
double *PV [N];
double **PM;
void main()
{
int I = 0;
while (I < N)
{
PV[I] = (int *) &Matrix[I].Row;
I++;
}
PM = (int **) &PV;
DoSome(N, PM);
}
В C++ можно использовать механизм шаблонов:
template <int N>
void DoSome(double M[][N])
{
int J = 1;
int K = 2;
M [J][K] = 0.0;
}
double M10x10[10][10];
double M10x20[10][20];
double M20x20[20][20];
void main()
{
DoSome(M10x10);
DoSome(M10x20);
DoSome(M20x20);
}
В данном случае компилятор сгенерирует две реализации функции DoSome - для матриц шириной 10 и 20. Высота матрицы не задается, так что если матрица не квадратная, высоту нужно передавать явно. Ширину матрицы передавать не нужно, т.к. она равна значению константы N.
Наконец, можно совместно использовать шаблоны и перегрузку операторов:
template <int N, class C>
class Vector
{
private:
C c[N];
public:
C &operator [](int I)
{
return c[I];
}
};
template <int N, class C>
void DoSome(Vector<N, Vector<N, C> > &M)
{
...
}
void main()
{
const int N = 10;
Vector<N, Vector<N, double> > M;
DoSome(M);
}
В этом примере матрица квадратная, ее размер передавать не нужно (он равен N), реализаций DoSome будет столько, сколько встретится различных аргументов.
В стандартном Pascal также нет необходимых средств, зато в языке Oberon работа с многомерными массивами не является проблемой:
MODULE arrays;
PROCEDURE doSome(VAR m: ARRAY OF ARRAY OF REAL);
VAR
j: INTEGER;
k: INTEGER;
BEGIN
j := 1;
k := 2;
m[j][k] := 0.0
END dosome;
PROCEDURE test*;
CONST
n = 10;
VAR
m: ARRAY n OF ARRAY n OF REAL;
BEGIN
doSome(m)
END test;
END arrays.
Размеры массива передаются процедуре doSome неявно, так что ошибиться здесь нельзя. Из перечисленных языков только Oberon предоставляет лучшие средства работы с многомерными массивами, чем Fortran:
REAL MATRIX(10, 10)
CALL DOSOME(10, M)
CALL DOSOME(20, 20)
END
SUBROUTINE DOSOME(N, M)
INTEGER N
REAL M(N, N)
RETURN
END
В примере показано, как двумерный массив передается подпрограмме DOSOME и как можно использовать эту возможность ненадлежащим образом. Соответствие формальных и фактических параметров не проверяется компилятором, вместо массива можно передать все, что угодно, хоть числовую константу.
Помимо реализации многомерных массивов такие ссылки могут использоваться при работе со списочными структурами. Например, в одном из вариантов компилятора построение синтаксического поддерева (разбор блока) выполнялось так:
struct NODE
word ID;
word Value;
NODE @Left;
NODE @Right;
end
...
begin
...
NODE @Node := NULL;
NODE @@P := @@Node;
while strcmp(@Scan(@Buff), "end") != 0 do
@P := @Ctrl(@Buff);
@@P := @@P.Right;
end
...
end
То же самое можно сделать и без использования ссылок второго порядка, но кода потребуется больше:
begin
...
NODE @Node := NULL;
NODE @P;
while strcmp (@Scan(@Buff), "end") != 0 do
if @Node = NULL then
@Node := @Ctrl(@Buff);
@P := @Node;
else
@P.Right := @Ctrl(@Buff);
@P := @P.Right;
end
end
...
end
Если потребовать непустоты поддерева (т.е. наличия хотя бы одного оператора в блоке, это вполне естественно), код можно вернуть к исходному размеру:
begin
...
NODE @Node := @Ctrl(@Scan(@Buff));
NODE @P := @Node;
while strcmp (@Scan(@Buff), "end") != 0 do
@P.Right := @Ctrl(@Buff);
@P := @P.Right;
end
...
end
Ссылки второго порядка могут использоваться для инициализациии ссылок первого порядка посредством вызова функции:
void Init(char @@P)
@P := "qwerty";
end
begin
char @P;
Init(@@P);
end
По-видимому, используется это редко и существует язык (Java), в котором ссылки порядка выше первого отсутствуют и это не создает трудностей.
Единственное реализованное средство - директива include, позволяющая собрать воедино несколько файлов, в DOS-версии не было и ее, но можно было воспользоваться внешним препроцессором. В силу ограничений DOS и формата исполняемых файлов COM это не было очень существенным, все равно программа длиной десять или сто тысяч строк не могла поместится в шестьдесят четыре килобайта кода.
Локальные функции полезны когда нужно выполнить некоторую вспомогательную работу, не имеющую самостоятельной ценности. В качестве примера можно привести реализацию алгоритма сортировки с помощью кучи.
Локальная переменная с тем же именем, что и параметр функции делает параметр недоступным и это может быть источником ошибок.
Представление шестнадцатеричных чисел и символьных констант было заимствовано из Turbo Pascal:
define VSEG $B800 // Сегментный адрес видеопамяти
define LF #10 // Символ перевода строки
Шестнадцатеричные константы в ряде случаев удобны, двоичные константы пожалуй еще более удобны для записи команд процессора, полезность записи констант в иных системах счисления неочевидна и может приводить к ошибкам (в языке C константа 010 - это не 10, а 8). Символов наподобие $ не так много и их связь с основанием системы счисления неочевидна, поэтому имеет смысл использовать другую нотацию. Как вариант, константа, представленная в отличной от десятичной системе счисления может начинаться с нуля, за которым следует символ, определяющий основание:
define VSEG 0hB800 // Сегментный адрес видеопамяти в шестнадцатеричной системе счисления
define NOP 0b10010000 // Пустая команда в двоичной системе счисления
Что касается символьных констант, использование решетки (#) было нужно только для ввода неотображаетых символов, например, символа конца строки (#0). Использование тильды (~) решает этот вопрос так же, как обратный слеш (\) в языке C:
define EOL '~0' // Символ конца строки
define CR '~r' // Символ возврата каретки
define LF '~n' // Символ перевода строки
define QUOTE '~'' // Кавычка
define TILDE '~~' // Тильда
Не для всех символов определены замены но ничто не мешает это сделать. Обратный слеш не использован, поскольку в DOS/Windows он является разделителем в имени файла.
В качестве основного типа было выбрано машинное слово без знака (word). В ряде случаев числа со знаком неободимы (например, координаты левого верхнего угла окна на экране - целые со знаком), в некоторых случаях они удобнее, но они ограничивают максимально допустимую длину массива байт. В шестнадцатиразрядных системах это может быть существенно - разница между 32 и 64 килобайтами гораздо больше, чем между 2 и 4 гигабайтами. Если же говорить только о написании компилятора, то отсутствие целых без знака принципиальных трудностей не создает, но для хранения смещений вместо одного слова без знака придется использовать пару слов со знаком, а для работы с парами чисел придется написать специальные арифметические функции - встроенными арифметическими операторами уже не обойтись. Для хранения создаваемого кода можно использовать массив символов (char) или знаковых байт (byte) и преобразование в них из целых со знаком (int).
Выбор не между знаковыми и беззнаковыми числами, а между наличием и отсутствием беззнаковых чисел. Оба варианта имеют достоинства и недостатки. При наличии обоих видов чисел нужно определить правила преобразования. В Context'е беззнаковое число преобразуется в знаковое:
//16 бит
//i >= w
begin
int i := 32767;
word w := 32768;
if i < w then
puts("i < w");
else
puts("i >= w");
end
end
В языке C знаковое число преобразуется в беззнаковое:
#include <stdio.h>
void main()
{
int i = -1;
unsigned u = 1;
printf("%i %s %d\n", i, i < u ? "<" : ">=", u); // -1 >= 1
}
Оба варианта формально некорректны, но преобразование беззнакового числа в знаковое не приводит к проблемам, если число невелико. Обратное преобразование небольшого числа к проблемам приводит. Отсутствие беззнаковых чисел также может приводить к проблемам (реальный код, написанный человеком, недавно начавшим изучение языка Java):
public final class Utils
{
//...
/**
* Метод преобразует массив байт в строку без завершающих пробелов.
*/
public static String rtrim(byte buff[], String characterSetName) throws UnsupportedEncodingException
{
int n = buff.length;
while (n > 0 && buff[n - 1] <= ' ')
{
n--;
}
if (n == 0)
{
return null;
}
return new String(buff, 0, n, characterSetName);
}
}
Этот метод понадобился для чтения dbf-файлов (да, они до сих пор используются) и был написан по аналогии с методом trim класса String:
public final class String
{
//...
public String trim() {
int len = count;
int st = 0;
int off = offset; /* avoid getfield opcode */
char[] val = value; /* avoid getfield opcode */
while ((st < len) && (val[off + st] <= ' ')) {
st++;
}
while ((st < len) && (val[off + len - 1] <= ' ')) {
len--;
}
return ((st > 0) || (len < count)) ? substring(st, len) : this;
}
}
Неприятность в том, что buff - массив байт со знаком, соответственно все коды от 0x80 до 0xFF считаются отрицательными и меньшими кода пробела. И приводит это к потере части или всего русского текста. Можно конечно сказать, что символы - это не числа и сравнивать их друг с другом нельзя, но в Java это не так и замена символа пробел числом 32 ничего не меняет. Символы же использовать нельзя, поскольку они двухбайтовые. Возможно, правильнее было сначала преобразовать массив байт в строку, а потом удалять пробелы, но дело не в этом - команды процессора тоже могут быть байтами без знака.