Overhead of call-by-need / call-by-name Lisp interpreter strategy

Question

I've a partially finished interpreter for a lexically scoped 'pure Lisp' (no set!) that uses a call-by-need evaluation model which comes down to call-by-name with simple caching, the interpreter naturally uses an environment-based evaluation model.

The standard way of evaluating lambda abstractions, as in, constructing a new environment from the formal paramatres and the environment in which the abstraction is evaluated and simply placing the evaluations of the arguments in their own environment in it. Then evaluate the body of the abstraction in the new environment wouldn't work because it would mean a call-by-value semantics.

My solution to this problem was replacing where required the idea of 'environments' with 'lookup functions', which just take a symbol as argument, and produce an associated datum. Which can easily be made from an environment. Lambda-applications are just done by evaluating the body again with a lookup function which is made from both the environment in which the definition lies, and in which the argument lie. Which evaluates them lazily and only when required.

What I wonder though is what the overhead from this model is, how expensive is it to generate these lookups for every application, the code for these lookups is pretty large. I know that lambda application and creation in Scheme is fairly cheap and many sources advocate using them extensively to maintain the readability of code even though in a lot of cases they would have a slight overhead. But as lambda-applications are ubiquitous in any lisp, I wonder just how much performance could be saved from using a potentially different model. I tried searching this on google but all the models for call-by-need interpreters I found were even more awkward, but often so to accommodate for set!.

Some relevant pieces of my code:

The evaluator that uses the lookup function:

; 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

And the function that generates the more advanced lookups. This especially is what worries me, though it's tail-recursive and uses very cheap eq? and null? comparisons, it doesn't look as efficient as simply using assq on an environment list, and some times even the lack of random access on those worries me a bit.

; 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

It should be apparent that the evaluator works by a simple term-reduction system that when evaluating expressions in a list simply replaces them with their result, quoting them whenever the result is not considered self-evaluating. Which is possible because it's a purely functional lisp. It also captures caching and most of the garbage collection in one go.

I should add that one of the things I always had very poor conception of is overhead and complexity theory. For those that say 'If you want performance, why are you making your interpreter in Lisp?', it's only a test of the general structure to see if it works, I'll be re-writing it in C-- soon enough.

Ah, I couldn't even submit this at first because the tag 'call-by-need' doesn't already exist, promising start.

Answer 1

Another thing that 'you' might do is simply mark every single datum with an environment on its own that can be retrieved from it in the data structure, it may seem exhaustive but in the end all that needs to be marked come to think of it are lists and a very special case that the body of the lambda abstraction contains only one symbol. For other data in 'your' model its evaluation is irrespective from its environment.

This also solves a major problem with lazy cons cells and lists that are just passed around to other places in the programme.

So assuming a list itself is marked with an environment, you can just extract the environment whenever you evaluate it.