Зачем нужна обработка списков в искусственном интеллекте?

LISP был придуман Джоном Маккарти в 1958 году для решения задач нечислового характера и базировался на трех основных китах: алгебре списочных структур, лямбда исчислении, теории рекурсивных функций. Долгое время LISP использовался исключительно узким кругом специалистов по искусственному интеллекту. Но, начиная с 80-х годов прошлого века, LISP начал набирать обороты и сейчас активно используется, например, в AutoCad и Emacs. [/qupte]

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

Но, например, ребята из OpenCOG пишут на C++.

По легенде, Lisp придуман для решения задач искусственного интеллекта. Зачем для этого надо было придумывать такой довольно необычный язык - язык обработки списков?

задумайся, как ты будешь записывать алгоритмы? Очевидно, тебе нужен список, и не просто список, а список, который ты можешь ВЫПОЛНЯТЬ. Т.е. тебе нужен такой язык, в котором в переменную можно класть не только числа, но и функции.

Вот пример:

 (defun factorial (n)
   (if (= n 0)
       1
       (* (factorial (- n 1)) n)))
}

Т.е. в списке действий есть не только функции над числами, но и другие списки. В фортране/сишечке так нельзя сделать (т.е. можно конечно, но уж больно запутано)

задумайся, как ты будешь записывать алгоритмы? Очевидно, тебе нужен список, и не просто список, а список, который ты можешь ВЫПОЛНЯТЬ

суть в том, что в последней строке ты умножаешь число на функцию

Наркоман, уходи.

Но, например, ребята из OpenCOG пишут на C++.

ВНЕЗАПНО: не только. Ещё на питоне и на схеме. Ещё более внезапно: если-бы они не трогали схему, то пришлось-бы им свой лисп выдумывать, СБИШ.

суть в том, что в последней строке ты умножаешь число на функцию

Наркоман, уходи.

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

И да, как обычно, первая таблетка бесплатно. Это SICP. Но там незаметно. Вроде читаешь — и всё нормально. Но если ты осилил дочитать до конца — скорее всего ты уже конченный наркоман.

В качестве пруфа, почитай вот эту статью: http://ru.wikipedia.org/wiki/Монада_(программирование) Там просто... Для упоротого.

суть в том, что в последней строке ты умножаешь число на функцию.

Да что за бред ты несёшь?

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

а как я их записываю в С? беру и записываю без всяких списков :)

Десятое правило Гринспуна...

Подсказка: языком для ИИ Лисп называют не потому что в нём были списки, а потому что в нём появились символы.

они изобрели рекурсию

Спасибо за подсказку. Имеются в виду строки (типа «abc»)? Почему это так существенно для ИИ? Вроде ничего супер-революционного.

Нет, имеются ввиду не строки.

Как непредсказуемо складывается судьба! Lisp в теории самый могучий, универсальный и удобный ЯП, но в реальном мире им никто не пользуется. PHP (Personal Home Page) сегодня используют далеко не только для домашних страничек, где ему должно было быть место. Java задумывалась как язык для тостеров и кофемолок, а очутилась в банках и в промышленности. Ruby был призван «вернуть fun в программирование», но привнёс только новую грусть и проблемы (то же касается и Python). SQL делался для людей, далёких от программирования, но сегодня таит в себе уйму технических нюансов и требует недюжинной квалификации. Haskell из академического языка-полигона превратился в объект нездорового культа среди жителей российской глубинки. Кто бы мог подумать!

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

int getRandom(){
    return 4;
}

int main(int argc, char *argv[])
{
    int b, c;
    b = getRandom();
    c = b * getRandom();
    cout<<c;
}

Запутано просто жутко, "(* (factorial (- n 1)) n)))" куда нагляднее.

Ну и для полноты картины:

int factorial(int x) { 
    return !x ? 1 : x * factorial(x - 1);
}

они изобрели рекурсию

Кто? И как это связано с «умножением числа на функцию»?

Имеются в виду строки (типа «abc»)? Почему это так существенно для ИИ?

Не только строки, но их уникальность по всей программе, возможность использовать их как имена переменных, и связывать с символами пачку значений внутри property lists. И проистекающие отсюда плюшки в виде макросов.

Вроде ничего супер-революционного.

Ну это сейчас так кажется :) А 50 лет назад было ого-го!

Хотя, думаю, немалую роль в формировании стереотипа «Лисп для ИИ» сыграло то, что Лисп удачно появился, когда ИИ был модым и от него ожидали решения всех проблем человечества.

суть в том, что в последней строке ты умножаешь число на функцию.

Да что за бред ты несёшь?

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

Вот что пишет по этому поводу вика:

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

В фортране аргументом любого оператора может быть только число.

В сишечке можно извернуться, и написать функцию, которая принимает указатель на функцию. Тогда можно тоже использовать лямбда исчисления. Т.е. например написать qsort(3), которая сортирует что угодно. Для сравнивания этого «чего угодно» qsort принимает указатель на функцию сравнения. Это работает, но выглядит довольно забавно. В ФП нет нужды для таких извращений. Там, если тебе надо скажем умножить функцию на число, прямо так и пишешь (* (factorial (x)) y) Тут factorial(x) умножается на y. В сишечке этот factorial будет жёстко вбит в код, а в ФП это просто переменная, не хуже x и y.

тогда какие символы имеются в виду?

а как я их записываю в С? беру и записываю без всяких списков

вот в том-то и дело, что так ты можешь записать только ОДИН алгоритм. Который никогда не поменяется. Что-бы он поменялся, это надо найти тебя, что-бы ты всё это исправил, и сделал новую версию своей программы. Ну а используя ФП, вполне реально написать такой код, который будет работать так, как это нужно в данном случае.

Те, которые 'foo.

Потому что списки — элемент исчисления символов

от него ожидали решения всех проблем человечества.

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

а потому что в нём появились символы.

символы были задолго до LISP'а. И списки тоже. В т.ч. и списки списков символов.

Ты действительно не различаешь вызов функции и передачу ее как аргумента функции?

«Символ» — дурацкое слово. Лучше использовать слово «атом». Единичный неделимый объект «в себе».

В каком языке программирования?

они изобрели рекурсию

рекурсия тоже была известна намного раньше.

Десятое правило Гринспуна...

в этой шутке есть доля шутки...

Эти

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

Изменять себя?

Имеются в виду строки (типа «abc»)? Почему это так существенно для ИИ?

в строке «abc» нет ничего существенного. Это просто строка. Просто число. А вот в строке factorial из моего примера есть существенное — это не просто строка/число, а алгоритм. Математики записывают этот алгоритм так

n! = 0; если n == 0
n! = n*(n-1)!; если n > 0

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

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

У LISP'а есть свои достоинства и недостатки. А серебряной пули не существует.

так а в чём разница с

int factorial(int x) { 
    return !x ? 1 : x * factorial(x - 1);
}

b = getRandom(); c = b * getRandom();

тут ты умножаешь ЗНАЧЕНИЕ функции, а не функцию.

Запутано просто жутко, "(* (factorial (- n 1)) n)))" куда нагляднее.

это к ЯП не относится. Тебе просто непривычна такая запись. Но она более удобна. Т.е. вместо 2+2*2 удобнее писать + 2 * 2 2. Причём заметь: в первом случае мне неявно понадобились скобки, т.к. сначала надо считать умножение, а во втором случае скобки не нужны, т.к. порядок вычислений определён без них. Т.ч. лисповые скобочки позволяют ВНЕЗАПНО экономить скобочки.

Самое смешное, что как будет работать x*y*z в сишечке — не знает никто. Причём даже скобками невозможно задать последовательность вычислений. В ФП таких фэйлов попросту не может быть.

int factorial(int x) { return !x ? 1 : x * factorial(x - 1);}

тут у тебя функция гвоздями прибита к коду. А если ты захочешь посчитать не произведение, а сумму? В лиспе достаточно вместо * поставить любую функцию. В сишечке — извините. Всю программу надо переписать.

А указатели на функции в сишечке — не самая понятная штука...

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

потому-что его ещё не придумали. Научи дикаря рисовать разные математические закорючки, ты думаешь, после этого он будет понимать формулы из высшей математики? Одного ЯП недостаточно для решения задачи. Ну вот тебе простой пример: ты можешь на сишечке без гугла и без math.h написать программу, которая вычисляет кубические корни? Да, все три.

А указатели на функции в сишечке — не самая понятная штука...

Так бы сразу и сказал, что ниасилил.

на сишечке без гугла и без math.h написать программу, которая вычисляет кубические корни?

Метод монте-карло. Долго, но приблизительно вычислить можно.

Ты действительно не различаешь вызов функции и передачу ее как аргумента функции?

в ФП просто нет такого понятия, как «вызов функции». Там функция == аргумент. А в сишечке эта задача решается исключительно костылями — указателями на функцию. Т.е. что-бы использовать функцию как аргумент, надо её представить как ЧИСЛО. И вот только тогда, функции удастся передать как аргументы.

В каком языке программирования?

ни в каком. Они ещё в машинных кодах были. Ещё ДО ЯП.

в ФП просто нет такого понятия, как «вызов функции». Там функция == аргумент. А в сишечке эта задача решается исключительно костылями — указателями на функцию. Т.е. что-бы использовать функцию как аргумент, надо её представить как ЧИСЛО. И вот только тогда, функции удастся передать как аргументы.

Это кресты так мозг разжижают?

Изменять себя?

именно так. Ты же можешь придумать новый алгоритм? А твой код на сишечке — не может. Даже если и может, то он не сможет этот алгоритм выполнить, если конечно ты не реализуешь какое-то подмножество LISP'а в своём коде.

суть в том, что в последней строке ты умножаешь число на функцию.

Вот, теперь я верю, что ты реинкарнация drBatty. Такой же бред несёшь. Феерический.

разница в том, что у тебя factorial == ЧИСЛО. Причём не просто число, а константа, жёстко вбитая в код. А в LISP'е это не число, а функция. Т.е. указатель на некоторый список последовательности действий. Причём этот список не жёстко вбит в память компьютера, а вполне себе изменяемый, и заранее в общем случае неизвестный.

На самом деле, в твоём примере тоже есть такой список. Неявно он хранится в стеке процессора. Он строится каждый раз по новой, и именно там и записано, как и куда код будет переходить.

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

Ты не знаешь правила вычисления в Lisp'е? Я могу тебе их объяснить (не будем трогать специальные формы)!

Упрощённый алгоритм вычисления function form таков:

1. вычислить все аргументы (cdr списка) слева направо;
2. применить функцию (car списка) к вычисленным значениям аргументов.

Не так уж и сложно!

Применительно к примеру с факториалом ((* (factorial (- n 1)) n)) это выглядит так:

1. вычислить (factorial (- n 1)) рекурсивно по правилам, описанным выше;
2. вычислить n;
3. применить * к результатам вычислений.

Так скажи мне, где здесь умножения числа на функцию?

А вот тебе пример функции высшего порядка (mapcar), для контраста:

(mapcar #'factorial '(1 2 3))

А говорить, что в лиспе можно умножить число на функцию, равносильно утверждению, в следующем примере число i умножается на функцию rand:

int foo = i * rand();

Но это ведь тупость, правда?

Вот что пишет по этому поводу вика:

Ох, то есть у тебя трудности даже с пониманием информации с вики.

Четверг обещает быть занятным.

А в лиспе с ними стало _удобно_ работать.

А указатели на функции в сишечке — не самая понятная штука...

Так бы сразу и сказал, что ниасилил.

что там осиливать? Там всё просто. Только жутко неудобно. Дело в том, что работа например с массивом функций выглядит так, что с первого взгляда совершенно не очевидно, как ЭТО работает. И проблема даже не в синтаксисе, а в самой парадигме этого ЯП.

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

тут ты умножаешь ЗНАЧЕНИЕ функции, а не функцию.

Ты правда не понимаешь, что в случае с лиспом ты тоже умножаешь на ЗНАЧЕНИЕ функции, или просто притворяешься? Я просто к тому, что такой тупости я даже от тебя не ожидал.

Рассуждения о порядке вычислений я комментировать не буду.

И проблема даже не в синтаксисе, а в самой парадигме этого ЯП

Што? В какой парадигме? В голых сях проблема только в синтаксисе.