Пару недель, но я не очень торопился и занимался им от случяя к случяю. За это время сделал нужную прогу на лисп строк на 200, походу изучяя ево.

пару часов .. лисп самый простой язык

Да ладно брехать-то.

Прямо-таки за 2 часа может научился приличные алгоритмы составлять или может быть все спец функции хотябы _просмотрел_ что делают и как?

эээ приличные алгоритмы составлять я научился до изучения лиспа .. спец функции? эээ а что это?

лисп это atom, car, cdr, cons, quote, lambda, cond, eval, apply, nil и t - остальное все производное

А я вообще выучил 2 функции - S и K. Всё остальное - их производные. :)

Всё-таки по сравнению с теми же с, у алгоритмов на лиспе есть своя специфика. В прожке, про которую я говорил ранее, потом переделал несколько функций с dolist на рекурсию, получилось гораздо проще и компактнее. А на с такое бы не прокатило бы без компилятора стандарта ISO C/99, который непонятно где взять.

Как-то наткнулся на Practical Common Lisp (http://www.gigamonkeys.com/book/), почитал и понял: лисп можно любить, можно не любить, но знать надо. :) Основные вещи усвоил где-то за пару дней или недель, а вот мега-гуру до сих пор не стал. =)

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

плохо выучил .. S и K не базисны и к томуже не функции ;)

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

И как раз S и K составляют минимальный базис.

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

хехе, хорошо согласен с тобой что слово функция широкоприменительная

> И как раз S и K составляют минимальный базис.

ну выведи мне из них комбинатор тождества

> хехе, хорошо согласен с тобой что слово функция широкоприменительная

Определение абсолютно строгое.

> ну выведи мне из них комбинатор тождества

(I x) = ((S K K) x)

> (I x) = ((S K K) x)

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

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

http://en.wikipedia.org/wiki/Combinatory_logic#Completeness_of_the_S-K_basis

Не нужен комбинатор тождества. Совсем.

> Не нужен комбинатор тождества. Совсем.

эээ если бы комбинатора тождества не было(не существовало) то не было бы неподвижной точки - а тем самым не было бы вообще ничего, не было б рекурсии, не былоб функционального программирования .. явно или неявно тождство входит в каждый базис комбинаторной логики .. если бы K S было бы базисом то как доказать что существует комбинатор тождества? то что I = SKK вовсе не значит что I существует

базисность S и K возможна лишь при условии СУЩЕСТВОВАНИЯ I, простейший способ удовлетворить это условие это определить I и включить его в базис ..

> то не было бы неподвижной точки

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

Для каждого терма F

X=WW, где W=\x -> F(x x) -- неподвижная точка, при чем тут кобинатор тождества?

> то что I = SKK вовсе не значит что I существует

хуяся. Мы можем обозвать выражение SKK как угодно. Надо лишь показать, что SKK x = x, где x -- произвольный терм. Не понимаю твоих мыслей в упор.

Вот комбинатор неподвижной точки, выраженный через S и K. Что тебе еще надо?

Y = S S K (S (K (S S (S (S S K)))) K)

> X=WW, где W=\x -> F(x x) -- неподвижная точка, при чем тут кобинатор тождества?

при том что при условии отсутствия(не доказаности) существования I, ты не сможешь создать НИ ОДНОГО БАЗИСА, ни K S и никакой другой

> хуяся. Мы можем обозвать выражение SKK как угодно. Надо лишь показать, что SKK x = x, где x -- произвольный терм. Не понимаю твоих мыслей в упор.

так, повторяем школьный курс .. SKK x = x - всегда выполнено! НО из этого равенства НЕ СЛЕДУЕТ I = SKK, I = SKK из SSK x = x следует в том и только в том случае когда известно что I СУЩЕСТВУЕТ .. под I здесь везде имеется ввиду комбинатор тождества

всё ты меня утомил, лучше возьми какую нибудь книжку толковую .. я посоветую книжки Вольфенгагена

> Y = S S K (S (K (S S (S (S S K)))) K)

ээ путаем что то? .. полный вывод пожалуйста без использования факта существования I

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

> так, повторяем школьный курс .. SKK x = x - всегда выполнено! НО из этого равенства НЕ СЛЕДУЕТ I = SKK, I = SKK из SSK x = x следует в том и только в том случае когда известно что I СУЩЕСТВУЕТ .. под I здесь везде имеется ввиду комбинатор тождества

Хорошо, какие свойства I тебе нужны еще, кроме того, что I x = x, для любого x?

лишь факт его существования всего навсего :)

> ээ путаем что то? .. полный вывод пожалуйста без использования факта существования I

Возьми и проверь, что F(YF) = YF. Думаешь, тебе кто-то будет сюда доказательство набивать?

> лишь факт его существования всего навсего :)

А как доказываются теоремы существования в математике? Просто приводится пример объекта, который обладает всеми нужными свойствами. SKK обладает всеми требуемыми свойствами комбинатора тождества, поэтому его и можно считать комбинатором тождества. ТО есть, по определению положить I=SKK

понимаешь тут есть небольшая разница .. эквивалентность комбинаторов и равенство комбинаторов суть разные штуки, из вывода SKK x = x и определения I как I x = x следует лишь эквивалентность SKK и I .. равенства ты сможешь достичь лишь применив комбинатор I, а применить ты его можешь только при условии его существования

Ответ в удаленных.

Я не понимаю о каких S и K вы тут спорете, но вот мимо таких заявлений не пройду!

Допустим у нас есть аксиомы Пеано. По вашей логике, имея определения 0, 1 и inc мы всё равно не можем сказать что такое 2, 3 и 4, потому что не ввели их в базис? Я верно понимаю?

>пару часов .. лисп самый простой язык

+1

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

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

хехе, нет я утверждаю что имея 1, -1 и + - ошибочно утверждать что существует 0 такой что 1+0=1, хотя и очевидно что 1+(1+(-1))=1

> lg, я тебя очень уважаю, но тут ты не прав. Я ж писал, положим по определению I = SKK. Дальше можно считать, что у нас есть 3 базисных комбинатора I, S, K. И строй дальше всю свою комбинаторную логику, все доказательства останутся такими же, какими они были бы если мы ввели I аксиоматически.

нет, ну пойми же .. все твои выводы комбинаторов не верны по существу ибо ты никогда не сможешь перевести эквивалентное равенство в комбинаторное(структурное/выводное/семантическое/задаваемое уж не знаю как донести) равенство без комбинатора тождества

кстати сказать, заметь что ОСНОВНАЯ аксиома арифметики это аксиома существования нуля :) - иначе то индукции по Пеано не плучается хехе .. назови ты его один, два, или три смысл от этого не поменяться - должна быть база .. то же самое и в комбинаторной логикиге, база это переход от эквивалентности к равенству - иначе вся логика рушится

> кстати сказать, заметь что ОСНОВНАЯ аксиома арифметики это аксиома существования нуля

Ну да, а у нас основа -- это комбинаторы S и K. И сравнение арифметики Пеано с КЛ некорректно, так как первая строится поверх теории множеств и вообще в аксиомах не нуждается.

В общем так, либо ты приводишь пример доказательства, которое изменится, если принять по определению I=SKK вместо I | для любого x I x = x, либо признавай свою неправоту.

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

> если ты до сих пор не видишь разницы между эквивалентностью и равенством то я не знаю уже как объяснить - я учитель дошкольников, а не в старших классах

Ну и учи своих дошкольников, а во взрослую математику не лезь, ты ее в упор не понимаешь. Принципиально.

> Ну и учи своих дошкольников, а во взрослую математику не лезь, ты ее в упор не понимаешь. Принципиально

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

дай мне пожалуйста аксиоматику твоей волшебной кл, может ты сделал какой то радикальный шаг вперёд, который мы не видим и не можем понять?

> ты даже не выучил в школе что такое индукция,

При чем тут индукция к S-K исчислению?

> дай мне пожалуйста аксиоматику твоей волшебной кл,

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

http://en.wikipedia.org/wiki/Combinatory_logic

Я еще тебе попросил привести пример доказательства, которое изменится, если положить по определению, что I=SKK.

всё хватит, пойми сначала как строятся теории, прочти внимательно ту самую ссылку http://en.wikipedia.org/wiki/Combinatory_logic осознай что переход SKK x = x к утверждению что SKK есть отношение тождества только при наличии отношения тождества

Пойми, ты говоришь что-то типа:

С чего вы взяли, что треугольник существует? Как мы можем доказывать теорему о сумме углов тр-ка, не приняв существования тр-ка как аксиому? Давайте введем аксиому, что треугольник существует.

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

Тебе попросили привести пример доказательства, которое изменится, от того, что определение I | I x = x поменять на I=SKK.

"

как I не назови это пофиг, хоть SKK хоть ТОЖДЕСТВО_ДЛЯ_МРАКОБЕСОВ, вывод ни одного комбинатора невозможен без него

смтотри, определим Y как комбинатор с характеристикой Y x = x(Y x), задача состоит в том чтоб вывести его через базисные, то есть прийти к Y = <нечто-из-K-и-S> .. с помощью K, S ты сможешь вывести Y x = (<нечто-из-К-и-S>) x, но кто даст тебе право сказать что Y это есть <нечто-из-K-и-S> ? не знаешь? а я знаю ..

всё с меня хватит, я завязываю с этим тредом

Ох, мама дорогая, читал и плакал! :-D

>> И как раз S и K составляют минимальный базис.

> ну выведи мне из них комбинатор тождества

lg, Вы таки не согласны с тем, что {S, K} - минимальный базис? Признайтесь в этом, и мы от Вас отстанем. =)

Тебе уже привели пример КНТ, выраженного через S и K. Что тебе еще надо?

> lg, Вы таки не согласны с тем, что {S, K} - минимальный базис? Признайтесь в этом, и мы от Вас отстанем. =)

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

> в кл без аксиоматического тождества - нет ..

докажи, пожалуйста, это утверждение

> в кл без аксиоматического тождества

М-да, месье знает толк в извращениях. =) Вы б ещё арифметику без сложения придумали!

Слиф защитан

> Слиф защитан

Нет, ну право, детский сад!

lg достаточно ясно объяснил, что он имел в виду, и он прав в том смысле, что для построения комбинаторной логики в современной её форме аксиоматически вводится существование _трёх_ комбинаторов, S, K и _I_, обладающих общеизвестными свойствами. Но опираясь на эти аксиомы, можно доказать минимальность базиса {S, K}, то есть в дальнейшем комбинатор тождества нам не понадобится, и в этом смысле прав онанимус.

Короче, предлагаю участникам дискуссии помириться наконец и идти пить пиво. =)

ну слава богу хоть один вменяемый :)

> Но опираясь на эти аксиомы, можно доказать минимальность базиса {S, K}, то есть в дальнейшем комбинатор тождества нам не понадобится,

Можно доказать минимальность базиса, не вводя аксиоматически существования I. В этом правы анонимусы, и не прав lg. Все.

Как знать... Ложки-то на самом деле нет.

увы да, я поганое чмо, I действительно не нужен аксиоматически, понял я это осознав что правило a=b => ac=bc работает в обе стороны :) - спасибо всем кто отрыл глаза!