mkatz@SESAME.STANFORD.EDU (Morris Katz) (12/17/88)
In order to yield better performance for my parallelization system, I am trying to derive an algorithm for ddetermining which calls to cons, make-vector, etc. generate objects which are guaranteed not to be mutated anywhere in a program. Any ideas on this subject or references to related literature would be greatly appreciated. It seems that this poroblem is much more difficult than one might suspect. It gets even worse if one wants to do things like determine that the objects returned by recursive calls of a procedure are immutable, but those returned to the original call are mutable. This form of analysis seems necessary if one wants to actually identify a significant number of sites where immutable objects are created. Thanks in advance for the help, Morry Katz katz@polya.stanford.edu
dor@lanl.gov (David Rich) (12/20/88)
In article <8812162238.AA27888@sesame.stanford.edu>, mkatz@SESAME.STANFORD.EDU (Morris Katz) writes: > In order to yield better performance for my parallelization system, I am trying > to derive an algorithm for ddetermining which calls to cons, make-vector, etc. > generate objects which are guaranteed not to be mutated anywhere in a program. > Any ideas on this subject or references to related literature would be greatly > appreciated... Well, here's a start: %A Adrienne Bloss %A Paul Hudak %A Jonathan Young %T Code Optimizations For Lazy Evaluation %R Draft %I CSD, Yale UNIV %C New Haven, CT %D 1988 Also, Adrienne's PhD dissertation is a good reference (it predates this one I believe) -- most likely available as a technical report from Yale. She uses a technique called "Path Analysis" (a form of abstract interpretation) to determine when destructive updates are possible. However, if I remember correctly, her work deals mainly with first order languages and serial evaluation. Hope this helps! --Dave