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!
> 
> 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
#
#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/