Ruby Colored Glasses

Slow progress this week. I can’t really point to anything inparticular, but I just had trouble getting focused and getting things done this week. Not having my MacBook Pro, also put me a bit off beat as I’m just so used to it as my development environment.

Fellowship Applications

I did finish up my fellowship applications, with the exception of getting information to my reviewers which I should get done tonight.

Ruby Partial Evaluator

I haven’t really made much progress on this, though I did get a chance to start working on this again a little today. In reflecting on it a little bit, I had mentioned treating calls to new special in two ways:

1. We need to check the initialize function for the implementation, rather then new
2. We can allow code in initialize (or functions it calls) to set instance variables on the newly created object

The second condition here though, I think could be broader. Since any method call can potentially add a new instance variable, I think it may be helpful to maintain a hash of the defined instance variables for a given instance of a class, and always allow the first assign to go without counting it as a modification (since it is really just an extension of the object, rather then a modification of its state). I think this will give us more precise information, though it may make it a little more difficult to be precise about this, since it is not uncommon to have initializer methods other then new or methods that add new instance variables the first time they’re called.

Ruby partial evaluation is the focus this week, with just a little bit of work to finish up for fellowship applications before I get started on this.

Fellowship Applications

• Send references requests off, with a packet of the information I had sent off to NSF
• NPSC Fellowship Application
  • Finish up these essays, largely rewriting and polishing at this point
  • Complete their online forms
  • Put together an equivalent packet for my reference writers for this stuff as well

Ruby Partial Evaluation

• Finish code that extracts properties of a method call (specifically constant, global, class, and instance variables modified or referenced, methods called, and which methods are called on objects passed in as arguments)
• Use properties of method call for special casing new method call (i.e. have it look at initialize
• Begin working on algorithm for determining which side-effects we can partial evaluate, and which will need to wait for runtime.
• Create simple partial evaluator that uses the safety information from the offline analysis to create the partially evaluated code.

Sad Mac News

Also, in sad mac news, my MacBook Pro started to randomly kernel panic on me over the weekend and by Sunday afternoon, was pretty consistent at dieing after 10-15 minutes of up time (at this point it is even less!) So I’m a little off schedule from this weekend. On the plus side, I didn’t loose anything, as I’ve pulled stuff I’ve been working on recently onto my home Linux server, and I’ve got AppleCare on the laptop, so hopefully they’ll be able to fix me up. Still, sad not to have a working laptop!

It was a busy week, this week, but I managed to make progress on both fellowship and Ruby partial evaluation implementation

Fellowships

It was a little down to the wire, but I managed to get my NSF Graduate Student Fellowship application in. The NPSC folks, extended the deadline by a week, so I’ll be finishing that up over the weekend.

Ruby Partial Evaluation

I’ve started working again on the Ruby partial evaluator, specifically focusing on the safety analysis piece of this code. I’ve gotten back to roughly the point where I was before, starting to look at extracting the properties of a function call at a given call site in order to figure out if it is safe or not.

For the first half of this week, I’ll be primarily focused on finishing a couple of fellowship applications that are both due this Wednesday, after that I’ll be getting back to work on the partial evaluator, with our revised algorithm

Fellowship Applications

• Write application essays
• Finish filling out application sheets (by Wednesday)

Partial Evaluator

• Start work on iterative analysis to determine which expressions are safe to evaluate and which are not
  • Initial pass: data-flow analysis to setup known variables/objects and initial method call safety list
  • Iterative pass: using discovered data, extend safety to new expressions, and re-evaluate

At a guess it will be at least next week before I get a chance to begin implementing the partial evaluator that uses this data, even if the safety analysis tool goes fairly smoothly, but once the safety stuff is working, it should make the partial evaluation run relatively quickly.

A bit of a slow week this week, but I did make at least a little bit of progress on my two goals for the week.

Fellowship Applications

Unfortunately, I didn’t get a lot done this week. I realized on Tuesday night, that the fellowships I’m applying for are due on the 5th not the 9th, so I’ve been mostly focused on getting these applications ready, though I’ve still got quite a bit to do on that front before I’m finished.

Ruby Partial Evaluator

While I didn’t get a chance to look much at the coding aspects of this, I did have a very good conversation about how to approach this with my advisor, and once my fellowship applications are ready, I’m looking forward to getting back to this.

The basic idea is pretty straight forward, we’re going to treat determining the safety of running expressions in Ruby as an iterative data-flow analysis problem.

• Initial pass
• A Ruby session, with fresh scope will be started
• Assignments of literals will be evaluated in the session
• Assignments of newly created objects will be evaluated, if no global or class variables are accessed, or functions called (other then known safe functions)
• The require and load functions (and methods that call them) will need special treatment to properly handle library inclusion.
• All other method calls will be evaluated into one of three categories
• Safe: No global, class, or instance variables accessed, and only known safe functions are called
• Unsafe: A known unsafe method is called
• Unresolved: Global, class, or instance variables are accessed, or unresolved functions are called, then an annotation is added to list the global, class, or instance variables set or read, and the methods called by each, along with what arguments are updated (if known) or what methods are called on these
• Iterative Pass
• The current Ruby session scope is thrown away, and a fresh one established
• The same assignments are originally computed are performed, along with any new method calls determined safe
• Once a method is determined to only be unsafe because of modifying variable state, we look to prove that these modifications can be propagated to all method calls referencing a given global, class, or instance variable, and can all be executed.
• Now that more methods can be executed, more information is known about the program, and it can be refined
• Once no more refinements can be made (i.e. a fixed-point is reached) we stop, the result is the original AST annotated with what is and is not safe

Once the basics are implemented, we’re hoping to extend this method to handle things like libraries and partial evaluation within methods, where properties (such as core library method definitions) hold.

This week, I hope to get to a point where I can again start working on code for deciding the safety of expressions in Ruby. While, I need to talk it over with my advisor, I have a few ideas that may allow us to move forward, using some special handling of new (initialize) and require/load

The Plan

• Finish/submit eScience 2008 “camera-ready” version of extended abstract with short description.
• Start working on essays for fellowship applications
• Decide on an implementation strategy for the partial evaluator
  • Discuss simpler, but perhaps less efficient idea of determining safety of evaluating expressions
  • Assuming we decide on something, begin implementation of this

This week, I continued reading about type inference schemes for dynamically typed object oriented programming languages and looking at existing Ruby libraries to see how well the technique I described previously might work. I also took a look at the possibility of using tracing information in order to help us determine types, safety, etc. for use in the partial evaluator

Analyzing Ruby

After taking a look through the RubyGems library a bit more this week, I think it may be difficult to analyze Ruby libraries outside of their usages, since it will be hard to know the types (or values) for things like program arguments, though I do think it may be possible to construct a representation for these with information about:

• Methods called by a library and by the methods defined in that library
• Constants references and in the case of constants that contain mutable data, like Arrays and Hashes, update this data
• Class variables and their initialized values
• Instance variables and their initialized values
• What instance/class/global variables are set/accessed in methods

Together this information may help to analyze what is safe/unsafe during a program run, though it is also true that more complicated methods, such as the Gem#activate method, which is recursive, updates and accesses an instance variable of the class, and calls several other methods that may modify state, might be better handled with the full source code available, rather then trying to distill it into a description which is not much less complicated.

Paper Research

In addition to the paper on Self, I described last time, I’ve found a few other interesting papers, including a dissertation from one of the researchers involved with Self describing six different type inferencing schemes for dynamically typed OOP, and implemented each one for Self. This is performing full type-inference, which may not be something we need to do so precisely since we are primarily concerned with methods we think we can partially evaluate.

Using Ruby Tracing

The Ruby tracing feature provides a way to hook into every line of code as it is executed through the interpreter and get information that the call has been made. While the facility is very powerful, since it gives you file and line number information, which can be used to look up the exact call, it is unfortunately not very granular, distinguishing only eight event types: c-call, c-return, call, class, end, line, raise, and return. In order to determine information such as variables set, etc. we’d need to find some other way to determine this information, either using functions like instance_variables, local_variables, etc. or by retrieving the source line being executed and handling it for those situations where an assignment might appear. In either case, we’d need to be careful to ensure that we were really getting the information we needed.

Other Items

While I didn’t get a chance to get started on any fellowship application essays, I did find out that my extended abstract was accepted for eScience 2008 and have started working that into a “camera-ready” form, and putting together the 250-word abstract to the extended abstract, that was requested.

Ruby Partial-Evaluation Golas

• Continue looking through more Ruby projects to determine feasibility of type inference for method calls when the receiver, arguments, and optional block and known and safe.
• Extend paper research to see if others have picked up where Craig Chambers and David Ungar’s Customization: Optimizing Compiler Technology for Self, a Dynamically-Typed Object-Oriented Programming Language from PLDI’89 left off.

Other Academic Related Goals

• Start working on NSF and other graduate fellowship essays!

In news from the outside world, there is now an extension to Ruby for LLVM intended to make working with LLVM easy and fun, called llvmruby.

Interesting VM News

An InfoQ article about it also notes a yarv2llvm compiler for translating YARV bytecode to LLVM, and says the Rubinius team’s new CPP based VM also has an LLVM library and is targeting LLVM with the new VM.

This week, as I mentioned at the beginning of the week, I’ve taken some time away from coding in order to try to come up with a better idea of how to accomplish some of our goals in determining safety for partial evaluation and implementing the partial evaluator. My advisor also recommended that I try to look through some Ruby code and get a feel for what people are doing to see how realistic some of my ideas on how to tackle this are, and if people have tried similar things with other languages in the past.

Looking through Ruby code

After spending a little time looking through the source code for the Webby project and some of its required libraries, I’ve found out a few things

1. It may be too restrictive to force programs to have all of their require statements inlined, in particular, Webby, Logging, and RubyGems all make use of require within functions, pulling in functionality only when needed, or using it to load plugins
2. Many projects, including parts of the built-in Ruby libraries load C code, so coming up with some sort of simple way to annotate or describe these libraries for the partial evaluator may be needed for realistic sized programs
3. I still need to spend more time looking through some code before I have an idea of how successful finding return types of methods will be

Paper Search

I also made a quick paper search through some of the Smalltalk and Self optimization papers, and ran across a retrospective, which talked about the paper “Customization: Optimizing Compiler Technology for Self, a Dynamically-Typed Object-Oriented Programming Language” which talks about a type approach similar to the one I was thinking about, based on a single pass data flow analysis looking at literal values and object creation to find types. I’ve not had a chance to read the paper in detail yet and the retrospective implied that there have been refinements on the idea since the paper was published in PLDI ‘89, so I’ll be looking more into that next week.