Русскоязычное программирование

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Русскоязычное программирование » базовые определения » Денотационная семантика vs операционная семантика


Денотационная семантика vs операционная семантика

Сообщений 1 страница 3 из 3

1

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

Программа — это, прежде всего, функция, преобразующая входные данные в выходные. В этом случае не требуется сложная машина: математика веками оттачивала такой способ «исполнения программ», называя его «применением функций». Таким образом, идея состоит в том, чтобы преобразовать программу в функцию (из определённого множества функций). Подобная функция называется денотацией программы. Теперь остаётся только определить вышеупомянутое множество.
Если в качестве такой теории взять какую-нибудь простую, всем понятную концепцию, то можно избавиться от поддержки зоопарка всевозможных машин. Для наших целей прекрасно подойдёт λ-исчисление. Его аксиомы настолько просты, что их толкование не вызывает никаких разногласий. Таким образом, семантику языка программирования можно понимать как способ перевода программ в соответствующие денотации. Этот процесс, между прочим, тоже можно представить как функцию.

[html]<a href="http://ilammy.github.io/lisp/ch05_denotational_semantics.html">http://ilammy.github.io/lisp/ch05_denotational_semantics.html</a>[/html]

Отредактировано Лис (2018-02-04 09:54:39)

0

2

Еще раз - описание языков программирования с помощью лямбд это недосягаемая высота для среднестатистического программиста. От слова совсем. Я Вам уже приводил пример факториала. В качестве машинных преобразований может быть. Для восприятия человеком забудьте. Вы изобретаете Хаскел, для которого, кстати говоря, сами авторы языка не удосужились составить полноценное описание в любой из нотаций. Можно конечно защитить какую-нибудь кандидатскую на этой теме, но на практике не взлетит. Уже много раз обмусолили почему это так. Главная претензия - зачем использовать инструмент, который не для этого, как обычно не закрыт.
Те же самые проблемы с формальной теорией вычислений под конкретную машину. Это пупец как не понятно для тех, кто не создавал машину. Ну для примера - чтобы пользоваться телевизором, Вы предлагаете каждому покупателю знать как он работает, учить схемы, стандарты и пр. Формальная теория вычислений это здорово когда у Вас архитектуры всего две CISC и RISC под 3,5 типа данных, укладываемых в исторические процессорные типы. Здоров так можно описать .Net, например. Описать так какой-нибудь SQL или ПРОЛОГ или РЕФАЛ это пупец как интересно. Я уже молчу об автоматическом символическом выводе типов. Написать такую теорию вычислений в которую будет укладываться все это вместе, это даже переплюнуть лямбды.
В итоге воз и ныне там и решения нет. Поэтому для того чтобы понять что пишет будден, павия или я, нужно сидеть и вдумчиво ковырять мануалы. А выразить все в единой понятной для простого смертного форме пока большая нерешенная проблема.

Его аксиомы настолько просты, что их толкование не вызывает никаких разногласий.

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

𝓔[[ν]]=λρκσ.(κ (σ (ρ ν)) σ)

Получение значения переменной. Мне одному кажется что египетские иероглифы читаются лучше?
Самое главный Ваш изъян - выбор лямбд в качестве описания языков программирования ничем не обоснован. Ни одни автор (включая и автора по ссылке) не говорит, что лямбды лучше остальных вариантов, потому то и потому. Он просто берет известный ему инструмент и использует его для решения своих проблем. Решение вопроса возникает примерно так:
1) Автор знает лямбда исчисление по умолчанию.
2) Автор выбирает среди известных ему инструментов, если их нет, он строит модель с использованием известных ему инструментов
3) Автор использует пункт 2 для профита.
Базовым принципом является начальное знание п.1. Если бы автор не был посвящен в лямбда исчисления, выбрал ли он его для своей работы? Большой вопрос на самом деле - начал ли он его изучать для этих целей или взял бы нечто иное. Ведь для этого нужно проводить сравнительный анализ инструментов (и он бы его провел, не сомневаюсь, что это проще чем учить новый матан в виде лямбда).

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

Отредактировано utkin (2018-02-05 10:16:51)

0

3

Ни одни автор (включая и автора по ссылке) не говорит, что лямбды лучше остальных вариантов, потому то и потому. Он просто берет известный ему инструмент и использует его для решения своих проблем. Решение вопроса возникает примерно так:
1) Автор знает лямбда исчисление по умолчанию.
2) Автор выбирает среди известных ему инструментов, если их нет, он строит модель с использованием известных ему инструментов
3) Автор использует пункт 2 для профита.
Базовым принципом является начальное знание п.1. Если бы автор не был посвящен в лямбда исчисления, выбрал ли он его для своей работы? Большой вопрос на самом деле - начал ли он его изучать для этих целей или взял бы нечто иное. Ведь для этого нужно проводить сравнительный анализ инструментов (и он бы его провел, не сомневаюсь, что это проще чем учить новый матан в виде лямбда).

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

Лис написал(а):

Его аксиомы настолько просты, что их толкование не вызывает никаких разногласий.

Или не вызывает разногласий, потому что число понимающих/использующих его настолько мало, что гораздо вероятнее.
Берём пример Уткина с факториалом:
Разворачиваем в дерево.
Перенумеруем имена в порядке упоминания.
Видим полное незнакомство с ЕСКД виетоватое непонимание того, что в нумерации пунктов алгоритма таки должен быть порядок.
В качестве развлечения я предлагаю по той записи восстановить само исчисление или хотя бы упорядоченную перенумерацию (можно и альтернативную), используя лишь знание о том, что это факториал.

Отредактировано MihalNik (2018-02-05 17:41:23)

0


Вы здесь » Русскоязычное программирование » базовые определения » Денотационная семантика vs операционная семантика