From: Ruby Quiz <james@...>
Date: 2006-09-23T07:13:37+09:00
Subject: [QUIZ] Code to S-Exp (#95)

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