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

> Спор ведь шел о символах и символьных вычислениях в CL,
> а Вы начинаете, мягко говоря, уводить в сторону.

Это я начинаю его уводить в сторону? Это не я говорил, что CL это алгебра над списками и прочий бред. Я привёл примеры код, реализующих символьные вычисления в императивном стиле и попросил объяснить при чём тут вообще алгебра.

archimag (05.03.2010 11:49:01)

> Я просто попытался показать, что имеет ввиду оппонент.

Извините, я не собираюсь гадать, что он (они, хрен их тут разберёшь) на самом деле имеет в виду: у него скорей всего просто каша в голове.

archimag (05.03.2010 11:53:45)

а может и у Вас каша? В общем, это Ваше дело, соглашаться с оппонентом или нет, понимать его или нет. Стиль Вашего общения тоже не всегда адекватен. Ну, да у всех свои недостатки. Жаль только, что он не рассказал о практических выводах.

>Это не я говорил, что CL это алгебра над списками и прочий бред.

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

> Тебе говорят, что Лисп ( и CL тоже) есть алгебра над списками и атомами. Об этом, кстати, пишут финские авторы на стр. 79 в своей книге. Что тут непонятного?

> Ты, я так понимаю, под алгеброй имеешь ввиду нечто другое - уравнения и т.д.. Но вообще-то алгебра (это уже другое понятие - не смешивать с тем, что выше!)как дисципина является очень обширной областью. Фактически она занимаются множествами, над которыми заданы те или иные операции. И это не обязательно только лишь алгебраические преобразования в "привычном" смысле (подстановки, разложение на множители).

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

> В базе CL именно алгебра над списками заложена.

В очень давней базе, в LISPе, наверное. Какая алгебра заложена в symbol plist? Какая алгебра заложена в создании 2ух пространствах имен - для функций и для переменных. Да никакой - это было сделано *только* из практических соображений.

>Называть лисповые символьные вычисления алгеброй - это полнейшее безграмотность.

Я Выше привел показательный пример с действительным числами. Когда Вы складываете числа, то Вы занимаетесь алгеброй. Хотя можете даже и не осозновать этого. Вот когда Вы рассуждаете о том, связно ли некоторое подмножество действительных чисел, вот тогда Вы уже перестаете заниматься алгеброй. В основе работы со списками в Лиспе лежит алгебра. Об этом речь. Вы же не говорите, что полей действительных чисел (над * и +) не является полем на том основании, что там еще может быть введена топологическая структура. Просто алгебра - некоторая точка зрения на некоторое множество с точки зрения алгебраических операций, введенных нами, безотносительно внутренней структуры элементов или дополнительных структур в множестве.

> В основе работы со списками в Лиспе лежит алгебра.

Выше уже ответили, но только зачем вы упираете на работу со списками? Ну при чём тут вообще работа со списками? А если я буду использовать только массивы? А если только структуры? А если только CLOS? А деструктивные операции? И какое отношение списки имеют к символам?

archimag (05.03.2010 12:47:37)

> Когда Вы складываете числа, то Вы занимаетесь алгеброй. Хотя можете даже и не осозновать этого.

"Когда я сижу на стуле, я занимаюсь физикой". Нет. У вас каша в голове. Когда я складываю числа, я занимаюсь арифметикой. Я занимаюсь алгеброй, когда работаю с алгебраическими структурами. Это принципиально и важно.

> Вы же не говорите, что полей действительных чисел (над * и +) не является полем на том основании, что там еще может быть введена топологическая структура.

Разницу между математическими структурами и нематематическими вы улавливаете? И это не совсем одно и то же. Символьные вычисления в CL - это не абстракция, это объективная реальность данная нам в ощущениях. То, что списочная алгебра не отражает их - это факт.

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

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

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

Практические выводы применены, например, в системе Axiom. А вообще они очень, очень далеко идущие, выводы эти.

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

> Каким образом сугубо императивный язык имеет отношение к алгебре над списками?

Ля-ля-ля. Императивный язык - алгебра над состоянием. Ага?

Ну да я знаю, что ты ничего про монады и слышать не желаешь. Ты же ламер...

> Ты называешь "символьными вычислениями" то, что ими не является.

Я привёл примеры преобразований текста в символьное представление, символьного представления шаблона в код на CL, шаблона в символьное представление кода на JS (в формате parenscript), кода на CL в код на JS и спросил у всех является ли это примеров символьных вычислений. Никто пока так и не ответил. Судя по вашей позиции, вы утверждаете что данные преобразования не являются примерами символьных вычислений? Вы можете сказать это явно?

archimag (05.03.2010 13:22:17)

> Я утверждаю, что cl-closure-template является примеров символьных вычислений и не имеет никакого отношения к алгебре.

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

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

dave (05.03.2010 13:24:00)

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

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

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

> Когда тебя мордой ткнули в определение
> symbolic computation из википедии

Более авторитетных источников не нашли?

> Те, которые отобразимы на term rewriting.

Какие? И что такое остальное?

> Тем самым подписавшись, что ты просто дурак, и не более того

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

archimag (05.03.2010 13:37:59)

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

Давай просвети незрячих.

а смысл?

> а смысл?

Интересно же, вдруг ты знаешь, чего-то, чего не знаю я :)

во-первых, вряд ли. У меня физическое образование, а не математическое. Да и в Лиспе я новичок. А просвещать людей, которые и не желают просвещаться, неблагодарное занятие) А вот если бы Вы просветили относительно далеко идущих практических выводов... Хотя бы полезные ссылки)

> У тебя своё, альтернативно одарённое определение > "символьных вычислений".

Давайте попробуем взять уж очень старую вещь (когда люди знали в этом толк), LISP 1.5 Programmer's Manual и начнём читать:

Или там:

Или стоит обратиться к другому источнику, например Common Lisp: A Gentle Introduction to Symbolic Computation и попробуем выяснить у кого проблемы с терминологией?

archimag (05.03.2010 14:09:12)

> "used for symbolic calculations in differential and integral calculus, electrical circuit theory, mathematical logic, game playing, and other fields of artificial intelligence"

Это symbolic calculations именно в том смысле, как его используют все, кроме тебя. Читай внимательнее.

Во второй цитате этот термин не употребляется. Лечи зрение.

> Это symbolic calculations именно в том смысле,
> как его используют все, кроме тебя.

В каком? Ссылку с цитатой пожалуйста. Только не на математиков, а на литературу по лисп.

archimag (05.03.2010 14:23:36)

> Более авторитетных источников не нашли?

Для твоего уровня и авторитет википедии зашкаливает.

http://www.google.com/search?q=site:citeseer.ist.psu.edu+symbolic%20and%20cal...

http://planetmath.org/encyclopedia/AlgebraicComputation.html

http://www.elsevier.com/wps/find/journaldescription.cws_home/622902/descripti...

> Ваша неспособность аргументировать свою позицию

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

Я ошибся в предыдущем посте. Ты действительно идиот. Цитата была твоя же. Завязываю с этим спором, с упёртыми, наглыми придурками говорить не о чем.

> У алгебры есть совершенно четкое определение.

RTFM определение абстрактной алгебры.

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

Символьные вычисления - это частный случай term rewriting system. Любая term rewriting system это алгебра.

Так что любая форма символьных вычислений это алгебра.

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

P.S. Машина Тьюринга - это тоже частный случай TRS. Что как бы элементарно доказывается из Тьюринг-полноты лямбда-исчисления.

> Символьные вычисления - это частный случай term rewriting system.
> Любая term rewriting system это алгебра.

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

archimag (05.03.2010 14:56:12)

> RTFM определение абстрактной алгебры.

Это ты про раздел математики? Причем здесь это?

> Это ты про раздел математики? Причем здесь это?

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

> Т.е. вы по прежнему утверждаете, что логика это алгебра?

Да, конечно же это абстрактная алгебра.

Множество определяется как: E \in T, if:

- E = 0

- E = Var (аналог единицы, но с несколько более сложными свойствами)

- E = tag(E...)

Над элементами этого множества определена операция унификации и композиции.

Если это для тебя слишком сложно, то вот тебе доказательство на пальцах: TRS это алгебра, лямбда-исчисление это TRS, логика предикатов тождественна лямбда-исчислению => логика предикатов это TRS, и логика предикатов это алгебра.

можно было просто дать
ссылку на булеву алгебру.

но вопрос остается прежним:
приведите пример как эти
знания могут улучшить код?

маленький конкретный пример

> можно было просто дать
> ссылку на булеву алгебру.

Хм, булева алгебра является логикой???

archimag (05.03.2010 15:30:44)

> можно было просто дать ссылку на булеву алгебру.

Нелья - разговор был про логику предикатов.

> но вопрос остается прежним: приведите пример как эти знания могут улучшить код?

Знания о том, какие преобразования транзитивны, например, позволяют код оптимизировать. Знание о том, что преобразование можно разделить на последовательность элементарных преобразований, позволяет писать более простой и читабельный код. Посмотри на любой хороший компилятор, его разработчики неизбежно этим знанием пользовались. Тот же SBCL подойдет.

Посмотри на любую реализацию XSLT. Не знающий ничего про алгебры XSLT сделать не смог бы.

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

Ну т.е. вообще "формальная система" это алгебра, я правильно понял?

> Над элементами этого множества определена операция
> унификации и композиции.

В логике? Тогда там может и резолюция сразу определена? чего уж мелочиться...

> лямбда-исчисление это TRS

Насколько я помню, в основе лямбда-исчисление лежит аппликация и лябда-абстракция, где TRS?

> логика предикатов тождественна лямбда-исчислению

На каком основании две различных формальных системы тождественны?

archimag (05.03.2010 15:40:06)

> Насколько я помню, в основе лямбда-исчисление лежит аппликация и лябда-абстракция, где TRS?

\alpha-, \beta- и \eta- редукции + определение нормальной формы. Чистейший TRS. Посмотри в примеры Qi II, там есть реализация лямбды.

> На каком основании две различных формальных системы тождественны?

Что такое Тьюринг-полнота знаешь? Доказательства Тьюринг-полноты для лямбда-исчисления и для логики предикатов видел?

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

Почитай вот эту книгу, если сможешь найти:

http://assets.cambridge.org/052139/1156/sample/0521391156WS.pdf

(по ссылке только первые 15 страниц, с оглавлением)

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

> \alpha-, \beta- и \eta- редукции + определение нормальной формы.
> Чистейший TRS.

И что с того? Это превращает лямбда-исчисление в TRS?

> Что такое Тьюринг-полнота знаешь? Доказательства Тьюринг-полноты
> для лямбда-исчисления и для логики предикатов видел?

Это является основание назвать их тождественным? Тогда я полагаю язык C тождественен языку Common Lisp?

> Посмотри на любую реализацию XSLT. Не знающий ничего
> про алгебры XSLT сделать не смог бы.

Смотрел и много, расскажи пожалуйста про использование алгебры в libxslt (можешь не стесняться, я хорошо ориентируюсь в исходниках).

archimag (05.03.2010 15:53:33)

> И что с того? Это превращает лямбда-исчисление в TRS?

Да. Упёртый ты. А значит - глупый. Как ты сумел диплом то получить вообще?

> Это является основание назвать их тождественным?

Математически - да. Ровно на тех же основаниях, на каких SK-логика тождественна SKI-логике, например.

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

> Смотрел и много, расскажи пожалуйста про использование алгебры в libxslt (можешь не стесняться, я хорошо ориентируюсь в исходниках).

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

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

>> И что с того? Это превращает лямбда-исчисление в TRS?
> Да. Упёртый ты. А значит - глупый.

Т.е. обосновать формально, что лямбда-исчисление это TRS вы не можете? Зачем тогда глупости говорите?

>> Это является основание назвать их тождественным?
>> Тогда я полагаю язык C тождественен языку Common Lisp?
> Математически - да. Ровно на тех же основаниях, на каких SK-логика
> тождественна SKI-логике, например.

Ну ка, что значит тождественны математически? Википедия даёт такое определение:

Википедия, конечно, не авторитет, так что предлагаю вам привести своё, ну либо отталкиваться от данного и пояснить, что вы всё таки имеете в ввиду?

> Для начала осознай, что язык XSLT это алгебра.

Так, сначал было сказано:

Я то посмотрел, но теперь смотреть на реализацию вы уже не хотите, и предлагает вернуться к своей любимой теме, что всё это АЛГЕБРА?

archimag (05.03.2010 16:13:42)

> Т.е. обосновать формально, что лямбда-исчисление это TRS вы не можете? Зачем тогда глупости говорите?

Я и обосновал. А ты не понял. Потому что ты дурак.

Я перечислил все шаблоны в этой TRS. А ты, дурак, не понял.

> так что предлагаю вам привести своё, ну либо отталкиваться от данного и пояснить, что вы всё таки имеете в ввиду?

Тождество и тождественность не различаем?

RTFM про "Turing equivalence".

> Я то посмотрел

Тебе смотреть бесполезно. Ты слеп, потому как глуп и безграмотен.

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

P.S. вот еще одна хорошая книга: http://books.google.com/books?id=N7BvXVUCQk8C&printsec=frontcover&source=gbs_...

Там как раз доказывается, что lambda calculus это TRS, и что логика предикатов это TRS. Пересказывать доказательства для упёртого и неспособного слушать, я уж не стану, извини. Если умеешь читать, то прочитаешь. За то время, что ты потратил на этот идиотский спор, ты бы уже успел прочитать и Чейтина, и Окасаки, и эту книгу.

P.S. Будешь искать про "тождественность" - то дабы не нарываться вместо этого на "тождество", читай про "отношение тождественности" и "отношение эквивалентности".

Ну и совсем уж в лоб, если тебе лениво много букв осиливать:

http://rw4.cs.uni-sb.de/~mueller/lconfluence.ps.gz