Status Update – 11/14/2009

weekly_goals  Tagged , , No Comments »

This week I contiued to work on getting to a point where the partial evaluator is at feature complete. In particular this week, I started looking at how to handle control flow from keywords like break, next, redo, retry, return, and yield. Since we are not yet handling the internals of methods at call sites return and yield don’t require handling and retry doesn’t exhibit the behaviour that would allow you to write a while style loop, which helps to simplify dealing with these a bit. I also started working on slides for my RubyConf’09 talk.

Control Flow

Control flow like break and next is a little more challenging to handle in the partial evaluator because right now we are not building a control flow graph, but instead rely on passes through the AST to provide our data flow. This is simpler then building a control flow graph, since we’ve already got the AST handy, but it does mean that we need to carry a control flow result from an arbitrarily nested expression back up to the loop it effects. It also means we need to carry that environment up, even when the control flow statement may have been unioned away.

Progress

Less then a week until RubyConf and I’m down to just handling function calls and tieing up a few loose ends. I’m hoping to have enough of this functional that I can demonstrate some real examples of its use, even if these are just simple examples.

Next Week

I’ll be spending the beginning of next week finishing up what I can of the partial evaluator and getting my slides ready and presentation polished for RubyConf!

Status Update – 11/07/2009

weekly_goals  Tagged , , No Comments »

This week I focused on finishing up the my definition of the Ruby super environment so that it will support the deepcopy, meet, and == methods, which are needed to support dataflow analysis through branches and loops. With that finished, I’ve also been working on getting matches defined for the last few node types. These include the branching and looping constructs as well as definitional constructs like, class, module, and function definitions. Most of these I’ve got the basics of now implemented, though they still need testing and need to be integrated into the evaluator side of the partial evaluator.

Complex Expressions

One interesting thing that came up in my individual meeting with my adviser this week is that I effectively need to flatten expressions in the code when I have a complex expression appearing in a place where a single expression is expected. This needs to be done to preserve any side-effecting actions in the original code. For example consider the following expression:

if (x = 7
    y = 8
    x == (y - 1)) then
   ---
end

Here we have a complex expression, (x = 7; y = 8; x == (y - 1)) in a place where a single expression was expected. We know statically that the value of the expression is true, because the value of x and y are literals and - is a safe method to evaluate. We cannot get rid of the assignments though because we don’t know if x and y will be used again in a non-compile time expression, so we need to make sure we preserve them. That said, they can be moved above the if because they will always be evaluated, without changing the semantics of the program.

It is interesting to note that we do not necessarily need more then one expression to have a “complex” expression. Consider for instance the embedded string statement:

x = "a #{y = "quick"} test"

Here we have a single assignment expression in the body of an embedded expression. We can statically determine that the value of x is “a quick test”, but we need to preserve the assignment to y. We’d like to do this by lifting the assignment out to be something like:

y = "quick"
x = "a #{y} test"

Which after partial evaluation would end up looking something like:

y = "quick"
x = "a quick test"

So I’ve been starting to work on integrating this partial flattening process into the partial evaluator.

Progress

So the environment is pretty much done and I’ve added quite a few more node types to the partial evaluator, with the remaining ones being a couple more challenging ones (like method invocation) and a few less challenging ones (like retry, redo, and break). After discussing this with my adviser, I’ve also started working on adding flattening for expressions that need it.

Goals for next week

With RubyConf’09 fast approaching, I’d really like to get a feature complete version of this code together. Right now that means getting the flattening code worked out, adding handling for the remaining node types, and adding a basic function safety analyzer. to get us to the point where we can run code through the partial evaluator, and as my adviser keeps saying “actually handle 2 + 2″. I also need to start working on my presentation and get the basics put together by my Thursday meeting so I’ll get a chance to discuss it with him. Lots to do!

Status Update – 11/02/2009*

weekly_goals  Tagged , , No Comments »

This week was focused on getting the environment representation setup to work with branching and looping statements where a meet is needed in order to get the correct semantic behavior in the partial evaluator. Additionally, I worked on adding a number of other node types to move the partial evaluator to feature completeness.

Progress

The environment, unfortunately, proved a bigger beast to tame then it at first appeared. After talking this through, it seems like there is no way to avoid at least some of the mess, and so I’ve been trying to get the environment pieces put together. I’ve still not finished this up, but hope to have this squared away early in the week this week.

Goals for this week

The big goal for this week is to get things feature complete. This means that all of the node types in the Ruby AST should be handled and the partial evaluator should be able to evaluate method safety and evaluate safe expressions into their results for at least a limited number of functions. Once this is done, my hope is to tie the code to the ruby-benchmark suite to get some time measures and RubySpec to make sure our transformations are correctness preserving.

* Sorry I’m a little late with my status this week.

Status Update – 10/23/2009

weekly_goals  Tagged , , No Comments »

This week I focused on getting more of the basics of the partial evaluator working. As of this week the following is now working:

  • Multiple assignment statements are now turned into a set of single assignments, preserving the semantics by using a temporary to capture the value.
  • A basic version fo the partial evaluator has been put into place. While there is not much it can do yet, it does at least give us a running program to start from, and running code is always a good start.
  • I am also now simplifying field assignment (o.a = 1), aref assignment (a[1] = 0), and aref references (x = a[1]) into the appropriate method calls.

The focus for next week is getting basic branching and looping constant propagation in, and adding basic support for called functions. Hopefully there will also be time to get the enough of the definitional stuff in that we can start analyzing defined functions.

Project Progress 8/19/2009

weekly_goals  Tagged , , No Comments »

Last week and early this week, I spent time working on the Ruby partial evaluation code, Scheme type recovery system, and my Scheme Workshop Paper.

Last Week

  • Type Recovery Improvements
    • Move off of match onto a datatype based implementation so we will be working with records the whole way through (Done)
    • Continue expanding the number of supported primitives, hopefully with some modified code based on a more declarative type table (In Progress)
  • Scheme Workshop
    • Write up slides (Done)
    • Give practice presentation on Thrusday at 10:00 AM (Done)
  • Ruby Partial Evaluation
    • Write a simple unsweetening pass to remove some of the syntactic sugar from the Ruby parse tree, while keeping the results still pretty printable back to valid Ruby (Done)
    • Write a pass for determining which variables can be treated as compile-time values by analyzing the Ruby parse tree (In Progress)
    • Begin working on using the compile-time variables to slice the program into the part that can be partially evaluated the slice that cannot (Not Done)

Additionally Michael and I ran into a couple of bugs in the system, which we worked together to try to track down. These have been exposed as we finish moving off of the environment version of the code and are making other simplifications to the code base.

This Week

This week I will be continuing to work on these items. I am also heading to Boston this weekend to present at the Scheme Workshop and attend the Mitch Wand Symposium. I’ll be leaving early Friday afternoon and returning on Tuesday morning.

  • Type Recovery Improvements
    • Continue expanding the number of supported primitives, hopefully with some modified code based on a more declarative type table
  • Scheme Workshop
    • Rework slides based on comments from my practice presentation
    • Give the real presentation on Saturday at 11:30 AM
  • Ruby Partial Evaluation
    • Write up presentation proposal for RubyConf’09 (due this Friday!)
    • Write a pass for determining which variables can be treated as compile-time values by analyzing the Ruby parse tree
    • Begin working on using the compile-time variables to slice the program into the part that can be partially evaluated the slice that cannot

Project Progress 8/10/2009

weekly_goals  Tagged , , , No Comments »

Last week I returned from a couple weeks of vacation, and got back into the swing of working on the Ruby partial evaluation code and the Scheme type recovery system. Between now and then I’ve:

  • Helped Michael and Kent integrate the type recovery system with a development version of the full compiler, pushing through some changes to allow our current code base to be invoked as a pass from the compiler code.
  • Finished re-working the parser from Ripper
    • Discovered a bug in handling heredocs and created a patch to fix it in the Ruby SVN source
    • Rewrote our tests to make sure that we still have a baseline to test RubyWriteRuby against
  • Finished re-working the unparser from our new RubyWriteRuby parse structure
    • Rewrote the RubyPrettyPrinter to handle the parse tree now being generated from the Ripper-based RubyWriteRuby
    • Reworte our tests to make sure that we have a baseline to test the pretty printer against

This Week

This week, I’ll be continuing to work with Michael and Kent on integrating the type recovery code into Chez Scheme and working on some improvements, moving onto the next steps with the Ruby partial evaluator, and preparing for my Scheme Workshop conference presentation. The plan:

  • Type Recovery Improvements
    • Move off of match onto a datatype based implementation so we will be working with records the whole way through
    • Continue expanding the number of supported primitives, hopefully with some modified code based on a more declarative type table
  • Scheme Workshop
    • Write up slides
    • Give practice presentation on Thrusday at 10:00 AM
  • Ruby Partial Evaluation
    • Write a simple unsweetening pass to remove some of the syntactic sugar from the Ruby parse tree, while keeping the results still pretty printable back to valid Ruby
    • Write a pass for determining which variables can be treated as compile-time values by analyzing the Ruby parse tree
    • Begin working on using the compile-time variables to slice the program into the part that can be partially evaluated the slice that cannot

Fixing Ripper’s Here Document Parsing

Ruby  Tagged , No Comments »

Ruby, like Perl, supports the idea of a “here document” (heredoc).  This basically gives you an easy way of writing large multiline strings that start and are terminated by an arbitrary string delimiter. In Ruby heredocs also support string interpolation, much like a double quoted string. Heredocs are often useful for several reason, not least of all when used along with metaprogramming features such as module_eval to embed the source for the Ruby source with normal formatting in the file.

Ripper — A Ruby Parser

Ripper provides a SAX-like, event-based protocol for parsing Ruby. It divides the events into scanner events and parser events. Roughly speaking the scanner events correspond to the lexical analysis steps, while the parser events correspond to the top level parser events. This provides a fairly easy way to write a simple parser, and we are using Ripper as the basis for our Ruby parser which generates a parse tree using our RubyWrite tool to generate the nodes. Unfortunately Ripper, a parser included as an extension with Ruby 1.9.x, does not properly support heredocs in its current implementation.

Ripper and Heredocs

Ripper, generates all the appropriate scanner events for the heredoc, but ultimately looses the last part of the string, just before the heredoc end event, because it overwrites the YACC value that contained the string before it gets the chance to make it to the parser. I think the problem partially stems from the fact that the lexer function treats heredocs specially, handling the processing of them out of the parser, and only dipping into the parser to process embedded strings. The problem with this approach is that the parser is not aware of the heredoc_beg and heredoc_end events generated in the Ripper scanner. In the case of the heredoc_beg this is fine, since the parser is just generating an event for the finished string, but it does mean that dispatching the heredoc_end event accidently wipes out the string content token that the parser was actually expecting here.

The bug can be demonstrated pretty easily using either Ripper’s built-in s-expression parser or our RubyWriteRuby parser:

$ irb -Ilib -rruby_write_ruby
>> Ripper.sexp("<<-EOF\nThis is a\ntest of heredocs\nEOF")
=> [:program, [[:string_literal, [:string_content, [:heredoc_end, "EOF", [4, 0]]]]]]
>> RubyWriteRuby.parse("<<-EOF\nThis is a\ntest of heredocs\nEOF").to_string
=> ":Program[[:StringLiteral[["EOF"]]]]"

I wanted to find a simple fix to this, rather then changing how heredocs are handled between the Ruby lexer and parser, I made a small change to the parse.y file to allow the heredoc_end event to be issued without having it overwrite final YACC value, so that the lexer is sending the correct information to the parser. I have added Bug 1921 to the Ruby redmine project with my patch. Hopefully this will be sufficient to patch the problem until a better fix can be written.

Instead of the heredoc_end, we get the expected tstring_content. This is done without changing the scanner events dispatched into Ripper, so it is still possible to capture the heredoc_beg, tstring_content, and heredoc_end scanner events in the correct order. Running the test with my patch:

$ irb -Ilib -rruby_write_ruby
>> Ripper.sexp("<<-EOF\nThis is a\ntest of heredocs\nEOF")
=> [:program, [[:string_literal, [:string_content,
     [:tstring_content, "This is a\ntest of heredocs\n", [2, 0]]]]]]
>> RubyWriteRuby.parse("<<-EOF\nThis is a\ntest of heredocs\nEOF").to_string
=> ":Program[[:StringLiteral[["This is a\\ntest of heredocs\\n"]]]]"

Renewed Focus for Spring

weekly_goals  Tagged , , No Comments »

After a couple weeks off from posting, I’ve made a bit of progress and find myself ready to get started again on the real meat of the Ruby, partial evaluation tool. Last week I used my shadow boxing library to put together a pretty printer for Ruby that passes all of my existing test cases for this tool. This week I intend to start working on some of the analysis tools that I need in order to get Ruby partial evaluation working.

This week

The plan this week is to get started on some of the analysis that needs to be done in order to determine when an expression is safe to be evaluated. The basic assumption is that we can partial evaluated those expressions that do not rely on external information (such as files, running environment, etc. that may change at runtime), and do not change the state of the program in inconsistent ways (for instance, we can evaluate something that modifies the state of object obj only if all previous statements that modified the state of object foo were also run. In doing this analysis we assume that we are working on whole programs and that all the source code is available for the program in Ruby, i.e. we cannot currently handle external C sources, outside the built-in Ruby classes.

This week, I’d like to get the basic framework for this analysis in place, along with tools for loading required files and handling dynamic updates to classes in the metadata for these items. If possible, I’d like to figure out how to construct a “sandbox” within Ruby to allow me to speculatively make changes, that won’t effect the tool around it. This could be done by spawning a new evaluation tool and talking back and forth with it using the distributed Ruby extension, but even in this case some protections will be needed.

Shadow Boxing

Ruby  Tagged , , 1 Comment »

While it has undergone very, very little testing the Shadow Boxing library is now available, and bug reports are welcome! I’ve added the shadow_boxing.rb and test_shadow_boxing.rb to the RubyWrite repository. The test_shadow_boxing.rb has a very simple test that plays double duty as an example of how to use it, but I wanted to post a little introduction here.

Using the Library

Here is an example of a little pretty printer for a small subset of Ruby. Important notes about what is going on here.

  • Each rule matches a node of the type represented by the symbol argument.
  • The result of each block should either be a pretty printer node: (:H, :V, etc.) or something that can be turned into a string.
  • The operators h, v, and hv work like their counterparts in Stratego/XT’s GPP
  • The h-star operator gives us a way to handle lists of items

Here is the example (note I use the instance_eval trick so that functions in the block will be called on the boxer object here)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
boxer = ShadowBoxing.new do 
  rule :If do |t, c, a|
    v({}, v({:is => 2}, h({:hs => 1}, "if", t, "then"), c), a, "end")
  end
  rule :Call do |recv, meth, args| 
    case meth
    when :==, :+, :-, :*, :/ 
      if args.value == :OptionalArgs then
        h({:hs => 1}, recv, meth,
          h_star({:hs => 1}, ",", *args.children[0].children[0]))
      else
        h({}, recv, meth)
      end
    else
      h({}, recv, ".", meth, args)
    end
  end
  rule :Vcall do |var_meth| var_meth end
  rule :OptionalArgs do |ary| 
    h({}, "(", h_star({:hs => 1}, ",", *ary.children[0]), ")")
  end
  rule :Lit do |lit| lit end
  rule :Fcall do |meth, args| h({}, meth, args) end
  rule :Str do |str| h({:hs => 0}, "\"", str, "\"") end
  rule :OptionalElse do |body| v({:is => 2}, "else", body) end
  rule :None do "" end
end

boxer now contains a pretty printer for a tiny subset of Ruby. We can call the pretty printer with a small block of Ruby AST in our Node classes:

1
2
3
4
5
box = boxer.unparse_node(
  :If[:Call[:Vcall[:y],:==, :OptionalArgs[:Array[[:Lit[5]]]]],
     :Fcall[:puts,:OptionalArgs[:Array[[:Str['foo']]]]],
  :OptionalElse[
     :Fcall[:put,:OptionalArgs[:Array[[:Str['bar']]]]]]])

This will return an object of the Boxer class containing our node to be pretty printed. All I need to do to get this is call: box.to_s to get the pretty printed source which looks like:

1
2
3
4
5
if y == 5 then
  puts "foo"
else
  puts "bar"
end

Bugs and Missing Features

I’m sure this source code probably has some bugs and missing features, so as you use the library and encounter problems, please let me know. I’ll be working on getting this working for the full Ruby source over the next week, and hopefully that will also help to find any bugs in this simple implementation.

(Sorry about the lack of syntax high-lighting, I cannot figure out how to get the extra CSS that coderay needs into the page without modifying the wordpress source.)

Busy Week: 03/02/2009

weekly_goals  Tagged , No Comments »

Always sad to have two posts about slow progress in a row, but I’ve been swamped for the last week, and probably the next few days won’t be too much better, though there is some light at the end of the tunnel. Our spring break is coming soon, and perhaps for the first time this semester I’ll be a little ahead of the curve instead of just behind it.

What did get done?

The Plan

  • Commit code, need to make sure the repository stays up to date! Done
  • Finish the GPP in Ruby implementation
    • Rework the GPP code to build a tree to be processed. In Progress
    • Implement a small PP for subset of Ruby as an example/start on the Ruby PP. Not Done
    • Finish full Ruby PP Not Done
    • Write Ruby PP tests, equivalent of Ruby parser tests Not Done

The Plan for this Week

The big plan for this week is mostly to get generally caught up with everything, first and foremost getting the pretty-printer in place so that Chun-Yu’s progress is not affected by my busy schedule. After that, getting as much done that wasn’t from last week is the priority.


WordPress Theme & Icons by N.Design Studio. WPMU Theme pack by WPMU-DEV.
Entries RSS Comments RSS Log in