In 2012 the idea of tags as used in Push was taken to one possible logical extreme in the development of an idea for “Tag Space Machines” in which all structure (of code and data) is mediated by tag references, rather than by sequencing within a collection like a list or tree.
An unpublished paper describes the Tag Space Machine concept in detail.
Emma Tosch developed and experimented with an implementation.
And it should probably be noted, the experimental implementation included a GP algorithm That GP algorithm was never able to evolve any interesting programs.
Indeed. If I recall correctly, the most immediate and obvious problem was that very few “random” tag space machines, in the initial population, did anything at all. So evolution couldn’t get started. Conceivably, more attention to the question of how to generate random tag space machines, and/or more attention to the question of how to randomly vary them (that is, the genetic operators to use), could change this picture significantly.
Also conceivably (as I might expect @thelmuth to chime in 
), more attention to these questions won’t change the picture! Only more research and experimentation will tell.
I’d be tempted to say that the Tag Space Machine was a different representation language from Push. Isn’t it? That is, it’s not just a genomic thing, but rather a fundamental difference in the dynamics and architecture of the interpreter itself.
Yes it is a fundamentally different representation language. But at its core is most of Push, with a stack per data type, etc. The big differences are that there’s no code stack, that the x stack isn’t quite like the Push exec stack because it can contain only literals, and that all code and data structure has to be achieved using tags (which can match inexactly).
(provoked by @lspector’s nearly drooling enthusiasm the other day) 
OK here are some observations and questions from 20 minutes spent on a branch:
:number, which doesn’t exist yet /shrug (see earlier discussion of wanting to fix numerics soon)name type never worked very well because it was so onerous for the interpreter to make keys up and associate them meaningfully with values, in this case there will need to be a source for a shit-ton of numbers for keys: either some kind of generator, or just some sort of reliable feed. Without an indefinitely large source of genetically-encoded non-random numeric keys, evolvability will suck.:number-source or what?:range type from pushSwift will be useful here, too, since operations on :tagspace instances will probably involve range-based manipulation. For instance, crossover, inversion, affine scaling, and so forth.:tagspace behavior is that you seem to want to treat them as something more than a simple type. I see them as another useful collection type, and essentially interoperable with the standard Push :set, :vector, :range and so forth. That is, they’re not privileged as far as I can see: they’re “just” little storage things that use approximate lookup.Some practical design questions:
I assume there’s nothing magical about the tuples you used in the sketch you’ve posted. I suspect that was written before there were a lot of collection types in Push, right? I like the idea of multiple items being retrieved, but we already have :vector and strongly-typed tuples, so the meaning of “retrieve this vector or its elements” is ambiguous.
So it seems reasonable that the lookup behavior in my implementation can be split into at least two variants, something like :get-as-item and :get-as-items. The first would push the collection itself onto :exec, and the second would push the contents of the item onto :exec in canonical order.
I take you at your word that any literal can be stored in a :tagspace collection.
:tagspace item can also get stored in a :tagspace?I can tell that in working through your “threaded items” example, you really really want those weird little imap maps to be a full-fledged type, but can’t quite bring yourself to say it. Clearly if we permit arbitrary tuples to be stored in a :tagspace collection, the fraction of them that “mean” this thing and also look up another thing right away will be vanishingly small.
If you want that to be able to happen (and it seems reasonable), then consider (1) some flexible and convenient way of generating a deterministic series of numeric keys to define a “sequence” of lookups, (2) a way of conveniently pulling a :range of values all at once, or (3) whether a special ":tagspace link" like your imap is in fact necessary, to pump the numbers up. I would count the last solution unlikely to help, since we’re already going to be short of just-plain-numbers if these things start to work. In fact, I’m really pessimistic about the imap chaining thing, since it feels very fragile and remote from the Push genome itself.
I suppose a simple linear CA would be a sort of “deterministic number generator” too. 
There’s a lot to think about here and I don’t have answers at the moment to all of the explicit or implicit question. But there is indeed a reason for the tuples to be limited to 2-tuples, and to have no other collection types in tag space machines: as expressed in footnote 4 of the tag space machine paper:
Why do we provide only pairs, rather than tuples of any length? Pairs provide structure that is not mediated by tags, which is something that we want to avoid in the TSM model. But they provide the minimum necessary non-tag-mediated structure. General tuples would provide more non-tag-mediated structure than we need, and we want as little as we can get away with.
Less pure versions of the idea may be superior in various ways… I don’t know. But the idea behind tag space machines was to make all structure tag-mediated, to the greatest extent possible.
Well, for the moment I’m going to treat these as pure, abstract containers with a red-black tree sorted key, and approximate lookups. As I said, I don’t see any reason to get too excited about them as a special magic data structure, since they’re literally just an off-the-shelf Clojure primitive already (sorted-map).
I also won’t artificially restrict storing anything in them until we see a reason to do so. I would rather build in a lot of capacity for diverse uses, and then select for behaviors we think are better. Sounds like your footnote is essentially hoping for emergent behavior, which in my experience is not the most effective approach.
I think they’re a good substitute for the :map type I was working on, since they’re essentially… well, a :map-of-numeric-keys. The tuples themselves need not even be part of a first release; they’re essentially a “fix” for the sort of behavior you think you want. When you don’t see that behavior, then we can add those.