[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Code to S-Exp (#95

James Gray

9/22/2006 10:14:00 PM

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

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://cls...) 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.)
23 Answers

Ryan Davis

9/23/2006 1:05:00 AM

0


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?

James Gray

9/23/2006 1:14:00 AM

0

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?

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

9/23/2006 2:02:00 AM

0

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.rub...
>
> 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://cls...) 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? :)

Sander Land

9/23/2006 10:52:00 AM

0

On 9/23/06, Robert Dober <robert.dober@gmail.com> wrote:
> 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} ...] ???

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

Ryan Davis

9/23/2006 11:27:00 AM

0


On Sep 22, 2006, at 6:13 PM, James Edward Gray II wrote:

> On Sep 22, 2006, at 8:04 PM, Ryan Davis wrote:
>> Am I exempt from the quiz?
>
> 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

9/23/2006 4:06:00 PM

0

Ryan Davis wrote:
>
> On Sep 22, 2006, at 6:13 PM, James Edward Gray II wrote:
>
>> On Sep 22, 2006, at 8:04 PM, Ryan Davis wrote:
>>> Am I exempt from the quiz?
>>
>> 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...
>
>
>
I was going to write it in Scheme, use a Scheme-to-C compiler, and then
interface the C code to Ruby.

<ducking>

James Gray

9/23/2006 5:48:00 PM

0

On Sep 23, 2006, at 6:27 AM, Ryan Davis wrote:

>
> On Sep 22, 2006, at 6:13 PM, James Edward Gray II wrote:
>
>> On Sep 22, 2006, at 8:04 PM, Ryan Davis wrote:
>>> Am I exempt from the quiz?
>>
>> Of course not. The real question though is using ParseTree
>> cheating, right? ;)
>
> 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

M. Edward (Ed) Borasky

9/24/2006 4:32:00 PM

0

Robert Dober wrote:
>
> 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 E. Fulton

9/24/2006 8:22:00 PM

0

M. Edward (Ed) Borasky wrote:
>
> 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

9/24/2006 8:56:00 PM

0

Hal Fulton wrote:
> M. Edward (Ed) Borasky wrote:
>>
>> 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
>
>
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...