теория языков и типов + управление памятьюlanguage & type theory + memory management

Языки Программирования, Семантика и АрхитектураProgramming Languages, Semantics & Architecture

Системы типов и лямбда-исчисление, обобщённое программирование, алгебраические типы данных, модели памяти рантайма, низкоуровневые аллокаторы, PE-файл/жизненный цикл процесса, а также автоматы и формальные языки — фундамент под парсеры и regex-движки. 3 подраздела, 11 пунктов: 1.1 заполнен полностью (3 страницы), в 1.2 заполнен 1.2.4 (PE-файл), 1.3 — новый каркас.Type systems and lambda calculus, generic programming, algebraic data types, runtime memory models, low-level allocators, the PE file/process lifecycle, and automata & formal languages — the foundation under parsers and regex engines. 3 subsections, 11 items: 1.1 is fully filled in (3 pages), 1.2 has 1.2.4 (the PE file) filled in, 1.3 is a new skeleton.

1.1 Теория Языков и Системы Типов1.1 Language theory & type systems

1.1.1 Система типов и лямбда-исчислениеType systems & lambda calculusБестиповое и просто типизированное λ-исчисление, изоморфизм Карри — Говарда, статическая vs динамическая типизация.Untyped and simply-typed λ-calculus, the Curry–Howard isomorphism, static vs dynamic typing. 1.1.2 Обобщённое программирование (Generic Programming)Generic programmingКонцепты, параметрический полиморфизм, мономорфизация vs динамическая диспетчеризация (vtables).Concepts, parametric polymorphism, monomorphization vs dynamic dispatch (vtables). 1.1.3 Алгебраические типы данных (ADT)Algebraic data types (ADT)Суммы и произведения типов, Pattern Matching, формализация недействительных состояний на уровне типов.Sum and product types, pattern matching, making invalid states unrepresentable at the type level.

1.2 Управление Памятью и Жизненным Циклом1.2 Memory & lifetime management

1.2.1 Модели памяти runtimeRuntime memory modelsСтек vs Куча (Heap), RAII (Resource Acquisition Is Initialization), управление ресурсами без GC.Stack vs Heap, RAII (Resource Acquisition Is Initialization), resource management without a GC. 1.2.2 Автоматическое управление памятьюAutomatic memory managementСборка мусора (Mark-and-Sweep, Generational GC, ZGC) и подсчёт ссылок (ARC) — накладные расходы и паузы.Garbage collection (Mark-and-Sweep, Generational GC, ZGC) and reference counting (ARC) — overhead and pauses. 1.2.3 Низкоуровневые аллокаторыLow-level allocatorsУстройство ptmalloc, jemalloc, mimalloc; арены (Arena Allocators) и пулы объектов (Object Pools).How ptmalloc, jemalloc, mimalloc work; arena allocators and object pools. 1.2.4 PE-файл и жизненный цикл процессаThe PE file & process lifecycleОт компиляции до запуска: секции PE (.text/.data/.rodata/.bss), что происходит при загрузке образа, где хранятся константы в незапущенном файле.From compilation to launch: PE sections (.text/.data/.rodata/.bss), what happens when the image loads, where constants live in a file that isn't running.

1.3 Автоматы и Формальные Языки1.3 Automata & formal languages

фундамент под regex-движки, парсеры, компиляторыthe foundation under regex engines, parsers, compilers

1.3.1 Иерархия ХомскогоThe Chomsky hierarchyРегулярные, контекстно-свободные, контекстно-зависимые и рекурсивно перечислимые языки — какой класс машин распознаёт каждый уровень и почему это не просто классификация, а вопрос вычислительных возможностей.Regular, context-free, context-sensitive, and recursively enumerable languages — which class of machine recognizes each level, and why this isn't just a taxonomy but a question of computational power.interview 1.3.2 Конечные автоматы и регулярные выраженияFinite automata & regular expressionsDFA/NFA, эквивалентность NFA и DFA (построение по подмножествам), теорема Клини — почему любой regex-движок либо строит автомат, либо симулирует бэктрекинг с экспоненциальным худшим случаем.DFA/NFA, NFA-DFA equivalence (the subset construction), Kleene's theorem — why every regex engine either builds an automaton or simulates backtracking with an exponential worst case.interview 1.3.3 Контекстно-свободные грамматики и парсингContext-free grammars & parsingАвтоматы с магазинной памятью (PDA), нормальная форма Хомского, парсинг сверху вниз (recursive descent, LL(k)) и снизу вверх (LR/LALR) — то, на чём стоит парсер любого языка программирования.Pushdown automata (PDA), Chomsky normal form, top-down (recursive descent, LL(k)) and bottom-up (LR/LALR) parsing — what every programming language's parser is built on.interview 1.3.4 Машины Тьюринга и разрешимостьTuring machines & decidabilityФормальное определение вычислимости, проблема остановки и её недоказуемость, сведение задач друг к другу как метод доказательства неразрешимости.The formal definition of computability, the halting problem and its unprovability, reducing problems to each other as a method for proving undecidability.

статусstatus

1.1 (система типов и λ-исчисление, обобщённое программирование, алгебраические типы данных) заполнен полностью — 3 страницы с примерами на C++/Rust/Python/TypeScript/Go. В 1.2 заполнен пункт 1.2.4 (PE-файл: секции .text/.rdata/.data/.bss, где хранятся константы до запуска, полный путь компиляция → линковка → загрузка → main) — 1.2.1–1.2.3 остаются каркасом. Нумерация 1.1.3 у ADT исправлена (в исходном плане была опечатка «1.2.3»); карточка 1.2.3 «низкоуровневые аллокаторы» — отдельный, корректно пронумерованный пункт. Добавлен подраздел 1.3 «Автоматы и формальные языки» (иерархия Хомского, конечные автоматы/regex, КС-грамматики/парсинг, машины Тьюринга/разрешимость) — эта тема раньше отсутствовала во всей базе знаний, хотя является стандартным столпом теории CS и фундаментом для regex-движков, парсеров и компиляторов.1.1 (type systems & lambda calculus, generic programming, algebraic data types) is fully filled in — 3 pages with examples in C++/Rust/Python/TypeScript/Go. In 1.2, item 1.2.4 is filled in (the PE file: .text/.rdata/.data/.bss sections, where constants live before launch, the full path from compilation → linking → loading → main) — 1.2.1–1.2.3 remain a skeleton. The 1.1.3 numbering for ADT has been corrected (the source plan had a "1.2.3" typo); the 1.2.3 card for "low-level allocators" is a separate, correctly numbered item. Subsection 1.3 "Automata & formal languages" was added (the Chomsky hierarchy, finite automata/regex, CFGs/parsing, Turing machines/decidability) — this topic was previously absent from the entire knowledge base, despite being a standard pillar of CS theory and the foundation for regex engines, parsers, and compilers.