У меня есть частично законченный интерпретатор для «чистого Лиспа» с лексической областью видимости (без set!), который использует модель оценки вызова по необходимости, которая сводится к вызову по имени с простым кэшированием, интерпретатор, естественно, использует основанный на среде модель оценки.
Стандартный способ оценки лямбда-абстракций, например, создание новой среды из формальных параметров и среды, в которой оценивается абстракция, и просто размещение в ней оценок аргументов в их собственной среде. Затем оценить тело абстракции в новой среде не получится, потому что это будет означать семантику вызова по значению.
Мое решение этой проблемы заключалось в замене, где это необходимо, идеи «окружения» «функциями поиска», которые просто принимают символ в качестве аргумента и создают связанные данные. Который можно легко сделать из окружающей среды. Лямбда-приложения просто выполняются путем повторной оценки тела с помощью функции поиска, которая создается как из среды, в которой находится определение, так и из среды, в которой находится аргумент. Который оценивает их лениво и только при необходимости.
Что мне интересно, так это то, каковы накладные расходы этой модели, насколько дорого генерировать эти поиски для каждого приложения, код для этих поисков довольно большой. Я знаю, что применение и создание лямбда-выражений в Scheme довольно дешево, и многие источники выступают за их широкое использование для поддержания удобочитаемости кода, хотя во многих случаях они будут иметь небольшие накладные расходы. Но поскольку лямбда-приложения повсеместно распространены в любом Лиспе, мне интересно, сколько производительности можно было бы сэкономить за счет использования потенциально другой модели. Я попытался найти это в Google, но все модели интерпретаторов вызова по необходимости, которые я нашел, были еще более неудобными, но часто так, чтобы приспособиться к set!.
Некоторые соответствующие фрагменты моего кода:
Оценщик, использующий функцию поиска:
; evaluates a datum using a lookup
; lookup is a function which takes a symbol as an argument and produces the value
; some sorts of more powerful environment
; if lookup is a standard environment, treats it as such
(define (eval-datum! d lookup)
(cond
((quoted? d) (dequote d)) ; if quoted, just dequote
((hastype d symbol-type) ; symbols ...
(if (procedure? lookup) ; checks if it's an environment or a lookup function
(lookup d)
(lookup-symbol d lookup)))
((hastype d pair-type) (eval-pair! d lookup)) ; function application
(else d))) ; rest is considered self-evaluating
И функция, которая генерирует более сложные запросы. Это особенно беспокоит меня, хотя это хвостовая рекурсия и используются очень дешевые сравнения eq? и null?, это выглядит не так эффективно, как простое использование assq в списке окружения, и иногда меня даже беспокоит отсутствие произвольного доступа к этим спискам. немного.
; extends a lookup for use in a lambda abstraction
; the inner environment is where the lambda is defined
; the outer environment where it is applied
; params can be either a pair or a symbol
; params automatically tries to match the argument's pattern
(define (extend-lookup! params args inner-env outer-env)
(lambda (s)
(let checkparams ((params params) (args args))
(cond
((eq? s params) (datum args)) ; for an improper list or a single symbol, simply turn the arglist into an evaluable list
((null? params) (lookup-symbol s inner-env)) ; if the number of paramatres are exhausted, simply use the inner-env
((eq? s (car params)) ; in case of a formal parametre match ...
(refeval! args 0 outer-env)) ; evaluate the needed argument and return it
(else (checkparams (cdr params) (cdr args))))))) ; repeat for the next paramatre
Должно быть очевидно, что оценщик работает по простой системе сокращения терминов, которая при оценке выражений в списке просто заменяет их их результатом, заключая их в кавычки всякий раз, когда результат не считается самооценивающимся. Что возможно, потому что это чисто функциональный лисп. Он также захватывает кэширование и большую часть сбора мусора за один раз.
Должен добавить, что одной из вещей, о которых я всегда плохо представлял, были накладные расходы и теория сложности. Для тех, кто говорит: «Если вам нужна производительность, почему вы делаете свой интерпретатор на Лиспе?», это всего лишь проверка общей структуры, чтобы увидеть, работает ли она, я перепишу ее на C — достаточно скоро.
Ах, я даже не мог сначала отправить это, потому что тег «вызов по необходимости» еще не существует, многообещающее начало.
