Языки программирования, в частности, ориентированы на их семантику.
Я изучил несколько частей теории категорий. Это, безусловно, другой взгляд на вещи. (Очень грубое резюме для тех, кто этого не видел: теория категорий дает способы выражения всех видов математического поведения исключительно в терминах функциональных отношений между объектами. Например, такие вещи,...
Иногда математики беспокоятся об аксиоме выбора (AC) и аксиоме детерминированности (AD). Аксиома выбора : При любом наборе непустых множеств существует функция F , что, учитывая множество S в C , возвращает элемент из S .СC{\cal C}еffSSSСC{\cal C}SSS Аксиома детерминированности : Пусть - набор...
Функциональное программирование имеет теоретическую основу в лямбда-исчислении и комбинаторной логике . Как человек, занимающийся статистическими вычислениями, я нахожу эти концепции очень полезными для моделирования. Существует ли эквивалентная математическая основа императивного программирования...
В другом потоке Андрей Бауэр определил денотационную семантику как: значение программы является функцией значений ее частей. Что беспокоит меня в этом определении, так это то, что оно, кажется, не выделяет то, что обычно считается денотационной семантикой, из того, что принято считать...
Есть ли какие-либо преимущества в расчете временной сложности алгоритма с использованием лямбда-исчисления? Или есть другая система, разработанная для этой цели? Любые ссылки будут...
Постоянно растущая сложность компьютерных программ и все более важное положение, которое компьютеры занимают в нашем обществе, заставляют меня задуматься, почему мы до сих пор не используем все вместе языки программирования, на которых вам необходимо предоставить формальное доказательство...
Спросите даже кого-то, имеющего опыт работы в области компьютерных наук, что такое регулярное выражение, и ответ, вероятно, выйдет за пределы возможности быть в пределах досягаемости конечного автомата. Например, «регулярное выражение» /^1?$|^(11+?)\1+$/ созданная известной личностью Perl Абигейл...
Большинство известных алгоритмов первого порядка в том смысле, что их ввод и вывод являются «простыми» данными. Некоторые из них являются вторым порядком тривиальным способом, например, сортировка, хеш-таблицы или функции map и fold: они параметризуются функцией, но на самом деле они не делают с...
Я не думаю, что понимаю классы типов. Я где-то читал, что думать о классах типов как о «интерфейсах» (из ОО), которые реализует тип, неправильно и вводит в заблуждение. Проблема в том, что я испытываю проблемы, видя их как нечто иное, и как это неправильно. Например, если у меня есть класс типов (в...
Невозможно написать язык программирования, который позволяет всем машинам, которые останавливаются на всех входах, и никаким другим. Тем не менее, кажется, что легко определить такой язык программирования для любого стандартного класса сложности. В частности, мы можем определить язык, на котором мы...
В духе некоторых общих дискуссий, подобных этой , я открываю эту ветку с намерением собрать мнения о том, какие открытые проблемы и актуальные темы в исследованиях по языкам программирования . Я надеюсь, что обсуждение может даже привести к поверхностному мнению относительно будущего исследований в...
Я читал несколько статей о зависимых типах и контрактах программирования. Из большей части того, что я прочитал, кажется, что контракты - это динамически проверяемые ограничения, а зависимые типы проверяются статически. Были некоторые бумаги, которые заставили меня думать, что возможно иметь...
Я читал « Семантику с приложениями » от Nielson & Nielson , и мне очень нравится эта тема. Я хотел бы иметь еще одну книгу по семантике языка программирования - но я действительно могу получить только одну. Я взглянул на книгу « Турбак / Гиффорд» , но она слишком многословна; Я думал, что с...
Существуют ли (функциональные?) Языки программирования, в которых все функции имеют каноническую форму? То есть любые две функции, которые возвращают одинаковые значения для всего набора ввода, представляются одинаково, например, если f (x) вернул x + 1, а g (x) вернул x + 2, то f (f (x )) и g (x)...
Я новичок, работающий над методами, доказывающими эквивалентность программы. Я прочитал несколько статей об определении логических отношений или симуляций, чтобы доказать, что две программы эквивалентны. Но я совершенно запутался в этих двух методах. Я только знаю, что логические отношения...
Это дополнительный вопрос к В чем разница между доказательствами и программами (или между предложениями и типами)? Какая программа будет соответствовать неконструктивному (классическому) доказательству вида ? (Предположим, что является интересным разрешимым отношением, например, тая TM не...
Если мы пойдем по книге (или любой другой версии спецификации языка, если вы предпочитаете), сколько вычислительной мощности может иметь реализация C? Обратите внимание, что «реализация C» имеет техническое значение: это конкретный экземпляр спецификации языка программирования C, в котором...
Я недавно изучаю Хаскель и языки программирования. Может ли кто-нибудь порекомендовать несколько книг по теории
В качестве стороннего проекта я пишу язык с использованием Python. Я начал с использования клона flex / bison под названием Ply, но столкнулся с трудностями, которые я могу выразить с помощью этого стиля грамматики, и мне не интересно взламывать свой язык из-за несоответствия импеданса с...
Меня интересует, почему натуральные числа так любимы авторами книг по теории языков программирования и теории типов (например, Дж. Митчелл, Основы языков программирования и Б. Пирс, Типы и языки программирования). Описание простейшего лямбда-исчисления и, в частности, языка программирования PCF...