Как найти лямбду через скорость и период

Обновлено: 04.07.2024

Чтобы описать колебательные процессы и отличить одни колебания от других, используют 6 характеристик. Они называются так (рис. 1):

амплитуда,
период,
частота,
циклическая частота,
фаза,
начальная фаза.

Такие величины, как амплитуду и период, можно определить по графику колебаний.

Начальную фазу, так же, определяют по графику, с помощью интервала времени \(\large \Delta t\), на который относительно нуля сдвигается начало ближайшего периода.

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

А фазу определяют с помощью формулы, в которую входит интересующий нас момент времени t колебаний. Читайте далее.

Что такое амплитуда

Амплитуда – это наибольшее отклонение величины от равновесия, то есть, максимальное значение колеблющейся величины.

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

В случае электрических колебаний, в которых изменяется заряд, ее измеряют в Кулонах. Если колеблется ток – то в Амперах, а если – напряжение, то в Вольтах.

К примеру, пусть колеблется величина \( \large x \). Тогда символом \( \large x_ \) обозначают амплитуду колебаний этой величины.

С помощью графика амплитуду можно определить так (рис. 2):

Рис. 2. Амплитуда – это максимальное отклонение от горизонтальной оси либо вверх, либо вниз. Горизонтальная ось проходит через уровень нуля на оси, на которой отмечены амплитуды

Что такое период

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

\( \large T \left( c \right) \) – период колебаний.

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

Чтобы по графику колебаний определить период (рис. 3), нужно найти два одинаковых значения колеблющейся величины. После, провести от этих значений к оси времени пунктиры. Расстояние между пунктирами – это период колебаний.

Период – это время одного полного колебания.

На графике период найти удобнее одним из таких способов (рис. 4):

Рис. 4. Удобно определять период, как расстояние между двумя соседними вершинами, либо между двумя впадинами

Что такое частота

Поэтому, размерность частоты — это единицы колебаний в секунду:

\( \large \nu \left( \frac \right) \).

Иногда в учебниках встречается такая запись \( \large \displaystyle \nu \left( c^ \right) \), потому, что по свойствам степени \( \large \displaystyle \frac = c^ \).

Начиная с 1933 года частоту указывают в Герцах в честь Генриха Рудольфа Герца. Он совершил значимые открытия в физике, изучал колебания и доказал, что существуют электромагнитные волны.

Одно колебание в секунду соответствует частоте в 1 Герц.

Чтобы с помощью графика определить частоту, нужно на оси времени определить период. А затем посчитать частоту по такой формуле:

Существует еще один способ определить частоту с помощью графика колеблющейся величины. Нужно отмерить на графике интервал времени, равный одной секунде, и сосчитать количество периодов колебаний, уместившихся в этот интервал (рис. 5).

Что такое циклическая частота

Колебательное движение и движение по окружности имеют много общего – это повторяющиеся движения. Одному полному обороту соответствует угол \(\large 2\pi\) радиан. Поэтому, кроме интервала времени 1 секунда, физики используют интервал времени, равный \(\large 2\pi\) секунд.

\( \large \displaystyle \omega \left( \frac> \right) \)

Примечание: Величину \( \large \omega \) так же называют круговой частотой, а еще — угловой скоростью (ссылка).

Обычная \( \large \nu \) и циклическая \( \large \omega \) частота колебаний связаны формулой:

Слева в формуле количество колебаний измеряется в радианах на секунду, а справа – в Герцах.

Чтобы с помощью графика колебаний определить величину \( \large \omega \), нужно сначала найти период T.

Затем, воспользоваться формулой \( \large \displaystyle \nu = \frac \) и вычислить частоту \( \large \nu \).

И только после этого, с помощью формулы \( \large \omega = 2\pi \cdot \nu \) посчитать циклическую \( \large \omega \) частоту.

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

Определить величину \( \large \omega \) по графику колебаний можно еще одним способом. На оси времени отметить интервал, равный \(\large 2\pi\), а затем, сосчитать количество периодов колебаний в этом интервале (рис. 6).

Рис. 6. На графике циклическая (круговая) частота – это количество периодов, уместившихся в 2 пи секунд

Что такое начальная фаза и как определить ее по графику колебаний

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

Такой, начальный угол отклонения, называют начальной фазой колебаний. Обозначим этот угол (рис. 7) какой-нибудь греческой буквой, например, \(\large \varphi_ \).

\(\large \varphi_ \left(\text \right) \) — начальная фаза, измеряется в радианах (или градусах).

Начальная фаза колебаний – это угол, на который мы отклонили качели, перед тем, как их отпустить. Из этого угла начнется колебательный процесс.

Рассмотрим теперь, как величина \(\large \varphi_ \) влияет на график колебаний (рис. 8). Для удобства будем считать, что мы рассматриваем колебания, которые происходят по закону синуса.

Рис. 8. Вертикальное положение стартовой точки в момент времени t = 0 и сдвиг графика по горизонтали определяется начальной фазой

Вторая кривая на рисунке обозначена красным цветом. Начало ее периода сдвинуто вправо относительно точки t = 0. Поэтому, для красной кривой, начавшей новый период колебаний спустя время \(\large \Delta t\), начальный угол \(\large \varphi_ \) будет отличаться от нулевого значения.

Определим угол \(\large \varphi_ \) с помощью графика колебаний.

Обратим внимание (рис. 8) на то, что время, лежащее на горизонтальной оси, измеряется в секундах, а величина \(\large \varphi_ \) — в радианах. Значит, нужно связать формулой кусочек времени \(\large \Delta t\) и соответствующий ему начальный угол \(\large \varphi_ \).

Как вычислить начальный угол по интервалу смещения

Алгоритм нахождения начального угла состоит из нескольких несложных шагов.

Сначала определим интервал времени, обозначенный синими стрелками на рисунке. На осях большинства графиков располагают цифры, по которым это можно сделать. Как видно из рис. 8, этот интервал \(\large \Delta t\) равен 1 сек.
Затем определим период. Для этого отметим одно полное колебание на красной кривой. Колебание началось в точке t = 1, а закончилось в точке t =5. Взяв разность между этими двумя точками времени, получим значение периода.

\[\large T = 5 – 1 = 4 \left( \text \right)\]

Из графика следует, что период T = 4 сек.

Рассчитаем теперь, какую долю периода составляет интервал времени \(\large \Delta t\). Для этого составим такую дробь \(\large \displaystyle \frac\):

Полученное значение дроби означает, что красная кривая сдвинута относительно точки t = 0 и черной кривой на четверть периода.

Нам известно, что одно полное колебание — один полный оборот (цикл), синус (или косинус) совершает, проходя каждый раз угол \(\large 2\pi \). Найдем теперь, как связана найденная доля периода с углом \(\large 2\pi \) полного цикла.

Для этого используем формулу:

\(\large \displaystyle \frac \cdot 2\pi = \frac<\pi > =\varphi_ \)

Значит, интервалу \(\large \Delta t\) соответствует угол \(\large \displaystyle \frac<\pi > \) – это начальная фаза для красной кривой на рисунке.

Примечания:

Физики начинают отсчет времени из точки 0. Поэтому, время в задачах будет величиной не отрицательной.
На графике колебаний начальная фаза \( \varphi_\) влияет на вертикальный сдвиг точки, из которой стартует колебательный процесс. Значит, можно для простоты сказать, что колебания имеют начальную точку.

Благодаря таким допущениям график колебаний при решении большинства задач можно изображать, начиная из окрестности нуля и преимущественно в правой полуплоскости.

Что такое фаза колебаний

Рассмотрим еще раз обыкновенные детские качели (рис. 9) и угол их отклонения от положения равновесия. С течением времени этот угол изменяется, то есть, он зависит от времени.

В процессе колебаний изменяется угол отклонения от равновесия. Этот изменяющийся угол называют фазой колебаний и обозначают \(\varphi\).

Различия между фазой и начальной фазой

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

Первый угол называют начальной \( \varphi_\) фазой (рис. 10а), она считается неизменной величиной. А второй угол – просто \( \varphi\) фазой (рис. 10б) – это величина переменная.

Рис. 10. Перед началом колебаний задаем начальную фазу — начальный угол отклонения от равновесия. А угол, который изменяется во время колебаний, называют фазой

Как на графике колебаний отметить фазу

На графике колебаний фаза \(\large \varphi\) выглядит, как точка на кривой. С течением времени эта точка сдвигается (бежит) по графику слева направо (рис. 11). То есть, в разные моменты времени она будет находиться на различных участках кривой.

На рисунке отмечены две крупные красные точки, они соответствуют фазам колебаний в моменты времени t1 и t2.

Рис. 11. На графике колебаний фаза – это точка, скользящая по кривой. В различные моменты времени она находится в разных положениях на графике

А начальная фаза на графике колебаний выглядит, как место, в котором находится точка, лежащая на кривой колебаний, в момент времени t=0. На рисунке дополнительно присутствует одна мелкая красная точка, она соответствует начальной фазе колебаний.

Как определить фазу с помощью формулы

Пусть нам известны величины \(\large \omega\) — циклическая частота и \(\large \varphi_\) — начальная фаза. Во время колебаний эти величины не изменяются, то есть, являются константами.

Время колебаний t будет величиной переменной.

Фазу \(\large \varphi\), соответствующую любому интересующему нас моменту t времени, можно определить из такого уравнения:

Левая и правая части этого уравнения имеют размерность угла (т. е. измеряются в радианах, или градусах). А подставляя вместо символа t в это уравнение интересующие нас значения времени, можно получать соответствующие им значения фазы.

Что такое разность фаз

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

Рассмотрим два колебательных процесса (рис. 12). Каждый имеет свою начальную фазу.

\( \large \varphi_\) – для первого процесса и,

\( \large \varphi_\) – для второго процесса.

Определим разность фаз между первым и вторым колебательными процессами:

Величина \(\large \Delta \varphi \) показывает, на сколько отличаются фазы двух колебаний, она называется разностью фаз.

Как связаны характеристики колебаний — формулы

Движение по окружности и колебательное движение имеют определенную схожесть, так как эти виды движения могут быть периодическими.

Поэтому, основные формулы, применимые для движения по окружности, подойдут так же, для описания колебательного движения.

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

\( \large T \left( c \right) \) – время одного полного колебания (период колебаний);

\( \large N \left( \text \right) \) – количество полных колебаний;

\( \large t \left( c \right) \) – общее время для нескольких колебаний;

\(\large \nu \left( \text \right) \) – частота колебаний.

Количество и частота колебаний связаны формулой:

Связь между частотой и циклической частотой колебаний:

\(\large \displaystyle \omega \left( \frac> \right) \) – циклическая (круговая) частота колебаний.

Фаза и циклическая частота колебаний связаны так:

\(\large \varphi_ \left( \text \right) \) — начальная фаза;

\(\large \varphi \left( \text \right) \) – фаза (угол) в выбранный момент времени t;

Между фазой и количеством колебаний связь описана так:

Интервал времени \(\large \Delta t \) (сдвигом) и начальная фаза колебаний связаны:

\(\large \Delta t \left( c \right) \) — интервал времени, на который относительно точки t=0 сдвинуто начало ближайшего периода.

Буквой λ (лямбда) обозначается длина волны того или иного излучения. Эту величину можно измерить, можно рассчитать теоретически, а если излучение является видимым, то даже определить на глаз.

Чтобы рассчитать длину волны излучения, зная частоту и скорость распространения этого излучения, поделите вторую величину на первую. Если же вместо частоты известен период, умножьте его на скорость распространения излучения. Наконец, если известна циклическая частота излучения, умножьте скорость на 2π, а затем результат поделите на циклическую частоту.
Чтобы результат получился в системе СИ, предварительно переведите в нее же все величины из условия задачи. Затем переведите результат обратно в удобные для вас единицы.

Если излучение является световым, длину его волны в вакууме определите на глаз: красный - от 635 до 690 нм, оранжевый - 590, желтый - от 570 до 580, зеленый - от 510 до 520, синий - от 440 до 480, фиолетовый - от 380 до 400.

Имея специальный прибор - спектрометр, определить длину волны света можно точнее, чем на глаз. Если он является полихроматическим, определить его спектральный состав можно только с помощью этого прибора Для этого направьте световой поток во входное окно прибора. Он пройдет через щель, перпендикулярную призме, а затем и через саму призму, а затем попадет либо на шкалу, либо на линейку датчиков. Во втором случае, обработку результата измерения осуществит электронный блок прибора.

Для нахождения длины волны излучения дециметрового или сантиметрового диапазона подключите антенну к волномеру, после чего начните плавно менять ее размер. Когда он станет равен половине длины волны, показания волномера окажутся максимальными.

Направьте тонкий луч света строго перпендикулярно дифракционной решетке. На экране появится ряд пятен. Измерьте угол между воображаемой линией, продолжающей ход луча после решетки, линией, соединяющей точку входа луча в решетку с первым из пятен. Найдите синус этого угла, а затем умножьте на расстояние между двумя соседними линиями решетки. Получится длина волны, которая будет выражена в тех же единицах, что и расстояние между линиями.

Лямбда-исчисление — это формальная система в математической логике для выражения подсчетов на основе абстракции и применения функций с использованием привязки и подстановки переменных. Это универсальная модель, которую можно применять для проектирования любой машины Тьюринга. Впервые введена лямбда-исчисления Черчем, известным математиком, в 1930-х годах.

Система состоит из построения лямбда-членов и выполнения над ними операций сокращения.

Пояснения и приложения

Вам будет интересно: Какие элементы входят в социальную структуру общества, виды и функции социальных групп

Греческая буква lambda (λ) используется в лямбда-выражениях и лямбда-терминах для обозначения связывания переменной в функции.

Лямбда-исчисление может быть нетипизировано или напечатано. В первом варианте функции могут быть применены только в том случае, если они способны принимать данные этого типа. Типизированные лямбда-исчисления слабее, могут выражать меньшее значение. Но, с другой стороны, они позволяют доказывать больше вещей.

Одной из причин того, что существует много разных типов — это желание ученых сделать больше, не отказываясь от возможности доказывать сильные теоремы лямбда-исчислений.

Вам будет интересно: Семейный этикет: основы и правила, особенности отношений с близкими родственниками

Система находит применение во многих различных областях математики, философии, лингвистики, и компьютерных наук. В первую очередь, лямбда-исчисления — это расчет, который сыграл важную роль в развитии теории языков программирования. Именно стили функционального создания реализуют системы. Они также являются актуальной темой исследований в теории этих категорий.

Для чайников

Лямбда-исчисление была введена математиком Алонзо Черчем в 1930-х годах в рамках исследования основ науки. Первоначальная система была показана как логически несовместимая в 1935 году, когда Стивен Клин и Дж. Б. Россер разработали парадокс Клини-Россера.

В последствии, в 1936 году Черч выделил и опубликовал только ту часть, которая имеет отношение к расчетам, то, что сейчас называется нетипизированным лямбда-исчислением. В 1940 он также представил более слабую, но логически непротиворечивую теорию, известную как система простого типа. В свое работе он объясняет всю теорию простым языком, поэтому, можно сказать, что Черч опубликовал лямбду исчисления для чайников.

Вам будет интересно: Профессии железнодорожников: перечень, описание, необходимое образование

До 1960-х годов, когда выяснилось его отношение к языкам программирования, λ стала лишь формализмом. Благодаря применениям Ричарда Монтегю и других лингвистов в семантике естественного языка, исчисление стало занимать почетное место как в лингвистике, так и в информатике.

Происхождение символа

Введение в лямбда исчисление

Система состоит из языка терминов, которые выбираются определенным формальным синтаксисом, и набора правил преобразования, которые позволяют манипулировать ими. Последний пункт можно рассматривать как эквациональную теорию или как операционное определение.

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

Лямбда-термины

Следующие три правила дают индуктивное определение, которое можно применять для построения всех синтаксически допустимых понятий:

Переменная x сама по себе является действительным лямбда-термином:

если T это ЛТ, и x непостоянная, то (lambda xt) называется абстракцией.
если T, а также s понятия, то (TS) называется приложением.

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

Определение

Вам будет интересно: Виды контроля качества продукции при производстве

Лямбда-выражения состоят из:

переменных v 1, v 2. v n.
символов абстракции 'λ' и точки '.'
скобок ().

Множество Λ, может быть определено индуктивно:

Если x переменная, то x ∈ Λ;
x непостоянная и M ∈ Λ, то (λx.M) ∈ Λ;
M, N ∈ Λ, то (MN) ∈ Λ.

Обозначение

Чтобы сохранить нотацию лямбда-выражений в незагроможденном виде, обычно применяются следующие соглашения:

Внешние скобки опущены: MN вместо (MN).
Предполагается, что приложения остаются ассоциативными: взамен ((MN) P) можно написать MNP.
Тело абстракции простирается дальше вправо: λx.MN означает λx. (MN), а не (λx.M) N.
Сокращается последовательность абстракций: λx.λy.λz.N можно λxyz.N.

Свободные и связанные переменные

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

Множество свободных переменных M обозначается как FV (M) и определяется рекурсией по структуре терминов следующим образом:

FV (x) = , где x - переменная.
FV (λx.M) = FV (M) .
FV (MN) = FV (M) ∪ FV (N).

Формула, которая не содержит свободных переменных, называется закрытой. Замкнутые лямбда-выражения также известны как комбинаторы и эквивалентны терминам в комбинаторной логике.

Сокращение

Значение лямбда-выражений определяется тем, как они могут быть сокращены.

Существует три вида урезания:

α-преобразование: изменение связанных переменных (альфа).
β-редукция: применение функций к своим аргументам (бета).
η-преобразование: охватывает понятие экстенсиональности.

Здесь речь также идет о полученных эквивалентностях: два выражения являются β-эквивалентными, если они могут быть β-преобразованы в одно и то же составляющее, а α / η-эквивалентность определяется аналогично.

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

(λ x.M) N является бета-редексом в выражении замены N на x в M. Составляющее, к которому сводится редекс, называется его редуктом. Редукция (λ x.M) N есть M [x: = N].

Если x не является свободной в M, λ х. М х также ет-REDEX с регулятором М.

α-преобразование

Альфа-переименования позволяют изменять имена связанных переменных. Например, λ x. х может дать λ у. у. Термины, которые отличаются только альфа-преобразованием, называются α-эквивалентными. Часто при использовании лямбда-исчисления α-эквивалентные считаются взаимными.

Точные правила для альфа-преобразования не совсем тривиальны. Во-первых, при данной абстракции переименовываются только те переменные, которые связаны с одной и той же системой. Например, альфа-преобразование λ x.λ x. x может привести к λ y.λ x. х, но это может не ввергнуть к λy.λx.y Последний имеет иной смысл, чем оригинал. Это аналогично понятию программирования затенения переменных.

Во-вторых, альфа-преобразование невозможно, если оно приведет к захвату непостоянной другой абстракцией. Например, если заменить x на y в λ x.λ y. x, то можно получить λ y.λ y. у, что совсем не то же самое.

В языках программирования со статической областью видимости альфа-преобразование можно использовать для упрощения разрешения имен. При этом следя за тем, чтобы понятие переменной не маскировало обозначение в содержащей области.

В нотации индекса Де Брюйна любые два альфа-эквивалентных термина синтаксически идентичны.

Замена

Изменения, написанные Е [V: = R], представляют собой процесс замещения всех свободных вхождений переменной V в выражении Е с оборотом R. Подстановка в терминах λ определяется лямбдой исчисления рекурсии по структуре понятий следующим образом (примечание: x и y - только переменные, а M и N - любое λ-выражение).

y [x: = N] ≡ y, если x ≠ y

(M 1 M 2) [x: = N] ≡ (M 1 [x: = N]) (M 2 [x: = N])

(λ x.M) [x: = N] ≡ λ x.M

(λ y.M) [x: = N] y λ y. (M [x: = N]), если x ≠ y, при условии, что y ∉ FV (N).

Для подстановки в лямбда-абстракцию иногда необходимо α-преобразовать выражение. Например, неверно, чтобы (λ x. Y) [y: = x] приводило к (λ x. X), потому что замещенный x должен был быть свободным, но в итоге был связанным. Правильная замена в этом случае (λ z. X) с точностью до α-эквивалентности. Стоит обратить внимание, что замещение определяется однозначно с верностью до лямбды.

β-редукция

Бета-редукция отражает идею применения функции. Бета-восстановительный определяется в терминах замещения: ((X V. E) Е ') является Е [V: = Е'].

Например, предполагая некоторое кодирование 2, 7, ×, имеется следующее β-уменьшение: ((λ n. N × 2) 7) → 7 × 2.

Бета-редукция может рассматриваться как то же самое, что и концепция локальной сводимости при естественной дедукции через изоморфизм Карри – Ховарда.

η-преобразование

Эта-конверсия выражает идею экстенсиональности, которая в этом контексте заключается в том, что две функции равны тогда, когда они дают одинаковый результат для всех аргументов. Эта конвертация обменивает между λ x. (F x) и f всякий раз, когда x не кажется свободным в f.

Вам будет интересно: Откуда появились славяне: определение, описание и история

Данное действие может рассматриваться как то же самое, что и концепция локальной полноты в естественной дедукции через изоморфизм Карри – Ховарда.

Нормальные формы и слияние

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

Тем не менее можно показать, что β-редукция сливается при работе до α-преобразования (т. е. можно считать две нормальные формы равными, если возможно α-преобразование одной в другую).

Поэтому и сильно нормализующие члены, и слабо налаживающие понятия имеют единственную нормальную форму. Для первых терминов любая стратегия сокращения гарантированно приведет к типичной конфигурации. Тогда как для слабо нормализующих условий некоторые стратегии сокращения могут не найти ее.

Дополнительные методы программирования

Существует большое количество идиом создания для лямбда-исчисления. Многие из них были первоначально разработаны в контексте использования систем в качестве основы для семантики языка программирования, эффективно применяя их в качестве создания низкого уровня. Поскольку некоторые стили включают лямбда-исчисление (или что-то очень похожее) в качестве фрагмента, эти методы также находят применение в практическом создании, но затем могут восприниматься как неясные или чужие.

Именованные константы

В лямбда-исчислении библиотека принимает форму набора ранее определенных функций, в которой термины являются просто конкретными константами. Чистое исчисление не имеет понятия именованных неизменных, поскольку все атомные лямбда-термины являются переменными. Но их также можно имитировать, выделив непостоянную в качестве имени константы, используя лямбда-абстракцию для связывания этой изменчивой в основной части, и применить эту абстракцию к намеченному определению. Таким образом, если использовать f для обозначения M в N, можно сказать,

Авторы часто вводят синтаксическое понятие, такое как let, чтобы разрешить писать все в более интуитивном порядке.

Заметным ограничением этого let является то, что имя f не определено в M, поскольку M находится вне области привязки лямбда-абстракции f. Это означает, что атрибут рекурсивной функции не может использоваться как M с let. Более продвинутая синтаксическая конструкция letrec, которая позволяет писать рекурсивные определения функций в этом стиле, вместо этого дополнительно использует комбинаторы с фиксированной точкой.

Печатные аналоги

Данный тип является типизированным формализмом, который использует символ для обозначения анонимной функции абстракция. В этом контексте типы обычно являются объектами синтаксической природы, которые присваиваются лямбда-терминам. Точная натура зависит от рассматриваемого исчисления. С определенной точки зрения, типизированные ЛИ можно рассматривать как уточнения нетипизированного ЛИ. Но с другой стороны, их также можно считать более фундаментальной теорией, а нетипизированное лямбда-исчисление — особым случаем только с одним типом.

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

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

А сегодня немного теории. Я не считаю, что лямбда-исчисление является необходимым знанием для любого программиста. Однако, если вам нравится докапываться до истоков, чтобы понять на чем основаны многие языки программирования, вы любознательны и стремитесь познать все в этом мире или просто хотите сдать экзамен по функциональном программированию (как, например, я), то этот пост для вас.

Что это такое

Лямбда-исчисление - это формальная система, то есть набор объектов, формул, аксиом и правил вывода. Благодаря таким системам с помощью абстракций моделируется теория, которую можно использовать в реальном мире, и при этом выводить в ней новые математически доказуемые утверждения. Например, язык запросов SQL основан на реляционном исчислении. Благодаря математической базе, на которой он существует, оптимизаторы запросов могут анализировать алгебраические свойства операций и влиять на скорость работы.

Но речь сегодня не о SQL, а о функциональных языках. Именно для них лямбда-исчисление является основой. Функциональные языки далеко не столь популярны, как, например, объектно-ориентированные, но тем не менее прочно занимают свою нишу. Кроме того, многие идеи из функционального программирования и лямда-исчисления постепенно прокрадываются в другие языки, под видом новых фич.

Если вы изучали формальные языки, то знаете о таком понятии как Машина Тьюринга. Эта вычислительная абстракция определяет класс вычислимых функций. Этот класс столь важен, так как по тезису Черча он эквивалентен понятию алгоритма. Другими словами, любую программу, которую можно запрограммировать на вычислительном устройстве, можно воспроизвести и на машине Тьюринга. А для нас главное то, что лямбда-исчисление по мощности эквивалентно машине Тьюринга и определяет этот же класс функций. Причем создателем лямбда-исчисления является тот самый Алонзо Черч!

Основные понятия

В нотации лямбда-исчисления есть всего три типа выражений:

Переменные: ` x, y, z `
Абстракция - декларация функции: ` lambda x.E ` . Определяем функцию с параметром ` x ` и телом ` E `.
Аппликация - применение функции ` E_1 ` к аргументу ` E_2 ` : ` E_1 E_2`

Сразу пара примеров:

Тождественная функция: ` lambda x. x `
Функция, вычисляющая тождественную функцию: ` lambda x.(lambda y . y) `

Соглашения

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

Аппликация лево-ассоциативна. То есть выражение ` x y z ` читается как ` (x y) z `.
В абстракции группируем скобки вправо. Другими словами, читая абстракцию необходимо распространять ее максимально вправо насколько возможно. Пример: выражение ` lambda x. x \ lambda y . x y z ` эквивалентно ` lambda x. (x \ (lambda y . ((x y) z))) ` , так как абстракция функции с аргументом ` x ` включила в себя все выражение. Следом было проведено включение абстракцией с аргументом ` y ` и ,наконец, в теле этой функции были расставлены скобки для аппликации.

Области видимости переменных

Определим контекст переменной, в котором она может быть использована. Абстракция ` lambda x.E ` связывает переменную ` x `. В результате мы получаем следующие понятия:

` x ` - связанная переменная в выражении .
` E ` - область видимости переменной ` x `.
Переменная свободна в ` E ` , если она не связана в ` E ` . Пример: ` lambda x. x (lambda y. x y z) ` . Cвободная переменная - ` z ` .

Взглянем на следующий пример: ` lambda x. x (lambda x. x) x ` .

Понимание лямбда-выражений существенно усложняется, когда переменные с разными значениями и контекстами используют идентичные имена. Поэтому впредь мы будем пользоваться следующим соглашением: связанные переменные необходимо переименовывать для того, чтобы они имели уникальные имена в выражении. Это возможно благодаря концептуально важному утверждению: выражения, которые могут быть получены друг из друга путем переименования связанных переменных, считаются идентичными. Важность этого утверждения в том, что функции в исчислении определяются лишь своим поведением, и имена функций не несут никакого смысла. То есть, функции ` lambda x. x ` , ` lambda y. y ` , ` lambda z. z ` на самом деле одна тождественная функция.

Вычисление лямбда-выражений

Вычисление выражений заключается в последовательном применении подстановок. Подстановкой ` E’ ` вместо ` x ` в ` E \ ` (запись: ` [E’//x]E ` ) называется выполнение двух шагов:

Альфа-преобразование. Переименование связанных переменных в ` E ` и ` E’ ` , чтобы имена стали уникальными.
Бета-редукция. По сути единственная значимая аксиома исчисления. Подразумевает замену ` x ` на ` E’ ` в ` E ` . Рассмотрим несколько примеров подстановок:

Преобразование к тождественной функции. ` (lambda f. f (lambda x. x)) (lambda x. x) -> ` (пишем подстановку) ` -> [lambda x. x // f] f ( lambda x. x)) = ` (делаем альфа-преобазование) ` = [(lambda x. x) // f] f (lambda y. y)) = ` (производим бета-редукцию) ` = (lambda x. x) (lambda y. y) -> ` (еще одна подстановка) ` -> [lambda y. y // x] x = lambda y. y `
Бесконечные вычисления. ` (lambda x. x x)(lambda x. x x) -> [lambda x. x x // x]x x = [lambda y. y y // x] x x = ` ` = (lambda y. y y)(lambda y. y y) -> … `
Также небольшой пример, почему нельзя пренебрегать альфа-преобразованием. Рассмотрим выражение ` (lambda x. lambda y. x) y ` . Если не выполнить первый шаг, результатом будет тождественная функция ` lambda y. y ` . Однако, после правильного выполнения подстановки с заменой ` y ` на ` z ` мы получим совсем другой результат ` lambda z. y ` , то есть константную функцию.

Функции нескольких переменных

Для того чтобы использовать функции нескольких переменных добавим в исчисление новую операцию ` add ` : она применяется к двум аргументам и является синтаксическим сахаром для следующих вычислений: ` (lambda x. lambda y. add \ x y) E_1 E_2 -> ([E_1 // x] lambda y. add \ x y) E_2 = ` ` (lambda y. add \ E_1 y) E_2 -> ` ` [E_2 // y] add \ E_1 y = add \ E_1 E_2 `

Как результат мы получили функцию от одного аргумента, которая возвращает еще одну функцию от одного аргумента. Такое преобразование называется каррирование (в честь Хаскелла Карри назвали и язык программирования, и эту операцию), а функция, возвращающая другую, называется функцией высшего порядка.

Порядок вычислений

Бывают ситуации, когда произвести вычисление можно несколькими способами. Например, в выражении ` (lambda y. (lambda x. x) y) E ` сначала можно подставлять ` y ` вместо ` x ` во внутреннее выражение, либо ` E ` вместо ` y ` во внешнее. Теорема Черча-Рассера говорит о том, что в не зависимости от последовательности операций, если вычисление завершится, результат будет одинаков. Тем не менее, эти два подхода принципиально отличаются. Рассмотрим их подробнее:

Вызов по имени. В вычислении всегда в первую очередь применяются самые внешние подстановки. Другими словами, нужно вычислять аргумент уже после подстановки в функцию. Кроме того нельзя использовать редукцию внутри абстракции. Пример: ` (lambda y. (lambda x. x) y) ((lambda u. u) (lambda v. v)) -> ` (применяем редукцию к внешней функции) ` -> (lambda x. x) ((lambda u. u) (lambda v. v)) -> ` (вновь подставляем, не меняя аргумент) ` -> (lambda u. u) (lambda v. v) = lambda v. v `
Вызов по значению. В этом способе вычисление проходит ровно наоборот, то есть сначала вычисляется аргумент функции. При этом редукция внутри абстракции также не применяется. Пример: ` (lambda y. (lambda x. x) y) ((lambda u. u) (lambda v. v)) -> ` (вычисляем аргумент функции) ` -> (lambda y. (lambda x. x) y) (lambda v. v) -> (lambda x. x) (lambda v. v) -> lambda v. v `

Из практических отличий этих двух подходов отметим, то что вычисление по значению более сложно в реализации и редко используется для всех вычислений в неисследовательских языках. Однако, второй подход может не привести к завершению вычисления. Пример: ` (lambda x. lambda z.z) ((lambda y. y y) (lambda u. u u)) ` . При вычислении аргумента мы попадаем в бесконечный цикл, в то время как, проводя вычисления по имени функции, мы сразу получим тождественную функцию.

Кодирование типов

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

Булевые значения. Поведение типа можно описать как функцию, выбирающую одно из двух. Тогда значения выглядят так: ` true = lambda x. lambda y. x ` и ` false = lambda x. lambda y. y `
Натуральные числа. Каждое натуральное число может быть описано как функция, проитерированная заданное число раз. Выпишем несколько первых чисел ( ` f ` - функция, которую итерируем, а ` s ` - начальное значение):
- ` 0 = lambda f. lambda s. s `
- ` 1 = lambda f. lambda s. f s `
- ` 2 = lambda f. lambda s. f (f s) `
Операции с натуральными числами.
- Следующее число. ` \s\u\c\c \ n = lambda f. lambda s. f (n f s) ` . Аргумент функции - число ` n ` , которое, будучи так же функцией, принимает еще два аргумента: начальное значение и итерируемую функцию. Для числа ` n ` один раз применяем функцию ` f ` и получаем следующее число.
- Сложение. ` add \ n_1 n_2 = n_1 \ \s\u\c\c \ n_2 ` . Для сложения чисел ` n_1 ` и ` n_2 ` нужно одному из слагаемых передать в параметры функцию ` \s\u\c\c `, как итерруемую функцию, и другое слагаемое, как начальное значение. В результате мы увеличим заданное число на единицу необходимое число раз.
- Умножение. ` \m\u\l\t \ n_1 n_2 = n_1 (add \ n_2) 0 ` . В роли итерируемой функции для множителя ` n_1 ` выступает функция ` \s\u\c\c ` с аргументом ` n_2 ` , а в роли начального значения уже определенное число ` 0 ` . То есть мы определяем умножение как прибавление ` n_2 ` к нулю ` n_1` раз.

Аналогично, с помощью лямбда-исчисления можно выразить любые конструкции языков программирования, такие как циклы, ветвления, списки и тд.

Заключение

Лямбда-исчисление - очень мощная система, которая позволяет писать любые программы. Однако, непосредственно программирование на лямбда-исчислении получается черезчур громоздким и неудобным. Тем не менее, чистое лямбда-исчисление предназначено вовсе не для программирования на нем, а для изучения существующих и создания новых языков программирования. А следующим шагом на пути к типовым функциональным языкам является типизированное лямбда-исчисление - расширение чистого исчисления типовыми метками.

Читайте также: