У меня есть частично законченный интерпретатор для лексически ограниченного по объему 'чистого Lisp' (нет set!
) это использует модель оценки вызова по необходимости, которая сводится к вызову по имени с простым кэшированием, интерпретатор естественно использует основанную на среде модель оценки.
Стандартный способ оценить абстракции лямбды, как в, создавая новую среду из формальных параметров и среду, в которой абстракция оценена и просто размещение оценок аргументов в их собственной среде в нем. Затем оцените орган по абстракции в новой среде, не работал бы, потому что это будет означать семантику вызова по значению.
Мое решение этой проблемы заменяло при необходимости идею 'сред' с 'функциями поиска', которые просто берут символ в качестве аргумента и производят связанную данную величину. Который может легко быть сделан из среды. Приложения лямбды просто сделаны путем оценки тела снова с функцией поиска, которая сделана и из среды, в которой определение находится, и в котором аргумент лежат. Который оценивает их лениво и только при необходимости.
Что интересно, хотя, каковы издержки из этой модели, насколько дорогой это для генерации этих поисков для каждого приложения, код для этих поисков является довольно большим. Я знаю, что приложение лямбды и создание в Схеме являются довольно дешевыми, и много источников рекомендуют использовать их экстенсивно для поддержания удобочитаемости кода даже при том, что в большом количестве случаев у них были бы небольшие издержки. Но поскольку приложения лямбды повсеместны в любой шепелявости, интересно, сколько производительности могло быть сохранено от использования потенциально другой модели. Я пытался искать это на 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
Должно быть очевидно, что средство анализа работает простой системой сокращения термина, которая при оценке выражений в списке просто заменяет их их результатом, заключая им в кавычки каждый раз, когда результат не рассматривают, самооценивая. Который возможен, потому что это - чисто функциональная шепелявость. Это также получает кэширование и большую часть сборки "мусора" сразу.
Я должен добавить, что одна из вещей, из которых у меня всегда была очень плохая концепция, является служебной и теория сложности. Для тех, которые говорят, 'Если Вы хотите производительность, почему Вы делаете свой интерпретатор в Lisp?', это - только тест общей структуры, чтобы видеть, работает ли это, я буду переписывать его в C - достаточно скоро.
А-ч, я не мог даже отправить это сначала, потому что тег 'вызов по необходимости' уже не существует, многообещающий запуск.
Еще одна вещь, которую «вы» можете сделать, - это просто пометить каждую единичную базу данных отдельной средой, которая может быть извлечена из нее в структуре данных, это может показаться исчерпывающим, но, в конце концов, все Если подумать, нужно отметить списки и очень частный случай, когда тело лямбда-абстракции содержит только один символ. Для других данных в «вашей» модели его оценка не зависит от среды.
Это также решает главную проблему с ленивыми cons-ячейками и списками, которые просто передаются в другие места в программе.
Предполагая, что список сам по себе отмечен окружением, вы можете просто извлекать окружение всякий раз, когда вы его оцениваете.