Здравствуйте, catbert, Вы писали:
C>Тем не менее, шаблоны не "плохи". Они чудесно выполняют свою главную функцию (поддержка обобщенного программирования), да еще и Тюринг-полны. Но в реалиях .НЕТ-а, имхо, более оптимальным выбором метапрограммирования являются макросы+генерики.
Тьюринг полны это ты погорячился, по определению "В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию", можно ли на шаблонах реализовать любую? Мы пришли к выводу что нет.
Но вот макросы + генерики это хорошая комбинация, но как оказалось еще не совсем совершенная, если мы не можем использовать аргументы типа T в самих макросах, тут нужно еще промежуточное решение.
Здравствуйте, CodingUnit, Вы писали:
CU>Тьюринг полны это ты погорячился, по определению "В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию", можно ли на шаблонах реализовать любую? Мы пришли к выводу что нет.
Можно поподробнее выделенное? Или здесь имеется ввиду ограничение на число рекурсивно вложенных инстанциаций шаблона?
Здравствуйте, Alexey F, Вы писали:
AF>Здравствуйте, CodingUnit, Вы писали:
CU>>Тьюринг полны это ты погорячился, по определению "В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию", можно ли на шаблонах реализовать любую? Мы пришли к выводу что нет. AF>Можно поподробнее выделенное? Или здесь имеется ввиду ограничение на число рекурсивно вложенных инстанциаций шаблона?
Я разве сказал что то об инстанционировании шаблона? Я сказал что на шаблонах нельзя написать любую программу в терминах Тьюринга, то есть нельзя писать в файлы, читать, выводить на экран, все что есть это какие то ограниченные прагма директивы конкретного компилятора, короче говоря на них нельзя написать программу любой сложности как на самом С++, C# и Nemerle потому что шаблоны не Тьюринг полны. Выкрутасы которые на них делают оперируя с определениями типов, не то на что расчитаны сами шаблоны, поэтому и компиляторы не все поддерживают эти функции, и скорее более хак чем родная функция, как и на макросах C можно сделать многое что на них никто не собирался изначально делать. Но это некачественное решение на фоне существующих систем метапрограммирования.
Здравствуйте, CodingUnit, Вы писали:
CU>Я разве сказал что то об инстанционировании шаблона? Я сказал что на шаблонах нельзя написать любую программу в терминах Тьюринга, то есть нельзя писать в файлы, читать, выводить на экран, все что есть это какие то ограниченные прагма директивы конкретного компилятора, короче говоря на них нельзя написать программу любой сложности как на самом С++, C# и Nemerle потому что шаблоны не Тьюринг полны.
Тут Тюринг ни при чем он про рисование на экране не говорил.
Здравствуйте, CodingUnit, Вы писали:
CU>Я разве сказал что то об инстанционировании шаблона?
Я предположил этот аргумент.
CU>Я сказал что на шаблонах нельзя написать любую программу в терминах Тьюринга, то есть нельзя писать в файлы, читать, выводить на экран
Пардон? Сама машина Тьюринга может не иметь возможности читать/писать в файлы и что-либо выводить на экран.
Равно как и программа для иного микроконтроллера, из всех возможностей имеющая лишь пинать пару-тройку ножек, может быть реализацией машины Тьюринга для небесконечной ленты.
Здравствуйте, Alexey F, Вы писали:
CU>>Я сказал что на шаблонах нельзя написать любую программу в терминах Тьюринга, то есть нельзя писать в файлы, читать, выводить на экран AF> Пардон? Сама машина Тьюринга может не иметь возможности читать/писать в файлы и что-либо выводить на экран. AF>Равно как и программа для иного микроконтроллера, из всех возможностей имеющая лишь пинать пару-тройку ножек, может быть реализацией машины Тьюринга для небесконечной ленты.
Тем не менее она должна быть возможна выполнять все функции что возможны на этой машине, мы говорим о современных архитектурах а не машины 50 летней давности и тема у нас о шаблонах, так чем они Тьюринг полны по вашему?
Здравствуйте, CodingUnit, Вы писали:
CU>Он говорил о любой функции, а на современных машинах это функции операционной системы.
Когда он это говорил? Можно цитату или ссылку на источник (см. выделенное ниже)?
Мои источники и память говорят лишь о машине, оперирующей над последовательностью операций на (разбитой на ячейки) ленте, с возможностью перемещаться по этой ленте влево и вправо, считывать и перезаписывать ячейки на оной для некоторого набора команд. Как раз эта машина может реализовать любые вычислительные ф-ции, да хоть эмуляцию любой современной машины со всеми её потрохами и запуском современной же операционной системы на ней.
Здравствуйте, CodingUnit, Вы писали:
CU>Он говорил о любой функции, а на современных машинах это функции операционной системы.
Тюринг говорил о вычислениях а не об IO. Опять же, если добавить примитив system, который вызывает из шаблона любую системную функцию, то шаблоны моментально станут Тюринг-полными и по вашему определению.
Здравствуйте, catbert, Вы писали:
C>Тюринг говорил о вычислениях а не об IO. Опять же, если добавить примитив system, который вызывает из шаблона любую системную функцию, то шаблоны моментально станут Тюринг-полными и по вашему определению.
Так вот сначала надо добавить этот примитив чтобы возможно было выполнять любую функцию, но сейчас такой возможность нет, поэтому и не полны по тьюрингу.
Re[7]: [почти offtop]
От:
Аноним
Дата:
04.02.12 11:00
Оценка:
Здравствуйте, CodingUnit, Вы писали:
CU>Здравствуйте, catbert, Вы писали:
C>>Тюринг говорил о вычислениях а не об IO. Опять же, если добавить примитив system, который вызывает из шаблона любую системную функцию, то шаблоны моментально станут Тюринг-полными и по вашему определению.
CU>Так вот сначала надо добавить этот примитив чтобы возможно было выполнять любую функцию, но сейчас такой возможность нет, поэтому и не полны по тьюрингу.
Добавляется через прагму. Только полнота по тьюринигу не зависит от ввода вывода. Это возможность написать программу которая по входным данным выдает выходные по алгоритму конечной длинны
Здравствуйте, Alexey F, Вы писали:
AF>Здравствуйте, CodingUnit, Вы писали:
CU>>Он говорил о любой функции, а на современных машинах это функции операционной системы. AF>Когда он это говорил? Можно цитату или ссылку на источник (см. выделенное ниже)? AF>Мои источники и память говорят лишь о машине, оперирующей над последовательностью операций на (разбитой на ячейки) ленте, с возможностью перемещаться по этой ленте влево и вправо, считывать и перезаписывать ячейки на оной для некоторого набора команд. Как раз эта машина может реализовать любые вычислительные ф-ции, да хоть эмуляцию любой современной машины со всеми её потрохами и запуском современной же операционной системы на ней.
Смотря что понимать под множеством выполнимых функций, если мы говорим о сравнении полноты языков программирования, то шаблоны вряд ли можно назвать полным формализмом. И ОС на нем не запустить, и команд как таковых нет.
Здравствуйте, CodingUnit, Вы писали:
CU>Тем не менее она должна быть возможна выполнять все функции что возможны на этой машине
Нет, она не должна. Серьёзно, Алан Тьюринг и словом об этом не обмолвился.
CU> мы говорим о современных архитектурах а не машины 50 летней давности и тема у нас о шаблонах, так чем они Тьюринг полны по вашему?
Тьюринг-полный язык программирования, который был создан 50 лет назад и без изменений функциональности перенесён на современную машину, даже не имея возможности выполнять все функции, что возможны на этой машине, остаётся тьюринг-полным.
Возможность уравнять права кода на этапе компиляции и кода на этапе выполнения, выражающаяся в возможности без внешних инструментов работать с возможностями ОС, безусловно полезна (читать как "невообразимо полезна"), но не имеет отношения к тьюринг-полноте.
Даже brainfuck(<>[]+-.,) тьюринг-полон — и это не мои домыслы. Я даже не знаю, стоит ли приводить источники, где упоминается о его тьюриг-полноте...
Здравствуйте, Аноним, Вы писали:
А>Добавляется через прагму.
И что можно сделать в шаблоне добавив прагму с вводом выводом системы? Помоему Вы говорите о конкретном компиляторе возможности которого ограниченны конкретным набором прагма директив.
A> Только полнота по тьюринигу не зависит от ввода вывода. Это возможность написать программу которая по входным данным выдает выходные по алгоритму конечной длинны
Так как можно по входным данным в шаблонах написать программу которая выдает выходные?
Re[7]: [почти offtop]
От:
Аноним
Дата:
04.02.12 11:08
Оценка:
Здравствуйте, CodingUnit, Вы писали:
CU>Смотря что понимать под множеством выполнимых функций, если мы говорим о сравнении полноты языков программирования, то шаблоны вряд ли можно назвать полным формализмом. И ОС на нем не запустить, и команд как таковых нет.
Запуск ос не возможно только по одной причине. Ограничение глубины рекурсии. Да и не совсем понятно как смотреть ее исполнение.
Здравствуйте, CodingUnit, Вы писали:
CU>Смотря что понимать под множеством выполнимых функций, если мы говорим о сравнении полноты языков программирования, то шаблоны вряд ли можно назвать полным формализмом. И ОС на нем не запустить, и команд как таковых нет.
Для тьюринг-полноты достаточно команд brainfuck'а, а реализация brainfuck на шаблонах C++ имеется Ввод/вывод, конечно, неинтерактивный, иногда в реализациях для простоты убирают ввод.
Вот минимум одна из них (C++11): http://devmaster.net/forums/topic/13973-c-template-metaprogramming-brainfck-interpreter/
CU>о сравнении полноты языков программирования
Ну так абстрактная "полнота" и "тьюринг-полнота" это совершенно разные вещи
Язык может состоять из пары-тройки символов и быть абсолютно бесполезным, но быть тьюринг-полным. А может быть объёмным и навороченным языком запросов к БД и не быть тьюринг-полным (SQL (был таким, как минимум — сейчас не знаю)).
На самом деле, если дать шаблонам C++ бесконечную память (см. машину Тьюринга) и (сверх)высокую производительность, на них можно построить виртуальную машину, где будет работать ОС, "читать"-"писать" свои виртуальные файлы, общаться с виртуальной клавиатурой и т.п. Это утверждение применимо и для brainfuck'а.
CU>и команд как таковых нет.
Да есть они.
Здравствуйте, Alexey F, Вы писали:
AF>Здравствуйте, CodingUnit, Вы писали:
CU>>Смотря что понимать под множеством выполнимых функций, если мы говорим о сравнении полноты языков программирования, то шаблоны вряд ли можно назвать полным формализмом. И ОС на нем не запустить, и команд как таковых нет. AF>Для тьюринг-полноты достаточно команд brainfuck'а, а реализация brainfuck на шаблонах C++ имеется Ввод/вывод, конечно, неинтерактивный, иногда в реализациях для простоты убирают ввод. AF>Вот минимум одна из них (C++11): AF>http://devmaster.net/forums/topic/13973-c-template-metaprogramming-brainfck-interpreter/
AF>На самом деле, если дать шаблонам C++ бесконечную память (см. машину Тьюринга) и (сверх)высокую производительность, на них можно построить виртуальную машину, где будет работать ОС, "читать"-"писать" свои виртуальные файлы, общаться с виртуальной клавиатурой и т.п. Это утверждение применимо и для brainfuck'а.
Это уже все же мечты, реально же вряд ли кто то будет строить и запускать такие виртуальные машины. Как расширение системы типов С++ шаблоны годятся, и в свое время пригодились, на некоторых платформах лучше ничего и не найти, но когда возможны более удобные системы метапрограммирования, намеренно их использовать это уже не лучшее решение.
Здравствуйте, CodingUnit, Вы писали:
CU>Это уже все же мечты, реально же вряд ли кто то будет строить и запускать такие виртуальные машины.
Тем не менее, это возможно. Вообще, мы и все, кто будет читать топик, уже поняли, что там было с определением тьюринг-полноты, поэтому вопрос исчерпан . С меня балансировка дерева и ещё что-то, что Вы просили в одном из сообщений.
CU>Как расширение системы типов С++ шаблоны годятся, и в свое время пригодились, на некоторых платформах лучше ничего и не найти, но когда возможны более удобные системы метапрограммирования, намеренно их использовать это уже не лучшее решение.
+1 Если бы в C++ или хотя бы для native было доступно лучшее решение в своё время, шаблоны никто даже не додумался бы копать.
CU>Смотря что понимать под множеством выполнимых функций, если мы говорим о сравнении полноты языков программирования, то шаблоны вряд ли можно назвать полным формализмом. И ОС на нем не запустить, и команд как таковых нет.
Я никак не пойму, почему надо проводить резкую границу, если можно все рассматривать в рамках одного формализма,
макроса, который принимает и типы в качестве аргументов. что тут военного?
мне только не хватает возможности, чтобы такой макрос мог читать определение как traits.
Здравствуйте, Alexey F, Вы писали:
AF>Язык может состоять из пары-тройки символов и быть абсолютно бесполезным, но быть тьюринг-полным. А может быть объёмным и навороченным языком запросов к БД и не быть тьюринг-полным (SQL (был таким, как минимум — сейчас не знаю)).
в диалектах, поддерживающих рекурсивные запросы(Oracle, MSSQL, Firebird) — тьюринг-полон