Пятнадцать байтов на стек от конца

(Я послал этот текст в список рассылки БЭСМ-6, но сохраню и здесь для памяти.)

Раз уж у нас тут постепенно актуализировалась тема написания компиляторов, я тоже увлёкся и реализовал давнишнюю мечту: портонул Би с PDP-7 на БЭСМ-6.

Исходник компилятора: b-besm.b

Проект на Гитхабе: besm6/b-compiler

История вопроса следующая. В 1969 году Кен Томпсон создал язык Би для машины PDP-7. Компилятор порождал так называемый шитый код, который интерпретировался во время выполнения. Позже в 1971-м Деннис Ритчи портонул Би на машину Honeywell GE 645, но без всякого шитого кода, а уже с нормальной генерацией бинарного кода целевого процессора. А когда Ритчи взялся тащить Би на PDP-11, оказалось, что наличие байтовой адресации существенно меняет дело. Пришлось добавить в Би типы, и он быстро превратился в знакомый нам Си.

Исходники компилятора Би считались потерянными. Но девять лет назад Robert Swierczek чудесным образом сумел восстановить тексты Би из обрывков распечаток в рамках проекта pdp7-unix.

Я взял эти исходники и вместо выдачи шитого кода для PDP-7 вставил генерацию машинных команд БЭСМ-6 для ассемблера Madlen. Добавил минимальную рантайм библиотеку и запихнул в мониторную систему Дубна. Компилятор пишет ассемблерный текст на барабан и, если не случилось ошибок, выполняет как бы команду *READ:1. Дальше обычным образом стартует Мадлен и формирует объектные модули. Компилятор Би и рантайм библиотеку я поместил на отдельную ленту, её можно подключать командой *TAPE:7/B. Покажу пример на симуляторе dubna.

Вот скрипт с исходным текстом классического примера Hello World. Компилятор запускается с ленты командой *TRANS.

*name B compiler
*tape:7/b,40
*library:40
*trans-main:40020
main() {
    printf("Hello, B!*n");
}
*execute
*end file

Запускаем. Я не стал убирать таблицу загрузки, чтобы вам было видно размер кода:

$ dubna hello.dub
...
*NAME B COMPILER
*TAPE:7/*,40
*LIBRARY:40
*TRANS-MAIN:40020
                     OVERLAY OT  20/04/25
B COMPILER FOR BESM-6, VERSION 04/2025
COMPILED 3 LINES OF CODE, FOUND 0 ERRORS

*NO LIST
*CALL BLOCKERR
*MADLEN
 MAIN          CP 0.0,      ST 0.0,      RT     1.0*
*READ OLD
*EXECUTE
      *LIBRA:40 = B/DIV       B/EQ        B/GT        B/LT        B/MUL       B/NE        B/RET       B/SAVE0     B/SAVE
      B/TOUT      B/TRUE      CHAR        PRINTD      PRINTO      PRINTF      WRITE       WRITEB      OUT*CNT     OUT*SHFT
      OUT*BUFF    FLUSH       FOUT
≠
         MAIN       01000                PRINTD     01413                B/MUL      01757                ISOTCOSY   06002
         PROGRAM  E 01000                PRINTO     01466                B/GT       01766                ISOTCOS1 E 06053
         B/SAVE0    01011                WRITE      01517                FOUT       01771                DRUMTAP*   06073
         B/RET      01016                B/TRUE     01622                WRCARD     01772                CHKWORD* C 06124
         PRINTF     01023                OUT*CNT    01623                WRWORD   E 02014                PRINT8     06125
         B/SAVE     01256                OUT*SHFT   01624                WBEGIN   E 02033                STOP*      06306
         CHAR       01263                OUT*BUFF   01625                WRIEND   E 02042                EXIT     E 06307
         B/NE       01301                FLUSH      01654                B/TOUT     02075                CBOБOДHO   06335
         B/EQ       01304                B/LT       01744                WRWORD/  C 04000
         WRITEB     01307                B/DIV      01747                XWRITE/  C 06000
≠
HELLO, B!

Вот ещё несколько примеров для Би из разных мест. Все они работают под Дубной:

• doors.dub - классическая задачка про 100 дверей
• e-2.dub - вычисление константы e
• fibonacci.dub - числа Фибоначчи
• fizzbuzz.dub - классическая задачка Fizz-Buzz
• isprime.dub - проверка числа на простоту
• mandelbrot.dub - вычисление множества Мандельброта

Мандельброт выглядит забавно: mandelbrot.txt

Выводы из всей этой затеи:

• Би вполне был возможен на БЭСМ-6 уже тогда, в середине 70-х. Увы, никто из аксакалов-бэсмачей про него не знал.
• Если бы Би тогда состоялся, он мог бы стать важным средством системной разработки. Не судьба. Позже язык ЯРМО пытался занять нишу.
• Результат примерно соответствует мечте Игоря Григорьевича Пасынкова, когда в 1986 году он позвал меня в курчатник заниматься Си для Эльбруса-Б. Ему хотелось видеть Си не только под юниксом, но и в мониторке.

Я затащил компилятор Би под мониторную систему Дубна. Сделал отдельную ленточку 7/b, на которой лежит бинарник компилятора и рантайм библиотека. Вот классический пример Hello World:

*name B compiler
*tape:7/b,40
*library:40
*trans-main:40020
main() {
    printf("Hello, B!*n");
}
*execute
*end file

Запускаем:

$ dubna b.dub
...
*NAME B COMPILER
*TAPE:7/*,40
*LIBRARY:40
*TRANS-MAIN:40020
                     OVERLAY OT  20/04/25
B COMPILER FOR BESM-6, VERSION 04/2025
COMPILED 3 LINES OF CODE, FOUND 0 ERRORS

*NO LIST
*CALL BLOCKERR
*MADLEN
 MAIN          CP 0.0,      ST 0.0,      RT     1.0*
*READ OLD
*EXECUTE
      *LIBRA:40 = B/DIV       B/EQ        B/GT        B/LT        B/MUL       B/NE        B/RET       B/SAVE0     B/SAVE
      B/TOUT      B/TRUE      CHAR        PRINTD      PRINTO      PRINTF      WRITE       WRITEB      OUT*CNT     OUT*SHFT
      OUT*BUFF    FLUSH       FOUT
≠
         MAIN       01000                PRINTD     01413                B/MUL      01757                ISOTCOSY   06002
         PROGRAM  E 01000                PRINTO     01466                B/GT       01766                ISOTCOS1 E 06053
         B/SAVE0    01011                WRITE      01517                FOUT       01771                DRUMTAP*   06073
         B/RET      01016                B/TRUE     01622                WRCARD     01772                CHKWORD* C 06124
         PRINTF     01023                OUT*CNT    01623                WRWORD   E 02014                PRINT8     06125
         B/SAVE     01256                OUT*SHFT   01624                WBEGIN   E 02033                STOP*      06306
         CHAR       01263                OUT*BUFF   01625                WRIEND   E 02042                EXIT     E 06307
         B/NE       01301                FLUSH      01654                B/TOUT     02075                CBOБOДHO   06335
         B/EQ       01304                B/LT       01744                WRWORD/  C 04000
         WRITEB     01307                B/DIV      01747                XWRITE/  C 06000
≠
HELLO, B!

Компилятор генерит ассемблерный код и пишет его на барабан, то есть временный файл фактически. И переключает мониторку на чтение этого барабана, как бы командой *READ:1. Вызывается Мадлен и превращает ассемблерный код в бинарные объектные модули.

Переписал некоторые функции рантайм библиотеки с ассемблера на Би. К примеру, было:

    writeb: ,name,
         12 ,base,*
c
c Append one byte to output buffer.
c
 b/output:lc,block, w_count, b_shift, buffer(22)
c
    flush:  ,subp,
            ,aax, =377
            ,aex, =12       . compare to linefeed
            ,uza, flush
            ,aex, =12
c
            ,utc, w_count
            ,xts,
            ,aex, =26       . 22 words
            ,u1a, putchar
            ,ita, 13
            ,its,
            ,call, flush
            ,sti,
            ,ati, 13
c
 putchar:   ,bss,           . append byte to buffer
            ,sti,
         11 ,vtm, b/output
         11 ,wtc, 1         . b_shift
            ,asn, 64-40     . shift left
         11 ,wtc, 0         . w_count
         11 ,aox, 2         . read word from buffer
         11 ,wtc, 0         . w_count
         11 ,atx, 2         . write word to buffer
c
         11 ,xta, 1         . b_shift
            ,aex, =50
            ,uza, next_w
            ,aex, =50
            ,arx, =10       . increase shift
         11 ,atx, 1         . b_shift
         13 ,uj,
c
 next_w:    ,bss,           . advance to next word
         11 ,atx, 1         . clear b_shift
         11 ,xta, 0         . w_count
            ,arx, =1        . increment word count
         11 ,atx, 0         . w_count
         13 ,uj,
            ,end,

Стало:

/*
 * Append one byte to output buffer.
 */
writeb(b) {
    extrn out_cnt, out_shft, out_buff;
    auto p;

    b = b & 0377;
    if (b == '*n') {
        flush();
        return;
    }

    if (out_cnt == 22) {
        flush();
    }

    p = &out_buff[out_cnt];
    *p = *p | (b << (40 - out_shft));

    if (out_shft == 40) {
        /* next word */
        out_shft = 0;
        ++out_cnt;
    } else {
        /* next byte */
        out_shft = out_shft + 8;
    }
}

out_cnt;
out_shft;
out_buff[22];

Так ведь понятнее выходит, правда?

Компилятор Би, будучи запущенным на БЭСМ-6, успешно обработал собственный исходный текст и выдал разумный ассемблерный код. До этого я гонял его в кросс-режиме под Линуксом. Но теперь уже и на самой БЭСМ-6 можно. С перекодировкой пришлось помучиться.

Сравниваю ассемблерный код, полученный в кросс-режиме и на БЭСМ. Вижу расхождение в одной строке.

$ diff bbesm.madlen bbesm2.madlen 
5185c5185
<     ,XTS,=37777777777777
---
>     ,XTS,=50000000000001

Это код функции negate().

negate(n) {
  return (-n & 037777777777777);
}

Почему-то на БЭСМ получилась неправильная целочисленная константа. Надо искать багу в арифметике.

Компилятор Би для БЭСМ-6 функционально закончен. То есть все фичи, в нём имеющиеся, вроде работают. Некоторые привычные для нас вещи отсутствуют: инкремент-декремент, сдвиги, операторы типа плюс-присвоить. Нет цикла for и оператора switch. Не поместились они у Кена Томпсона в 16 килобайт памяти PDP-7.

Сгенерённый компилятором код получается неэффективный, но для нас сейчас главное, что он функционально правильный. А насколько он неэффективный - давайте померяем. Возьмём для теста известный алгоритм вычисления e-2 по формуле 1/2! + 1/3! и так далее. Вот реализация на Би: e-2.b. Компилируем, запускаем:

$ bbesm < e-2.b > e-2.madlen
$ besmc e-2.madlen libb.obj
$ time ./e-2.exe
71828 18284 59045 23536 02874 71352 66249 77572 47093 69995
...
88683 31483 28027 06553 83300 46932 90115 74414 75631 39997

real	0m18.310s
user	0m18.302s
sys	0m0.008s

Для сравнения я переписал этот код на Паскаль: e-2.dub. Запустим на том же симуляторе:

$ dubna e-2.dub
...
≠
 71828 18284 59045 23536 02874 71352 66249 77572 47093 69995
...
 88683 31483 28027 06553 83300 46932 90115 74414 75631 39997
------------------------------------------------------------
   Elapsed time: 12.3 seconds
      Simulated: 626677681 instructions
Simulation rate: 51010913 instructions/sec

Выходит 18.3 секунды против 12.3 секунды на Паскале. Не так ужасно, всего в полтора раза медленнее. С оптимизацией Би может оказаться даже эффективнее Паскаля.

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

(из исходников ассемблера для PDP-7)

Вдогонку про представление массивов в языке Би. Поддерживались только одномерные массивы, и назывались они векторами. Из описания языка Би:

7.2 Vector Definitions

An external vector definition has one of the following forms:

name [ ] ;
name [ constant ] ;
name [ ] ival , ival . . . ;
name [ constant ] ival , ival . . . ;

The name is initialized with the lvalue of the base of an external vector. If the vector size is missing, zero is assumed. In either case, the vector is initialized with the list of ivals (See 7.1). The actual size of the vector is the maximum of constant+1 and the number of initial values. Any vector elements which are not explicitly initialized have undefined values.

Туманная фраза "The name is initialized with the lvalue of the base of an external vector" означает, что переменная name изначально содержит адрес начала массива.

Почему бы не подурачиться 1 апреля. Думаю, парсер грамматики Си вполне сойдёт за дурацкую затею. Тем более я ж не сам напрягаться собираюсь, а ИИ подряжу. Я упоминал про ASDL, а есть ещё Ungrammar, другой способ описывать синтаксические деревья. Я попросил Грок сбацать мне грамматику языка Си. Он предложил упрощённый вариант:

// Top-level program structure
TranslationUnit = Declaration*

// Declarations
Declaration = Type Identifier ';'
            | Type Identifier '(' ParameterList ')' CompoundStmt
ParameterList = (Type Identifier (',' Type Identifier)*)?

// Types
Type = 'int'
     | 'float'
     | 'char'
     | 'void'

// Statements
Stmt = CompoundStmt
     | ExprStmt
     | IfStmt
     | WhileStmt
     | ReturnStmt

CompoundStmt = '{' Declaration* Stmt* '}'
ExprStmt = Expr ';'
IfStmt = 'if' '(' Expr ')' Stmt ('else' Stmt)?
WhileStmt = 'while' '(' Expr ')' Stmt
ReturnStmt = 'return' Expr? ';'

// Expressions
Expr = AssignmentExpr
AssignmentExpr = EqualityExpr ('=' EqualityExpr)?
EqualityExpr = RelationalExpr (('==' | '!=') RelationalExpr)?
RelationalExpr = AddExpr (('<' | '>' | '<=' | '>=') AddExpr)?
AddExpr = MultExpr (('+' | '-') MultExpr)*
MultExpr = UnaryExpr (('*' | '/') UnaryExpr)*
UnaryExpr = PrimaryExpr
          | '-' UnaryExpr
          | '!' UnaryExpr
PrimaryExpr = Identifier
            | Number
            | String
            | '(' Expr ')'

// Basic tokens
Identifier = <token>
Number = <token>
String = <token>

Неплохо, вполне годится. А теперь говорю, напиши парсер этой грамматики на Rust. С третьей попытки получился работающий код: c_parser/src/main.rs. Полтыщи строк нетривиального кода одним махом побиваши.

В качестве теста обработаем Си-шную программу:

int x = 42;
int main(int argc) {
    int y = 3 + 5 * 2;
    if (y > x) {
        return 1;
    } else {
        return 0;
    }
}

Компилируем, запускаем:

$ cargo run
...
     Running `/home/vak/c_parser/target/debug/c_parser`
( результат )

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

Как ни странно, в мире всё ещё существуют люди, увлекающиеся разработкой компиляторов.



Блог автора: norasandler.com/book/

Набор тестов: github.com/nlsandler/writing-a-c-compiler-tests

Пример реализации Си компилятора, на языке OCaml: github.com/nlsandler/nqcc2

Концепция copy-on-write не представлена в традиционных языках программирования, поэтому вызывает трудности у народа. Тип Cow<T> в Rust часто используется со строками, чтобы избежать лишнего клонирования. Грок покажет нам упрощённую реализацию.

Question: Please show a possible implementation of Rust's type std::borrow::Cow in C++.

I'll show you how to implement a simplified version of Rust's std::borrow::Cow (Copy-on-Write) in C++. Rust's Cow is an enum that can hold either a borrowed reference (&'a T) or an owned value (T), typically used to avoid unnecessary cloning. In C++, we can approximate this using a combination of templates, variants, and smart pointers.

Here's a possible implementation: cow.cpp.

#include <variant>
#include <memory>
#include <string>
#include <stdexcept>

// A simplified Cow implementation in C++
template<typename T>
class Cow {
private:
    // Using variant to hold either a borrowed pointer or an owned value
    std::variant<const T*, std::unique_ptr<T>> data;

public:
    // Constructor for borrowed value
    explicit Cow(const T* borrowed) : data(borrowed) {
        if (!borrowed) {
            throw std::invalid_argument("Borrowed pointer cannot be null");
        }
    }

    // Constructor for owned value
    explicit Cow(T&& owned) : data(std::make_unique<T>(std::move(owned))) {}

    // Copy constructor
    Cow(const Cow& other) {
        if (std::holds_alternative<const T*>(other.data)) {
            data = std::get<const T*>(other.data);
        } else {
            const auto& owned = std::get<std::unique_ptr<T>>(other.data);
            data = std::make_unique<T>(*owned);
        }
    }

    // Move constructor
    Cow(Cow&& other) noexcept = default;

    // Assignment operators
    Cow& operator=(const Cow& other) {
        if (this != &other) {
            Cow temp(other);
            swap(*this, temp);
        }
        return *this;
    }

    Cow& operator=(Cow&& other) noexcept = default;

    // Access the underlying value (non-mutating)
    const T& operator*() const {
        if (std::holds_alternative<const T*>(data)) {
            return *std::get<const T*>(data);
        }
        return *std::get<std::unique_ptr<T>>(data);
    }

    const T* operator->() const {
        return &(**this);
    }

    // Check if the Cow holds a borrowed value
    bool is_borrowed() const {
        return std::holds_alternative<const T*>(data);
    }

    // Check if the Cow holds an owned value
    bool is_owned() const {
        return std::holds_alternative<std::unique_ptr<T>>(data);
    }

    // Convert to owned value if borrowed (clone on write)
    void to_owned() {
        if (is_borrowed()) {
            data = std::make_unique<T>(*std::get<const T*>(data));
        }
    }

    // Swap implementation
    friend void swap(Cow& lhs, Cow& rhs) noexcept {
        using std::swap;
        swap(lhs.data, rhs.data);
    }
};