Let's say I have the lambda calculus extended with set! for assignment.

e ::= x
   |  (lambda x . e)
   |  (e e)
   |  (set! x e)

What I would like to do, is walk through a program in this language, and add an annotation to each lambda expression denoting all of the assigned variables in it.

So for example, we could put it in the following language:

e ::= x
   | (lambda x . ae)
   | (e e)
   | (set! x e)

ae ::= (assigned (x ...) e)

(In this example we could say x ... is a set for constant time access if we would like to.)

The most trivial algorithm which walks down each structure and combines each expression is $O(n^2)$. (Assuming we have constant time set access.)

The algorithm will look something like this:

(define (ae e)
  (match e
    [`(lambda (,x) ,e)
     (define-values (e* a) (ae e))
      (values `(lambda (,x) (assigned ,a ,e*))
              (set-remove a x))]
    [`(,e1 ,e2)
     (define-values (e1* a1) (ae e1))
     (define-values (e2* a2) (ae e2))
     (values `(,e1 ,e2)
             (set-union a1 a2))]
    [`(set! ,x ,e)
      (define-values (e* a) (ae e))
      (values `(set! ,x ,e)
              (set-add a x))]
     (values x (set x))]))

(I did take some liberties in this algorithm because having an immutable set means it will be $O(log(n))$, rather than $O(1)$, but that is easily fixable by using a mutable set and adding and removing the elements at the start and end of the recursion.

The problem here is the set-union, which, at best, can be $O(log(n))$ (sure, there are some representations that are $O(1)$, but those representations, as far as I know, do not also have $O(1)$ additions and removals.

There is another, more complicated algorithm that walks down the expression, and mutates the outer expression when it sees an assignment. This however, is $O(n^2)$ because it will have to mutate (at worst) $O(n)$ expressions when it get's there. The program that would cause this behavior would look something like this:

(lambda x . (lambda a . ... (lambda z . ((set! x 1) ... (set! x 1))) ...))

So, is there a linear time ($O(n)$) algorithm that can find all of the assigned variables in every lambda expression in a program?

  • 1
    $\begingroup$ (1) I think you meant (values x (set)) for the last case (to return the empty set, since there is no assignment in that case). (2) Have I understood correctly that you want only assignments to the free variables? If it's true, then it may be a good idea to reflect that in your description: "... denoting all of the assigned <free> variables in it." $\endgroup$ – Anton Trunov Feb 18 '16 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.