Накладные расходы по вызову/по вызову Стратегия интерпретатора Lisp

Question

У меня есть частично завершенный интерпретатор для лексически ограниченной «чистой Лиспы» (нет set!), в которой используется модель оценки по требованию вплоть до вызова по имени с простым кэшированием, интерпретатор, естественно, использует модель оценки на основе среды.

Стандартный способ оценки лямбда-абстракций, как и в случае создания новой среды из формальных параметров и среды, в которой оценивается абстракция, и просто размещения оценок аргументов в их собственной среде. Тогда оценка тела абстракции в новой среде не будет работать, потому что это будет означать семантику по принципу «по вызову».

Мое решение этой проблемы заменяло в случае необходимости идею «среды» с помощью «функций поиска», которые просто принимают символ в качестве аргумента и создают связанную датум. Это легко сделать из среды. Лямбда-приложения просто выполняются путем оценки тела снова с помощью функции поиска, которая создается как из среды, в которой лежит определение, и в которой аргумент лежит. Который оценивает их лениво и только тогда, когда это необходимо.

Что мне интересно, хотя это то, что накладные расходы от этой модели, насколько это дорого, чтобы генерировать эти поисковые запросы для каждого приложения, код для этих поисков довольно большой. Я знаю, что приложение лямбда и создание на Схеме довольно дешево, и многие источники выступают за их использование, чтобы поддерживать читаемость кода, хотя во многих случаях у них были бы небольшие накладные расходы. Но поскольку lambda-приложения повсеместны в любом lisp, мне интересно, сколько производительности можно было бы сэкономить на использовании потенциально другой модели. Я попытался найти это в 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. Он также захватывает кеширование и большую часть мусорной коллекции за один раз.

Я должен добавить, что одна из вещей, которые у меня всегда были очень плохое, - это накладные расходы и теория сложности. Для тех, кто говорит: «Если вы хотите производительность, почему вы делаете свой интерпретатор в Lisp?», Это всего лишь проверка общей структуры, чтобы увидеть, работает ли она, я скоро переписал ее на C--.

А, я не мог даже представить это сначала, потому что тег «по требованию» еще не существует, обещая начать.

Answer 1

Другая вещь, которую вы можете сделать, - это просто отметить каждую отдельную базу данных собственной средой, которая может быть извлечена из нее в структуре данных, это может показаться исчерпывающим, но в конце все, что должно быть отмечено, думать об этом - это списки и очень частный случай, когда тело абстракции лямбды содержит только один символ.Для других данных в «вашей» модели ее оценка не зависит от ее среды.

Это также решает серьезную проблему с ленивыми ячейками cons и списками, которые просто передаются в другие места в программе.

Таким образом, если сам список отмечен средой, вы можете просто извлечь среду, когда вы ее оцениваете.