[QUIZ] Code to S-Exp (#95)

ruby-talk
1

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Ken Bloom

S-expressions are a useful way of representing functional expressions in many
aspects of computing. Lisp's syntax is based heavily on s-expressions, and the
fact that Lisp uses them to represent both code and data allows many interesting
libraries (such as CLSQL: http://clsql.b9.com/) which do things with functions
besides simply evaluating them. While working on building a SQL generation
library, I found that it would be nice to be able to generate s-expressions
programmatically with Ruby.

An s-expression is a nested list structure where the first element of each list
is the name of the function to be called, and the remaining elements of the list
are the arguments to that function. (Binary operators are converted to prefix
notation). For example the s-expression (in LISP syntax)

  (max (count field))

would correspond to

  max(count(field))

in ordinary functional notation. Likewise,

  (roots x (+ (+ (* x x) x) 1 ))

would correspond to

  roots(x, ((x*x) + x) + 1)

since we treat binary operators by converting them to prefix notation.

Your mission: Create a function named sxp() that can take a block (not a
string), and create an s-expression representing the code in the block.

Since my goal is to post-process the s-expressions to create SQL code, there is
some special behavior that I will allow to make this easier. If your code
evaluates (rather than parsing) purely numerical expressions that don't contain
functions or field names (represented by Symbols here), then this is
satisfactory behavior since it shouldn't matter whether Ruby evaluates them or
the SQL database evaluates them. This means, for example, that sxp{3+5} can give
you 8 as an s-expression, but for extra credit, try to eliminate this behavior
as well and return [:+, 3, 5].

It is very important to avoid breaking the normal semantics of Ruby when used
outside of a code block being passed to sxp.

Here are some examples and their expected result:

  sxp{max(count(:name))} => [:max, [:count, :name]]
  sxp{count(3+7)} => [:count, 10] or [:count, [:+, 3, 7]]
  sxp{3+:symbol} => [:+, 3, :symbol]
  sxp{3+count(:field)} => [:+, 3, [:count, :field]]
  sxp{7/:field} => [:/, 7, :field]
  sxp{:field > 5} => [:>, :field, 5]
  sxp{8} => 8
  sxp{:field1 == :field2} => [:==, :field1, :field2]
  7/:field => throws TypeError
  7+count(:field) => throws NoMethodError
  5+6 => 11
  :field > 5 => throws NoMethodError

(In code for this concept, I returned my s-expression as an object which had
inspect() modified to appear as an array. You may return any convenient object
representation of an s-expression.)

2

Am I exempt from the quiz?

···

On Sep 22, 2006, at 3:13 PM, Ruby Quiz wrote:

Your mission: Create a function named sxp() that can take a block (not a
string), and create an s-expression representing the code in the block.

3

Ruby Quiz wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Ken Bloom

S-expressions are a useful way of representing functional expressions in many
aspects of computing. Lisp's syntax is based heavily on s-expressions, and the
fact that Lisp uses them to represent both code and data allows many interesting
libraries (such as CLSQL: http://clsql.b9.com/\) which do things with functions
besides simply evaluating them. While working on building a SQL generation
library, I found that it would be nice to be able to generate s-expressions
programmatically with Ruby.

An s-expression is a nested list structure where the first element of each list
is the name of the function to be called, and the remaining elements of the list
are the arguments to that function. (Binary operators are converted to prefix
notation). For example the s-expression (in LISP syntax)

  (max (count field))

would correspond to

  max(count(field))

in ordinary functional notation. Likewise,

  (roots x (+ (+ (* x x) x) 1 ))

would correspond to

  roots(x, ((x*x) + x) + 1)

since we treat binary operators by converting them to prefix notation.

Your mission: Create a function named sxp() that can take a block (not a
string), and create an s-expression representing the code in the block.

Since my goal is to post-process the s-expressions to create SQL code, there is
some special behavior that I will allow to make this easier. If your code
evaluates (rather than parsing) purely numerical expressions that don't contain
functions or field names (represented by Symbols here), then this is
satisfactory behavior since it shouldn't matter whether Ruby evaluates them or
the SQL database evaluates them. This means, for example, that sxp{3+5} can give
you 8 as an s-expression, but for extra credit, try to eliminate this behavior
as well and return [:+, 3, 5].

It is very important to avoid breaking the normal semantics of Ruby when used
outside of a code block being passed to sxp.

Here are some examples and their expected result:

  sxp{max(count(:name))} => [:max, [:count, :name]]
  sxp{count(3+7)} => [:count, 10] or [:count, [:+, 3, 7]]
  sxp{3+:symbol} => [:+, 3, :symbol]
  sxp{3+count(:field)} => [:+, 3, [:count, :field]]
  sxp{7/:field} => [:/, 7, :field]
  sxp{:field > 5} => [:>, :field, 5]
  sxp{8} => 8
  sxp{:field1 == :field2} => [:==, :field1, :field2]
  7/:field => throws TypeError
  7+count(:field) => throws NoMethodError
  5+6 => 11
  :field > 5 => throws NoMethodError

(In code for this concept, I returned my s-expression as an object which had
inspect() modified to appear as an array. You may return any convenient object
representation of an s-expression.)

Could you write some more tests? :slight_smile:

4

I only spent about 30 minutes on this and it does a minimal job of passing the current tests (plus the ones added by Sander). It'll break when other ruby expression types (if/case/blocks) are thrown at it, but those are really easy to cover if need be. That said, I thought this was a good example of the power of ParseTree.

This requires the latest release of ParseTree. The rest came from ZenHacks/ruby2ruby but I extracted the crucial bits and put them in here directly.

#!/usr/local/bin/ruby -w

# Your mission: Create a function named sxp() that can take a block
# (not a string), and create an s-expression representing the code in
# the block.

require 'rubygems'
require 'parse_tree'
require 'sexp_processor'

···

############################################################
# From unreleased ruby2ruby:

class ProcStoreTmp
   @@n = 0
   def self.name
     @@n += 1
     return :"myproc#{@@n}"
   end
end

class Method
   def with_class_and_method_name
     if self.inspect =~ /<Method: (.*)\#(.*)>/ then
       klass = eval $1 # cheap
       method = $2.intern
       raise "Couldn't determine class from #{self.inspect}" if klass.nil?
       return yield(klass, method)
     else
       raise "Can't parse signature: #{self.inspect}"
     end
   end

   def to_sexp
     with_class_and_method_name do |klass, method|
       ParseTree.new(false).parse_tree_for_method(klass, method)
     end
   end
end

class Proc
   def to_method
     name = ProcStoreTmp.name
     ProcStoreTmp.send(:define_method, name, self)
     ProcStoreTmp.new.method(name)
   end

   def to_sexp
     body = self.to_method.to_sexp[2][1..-1]
     [:proc, *body]
   end
end

# END unreleased ruby2ruby:
############################################################

class Quiz < SexpProcessor
   def initialize
     super
     self.auto_shift_type = true
     self.strict = false
     self.expected = Object
   end

   def process_proc(exp)
     return * _list(exp)
   end

   def process_fcall(exp)
     [exp.shift, process(exp.shift)]
   end

   def process_call(exp)
     lhs = process(exp.shift)
     name = exp.shift
     rhs = process(exp.shift)
     [name, lhs, rhs].compact
   end

   def process_array(exp)
     return * _list(exp)
   end

   def process_lit(exp)
     exp.shift
   end

   def process_str(exp)
     exp.shift
   end

   def _list(exp)
     result = []
     until exp.empty? do
       result << process(exp.shift)
     end
     result
   end
end

def sxp(&block)
   Quiz.new.process(block.to_sexp)
end

if $0 == __FILE__ then
   require 'test/unit'

   class TestQuiz < Test::Unit::TestCase
     def test_sxp_nested_calls
       assert_equal [:max, [:count, :name]], sxp{max(count(:name))}
     end

     def test_sxp_call_plus_eval
       assert_equal [:count, [:+, 3, 7]], sxp{count(3+7)}
     end

     def test_sxp_binarymsg_mixed_1
       assert_equal [:+, 3, :symbol], sxp{3+:symbol}
     end

     def test_sxp_binarymsg_mixed_call
       assert_equal [:+, 3, [:count, :field]], sxp{3+count(:field)}
     end

     def test_sxp_binarymsg_mixed_2
       assert_equal [:/, 7, :field], sxp{7/:field}
     end

     def test_sxp_binarymsg_mixed_3
       assert_equal [:>, :field, 5], sxp{:field > 5}
     end

     def test_sxp_lits
       assert_equal 8, sxp{8}
     end

     def test_sxp_binarymsg_syms
       assert_equal [:==, :field1, :field2], sxp{:field1 == :field2 }
     end

     def test_sxp_from_sander_dot_land_at_gmail_com
       assert_equal [:==,[:^, 2, 3], [:^, 1, 1]], sxp{ 2^3 == 1^1}
       assert_equal [:==, [:+, 3.0, 0.1415], 3], sxp{3.0 + 0.1415 == 3}

       assert_equal([:|,
                     [:==, [:+, :hello, :world], :helloworld],
                     [:==, [:+, [:+, "hello", " "], "world"], "hello world"]] ,
                    sxp {
                      (:hello + :world == :helloworld) |
                      ('hello' + ' ' + 'world' == 'hello world')
                    })

       assert_equal [:==, [:+, [:abs, [:factorial, 3]], [:*, [:factorial, 4], 42]],
                      [:+, [:+, 4000000, [:**, 2, 32]], [:%, 2.7, 1.1]]],
       sxp{ 3.factorial.abs + 4.factorial * 42 == 4_000_000 + 2**32 + 2.7 % 1.1 }
     end

     def test_ihavenocluewhy
       assert_equal 11, 5 + 6
       assert_raise(TypeError) { 7 / :field }
       assert_raise(NoMethodError) { 7+count(:field) }
       assert_raise(NoMethodError) { :field > 5 }
     end
   end
end

5

Here is my solution.

It uses RubyNode (which is available as gem now, see http://rubynode.rubyforge.org/) to access the block's body node and then transforms that body node into the s-expression.

It is pretty similar to Ryan's ParseTree solution, but supports some additional node types and has some more tests.

Dominik

require "rubynode"

class Node2Sexp
   # (transformed) nodes are arrays, that look like:
   # [:type, attribute hash or array of nodes]
   def to_sexp(node)
     node && send("#{node.first}_to_sexp", node.last)
   end

   # fixed argument lists are represented as :array nodes, e.g.
   # [:array, [argnode1, argnode2, ...]]
   def process_args(args_node)
     return [] unless args_node
     if args_node.first == :array
       args_node.last.map { |node| to_sexp(node) }
     else
       raise "variable arguments not allowed"
     end
   end

   # :call nodes: method call with explicit receiver:
   # nil.foo => [:call, {:args=>false, :mid=>:foo, :recv=>[:nil, {}]}]
   # nil == nil =>
   # [:call, {:args=>[:array, [[:nil, {}]]], :mid=>:==, :recv=>[:nil, {}]}]
   def call_to_sexp(hash)
     [hash[:mid], to_sexp(hash[:recv]), *process_args(hash[:args])]
   end

   # :fcall nodes: function call (no explicit receiver):
   # foo() => [:fcall, {:args=>false, :mid=>:foo}]
   # foo(nil) => [:fcall, {:args=>[:array, [[:nil, {}]]], :mid=>:foo]
   def fcall_to_sexp(hash)
     [hash[:mid], *process_args(hash[:args])]
   end

   # :vcall nodes: function call that looks like variable
   # foo => [:vcall, {:mid=>:foo}]
   alias vcall_to_sexp fcall_to_sexp

   # :lit nodes: literals
   # 1 => [:lit, {:lit=>1}]
   # :abc => [:lit, {:lit=>:abc}]
   def lit_to_sexp(hash)
     hash[:lit]
   end

   # :str nodes: strings without interpolation
   # "abc" => [:str, {:lit=>"abc"}]
   alias str_to_sexp lit_to_sexp

   def nil_to_sexp(hash) nil end
   def false_to_sexp(hash) false end
   def true_to_sexp(hash) true end
end

def sxp(&block)
   body = block.body_node
   return nil unless body
   Node2Sexp.new.to_sexp(body.transform)
end

if $0 == __FILE__ then
   require 'test/unit'

   class TestQuiz < Test::Unit::TestCase
     def test_sxp_nested_calls
       assert_equal [:max, [:count, :name]], sxp{max(count(:name))}
     end

     def test_sxp_vcall
       assert_equal [:abc], sxp{abc}
     end

     def test_sxp_call_plus_eval
       assert_equal [:count, [:+, 3, 7]], sxp{count(3+7)}
     end

     def test_sxp_call_with_multiple_args
       assert_equal [:count, 3, 7], sxp{count(3,7)}
     end

     def test_sxp_binarymsg_mixed_1
       assert_equal [:+, 3, :symbol], sxp{3+:symbol}
     end

     def test_sxp_binarymsg_mixed_call
       assert_equal [:+, 3, [:count, :field]], sxp{3+count(:field)}
     end

     def test_sxp_binarymsg_mixed_2
       assert_equal [:/, 7, :field], sxp{7/:field}
     end

     def test_sxp_binarymsg_mixed_3
       assert_equal [:>, :field, 5], sxp{:field > 5}
     end

     def test_sxp_lits
       assert_equal 8, sxp{8}
     end

     def test_sxp_true_false_nil
       assert_equal [:+, true, false], sxp{true+false}
       assert_equal nil, sxp{nil}
     end

     def test_sxp_empty
       assert_equal nil, sxp{}
     end

     def test_sxp_binarymsg_syms
       assert_equal [:==, :field1, :field2], sxp{:field1 == :field2 }
     end

     def test_sxp_from_sander_dot_land_at_gmail_com
       assert_equal [:==,[:^, 2, 3], [:^, 1, 1]], sxp{ 2^3 == 1^1}
       assert_equal [:==, [:+, 3.0, 0.1415], 3], sxp{3.0 + 0.1415 == 3}

       assert_equal([:|,
                     [:==, [:+, :hello, :world], :helloworld],
                     [:==, [:+, [:+, "hello", " "], "world"], "hello world"]] ,
                    sxp {
                      (:hello + :world == :helloworld) |
                      ('hello' + ' ' + 'world' == 'hello world')
                    })

       assert_equal [:==, [:+, [:abs, [:factorial, 3]], [:*, [:factorial, 4], 42]],
                      [:+, [:+, 4000000, [:**, 2, 32]], [:%, 2.7, 1.1]]],
       sxp{ 3.factorial.abs + 4.factorial * 42 == 4_000_000 + 2**32 + 2.7 % 1.1 }
     end

     def test_ihavenocluewhy
       assert_equal 11, 5 + 6
       assert_raise(TypeError) { 7 / :field }
       assert_raise(NoMethodError) { 7+count(:field) }
       assert_raise(NoMethodError) { :field > 5 }
     end
   end
end

6

Here is my solution.
It's a pure Ruby solution so it's rather hackish as it needs to
redefine many core methods.
Also, supporting methods on String didn't make it any prettier :wink:

Pastie:
http://pastie.caboo.se/14794

Code:
class Class
  def rename_method(new_name,old_name)
      alias_method new_name,old_name
      undef_method old_name
  end
  def hide_methods
    instance_methods.each{|m| rename_method '____'.__send__('__+',m),
m unless m.__send__('__=~',/^__/) }
    define_method(:method_missing){|m,*a| SXP.new [m,self,*a] }
  end
  def restore_methods
    undef_method :method_missing
    instance_methods.each{|m| rename_method m.__send__('__[]',4..-1),m
if m.__send__('__=~',/^____/) }
  end
end

HIDE_METHODS_FOR = [Fixnum,Bignum,Float,Symbol,String]
class String
  [:+,:=~,:[]].each{|m| alias_method '__'+m.to_s,m } # these methods
are used by hide_methods and restore_methods
end

class Object
  def __from_sxp; self ; end
end

class SXP < Class.new{hide_methods}
  def initialize(a); @a = a; end
  def __from_sxp
    @a.map{|x| x.__from_sxp }
  end
end

class SXPGen < Class.new{hide_methods}
  def method_missing(m,*args)
    SXP.new [m,*args]
  end
end

def sxp(&b)
  HIDE_METHODS_FOR.each{|klass| klass.hide_methods }
  SXPGen.new.____instance_eval(&b).__from_sxp rescue nil
  ensure HIDE_METHODS_FOR.each{|klass| klass.restore_methods }
end

7

I wanted to see how far I could get if I let Ruby do the math. Answer: Not too far. Without hacking Ruby core methods I could only get these quiz tests to pass:

#!/usr/bin/env ruby -w

require "test/unit"

require "sxp"

class TestSXP < Test::Unit::TestCase
   def test_quiz_examples
     assert_equal([:max, [:count, :name]], sxp { max(count(:name)) })
     assert_equal([:count, 10], sxp { count(3 + 7) })
     assert_equal(8, sxp { 8 })
   end

   def test_normal_ruby_operations
     assert_raise(TypeError) { 7 / :field }
     assert_raise(NoMethodError) { 7 + count(:field) }
     assert_equal(11, 5 + 6)
     assert_raise(NoMethodError) { :field > 5 }
   end
end

Here's the solution used to get that far:

#!/usr/bin/env ruby -w

class SXP
   instance_methods.each do |meth|
     undef_method(meth) unless meth =~ /\A__/ or meth == "instance_eval"
   end

   def initialize(&block)
     @code = block
   end

   def method_missing(meth, *args, &block)
     if args.any? { |e| e.is_a? Array }
       [meth, args.inject(Array.new) { |arr, a| arr.push(*a) }]
     else
       [meth, *args]
     end
   end

   def result
     instance_eval(&@code)
   end
end

def sxp(&block)
   SXP.new(&block).result
end

James Edward Gray II

···

On Sep 22, 2006, at 5:13 PM, Ruby Quiz wrote:

If your code evaluates (rather than parsing) purely numerical expressions that don't contain functions or field names (represented by Symbols here), then this is satisfactory behavior since it shouldn't matter whether Ruby evaluates them or the SQL database evaluates them. This means, for example, that sxp{3+5} can give you 8 as an s-expression

8

Hi,

I wouldn't use this code in a production environment, because
methods of built-in classes are redefined.

(But it also throws a lot of warnings, so...)

Best regards,
Boris

class RealityDistortionField
   OVERRIDE = [:+, :-, :*, :/, :>, :<, :>=, :<=, :==]
   CLASSES = [Fixnum, Symbol, String]

   def self.on
     CLASSES.each do |klass|
       klass.class_eval do
         counter = 0
         OVERRIDE.each do |meth|
           # save old method:
           savemeth = "rdf_save_#{counter}".to_sym
           alias_method savemeth, meth if method_defined? meth
           counter = counter.next # since '+' is already overridden

           # override method to return an expression array:
           define_method meth do |other|
             [meth, self, other]
           end
         end
       end
     end
     # define new Object.method_missing()
     Object.class_eval do
       alias_method :method_missing_orig, :method_missing
       define_method :method_missing do |meth, *args|
         [meth, *args]
       end
     end
   end

   # Clean up:
   def self.off
     CLASSES.each do |klass|
       klass.class_eval do
         counter = 0
         OVERRIDE.each do |meth|
           # restore original methods:
           savemeth = "rdf_save_#{counter}".to_sym
           if method_defined? savemeth
             alias_method meth, savemeth
           else
             remove_method meth
           end
           counter = counter.next
         end
       end
     end
     # restore original Object.method_missing()
     Object.class_eval do
       remove_method :method_missing
       alias_method :method_missing, :method_missing_orig
     end
   end
end

class Object
   def sxp
     RealityDistortionField.on
     begin
       expression = yield
     ensure
       RealityDistortionField.off
     end
     expression
   end
end

require 'test/unit'

class SXPTest < Test::Unit::TestCase

   def test_quiz
     assert_equal [:max, [:count, :name]], sxp{max(count(:name))}
     assert_equal [:count, [:+, 3, 7]], sxp{count(3+7)}
     assert_equal [:+, 3, :symbol], sxp{3+:symbol}
     assert_equal [:+, 3, [:count, :field]], sxp{3+count(:field)}
     assert_equal [:/, 7, :field], sxp{7/:field}
     assert_equal [:>, :field, 5], sxp{:field > 5}
     assert_equal 8, sxp{8}
     assert_equal [:==, :field1, :field2], sxp{:field1 == :field2}
     assert_raises(TypeError) {7/:field}
     assert_raises(NoMethodError) {7+count(:field)}
     assert_equal 11, 5+6
     assert_raises(NoMethodError) {p(:field > 5)}
   end

   def test_more
     assert_equal [:+, "hello", :world], sxp{"hello" + :world}
     assert_equal [:count], sxp {count}
   end
end

9

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Ken Bloom

S-expressions are a useful way of representing functional expressions in many
aspects of computing. Lisp's syntax is based heavily on s-expressions, and the
fact that Lisp uses them to represent both code and data allows many interesting
libraries (such as CLSQL: http://clsql.b9.com/\) which do things with functions
besides simply evaluating them. While working on building a SQL generation
library, I found that it would be nice to be able to generate s-expressions
programmatically with Ruby.

An s-expression is a nested list structure where the first element of each list
is the name of the function to be called, and the remaining elements of the list
are the arguments to that function. (Binary operators are converted to prefix
notation). For example the s-expression (in LISP syntax)

  (max (count field))

would correspond to

  max(count(field))

in ordinary functional notation. Likewise,

  (roots x (+ (+ (* x x) x) 1 ))

would correspond to

  roots(x, ((x*x) + x) + 1)

since we treat binary operators by converting them to prefix notation.

Your mission: Create a function named sxp() that can take a block (not a
string), and create an s-expression representing the code in the block.

Since my goal is to post-process the s-expressions to create SQL code, there is
some special behavior that I will allow to make this easier. If your code
evaluates (rather than parsing) purely numerical expressions that don't contain
functions or field names (represented by Symbols here), then this is
satisfactory behavior since it shouldn't matter whether Ruby evaluates them or
the SQL database evaluates them. This means, for example, that sxp{3+5} can give
you 8 as an s-expression, but for extra credit, try to eliminate this behavior
as well and return [:+, 3, 5].

It is very important to avoid breaking the normal semantics of Ruby when used
outside of a code block being passed to sxp.

Here are some examples and their expected result:

  sxp{max(count(:name))} => [:max, [:count, :name]]
  sxp{count(3+7)} => [:count, 10] or [:count, [:+, 3, 7]]
  sxp{3+:symbol} => [:+, 3, :symbol]
  sxp{3+count(:field)} => [:+, 3, [:count, :field]]
  sxp{7/:field} => [:/, 7, :field]
  sxp{:field > 5} => [:>, :field, 5]
  sxp{8} => 8
  sxp{:field1 == :field2} => [:==, :field1, :field2]
  7/:field => throws TypeError
  7+count(:field) => throws NoMethodError
  5+6 => 11
  :field > 5 => throws NoMethodError

(In code for this concept, I returned my s-expression as an object which had
inspect() modified to appear as an array. You may return any convenient object
representation of an s-expression.)

Here's my pure ruby code, which I coded up before making the quiz. I
honestly didn't even know that ParseTree was out there.

Thinking about where I made it now, what I came up with probably wasn't
strictly speaking a complete s-expression generator for arbitrary ruby
code, but something of a relatively limited domain for working with SQL
functions.

require 'singleton'

#the Blank class is shamelessly stolen from the Criteria library
class Blank
  mask = ["__send__", "__id__", "inspect", "class", "is_a?", "dup",
  "instance_eval"];
  methods = instance_methods(true)

  methods = methods - mask
  
  methods.each do
    > m |
    undef_method(m)
  end
end

#this is a very blank class that intercepts all free
#functions called within it.
class SExprEvalBed < Blank
   include Singleton
   def method_missing (name, *args)
      SExpr.new(name, *args)
   end
end

#this is used internally to represent an s-expression.
#I extract the array out of it before returning the results
#because arrays are easier to work with. Nevertheless, since I could use
#an s-expression class as the result of certain evaluations, it didn't
#make sense to override standard array methods

···

On Sat, 23 Sep 2006 07:13:37 +0900, Ruby Quiz wrote:
#
#other built-in classes weren't so lucky
class SExpr
   def initialize(*args)
     @array=args
   end
   attr_accessor :array
   def method_missing(name,*args)
      SExpr.new(name,self,*args)
   end
   def coerce(other)
      [SQLObj.new(other),self]
   end
   def ==(other)
      SExpr.new(:==,self,other)
   end
   def to_a
      return @array.collect do |x|
   if x.is_a?(SExpr)
      x.to_a
   elsif x.is_a?(SQLObj)
      x.contained
   else
      x
   end
      end
   end
end

#this is used for wrapping objects when they get involved in
#coercions to perform binary operations with a Symbol
class SQLObj
   def initialize(contained)
      @contained=contained
   end
   attr_accessor :contained
   def method_missing (name,*args)
      SExpr.new(name,self,*args)
   end
   def ==(other)
      SExpr.new(:==,self,other)
   end
end

class Symbol
   def coerce(other)
      #this little caller trick keeps behavior normal
      #when calling from outside sxp
      if caller[-2]=~/in `sxp'/
   [SQLObj.new(other),SQLObj.new(self)]
      else
   #could just return nil, but then the
   #text of the error message would change
   super.method_missing(:coerce,other)
      end
   end
   def method_missing(name, *args)
      if caller[-2]=~/in `sxp'/
   SExpr.new(name,self,*args)
      else
   super
      end
   end
   alias_method :old_equality, :==
   def ==(other)
      if caller[-2]=~/in `sxp'/
   SExpr.new(:==,self,other)
      else
   old_equality(other)
      end
   end
end

def sxp(&block)
   r=SExprEvalBed.instance.instance_eval(&block)
   if r.is_a?(SExpr)
      r.to_a
   elsif r.is_a?(SQLObj)
      r.contained
   else
      r
   end
end

require 'irb/xmp'

xmp <<-"end;"
sxp{max(count(:name))}
sxp{count(3+7)}
sxp{3+:symbol}
sxp{3+count(:field)}
sxp{7/:field}
sxp{:field > 5}
sxp{8}
sxp{:field1 == :field2}
sxp{count(3)==count(5)}
sxp{3==count(5)}
7/:field rescue "TypeError"
7+count(:field) rescue "NoMethodError"
5+6
:field > 5 rescue "NoMethodError"
end;

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

10

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Ken Bloom

S-expressions are a useful way of representing functional expressions in many
aspects of computing. Lisp's syntax is based heavily on s-expressions, and the
fact that Lisp uses them to represent both code and data allows many interesting
libraries (such as CLSQL: http://clsql.b9.com/\) which do things with functions
besides simply evaluating them. While working on building a SQL generation
library, I found that it would be nice to be able to generate s-expressions
programmatically with Ruby.

An s-expression is a nested list structure where the first element of each list
is the name of the function to be called, and the remaining elements of the list
are the arguments to that function. (Binary operators are converted to prefix
notation). For example the s-expression (in LISP syntax)

  (max (count field))

would correspond to

  max(count(field))

in ordinary functional notation. Likewise,

  (roots x (+ (+ (* x x) x) 1 ))

would correspond to

  roots(x, ((x*x) + x) + 1)

since we treat binary operators by converting them to prefix notation.

Your mission: Create a function named sxp() that can take a block (not a
string), and create an s-expression representing the code in the block.

Since my goal is to post-process the s-expressions to create SQL code, there is
some special behavior that I will allow to make this easier. If your code
evaluates (rather than parsing) purely numerical expressions that don't contain
functions or field names (represented by Symbols here), then this is
satisfactory behavior since it shouldn't matter whether Ruby evaluates them or
the SQL database evaluates them. This means, for example, that sxp{3+5} can give
you 8 as an s-expression, but for extra credit, try to eliminate this behavior
as well and return [:+, 3, 5].

It is very important to avoid breaking the normal semantics of Ruby when used
outside of a code block being passed to sxp.

Here are some examples and their expected result:

  sxp{max(count(:name))} => [:max, [:count, :name]]
  sxp{count(3+7)} => [:count, 10] or [:count, [:+, 3, 7]]
  sxp{3+:symbol} => [:+, 3, :symbol]
  sxp{3+count(:field)} => [:+, 3, [:count, :field]]
  sxp{7/:field} => [:/, 7, :field]
  sxp{:field > 5} => [:>, :field, 5]
  sxp{8} => 8
  sxp{:field1 == :field2} => [:==, :field1, :field2]
  7/:field => throws TypeError
  7+count(:field) => throws NoMethodError
  5+6 => 11
  :field > 5 => throws NoMethodError

(In code for this concept, I returned my s-expression as an object which had
inspect() modified to appear as an array. You may return any convenient object
representation of an s-expression.)

Here's my pure ruby code, which I coded up before making the quiz. I
honestly didn't even know that ParseTree was out there.

Thinking about where I made it now, what I came up with probably wasn't
strictly speaking a complete s-expression generator for arbitrary ruby
code, but something of a relatively limited domain for working with SQL
functions.

require 'singleton'

#the Blank class is shamelessly stolen from the Criteria library
class Blank
  mask = ["__send__", "__id__", "inspect", "class", "is_a?", "dup",
  "instance_eval"];
  methods = instance_methods(true)

  methods = methods - mask
  
  methods.each do
    > m |
    undef_method(m)
  end
end

#this is a very blank class that intercepts all free
#functions called within it.
class SExprEvalBed < Blank
   include Singleton
   def method_missing (name, *args)
      SExpr.new(name, *args)
   end
end

#this is used internally to represent an s-expression.
#I extract the array out of it before returning the results
#because arrays are easier to work with. Nevertheless, since I could use
#an s-expression class as the result of certain evaluations, it didn't
#make sense to override standard array methods

···

On Sat, 23 Sep 2006 07:13:37 +0900, Ruby Quiz wrote:
#
#other built-in classes weren't so lucky
class SExpr
   def initialize(*args)
     @array=args
   end
   attr_accessor :array
   def method_missing(name,*args)
      SExpr.new(name,self,*args)
   end
   def coerce(other)
      [SQLObj.new(other),self]
   end
   def ==(other)
      SExpr.new(:==,self,other)
   end
   def to_a
      return @array.collect do |x|
   if x.is_a?(SExpr)
      x.to_a
   elsif x.is_a?(SQLObj)
      x.contained
   else
      x
   end
      end
   end
end

#this is used for wrapping objects when they get involved in
#coercions to perform binary operations with a Symbol
class SQLObj
   def initialize(contained)
      @contained=contained
   end
   attr_accessor :contained
   def method_missing (name,*args)
      SExpr.new(name,self,*args)
   end
   def ==(other)
      SExpr.new(:==,self,other)
   end
end

class Symbol
   def coerce(other)
      #this little caller trick keeps behavior normal
      #when calling from outside sxp
      if caller[-2]=~/in `sxp'/
   [SQLObj.new(other),SQLObj.new(self)]
      else
   #could just return nil, but then the
   #text of the error message would change
   super.method_missing(:coerce,other)
      end
   end
   def method_missing(name, *args)
      if caller[-2]=~/in `sxp'/
   SExpr.new(name,self,*args)
      else
   super
      end
   end
   alias_method :old_equality, :==
   def ==(other)
      if caller[-2]=~/in `sxp'/
   SExpr.new(:==,self,other)
      else
   old_equality(other)
      end
   end
end

def sxp(&block)
   r=SExprEvalBed.instance.instance_eval(&block)
   if r.is_a?(SExpr)
      r.to_a
   elsif r.is_a?(SQLObj)
      r.contained
   else
      r
   end
end

require 'irb/xmp'

xmp <<-"end;"
sxp{max(count(:name))}
sxp{count(3+7)}
sxp{3+:symbol}
sxp{3+count(:field)}
sxp{7/:field}
sxp{:field > 5}
sxp{8}
sxp{:field1 == :field2}
sxp{count(3)==count(5)}
sxp{3==count(5)}
7/:field rescue "TypeError"
7+count(:field) rescue "NoMethodError"
5+6
:field > 5 rescue "NoMethodError"
end;

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

11

Hi all,

Here's my solution which uses Ruby only and modifies core classes and restores them at the end of the function. I wouldn't trust it ;).

Maybe this would be a task for Why's Sandbox library? Create a sandbox, modify the core classes there and evaluate the blocks there. It's just an idea, I don't know if it's possible.

   Robin Stocker

class SxpGenerator

   def method_missing(meth, *args)
     [meth, *args]
   end

   BINARY_METHODS = [:+, :-, :*, :/, :%, :**, :^, :<, :>, :<=, :>=, :==]

   def self.overwrite_methods(mod)
     BINARY_METHODS.each do |method|
       mod.module_eval do
         if method_defined? method
           alias_method "__orig_#{method}__", method
         end
         define_method method do |arg|
           [method, self, arg]
         end
       end
     end
   end

   def self.restore_methods(mod)
     BINARY_METHODS.each do |method|
       mod.module_eval do
         orig_method = "__orig_#{method}__"
         if method_defined? orig_method
           alias_method method, orig_method
           remove_method orig_method
         else
           remove_method method
         end
       end
     end
   end

end

def sxp(&block)
   klasses = [Fixnum, Bignum, Symbol, Array, Float, String]
   klasses.each do |klass|
     SxpGenerator.overwrite_methods(klass)
   end
   begin
     result = SxpGenerator.new.instance_eval &block
   rescue Exception
     result = nil
   end
   klasses.each do |klass|
     SxpGenerator.restore_methods(klass)
   end
   result
end

require 'test/unit'

class TestSxp < Test::Unit::TestCase

   def test_function
     assert_equal [:max, [:count, :name]], sxp { max(count(:name)) }
   end

   def test_number
     assert_equal 8, sxp { 8 }
     assert_equal [:+, 3, 4], sxp { 3 + 4 }
     assert_equal [:+, 3, :symbol], sxp { 3 + :symbol }
     assert_equal [:/, 7, :field], sxp { 7 / :field }
   end

   def test_symbol
     assert_equal [:>, :field, 5], sxp { :field > 5 }
     assert_equal [:==, :field1, :field2], sxp { :field1 == :field2 }
   end

   def test_mixed
     assert_equal [:count, [:+, 3, 7]], sxp { count(3+7) }
     assert_equal [:+, 3, [:count, :field]], sxp { 3 + count(:field) }
   end

   def test_environment
     assert_equal [:-, 10, [:count, [:*, :field, 4]]],
                  sxp { 10 - count(:field * 4) }
     assert_raise(TypeError) { 7 / :field }
     assert_raise(NoMethodError) { 7 + count(:field) }
     assert_equal 11, 5 + 6
     assert_raise(NoMethodError) { :field > 5 }
   end

end

12

Hi,

I've been away for a while, and I like an interesting problem to get me
back into the swing of things, so this quiz came at the perfect time for
me - I've had a lot of fun with it :slight_smile: I started coding it on Monday
(before I looked at other solutions of course) and, though I'm still not
entirely happy with it, I'd better post it or I'll be still fiddling
with it long after Wednesday.

It's a fairly brief solution, and I decided to use _why's Sandbox
library which looked pretty intriguing. This is my first run with
Sandbox, though, so I'm probably misusing it a bit.

The basic idea is to keep the core classes in the main interpreter as
they are, and use a sandbox in which the the core is gutted to execute
the block. The main file (sexpr.rb) simply defines the Sxp module. When
Sxp.sxp is called, it sets up a new sandbox, passes in the block (via an
instance variable - any better way to do this?) and runs the second
script ('sandboxed.rb') which does the core mods and then calls the
block.

In the sandbox, most calls go through one of the method_missings, which
are set up so that the calls passing through will build up an array
representing the sexpr. This is the result of the last statement in
sandboxed.rb, and so the result of the Sandbox#load call.

It's not without it's problems - neither Strings nor Floats work
properly, and instead will be evaluated normally and (usually) the
result placed in the sexpr. This has some 'interesting' side effects:

  $ ruby -rsexpr -e 'Sxp.sxpp { 3 + 3.0 + 3.0 }'
    [:+, [:+, 3, 3.0], 3.0]

  $ ruby -rsexpr -e 'p Sxp.sxp { 3.0 + 3.0 + 3 }'
  [:+, 6.0, 3]

  $ ruby -rsexpr -e 'Sxp.sxpp { 3.0 + 3.0 * 3 }'
  12.0 # oops :slight_smile:

  $ ruby -rsexpr -e 'Sxp.sxpp { [:a] + [3.0 * 3] }'
  [:+, [:a], [9.0]]
  
  $ ruby -rsexpr -e 'Sxp.sxpp { [:a] + terms(3.42 * 3) }'
  [:+, [:a], [:terms, 10.26]]

I think the problem here is related to the fact that object classes are
preserved across the sandbox boundary, and the proc passed keeps it's
original scope. This has an effect the other way too - you'll often get
'gutted' arrays in the returned sexpr array...

It does pass the tests posted on the list, though, and for the basic
functional stuff it's probably not too bad.

(Also, Sandbox is *way cool* - thanks _why & MenTaL :). It's gotta
become part of the distribution in the near future).

# ---[sandboxed.rb]---
class Object ; alias :__instance_eval :instance_eval ; end
class Array ; alias :__each :each ; end

[Object, Kernel, Symbol, Fixnum, Bignum, Float, NilClass, FalseClass,
                         TrueClass, Hash, Array, String].__each do |clz|
  clz.class_eval do
    instance_methods.__each do |m|
      undef_method m unless /^__|^inspect$|^to_(s(?:tr)?|a(?:ry)?)$/.match(m)
    end
    def method_missing(sym, *args); [sym, self, *args]; end
    def to_ary; [self]; end # needed by every class in this world
  end
end

# A special method_missing on the main object handles 'function' calls
class << self; def method_missing(sym, *args); [sym, *args]; end; end

__instance_eval &@blk

__END__

# ---[sexpr.rb]---
require 'sandbox'

module Sxp
  class << self
    def sxp(&blk)
      sb = Sandbox.new
      sb.main.instance_variable_set(:@blk,
                              blk || raise(LocalJumpError, "No block given"))
      sb.load("#{File.dirname(__FILE__)}/sandboxed.rb")
    end

    def sxpp(&blk)
      p(r = sxp(&blk)) || r
    end
  end
end

if $0 == __FILE__
  require 'test/unit'

  class Test::Unit::TestCase
    def sxp(&blk)
      Sxp.sxpp(&blk) # use the printing version
    end
  end

  class ProvidedSxpTest < Test::Unit::TestCase
    def test_sxp_01
      assert_equal [:max, [:count, :name]], sxp{max(count(:name))}
    end

    def test_sxp_02
      assert_equal [:count, [:+, 3, 7]], sxp{count(3+7)}
    end

    def test_sxp_03
      assert_equal [:+, 3, :symbol], sxp{3+:symbol}
    end

    def test_sxp_04
      assert_equal [:+, 3, [:count, :field]], sxp{3+count(:field) }
    end

    def test_sxp_05
      assert_equal [:/, 7, :field], sxp{7/:field}
    end

    def test_sxp_06
      assert_equal [:>, :field, 5], sxp{:field > 5}
    end

    def test_sxp_07
      assert_equal 8, sxp{8}
    end

    def test_sxp_08
      assert_equal [:==, :field1, :field2], sxp{:field1 == :field2}
    end

    def test_sxp_09
      assert_raise(TypeError) { 7/:field }
    end

    def test_sxp_10
      assert_raise(NoMethodError) { 7+count(:field) }
    end

    def test_sxp_11
      assert_equal 11, 5+6
    end

    def test_sxp_12
      assert_raise(NoMethodError) { :field > 5 }
    end

    def test_sxp_13
      assert_equal [:+, 3, 'string'], sxp{3+'string'}
    end

    def test_sxp_14
      assert_equal [:abs, [:factorial, 3]], sxp{3.factorial.abs}
    end

    def test_sxp_15
      assert_raise(LocalJumpError) { sxp }
    end

    def test_sxp_16
      assert_equal 3.0, sxp{3.0}
    end

    def test_sxp_17
      assert_equal [:count, 3.0], sxp{count(3.0)}
    end

    # This test always fails right now, because string methods always get
    # called regardless. This is the same with Floats, but apparently not
    # on any immediate objects, or the standard Array / Hash classes,
    # Bignum, and so on...

···

#
    #def test_sxp_18
    # assert_equal [:+, 'longer', 'string'], sxp{'longer'+'string'}
    #end

    def test_sxp_19
      assert_equal [:+, [1,2], [:*, {3=>4}, 1100000000]], sxp{[1,2]+{3=>4}*1100000000}
    end

    def test_sxp_20
      assert_equal [:+, [1,2], [3,4]], sxp{[1,2]+[3,4]}
    end
  end

  class SanderLandSxpTest < Test::Unit::TestCase
    def test_more
      assert_equal [:==,[:^, 2, 3], [:^, 1, 1]], sxp{ 2^3 == 1^1}

      assert_equal [:==, 3.1415, 3] , sxp{3.0 + 0.1415 == 3}

      assert_equal [:|, [:==, [:+, :hello, :world], :helloworld],
        [:==, [:+, [:+, "hello", " "], "world"], "hello world"]] ,
        sxp{ (:hello + :world == :helloworld) | ('hello' + ' ' + 'world' == 'hello world') }

      assert_equal [:==, [:+, [:abs, [:factorial, 3]], [:*, [:factorial, 4], 42]],
        [:+, [:+, 4000000, [:**, 2, 32]], [:%, 2.7, 1.1]]],
        sxp{ 3.factorial.abs + 4.factorial * 42 == 4_000_000 + 2**32 + 2.7 % 1.1 }
    end
  end

  class RobinStockerSxpTest < Test::Unit::TestCase
    def test_number
      assert_equal 8, sxp { 8 }
      assert_equal [:+, 3, 4], sxp { 3 + 4 }
    end

    def test_environment
      assert_equal [:-, 10, [:count, [:*, :field, 4]]],
        sxp { 10 - count(:field * 4) }
      assert_raise(TypeError) { 7 / :field }
      assert_raise(NoMethodError) { 7 + count(:field) }
      assert_equal 11, 5 + 6
      assert_raise(NoMethodError) { :field > 5 }
    end
  end
end

__END__

--
Ross Bamford - rosco@roscopeco.REMOVE.co.uk

13

Of course not. The real question though is using ParseTree cheating, right? :wink:

Hit us with your trivial solution I say. It'll be great advertising for the project!

James Edward Gray II

···

On Sep 22, 2006, at 8:04 PM, Ryan Davis wrote:

On Sep 22, 2006, at 3:13 PM, Ruby Quiz wrote:

Your mission: Create a function named sxp() that can take a block (not a
string), and create an s-expression representing the code in the block.

Am I exempt from the quiz?

14

sxp{ a; b} => sxp{a} + sxp{b} which seems complicated for
sxp{ 4; 2} ???
sxp{ obj.meth *args } => [ :meth, <object_id:object_class>, *sxp{arg.first},
*sxp{arg.second} ...] ???

Can we avoid blocks ?
sxp{ 42.times do ....
}

Robert

···

On 9/23/06, M. Edward (Ed) Borasky <znmeb@cesmail.net> wrote:

Ruby Quiz wrote:

>
Could you write some more tests? :slight_smile:

Especially

--
Deux choses sont infinies : l'univers et la bêtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

15

Shouldn't 3 be entirely optional? =]

···

On Sat, 23 Sep 2006 07:13:37 +0900, Ruby Quiz wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

--
Jeremy Tregunna
jtregunna@blurgle.ca

16

Hi all,

Here's my solution which uses Ruby only and modifies core classes and
restores them at the end of the function. I wouldn't trust it ;).

Maybe this would be a task for Why's Sandbox library? Create a sandbox,
modify the core classes there and evaluate the blocks there. It's just
an idea, I don't know if it's possible.

Very elegant solution, much more elegant than my own. I'm thinking of
using your code to implement my desired SQL expression generation. I do
suggest blanking the SxpGenerator class first that way built-in methods
will call method_missing (which is the desired behavior).

class SxpGenerator

[SOME CODE SNIPPED as I want people to see what I wrote and not miss it in
the code.]

   def self.restore_methods(mod)
     BINARY_METHODS.each do |method|
       mod.module_eval do
         orig_method = "__orig_#{method}__"
         if method_defined? orig_method

After looking at Borris' post, where he mentioned throwing lots of
warnings, I tested your code with warnings on. You can keep your code from
generating warnings by adding one line here (in the space where this
comment is):

remove_method method

(this way, the alias_method doesn't replace an existing method, thereby
generating warnings)

           alias_method method, orig_method
           remove_method orig_method
         else
           remove_method method
         end
       end
     end
   end

end

[REST OF CODE SNIPPED]

   def test_variables_from_outside
     var=:count
     assert_equal [:-,:count,3], sxp { var-3 }
   end

This test, which your code passes, also happens to be pretty useful for my
purposes.

--Ken

···

On Tue, 26 Sep 2006 05:49:48 +0900, Robin Stocker wrote:

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I've added a signing subkey to my GPG key. Please update your keyring.

17

Hi all,

Here's my solution which uses Ruby only and modifies core classes and
restores them at the end of the function. I wouldn't trust it ;).

Maybe this would be a task for Why's Sandbox library? Create a sandbox,
modify the core classes there and evaluate the blocks there. It's just
an idea, I don't know if it's possible.

Very elegant solution, much more elegant than my own. I'm thinking of
using your code to implement my desired SQL expression generation. I do
suggest blanking the SxpGenerator class first that way built-in methods
will call method_missing (which is the desired behavior).

class SxpGenerator

[SOME CODE SNIPPED as I want people to see what I wrote and not miss it in
the code.]

   def self.restore_methods(mod)
     BINARY_METHODS.each do |method|
       mod.module_eval do
         orig_method = "__orig_#{method}__"
         if method_defined? orig_method

After looking at Borris' post, where he mentioned throwing lots of
warnings, I tested your code with warnings on. You can keep your code from
generating warnings by adding one line here (in the space where this
comment is):

remove_method method

(this way, the alias_method doesn't replace an existing method, thereby
generating warnings)

           alias_method method, orig_method
           remove_method orig_method
         else
           remove_method method
         end
       end
     end
   end

end

[REST OF CODE SNIPPED]

   def test_variables_from_outside
     var=:count
     assert_equal [:-,:count,3], sxp { var-3 }
   end

This test, which your code passes, also happens to be pretty useful for my
purposes.

--Ken

···

On Tue, 26 Sep 2006 05:49:48 +0900, Robin Stocker wrote:

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I've added a signing subkey to my GPG key. Please update your keyring.

18

And you should have no clue why, since you're not overriding core methods
anywhere. For people whose solutions override core
methods, these tests are meant to ensure that things still operate
normally outside the sxp call.

--Ken

···

On Mon, 25 Sep 2006 07:23:40 +0900, Ryan Davis wrote:

     def test_ihavenocluewhy
       assert_equal 11, 5 + 6
       assert_raise(TypeError) { 7 / :field }
       assert_raise(NoMethodError) { 7+count(:field) }
       assert_raise(NoMethodError) { :field > 5 }
     end

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I've added a signing subkey to my GPG key. Please update your keyring.

19

Is there a way to make your code pass this test (even though it's not
strictly turning the parse tree into an s-expression anymore?)
     
     def test_varaible
  var=:field
  assert_equal [:count, :field], sxp{ count(var) }
     end

···

On Mon, 25 Sep 2006 23:15:47 +0900, Dominik Bathon wrote:

Here is my solution.

It uses RubyNode (which is available as gem now, see
http://rubynode.rubyforge.org/\) to access the block's body node and then
transforms that body node into the s-expression.

It is pretty similar to Ryan's ParseTree solution, but supports some
additional node types and has some more tests.

Dominik

require "rubynode"

class Node2Sexp
   # (transformed) nodes are arrays, that look like:
   # [:type, attribute hash or array of nodes]
   def to_sexp(node)
     node && send("#{node.first}_to_sexp", node.last)
   end

   # fixed argument lists are represented as :array nodes, e.g.
   # [:array, [argnode1, argnode2, ...]]
   def process_args(args_node)
     return unless args_node
     if args_node.first == :array
       args_node.last.map { |node| to_sexp(node) }
     else
       raise "variable arguments not allowed"
     end
   end

   # :call nodes: method call with explicit receiver:
   # nil.foo => [:call, {:args=>false, :mid=>:foo, :recv=>[:nil, {}]}]
   # nil == nil =>
   # [:call, {:args=>[:array, [[:nil, {}]]], :mid=>:==, :recv=>[:nil, {}]}]
   def call_to_sexp(hash)
     [hash[:mid], to_sexp(hash[:recv]), *process_args(hash[:args])]
   end

   # :fcall nodes: function call (no explicit receiver):
   # foo() => [:fcall, {:args=>false, :mid=>:foo}]
   # foo(nil) => [:fcall, {:args=>[:array, [[:nil, {}]]], :mid=>:foo]
   def fcall_to_sexp(hash)
     [hash[:mid], *process_args(hash[:args])]
   end

   # :vcall nodes: function call that looks like variable
   # foo => [:vcall, {:mid=>:foo}]
   alias vcall_to_sexp fcall_to_sexp

   # :lit nodes: literals
   # 1 => [:lit, {:lit=>1}]
   # :abc => [:lit, {:lit=>:abc}]
   def lit_to_sexp(hash)
     hash[:lit]
   end

   # :str nodes: strings without interpolation
   # "abc" => [:str, {:lit=>"abc"}]
   alias str_to_sexp lit_to_sexp

   def nil_to_sexp(hash) nil end
   def false_to_sexp(hash) false end
   def true_to_sexp(hash) true end
end

def sxp(&block)
   body = block.body_node
   return nil unless body
   Node2Sexp.new.to_sexp(body.transform)
end

if $0 == __FILE__ then
   require 'test/unit'

   class TestQuiz < Test::Unit::TestCase
     def test_sxp_nested_calls
       assert_equal [:max, [:count, :name]], sxp{max(count(:name))}
     end

     def test_sxp_vcall
       assert_equal [:abc], sxp{abc}
     end

     def test_sxp_call_plus_eval
       assert_equal [:count, [:+, 3, 7]], sxp{count(3+7)}
     end

     def test_sxp_call_with_multiple_args
       assert_equal [:count, 3, 7], sxp{count(3,7)}
     end

     def test_sxp_binarymsg_mixed_1
       assert_equal [:+, 3, :symbol], sxp{3+:symbol}
     end

     def test_sxp_binarymsg_mixed_call
       assert_equal [:+, 3, [:count, :field]], sxp{3+count(:field)}
     end

     def test_sxp_binarymsg_mixed_2
       assert_equal [:/, 7, :field], sxp{7/:field}
     end

     def test_sxp_binarymsg_mixed_3
       assert_equal [:>, :field, 5], sxp{:field > 5}
     end

     def test_sxp_lits
       assert_equal 8, sxp{8}
     end

     def test_sxp_true_false_nil
       assert_equal [:+, true, false], sxp{true+false}
       assert_equal nil, sxp{nil}
     end

     def test_sxp_empty
       assert_equal nil, sxp{}
     end

     def test_sxp_binarymsg_syms
       assert_equal [:==, :field1, :field2], sxp{:field1 == :field2 }
     end

     def test_sxp_from_sander_dot_land_at_gmail_com
       assert_equal [:==,[:^, 2, 3], [:^, 1, 1]], sxp{ 2^3 == 1^1}
       assert_equal [:==, [:+, 3.0, 0.1415], 3], sxp{3.0 + 0.1415 == 3}

       assert_equal([:|,
                     [:==, [:+, :hello, :world], :helloworld],
                     [:==, [:+, [:+, "hello", " "], "world"], "hello
world"]] ,
                    sxp {
                      (:hello + :world == :helloworld) |
                      ('hello' + ' ' + 'world' == 'hello world')
                    })

       assert_equal [:==, [:+, [:abs, [:factorial, 3]], [:*, [:factorial,
4], 42]],
                      [:+, [:+, 4000000, [:**, 2, 32]], [:%, 2.7, 1.1]]],
       sxp{ 3.factorial.abs + 4.factorial * 42 == 4_000_000 + 2**32 + 2.7
% 1.1 }
     end

     def test_ihavenocluewhy
       assert_equal 11, 5 + 6
       assert_raise(TypeError) { 7 / :field }
       assert_raise(NoMethodError) { 7+count(:field) }
       assert_raise(NoMethodError) { :field > 5 }
     end
   end
end

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I've added a signing subkey to my GPG key. Please update your keyring.

20

Is there a way to make your code pass this test (even though it's not
strictly turning the parse tree into an s-expression anymore?)
     
     def test_varaible
  var=:field
  assert_equal [:count, :field], sxp{ count(var) }
     end

···

On Mon, 25 Sep 2006 23:15:47 +0900, Dominik Bathon wrote:

Here is my solution.

It uses RubyNode (which is available as gem now, see
http://rubynode.rubyforge.org/\) to access the block's body node and then
transforms that body node into the s-expression.

It is pretty similar to Ryan's ParseTree solution, but supports some
additional node types and has some more tests.

Dominik

require "rubynode"

class Node2Sexp
   # (transformed) nodes are arrays, that look like:
   # [:type, attribute hash or array of nodes]
   def to_sexp(node)
     node && send("#{node.first}_to_sexp", node.last)
   end

   # fixed argument lists are represented as :array nodes, e.g.
   # [:array, [argnode1, argnode2, ...]]
   def process_args(args_node)
     return unless args_node
     if args_node.first == :array
       args_node.last.map { |node| to_sexp(node) }
     else
       raise "variable arguments not allowed"
     end
   end

   # :call nodes: method call with explicit receiver:
   # nil.foo => [:call, {:args=>false, :mid=>:foo, :recv=>[:nil, {}]}]
   # nil == nil =>
   # [:call, {:args=>[:array, [[:nil, {}]]], :mid=>:==, :recv=>[:nil, {}]}]
   def call_to_sexp(hash)
     [hash[:mid], to_sexp(hash[:recv]), *process_args(hash[:args])]
   end

   # :fcall nodes: function call (no explicit receiver):
   # foo() => [:fcall, {:args=>false, :mid=>:foo}]
   # foo(nil) => [:fcall, {:args=>[:array, [[:nil, {}]]], :mid=>:foo]
   def fcall_to_sexp(hash)
     [hash[:mid], *process_args(hash[:args])]
   end

   # :vcall nodes: function call that looks like variable
   # foo => [:vcall, {:mid=>:foo}]
   alias vcall_to_sexp fcall_to_sexp

   # :lit nodes: literals
   # 1 => [:lit, {:lit=>1}]
   # :abc => [:lit, {:lit=>:abc}]
   def lit_to_sexp(hash)
     hash[:lit]
   end

   # :str nodes: strings without interpolation
   # "abc" => [:str, {:lit=>"abc"}]
   alias str_to_sexp lit_to_sexp

   def nil_to_sexp(hash) nil end
   def false_to_sexp(hash) false end
   def true_to_sexp(hash) true end
end

def sxp(&block)
   body = block.body_node
   return nil unless body
   Node2Sexp.new.to_sexp(body.transform)
end

if $0 == __FILE__ then
   require 'test/unit'

   class TestQuiz < Test::Unit::TestCase
     def test_sxp_nested_calls
       assert_equal [:max, [:count, :name]], sxp{max(count(:name))}
     end

     def test_sxp_vcall
       assert_equal [:abc], sxp{abc}
     end

     def test_sxp_call_plus_eval
       assert_equal [:count, [:+, 3, 7]], sxp{count(3+7)}
     end

     def test_sxp_call_with_multiple_args
       assert_equal [:count, 3, 7], sxp{count(3,7)}
     end

     def test_sxp_binarymsg_mixed_1
       assert_equal [:+, 3, :symbol], sxp{3+:symbol}
     end

     def test_sxp_binarymsg_mixed_call
       assert_equal [:+, 3, [:count, :field]], sxp{3+count(:field)}
     end

     def test_sxp_binarymsg_mixed_2
       assert_equal [:/, 7, :field], sxp{7/:field}
     end

     def test_sxp_binarymsg_mixed_3
       assert_equal [:>, :field, 5], sxp{:field > 5}
     end

     def test_sxp_lits
       assert_equal 8, sxp{8}
     end

     def test_sxp_true_false_nil
       assert_equal [:+, true, false], sxp{true+false}
       assert_equal nil, sxp{nil}
     end

     def test_sxp_empty
       assert_equal nil, sxp{}
     end

     def test_sxp_binarymsg_syms
       assert_equal [:==, :field1, :field2], sxp{:field1 == :field2 }
     end

     def test_sxp_from_sander_dot_land_at_gmail_com
       assert_equal [:==,[:^, 2, 3], [:^, 1, 1]], sxp{ 2^3 == 1^1}
       assert_equal [:==, [:+, 3.0, 0.1415], 3], sxp{3.0 + 0.1415 == 3}

       assert_equal([:|,
                     [:==, [:+, :hello, :world], :helloworld],
                     [:==, [:+, [:+, "hello", " "], "world"], "hello
world"]] ,
                    sxp {
                      (:hello + :world == :helloworld) |
                      ('hello' + ' ' + 'world' == 'hello world')
                    })

       assert_equal [:==, [:+, [:abs, [:factorial, 3]], [:*, [:factorial,
4], 42]],
                      [:+, [:+, 4000000, [:**, 2, 32]], [:%, 2.7, 1.1]]],
       sxp{ 3.factorial.abs + 4.factorial * 42 == 4_000_000 + 2**32 + 2.7
% 1.1 }
     end

     def test_ihavenocluewhy
       assert_equal 11, 5 + 6
       assert_raise(TypeError) { 7 / :field }
       assert_raise(NoMethodError) { 7+count(:field) }
       assert_raise(NoMethodError) { :field > 5 }
     end
   end
end

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I've added a signing subkey to my GPG key. Please update your keyring.