lambda x.x x - ?

[Sonic86]

$\lambda x.x \ x$ - это что?
Это можно выразить в терминах "аргумент", функция, композиция и т.п.?
Я могу понять выражение $\lambda x. f \ f \ x$ - это вроде как функция $f\circ f$ (правильно?)
Я видел, что бывают функции (функционалы?), которые можно вычислять от самих себя: например, если $g(f) = f\circ f \circ f$, то $g(g)=g^{(9)}$ - $9$-ирная композиция $g$, потому что такое $x\ x$ понять можно.
Но блин! $\lambda f. f \ x$ - это что тоже? Это не функция? $f(2)$ например, если $f$ - переменная, - это не константа, но и не функция в обычном смысле.
Т.е. отождествим функцию с ее графиком. Если $x$ - переменная, $f$ константа, то $f \ x$ - это график функции. Наоборот, если $x$ - константа, $f$ - переменная, то $f \ x$ - это какой-то график переменной а че это такое вообще?!
А $\lambda f.f \ f$ - это когда график графика как переменной, да еще и как функция...

Кто-нибудь что-нибудь понимает?

-- Пн сен 26, 2016 19:02:58 --

А что такое $\lambda x_1 \ ... \ x_n . A$? Это $\lambda x_1. \ ... \ \lambda x_n. \ A$?

[nnetwork]

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

[Sonic86]

nnetwork в сообщении #1154934 писал(а):

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

Это мне все понятно.
Мне непонятно, как это на обычный язык переводится.

[Munin]

А как переводится на обычный язык $\lambda fx.f\,x,$ вам понятно?

[arseniiv]

Sonic86 в сообщении #1154931 писал(а):

А что такое $\lambda x_1 \ ... \ x_n . A$? Это $\lambda x_1. \ ... \ \lambda x_n. \ A$?

Да.

Sonic86 в сообщении #1154937 писал(а):

Мне непонятно, как это на обычный язык переводится.

Не всегда переводится. Например, в ZFC (обычной с аксиомой регулярности) нет такой функции, которая была бы применима к себе.

У λ-исчисления существуют интерпретации, но я в них не селен. Можете посмотреть монографию Барендрегта Ламбда-исчисление. Его синтаксис и семантика, там есть о них.

Кстати, тема точно должна быть где сейчас есть?

-- Вт сен 27, 2016 01:17:10 --

arseniiv в сообщении #1154970 писал(а):

Не всегда переводится.

Правда, тут я ответил не совсем то.

Sonic86 в сообщении #1154931 писал(а):

Наоборот, если $x$ - константа, $f$ - переменная, то $f \ x$ - это какой-то график переменной

Да не, это обычный график функции, но функции $f\mapsto f\ x$. В рамках элементарной математики можно было бы рассмотреть функцию из, скажем, множества аффинных функций $A=\{x\mapsto ax+b\colon K\to K \mid a,b\in K\}$ над каким-то полем, в само $K$, типа уже упомянутой вами $f\mapsto f(2)$. График будет вполне нормальный, если не забыть, что $A$ двумерное линейное пространство над $K$. Другие функционалы, наверное, тоже встречали.

-- Вт сен 27, 2016 01:24:15 --

Sonic86 в сообщении #1154931 писал(а):

А $\lambda f.f \ f$ - это когда график графика как переменной, да еще и как функция...

А вот это уже хитрее, потому что нельзя получить это заменой из $\lambda f.fx$ или $\lambda x.fx$. Тут уж стоит отключиться от внешнего мира и начать воспринимать λ-исчисление как модель вычислений, и смотреть на термы в контексте формул, в которых они встречаются, а не поодиночке. Ну или рассмотреть те интерпретации в книге, но вряд ли они прояснят дело здесь и сейчас.

[Munin]

Sonic86 в сообщении #1154931 писал(а):

Т.е. отождествим функцию с ее графиком.

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

И вообще. Лучше всего начать с чтения описания Unlambda. Потом вернуться к обычному лямбда-исчислению будет большим облегчением  и вставкой мозгов опять в черепушку .

[nnetwork]

Munin в сообщении #1155010 писал(а):

Лучше всего начать с чтения описания Unlambda

Уж лучше тогда к первоисточнику -- комбинаторной логике Шейнфинкеля, у которого, к слову, Карри скромно и не в меру молчаливо позаимствовал идею о так называемом "каррировании"

[arseniiv]

(Оффтоп)

nnetwork в сообщении #1155015 писал(а):

у которого, к слову, Карри скромно и не в меру молчаливо позаимствовал идею о так называемом "каррировании"

Не сам же он в честь себя его назвал. То, что имена часто даются не совсем исторически в том числе и в математике, далеко не новость.

[nnetwork]

arseniiv

(Оффтоп)

Ему никто не запрещал проявить инициативу и исправить данное "недоразумение". По всей видимости, его все устраивало

[arseniiv]

(Оффтоп)

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

(Оввтоб)

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

[Sonic86]

Munin в сообщении #1154967 писал(а):

А как переводится на обычный язык $\lambda fx.f\,x,$ вам понятно?

Нет

Munin в сообщении #1155010 писал(а):

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

И вообще. Лучше всего начать с чтения описания Unlambda
. Потом вернуться к обычному лямбда-исчислению будет большим облегчением и вставкой мозгов опять в черепушку .

Спасибо, попробую вечером. Я только начал и шаблон оно мне рвет сильно.

arseniiv в сообщении #1154970 писал(а):

Не всегда переводится. Например, в ZFC (обычной с аксиомой регулярности) нет такой функции, которая была бы применима к себе.

А как же функционал, который делает композицию $f$ 3 раза? Это какая-то ненормальная функция?

arseniiv в сообщении #1154970 писал(а):

У λ-исчисления существуют интерпретации, но я в них не селен. Можете посмотреть монографию Барендрегта Ламбда-исчисление. Его синтаксис и семантика, там есть о них.

Я пробовал и сразу умер на 2-й странице. Пока Харрисона читаю. Еще Пирс на будущее.

(Оффтоп)

arseniiv в сообщении #1154970 писал(а):

но я в них не селен

плюмбум?

arseniiv в сообщении #1154970 писал(а):

Кстати, тема точно должна быть где сейчас есть?

Я предполагаю, что мой вопрос очень глупый или бессмысленный. Потому сделал тему здесь.

arseniiv в сообщении #1154970 писал(а):

Да не, это обычный график функции, но функции $f\mapsto f\ x$. В рамках элементарной математики можно было бы рассмотреть функцию из, скажем, множества аффинных функций $A=\{x\mapsto ax+b\colon K\to K \mid a,b\in K\}$ над каким-то полем, в само $K$, типа уже упомянутой вами $f\mapsto f(2)$. График будет вполне нормальный, если не забыть, что $A$ двумерное линейное пространство над $K$. Другие функционалы, наверное, тоже встречали.

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

arseniiv в сообщении #1154970 писал(а):

А вот это уже хитрее, потому что нельзя получить это заменой из $\lambda f.fx$ или $\lambda x.fx$. Тут уж стоит отключиться от внешнего мира и начать воспринимать λ-исчисление как модель вычислений, и смотреть на термы в контексте формул, в которых они встречаются, а не поодиночке. Ну или рассмотреть те интерпретации в книге, но вряд ли они прояснят дело здесь и сейчас.

Ааа, понятно. Значит не все так просто...
Спасибо.

[Munin]

Sonic86 в сообщении #1155095 писал(а):

Munin в сообщении #1154967 писал(а):

А как переводится на обычный язык $\lambda fx.f\,x,$ вам понятно?

Нет :-(

Давайте на этом сосредоточимся. Это значит "взять функцию и аргумент, и применить одно к другому".

Разумеется, обозначения здесь специально подобраны "говорящие". Это то же самое, что и $\lambda xy.x\,y,$ или $\lambda fg.f\,g.$

[arseniiv]

Sonic86 в сообщении #1155095 писал(а):

А как же функционал, который делает композицию $f$ 3 раза? Это какая-то ненормальная функция?

Ну, какую-то функцию в ZFC с таким свойством можно будет указать, и не одну, но её явно нельзя будет применить к себе.

Sonic86 в сообщении #1155095 писал(а):

Я предполагаю, что мой вопрос очень глупый или бессмысленный.

На самом деле не очень и бессмысленный. Подобные трудности с λ-исчислением могут быть ещё у кого-нибудь.

Я вас ещё обрадую, в теориях типов на применение $fa$ накладывается очевидное ограничение $f\colon t\to u,a\colon t$, так что там не будет многих из таких смущающих термов. Одна из самых простых, так и зовущаяся «просто типизированное (simply typed) λ-исчисление» у Барендрегта, кажется, где-то есть.

[Sonic86]

Munin в сообщении #1155110 писал(а):

Sonic86 в сообщении #1155095 писал(а):

Munin в сообщении #1154967 писал(а):

А как переводится на обычный язык $\lambda fx.f\,x,$ вам понятно?

Нет

Давайте на этом сосредоточимся. Это значит "взять функцию и аргумент, и применить одно к другому".

Разумеется, обозначения здесь специально подобраны "говорящие". Это то же самое, что и $\lambda xy.x\,y,$ или $\lambda fg.f\,g.$

Тут понятно: 1-е - это что-то типа $\mathrm{Apply}$ - берет функцию и аргумент и применяет одно к другому. Правда странно, но 2-й терм, $\alpha$-равносильный первому вызывает вообще другие ассоциации - композиция функций.
Соответственно - мой вопрос - это функция, которая применяется сама к себе, причем она переменная. Что-то такое.

arseniiv в сообщении #1155127 писал(а):

Ну, какую-то функцию в ZFC с таким свойством можно будет указать, и не одну, но её явно нельзя будет применить к себе.

А как же:

Sonic86 в сообщении #1154931 писал(а):

бывают функции (функционалы?), которые можно вычислять от самих себя: например, если $g(f) = f\circ f \circ f$, то $g(g)=g^{(9)}$ - $9$-ирная композиция $g$

arseniiv в сообщении #1155127 писал(а):

Я вас ещё обрадую, в теориях типов на применение $fa$ накладывается очевидное ограничение $f\colon t\to u,a\colon t$, так что там не будет многих из таких смущающих термов. Одна из самых простых, так и зовущаяся «просто типизированное (simply typed) λ-исчисление» у Барендрегта, кажется, где-то есть.

Спасибо, действительно обрадовали

[Karan]

Тема перемещена из форума «Тестирование» в форум «Помогите решить / разобраться (М)»