Сразу оговорюсь, что я считаю схему

Автор: VladD2
Дата: 21.05.11

предложенную Владом неадекватно переусложненной и крайне не гибкой.
Поэтому я не буду делить AST на AST, SST, TSST, TAST.
У меня будет AST это то что выдает парсер и TAST это то что получается при типизации AST.

Для того чтобы сделать простой в использовании, расширяемый и быстрый типизатор нужно создать язык описания типизатора.
Язык нужен для того чтобы очистить модель типизатора от деталей реализации. Библиотека на это не способна.

Для того чтобы сделать типизатор нам нужно формализовать 3 вещи:
1)Описание структуры типа.
Даже в немерле понадобятся как минимум две группы типов с разной структурой.
Типы выражений.
Типы паттернов.
Про пользовательские языки типа ПЕГ я вообще молчу. Там типы совсем другими получаются.
Можно конечно попытаться их унифицировать, но код типизации сразу обрастет костылями, которые разбираются где какой тип. Короче динамическая типизация во всей красе.

Также нужно не забыть про "многослойные" системы типов.
Это нужно, например для:
http://scholar.google.com/scholar?q=type+refinements+programming

Вывод типов производится в два этапа.
Сначала выводятся основные типы.
Потом "рафинированные".

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

Требование объявления перед использованием решается заведением новой области видимости при объявлении переменной.

б) Доступ к члену объекта/пространства имен/...

3)Собственно язык описания правил вывода типов.
Мои мысли в данный момент крутяться вокруг Mercury.
Несколько упрощенный Mercury будет отличной основой для создания языка описания типизации.
Я выбрал Mercury ибо типизация это поиск с откатами. Как раз то вокруг чего построен этот язык.
Пролог пошёл лесом, ибо Mercury это пролог сделанный правильно.

Примеры пойдут ответами на это сообщение.