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

[Boris Prinz]

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(countname))}
assert_equal [:count, [:+, 3, 7]], sxp{count(3+7)}
assert_equal [:+, 3, :symbol], sxp{3+:symbol}
assert_equal [:+, 3, [:count, :field]], sxp{3+countfield)}
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+countfield)}
assert_equal 11, 5+6
assert_raises(NoMethodError) {pfield > 5)}
end

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

 

[Ken Bloom]

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(countname))} => [:max, [:count, :name]]
sxp{count(3+7)} => [:count, 10] or [:count, [:+, 3, 7]]
sxp{3+:symbol} => [:+, 3, :symbol]
sxp{3+countfield)} => [:+, 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+countfield) => 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_missingcoerce,other)
end
end
def method_missing(name, *args)
if caller[-2]=~/in `sxp'/
SExpr.new(name,self,*args)
else
super
end
end
alias_method ld_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(countname))}
sxp{count(3+7)}
sxp{3+:symbol}
sxp{3+countfield)}
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+countfield) rescue "NoMethodError"
5+6
:field > 5 rescue "NoMethodError"
end;

 

[Ken Bloom]

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(countname))} => [:max, [:count, :name]]
sxp{count(3+7)} => [:count, 10] or [:count, [:+, 3, 7]]
sxp{3+:symbol} => [:+, 3, :symbol]
sxp{3+countfield)} => [:+, 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+countfield) => 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_missingcoerce,other)
end
end
def method_missing(name, *args)
if caller[-2]=~/in `sxp'/
SExpr.new(name,self,*args)
else
super
end
end
alias_method ld_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(countname))}
sxp{count(3+7)}
sxp{3+:symbol}
sxp{3+countfield)}
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+countfield) rescue "NoMethodError"
5+6
:field > 5 rescue "NoMethodError"
end;

 

[Jeremy Tregunna]

Shouldn't 3 be entirely optional? =]

 

[James Edward Gray II]

Shouldn't 3 be entirely optional? =]

Sorry, it's required.

James Edward Gray II

 

[Robin Stocker]

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(countname)) }
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 + countfield) }
end

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

end

 

[Ken Bloom]

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

 

[Ken Bloom]

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

 

[Ken Bloom]

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

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

 

[Ken Bloom]

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

sxp {3.meth(*[1,2,3]) } => [:meth, 3, 1, 2, 3] for me, don't know
about the other ones.

Here are the tests I'm using now:
http://pastie.caboo.se/14546

Here's a few important ones that I just thought of. This should make the
problem much harder:

sxp{ not :field } => [:not, :field]
sxp{ :a != :b } => [:"!=", :a, :b]

var=:field
sxp{ :count(var) } => [:count, :field]

 

[Ken Bloom]

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(countname))}
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+countfield)}
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+countfield) }
assert_raise(NoMethodError) { :field > 5 }
end
end
end

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

 

[Ken Bloom]

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(countname))}
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+countfield)}
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+countfield) }
assert_raise(NoMethodError) { :field > 5 }
end
end
end

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

 

[Dominik Bathon]

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=3D:field
assert_equal [:count, :field], sxp{ count(var) }
end

Yes that is possible by using eval and the block as binding. I implement=
ed =

it for lvars and dvars, but it would be possible to do the same for =

instance variables, class variables, ...

I also implemented :not nodes as you suggested in the other mail.

Below is the diff and also the complete solution again.

Dominik


--- sexp_1.rb 2006-09-27 19:30:05.000000000 +0200
+++ sexp.rb 2006-09-27 19:52:02.000000000 +0200
@@ -2,6 +2,10 @@
require "rubynode"

class Node2Sexp
+ def initialize(binding)
+ @binding =3D binding
+ end
+
# (transformed) nodes are arrays, that look like:
# [:type, attribute hash or array of nodes]
def to_sexp(node)
@@ -52,12 +56,33 @@
def nil_to_sexp(hash) nil end
def false_to_sexp(hash) false end
def true_to_sexp(hash) true end
+
+ # :lvar nodes: local variables
+ # var =3D> [:lvar, {:cnt=3D>3, :vid=3D>:var}] # cnt is the index in t=
he lvar =

table
+ def lvar_to_sexp(hash)
+ eval(hash[:vid].to_s, @binding)
+ end
+ # :dvar nodes: block local variables
+ # var =3D> [:dvar, {:vid=3D>:var}]
+ alias dvar_to_sexp lvar_to_sexp
+
+ # :not nodes: boolean negation
+ # not :field =3D> [:not, {:body=3D>[:lit, {:lit=3D>:field}]}]
+ # !:field =3D> [:not, {:body=3D>[:lit, {:lit=3D>:field}]}]
+ def not_to_sexp(hash)
+ body =3D to_sexp(hash[:body])
+ if Array =3D=3D=3D body && body[0] =3D=3D :=3D=3D && body.size =3D=3D=
3
+ [:"!=3D", body[1], body[2]]
+ else
+ [:not, body]
+ end
+ end
end

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

if $0 =3D=3D __FILE__ then
@@ -113,6 +138,20 @@
assert_equal [:=3D=3D, :field1, :field2], sxp{:field1 =3D=3D :fi=
eld2 }
end

+ def test_sxp_variables
+ lvar =3D :field # local variable
+ assert_equal [:count, :field], sxp{ count(lvar) }
+ proc {
+ dvar =3D :field2 # dynavar (block local variable)
+ assert_equal [:=3D=3D, :field, :field2], sxp{ lvar =3D=3D dvar =
}
+ }.call
+ end
+
+ def test_sxp_not
+ assert_equal [:not, :field], sxp{ not :field }
+ assert_equal [:"!=3D", :a, :b], sxp{ :a !=3D :b }
+ end
+
def test_sxp_from_sander_dot_land_at_gmail_com
assert_equal [:=3D=3D,[:^, 2, 3], [:^, 1, 1]], sxp{ 2^3 =3D=3D 1=
^1}
assert_equal [:=3D=3D, [:+, 3.0, 0.1415], 3], sxp{3.0 + 0.1415 =3D=
=3D 3}

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

require "rubynode"

class Node2Sexp
def initialize(binding)
@binding =3D binding
end

# (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 =3D=3D :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 =3D> [:call, {:args=3D>false, :mid=3D>:foo, :recv=3D>[:nil,=
{}]}]
# nil =3D=3D nil =3D>
# [:call, {:args=3D>[:array, [[:nil, {}]]], :mid=3D>:=3D=3D, :recv=3D=

[: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() =3D> [:fcall, {:args=3D>false, :mid=3D>:foo}]
# foo(nil) =3D> [:fcall, {:args=3D>[:array, [[:nil, {}]]], :mid=3D>:f=
oo]
def fcall_to_sexp(hash)
[hash[:mid], *process_args(hash[:args])]
end

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

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

# :str nodes: strings without interpolation
# "abc" =3D> [:str, {:lit=3D>"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

# :lvar nodes: local variables
# var =3D> [:lvar, {:cnt=3D>3, :vid=3D>:var}] # cnt is the index in t=
he lvar =

table
def lvar_to_sexp(hash)
eval(hash[:vid].to_s, @binding)
end
# :dvar nodes: block local variables
# var =3D> [:dvar, {:vid=3D>:var}]
alias dvar_to_sexp lvar_to_sexp

# :not nodes: boolean negation
# not :field =3D> [:not, {:body=3D>[:lit, {:lit=3D>:field}]}]
# !:field =3D> [:not, {:body=3D>[:lit, {:lit=3D>:field}]}]
def not_to_sexp(hash)
body =3D to_sexp(hash[:body])
if Array =3D=3D=3D body && body[0] =3D=3D :=3D=3D && body.size =3D=3D=
3
[:"!=3D", body[1], body[2]]
else
[:not, body]
end
end
end

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

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

class TestQuiz < Test::Unit::TestCase
def test_sxp_nested_calls
assert_equal [:max, [:count, :name]], sxp{max(countname))}
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+countfield)}
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 [:=3D=3D, :field1, :field2], sxp{:field1 =3D=3D :fie=
ld2 }
end

def test_sxp_variables
lvar =3D :field # local variable
assert_equal [:count, :field], sxp{ count(lvar) }
proc {
dvar =3D :field2 # dynavar (block local variable)
assert_equal [:=3D=3D, :field, :field2], sxp{ lvar =3D=3D dvar =
}
}.call
end

def test_sxp_not
assert_equal [:not, :field], sxp{ not :field }
assert_equal [:"!=3D", :a, :b], sxp{ :a !=3D :b }
end

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

assert_equal([:|,
[:=3D=3D, [:+, :hello, :world], :helloworld],
[:=3D=3D, [:+, [:+, "hello", " "], "world"], "hello=
=

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

assert_equal [:=3D=3D, [:+, [:abs, [:factorial, 3]], [:*, [:fact=
orial, =

4], 42]],
[:+, [:+, 4000000, [:**, 2, 32]], [:%, 2.7, 1.1]]]=
,
sxp{ 3.factorial.abs + 4.factorial * 42 =3D=3D 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+countfield) }
assert_raise(NoMethodError) { :field > 5 }
end
end
end