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))] [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?