LINUX.ORG.RU

Лямбды в LC и языках программирования.

 , ,


3

3

Я не знаток LC, но немного знаком, и возник вопрос: а существуют ли безымянные функции в LC? Ведь, по факту, в LC, каждая функция, четко связана со своим аргументом, через который она передается, а значит, абсолютно каждая функция в LC, имеет свое имя. Однако, безымянные ф-ции, в ЯП, обычно выдаются за фичу LC. Фактически, есть даже устоявшееся значения слова «лямбда», в смысле, «безымянная ф-ция».

Насколько я понимаю, выражение, подобное этому, например:

(define foo ((lambda(x) (lambda(y) (x y)))) (lambda(x) x))
не является выражением с безымянными функциями, поскольку выражение переданное в качестве аргумента, связывается с именем x, а возвращаемая ф-ция, которую принято называть в программировании безымянной, связывается с именем foo. при дальнейшей редукции, когда foo получит свой аргумент, он тоже будет связан с именем y. Таким образом, никаких безымянных ф-ций не существует, так откуда же появилось это слово? Это ошибка?

Я так делал:

(function (lambda (&REST childs) ,(cadr (assoc node *commands* :test 'string=))))

Тут не только имени нет, но и тела (вытаскивается из списка по ключу).

ziemin ★★ ()

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

А если она никуда не передаётся?

anonymous ()

А вообще, ты пытаешься приплести терминологию языков программирования к LC, которой там отродясь небыло. Например, то что ты тут называешь «связыванием»:

каждая функция, четко связана со своим аргументом, через который она передается

в LC вообще отсутствует (понятие связывания там вообще-то тоже есть, но оно озночает нечто другое).

anonymous ()
Ответ на: комментарий от ziemin

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

anonimous ()
Ответ на: комментарий от anonymous

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

Там есть, подстановка, она эквивалентна связыванию, в ЯП.

нечто другое

семантически - то же самое.

anonimous ()
Ответ на: комментарий от anonymous

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

anonimous ()
Ответ на: комментарий от anonimous

Можно считать что это глобал, или аутпут, это сути не меняет.

Тот же вопрос относительно (λx.x), никаких глобалов: (λz.z) ((λx.x) (λy.y))

anonymous ()
Ответ на: комментарий от anonimous

семантически - то же самое.

Но вопрос не о семантике, вопрос о терминологии. Попросту говоря, что ты вооще подразумеваешь под «именем»?

anonymous ()
Ответ на: комментарий от anonymous

что ты вооще подразумеваешь под «именем»

В данном случае, ассоциация символа аргументного места с функцией, это имя, по сути.

anonimous ()
Ответ на: комментарий от anonimous

Здесь все то же самое, все функции кроме одной, имеют имена по соответствующим аргументам

Я вижу как минимум 2 функции без имён: (λz.z) и (λx.x)

anonymous ()
Ответ на: комментарий от anonimous

Oк, в таком случае ранее приведённый пример (λz.z) ((λx.x) (λy.y)) тебе демонстрирует 2 функции, которые ни с чем не «связываются».

anonymous ()
Ответ на: комментарий от anonymous

функции без имён: (λz.z) и (λx.x)

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

anonimous ()
Ответ на: комментарий от anonimous

все функции, которые первыми принимают аргументы не имеют имени

Не только, можно привести и другие примеры (тут ни одна из 3 фцнкций не имеет имени): (λx. (λy. (λz. z)))

anonymous ()
Ответ на: комментарий от anonymous

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

(let ((x (lambda(y) y))) x)

anonimous ()
Ответ на: комментарий от anonymous

тут ни одна из 3 фцнкций не имеет имени

Тут подразумевается, что они будут: каждая переменная тут ожидает функцию, это имена ф-ций, которые «придут» в будущем.

anonimous ()

Идиот. Больной.

Почитай Барендрегта, что ли.

anonymous ()

ЗЫ: можно сделать лямбда-исчисление вообще без именованных аргументов. Достаточно определить два комбинатора - S и K.

anonymous ()
Ответ на: комментарий от ilammy

Безымянные, потому что у них нет собственного имени.

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

anonimous ()
Ответ на: комментарий от anonymous

Достаточно определить два комбинатора - S и K.

ЕМНИП, даже одного достатаочно, но это уже другая история.

anonimous ()
Ответ на: комментарий от ilammy

Возьмем хоть вот этот пример: (λx. (λy. (λz. z)))

Здесь ожидаются значения имен x y z. Имена уже есть, не хватает только значений. ККак только появятся значения, пойдет пр-сс вычисления - подстановки и редукции.

anonimous ()
Ответ на: комментарий от anonimous

Ещё раз: у функций нет имён. Имена есть у переменных. Поэтому функции сами по себе «безымянные». От того, что функция связывается с переменной, своего имени она не получает. К вычислениям, редукциям и прочему это не имеет никакого отношения. Лямбда-терм — это лямбда-терм. Он существует независимо от того, хочет ли анонимус его вычислить редуцировать или нет.

ilammy ★★★ ()
Последнее исправление: ilammy (всего исправлений: 3)
Ответ на: комментарий от ilammy

Имена есть у переменных

Еще раз:) переменные — это семантически, по-сути, и есть имена ф-ций.

От того, что функция связывается с переменной, своего имени она не получает

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

anonimous ()
Ответ на: комментарий от anonimous

Безымянные функции (полноценные значения) противопоставляются именованным функциям (сущностям, которые идентифицируются только по собственному имени).

В лямбда-исчислении функции — это значения. У них нет собственных имён. Точно так же, как нет своего имени у числа 3.

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

ilammy ★★★ ()

Угадал автора по заголовку (с)

anonymous ()
Ответ на: комментарий от ilammy

Возьмем такой пример (define a 'b) и (lambda() 'b). Пока ф-ция «висит в возухе» - она не значит ничего это равноценно тому, что ее вообще не существует. Мы должны как то ее вызвать, она должна иметь свой адрес, о котором знает хотя бы один программный объект. А когда мы пишем ((lambda(a) (a 'b)) (lambda(x) x)) - мы получаем те же яйца, только сбоку, через жопу лишнюю прослойку, мы получили доступ к 'b через a. Но мы могли бы это сделать и напрямую: ((lambda(a) 'b) 'c).

anonimous ()
Ответ на: комментарий от anonimous

Но мы могли бы это сделать и напрямую: ((lambda(a) 'b) 'c).

Точнее даже вот так: ((lambda(a) a) 'b) - вот этот пример вообще на 100% эквивалентен связыванию.

//fixed

anonimous ()
Ответ на: комментарий от anonimous

Возьмем такой пример (define a 'b) и (lambda() 'b)
как то ее вызвать
должна иметь свой адрес
программный объект
символ '3

Мы всё ещё говорим о лямбда-исчислении? А то в настоящих компьютерах и функций-то нет.

Или просто очередной идиотский терминологический спор? «Почему яблоки называются яблоками? Это ошибка предков? Возьмём пример с грушами, ведь получается не хуже!»

ilammy ★★★ ()
Последнее исправление: ilammy (всего исправлений: 1)
Ответ на: комментарий от ilammy

Мы всё ещё говорим о лямбда-исчислении?

Да, тут под 'b и 'c понимается любая ф-ция, произвольная, просто для краткости, что бы глаза не мозолить. Подставьте туда любую ф-цию, вместо символов, это в данном случае не имеет значения.

anonimous ()
Ответ на: комментарий от ilammy

Я говорю о том, в данном случае, что семантика LC вообще не отличается от семантики любого ЯП, и выразима даже через присваивания. И присваивания можно выразить на LC. А те переменные в функциях, которые не сопоставлены именам - это просто задержанные вычисления. Как только имена получат значения, они будут редуцированы. Т.е. Для того, чтобы вычисления происходили, имена необходимы, и они там есть, просто называются по другому, но суть от этого не меняется. Семантика LC эквивалентна той же МТ, например. Это просто императивный код, но чрезжопный, с синтаксическими извращениями. Откуда взялось мнение, что есть какой-то ФП, я хз.

anonimous ()
Ответ на: комментарий от ilammy

функций-то нет

Их вообще нет, только в головах математиков. То что принято называть умным словом ф-ция, это всего-лишь шаблон для подстановок. Если в шелле мы пишем a=b, затем вызываем «функцию» a, которая возвращает b: $a-->b, то в других ЯП мы пишем умные конструкции a=function(){return b}, и получаем то же самое, только like a sir.

anonimous ()
Ответ на: комментарий от anonimous

Пока ф-ция «висит в возухе» - она не значит ничего это равноценно тому, что ее вообще не существует.

В LC именно это и не выполняется.

userid2 ()
Ответ на: комментарий от userid2

Что не выполнется? Смысл функции, самой по себе в любом случае равен 0. В LC, ф-ция становиться аргументом другой функции, либо получает в качестве аргумента другую ф-цию только тогда мы получаем какой то результат. Абстракция и аппликация, другими словами. Если есть только абстракция, как в случае с «висящей» ф-цией, толку ноль. Смысл абстракции в том, что когда то она будет применена. Абстракция задает правила преобразований, но на одних правилах, без их применения далеко не уедешь.

anonimous ()
Ответ на: комментарий от anonimous

Смысл функции, самой по себе в любом случае равен 0.

Тогда и во всем ЛИ толку ноль, ведь применение термов на выходе дает еще один терм, в котором, по твоим словам, смысла нет.

jerk-of-all-trades ()
Ответ на: комментарий от jerk-of-all-trades

в котором, по твоим словам, смысла нет

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

anonimous ()

А если

(define foo
   (list (lambda (x) (+ 1 x))
         (lambda (y) (+ 2 y))
         (lambda (z) (+ z z))))

, то какие имена у функций?

На всех одно имя foo? Или (list-ref foo 0), (list-ref foo 1), (list-ref foo 3)?

monk ★★★★★ ()
Ответ на: комментарий от monk

Я на это вот что скажу. В scheme довольно путанный синтаксис. По идее, выражение (list x) соответствует (lambda x x), а list - это уже имя. Если расахарить, получится вот это:

(define foo
  ((lambda x x)
   (lambda(x) x)
   (lambda(y) y)
   (lambda(z) z)))
Тут опять проблема. LC не позволяет забирать несколько аргументов зараз, а у нас именно это здесь и происходит, поскольку (lambda x x) - это все равно, что
((lambda(l1 l2 l3) l1 l2 l3)l1 l2 l3)
Это нужно преоблазовать в
(define foo ((((lambda(x) (lambda(y) (lambda(z) [[ fuckin' x y z ]])))l1)l2)l3))

причем, что будет значить это [[ fuckin' x y z]], с точки зрения забубенной модели scheme я хз, но имена есть, да, все можно отследить, если убрать сахар и lisp-специфичные закидоны.

anonimous ()
Ответ на: комментарий от monk

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

(write ((lambda(x) (x 1)) (car foo)))  ; 2
Во время вычисления, ф-ция получает таки имя свое.

He is forty-eight years old, and he was part of Project Mayhem. Only in death will we have our own names since only in death are we no longer part of the effort. In death we become heroes.:)

anonimous ()
Ответ на: комментарий от buddhist

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

anonimous ()
Ответ на: комментарий от buddhist

Даже просто абстрагироваться от имен мы не можем. Мы могли бы предположить, что, типа, если у нас все ф-ции с одним аргументом, то зачем нам вообще имена — но ясно, что имена тут еще участвуют в разруливании порядка вычислений: (lambda(x) (lambda(y) (y x))). Нет тут никакой возможности абстрагироваться от имен.

anonimous ()
Ответ на: комментарий от buddhist

Опять же, можно подойти и с другой точки зрения: есть синтаксис, есть правила подстановки. Нам говорят, что этого достаточно? Позвольте, а кто будет подстановки производить по этим правилам? Что, по-твоему, лямбда-термы сами себя будут редуцировать? Нужен транслятор, мля, для этого, и вот транслятор, как раз, «знает эти правила», сами записи термов - программа, в рыло не е*т, что делать с собой. А Транслятору нужны имена для подстановок, поэтому-то, они там и есть.

anonimous ()
Ответ на: комментарий от anonimous

Ну и какие такие имена в редукторе графов? Нет там уже никаких имен.

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

anonymous ()

Запутался в буквах?

Читай TaPL.

Можно убрать буквы и использовать цифры. Первая по счету лямбда связана с 1, вторая с 2 и т.д.

\.((\.1 2) (\. 1))

И какое «имя» у \. 1 ?

Kuzy ★★★ ()
Ответ на: комментарий от Kuzy

И какое «имя» у \. 1 ?

Для ясности, я заменил 1 на 3

\.((\.1 2) (\. 3))
В этом коде, \.3 имеет имя 1.

anonimous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.