Ответ на »сообщение 948« (Jack Of Shadows)
___________________________

Function types provide a natural way to express some kinds of abstraction that are currently quite awkward to express in Java.

Вот вам еще одно признание того что в ООП встроен жесткий потолок, который мешает описывать высокоуровневые абстракции естественным образом.


Как обычно, цитаты искажаются и "обобщаются" самым несерьезным образом.
Неохота разбирать.

И еще у меня складывается такое впечатление, что Вы спорите уже не со мной, а со всеми работами на эту тему :)

"It's easy to prove that all modern computers are Turing complete. This means not only that you can use a Turing machine to do simple arithmetic or calculate pi to n places but that you could simulate a word processor, spreadsheet or video game on a Turing machine."

http://www.cs.unm.edu/~saia/computability.html

>>>А я попробую. :-) "... Обратное, вообще говоря, неверно."

Если Вы заметили, то об обратном никто и не говорит! Того "прямого", что сказано, вполне достаточно.

>>>Если не быть формалистом, с этим можно согласиться. (Но как учитель
>>>математики оценит заявление ученика что отрезки – это прямые конечной
>>>длины?)

А что Вы так прицепились к этой бесконечности?!
Неужели непонятно, что для выполнения любого КОНЕЧНОГО алгоритма машина Тьюринга все равно будет использовать только КОНЕЧНОЕ количество ячеек своей ленты. Бесконечная лента потребуется только в случае бесконечной работы! А бесконечные "алгоритмы" мы вообще не обсуждаем, ибо они вообще не являются алгоритмами в общепринятом смысле слова, т.к. не обладают свойством результативности (по-Маркову). Поэтому любой реальный компьютер, а точнее любую программу, выполняемую на этом компьютере, можно имитировать с помощью соответствующей МТ - лента у нее, конечно, будет бесконечная, но использоваться будет все равно только отрезок конечной длины, который будет имитировать конечную память реального компьютера!

P.S.
Мне кажется, что Вы уже спорите не с моими исходными тезисами, а со своим
представлением о них :) Суть всех моих слов сводилась к тому, что по основным принципам функционирования любой реальный компьютер можно считать машиной Тьюринга, воплощенной в "железе". Архитектура компьютера буквально "срисована" с МТ: есть память (лента) и процессор (автомат). Процессор читает информацию из памяти и изменяет, как ее состояние, так и состояние самого себя. Т.е. ведет себя, как и положено любой машине Тьюринга. И с чем тут спорить-то?

Но если уж Вы такой формалист, то исправляюсь:
Все реальные компьютеры - это машины Тьюринга с конечной памятью.

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

Следовательно, для каждого реального компьютера можно построить эквивалентную этому компьютеру машину Тьюринга. Ну, и почему, спрашивается, я не могу считать любой реальный компьютер реализацией и некоторого конечного автомата, и некоторой эквивалентной этому автомату машины Тьюринга? Вопрос риторический - конечно, могу.
Естественно, можете. Дело в том, что отображение множества конечных автоматов в множество машин Тьюринга инъективно, но не сюръективно. А это нарушает логическую связность рассуждений из »сообщение 877«

А вот что говорит о closures один из разработчиков java Neal Gafter:

Function types provide a natural way to express some kinds of abstraction that are currently quite awkward to express in Java.

Вот вам еще одно признание того что в ООП встроен жесткий потолок, который мешает описывать высокоуровневые абстракции естественным образом.
Под давлением обстоятельств Sun приходится нехотя встраивать в java функциональные инструменты, вопреки тому что closures вообще то разрушают обьектную модель.

Вот это вот quite awkward то express в школах конечно не преподают.
Там будущим программистам вешают лапшу что ООП - это идеальный инструмент. На примерчиках все так просто, и красиво. К сожалению, отсутствие ДОКАЗАТЕЛЬСТВ и сплошные ничем не подтверженные утверждения мало кого из учеников беспокоят. Все хавается на ура.

А потом закончив школу программисты приступают к работе на больших проектах.
И вот тут они сталкиваются на каждом шагу с этим вот quite awkward то express.

Так рождается опыт. Опыт борьбы с инструментом, который вообще то призван помогать, а не мешать в работе.
Этот опыт четверка программистов, известная сегодня как Gang of Four, и изложила в своей книге Design Patterns.
Книга необходимая любому ООП программисту-практику. Моя настольная книга в годы работы на java. Без нее как без рук.
Однако книга вредная для школ, в которых преподают ООП.
Потому что прочитав эту книгу у учеников могут возникнуть неудобные вопросы.
Почему ? Почему требуется делать все эти странные и неуклюжие телодвижения ? Разве ООП не может дать адекватный механизм решения ТИПИЧНЫХ и ЧАСТО ВСТРЕЧАЮЩИХСЯ задач в виде библиотеки классов, как их всех учат ?

ОК, может быть проблемы, решаемые в design patterns являются трудно описываемыми на любом языке.
Если бы это было так, то design patterns были бы широко распространены независимо от языка.
Однако это не так. В сообществе лисперов design patterns совершенно не используются. Для подавляющего большинства проблем, решаемых design patterns в ОО языках, в лиспе (и в любом другом ФЯ) существуют адекватные механизмы создания соответствующих абстракций.
При этом полноценный ОО для реализации всех этих паттернов в лиспе и в ocaml есть.
И в принципе просто как упражнение все они могут быть реализованы. Но как полезный практический инструмент ? Да на черта они не нужны!

Такие попытки поупражняться в реализации известных design patterns в лиспе есть.
Вот например ссылка на Visitor Pattern из wikipedia: http://en.wikipedia.org/wiki/Visitor_pattern

Цитата: Lisp's object system with its multiple dispatch does not replace the Visitor pattern, but merely provides a more concise implementation of it in which the pattern all but disappears .

Вот еще реализация паттерна Iterator (совершенно бесполезная штука в лиспе) http://www.dynamiclearningcenter.com/samples/design-patterns/iterators-in-lisp-notes.html

Цитата: Lisp has sometimes been criticised for its lack of support for such patterns. Partly this is because design patterns are less useful in a high level language with an advanced object system, and which allows syntactic extensions, such as Lisp. Partly it is because the implementation of these patterns is sufficiently easy in Lisp that people have often not formalised them. However there is a place for these ideas in Lisp, even if it is sometimes only to aid communication with people using other languages!

:)))

Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides - программисты с большим стажем, накопили свои шишки на лбу, стукаясь в потолок абстракции ООП, в 80-х годах.
Понятно, выбора у них не было. Хочешь, не хочешь, а ООП было данностью в то время. Время ФП еще не пришло.
Приходилось мириться с тем что есть, и в 1995 году они выпустили книжку Design Patterns, суммирующюю их опыт ПРАКТИКИ ООП.

Но сегодня, сегодня у программистов есть возможность и есть выбор.
За полгода активной работы над сервером правил на лиспе, мне ни разу не пришлось заглядывать в мою некогда настольную книгу по design patterns.

Вы тоже можете вырваться из клетки ООП.
Для этого надо то всего ничего. Еще немножко поучиться :))

Ответ на »сообщение 944« (SJ)
___________________________

"Таким образом, любому конечному автомату соответствует эквивалентная машина Тьюринга"
Мне к этому больше добавить нечего.

А я попробую. :-) "... Обратное, вообще говоря, неверно."

Ответ на »сообщение 945« (SJ)
___________________________

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

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

>>>Мне к этому больше добавить нечего. Если хотите опровергайте :)
Поспешил. Добавлю только вывод :)
Итак, для любого конечного автомата можно построить машину Тьюринга, которая будет выполнять тот же самый алгоритм. Мои уважаемые оппоненты считают реальные компьютеры конечными автоматами. Отлично. Строим для каждого такого КА эквивалентную ему МТ. Следовательно, для каждого реального компьютера можно построить эквивалентную этому компьютеру машину Тьюринга. Ну, и почему, спрашивается, я не могу считать любой реальный компьютер реализацией и некоторого конечного автомата, и некоторой эквивалентной этому автомату машины Тьюринга? Вопрос риторический - конечно, могу.

>>>Что же касается "машины Тьюринга с конечной памятью", то если эта память
>>>объемом N символов M-значного алфавита, то это ни что иное, как конечный
>>>автомат с M^N состояний. Не нужно подменять понятия.

Не будем подменять понятия :)
Обратимся к "независимым экспертам", мнению которых я, почему-то, доверяю :).
Вот две выдержки из книги "ЦВМ: принципы построения цифровых вычислительных машин", авторы Бузунов Ю.А., Вавилов Е.Н., Изд. "Техника", 1972, рецензент Малиновский Б.Н.,чл.-корр.АН УССР. (это я для того, чтобы меня не обвинили в неверном цитировании).
Итак, пропускаем математические подробности теории алгоритмов, открываем стр 22:
"Нетрудно показать, что можно построить машину Тьюринга, которая будет выполнять алгоритм, реализуемый произвольным конечным автоматом. Для этого достаточно использовать заданный автомат в качестве управляющего автомата машины Тьюринга"...
И далее:
"Таким образом, любому конечному автомату соответствует эквивалентная машина Тьюринга"
Мне к этому больше добавить нечего. Если хотите опровергайте :)

Ответ на »сообщение 942« (SJ)
___________________________

Все реальные компьютеры - это машины Тьюринга с конечной памятью.

Тогда это не машина Тьюринга. Если память конечна, то, очевидно, найдется алгоритм, который невозможно реализовать в этой памяти (например, если у нас память объемом N знаков, попробуйте в ней отсортировать массив размером N+1). А машина Тьюринга по определению это универсальный исполнитель, способный выполнить любой алгоритм.

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

Что же касается "машины Тьюринга с конечной памятью", то если эта память объемом N символов M-значного алфавита, то это ни что иное, как конечный автомат с M^N состояний. Не нужно подменять понятия.

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

Взаимно.