[Oberon7] "Man or Boy test" by Donald Knuth

[valexey_u]

- Вводится маркер для параметра процедуры (по аналогии с VAR), что этот параметр процедурного типа может быть локальной процедурой из процедуры выше по стеку. Например некий LOCAL:

Можно расширить эту идею и на указатели. Т.е., локальная переменная может быть приведена к LOCAL POINTER TO с теми же ограничениями и совместимостями. Тогда оригинальная задача тоже быть решена без обращения к куче и GC.

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

[igor]

Ну, на самом деле, если ослабить вот это требование: "The scope extends textually from the point of the declaration to the end of the block (procedure or module) to which the declaration belongs and hence to which the object is local." до "whole block (procedure or module)", то получится язык поприятнее для кодописателя (и чуть менее приятный для компилятороклепателя, хотя и тут выигрыш таки в итоге будет, ибо компилятор железно перестает быть однопроходным).

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

[valexey_u]

Ну, на самом деле, если ослабить вот это требование: "The scope extends textually from the point of the declaration to the end of the block (procedure or module) to which the declaration belongs and hence to which the object is local." до "whole block (procedure or module)", то получится язык поприятнее для кодописателя (и чуть менее приятный для компилятороклепателя, хотя и тут выигрыш таки в итоге будет, ибо компилятор железно перестает быть однопроходным).

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

Да? А как? Вот у меня процедура Foo, которая использует другую процедуру которая определена где-то далеко внизу. Вопрос - как за один проход такое компилировать?

[vlad]

Да? А как? Вот у меня процедура Foo, которая использует другую процедуру которая определена где-то далеко внизу. Вопрос - как за один проход такое компилировать?

Никак. Просто потому, что в общем случае нельзя "угадать" сигнатуру - оберон допускает неявные преобразования типов аргументов. Например f('A') может быть как вызовом "PROCEDURE f(c: CHAR)" так и "PROCEDURE(s: ARRAY OF CHAR)". Кроме того, передача VAR-аргументов тоже влияет на генерируемый код в точке вызова.

[valexey_u]

Да? А как? Вот у меня процедура Foo, которая использует другую процедуру которая определена где-то далеко внизу. Вопрос - как за один проход такое компилировать?

Никак. Просто потому, что в общем случае нельзя "угадать" сигнатуру - оберон допускает неявные преобразования типов аргументов. Например f('A') может быть как вызовом "PROCEDURE f(c: CHAR)" так и "PROCEDURE(s: ARRAY OF CHAR)". Кроме того, передача VAR-аргументов тоже влияет на генерируемый код в точке вызова.

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

[igor]

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

Для сомневающихся хочу дать некоторые пояснения. Я использовал специальную структуру данных, которую назвал "буфер отложенных объявлений". Основная идея в упрощенном виде выглядит так. Парсер делает один проход по исходному тексту. Если парсер в операторной последовательности встречает неизвестный идентификатор, то он панику не разводит, а помещает этот идентификатор в буфер отложенных объявлений. Затем, если далее по тексту встречается объявление этого идентификатора, то парсер переносит его из буфера в таблицу имён. К тому моменту, когда будет достигнут конец модуля, буфер должен быть пуст, иначе ошибка. На самом деле всё несколько сложнее из-за вложенности областей видимости, но в моём случае (обероноподобный язык, но не Оберон) задача алгоритмически вполне решабельна (проверено на практике).

[vlad]

Ну и для полноты картины решение на С++. Решение "в лоб", без придумок, с использованием библиотечных замыканий:

Код: [Выделить]

#include <boost/bind.hpp>
#include <boost/function/function0.hpp>
#include <iostream>

typedef boost::function0<int> function_t;

int f0(){return 0;}
int f1(){return 1;}
int fn1(){return -1;}

int b(int& k,
      function_t const& x1,
      function_t const& x2,
      function_t const& x3,
      function_t const& x4);

int a(int k,
      function_t const& x1,
      function_t const& x2,
      function_t const& x3,
      function_t const& x4,
      function_t const& x5)
{
    return k <= 0 ? x4() + x5() : b(k, x1, x2, x3, x4);
}

int b(int& k,
      function_t const& x1,
      function_t const& x2,
      function_t const& x3,
      function_t const& x4)
{
    --k;
    return a(k,
             boost::bind(&b, boost::ref(k), x1, x2, x3, x4),
             x1,
             x2,
             x3,
             x4);
}

int main()
{
    std::cout << a(10, f1, fn1, fn1, f1, f0) << std::endl;
    return 0;
}


[vlad]

И в довесок "велосипедное" (замыкания вручную) решение на С++. Работает сильно быстрее, не лезет в кучу и кушает меньше стека.

Код: [Выделить]

#include <iostream>

struct function_t
{
    virtual int operator() () const = 0;
};

struct f0 : function_t
{
    virtual int operator() () const {return 0;}
};

struct f1 : function_t
{
    virtual int operator() () const {return 1;}
};

struct fn1 : function_t
{
    virtual int operator() () const {return -1;}
};

struct b : function_t
{
    b(int k,
      function_t const& x1,
      function_t const& x2,
      function_t const& x3,
      function_t const& x4)
    : k(k), x1(x1), x2(x2), x3(x3), x4(x4)
    {}

    virtual int operator() () const;
private:
    mutable int k;
    function_t const& x1;
    function_t const& x2;
    function_t const& x3;
    function_t const& x4;
};

int a(int k,
      function_t const& x1,
      function_t const& x2,
      function_t const& x3,
      function_t const& x4,
      function_t const& x5)
{
    return k <= 0 ? x4() + x5() : b(k, x1, x2, x3, x4)();
}

int
b::operator() () const
{
    --this->k;
    return a(this->k,
             *this,
             this->x1,
             this->x2,
             this->x3,
             this->x4);
}

int main()
{
    std::cout << a(10, f1(), fn1(), fn1(), f1(), f0()) << std::endl;
    return 0;
}


[vlad]

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

Хорошо, парсер однопроходный. А код кто генерить будет? В текущей реализации моего компилятора все далется за один проход - и парсинг, и проверка семантики и генерация кода (никаких AST не строится). Почему нельзя сгенерировать код для вызова необъявленной процедуры - я написал выше.

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

[Geniepro]

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

Для сомневающихся хочу дать некоторые пояснения. Я использовал специальную структуру данных, которую назвал "буфер отложенных объявлений". Основная идея в упрощенном виде выглядит так. Парсер делает один проход по исходному тексту. Если парсер в операторной последовательности встречает неизвестный идентификатор, то он панику не разводит, а помещает этот идентификатор в буфер отложенных объявлений. Затем, если далее по тексту встречается объявление этого идентификатора, то парсер переносит его из буфера в таблицу имён. К тому моменту, когда будет достигнут конец модуля, буфер должен быть пуст, иначе ошибка. На самом деле всё несколько сложнее из-за вложенности областей видимости, но в моём случае (обероноподобный язык, но не Оберон) задача алгоритмически вполне решабельна (проверено на практике).

Если Вы генерируете маш. код уже после прохода по тексту по какой-то внутренней структуре данных -- то вот уже второй проход, компилятор двухпроходным стал...

[igor]

Под многопроходностью я понимаю несколько проходов по одному и тому же представлению программы. Проходы по другому представлению программы - это следующий этап обработки. Front-end и back-end обычно разделены в коде. Это же не означает, что компилятор стал двухпроходным? Или означает? Вопрос терминологии.

[Geniepro]

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

Транслятор с фронт-эндом и бэк-эндом -- уже как минимум двухпроходные...

[igor]

Вот у меня процедура Foo, которая использует другую процедуру которая определена где-то далеко внизу. Вопрос - как за один проход такое компилировать?

Никак. Просто потому, что в общем случае нельзя "угадать" сигнатуру - оберон допускает неявные преобразования типов аргументов. Например f('A') может быть как вызовом "PROCEDURE f(c: CHAR)" так и "PROCEDURE(s: ARRAY OF CHAR)".

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

[valexey_u]

Под многопроходностью я понимаю несколько проходов по одному и тому же представлению программы. Проходы по другому представлению программы - это следующий этап обработки. Front-end и back-end обычно разделены в коде. Это же не означает, что компилятор стал двухпроходным? Или означает? Вопрос терминологии.

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

По такой схеме писан например GPCP. И это круто. Классическая Виртовская однопроходность компиляторов штука хорошая только в плане скорости компиляции на слабом железе.

[igor]

Под многопроходностью я понимаю несколько проходов по одному и тому же представлению программы. Проходы по другому представлению программы - это следующий этап обработки. Front-end и back-end обычно разделены в коде. Это же не означает, что компилятор стал двухпроходным? Или означает? Вопрос терминологии.

Угу, означает. Это и есть классический многопроходный компилятор. С созданием промежуточного представления и так далее.

Вот, и Geniepro то же самое говорит. Хорошо, буду знать (не зря всё-таки я этот разговор затеял).
Кстати, Свердлов в своей книге упоминает о 16-проходном компиляторе (один из ранних). Неужели там использовалось 16 различных представлений одной и той же программы?    Хотя, нет конечно. Вот там действительно по каждому из представлений делалось по несколько проходов. Памяти не хватало даже на то, чтобы хранить код самого компилятора, загружался и выполнялся по частям.