![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
see also jasperDataModes, jasperAttributes
---
homogeneous hypergraph
--
relations hypergraphs chu spaces algebras homomorphisms points sets (and power set operation?) topologies categories nodes, edges, paths natural numbers terms grammars ordered sequences/lists/tuples functions logical propositions/sentences inference rules/reductions proofs boolean values posets lattices types hypercategory? [my own idea; a hypergraph with optional equalivalences over paths, semi-equivalently a composition operation over paths] topoi [topos's] variables and substitution/anti-substitution [my term for tdn lambda calculus's 'abstraction' operation] e.g. the lambda calculus induction trees formal languges automata groups
memory-to-memory machines (ram machine; no registers) stack machine (no registers) register machine combinatorial calculus lambda calculus turing machine accumulator machine which have only one visible general-purpose temp register
note to self: look at l/say.txt, there might be something on that list that isnt here
toread++ graph transformation by computational category theory
---
Yegge goes on about how prototype-based dicts are really really useful:
(if you read this article, skip everything up to here) " Properties Pattern high-level overview
At a high level, every implementation of the Properties Pattern has the same core API. It's the core API for any collection that maps names to values:
get(name)
put(name, value)
has(name)
remove(name)There are typically also ways to iterate over the properties, optionally with a filter of some sort.
So the simplest implementation of the Properties Pattern is a Map of some sort. The objects in your system are Maps, and their elements are Properties.
The next step in expressive power is to reserve a special property name to represent the (optional) parent link. You can call it "parent", or "class", or "prototype", or "mommy", or anything you like. If present, it points to another Map.
Now that you have a parent link, you can enhance the semantics of get, put, has and remove to follow the parent pointer if the specified property isn't in the object's list. This is largely straightforward, with a few catches that we'll discuss below. But you should be able to envision how you'd do it without too much thought.
At this point you have a full-fledged Prototype Pattern implementation. All it took was a parent link!
From here the pattern can expand in many directions, and we'll cover a few of the interesting ones in the remainder of this article. "
after that point there are some interesting implementation notes:
"JavaScript? permits you to use arbitrary objects as keys, but what's really happening under the covers is that they're being cast to strings, and they lose their unique identity. This means JavaScript? Object property lists cannot be used as be a general-purpose hashtable with arbitrary unique objects for keys.".
"
Quoting
JavaScript? syntax is especially nice (compared to Ruby and Python) because it allows you to use unquoted keys. For instance, you can say
var person = { name: "Bob", age: 20, favorite_days: ['thursday', 'sunday'] }
and the symbols name, age and favorite_days are NOT treated as identifiers and resolved via the symbol table. They're treated exactly as if you'd written:
var person = { "name": "Bob", "age": 20, "favorite_days": ['thursday', 'sunday'] }
You also have to decide whether to require quoting values. It can go either way. For instance, XML requires attribute values to be quoted, but HTML does not (assuming the value has no whitespace in it). "
" Logically a property list is an unordered set, not a sequential list, but when the set size is small enough a linked list can yield the best performance. The performance of a linked list is O(N), so for long property lists the performance can deteriorate rapidly.
The next most common implementation choice is a hashtable, which yields amortized constant-time find/insert/remove for a given list, albeit at the cost of more memory overhead and a higher fixed per-access cost (the cost of the hash function.)
In most systems, a hashtable imposes too much overhead when objects are expected to have only a handful of properties, up to perhaps two or three dozen. A common solution is to use a hybrid model, in which the property list begins life as a simple array or linked list, and when it crosses some predefined threshold (perhaps 40 to 50 items), the properties are moved into a hashtable. "
" Note that you can get a poor-man's splay tree (at least, the LRU trick of bubbling recent entries to the front of the list) using a linked list by simply moving any queried element to the front of the list, a constant-time operation. It's surprising that more implementations don't take this simple step: an essentially free speedup over the lifetime of most property lists. "
" The algorithm for inherited property lookup is simple: look in my list, and if the property isn't there, look in my parent's list. If I have no parent, return null. This can be accomplished recursively with less code, and but it's usually wiser to do it iteratively, unless your language supports tail-recursion elimination. Property lookups can be the most expensive bottleneck in a Properties Pattern system, so thinking about their performance is (for once) almost never premature. "
" As I described in the Overview, the simplest approach for implementing inheritance is to set aside a name for the property pointing to the parent property list: "prototype", "parent", "class" and "archetype" are all common choices. "
"
The deletion problem
If you delete a property from an object, you usually want subsequent checks for the property to return "not found". In non-inheritance versions of the pattern, to delete a property you simply remove its key and value from the data structure.
In the presence of inheritance the problem gets trickier, because a missing key does not mean "not found" – it means "look in my parent to see if I've inherited this property."
...
The solution ... is to have a special "NOT_PRESENT" property value that deleteProperty sets when you delete a property that would otherwise be inherited. This object should be a flyweight value so that you can check it with a pointer comparison. " (he goes on to note that you may or may not want NOT_PRESENT == null)
(so i guess we want a way to create objects and inherit once, at creation time -- see below, this is similar to a pass-by-reference vs. pass-by-value problem; the prototype parents are by default references but if we let the programmer optionally freeze them into values there is no trouble)
" Read/write asymmetry
One logical consequence of prototype inheritance as we've defined it is that reads and writes work differently. In particular, if you read an inherited property, it gets the value from an ancestor in the prototype chain. But if you write an inherited property, it sets the value in the object's local list, not in the ancestor. "
optimization: "
Make sure your string keys are interned. Most languages provide some facility for interning strings, since it's such a huge performance win. Interning means replacing strings with a canonical copy of the string: a single, immutable shared instance. Then the lookup algorithm can use pointer equality rather than string contents comparison to check keys, so the fixed overhead is much lower.
...
Corollary: don't use case-insensitive keys. It's performance suicide. Case-insensitive string comparison is really slow, especially in a Unicode environment. "
(i might want to not use case-insensitive keys in the runtime, but at compile time to lowercase the key names which are in the source code; or perhaps even use a Haskell-eque syntax with significant case)
another optimization:
" Perfect hashing
If you know all the properties in a given plist at compile-time (or at runtime early on in the life of the process), then you might consider using a "perfect hash function generator" to create an ideal hash function just for that list. It's almost certainly more work than it's worth unless your profiler shows that the list is eating a significant percentage of your cycles. But such generators (e.g. gperf) do exist, and are tailor-made for this situation.
Perfect hashing doesn't conflict with the extensible-system nature of the Properties pattern. You may have a particular set of prototype objects (such as your built-in monsters, weapons, armor and so on) that are well-defined and that do not typically change during the course of a system session. Using a perfect hash function generator on them can speed up lookups, and then if any of them is modified at runtime, you just fall back to your normal hashing scheme for that property list. "
another optimization (note this is different from the optional parent freezing that i discuss below):
"
Copy-on-read caching
If you have lots of memory, and your leaf objects are inheriting from prototype objects that are unlikely to change at runtime, you might try copy-on-read caching. In its simplest form, whenever you read a property from the parent prototype chain, you copy its value down to the object's local list.
The main downside to this approach is that if the prototype object from which you copied the property ever changes, your leaf objects will have the now-incorrect old value for the property.
Let's call copy-on-read caching "plundering" for this discussion, for brevity. If Morris caches his prototype Cat's copy of the "favorite-food" property (value: "9Lives"), then Morris is the "plunderer" and Cat is the plundered object.
The most common workaround to the stale-cache problem is to keep a separate data structure mapping plundered objects to their plunderers. It should use weak references so as not to impede garbage collection. (If you're writing this in C++, then may God have mercy on your soul.) Whenever a plundered object changes, you need to go through the plunderers and remove their cached copy of the property, assuming it hasn't since then changed from the original inherited value.
That's a lot of stuff to keep track of, so plundering is a strategy best used only in the direst of desperation. But if performance is your key issue, and nothing else works, then plundering may help. "
another optimization:
" The idea is that you don't need to pay for the overhead of property lists when very few of the objects in your system will ever have one. Instead of using a field in each class with a property list, you maintain a global hashtable whose keys are object instances, and whose values are property lists. "
another optimization (omitted for now):
"
REDACTED
Brendan Eich came up with astoundingly clever performance optimization for the Properties Pattern, which he told me about back in January. I was ready to publish this article, but I told him I'd hold off until he blogged about his optimization. Every once in a while he'd ping me and tell me "any day now."
Brendan, it's October, dammit! "
---
TODO:
four fundamental forms, realizations in graphs:
relations functions tables (non-graphical???) orders
TODO: write down realizations (e.g. in relations, nodes are the dimensions, but if a function is seen as a relation, the alphabet on labels is one of the dimensions) and conversions
comment: Chu space is embedding of relation into table (relations have alphabet of 1,0)
comment: type system should include types (which specify domains and ranges of partial functions), properties (like 'total on its domain', 'injective', 'associative', 'functional relation', "antisymmetric relation", and what you are allowed to do (copyable vs. only movable, immutable)
---
linq
