Темы

Теория языков программирования

Programming Language Theory · 112 статей

  1. Каррирование функций: Преобразование функций с несколькими аргументами

    Каррирование функций: преобразование функции с несколькими аргументами в последовательность функций с одним аргументом. Математика, программирование, частичное применение.

    #1452 · 8 мин чтения

  2. Ленивые вычисления в программировании

    Ленивые вычисления в программировании: отложенная оценка выражений, избежание повторных вычислений, работа с бесконечными структурами данных и ошибками.

    #4380 · 3 мин чтения

  3. Меркурий: Функциональный язык логического программирования

    Меркурий – функциональный логический язык программирования, сочетающий Prolog и Haskell. Строгая типизация, надежность и подходит для реальных задач.

    #4770 · 2 мин чтения

  4. Взаимная рекурсия: определение и применение

    Взаимная рекурсия в математике и программировании: определение, примеры (деревья, парсеры). Оптимизация хвостовых вызовов для глубокой рекурсии.

    #4840 · 5 мин чтения

  5. Рекурсия: самоповторяющиеся процессы и определения.

    Рекурсия: определение, примеры в математике и программировании. Самоповторяющиеся концепции и процессы, избегающие бесконечных циклов.

    #6139 · 7 мин чтения

  6. Референциальная прозрачность в программировании и философии языка

    Референциальная прозрачность в программировании и философии: замена выражений эквивалентными значениями не меняет результат. Различия и примеры.

    #6416 · 2 мин чтения

  7. Машина SECD: Виртуальная машина для компиляции функциональных языков программирования

    SECD-машина: виртуальная машина для компиляторов функциональных языков. Основана на лямбда-исчислении, разработана Питером Ландином в 1964 году.

    #7015 · 3 мин чтения

  8. Нотация Z: Формальное описание вычислительных систем

    Z-нотация: формальный язык спецификаций для моделирования компьютерных систем. Разработан Ж.-Р. Абриалем, применяется для чёткого описания программ и систем.

    #8232 · 2 мин чтения

  9. Алгоритмическое решение уравнений: унификация в логике и информатике

    Унификация – алгоритм решения уравнений в логике и информатике. Ключевые понятия: подстановка, типы данных, системы типов, алгоритм Хинли-Милнера.

    #12756 · 7 мин чтения

  10. Денотационная семантика языков программирования: математическое представление

    Денотационная семантика: формализация языков программирования через математические объекты. Определение значений выражений, композиционность семантики.

    #12924 · 6 мин чтения

  11. Теоретические вычислительные модели: абстрактные машины

    Абстрактные машины в информатике: теоретические модели вычислений, анализ работы систем, математическая основа программ. Независимость от железа.

    #14167 · 5 мин чтения

  12. Формальные языки спецификаций в информатике

    Языки спецификаций в информатике: описание систем на высоком уровне, анализ требований и проектирование. Отличаются от языков программирования.

    #45151 · 1 мин чтения

  13. Unlambda: Минималистичный функциональный язык программирования

    Unlambda: минималистичный функциональный язык программирования, основанный на комбинаторной логике. Turing-полный, без переменных и лямбда-выражений.

    #46530 · 4 мин чтения

  14. Комбинаторная логика: формализм без переменных

    Комбинаторная логика: формализм без переменных. Основана на комбинаторах, заменяющих кванторы. Модель вычислений и база функциональных языков программирования.

    #47174 · 4 мин чтения

  15. Комбинатор фиксированной точки Y в комбинаторной логике

    Фиксированные точки в комбинаторной логике и лямбда-исчислении: определение, применение для рекурсивных функций, комбинатор Карри Y. Основы функционального программирования.

    #47276 · 4 мин чтения

  16. Clean: Функциональный язык программирования с уникальной системой типов

    Clean – функциональный язык программирования, разработанный с 1987 года. Похож на Haskell: прозрачность, ленивые вычисления, сборка мусора.

    #50139 · 2 мин чтения

  17. Уникальные типы в функциональном программировании

    Уникальные типы в программировании: гарантия однопоточного использования объектов, оптимизация кода и повышение эффективности функциональных языков.

    #50142 · 2 мин чтения

  18. Формальные методы в разработке программного обеспечения

    Формальные методы в Computer Science: математические техники для разработки и верификации ПО и оборудования. Логика, семантика, типы – повышение надежности!

    #50144 · 9 мин чтения

  19. LCF: Автоматический доказыватель теорем 1970-х годов.

    LCF: интерактивный автоматический доказатель теорем 1970-х. Основан на логике вычислимых функций, ввёл язык ML для тактик доказательства и абстрактных типов данных.

    #50152 · 2 мин чтения

  20. ACL2: Язык программирования и автоматический доказатель теорем

    ACL2: язык программирования и автоматический теорем-доказатель для верификации ПО и оборудования. Основан на Common Lisp, открытый исходный код.

    #50191 · 2 мин чтения

  21. Логика Хоара: Правила проверки корректности программ

    Логика Хоара: формальная система для проверки корректности программ. Правила Хоара, тройки Хоара, доказательство правильности кода, формальные методы.

    #54943 · 2 мин чтения

  22. Программирование с ограничениями

    Программное обеспечение с ограничениями (CP): парадигма решения задач, где связи между переменными задаются в виде ограничений. ИИ, компьютерные науки.

    #56271 · 4 мин чтения

  23. Система Mizar: Формализация математических знаний и доказательств.

    Mizar: формальный язык для математических доказательств, ассистент проверки и библиотека формализованной математики. Проект Mizar – крупнейшая база верифицированных теорем.

    #59879 · 3 мин чтения

  24. Декартово замкнутые категории: теория и приложения

    Декартово замкнутая категория в теории категорий: определение, связь с лямбда-исчислением и логикой. Обобщение – замкнутые моноидальные категории.

    #64867 · 2 мин чтения

  25. Функции высшего порядка

    Функции высшего порядка: определение, примеры в математике и программировании. Принимают/возвращают функции. Операторы, функционалы, HOF.

    #66280 · 2 мин чтения

  26. Коммуницирующие последовательные процессы (CSP): формальная модель конкурентности.

    CSP: язык для описания параллельных систем. Теория конкурентности, разработка языков программирования (occam, Erlang, Go). Применение в промышленности.

    #66721 · 3 мин чтения

  27. Формальная верификация аппаратного и программного обеспечения

    Формальная верификация: доказательство корректности алгоритмов и систем с помощью математических методов. Безопасность, надежность ПО и оборудования.

    #70718 · 5 мин чтения

  28. Операционная семантика языков программирования: подходы и классификация

    Операционная семантика языков программирования: формальное описание выполнения программ, доказательство корректности и безопасности. Структурная и естественная семантика.

    #70721 · 5 мин чтения

  29. Сопоставление с образцом в программировании

    Сопоставление с образцом в программировании: проверка последовательностей на соответствие заданному шаблону. Точное соответствие, регулярные выражения, поиск и замена.

    #71859 · 3 мин чтения

  30. Автоматическое определение типов выражений в формальных языках.

    Автоматическое определение типов выражений в формальных языках: программирование, математика, лингвистика. Вывод типов и их роль в использовании объектов.

    #71861 · 4 мин чтения

  31. Алгебраические типы данных

    Алгебраические типы данных (ADT) в программировании: объединение типов, продуктовые (кортежи, записи) и суммовые типы (варианты). Основы теории типов.

    #72031 · 1 мин чтения

  32. Состояние системы в информатике и вычислительной технике.

    Состояние системы в IT: что это такое? Узнайте о запоминании данных, пространствах состояний и принципах работы stateful систем в компьютерных науках.

    #72295 · 4 мин чтения

  33. Строгость функций в программировании: определение и анализ

    Строгие и нестрогие функции в программировании: определение, семантика, влияние на завершение вычислений и языки программирования. Объяснение "bottom".

    #78201 · 1 мин чтения

  34. Проверка моделей в компьютерных науках

    Проверка моделей в компьютерных науках: метод подтверждения соответствия систем заданным требованиям (безопасности и живости) с помощью логики.

    #78517 · 5 мин чтения

  35. Теоретическая информатика: Основы и направления исследований

    Теоретическая информатика: основы вычислений, алгоритмы, теория формальных языков и лямбда-исчисление. Математические основы компьютерных наук.

    #78927 · 12 мин чтения

  36. Теория областей: Частично упорядоченные множества и семантика программирования

    Теория доменов: раздел математики, изучающий частично упорядоченные множества (posets) и их применение в информатике, особенно в семантике языков программирования.

    #79218 · 9 мин чтения

  37. Типизированные лямбда-исчисления: обзор и классификация

    Лямбда-исчисление с типами: основы функционального программирования, ML, Haskell. Типизация для безопасности и надежности программного кода.

    #86235 · 3 мин чтения

  38. Бисимуляция и системы переходов состояний

    Бисимуляция в компьютерных науках: отношение между системами переходов, моделирующими поведение. Определение, примеры и уточнения понятия.

    #91191 · 2 мин чтения

  39. Математические основы семантики языков программирования

    Семантика языков программирования: математическое изучение смысла кода. Определение вычислений, связь входных и выходных данных, модели вычислений.

    #91197 · 2 мин чтения

  40. Исчисление процессов: π-исчисление и его применения

    π-исчисление: формальная система для описания параллельных вычислений и обмена сообщениями. Применяется в теории игр, криптографии и моделировании процессов.

    #95464 · 6 мин чтения

  41. Действия как основа семантики программирования: подход Уатта и Моссеса.

    Действия семантики: формальная спецификация семантики языков программирования. Объединяет денотационную, операционную и алгебраическую семантику, масштабируемость и модифицируемость.

    #106392 · 6 мин чтения

  42. Синтез программ: от математических требований к автоматическому построению кода.

    Синтез программ: автоматическое создание кода по формальной спецификации. Методы, применение в оптимизации и проверке корректности. Автоматизация разработки.

    #108190 · 1 мин чтения

  43. Представление состояния управления компьютерной программой

    Континуации в программировании: абстрактное представление состояния программы. Реализация контроля, исключений, корутин. Сохранение и возобновление выполнения.

    #109280 · 4 мин чтения

  44. Монады в функциональном программировании: от теории категорий к практике

    Монады в функциональном программировании: обобщенные типы, объединение функций и управление побочными эффектами. Основы из теории категорий.

    #119224 · 3 мин чтения

  45. Типы функций в информатике и математической логике

    Тип функции в информатике: определение, свойства и обозначения (A → B, B^(A)). Важный концепт в математической логике и языках программирования.

    #119809 · 2 мин чтения

  46. Исчисление конструкций: Теория типов Тьерри Коканда

    Калькулус конструкций (CoC): теория типов, созданная Тьерри Кокан. Основа для Coq и других систем доказательства. Математика, программирование, логика.

    #124119 · 1 мин чтения

  47. Питер Ландин: Пионер функционального программирования и информатики

    Питер Ландин: британский ученый-компьютерщик, пионер функционального программирования и семантики. Разработал применение лямбда-исчисления в языках программирования.

    #130980 · 3 мин чтения

  48. Lispkit Lisp: Чистая функциональная среда для исследований

    Lispkit Lisp: чистый функциональный диалект Lisp для исследований. Реализация на SECD-машине, портативность, ленивые вычисления, расширения языка.

    #132164 · 2 мин чтения

  49. Системы эффектов в программировании

    Эффектные системы в программировании: формальное описание побочных эффектов, проверка на этапе компиляции, расширение типов для контроля операций.

    #133021 · 2 мин чтения

  50. Расширенная статическая проверка Java: ESC/Java и OpenJML

    ESC/Java – инструмент статического анализа Java, выявляющий ошибки компиляции. Проверка корректности кода, границ массивов и условий с помощью теоремного решателя.

    #133179 · 2 мин чтения

  51. Охраняемый язык команд: Основы и применение.

    GCL: язык программирования от Дейкстры для разработки и доказательства программ. Компактный синтаксис, недетерминизм и возможность вычисления частей кода.

    #138436 · 3 мин чтения

  52. Стиль продолжений в функциональном программировании

    Стиль программирования CPS: передача управления через продолжения. Подробно о продолжениях, прямом и непрямом стилях в функциональном программировании.

    #141175 · 3 мин чтения

  53. Система F: Типизированное лямбда-исчисление второго порядка

    Лямбда-исчисление с типами (System F): формализация полиморфизма в языках программирования, таких как Haskell и ML. Основа для теории типов и функций.

    #143488 · 3 мин чтения

  54. Логика вычислений с ветвлением времени (CTL) и ее применение в верификации

    Логика вычислений CTL: проверка безопасности и живости программного и аппаратного обеспечения. Ветвление времени, моделирование, формальная верификация.

    #149325 · 2 мин чтения

  55. Процесс-алгебры: Моделирование и анализ конкурентных систем

    Процесс-алгебры: формальное моделирование конкурентных систем в computer science. CSP, CCS, π-исчисление и др. для анализа и синхронизации процессов.

    #151027 · 5 мин чтения

  56. Функциональное программирование: уровень функций и математические объекты

    Функциональное программирование: парадигма от Джона Бэкуса, альтернатива объектно-ориентированному подходу. Эволюция языков и повышение надежности кода.

    #157152 · 2 мин чтения

  57. Функциональное программирование: FP, FL и FP84

    Функциональное программирование (FP): история, основы (лямбда-исчисление), отличия от парадигмы Backus. Язык FL как развитие FP в IBM.

    #157184 · 1 мин чтения

  58. Лямбда-куб: измерения зависимостей в исчислении конструкций.

    Лямбда-куб: математическая логика, теория типов. Исследование обобщений лямбда-исчисления через зависимости типов и термов (зависимые типы, полиморфизм).

    #157501 · 3 мин чтения

  59. Связанная логика: ресурсы, композиция и верификация программ.

    Банчевая логика: субструктурная логика для анализа ресурсов и композиционного анализа систем. Применение в верификации программ и моделировании систем.

    #160104 · 2 мин чтения

  60. Клэр: Функциональный и объектно-ориентированный язык программирования с возможностями обработки правил.

    Claire: функциональный язык программирования с объектно-ориентированными возможностями и системой правил. Open source, CLAIRE4 на Go. Разработка с 2004.

    #161241 · 3 мин чтения

  61. Оператор управления потоком call/cc в функциональном программировании

    Оператор управления потоком call/cc в Scheme: применение к текущей континуации, эквивалентность (lambda (c) (c e2)). Функциональное программирование.

    #176797 · 3 мин чтения

  62. Абстрактные семантические графы: представление выражений в компиляторах

    Абстрактный семантический граф (ASG): что это такое? Представление кода в виде графа, более компактное и сложное, чем AST. Используется компиляторами.

    #185723 · 3 мин чтения

  63. Функции как объекты первого класса в программировании

    Функции первого класса в программировании: передача функций как аргументов, возврат из функций, присваивание переменным. Обзор и история концепции.

    #188541 · 4 мин чтения

  64. Машина X: Теория, варианты и применение в тестировании программного обеспечения.

    X-машина: теоретическая модель вычислений, предложенная Эйленбергом. Структурно схожа с конечным автоматом, оперирует отношениями X→X. Применение в лексической семантике.

    #196083 · 4 мин чтения

  65. Система Maude: Логика переписывания для формальной верификации и анализа.

    Maude – мощная система переписывания, альтернатива C, Java. Бесплатное ПО для моделирования и метапрограммирования с поддержкой рефлексии. Обучение онлайн.

    #198928 · 2 мин чтения

  66. Эстерель: Синхронный язык программирования для реактивных систем.

    Esterel: язык программирования для реактивных систем. Параллелизм, прерывания, разработка моделей управления. Компиляция в C, VHDL, Verilog.

    #202662 · 3 мин чтения

  67. Корекурсия в информатике: синтез данных против анализа

    Корекурсия в информатике: двойственная рекурсии операция. Создание сложных данных из простых, итеративное построение структур, потоки данных.

    #207326 · 4 мин чтения

  68. Теорема о структурированных программах и вычислимость функций

    Теорема Бёма-Якопини: любые вычисления возможны с помощью 3 структур управления – последовательность, выбор, повторение. Основа структурированного программирования.

    #221790 · 2 мин чтения

  69. Уточнение программного обеспечения: методы и подходы.

    Уточнение программного обеспечения: формальная верификация, разработка по методу Scrum, поэтапное преобразование спецификаций в код. Повышение качества ПО.

    #237561 · 2 мин чтения

  70. Логическое программирование с ограничениями: язык CHR

    CHR: декларативный язык логического программирования с ограничениями. Применение: от грамматической индукции до верификации. Правила, ограничения, мультиагентные системы.

    #248087 · 2 мин чтения

  71. Семантические кодировки: Сохранение выразительности и поведения языков

    Семантическая кодировка: перевод между формальными языками, компиляция кода (TeX, LaTeX, OCaml). Преобразование форматов и языков программирования.

    #248568 · 4 мин чтения

  72. Эпиграм: Функциональный язык с зависимыми типами

    Epigram: функциональный язык программирования с зависимыми типами и IDE. Поддержка спецификаций, доказательств и верификации компилятором. Основан на теории типов.

    #265579 · 2 мин чтения

  73. Зависимые типы: типы, зависящие от значений

    Зависимые типы в программировании: типы, зависящие от значений. Уменьшают ошибки, кодируют логические кванторы (∀, ∃) в Agda, Coq, Idris и др.

    #267069 · 4 мин чтения

  74. Коалгебры в теории категорий и их применение в информатике.

    Коалгебра в теории категорий: определение, свойства, связь с алгебрами и ковариетами. Применение в информатике: ленивые вычисления, потоки данных, системы переходов.

    #270391 · 2 мин чтения

  75. Просто типизированное лямбда-исчисление: формальная система и семантика

    Лямбда-исчисление с простой типизацией: формальная система математической логики, предложенная Алонзо Чёрчем. Основы теории типов и избежание парадоксов.

    #270608 · 3 мин чтения

  76. Twelf: Логический фреймворк LF для формализации теории языков программирования.

    Twelf: логическое программирование и теория языков. Реализация логической основы LF от CMU. Объявление типов, констант и определение натуральных чисел.

    #276916 · 3 мин чтения

  77. Теория акторов: Счетность, причинность и порядок прибытия сообщений.

    Актерная модель: теория конкурентных вычислений. Принципы работы акторов, создание сообщений и локальные решения. Основы и модели акторных систем.

    #289408 · 2 мин чтения

  78. Акторная модель и исчисления процессов: Сравнение и различия.

    Акторная модель и исчисления процессов: сравнение подходов к моделированию конкурентных вычислений. Различия, вдохновение, применение в ИТ.

    #289555 · 3 мин чтения

  79. Рекурсивные типы данных

    Рекурсивные типы данных в программировании: определение, примеры (списки, деревья). Динамические структуры, растущие во время выполнения. Индуктивные типы.

    #292443 · 2 мин чтения

  80. Лямбда-подъём: Метапроцесс реструктуризации программного кода

    Лямбда-подъём: оптимизация кода, преобразование локальных функций в глобальные. Устранение свободных переменных, расширение области видимости функций.

    #292711 · 5 мин чтения

  81. Стрелки в информатике: обобщение монады и декларативное программирование.

    Стрелки в информатике: тип классов для декларативного описания вычислений. Обобщение монады, функциональное реактивное программирование, парсеры.

    #302454 · 1 мин чтения

  82. Метод B и Event-B: формальные методы разработки программного обеспечения

    Метод B: формальная разработка ПО. Основан на нотации абстрактных машин, применяется в критически важных системах (Ariane 5, Парижское метро). Инструменты и доказательства.

    #311423 · 3 мин чтения

  83. Коррадо Бём: вклад в теорию программирования и информатику

    Коррадо Бём: биография и вклад в информатику. Структурное программирование, лямбда-исчисление, теорема Бёма-Жакопини и кодировка Бёма-Берардуччи.

    #313117 · 2 мин чтения

  84. Высший порядок абстрактного синтаксиса: представление связывания переменных

    Высокоуровневый абстрактный синтаксис (HOAS) в информатике: представление деревьев синтаксиса с переменными. Структура связывания переменных и их областей видимости.

    #327177 · 1 мин чтения

  85. Неограниченная недетерминированность в конкурентных системах

    Неограниченная недетерминированность в конкурентных системах: задержки обработки запросов могут быть произвольными, но запрос будет выполнен. Теория вычислений.

    #328176 · 5 мин чтения

  86. Язык спецификаций JML для Java-программ

    JML: язык спецификаций для Java. Описывает поведение программ с помощью предусловий, постусловий и инвариантов. Повышает надежность кода и упрощает отладку.

    #329915 · 2 мин чтения

  87. Области степеней в денотационной семантике и теории доменов.

    Power domains в семантике и теории доменов: недетерминированные вычисления, множества значений функций, параллельные системы. Сложные понятия для корректности.

    #330561 · 3 мин чтения

  88. Неопределенность в параллельных вычислениях: дедукция против акторной модели.

    Неопределенность в параллельных вычислениях: влияние арбитров, связь вычислений и дедукции (Хейс, Ковальски). Важно для многоядерных систем и сетей.

    #330970 · 3 мин чтения

  89. Джон Чарльз Рейнольдс: Жизнь и вклад в информатику

    Джон Чарльз Рейнольдс (1935-2013) – американский ученый-компьютерщик, профессор Сиракузского и Карнеги-Меллона. Теоретическая физика, информатика.

    #333403 · 2 мин чтения

  90. Strictness analysis

    #333652 · 2 мин чтения

  91. Филип Ли Вадлер: вклад в теорию и практику программирования

    Филип Вадлер – американский ученый-компьютерщик, эксперт в теории типов и языков программирования (Haskell, Java, XQuery). Разработки в области функционального программирования.

    #341275 · 2 мин чтения

  92. Evaluation strategy

    #352349 · 5 мин чтения

  93. Анонимная рекурсия: вызов функции без имени

    Анонимная рекурсия в программировании: реализация без явного вызова функции по имени. JavaScript, функции высшего порядка, рефлексия. Плохой стиль.

    #358709 · 2 мин чтения

  94. Проверка во время выполнения: анализ и мониторинг работающих систем

    Проверка во время выполнения: анализ систем, выявление ошибок и соответствия свойствам. Формальные спецификации, логика, регулярные выражения для надёжности ПО.

    #361437 · 17 мин чтения

  95. Основы параметрического полиморфизма

    Параметрический полиморфизм в программировании: обобщенные типы, функции для разных типов данных (списки, и т.д.). Основы generic programming.

    #381434 · 3 мин чтения

  96. Единичный тип данных в программировании

    Единичный тип в теории типов: определение, свойства и роль в математической логике и программировании. Обозначает тип с единственным значением.

    #397988 · 3 мин чтения

  97. Денотационная семантика акторной модели и композиционность программ

    Денотационная семантика акторной модели: теория, композиционность и анализ программ. Развитие и применение акторов в современных языках программирования.

    #403774 · 2 мин чтения

  98. Процедурные параметры в программировании: история и применение

    Процедурные параметры в программировании: передача функций как аргументов. Мощный инструмент для модификации кода библиотек без изменений в них. Pascal, C.

    #416061 · 2 мин чтения

  99. Рекурсия в программировании: принципы и применение

    Рекурсия в программировании: метод решения задач через самовызов функций. Основа компьютерной науки, поддерживаемая большинством языков программирования.

    #420775 · 9 мин чтения

  100. Актерная модель: история развития и первые реализации.

    Актерная модель: история развития (1973-наст.вр.). Параллельные вычисления, реализация, приложения, теория доказательств. Автоматическая сборка мусора.

    #422468 · 2 мин чтения