- Подстановка
-
- Это статья о подстановке как о синтаксической операции над термами. Возможно, вас интересует перестановка.
В математике и компьютерных науках подстановка — это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной.
Содержание
Определения и обозначения
Для подстановки не существует универсальной, согласованной нотации, равно как и стандартного определения. Понятие подстановки варьируется не только в рамках разделов, но и на уровне отдельных публикаций. В целом, можно выделить контекстную подстановку и подстановку «вместо». В первом случае место в терме, где происходит замена, задаётся контекстом, то есть частью терма, «окружающим» это место. В частности, такое понятие подстановки используется в переписывании. Второй вариант более распространён. В этом случае подстановка обычно задаётся некоторой функцией из множества переменных в множество термов. Для обозначения действия подстановки, как правило, используют постфиксную нотацию. Например, означает результат действия подстановки на терм .
В подавляющем большинстве случаев требуется чтобы подстановка имела конечный носитель, то есть, чтобы множество было конечным. В таком случае её можно задать простым перечислением пар «переменная-значение». Поскольку каждую такую подстановку можно свести к последовательности подстановок, замещающих всего по одной переменной каждая, не ограничивая общности можно считать, что подстановка задаётся одной парой «переменная-значение», что обычно и делается.
Последнее определение подстановки является, видимо, самым типичным и часто используемым. Однако и для него не существует единой общепринятой нотации. Наиболее часто для обозначения подстановки a вместо x в t используется запись t[a/x], t[x:=a] или t[x←a].
Подстановка переменной в λ-исчислении
В λ-исчислении, подстановка определяется структурной индукцией. Для произвольных объектов , и произвольной переменной результат замещения произвольного свободного вхождения в считается подстановкой и определяется индукцией по построению :
- (i) базис: : объект совпадает с переменной . Тогда ;
- (ii) базис: : объект совпадает с константой . Тогда для произвольных атомарных ;
- (iii) шаг: : объект неатомарный и имеет вид аппликации . Тогда ;
- (iv) шаг: : объект неатомарный и является -абстракцией . Тогда [;
- (v) шаг: : объект неатомарный и является -абстракцией , причем . Тогда:
- для и или ;
- для и и .
Подстановка переменной в программировании
- Подстановка переменной (англ. substitution) в аппликативном программировании понимается следующим образом. Для вычисления значения функции f на аргументе v применяется запись f(v)}, где f определена конструкцией f(x) = e. Запись f(v) в этом случае означает, что в выражении e происходит замещение, или подстановка переменной x на v. Выполнение замещения происходит в соответствии с семантикой вычислений.
- Подстановка переменной (англ. assignment) в программировании понимается как присваивание. Оператор присваивания является проявлением эффекта «бутылочного горлышка» фон Нейманна для традиционных языков программирования[1]. От этого свободны аппликативные вычислительные системы.
См. также
Ссылки
- ↑ Лекция Дж. Бэкуса при получении премии Тьюринга в 1977 г.: Можно ли освободить программирование от стиля фон Нейманна?
Категории:- Комбинаторика
- Информатика
Wikimedia Foundation. 2010.