I'm exploiting Ruby references

Hi,

I think I’ve found a nice example that shows the power of Ruby
usually not making copies of objects. But while I was trying to
take it further, I just bumped into a limitation: as far as I know it’s
impossible to replace an object with any other and changing all
the references pointing to the new one at once. It is possible to do
it with #replace(other_obj) only if the type of the new object is still
an
Array, Hash or String. But what if I want to change the underlying
type?

Let me explain what I’m trying to do in a more details:

I’m dealing with an equation system in my Ruby code, and
references are very useful in my case. Suppose that we have an
equation system that always has a variable on the left hand side,
and an expression on the right hand side, and variables have maximum
one equations where they appear on the left hand side. So, it is
straightforward to represent this in a Hash, like this:

eq = {
“k”=>12,
“y”=>[“k”, :+, 1],
“a”=>“y”,
“x”=>[“y”, :*, [“a”, :+, “k”, :+, 1]]
}

This represents the equation system

k = 12
y = k + 1
a = y
x = y * (a + k + 1)

Variables are always Strings, operators are Symbols, and compound
statements
are represented by Arrays. Now suppose that I want to substitute values
in
one
equation from another. For instance let’s replace the variable “y” in
the
equation
x = y * (…) with k+1 from the second equation (y = k+1):

eq[‘x’][0] = eq[‘y’]

The equation system changes to this:

{
“k”=>12,
“y”=>[“k”, :+, 1],
“a”=>“y”,
“x”=>[[“k”, :+, 1], :*, [“a”, :+, “k”, :+, 1]]
}

The wonderful thing in this is that instead of having a copy of it the
expression of k+1
it’s now referenced by two equations. The befit of this is that if I do
further substitutions
on the y = k+1 equation, I’ll have the modifications in the x =…
equation
too. When we
replace “k” with it’s value from the first equation:

eq[‘y’][0] = eq[‘k’] # eq[‘k’] is 12

we’ll get this

{
“k”=>12,
“y”=>[12, :+, 1],
“a”=>“y”,
“x”=>[[12, :+, 1], :*, [“a”, :+, “k”, :+, 1]]
}

Can you see the number 12 appering in the last equation? :slight_smile: Awesome!
It’s
exactly what I
wanted to get.

So far so good.

Now let’s do some simplifications here. Everybody knows that 12+1 is
13,
so let’s replace
eq[‘y’] with 13. Well, the problem is, that we can’t, because eq[‘y’] =
13
will break the
carefully built reference system between the equations. The new value
of
eq[‘y’] will be
13, of course, but the other references (the one from the last equation)
pointing to the
array [12, :+, 1] will still hold the old reference to the array.

There’s one ugly solution however. I can use Array#replace on eq[‘y’]
to
replace it with
another Array, for instance with the array [13]. ([13] is an array
with a
single element that is
the numbe 13) The array [13] is not exactly 13, but very similar, and I
don’t know any
better solution at the moment:

eq[‘y’].replace [13]

This will do the trick, but [13] is not very nice, it’s like the numbe
13
in totally unnecessary
brackets:

{“k”=>12, “y”=>[13], “a”=>“y”, “x”=>[[13], :*, [“a”, :+, “k”, :+, 1]]}

I don’t want to represent 13 as [13]. What I really would love to do it
to
replace an
object (in this case the array [12, :+, 1]) with any other object (in
this
case the Fixnum
13) in a way that changes all the references from the old object to the
new
one. Just
like #replace does if the new object has the same type as the old one
(String, Array or
Hash).

Array#replace does not work with non-Array arguments, but it would be
great
to force
it to work somehow. Is it somehow possible?

u.

On Sat, Nov 24, 2012 at 2:39 AM, Nokan E. [email protected]
wrote:

I think I’ve found a nice example that shows the power of Ruby
usually not making copies of objects. But while I was trying to
take it further, I just bumped into a limitation: as far as I know it’s
impossible to replace an object with any other and changing all
the references pointing to the new one at once. It is possible to do
it with #replace(other_obj) only if the type of the new object is still an
Array, Hash or String. But what if I want to change the underlying
type?

Smalltalk supports this with the become method. Here’s one ruby
implementation I found on github: GitHub - cout/become: `Object#become` will swap two Ruby objects, similar to Smalltalk's become.

Let me explain what I’m trying to do in a more details:
[…]

The equation system changes to this:
{
“k”=>12,
“y”=>[“k”, :+, 1],
“a”=>“y”,
“x”=>[[“k”, :+, 1], :*, [“a”, :+, “k”, :+, 1]]
}

If you’re doing this sort of symbolic equation manipulation I’d
actually advise you to express an equation as a tree, and implement
some explicit tree rewriting code for variable substitution and
simplifications. It’s a bit of extra work up-front, but you’ll have
complete control of the way things are done.

Your code is conceptually almost there - a minimal tweak without
resorting to new datatypes would be to have the rule that values
(numbers or variables) are always arrays, and that an operator
combines two arrays to give a third array. Your use of ruby references
will then work happily enough - one of your current problems is that
fixnums are immediate values, so there is no way for two variables to
point to the same fixnum.

martin

Smalltalk supports this with the become method.

Wow! become is a great thing. Why don’t we have a built-in become in
Ruby?
Or a general replace on every object? The latter would be a bit more
general,
because swapping to objects (that’s what become does if I’m right) could
be
done with three replaces.

Here’s one ruby

implementation I found on github: GitHub - cout/become: `Object#become` will swap two Ruby objects, similar to Smalltalk's become.

Unfortunately it does not work for me.

irb(main):023:0> x.become y
irb: symbol lookup error: /…/become.so: undefined symbol: STR2CSTR
$ _

If you’re doing this sort of symbolic equation manipulation I’d
actually advise you to express an equation as a tree,

It is actually a tree represented by arrays and subtrees by
array elements in the array.

and implement
some explicit tree rewriting code for variable substitution and
simplifications. It’s a bit of extra work up-front, but you’ll have
complete control of the way things are done.

The thing is that I have to solve a huge equation system with more
than 60 000 equations, and I’m trying to keep the memory footprint
of the whole thing as low as possible. The lexer already produces
arrays in a similar format shown in my examples, and references
make substitution “parallel” on different equations. (It’s not really
parallel, but thanks to references I can make substitutions in one
equation, and it also happens in many other. I don’t want to build
custom classes around it, that would just slow down things, and
generate unnecessary metadata.

values
(numbers or variables) are always arrays, and that an operator
combines two arrays to give a third array. Your use of ruby references
will then work happily enough -

Yes, that is my “rescue” idea too. It is just not very nice to have
things in equations like [13], or what’s worse [[[[13]]]], which just
means 13. My simplifier (which is at the moment recursive) has to
dig through these extra layers.

one of your current problems is that

fixnums are immediate values, so there is no way for two variables to
point to the same fixnum.

Oh, yes, you are right, but that’s just because my example was wrong.
I can deal with that. (I can represent numbers as strings, or create a
wrapper class around numbers to solve this.) My main problem was
to figure out how to replace an object with more than one references
to it and access the new object via all the original references, even if
the new object has a different type. (The Fixnum 13 was an unlucky
chice. :slight_smile:

Just as an aside, I’m not sure of the full scope of your program, but
you might find Pure interesting.

http://code.google.com/p/pure-lang/

martin

Hei Nokan,

Here’s what you could do: Put a proxy object between the referencing
code and the object referenced. The proxy object could implement a
#become that simply replaces the object proxied to.

This way everyone points to the proxy object which stays the same, no
matter what object it points to, so references needn’t change.

Pseudo-Code:

class Proxy < BlankSlate
def method_missing(sym, *args, &block)
@obj.send(sym, *args, &block)
end
def respond_to?(sym)
@obj.respond_to?(sym)
end
def become(obj)
@obj = obj
end
end

More complex implementations are possible if you have more design
constraints - this is just the simplest thing that could work.

regards,
kaspar