Настроение: | calm |
Музыка: | Legowelt -- Strada 83 |
Type Refinements for the Working Class
Есть два мотива: синенький и рыженький.
Рыженькие определения вычислимости основаны на языке (или лучше сказать на понятиях выражения, переменной, подстановки и сокращений), а синенькие -- на понятии машины. Рыженькие языки программирования -- это те, семантику (или большую ее часть) которых можно объяснить в терминах самого языка, а для объяснения семантики синеньких нужно вводить дополнительные сущности (типа нельзя объяснить программу на Си, не упоминая о том, что есть машина, на которой она выполняется). Рыженькие конструктивные объекты -- это корневые деревья (as in abstract syntax tree), а синенькие -- это простые неориентированные графы. В пользу последнего говорит многое. Например, наименее уродливые программы на рыженьких языках для неориентированных графов в первую очередь строят дерево его обхода, а потом уже делают рекурсию по этому дереву.
Что касается комбинаторных объектов, то тут... часть записи утеряна... переписать как рыженький.
Иллюстрация ко всему вышесказанному: