Quine–McCluskey algorithm

Jun. 10th, 2025 04:28 pm
vak: (Default)
[personal profile] vak
На днях обсуждали со [personal profile] spamsink минимизацию булевских функций. Тема из далёкого студенчества. Задачка нетривиальная, но давно и глубоко проработанная. Озадачил нею Грока, получил два решения:

на Питоне: minimize-boolean-function.py

на Rust: minimize-boolean-function.rs

Функция с 8 переменными вычисляется на Rust за шесть секунд:
$ rustc minimize-boolean-function.rs

$ /usr/bin/time ./minimize-boolean-function

Truth table: 0000000000X10000000000000000000000000000000000000000000000000000010X010X010X010X010X010X010X010X010X010X010X010X010X010X010X010X00000000001X0000000000000000000000000000000000001X1X1X1X1X1X1X1X0000000000000000000000000000000000000000000000000000000000000000
8-variable result: ~ABH + ~B~C~DE~FG + A~BCD
6.26 real 6.22 user 0.03 sys
vak: (Знайка)
[personal profile] vak
Пост в группе PDP-11 на фейсбуке: facebook.com/groups/dec.pdp.11/posts/10163012987613979/

Инструкции по сборке симулятора SIMH и установке операционной системы OpenVMS: openvmshobby.com/vax-vms/openvms-on-vax-simh/



Как молоды мы были

Jun. 8th, 2025 11:48 pm
vak: (Default)
[personal profile] vak
1967



Полезный сервис для улучшательства фоток: https://kontext-chat.replicate.dev

Интересный поворот

Jun. 8th, 2025 11:48 am
vak: (Кризис так себе)
[personal profile] vak
Отец Илона Маска работает на гебешников. Маск скомпроментирован, инвестиции в его затеи становятся токсичными. Это ставит жирный крест на Tesla и SpaceX.
vak: (Житель планеты Узм)
[personal profile] vak
Планета Шелезяка. Воды нет. Воздуха нет. Полезных ископаемых нет. Населена четырьмя роботами. Двое из них на фотке. Кликайте чтобы увеличить.

vak: (Путиномедвед)
[personal profile] vak
На одного заядлого рашитстского Z-писателя наехала цензура. Он теперь жалуется на жизнь (Otvet_Po_Zvezdam.pdf).

Перепощу здесь ценный исторический материал.

Disputed Text/Image Justification Comment
— А что ты мне говорила, когда я писал, что Путина нужно сместить и судить за нарушение Хасавюртовских соглашений? Призыв к смене власти в России. Исключить
— Потрясающе. То есть ты хочешь сказать, я же и виновата в том, что у тебя нет прежних возможностей плеваться желчью?
— Не ты одна. Народ опять взалкал величия и вечных ценностей. Как я еще в девяносто седьмом писал, сравнивая нацистскую Германию и современную Россию, «расцвет национальной культуры даром не проходит».
Приравнивание СССР к гитлеровской Германии. Убрать или переформулировать
Любить эту страну может только тот, кто любит, когда его, извините, дерут в зад. Коллективно. Повзводно. Имеются признаки пропаганды нетрадиционных сексуальных отношений Убрать или переформулировать
Просвещали их двое: некий сильно пожилой представитель «Полудня», неприятный франтоватый энтузиаст, и вторым голосом — местный офицерик, будто соскочивший с плаката типа «Дошли до Берлина»: лицо безмозгло восторженное, розовые крепкие щеки, пшеничный чуб лихо выбивается из-под фуражки... в больших городах таких лиц уже не встретишь. Презрительное отношение к Победе в Великой отечественной войне и советским солдатам Исключить или переформулировать
Лишь через много лет он убедился, что это единственно верная и единственно достойная позиция, что в большом мире лишь она и пользуется уважением. Поэтому так легко он становился своим для совсем, вроде бы, чужих — от прибалтийских якобы ветеранов СС до чеченских так называемых боевиков... Оправдание чеченских боевиков и прибалтийских неонацистов Исключить
Возлюбил, сказал Славомир, исламских прихвостней жидовни и сидит в одних президиумах то с мусликами, то с какой-нибудь валютной Хакамадой... Упоминаются реальные люди. В частности Хакамада, которую автор обвиняет в проституции Удалить
Еврей, вечно невинная овечка, как всегда, со скрипочкой, на худой конец — у синхрофазотрона, таджик, ясен перец, то с лопатой, то с мастерком, армянин, натурально, с книжкой (чаще, правда, с чековой — но ведь все равно с книжкой!); а русский, подлюка, снова, из года в год, из века в век, беспробудно — с окровавленным топором и с пеной на губах. Оскорбление евреев и русских по национальному признаку Удалить
Все диктатуры именно этим и берут — обещают личную безопасность. А потом ежедневно творят такое, что никакая мафия за сто лет не сумеет...
— Ну, адаптированная к свободам двадцать первого века шарашка, — сказал Бабцев, примирительно улыбнувшись. — Все-таки времена не те, пришлось им сделать косметические поправки. Но в целом... А как ты думаешь — Путин про вашу контору в курсе?
— Ну, знаешь... Он мне как-то не отчитывался. Думаю, вряд ли такое дело могло быть организовано без поддержки с самого верха.
Обвинения президента Путина в использовании рабского труда ученых Удалить или переформулировать
Всякий хоть немного интеллигентный россиянин впитывает с молоком матери — одна-единственная спецслужба в мире представляет для него опасность, одна-единственная: своя, российская. Наглая, подлая, открыто презирающая и в то же время беззастенчиво использующая все лучшие свойства души человеческой: доброту, верность, порядочность, чувство долга... Люди для нее — мусор. Лагерная пыль. Всегда. При царях, при генсеках, при президентах всенародно избранных... Всегда. Обвинение спецслужб России в насилии над народом Удалить или переформулировать
А позволь, Микитка, я положу на тебя свою ножку, — пробормотала она. — А он и рад тому: не то что ножку, говорит, но и сама садись на меня. И как увидел он ее белую полную ножку...
— Ты эти секс-прихваты брось, — с негодованием прервал он. — Подрасти сперва!
— Это же «Вий»!..
Сексуальные темы, подросток и ребенок, не достигший возраста согласия Удалить или переформулировать
Недавно в новостях прошло: где-то в Европах боевая организация лесбиянок обнаружилась. Караулили на улицах беременных и били, стараясь вызвать выкидыш. Идеологию придумали: беременность, являющаяся результатом гетеросексуальных контактов, есть вопиющее проявление гомофобии и шовинистической дискриминации сексуальных меньшинств. И суд их чуть не оправдал, что ли; во всяком случае, адвокаты закрутили уж так убедительно, что дальше некуда: беременным, дескать, не следовало выставлять напоказ свое состояние, это было провоцирующее поведение, сами виноваты... Пропаганда ЛГБТ Удалить
Нет, неужто НАСТОЛЬКО взаправду русскому серьезности и ума может вогнать только казарма? Неужели Вовка там кого-то по-настоящему убил — о, конечно, отцы-командиры ему объяснили, что это враг! — и теперь из-за этого почувствовал себя таким полноценным? Чудовищный народ... Презрительное отношение к армии и солдатам Удалить
Безответственное манипулирование такими аляповатыми абстракциями, как «Родина-мать», в наше время как раз и воспринимается отрыжкой сталинских времен. Оскорбительное отношение к символам Победы Удалить
Я, конечно, не утверждаю, что приказ убить известного оппозиционного журналиста Бабцева отдали лично господин Медведев или господин Путин, но весь уклад нынешней жизни в России, вся деятельность преступной власти дает негласный, но явный и однозначный сигнал любому негодяю, у которого чешутся кулаки: убивать честных людей можно... Обвинения Путина и Медведева в убийствах журналиста Бабцева, прототипом которому послужил некий Бабченко, бежавший на Украину. Удалить
vak: (Житель планеты Узм)
[personal profile] vak
В Тихом океане полыхает брошенный корабль, вёзший 3000 автомобилей из Китая в Мексику. Команда пыталась тушить пожар имеющимися средствами, но не осилила. Четверть перевозимых автомобилей электрические, а полыхающие литиевые батареи не так просто потушить. Подали сигнал бедствия и их спас проходящий мимо корабль.



vak: (Кризис так себе)
[personal profile] vak
Есть такое недавнее постановление Нью Йоркского суда:

NYT-v-OpenAI-Preservation-Order-5-13-25.pdf

This document is a court order from the United States District Court for the Southern District of New York, issued on May 13, 2025, by Magistrate Judge Ona T. Wang. It pertains to a copyright infringement litigation involving OpenAI, Inc., specifically addressing the preservation of "output log data" (i.e., records of user interactions with OpenAI’s ChatGPT, such as conversation logs). The case is part of a multi-district litigation (MDL) under case number 25-md-3143, with a related case number 23-cv-11195.

Explanation of the Document

The order focuses on a dispute between the "News Plaintiffs" (likely media organizations alleging copyright infringement by OpenAI) and OpenAI regarding the preservation of output log data. Here’s a breakdown of the key points:

1. Background of the Issue:
  • The News Plaintiffs requested that OpenAI preserve all output log data, which includes user conversations with ChatGPT, as potential evidence in the litigation.
  • OpenAI has been deleting some of this data, either at users’ requests or to comply with privacy laws and regulations globally.
  • The issue was first raised in January 2025, discussed during a conference on January 22, 2025. At that time, the court denied the plaintiffs’ request for "wholesale preservation" of all output log data but asked OpenAI to explore ways to segregate or anonymize data to balance user privacy concerns with the need for evidence preservation.
2. OpenAI’s Position:
  • OpenAI resisted preserving all output log data, citing:
  • User preferences (e.g., users explicitly requesting deletion of their chat logs).
  • Compliance with privacy laws and regulations worldwide that mandate data deletion under certain conditions.
  • The sheer volume of data (described as "many, many billions of conversations").
  • OpenAI noted that a "fraction" of conversations from ChatGPT Free, Pro, and Plus users have not been retained due to their default retention policies, though they didn’t clarify what "fraction" means.
3. Plaintiffs’ Argument:
  • The News Plaintiffs renewed their request for OpenAI to preserve all output log data moving forward, arguing that the volume of deleted conversations is significant and relevant to the litigation.
  • They likely believe this data could demonstrate how OpenAI’s models use or reproduce copyrighted material.
4. Court’s Ruling:
  • The court now orders OpenAI to preserve and segregate all output log data that would otherwise be deleted, whether due to user requests or privacy laws, until further notice.
  • This means OpenAI must retain this data separately (not destroy it) to ensure it’s available for the litigation, even if it would normally be deleted under their policies or legal obligations.
  • The order is forward-looking, applying to data that would be deleted after May 13, 2025.
5. Additional Notes:
  • The court references a January 22, 2025, conference transcript for further context, available in related case dockets.
  • There’s a correction about the judge presiding over the January 22 conference (it was Judge Wang, not Judge Stein, as incorrectly noted in some docket entries).

Relation to Privacy of Your Data

This court order directly relates to the privacy of your data if you are a user of OpenAI’s ChatGPT or similar services. Here’s how:

1. Preservation of Your Conversations:
  • If you’ve interacted with ChatGPT, your conversation logs (output log data) may be retained by OpenAI, even if you requested deletion or if OpenAI would normally delete them to comply with privacy laws (e.g., GDPR in Europe, CCPA in California, or other regulations).
  • The court’s order overrides user deletion requests and OpenAI’s standard data retention policies for the duration of the litigation, meaning your data might be kept longer than you expect.
2. Privacy Concerns:
  • During the January 22, 2025, conference, the court asked OpenAI about anonymizing or segregating data to address privacy concerns. However, the order doesn’t specify whether OpenAI must anonymize the preserved data, so it’s unclear if your personally identifiable information (if any) in the logs will be protected.
  • OpenAI argued that preserving all data could conflict with global privacy laws, which often require companies to honor user deletion requests or delete data after a certain period. This litigation may force OpenAI to retain data in ways that could raise privacy compliance issues.
3. Scope of Data:
  • The order applies to all output log data, including conversations from ChatGPT Free, Pro, and Plus users. If you use any of these services, your interactions are potentially affected.
  • The data preserved may include sensitive or personal information you’ve shared with ChatGPT, depending on the nature of your conversations.
4. Implications for You:
  • If you’re concerned about privacy, this order means your chat logs might be stored and potentially reviewed as part of the litigation, even if you opted for deletion.
  • There’s no indication in the document that this data will be publicly disclosed, but it could be accessed by parties involved in the lawsuit (e.g., plaintiffs, OpenAI, or the court) under controlled conditions (e.g., protective orders).
  • The order is temporary (“until further order of the Court”), so it’s unclear how long OpenAI will need to retain this data.
5. Balancing Act:
  • The court is trying to balance the plaintiffs’ need for evidence in the copyright case with user privacy rights. OpenAI’s reluctance to preserve all data stems from both logistical challenges (billions of conversations) and legal obligations to protect user privacy.
  • However, the court’s decision to prioritize evidence preservation over deletion requests may raise concerns for users who expected their data to be deleted promptly.

What You Can Do

  • Review OpenAI’s Privacy Policy: Check OpenAI’s terms of service and privacy policy (available on their website, likely at openai.com) to understand how your data is handled and what deletion options are available.
  • Limit Sensitive Inputs: Be cautious about sharing personal or sensitive information with ChatGPT, as your conversations may be retained longer than expected due to this litigation.
  • Contact OpenAI: If you’ve requested deletion of your data, you could reach out to OpenAI’s support to inquire about the status of your request in light of this court order.
  • Stay Informed: Monitor updates on this case (docket numbers 25-md-3143 or 23-cv-11195) through public court records or news reports, as future rulings may clarify how preserved data is handled or when OpenAI can resume deletions.
vak: (Знайка)
[personal profile] vak
Structure and Interpretation of Quantum Mechanics — a Functional Framework

Типа такого:
infixl 7 *>
infixl 6 <+>,<->

class Vspace v where
(<+>) :: v -> v -> v
(<->) :: v -> v -> v
(*>) :: Scalar -> v -> v

type HV b = b->Scalar
instance Vspace (HV b) where
(f <+> g) a = f a + g a
(f <-> g) a = f a - g a
(c *> f) a = c*(f a)

Три типа char в Си

Jun. 5th, 2025 09:48 pm
vak: (Default)
[personal profile] vak
Копаясь в семантике компилятора, чего только не узнаешь. Выясняется, в языке Си не два типа "signed char" и "unsigned char", а три. Тип просто "char" отличается от первых двух, хоть и ведет себя как один из них. Обнаружить этот факт можно, попытавшись повторно определить typedef:
$ cat foo.c
typedef char foo;
typedef signed char foo;

$ cc -c foo.c
typedef-char.c:2:21: error: typedef redefinition with different types ('signed char' vs 'char')
2 | typedef signed char foo;
| ^
typedef-char.c:1:14: note: previous definition is here
1 | typedef char foo;
| ^
1 error generated.
С другими типами такого выпендрёжа нет. Компилируется без ошибок:
$ cat bar.c
typedef int bar;
typedef signed int bar;

$ cc -c bar.c

AnyHack-8

Jun. 5th, 2025 06:27 pm
netch80: (finch)
[personal profile] netch80
CESU-8 disallows what is allowed in WTF-8 or MUTF-8.

WTF-8 disallows what is allowed in CESU-8 or MUTF-8.

MUTF-8 disallows what is allowed in WTF-8 or CESU-8.

I find this discriminational. All these hacks are not mutually incompatible. Why canʼt anybody combine them?
vak: (Знайка)
[personal profile] vak
Я вижу, машина Тьюринга на OCaml не произвела впечатления. Слишком незнакомый язык. Давайте для сравнения перепишем её на что-нибудь традиционное, скажем C++17.
#include <deque>
#include <iostream>
#include <optional>
#include <string>
#include <tuple>
#include <unordered_map>

// Types for Turing machine
enum class Symbol { One, Blank };
enum class Direction { Left, Right };
using State           = std::string;
using TransitionKey   = std::tuple<State, Symbol>;
using TransitionValue = std::tuple<State, Symbol, Direction>;
using Transitions     = std::unordered_map<TransitionKey, TransitionValue, std::hash<TransitionKey>>;

struct Tape {
    std::deque<Symbol> data;
    size_t head_pos;
};

// Hash function for TransitionKey
namespace std {
template <>
struct hash<TransitionKey> {
    size_t operator()(const TransitionKey &key) const
    {
        auto [state, sym] = key;
        return hash<string>()(state) ^ (hash<size_t>()(static_cast<size_t>(sym)) << 1);
    }
};
} // namespace std

// Convert symbol to string for printing
std::string symbol_to_string(Symbol sym)
{
    return sym == Symbol::One ? "1" : "_";
}

// Print the current tape and head position
void print_tape(const Tape &tape, const State &state)
{
    std::string left_str, right_str;
    size_t i = 0;
    for (const auto &sym : tape.data) {
        if (i < tape.head_pos) {
            left_str += symbol_to_string(sym);
        } else if (i > tape.head_pos) {
            right_str += symbol_to_string(sym);
        }
        ++i;
    }
    std::cout << "[" << left_str << "] " << symbol_to_string(tape.data[tape.head_pos]) << " ("
              << state << ") " << right_str << "\n";
}

// Move the tape head
void move_head(Tape &tape, Direction dir)
{
    if (dir == Direction::Right) {
        if (tape.head_pos + 1 >= tape.data.size()) {
            tape.data.push_back(Symbol::Blank);
        }
        ++tape.head_pos;
    } else { // Left
        if (tape.head_pos == 0) {
            tape.data.push_front(Symbol::Blank);
        } else {
            --tape.head_pos;
        }
    }
}

// Step the Turing machine
std::optional<State> step(Tape &tape, const State &state, const Transitions &transitions)
{
    TransitionKey current = { state, tape.data[tape.head_pos] };
    auto it               = transitions.find(current);
    if (it == transitions.end()) {
        return std::nullopt; // No transition: halt
    }
    const auto &[new_state, new_symbol, dir] = it->second;
    tape.data[tape.head_pos]                 = new_symbol;
    move_head(tape, dir);
    return new_state;
}

// Run the Turing machine
void run_turing_machine(Tape tape, const State &start_state, const Transitions &transitions,
                        const State &accept_state, const State &reject_state)
{
    State current_state = start_state;
    while (true) {
        print_tape(tape, current_state);
        if (current_state == accept_state) {
            std::cout << "Accepted\n";
            break;
        }
        if (current_state == reject_state) {
            std::cout << "Rejected\n";
            break;
        }
        auto next_state = step(tape, current_state, transitions);
        if (!next_state) {
            std::cout << "Halted (no transition)\n";
            break;
        }
        current_state = *next_state;
    }
}

// Turing machine to add two unary numbers
void example_add()
{
    Transitions transitions = {
        // q0: Move right to find blank
        { { "q0", Symbol::One }, { "q0", Symbol::One, Direction::Right } },
        { { "q0", Symbol::Blank }, { "q1", Symbol::One, Direction::Left } },
        // q1: Move left to start
        { { "q1", Symbol::One }, { "q1", Symbol::One, Direction::Left } },
        { { "q1", Symbol::Blank }, { "qaccept", Symbol::Blank, Direction::Right } }
    };
    // Tape represents 2 + 3: 11_111
    Tape tape = {
        { Symbol::One, Symbol::One, Symbol::Blank, Symbol::One, Symbol::One, Symbol::One }, 0
    };
    run_turing_machine(tape, "q0", transitions, "qaccept", "qreject");
}

int main()
{
    example_add();
}
Кода вышло в два раза больше. Стало ли яснее? Запустим для проверки.
$ c++ -std=c++17 turing-add.cpp -o turing-add
$ ./turing-add
[] 1 (q0) 1_111
[1] 1 (q0) _111
[11] _ (q0) 111
[1] 1 (q1) 1111
[] 1 (q1) 11111
[] _ (q1) 111111
[_] 1 (qaccept) 11111
Accepted
vak: (Украина)
[personal profile] vak
На кадрах зафиксированы удары FPV-дронов СБУ по четырем вражеским аэродромам: «Оленья», «Иваново», «Дягилево» и «Белая», где базировалась стратегическая авиация государства-агрессора, которая регулярно обстреливает мирные украинские города.

Среди пораженных воздушных судов — А-50, Ту-95, Ту-22, Ту-160, а также Ан-12 и Ил-78.

vak: (Знайка)
[personal profile] vak
В качестве иллюстрации к языку 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
vak: (бэсм-6)
[personal profile] vak
Постепенно нарабатываю методику разработки софта посредством ИИ. Законспектирую для памяти, вдруг пригодится для мемуаров. 😀 Вчера удалось заметно продвинуться в Си компиляторе. Нужно сделать проход, который получает от парсера синтаксическое дерево (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), через создание тестов (импортируй юнит тесты из стороннего проекта для этой фичи), до собственно разработки софта (реализуй эту фичу) и его доводки (продолжай чинить исходники пока не пройдут все тесты). Сам я пока такое не решаюсь пробовать. Может со временем. Пока довожу код до ума вручную.

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

Jun. 3rd, 2025 12:48 pm
vak: (U.S.A.)
[personal profile] vak
Когда-то и в наших краях рок-н-ролл запрещали.

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

Jun. 3rd, 2025 11:14 am
vak: (Кризис так себе)
[personal profile] vak
Хотите увидеть фотку Гитлера 1955 года? Здесь на третьей странице.

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

OCaml

Jun. 2nd, 2025 01:18 pm
vak: (Знайка)
[personal profile] vak
Новая книжка на моей полке.



Свет не сошёлся клином на одном Rust. За последние годы появился ещё один значимый язык. В 2023 году OCaml получил престижную премию SIGPLAN Award. Когда-то в юности я фигел от Снобола-4, позже от Scheme. А здесь всё совсем удобно сделано.



Сижу разбираюсь, как устроен NQCC, компилятор Си из книжки, написанный на OCaml. И прихожу к выводу, что сделан он весьма неплохо, причём во многом благодаря OCaml. Если бы я сейчас начинал какую нибудь серьёзную разработку типа компилятора, возможно я бы делал его на OCaml вместо Rust или Golang.

Для примера, перепрём /bin/echo на OCaml.
let process_escapes str =
let len = String.length str in
let buf = Buffer.create len in
let rec loop i =
if i >= len then Buffer.contents buf
else if str.[i] <> '\\' then (
Buffer.add_char buf str.[i];
loop (i + 1)
) else if i + 1 < len then (
match str.[i + 1] with
| 'n' -> Buffer.add_char buf '\n'; loop (i + 2)
| 't' -> Buffer.add_char buf '\t'; loop (i + 2)
| '\\' -> Buffer.add_char buf '\\'; loop (i + 2)
| _ -> Buffer.add_char buf str.[i]; loop (i + 1)
) else (
Buffer.add_char buf str.[i];
loop (i + 1)
)
in
loop 0

let echo no_newline enable_escapes args =
let process = if enable_escapes then process_escapes else fun x -> x in
let output = String.concat " " (List.map process args) in
if no_newline then print_string output
else print_endline output

let main () =
let no_newline = ref false in
let enable_escapes = ref false in
let args = ref [] in
let speclist = [
("-n", Arg.Set no_newline, "do not output the trailing newline");
("-e", Arg.Set enable_escapes, "enable interpretation of backslash escapes");
] in
Arg.parse speclist (fun arg -> args := arg :: !args) "Usage: echo [-n] [-e] [string ...]";
echo !no_newline !enable_escapes (List.rev !args)

let () = main ()
Компилируем, запускаем:
$ ocamlopt -O2 -o echo echo.ml

$ ./echo --help
Usage: echo [-n] [-e] [string ...]
-n do not output the trailing newline
-e enable interpretation of backslash escapes
-help Display this list of options
--help Display this list of options

$ ./echo -e "Hello\nWorld"
Hello
World
Page generated Jun. 11th, 2025 01:33 am
Powered by Dreamwidth Studios