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

[Ruby Quiz]

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.)

 

[Ryan Davis]

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?

 

[James Edward Gray II]

Am I exempt from the quiz?

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

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

James Edward Gray II

 

[M. Edward (Ed) Borasky]

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.)

Could you write some more tests?

 

[Sander Land]

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

 

[Ryan Davis]

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

That is up to you. I've spent approx 30 minutes on this so far and
all the current tests pass. I will second the vote that more tests
would be appreciated.

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

I'm wondering how many others do the same thing...

 

[M. Edward (Ed) Borasky]

That is up to you. I've spent approx 30 minutes on this so far and all
the current tests pass. I will second the vote that more tests would be
appreciated.


I'm wondering how many others do the same thing...

I was going to write it in Scheme, use a Scheme-to-C compiler, and then
interface the C code to Ruby.

<ducking>

 

[James Edward Gray II]

That is up to you.

I'm not really about restrictions. If a quiz can be easily solved
using a library, I say good job knowing which library to use! When
you post your solution, others will learn too. That's a good thing.

I'm pretty sure someone will solve it without ParseTree, which will
make for a fun comparison.

James Edward Gray II

 

[James Britt]

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

What about using the sexp library?

gem install -r sexp


http://www.artima.com/rubycs/articles/patterns_sexp_dsls3.html

 

[James Edward Gray II]

What about using the sexp library?

gem install -r sexp

Fine with me. Code it up and don't forget to brag about how little
time it took.

James Edward Gray II

 

[M. Edward (Ed) Borasky]

you see when the scales fall from the eyes the world can be seen in an
amazingly clear light.
And that is thanks to you Ed.

First he was typing, than he was ducking!

Modestly I suggest to call Ed the creator of ducktyping, it is second
nature
to me to step back.

Robert

-- My psy is a rich man.

Speaking of duck typing, the first time I heard the phrase "walks like a
duck, quacks like a duck ..." was way back when the leader of the
Republican party in the Senate was a man named Everett Dirksen. At one
point there was a debate about whether something was or was not a tax,
and my recollection is that Dirksen used the duck phrase to claim that
it was, in fact, a tax.

"Put it on my *bill*? What kind of duck do you think I am?"

 

[Hal Fulton]

Speaking of duck typing, the first time I heard the phrase "walks like a
duck, quacks like a duck ..." was way back when the leader of the
Republican party in the Senate was a man named Everett Dirksen. At one
point there was a debate about whether something was or was not a tax,
and my recollection is that Dirksen used the duck phrase to claim that
it was, in fact, a tax.

The first time I heard the phrase was in 1980 or '81 when my friend
Jamie used it to me. I *think* that was long after Dirksen's time,
but I'm not much on history.


Hal

 

[M. Edward (Ed) Borasky]

The first time I heard the phrase was in 1980 or '81 when my friend
Jamie used it to me. I *think* that was long after Dirksen's time,
but I'm not much on history.


Hal

Well, it turns out Dirksen most likely got it from Richard Cardinal
Cushing -- no telling where Cushing got it from:

http://www.bartleby.com/73/1278.html

 

[Ryan Davis]

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.senddefine_method, name, self)
ProcStoreTmp.new.method(name)
end

def to_sexp
body = self.to_method.to_sexp[2][1..-1]
[roc, *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(countname))}
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+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_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

 

[fprimus]

The first time I heard the phrase was in 1980 or '81 when my friend
Jamie used it to me. I *think* that was long after Dirksen's time,
but I'm not much on history.

I thought it came from:

"If it looks like a duck, walks like a duck, and quacks like a duck,
it's probably a duck." - Senator Joseph McCarthy, in a 1952 speech,
suggesting a method for identifying communists and communist sympathizers.

Referenced at http://www.gantthead.com/content/articles/86476.cfm

Maybe there was an even earlier reference.

-flp

--

Music: http://www.myspace.com/acidredux

Links: http://del.icio.us/furlan

Home: http://thispaceavailable.uxb.net/index.html

We are here to laugh at the odds and live our lives so well that Death
will tremble to take us.
-- Charles Bukowski

 

[Ryan Davis]

The first time I heard the phrase was in 1980 or '81 when my friend
Jamie used it to me. I *think* that was long after Dirksen's time,
but I'm not much on history.

I thought it came from: [snip... who cares?]

OT Guys... OT. Instead of polluting the quiz's thread, change the
subject.

 

[Ben Bleything]

OT Guys... OT. Instead of polluting the quiz's thread, change the
subject.

And compose a new message and copy/paste whatever you're quoting, or
otherwise fix your headers, because otherwise MUAs that (correctly)
thread based on In-Reply-To: or References: will keep your message in
the thread you're splitting from...

Ben

 

[Dominik Bathon]

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 =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
end

def sxp(&block)
body =3D block.body_node
return nil unless body
Node2Sexp.new.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_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

 

[Sander Land]

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

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_methodmethod_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

 

[James Edward Gray II]

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

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