Редактирование: Парадигмы программирования, 06 лекция (от 29 октября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
[[Image:paradigm_091029_01.jpg|thumb|right|300px|«На эту тему мне понравилась [http://theartoftattoo.files.wordpress.com/2009/04/y-combinator.jpg татуировка с Y-combinator»]]] | [[Image:paradigm_091029_01.jpg|thumb|right|300px|«На эту тему мне понравилась [http://theartoftattoo.files.wordpress.com/2009/04/y-combinator.jpg татуировка с Y-combinator»]]] | ||
- | * '''Аудиозапись:''' http://esyr.org/lections/audio/paradigms_2009_winter/paradigms_09_10_29.ogg | ||
= лямбда-исчисления = | = лямбда-исчисления = | ||
Строка 147: | Строка 146: | ||
(λ x . λ y . y) ((λ z . z z) (λ z . z. z)) | (λ x . λ y . y) ((λ z . z z) (λ z . z. z)) | ||
- | Вопрос, какой же редекс тогда надо выбирать и зачем? Введём | + | Вопрос, какой же редекс тогда надо выбирать и зачем? Введём неск. определений. |
* Самый левый редекс --- его лямбда или имя примитивной функции находятся текстуально левее всех остальных. | * Самый левый редекс --- его лямбда или имя примитивной функции находятся текстуально левее всех остальных. | ||
* Самый внешний редекс --- тот, который текстуально не содержится ни в каком другом. | * Самый внешний редекс --- тот, который текстуально не содержится ни в каком другом. | ||
- | * Самый внутренний --- тот, в котором не | + | * Самый внутренний --- тот, в котором не содерж. никакой другой. |
Есть два порядка? | Есть два порядка? | ||
Строка 158: | Строка 157: | ||
Здесь мы сначала применили сначала нормальный, потом аппликативный. Теперь можно уточнить: | Здесь мы сначала применили сначала нормальный, потом аппликативный. Теперь можно уточнить: | ||
- | Следствие из теор. Чёрча-Россера. нормальный порядок редукции приводит к | + | Следствие из теор. Чёрча-Россера. нормальный порядок редукции приводит к норм. форме за конеч. число шагов, если она вообще есть. |
- | форме за | + | |
- | Теперь самое интересное. Если отвлечься от л- | + | Теперь самое интересное. Если отвлечься от л-выр. и вернуться к прогр., то можно вспомнить, что есть энергинча и ленивая стратегия вычисл. При энерг. мы выч. всё, что только можем. При ленивых выч. мы при виде выр. мы запоминаем его и не вычисляем, пока можно, до тех пор, пока не припрёт. Например: |
( ) > 3 | ( ) > 3 | ||
- | Вот тут нам | + | Вот тут нам надо вычислить знач. выр., не раньше. Бывает ли такое в языках прогр.? Бывает, но очень редко и по-немногу. Ленивая семантика из компилир. языков --- только хаскель, но все привычные, императивные --- энергичные. |
- | Где можно встретить ленивую модель вычислений? Например, при | + | Где можно встретить ленивую модель вычислений? Например, при подст. макросов. Макропроцессору это просто, поск. он работает на уровне текстовых строк. В некоторых командно-скриптовых языках ленивая семантика имеется. |
Но сейчас, когда мы смотрим на л-выч., мы видим, что ленивый порядок вычисл. оказался в каком-то виде мощнее. | Но сейчас, когда мы смотрим на л-выч., мы видим, что ленивый порядок вычисл. оказался в каком-то виде мощнее. | ||
- | Введём такую | + | Введём такую вещб, как понятие связанных и свободных переменных |
λ x . x y | λ x . x y | ||
- | Понятно, что x | + | Понятно, что x связ., а y --- вободная. Если чуть строже, то построим мн-во FV(E) (free variables(expression)). Как оно вводится: |
* FV(x) = {x} | * FV(x) = {x} | ||
* FV(c) = ∅ | * FV(c) = ∅ | ||
Строка 193: | Строка 191: | ||
(λ x . E x) a →<sub>β</sub> E a | (λ x . E x) a →<sub>β</sub> E a | ||
- | Главное, чтобы в E не было свободной переменной x, иначе ничего не выйдет. | + | Главное, чтобы в E не было свободной переменной x, иначе ничего не выйдет. Соотв, делаем это преобр.: |
E →<sub>η</sub> λ x. E x | E →<sub>η</sub> λ x. E x | ||
- | Что оно | + | Что оно позв. делать? Например, част. применение встроенных функций. Например, если есть * x y. Является ли * 3 л-выр? Да. А как же с ним работать. Применим η-преобр, получим λ x . * 3 x. Благодаря этому мы можем делать частичное применение функций. |
- | ... это называется карринг, по имени учёного Карри | + | ... это называется карринг, по имени учёного Карри (Curry). |
Наконец, последнее на сегодня, что же такое Y-combinator. Хочется нам, к примеру, сделать рек. функцию, но как, здесь же нет имён? Мы эту фнкцию получим в кач. второго аргумента. То есть функция получает на фход аргмент и самого себя, и исхитримся и подадим её на вход. | Наконец, последнее на сегодня, что же такое Y-combinator. Хочется нам, к примеру, сделать рек. функцию, но как, здесь же нет имён? Мы эту фнкцию получим в кач. второго аргумента. То есть функция получает на фход аргмент и самого себя, и исхитримся и подадим её на вход. |