gistfile1.rb

require "set"

def main
  # 関数の引数はすべて参照渡しということにする
  @program = [
    [:sub, :main, [],
      [:f, :a]],
    [:sub, :f, [:x], 
      [:set!, :a],
      [:g, :x]],
    [:sub, :g, [:y],
      [:set!, :y]]]
  init()
  p gmod(:main)
  p gmod(:f)
  p gmod(:g)
end

class Symbol; alias inspect to_s end
Sub = Struct.new(:args, :body, :out_edges)

# in,outが同じ辺同士であっても==になってほしくないためStructは使わない
class Edge
  def initialize(in_,out) @in,@out=in_,out end
  attr_reader :in, :out
end 

# gmod(f) = 関数fを呼び出したときに値が変わる可能性のある変数の集合
# 関数呼び出しに循環がなければ、再帰的にgmodは決定可能
def gmod(f)
  @imod[f] | @subs[f].out_edges.map{|e| g=e.out; gmod(g).map(&@b[e]) }.inject(Set[], :|)
end

def init
  @imod = {}
  @b = {} 
  @subs = {}
  # 仮引数の名前に関数名を付加しておく
  @program.each do |(_, f, args, *body)|
    replace = ->x { args.include?(x) ? "#{x}@#{f}".intern : x }
    argsp = args.map(&replace)
    bodyp = body.map{|(g,*params)| [g, params.map(&replace)] }
    @subs[f] = Sub.new(argsp, bodyp)
  end

  @subs.each do |f, sub|
    args, body = sub.args, sub.body
    @imod[f] = Set[]
    @subs[f].out_edges = []
    body.each do |(g, *params)|
      if g == :set!
        @imod[f].add(params[0])
      else
        e = Edge.new(f,g)
        @subs[f].out_edges << e
        b = {}
        @subs[g].args.zip(params) do |arg,param|
          b[arg] = param
        end
        @b[e] = ->x{ b[x] or x }
      end
    end
  end
end

main() if $0 == __FILE__