XST: Embedded Scope Transformation
A New Requirement
Experiences with Scope Transformation, ShiftedRecord, and the thinking that was described in the preceding article lead me to state a new requirement:
Rather than representing Scope Transformation as an operation of its own, producing a new set, Scope Transformation should be an "embedded" characteristic of a set, causing the set to produce its elements with differing scopes than it otherwise would.
I want to be clear up front that I’m not certain about this new idea, but it seems to me to be a good one. It’s entirely possible to build a ScopeTransform set that acts like a “view” on another set. The one we wrote a few articles back works like that, and it’s not entirely bad. But it seems to me that our more physical sets may want to do their own iteration rather than be accessed randomly. So I’m going to do a quick experiment with embedding Scope Transformation right inside our main set type, XSet.
Reviewing the Code
Take a look at the XSet code with me. I’ll highlight the bits that jump out at me as interesting in this context.
class XSet
include Enumerable
attr_reader :contents
def initialize(element_length, contents, rank=2)
@element_length = element_length
@contents = contents
@rank = rank
end
def each
for scope in element_range
yield ScopedElement.new(element(scope), scope)
end
end
def restrict(selector)
matching_scopes = []
each do | scoped_element |
if selector.matches(scoped_element)
matching_scopes << scoped_element.scope
end
end
ScopeTransform.new(self, matching_scopes)
end
def matches(a_scoped_element)
any? { | scoped_element |
match(a_scoped_element, scoped_element)
}
end
def match(my_scoped_element, selector_scoped_element)
selector_scoped_element.element.subset?(my_scoped_element.element)
end
def subset?(larger_set)
element_range.all? { | scope |
larger_set.contains?(element(scope), scope)
}
end
# def subset? set
# each do | se |
# if ( set.element(se.scope) != se.element )
# return false
# end
# end
# return true
# end
def element(scope)
element_contents = @contents[scope*@element_length,@element_length]
if (@rank > 1)
return XSet.new(1,element_contents, self.rank-1)
else
return element_contents
end
end
def contains?(an_element, scope)
element(scope) == an_element
end
def element_range
0...cardinality
end
def cardinality
@contents.length / @element_length
end
def rank
@rank
end
The methods :each and :element are surely impacted by any Scope Transform that is in effect, in that they must produce and respond to the mapped scopes rather than the ones in the base set. The method :cardinality is interesting because it is possible for a Scope Transform to change the cardinality of a set (its number of records), by mapping some records completely out of existence. Review the ScopeTransformTest tests – they do that.
Cardinality looks like a problem to me, in that we really don’t know the cardinality of a set given just a Scope Transform on it. If the set is a vector, however, the cardinality of the result is the cardinality of the map, I believe. That is, if the map only maps three elements from the set, that’s how many records will be in the output. But there are more complex examples than the ones I have used in these articles. A Scope Transform can map all the elements to the same place, taking, for example: <J, e, f, f, r, i, e, s> to { J3, e3, f3, f3, r11, i11, e11, s11}.
We’ll burn that bridge when we come to it. For now, let’s put some simple embedding into XSet. I plan to implement the feature by replacing references to scope with messages sent to a mapper in the XSet. The first step will be an identity transform, and the existing tests should suffice for that.
def initialize(element_length, contents, rank=2)
@element_length = element_length
@contents = contents
@rank = rank
@scope_transform = nil
end
def each
for scope in element_range
new_scope = output_scope(scope)
if (scope != nil)
yield ScopedElement.new(element(scope), scope)
end
end
end
def output_scope(input_scope)
if (@scope_transform == nil)
return input_scope
end
end
The code works. The output_scope method is just noticing that the @scope_transform is nil, and returns the input scope. Now let’s build an identity scope transform object and use that instead:
class IdentityScopeTransform def output_scope(input_scope) return input_scope end end def initialize(element_length, contents, rank=2) @element_length = element_length @contents = contents @rank = rank @scope_transform = IdentityScopeTransform.new end def each for scope in element_range new_scope = output_scope(scope) if (scope != nil) yield ScopedElement.new(element(scope), scope) end end end def output_scope(input_scope) return @scope_transform.output_scope(input_scope) end
Well, that was simple enough. Now let’s map some records out of a collection, and change a selection result. Time for a test:
def test_scope_transform_removes_records
select_data = "Johnson "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("Johnson Lee ", result.contents)
@name_set.scope_transform = IntegerScopeTransform.new([0,1])
result = @name_set.restrict(select)
assert_equal("", result.contents)
select_data = "Jeffries "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("Jeffries Ron ", result.contents)
end
This is fairly aggressive, and in fact it took some time to get it right. Here’s the result:
class XSet
include Enumerable
attr_reader :contents
attr_writer :scope_transform
def initialize(element_length, contents, rank=2)
@element_length = element_length
@contents = contents
@rank = rank
@scope_transform = IdentityScopeTransform.new
end
def each
for scope in element_range
new_scope = output_scope(scope)
if (new_scope != nil)
yield ScopedElement.new(element(new_scope), scope)
end
end
end
def output_scope(input_scope)
return @scope_transform.output_scope(input_scope)
end
def restrict(selector)
matching_scopes = []
each do | scoped_element |
if selector.matches(scoped_element)
matching_scopes << output_scope(scoped_element.scope)
end
end
ScopeTransform.new(self, matching_scopes)
end
Here’s the new Transform:
class IntegerScopeTransform
def initialize(array)
@transform = array
end
def output_scope(input_scope)
return @transform[input_scope]
end
end
As I mentioned, this turned out to be a bit tricky to get right, for two reasons. First, I had forgotten that restrict was returning a ScopeTransform set, and I stumbled there for a bit before I realized I needed that output_scope call there. I also had to write a second test, because the first one used the first two records of the set, which wasn’t sufficient to let me check the values and scopes, since they were the same. (The first test’s transform is the identify transform, for two records.) Here’s the other test:
def test_scope_transform_removes_records_2
select_data = "Johnson "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("Johnson Lee ", result.contents)
@name_set.scope_transform = IntegerScopeTransform.new([2,3])
result = @name_set.restrict(select)
assert_equal("Johnson Lee ", result.contents)
select_data = "Anderson "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("Anderson Ann ", result.contents)
select_data = "Jeffries "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("", result.contents)
end
There wasn’t any long debugging or any big sign of evil, but there were a couple of moments there when I was feeling confused. One reason, certainly, is that there was just a fair amount of code to type in. Another is that the changes to :each and :restrict are a bit intricate. End of the day, though, I like the way this functions, if not quite the way it looks. There are some issues …
We should probably get rid of the ScopeTransform set return, and instead return an XSet with an appropriate embedded transform. I expect that to be easy, and it will allow us to remove an entire class. That’s a good thing, I believe.
Another issue is in :each. Take a look:
def each
for scope in element_range
new_scope = output_scope(scope)
if (new_scope != nil)
yield ScopedElement.new(element(new_scope), scope)
end
end
end
def element_range
0...cardinality
end
def cardinality
@contents.length / @element_length
end
This code is iterating over the complete element_range of the original base set, even though there are probably fewer records in the transformed set. If there’s a scope transform in place, we should just use it directly to produce the records. My intuition is telling me that if we do that, we’re going to find some kind of duplication somewhere. Possibly we should let the transforms return the record range to use. The IdentityRange, however, is a virtual range, and doesn’t really now how big the set is.
Finally, I think there’s something a bit off about the need to map the scopes in the restrict. That’s two things that the restrict needs, so I’ll start there, removing the ScopeTransform set and replacing it with an XSet with an embedded transform. The code starts this way:
def restrict(selector)
matching_scopes = []
each do | scoped_element |
if selector.matches(scoped_element)
matching_scopes << output_scope(scoped_element.scope)
end
end
ScopeTransform.new(self, matching_scopes)
end
The matching scopes are surely just what we want. We should be able to just return a new XSet. To do that cleanly, we’ll have to add the embedded scope transform to the XSet constructor:
def initialize(element_length, contents, rank=2, transform=IdentityScopeTransform.new)
@element_length = element_length
@contents = contents
@rank = rank
@scope_transform = transform
end
Note that Ruby lets me default the transform to an expression, right in the initialize parameters. I love this language! Now we should be able to make :restrict use an XSet:
def restrict(selector)
matching_scopes = []
each do | scoped_element |
if selector.matches(scoped_element)
matching_scopes << output_scope(scoped_element.scope)
end
end
transform = IntegerScopeTransform.new(matching_scopes)
XSet.new(@element_length, @contents, @rank, transform)
end
Now this seems right, but it doesn’t quite work. A bunch of tests blow. They are all calling :contents on their result, which is just returning the @contents attribute. We need to be more clever, and if we have a transform in effect, construct the string on the fly. Another problem with the notion of “contents”. This method is useful but its definition is weak. Must think on that. For now, what about updating contents? I tried a few things, up to this:
def contents
result = ""
each do | se |
element = se.element
if element.isSet? then
result += element.contents
else
result += element
end
end
result
end
I needed to define isSet? to return true for XSet, and false for object:
class Object
def isSet?
false
end
end
That’s a crock. We should never need to ask an object what it is … more evidence that :contents is off. Basically what’s happening is that :contents is supposed to return a string, whether the set in question is a set of sets, or a set of characters. I really need to do something about that.
On the bright side, the ScopeTransform set is removed from use. I’ll remove its code and tests from the project and run the tests. The rest all run. Byebye ScopeTransform set. It’s still in the archive, though, in case I need it.
Now that :contents is stable again, let’s see about getting :each to iterate just over the records the set is supposed to know about. I expect this to take a couple of passes before it’s clean. The code again:
def each
for scope in element_range
new_scope = output_scope(scope)
if (new_scope != nil)
yield ScopedElement.new(element(new_scope), scope)
end
end
end
def element_range
0...cardinality
end
def cardinality
@contents.length / @element_length
end
That code is basically considering all record scopes, testing to see if they are in range, and using the ones that are. If we have a scope transform in effect, we should use its scope list instead. But in that case, we won’t need to map the scopes … they will already be mapped. (Think of that second mapping test, with the array [3,4]. That means we only want records 3 and 4, and their scopes in the output are 0 and 1. This is tricky.
I was going to use “Programming by Intention” here, rewriting the method, but on a moment’s reflection it’s easy to see that this code is just fine, with one exception … the element range is sometimes too large. We want 0…cardinality if our scope transformation is an identity. Otherwise we want zero to whatever the size of the transform is. We’ll do this with a call-back, since the identity guy doesn’t know our size:
In XSet:
def element_range
@scope_transform.element_range(self)
end
def prim_element_range
0...cardinality
end
class IdentityScopeTransform
def output_scope(input_scope)
return input_scope
end
def element_range(set)
return set.prim_element_range
end
end
class IntegerScopeTransform
def initialize(array)
@transform = array
end
def output_scope(input_scope)
return @transform[input_scope]
end
def element_range(set)
return 0...@transform.size
end
end
Let’s talk a bit about that callback. The issue is that, though the IntegerScopeTransform knows its length, the IdentityScopeTransform is “virtual”, just mapping whatever you give it back to its input. So, to help it out, we have to ask “what is the element_range you would use for this set?” We pass it ourself. It doesn’t know, so it calls back to ask us: “what’s your actual size?”. We answer that result. This two stage process is called “callback”, and it is quite common to add a method, here called “prim_element_range” to support the bottom of the call chain. If this wasn’t in your bag of tricks before … it can be now!
The tests are all good, and I’m tired and it is nearly time for my wife get home and to head to Zukey Lake Tavern. So let’s retrospect, and put this article to bed.
How Are We Doing?
The idea of the embedded scope transform works nicely (so far), and it has let us remove a class that we don’t need any more. Since this is all a bit experimental, it’s nice when things start to collapse together already.
On the other hand, my guess is that you may be a bit overwhelmed at this point. Our XSet has gained some very interesting power, and its implemented in a very simple way, all just with some subscripting and simple mapping of integers. I’m a bit whelmed myself, as a matter of fact, and I’ve worked on this problem a few times in the past, though not quite along these same lines. Next time, I’ll put together a bit of a summary of where we are, but in fact we’re in pretty good shape. We really only have one real object, XSet, which is doing a lot of nifty things. It has only a few operational methods, and most of them are reasonable. We’ll look at it in an upcoming article to see whether it could profit from some cleanup … and that :contents thing has to be dealt with!
The code went fairly smoothly, but I took some big bites and felt some fear along the way when things didn’t work the first or second time. This probably means that I should slow down a bit.
I’m finding the ScopeTransform stuff a bit hard to think about. It’s difficult to think about the mapping when it’s stored in an array, might be easier as a hash: 2=>0, 3=>1, but that would be much harder to type in. I’m thinking that, as a rule, people won’t be using the feature much, but we’ll see. It should be easy enough to build a suitable map from a hash or the like, if it’s needed.
Summing up my sense of things at the moment, I need to be a bit more careful, and it’s probably time to take an overall look at cleaning the code, and at getting everything back into my head – and yours, if you’re out there! Until next time, here’s the code and tests for XSet. And that last commented-out test? I think we’re close to having a good way to do it. Have you ever heard of ConstituentScopeTransform? ;->
XSet Code and Tests
require 'project.rb'
class XSet
include Enumerable
attr_writer :scope_transform
def initialize(element_length, contents, rank=2, transform=IdentityScopeTransform.new)
@element_length = element_length
@contents = contents
@rank = rank
@scope_transform = transform
end
def isSet?
true
end
def each
for scope in element_range
new_scope = output_scope(scope)
if (new_scope != nil)
yield ScopedElement.new(element(new_scope), scope)
end
end
end
def output_scope(input_scope)
return @scope_transform.output_scope(input_scope)
end
def restrict(selector)
matching_scopes = []
each do | scoped_element |
if selector.matches(scoped_element)
matching_scopes << output_scope(scoped_element.scope)
end
end
transform = IntegerScopeTransform.new(matching_scopes)
XSet.new(@element_length, @contents, @rank, transform)
end
def matches(a_scoped_element)
any? { | scoped_element |
match(a_scoped_element, scoped_element)
}
end
def match(my_scoped_element, selector_scoped_element)
selector_scoped_element.element.subset?(my_scoped_element.element)
end
def subset?(larger_set)
element_range.all? { | scope |
larger_set.contains?(element(scope), scope)
}
end
# def subset? set
# each do | se |
# if ( set.element(se.scope) != se.element )
# return false
# end
# end
# return true
# end
def element(scope)
element_contents = @contents[scope*@element_length,@element_length]
if (@rank > 1)
return XSet.new(1,element_contents, self.rank-1)
else
return element_contents
end
end
def contents
result = ""
each do | se |
element = se.element
if element.isSet? then
result += element.contents
else
result += element
end
end
result
end
def contains?(an_element, scope)
element(scope) == an_element
end
def element_range
@scope_transform.element_range(self)
end
def prim_element_range
0...cardinality
end
def cardinality
@contents.length / @element_length
end
def rank
@rank
end
def to_s
"{#{contents}}"
end
end
class Object
def isSet?
false
end
end
require 'project.rb'
class TC_MyTest < Test::Unit::TestCase
def setup
name_data = "Jeffries Ron Hendrickson ChetAnderson Ann Johnson Lee "
@name_set = XSet.new(16, name_data)
@five_element_set = XSet.new(4, "123 234 132 342 abc ")
end
def test_cardinality
assert_equal(5, @five_element_set.cardinality)
end
def test_one_byte_record
input = XSet.new(1,"abcdef")
assert_equal("b", input.element(1).element(0))
end
def test_record_bytes
johnson = @name_set.element(3);
assert_equal(2, @name_set.rank)
assert_equal(1, johnson.rank)
assert_equal("J", johnson.element(0))
end
def test_element_range
assert_equal(0...5, @five_element_set.element_range)
end
def test_element_extraction
assert_equal("132 ", @five_element_set.element(2).contents)
end
def test_restrict
select = XSet.new(1,"1")
expected = "123 132 "
result = @five_element_set.restrict(select)
assert_equal(expected,result.contents)
end
def test_name_restrict
select_data = "HendricksonJeffries "
select = XSet.new(11, select_data)
expected = "Jeffries Ron Hendrickson Chet"
result = @name_set.restrict(select)
assert_equal(expected, result.contents)
end
def test_single_selection
select_data = "Jeffries Jeffries "
select = XSet.new(11, select_data)
expected = "Jeffries Ron "
result = @name_set.restrict(select)
assert_equal(expected, result.contents)
end
def test_each_using_scope
ann = ""
@name_set.each do
| scope_element |
if (scope_element.scope==2)
ann = scope_element.element.contents
end
end
assert_equal("Anderson Ann ", ann)
end
def test_detect
chet_scope_element = @name_set.detect {
| scope_element |
scope_element.element.contents.include? "Chet" }
assert_equal("Hendrickson Chet", chet_scope_element.element.contents)
end
def test_rank
assert_equal(2, @name_set.rank)
end
def test_element_rank
element = @name_set.element(2)
assert_equal(1, element.rank)
end
def test_shifted_record
r = XSet.new(1, "Hendrickson Chet", 1)
chet = ShiftedRecord.new(12,4,"Chet")
ron = ShiftedRecord.new(12,4,"Ron ")
assert(chet.subset?(r), "Chet sought but not found")
assert(!ron.subset?(r), "Ron incorrectly found")
end
def test_scope_transform_removes_records
select_data = "Johnson "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("Johnson Lee ", result.contents)
@name_set.scope_transform = IntegerScopeTransform.new([0,1])
result = @name_set.restrict(select)
assert_equal("", result.contents)
select_data = "Jeffries "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("Jeffries Ron ", result.contents)
end
def test_scope_transform_removes_records_2
select_data = "Johnson "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("Johnson Lee ", result.contents)
@name_set.scope_transform = IntegerScopeTransform.new([2,3])
result = @name_set.restrict(select)
assert_equal("Johnson Lee ", result.contents)
select_data = "Anderson "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("Anderson Ann ", result.contents)
select_data = "Jeffries "
select = XSet.new(11, select_data)
result = @name_set.restrict(select)
assert_equal("", result.contents)
end
# def test_firstname_restrict
# name_data = "Jeffries Ron Hendrickson ChetAnderson Ann Johnson Lee "
# input = XSet.new(16, name_data)
# select_data = "Ron Lee "
# select = XSet.new(4, select_data)
# expected = "Jeffries Ron Johnson Lee "
# result = input.restrict(select)
# assert_equal(expected, result.contents)
# end
end