Я столкнулся со странной проблемой при написании интерпретатора, который (должен) подключаться к внешним программам / функциям: функции в «C» и «C ++» не могут перехватывать переменные функции , например, я не могу создать функцию, которая вызывает «printf» с точно такими же аргументами, которые он получил, и вместо этого должен вызвать альтернативную версию, которая принимает объект с переменным числом аргументов. Это очень проблематично, так как я хочу иметь возможность создавать объект, который содержит анонимный хук.

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

Полные языки Тьюринга могут вычислять один и тот же набор функций , который представляет собой набор общих рекурсивных частичных функций. Вот и все.$\mathbb{N}^k \rightarrow \mathbb{N}$

Это ничего не говорит о языковых особенностях. Машина Тьюринга имеет очень ограниченные композиционные особенности. Нетипизированный -calculus гораздо более композиционный, но в нем отсутствуют многие функции, обычно встречающиеся в современных языках.$\lambda$

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

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

Полнота и языковая выразительность Тьюринга - это два разных понятия.

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

Это, однако, не говорит о том, насколько это удобно. Некоторые функции, которые просты в некоторых языках, могут быть очень трудными в других из-за выбора дизайна. Полнота Тьюринга просто говорит о том, что вы можете делать вычисления. В качестве крайнего примера, может быть трудно перехватить varadic функции в C ++, но можно написать интерпретатор JavaScript в C ++, который может перехватывать функции variadic.

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

Что касается вашего конкретного примера, когда разрабатывался C, он был разработан так, чтобы работать очень близко к тому, как работали языки ассемблера того времени. Функции Variadic просто помещают аргументы в стек с минимальной безопасностью типов. Реализация этих переменных функций была оставлена ​​на усмотрение компилятора, чтобы обеспечить максимальную переносимость. Соответственно, было сделано очень мало предположений о возможностях аппаратного обеспечения. К тому времени, когда появился JavaScript, сцена изменилась. Он уже работает на виртуальной машине как интерпретируемый язык, поэтому баланс смещается в сторону удобства. Разрешение перехвата переменных функций становится разумным. Даже в случае JavaScript, который компилируется как раз вовремя, наши компиляторы готовы хранить гораздо больше дополнительной информации об аргументах, чем те, что были готовы компиляторами C ранее.

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

Полнота Тьюринга говорит, что «этот автомобиль может ездить везде, где может идти любой другой автомобиль». То есть вы можете вычислить все те же функции. Вход на выход, начало до конца.

Но это утверждение ничего не говорит о том, как вы туда попали. Это может быть на рельсах, это может быть на дорогах, это может быть в воздухе. Точно так же Turing Completeness ничего не говорит о том, как вы вычисляете функцию. Вы можете использовать рекурсию, итерацию или какие-то странные клеточные автоматы. Вы можете использовать типы или нет, вы можете использовать динамические или статические методы. Но если все, что вы считаете, это функции (или наборы / формальные языки), которые вы можете вычислять, пока вы выполняете Turing Complete, эти функции дают вам одинаковую мощность.

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

Вычислительная мощность

Вычислительная мощность относится к тому , какие проблемы языка можно вычислить. Наиболее известным классом вычислительной мощности является тот, который эквивалентен универсальной машине Тьюринга . Существует множество других систем вычислений, таких как машины произвольного доступа , λ-исчисление , комбинаторное исчисление SK , µ-рекурсивные функции , WHILEпрограммы и многие другие. И, как выясняется, все они могут имитировать друг друга, что означает, что все они имеют одинаковую вычислительную мощность.

Это порождает тезис Черч-Тьюринга (названный в честь Алонзо Черча, который создал λ-исчисление, и Алана Тьюринга, который создал Универсальную Машину Тьюринга). Тезис Черча-Тьюринга является гипотезой вычислимости с двумя аспектами:

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

Второе, однако, более важно в области философии сознания, чем информатика.

Однако есть две вещи, о которых не говорит Тезис Черча-Тьюринга , которые очень актуальны для вашего вопроса:

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

Простой пример для (1): на компьютере с произвольным доступом копирование массива занимает время, пропорциональное длине массива. Однако на машине Тьюринга это занимает время, пропорциональное квадрату длины массива, поскольку машина Тьюринга не имеет произвольного доступа к памяти, она может перемещаться по ленте только по одной ячейке за раз. Следовательно, необходимо скопировать n элементов массива n раз, чтобы скопировать их. Таким образом, разные модели вычислений могут иметь разные характеристики производительности даже в асимптотическом случае, когда мы пытаемся абстрагироваться от деталей реализации.

Примеров (2) предостаточно: и λ-исчисление, и Python полны по Тьюрингу. Но вы бы предпочли написать программу на Python или в λ-исчислении?

Есть еще одна третья морщина, которую я обходил до сих пор: все эти оригинальные системы были разработаны логиками, философами или математиками, а не учеными-компьютерщиками ... просто потому, что компьютеров и, следовательно, компьютерных наук не было. Все это восходит к началу 1930-х годов, даже до самых первых экспериментов Конрада Цузе (которые в любом случае не были программируемыми и / или не завершенными по Тьюрингу). Они говорят только о «вычислимых функциях на натуральных числах».

Теперь, как выясняется, можно многое выразить в виде функций на натуральных числах - в конце концов, наши современные компьютеры даже обходятся намного меньше (в основном 3-4 функции для чисел 0 и 1, и все) ), но, например, какую функцию выполняет операционная система?

Это понятие I / O, побочных эффектов, взаимодействующих с окружающей средой, не охвачено идеей «функций над натуральными числами». И тем не менее, это своего рода важно, поскольку, как Саймон Пейтон Джонс однажды выразился «Все чисто функции без каких - либо побочных эффектов делает, сделайте ваш процессор горячим» , к которому член аудитории ответили « на самом деле, что является побочным -эффект тоже!

Эдвин Брэди , дизайнер Idris , (только половина) в шутку использует (я не знаю, изобрел ли он его) термин «Tetris-complete», чтобы выразить эту разницу между «может вычислять любую вычислимую функцию на натуральных числах» и «может использоваться для написания нетривиальных программ, взаимодействующих со средой ". Еще более иронично, он демонстрирует это, внедрив клон Космических захватчиков в Идрисе , но он говорит, что уверен, что Тетрис превращается в Космических захватчиков.

Еще одна вещь, на которую следует обратить внимание, заключается в том, что не только эквивалентности по Тьюрингу не обязательно достаточно для того, чтобы говорить о написании «полезных» программ, но и, возможно, OTOH даже не является необходимым . Например, SQL стал эквивалентным по Тьюрингу только с ANSI SQL: 1999 , но до этого он все еще был полезен. На самом деле, некоторые могут возразить, что создание его эквивалентного по Тьюрингу вовсе не увеличило его полезность. Существует много доменных языков, которые не эквивалентны по Тьюрингу. Язык описания данных обычно нет (и не должен быть). Очевидно, что Total Languages ​​не может быть эквивалентным по Тьюрингу, но вы все равно можете записывать в них циклы событий, веб-серверы или операционные системы. Есть также языки, которые эквивалентны по Тьюрингу, но где это фактически считается ошибкой.

В общем, эквивалентность по Тьюрингу не очень интересна, если только вы не хотите статически анализировать программы.

Выразительность

Если предположить, что наша вычислительная система достаточно мощна в вычислительном отношении, чтобы вообще решить нашу проблему, то, что нам нужно сделать дальше, - это выразить наш алгоритм для решения этой проблемы в некоторой формальной записи для этой системы. Другими словами: нам нужно написать программу на каком-нибудь компьютерном языке. Вот где приходит понятие выразительности .

По сути, это означает, насколько «легко» или «приятно» писать нашу программу на нашем конкретном языке программирования. Как видите, это понятие довольно размытое, субъективное и скорее психологическое, чем техническое.

Однако есть попытки более точных определений. Самым известным (и самым строгим из известных мне) является Матиас Феллайзен в своей статье « О выразительной силе языков программирования» (первые две страницы содержат мягкое введение, остальная часть статьи более мясистая).

Основная интуиция заключается в следующем: при переводе программы с языка на другой язык некоторые из изменений, которые вам нужно сделать, содержатся локально (например, превращение FORциклов в WHILEциклы или циклов в условные GOTOs), а некоторые требуют изменения глобального Структура программы.

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

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

Обратите внимание, что это дает объективно измеримое определение выразительности. Также обратите внимание, что это понятие зависит от контекста и является сравнительным. Таким образом, если каждая программа на языке A может быть переведена на язык B только с локальными изменениями, и есть хотя бы одна программа на языке B, которая не может быть переведена на A только локальными изменениями, то язык B строго более выразителен, чем язык, Однако более вероятный сценарий состоит в том, что многие программы на обоих языках можно переводить туда и обратно, но есть некоторые программы на обоих языках, которые нельзя перевести на другой. Это означает, что ни один язык не является строго более выразительным, чем другой, они просто имеют разные функции, которые позволяют различным программам выражаться по-разному.

Это дает формальное определение того, что значит быть «более выразительным», но все же не отражает психологические понятия, лежащие в основе этого явления. Например, синтаксический сахар, согласно этой модели, не увеличивает выразительную силу языка, потому что он может быть переведен с использованием только локальных изменений. Тем не менее, мы знаем из опыта , что наличие FOR, WHILEи IFдоступно, даже если они просто синтаксический сахар для условных GOTOмоделей выражения нашего намерения легче .

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

Пример, который я нашел в теге Ruby на StackOverflow: многие пользователи, которые следуют тегу Ruby, утверждают, что циклы легче понять, чем рекурсию, и рекурсия предназначена только для опытных функциональных программистов, а циклы более интуитивны для новичков, но я видел несколько случаев полные новички, которые интуитивно пишут такой код:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Что обычно приводит к тому, что несколько человек комментируют, что «это не работает» и «они делают это неправильно», а «правильный путь» таков:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

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

Резюме

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

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

Означает ли это, что класс проблем, которые каждый язык программирования может решать, зависит от языка, хотя все эти языки завершены?

Да.

1. Существуют проблемы, которые не охватываются термином «полный Тьюринг» (который касается только вычислительных функций на натуральных числах), например печать на экран. Два языка могут быть полными по Тьюрингу, но один может разрешить печать на экране, а другой - нет.
2. Даже если оба языка могут решать одни и те же проблемы, это ничего не говорит о том, насколько сложна кодировка и насколько легко выразить эту кодировку. Например, C может решить любую проблему, которую может Haskell, просто написав интерпретатор Haskell на C ... но сначала вы должны написать интерпретатор Haskell, чтобы решить проблему таким образом!

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

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

Некоторые из них могут представлять интерес:

• Компилятор исходного кода в Википедии

• О важности полноты по Тьюрингу на лямбда-пределе

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

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

Вот некоторые примеры:

• Если у вас нет перечислений, вы можете использовать целые числа.
• Если у вас нет буферов, которые знают их размер, вы можете создать тип, который содержит размер, и буфер, который не знает его размер.
• Если у вас нет проверки границ буферов, вы можете просто проверять индекс каждый раз, когда используете их.
• Если у вас нет функций с переменными числами, вы можете создать функцию, которая будет принимать буфер, который знает его размер, и считывать из этого буфера ту же информацию, которую вы получите из формальных аргументов.
• Если у вас нет операторов, вы можете использовать функции.
• Если у вас нет типов, которые могут наследовать друг друга, вы можете создавать типы, которые содержат друг друга, и обращаться к ним через дополнительный уровень косвенности, при этом подтип - это просто преобразование типа handle-to-the-all-type в ручка-к-содержащемуся типа.
• Если у вас нет делегатов, но есть указатели на функции, вы можете создать тип, который содержит референтный объект и указатель на функцию.
• Если у вас нет делегатов, но у вас есть интерфейсы, вы можете объявить интерфейс, который содержит один метод с нужной вам подписью.
• Если у вас нет универсальных типов, вы можете использовать неуниверсальные типы, которые принимают только верхнюю или нижнюю границы, которые вас интересуют (и, возможно, выполняете соответствующие преобразования в местах использования, чтобы компилятор был доволен).
• Если у вас нет системы линейного / аффинного типа, вы можете просто избегать использования любой переменной более одного раза.
• ...и так далее.

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

Чисто вычислительные вещи были заколочены давным-давно.

Существующие ответы справедливо указывают на то, что полнота по Тьюрингу не является хорошим способом сравнения языков. Действительно, почти все языки являются тьюринговыми. («Если все особенные, то никто не особенный», как говорили «Невероятные».)

Тем не менее, это можно сравнить выразительность языка с математической точностью. Взгляните на книгу Феллайзена « О выразительной силе языков программирования» . Грубо говоря, идея состоит в том, чтобы задать следующий вопрос: Могу ли я преобразовать любую программу на языке A в программу на языке B, внеся только локальные изменения? Другими словами, Феллайзен дает математически точную форму вашей интуиции.

В довершение всех остальных, вот еще одна аналогия.

Для стирки белья нужны три вещи: резервуар для воды, какое-то моющее средство и механизм перемешивания. Это может быть реализовано разными способами. Резервуар для воды - это все, что содержит достаточно воды (например, ванна, озеро, река). Механизм перемешивания может представлять собой механическое устройство, стиральную доску или даже камень, по которому бьют одежду. И моющие средства бывают разных форм тоже.

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

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

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

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

Возьмем, к примеру, язык, который выражает машины Тьюринга. Каждая программа на языке является машиной Тьюринга.

Теперь рассмотрим подъязык всех машин Тьюринга, которые читают и пишут только символы a, b и пробел. Он завершен по Тьюрингу, но не может выразить какие-либо программы, которые, например, выдают c на всех входных данных, потому что он не может писать никаких cs. Он может выражать только все вычислимые функции на входах и выходах, закодированные как строки as и bs.

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