Posted to tcl by aspect at Thu Mar 06 18:19:34 GMT 2014view raw

  1. # Tcl feels like a programmable debugger for itself. The facilities for introspection
  2. # and reflection are par excellence. What seems sorely neglected though - especially because it's so close - is the few more building blocks for Abstract Interpretation.
  3. #
  4. # In AI, the goal is to run the program on a machine with simplified semantics. For example: I have a small script containing a number of procs for which I want to generate a complete call-graph, without having to run them all with every possible input while tracing. In a page of code I can get most of the way there.
  5. #
  6. # Here's a simple test input:
  7. #
  8. # set script {
  9. # proc a {} { b; c }
  10. # proc b {} { c }
  11. # proc c {} {
  12. # puts "Hello, world!"
  13. # }
  14. # }
  15.  
  16. proc K {x args} {set x}
  17. proc readfile {fn} {K [read [set fd [open $fn r]]] [close $fd]}
  18. set script [readfile [lindex $argv 0]]
  19.  
  20. interp create -safe i0
  21. interp eval i0 {namespace delete ::}
  22.  
  23. namespace eval ai { ;# our abstract interpreter
  24. variable procs ;# an array
  25. proc collect_procs {name args body} {
  26. variable procs
  27. set procs($name) ""
  28. }
  29. proc trace_calls {name args body} {
  30. variable current_proc
  31. set current_proc $name
  32. try {
  33. i0 eval $body
  34. } finally {
  35. unset current_proc
  36. }
  37. }
  38. proc unknown {cmd args} {
  39. variable procs
  40. variable current_proc
  41. if {[info exists current_proc] && [info exists procs($cmd)]} {
  42. # track the call
  43. lappend procs($current_proc) $cmd
  44. }
  45. }
  46. }
  47.  
  48. # 1st run: collect only proc statements
  49. interp alias i0 unknown {} ai::unknown
  50. interp alias i0 proc {} ai::collect_procs
  51.  
  52. i0 eval $script
  53.  
  54. # 2nd run: collect any calls to known procs
  55. interp alias i0 proc {} ai::trace_calls
  56. i0 eval $script
  57.  
  58. # procs(a) = b c ;# indicates [a] calls [b] and [c]
  59. parray ::ai::procs
  60.  
  61. # this works perfectly, except for a few details:
  62. #
  63. # - core commands that take a script argument should be shimmed like [proc]. Trivial. It's noteworthy that (for this analysis) in every case we want to "execute" (under AI) every script argument exactly once. Callbacks are a bit more tricky (should an [apply] argument be evaluated?), but not that much .. and AI doesn't seek 100% replication of the host language - that would defeat the point.
  64. # - namespace resolution support. Not exactly trivial, but a SMOP. Anyone who's written procs using [uplevel] is aware of the sort of precautions that are needed here.
  65. # - variables. This bit sucks.
  66. #
  67. # The slave interp doesn't give us any control over variable resolution (as it does over command resolution). Variables need to exist in the enclosing scope before they are referenced, or an ugly error will be thrown, that we cannot recover from. To address variables with existing machinery we would need to ensure [set], [lappend] and all its friends create the appropriate variables and even handle juggling scopes for [apply] and [proc] execution. This is a lot of work ... particularly for this analysis, which simply wants to *ignore* variables!
  68. # And for a more complex analysis using variables - taint analysis, simple type tracking - the AI would have to pass around structures (or handles) that every command must know about. It significantly complicates the code.
  69. #
  70. # An answer? Well, if i0 could be given a command for variable resolution (kind of like [unknown] for command resolution), this particular AI could be completed with two lines. And more complex analyses would be well within reach. With nice and simple code.
  71. #
  72.