find free variables in lambda expression

Question

Does anyone know how I can figure out the free variables in a lambda expression? Free variables are the variables that aren't part of the lambda parameters.

My current method (which is getting me nowhere) is to simply use car and cdr to go through the expression. My main problem is figuring out if a value is a variable or if it's one of the scheme primitives. Is there a way to test if something evaluates to one of scheme's built-in functions? For example:

(is-scheme-primitive? 'and)
;Value: #t

I'm using MIT scheme.

Answer 1

[EDIT 4] Disclaimer; or, looking back a year later:

This is actually a really bad way to go about solving this problem. It works as a very quick and dirty method that accomplishes the basic goal of the OP, but does not stand up to any 'real life' use cases. Please see the discussion in the comments on this answer as well as the other answer to see why.

[/EDIT]

This solution is probably less than ideal, but it will work for any lambda form you want to give it in the REPL environment of mit-scheme (see edits). Documentation for the procedures I used is found at the mit.edu doc site. get-vars takes a quoted lambda and returns a list of pairs. The first element of each pair is the symbol and the second is the value returned by environment-reference-type.

(define (flatten lst)
  (cond ((null? lst) ())
        ((pair? (car lst)) (append (flatten (car lst)) (flatten (cdr lst))))
        (else
          (cons (car lst) (flatten (cdr lst))))))

(define (get-free-vars proc-form)
  (let ((env (ge (eval proc-form user-initial-environment))))
    (let loop ((pf (flatten proc-form))
               (out ()))
      (cond ((null? pf) out)
            ((symbol? (car pf))
             (loop (cdr pf) (cons (cons (car pf) (environment-reference-type env (car pf))) out)))
            (else
              (loop (cdr pf) out))))))

EDIT: Example usage:

(define a 100)

(get-vars '(lambda (x) (* x a g)))
 => ((g . unbound) (a . normal) (x . unbound) (* . normal) (x . unbound) (lambda . macro))

EDIT 2: Changed code to guard agains calling environment-reference-type being called with something other than a symbol.

EDIT 3: As Sam has pointed out in the comments, this will not see the symbols bound in a let under the lambda as having any value.. not sure there is an easy fix for this. So, my statement about this taking any lambda is wrong, and should have read more like "Any simple lambda that doesn't contain new binding forms"... oh well.

Answer 2

For arbitrary MIT Scheme programs, there isn't any way to do this. One problem is that the function you describe just can't work. For example, this doesn't use the 'scheme primitive' and:

(let ((and 7)) (+ and 1))

but it certainly uses the symbol 'and.

Another problem is that lots of things, like and, are special forms that are implemented with macros. You need to know what all of the macros in your program expand into to figure out even what variables are used in your program.

To make this work, you need to restrict the set of programs that you accept as input. The best choice is to restrict it to "fully expanded" programs. In other words, you want to make sure that there aren't any uses of macros left in the input to your free-variables function.

To do this, you can use the expand function provided by many Scheme systems. Unfortunately, from the online documentation, it doesn't look like MIT Scheme provides this function. If you're able to use a different system, Racket provides the expand function as well as local-expand which works correctly inside macros.

Racket actually also provides an implementation of the free-variables function that you ask for, which, as I described, requires fully expanded programs as input (such as the output of expand or local-expand). You can see the source code as well.

For a detailed discussion of the issues involved with full expansion of source code, see this upcoming paper by Flatt, Culpepper, Darais and Findler.