Сталина пережил

Хотите увидеть фотку Гитлера 1955 года? Здесь на третьей странице.

cia.gov/readingroom/docs/HITLER%2C%20ADOLF_0003.pdf

Санта Круз против

Когда-то и в наших краях рок-н-ролл запрещали.

Интеллект из ларца, исполнительный с лица

Постепенно нарабатываю методику разработки софта посредством ИИ. Законспектирую для памяти, вдруг пригодится для мемуаров. 😀 Вчера удалось заметно продвинуться в Си компиляторе. Нужно сделать проход, который получает от парсера синтаксическое дерево (AST), по нему строит таблицу символов (переменных и функций), таблицу типов (структуры и union), и расставляет типы во всех выражениях.

Гляжу в книжку, беру за образец исходники компилятора NQCC и делаю как там написано. Но на чистом Си. Много нетривиального кода. Работа получается нудная и малоинтересная. Без посторонней помощи я бы не взялся. Но к счастью, нынче мы имеем ИИ, а он товарищ неленивый. Хотя часто невнимательный склонный к многословности вместо упрощения. И тут нужно иметь подход. Чем я и занимаюсь. Вчера удалось подобрать ключик и посредством серии запросов наворотить солидную часть компилятора. По сути творчески переписать модуль typecheck.ml с OCaml на Си, с учётом всех деталей.

Итак, первый запрос:

Hi Grok,
I'm attaching file "typecheck.ml" in OCaml, which parses an AST and builds two tables: Symbols and Type_table.
I'm going to rewrite this code into C.
Please analyze this code focusing on "Symbols".
I will create a map "symtab" in C which converts a name of symbol into a pointer to a data structure which describes that symbol.
Please tell me, how this data structure should look.
Structure of AST in C is defined in file "ast.h", attached.
Methods of Symbols in OCaml are defined in file "symbols.ml", also attached.

Таблица символов представляет собой map, отображающий строку (имя переменной или функции) в структуру Symbol. Но что должно быть в этой структуре? Я сначала сам ломал голову, а потом догадался озадачить Грока. В ответ получил весьма осмысленные определения нужных структур, и даже пример работы с ними. Подпилил маленько вручную.

Но это структуры, а к ним бы и методы. Следующий запрос:

Good. Here is my decision: file "symbol.h" attached.
Now please give me a full list of signatures for routines in C which I need to implement for symtab, like the above add_static_var(). For example:
void symtab_add_static_var(char *name, Type *t, bool global, InitKind kind, StaticInitializer *data);

Грок немедленно выдал список нужных функций. Все вместе после моих доделок можно видеть в файле: symtab.h

Хорошо, это таблица символов. А теперь примемся за таблицу типов:

Very good.
Now please do a similar analysis focusing on "Type_table".
I'm attaching file "type_table.ml", which defines details of the OCaml implementation.
I will create a map "typetab" in C which converts a name into a pointer to a data structure which describes each type entry.
Please tell me, how this data structure should look.

И методы к таблице типов:

Good.
Now please give me a full list of signatures for routines in C which I need to implement for typetab, like the above typetab_add_struct_definition().

Результат здесь: typetab.h

Неплохо дело идёт, подумал я. А давай Грок весь этот код перепишет на Си. Сам бы я несколько месяцев трудился. Только как бы не нагородил лишнего. Пришлось давать подробные указания.

Good.
Now please reimplement the above file "typecheck.ml" in C.
The goal is to iterate through the AST tree, build symtab and typetab, and annotate the AST tree with type information.
It means to set values of Type *type field of each struct Expr, and similar field in initializers.
Use structures defined in the above files "symbol.h" and "typetab.h".
Avoid reallocation of AST nodes, better modify them in place.
Assume routines declared in the above files "symtab.h" and "typetab.h" are available.
In case any fieilds are missing in the AST definition, please let me know.
Note that for allocating or copying AST nodes a set of routines is available, for example:

Type *new_type(TypeKind kind);
Type *clone_type(const Type *type);

Удивительно, но код на Си получился очень неплохой. Процентов на 95%. Мелочёвку я уж сам подчищу, ладно. Но обнаружились две тонкости, которые мне Грок указал в комментариях. В узле Initializer дерева AST недоставало поля Type *type. И структуру StaticInitializer Грок сорганизовал в массив вместо списка. Надо исправить.

Not bad!
I've added Type *type to Initializer in "ast.h", new file attached.
I'm also uploading new version of symtab.h - please use it instead of the old one.
Note that it has type StaticInitializer which is a linked list (with field *next).
Please use it instead of Initializers handle static initializers.
I'm also uploading file "initializers.ml" in OCaml in case it helps.

Please update the C implementation: use new field "type" in Initializer in ast.h,
and handle static initializers using struct StaticInitializer.

Уже лучше. Ещё раз пересмотрел внимательно весь код - есть ещё где упростить.

Please modify function:

Declaration *typecheck_fn_decl(Declaration *d)

to accept ExternalDecl instead of Declaration.
Let it return void, as it never reallocates the argument. Let it be:

void typecheck_fn_decl(ExternalDecl *d)

Also modify other similar functions to return void.

Отлично. Имеем 1300 строк неплохого кода на Си. Главное - понятного кода, простого в сопровождении. Результат после моих правок можно видеть в файле: typecheck.c

Там ещё не всё вычищено, в процессе. Но теперь займёмся тестами.Сами тесты я сделаю, а от Грока требуется вход и ожидаемый результат.

Excellent.
Please propose a comprehensive list of unit tests for the typecheck implementation.
Each test case should have:
1. A snippet of C code to be converted to AST by parser. The parser is already available.
2. Expected contents of symtab.
3. Expected contents of typetab.
4. Expected contents of "type" fields in the resulting AST tree.

Имеем данные для десятка простых тестов для начала: typecheck_tests.cpp

Но это потом, когда таблицы символов и типов заработают. А пока примемся за таблицу символов.

Please create isolated unit tests for symtab_xxx() routines. Use Googletest.

Результат в файле: symtab_tests.cpp

Аналогично для таблицы типов:

Good. Now please create tests for typetab routines.

Тоже не вопрос: typetab_tests.cpp

Тут надо понимать, что исходники, получаемые от ИИ, не есть законченное решение. Часто они даже компилируются без ошибок, в простых случаях работают с первого раза. Это не так важно. Можно указать Гроку на ошибку компиляции или при запуске программы, и он её исправит. С 90% вероятностью. Исправить я и сам могу, нетрудно. Ценность в том, что код получается достаточно простым и понятным, легким в понимании, а значит и в последующем развитии.

Я слышал, уже есть платные сервисы, где ИИ берёт на себя весь цикл разработки, от формулировки задачи (создай Jira тикет: добавить такую-то фичу), через организацию непрерывной сборки (активируй CI build на Github Actions), через создание тестов (импортируй юнит тесты из стороннего проекта для этой фичи), до собственно разработки софта (реализуй эту фичу) и его доводки (продолжай чинить исходники пока не пройдут все тесты). Сам я пока такое не решаюсь пробовать. Может со временем. Пока довожу код до ума вручную.

Машина Тьюринга на OCaml

В качестве иллюстрации к языку OCaml вот вам реализация машины Тьюринга. В студенчестве я на Рефале такое писал. Жаль не сохранилось.

(* Types for Turing machine *)
type symbol = One | Blank
type direction = Left | Right
type state = string
type transition = (state * symbol) * (state * symbol * direction)
type tape = { left: symbol list; head: symbol; right: symbol list }

(* Convert symbol to string for printing *)
let string_of_symbol = function
    | One -> "1"
    | Blank -> "_"

(* Print the current tape and head position *)
let print_tape tape state =
    let left_str = List.map string_of_symbol tape.left |> String.concat "" in
    let right_str = List.map string_of_symbol tape.right |> String.concat "" in
    Printf.printf "[%s] %s (%s) %s\n" left_str (string_of_symbol tape.head) state right_str

(* Move the tape head *)
let move_head tape dir =
    match dir with
    | Right ->
      let new_right, new_head = match tape.right with
          | [] -> ([], Blank)
          | h :: t -> (t, h)
      in
      { left = tape.head :: tape.left; head = new_head; right = new_right }
    | Left ->
      let new_left, new_head = match tape.left with
          | [] -> ([], Blank)
          | h :: t -> (t, h)
      in
      { left = new_left; head = new_head; right = tape.head :: tape.right }

(* Step the Turing machine *)
let step tape state transitions =
    let current = (state, tape.head) in
    match List.assoc_opt current transitions with
    | None -> None (* No transition: halt *)
    | Some (new_state, new_symbol, dir) ->
      let new_tape = { tape with head = new_symbol } in
      let moved_tape = move_head new_tape dir in
      Some (moved_tape, new_state)

(* Run the Turing machine *)
let run_turing_machine tape start_state transitions accept_state reject_state =
    let rec run tape state =
        print_tape tape state;
        if state = accept_state then Printf.printf "Accepted\n"
        else if state = reject_state then Printf.printf "Rejected\n"
        else match step tape state transitions with
            | None -> Printf.printf "Halted (no transition)\n"
            | Some (new_tape, new_state) -> run new_tape new_state
    in
    run tape start_state

(* Turing machine to add two unary numbers *)
let example_add () =
    let transitions = [
        (* q0: Move right to find blank *)
        (("q0", One), ("q0", One, Right));
        (("q0", Blank), ("q1", One, Left));
        (* q1: Move left to start *)
        (("q1", One), ("q1", One, Left));
        (("q1", Blank), ("qaccept", Blank, Right));
    ] in
    (* Tape represents 2 + 3: 11_111 *)
    let tape = { left = []; head = One; right = [One; Blank; One; One; One] } in
    run_turing_machine tape "q0" transitions "qaccept" "qreject"

(* Run the example *)
let () = example_add ()

Вышеприведённая программа на машине Тьюринга складывает два числа 2+3, записанные как последовательность единиц: 11 111. В результате получается 5, то есть 11111. Запускаем:

$ ocaml turing_add.ml 
[] 1 (q0) 1_111
[1] 1 (q0) _111
[11] _ (q0) 111
[1] 1 (q1) 1111
[] 1 (q1) 11111
[] _ (q1) 111111
[_] 1 (qaccept) 11111
Accepted