У меня есть частично законченный интерпретатор для лексически ограниченного «чистого Лиспа» (нет 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 - достаточно скоро.
Поначалу я даже не мог отправить это, потому что тег 'call-by-need' еще не существует, многообещающее начало.