Язы́к программи́рования — формальный язык, предназначенный для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, определяющих внешний вид программы и действия, которые выполнит исполнитель под её управлением.
Лисп — семейство языков программирования, программы и данные в которых представляются системами линейных списков символов. Лисп был создан Джоном Маккарти для работ по искусственному интеллекту и до сих пор остаётся одним из основных инструментальных средств в данной области. Применяется он и как средство обычного промышленного программирования, от встроенных скриптов до веб-приложений массового использования, хотя популярным его назвать нельзя.
Функциона́льное программи́рование — парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних.
Система типов — совокупность правил в языках программирования, назначающих свойства, именуемые типами, различным конструкциям, составляющим программу — таким как переменные, выражения, функции или модули. Основная роль системы типов заключается в уменьшении числа багов в программах посредством определения интерфейсов между различными частями программы и последующей проверки согласованности взаимодействия этих частей. Эта проверка может происходить статически или динамически, а также быть комбинацией обоих видов.
Standard ML (SML) — компилируемый язык программирования общего назначения высшего порядка, основанный на системе типов Хиндли — Милнера.
Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем для формализации и анализа понятия вычислимости.
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Комбина́торная ло́гика — направление математической логики, занимающееся фундаментальными понятиями и методами формальных логических систем или исчислений. В дискретной математике комбинаторная логика тесно связана с лямбда-исчислением, так как описывает вычислительные процессы.
Ха́скелл Брукс Ка́рри — американский математик и логик.
Unlambda — минимальный функциональный язык программирования, придуманный Дэвидом Мэдором (David Madore). Он основан на комбинаторной логике, варианте лямбда-исчисления, который опускает оператор lambda. Язык полагается в основном на две встроенные функции (s и k) и оператор аппликации (`). Уже это делает язык полным по Тьюрингу, но в нём также есть несколько функций ввода-вывода для возможности взаимодействия с пользователем, функция для ленивых вычислений и короткие эквиваленты некоторых функций.
Категориа́льная абстра́ктная маши́на (КАМ) — это модель вычисления программы, в которой сохраняются особенности аппликативного, функционального либо композиционного стиля. Она опирается на технику аппликативного вычисления.
Аппликативное программирование — один из видов декларативного программирования, в котором написание программы состоит в систематическом осуществлении применения одного объекта к другому. Результатом такого применения вновь является объект, который может участвовать в применениях как в роли функции, так и в роли аргумента и так далее. Это делает запись программы математически ясной. Тот факт, что функция обозначается выражением, свидетельствует о возможности использования значений-функций — функциональных объектов — на равных правах с прочими объектами, которые можно передавать как аргументы, либо возвращать как результат вычисления других функций.
Теория вычислимости и теория сложности вычислений трактует модель вычисления не только как определение множества допустимых операций, использованных для вычисления, но также и относительных издержек их применения. Охарактеризовать необходимые вычислительные ресурсы — время выполнения, объём памяти, а также ограничения алгоритмов или компьютера — можно только в том случае, если выбрана определённая модель вычислений.
Типизированное лямбда-исчисление — это версия лямбда-исчисления, в которой лямбда-термам приписываются специальные синтаксические метки, называемые типами. Допустимы различные наборы правил конструирования и приписывания таких меток, они порождают различные системы типизации.
Вячеслав Эрнстович Вольфенгаген — доктор технических наук, профессор, российский математик и инженер.
Тьюринговская трясина — жаргонное общее название для языков программирования, которые Тьюринг-полны, но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования, зато хорошо подходят для некоторых других задач. Поэтому они интересны для информатики. Многие эзотерические языки программирования также являются «трясинами Тьюринга».
Комбина́торное программирование — парадигма программирования, использующая принципы комбина́торной логики, то есть не требующая явного упоминания аргументов определяемой функции (программы) и использующая вместо переменных комбинаторы и композиции. Является особой разновидностью функционального программирования, но, в отличие от основного его направления, комбинаторное программирование не использует λ-абстракцию.
Комбина́тор неподви́жной то́чки — функция высшего порядка, вычисляющая неподвижную точку другой функции.
Стратегия вычисления — правила семантики языка программирования, определяющие, когда следует вычислять аргументы функции, и какие значения следует передавать. Например, стратегия «вызов-при-упоминании/передача-по-ссылке» диктует, что аргументы должны быть вычислены перед выполнением тела вызываемой функции, и что ей должны быть предоставлены две возможности в отношении каждого аргумента: чтение текущего значения и его изменение посредством операции присваивания. На эту стратегию похожа стратегия редукции в лямбда-исчислении, но есть отличия.
SECD-машина — абстрактная машина, интерпретатор выражений λ-исчисления. Использует четыре стека: S — стек объектов для вычисления рекурсивных выражений, E — контекст, C — управляющая строка, D — дамп, хранилище предыдущих состояний, используемое для возврата из вызова функций.