раздел 02

Программирование / CS

Фундаментальный блок: ФП, парсеры, алгоритмы и структуры под нагрузкой. Не устаревает вместе с фреймворками.

32 урока66 тем · 8 кластеров

Начать раздел

Хочу пройти

Без входа у каждого урока видно начало. Войди, чтобы читать целиком, отмечать пройденное и решать задачи. войти

Уроки раздела

Начать раздел

Понятия курса

Понятия разобраны внутри уроков. Нажми на понятие, чтобы открыть урок, где оно объясняется.

Фундамент

Кэш-память и локальностьИерархия L1/L2/L3, cache line 64 байта, пространственная и временная локальность, latency numbers.урок 14 · Машина под уроком: процессор, память, кэш и ОС
Миры языков программированияПроектируем небольшой язык: одиннадцать решений о модулях, каналах, макросах, типах, actors, живой среде, стеке, логике, массивах и владении.урок 31 · Разрабатываем язык: одиннадцать миров, одиннадцать решений
Побитовые операции и битовые маскиСемь операторов JS, приоритеты, флаги через 1 << n, проверка и снятие, упаковка полей.урок 13 · Биты и байты: как машина кодирует числа
Процессор, адресация и сегменты памятиРегистры, такты, разрядность. Память как массив байтов, сегменты text/data/heap/stack, стек вызовов против кучи.урок 14 · Машина под уроком: процессор, память, кэш и ОС
Процессы, потоки и управление памятьюВытесняющий планировщик ОС, поток как стек плюс регистры, malloc/free против GC, mark-and-sweep и поколения.урок 14 · Машина под уроком: процессор, память, кэш и ОСопираются: урок 32
Системы счисления, бит и байтДвоичная и hex записи, литералы 0b/0x, бит, байт, машинное слово, степени двойки.урок 13 · Биты и байты: как машина кодирует числаопираются: урок 14
Сложность алгоритмов: основыBig-O в практическом измерении. Учиться оценивать на глаз.урок 1 · Типы и системы типов: фундаментопираются: урок 18
Целые со знаком: дополнительный кодДополнительный код, переполнение как арифметика по модулю, ToInt32 и трюк x|0 в JS.урок 13 · Биты и байты: как машина кодирует числаопираются: урок 14
Абстракция как отображениеАбстракция это отображение из грязного конкретного домена в чистый (Cousot 1977, Дейкстра), живёт не в коде.урок 1 · Типы и системы типов: фундамент
Алгебраические типы данныхSum-типы и product-типы как алгебра данных. Pattern matching разбирает значение по конструктору и делает невозможные состояния непредставимыми.урок 1 · Типы и системы типов: фундаментопираются: урок 26
Потоки и модели выполненияПроцесс и поток, переключение контекста, fork в многопоточном процессе, модели N:1, 1:1 и M:N, TLS, реентерабельность, потоки против событийного цикла.урок 32 · Потоки: N:1, 1:1, M:N и событийный цикл
Типы и системы типовТип как множество значений + допустимых операций. Что гарантирует type system.урок 1 · Типы и системы типов: фундаментопираются: урок 2
Co/contravariance, subtyping, LSPФункции контравариантны по аргументам, ковариантны по результату. Liskov substitution.урок 1 · Типы и системы типов: фундамент
Curry-Howard correspondenceТип = proposition, программа = proof. Пропозиция A->B = доказательство.урок 1 · Типы и системы типов: фундамент

ООП

Три кита ООПИнкапсуляция, наследование (+ агрегация, композиция), полиморфизм.урок 2 · ООП без карго-культа: столпы, SOLID, GRASPопираются: урок 3
Виды полиморфизмаAd-hoc (overloading), параметрический (generics), subtype.урок 2 · ООП без карго-культа: столпы, SOLID, GRASP
Композиция vs наследованиеFragile base class, diamond, coupling. Почему композиция почти всегда лучше.урок 2 · ООП без карго-культа: столпы, SOLID, GRASP
Паттерны GoFCreational / Structural / Behavioral. Знать назначение каждого, не зубрить UML.урок 3 · Паттерны GoF и что от них осталось в JSопираются: урок 26
JS/TS-актуальные паттерныStrategy, Observer, Factory, Builder, Decorator, Proxy, Facade, Adapter, CoR, Visitor, Fluent Interface, Value Object.урок 3 · Паттерны GoF и что от них осталось в JSопираются: урок 28
SOLIDSRP, OCP, LSP, ISP, DIP. Для каждого знать пример из реального кода.урок 2 · ООП без карго-культа: столпы, SOLID, GRASPопираются: урок 3
GRASPInformation Expert, Creator, Controller, Low Coupling, High Cohesion, Polymorphism, Pure Fabrication, Indirection, Protected Variations.урок 2 · ООП без карго-культа: столпы, SOLID, GRASP

ФП

Pure functions, immutability, HOFЧистые функции, referential transparency, immutability, функции как данные.урок 4 · ФП: четыре столпа и переход от мутации к выражениюопираются: урок 5, урок 6, урок 19, урок 20
Воркшоп: оценщик авто на fp-tsEq, Ord, Semigroup, Monoid и Reader на одном домене: сравнение машин, порядок по дороговизне, склейка профилей владельцев, финальная мини-игра.урок 8 · fp-ts на практике: оценщик автомобилей
Словарь жаргона ФПАрность, замыкание, каррирование, функтор, монада, катаморфизм, линза: термины ФП с короткими примерами на JavaScript.урок 30 · Жаргон ФП: словарь терминов с примерами на JavaScript
Composition: pipe, compose, KleisliКомпозиция функций как способ структурировать программу.урок 5 · Композиция и итерация без цикловопираются: урок 6, урок 7, урок 20
Currying, partial applicationКаррирование как способ адаптации функций к pipe-композиции.урок 5 · Композиция и итерация без циклов
Monadic error handling, Railway Oriented ProgrammingКомпозиция функций, возвращающих Result. Две дорожки вычисления (успех и ошибка): bind и map ведут значение по успешной дорожке, а ошибка проскакивает мимо без вложенных проверок.урок 6 · Типы и ошибки: parse, не validate
Option / Either / Result для ошибокMonadic error handling вместо try/catch. Сделать ошибки частью типа.урок 6 · Типы и ошибки: parse, не validateопираются: урок 7, урок 9, урок 21, урок 23
Functor / Applicative / Monadmap / ap / flatMap. Typeclass-дисциплина в TS через fp-ts.урок 7 · Typeclass-дисциплина: Functor, Applicative, Monad, HKT в TSопираются: урок 9, урок 21, урок 22, урок 23, урок 24
Lenses и opticsLens, Prism, Traversal: композабельные геттеры и сеттеры для вложенных иммутабельных структур. monocle-ts.урок 23 · Lenses и optics: композабельные апдейты вложенных структуропираются: урок 24
Algebraic effectsResumable exceptions с handler-ами. OCaml 5, Koka, Unison.урок 9 · Effect systems: эффект как значение, от монад к algebraic effects
Effect systemsIO/Task/TaskEither, ReaderTaskEither, MTL-стек. Effect.ts / ZIO как single Effect<A,E,R>.урок 9 · Effect systems: эффект как значение, от монад к algebraic effectsопираются: урок 12, урок 25, урок 27
Persistent collections, zippersИммутабельные структуры данных с structural sharing.урок 19 · Персистентные структуры: иммутабельность без копирования
Higher-Kinded DataОдна модель данных, много форм: поля завёрнуты в параметр-конструктор f. Валидация, partial, form state из одного объявления.урок 24 · Higher-Kinded Data: одна модель, много форм
Lazy evaluation и стратегии вычисленияEager против lazy, thunks, WHNF, fusion. Generators и Iterator Helpers как ленивость в JS, lazy Effect против eager Promise.урок 25 · Lazy evaluation: стратегии, thunks, fusion, generators
Recursion schemescata, ana, hylo, para: рекурсия как переиспользуемая алгебра поверх Fix. Свёртки AST без ручного обхода.урок 22 · Recursion schemes: алгебра рекурсии cata, ana, hylo, paraопираются: урок 25

Алгоритмы и структуры

Базовые структуры данныхArray, LinkedList, Stack, Queue, Deque, HashTable, BST, Heap, Trie, Graph.урок 15 · Алгоритмы: Big-O, структуры и базовые паттерныопираются: урок 18, урок 19
Поиск и сортировкиQuick/Merge/Heap/TimSort/Counting/Radix. Linear/Binary/Interpolation/Exponential.урок 15 · Алгоритмы: Big-O, структуры и базовые паттерны
Алгоритмические парадигмыDivide & Conquer, DP (memo/tabulation), Greedy, Backtracking, Two pointers / sliding window.урок 16 · Графы и парадигмы: DFS, BFS, Dijkstra, DP, Backtracking, Sliding Window
Графы и обходыDFS/BFS, Dijkstra, Bellman-Ford, Floyd-Warshall, A*, MST, SCC, topo sort.урок 16 · Графы и парадигмы: DFS, BFS, Dijkstra, DP, Backtracking, Sliding Window
Поиск в строке: KMP, Boyer-Moore, Rabin-KarpНаивный поиск и его худший случай, префикс-функция и KMP, прыжки Boyer-Moore, rolling hash.урок 18 · Поиск в строке: от наивного цикла к KMP и автоматам
Поиск как автомат: ДКА, regex-движки, Aho-CorasickKMP как конечный автомат, НКА с бэктрекингом против ДКА, бор с суффиксными ссылками для тысяч образцов.урок 18 · Поиск в строке: от наивного цикла к KMP и автоматам
Interview-level patternsTwo pointers, Binary search on answer, Hashing, Monotonic stack, Tree/BST, Trie, Heap, Graph, DP, Backtracking, Bit tricks.урок 17 · Production-grade структуры: LRU, Bloom, Trie, Union-Find, Consistent Hashing
Production-grade структурыLRU/LFU/ARC, Bloom/Cuckoo, HyperLogLog, Count-Min Sketch, Skip List, B/B+/LSM, Trie, Union-Find, Segment/Fenwick, Merkle, Consistent Hashing, Rate Limiters.урок 17 · Production-grade структуры: LRU, Bloom, Trie, Union-Find, Consistent Hashing
Сложность глубжеAmortized analysis, cache locality, parallel complexity, online vs offline, approximation, Monte Carlo / Las Vegas.урок 17 · Production-grade структуры: LRU, Bloom, Trie, Union-Find, Consistent Hashing

Метапрограммирование

Виды метапрограммированияПрепроцессинг, интроспекция, рефлексия, скаффолдинг, codemod.урок 28 · Метапрограммирование в JS и TS: Proxy, Reflect, декораторы
Proxy, Reflect, DecoratorsJS-механики: Proxy, Reflect, Stage 3 decorators, reflect-metadata.урок 28 · Метапрограммирование в JS и TS: Proxy, Reflect, декораторыопираются: урок 29
AST tools: ts-morph, babel, codemodКодомод-инструменты для автоматических миграций и анализа.урок 29 · AST-инструменты и DSL: от codemod до своего языка
DSL: четыре уровня абстракцииОт fluent API через JSX и data-as-language до full custom syntax (Racket macros).урок 29 · AST-инструменты и DSL: от codemod до своего языка
Континуации: CPS и абстракция эффектовТип (next: (a: A) => T) => T, pure/bind/each, одна task и раннеры: чистый, Result, Promise, multi-shot. Филинский 1994.урок 11 · Континуации: колбэк, доведённый до абстракции
От метапрограммирования к DDD через DSLПравильный уровень абстракции = правильная математика домена. DSL и bounded context.урок 29 · AST-инструменты и DSL: от codemod до своего языка
Своя ORM на Effect.tsFree/AST + phantom-typed builder + Datamapper: PGlite, SQLite, Repository, Identity Map, Unit of Work, FiberRef-транзакции и миграции.урок 12 · Своя ORM на TypeScript + Effect.ts
IO-монада: free vs closureДва пути: tagged union с continuations vs closure с RealWorld-passing. Монада как паттерн.урок 10 · Построй свою IO-монадуопираются: урок 11, урок 12

Парсеры и AST

Lexer -> Parser -> AST -> IR -> CodegenЭтапы парсинга. Где регулярки уместны, а где нет.урок 20 · Парсеры: грамматики, recursive descent, Pratt, LR, PEGопираются: урок 29
Parser combinatorsМонадический recursive descent. Композиция парсеров.урок 21 · Парсер-комбинаторы: парсер как монада, декларативный DSL поверхопираются: урок 22
Recursive descent, LL/LR/PEGТипы парсеров и trade-offs. Когда нужен формальный grammar.урок 20 · Парсеры: грамматики, recursive descent, Pratt, LR, PEG

Моделирование бизнес-процессов

DDD-фундаментBounded context, ubiquitous language, domain model, service layer, repository.урок 26 · Моделирование: домен, контракты и конечные автоматы
FSM как способ моделированияAutomata-based programming. Когда жизненный цикл сущности: конечный автомат.урок 26 · Моделирование: домен, контракты и конечные автоматыопираются: урок 27
Контрактное программированиеPre/postcondition, invariants. Закон Деметры. Aspect-Oriented Programming.урок 26 · Моделирование: домен, контракты и конечные автоматыопираются: урок 27

Верификация

Property-Based TestingГенеративные тесты ищут counterexamples. fast-check, hypothesis. Formal-lite.урок 27 · Верификация: ящик инструментов от свойств до доказательств
Static analysisLinters, taint analysis, abstract interpretation. От ESLint до Semgrep / CodeQL.урок 27 · Верификация: ящик инструментов от свойств до доказательств
Fuzz testingAFL, libFuzzer, jazzer. Coverage-guided мутации входов.урок 27 · Верификация: ящик инструментов от свойств до доказательств
Hoare logic / Design by Contract{P} S {Q}. Eiffel-style контракты, Spec#, JML.урок 27 · Верификация: ящик инструментов от свойств до доказательств
Model checking: TLA+, Alloy, PTLA+ (Lamport) для distributed/concurrency, Alloy для structural, P для protocols.урок 27 · Верификация: ящик инструментов от свойств до доказательств
Refinement typesLiquidHaskell, F*, Refinement TS. Уточнение типов предикатами.урок 27 · Верификация: ящик инструментов от свойств до доказательств
Theorem proving: Coq, Lean, Agda, IdrisПолная корректность через dependent types. CompCert, seL4, F*: где это окупается.урок 27 · Верификация: ящик инструментов от свойств до доказательств

Фундамент

ООП

ФП

Алгоритмы и структуры

Метапрограммирование

Парсеры и AST

Моделирование бизнес-процессов

Верификация

Databases

Микросервисы (Go)

Data Engineering

Системное программирование: Zig, ассемблер, Verilog