briarpig: mu: box

problem

box — an object allocated in garbage collected gc space is called a box, as first mentioned on the stack demo. A box is the equivalent of struct in C and C++, and in fact a struct is used to represent each box format. Living in gc space is what makes a struct a box: it's subject to garbage collection, aka gc. This page shows early drafts of box formats still under revision.

(These boxes are used in toy programming language lathe: a lisp dialect plus smalltalk class system, using þ library using the mu-babel license, under mu which presents broad context including a main focus on usefulness to the author.)

Dialogs below use a new character named Zé, whose role is explained on the design page. This is done in part to help put chaoticly incomplete aspects into better focus. More boxes are shown than needed or currently used, and ones currently used are subject to change.

cast «

"I've always been interested in gc box formats," Stu said. "So I'd like to hang out while you show parts to Zé."

"No problemo," Wil waved. Then as Zé entered holding sodas Wil asked, "Did you get me a coke?"

"No," Zé smiled, "just one for Stu. Bet you never offered guests a drink before, right? Shame on you."

Wil turned to Stu and stage-whispered behind a hand, "I'm actually the nurturing one. This is just an act."

"Your Vaudeville show must have been called 'Ripping You a New One' then," Zé suggested. "Staying in practice?"

"Can we throttle jokes a little?" Wil asked nicely.

Zé shrugged: all the same to him. "Are these gc boxes like the ones you showed me — when was it? 1995?" he asked.

"Similar, but completely different," Wil semi-joked. "A little like the ML inspired boxes, but not at all like the XLisp style nodes in my Ygg interpreter."

"That the one like Scheme with Smalltalk classes added?" Stu asked. "Gonna show that one too?"

"That's the one," Wil agreed. "But it's too warty. However, you can consider this a rewrite of Ygg, but about three generations after. Maybe four. They pile up. It was called Mithril when I was at Netscape."

Zé mocked Wil's excess chatter with a one-handed yak-yak-yak gesture. "What happened to Mithril?" he asked.

"Got distracted by too much Smalltalk and too much C++ efficiency," Wil looked up, trying to remember.

"Did you use a Y code prefix in Ygg?" Stu guessed.

"That's right!" Zé realized. Then to Wil, "So thorn is a little Yggdrasil? And you kept a small y?"

"Well," Wil looked sheepish. "Let's look at boxes."

meat «

"Of course, you need to read peg and tag along with this stuff," Wil explained. "Virtually at the same time, unfortunately. All three depend on each other. And imm showing immediate values encoded using the yp peg api."

"A yt tag precedes each box in memory?" Stu recalled.

"Yes," Wil confirmed. "And each tag is four bytes — a 32-bit strong dynamic type tag describing primitive class, size, format, and metainfo bits."

"Are boxes four byte aligned?" Zé guessed. "I guess eight byte alignment is another good choice: giving you three primary tag bits in pointers instead of only two."

"Yes, just four byte aligned," Wil nodded. "More alignment would make things bigger, wasting space. I'll save eight byte alignment for a later 64 bit version."

"Why are boxes aligned?" Stu wondered.

"Several reasons," Wil ticked off his fingers. "Might as well since most C structs are multiples of four anyway; necessary to tell immediate values from box pointers; and aligned data is faster to execute most of the time."

"Code used to crash when accessing data at non-aligned addresses," Zé noted. "But now Intel accesses data of any size at any address — it's just slower if not aligned."

"How do boxes get aligned?" Stu asked. "How can you make sure? Allocate them using the book api?"

"Yes, exactly," Wil smiled. "Books and pages have much better than four byte alignment. So it's only necessary to allocate space in multiples of four bytes."

"And every box has a yt tag before it?" Stu asked. "Which are also four bytes in size? How do you ensure a tag precedes each box? You just do it?"

"Yes, every box has a tag in the four bytes immediately preceding its starting address," Wil confirmed. "It's the contract — an invariant that must be true, no exceptions."

"What did they call tags in ML source code," Zé asked.

"Descriptors," Wil replied. "Descriptor means tag in more letters and syllables. In early 90's ML, every descriptor had 0x10 in the low two bits, so you could see the start of a box in some places. But I don't do that."

"What's that ybox class I see there?" Zé pointed.

ybox «

"This ybox class represents what is known about all boxes," Wil explained. "Mainly two things: a box must be four byte aligned and is preceded by a yt tag."

"Sounds familiar," Zé joked. "Where did I hear that before?"

Wil ignored him. "Note there's no state: no members are declared. Just a static method testing alignment, and uh, a method getting the tag. Which kinda looks like state, because it is. But using an unconventional negative index to reach back before the box."

struct ybox { // opaque type NOMINALLY base of box structs « typedef ptrdiff_t p_t; // ptr type: suitable int for masks «

// good: 4 byte aligned (nil is permitted for ybh::hgood()); // b is a box ptr; don't check for nil: peg boxes never nil; // return true if low two bits off p are zero (u32 aligned): static bool goodb(const void* b) { // 4-byte aligned? « return 0 == (3 & (p_t) b); // zero in low two bits } static void badb(const void* b, const char* where);

// goodn: length is 4-byte aligned? static bool goodn(n32 len) { return 0 == (3 & len); } « static void badn(n32 len, const char* where); // not goodn // enum ebase { e_box = 0 };

// b must be a 4-byte-aligned box addr in gc format memory; // return four bytes before any 4-byte-aligned box as tag static const yt& btag(const void* b) { « return ((const yt*) b)[-1]; } }; // struct ybox

"Wil, that btag() method is disturbing," Stu squirmed.

"Tough, it works," Wil shrugged. "If it stops working — won't happen — I'll change it to something else."

"What if pointer b is a nil pointer?" Zé asked.

"That's a good question," Wil beamed. "Obviously, don't use nil as a box address. Pegs stored in gc space never contain a nil value. Pegs are never zero: not a valid peg value."

"What if it happens anyway?" Stu wondered.

"Treated like memory corruption: an assert or an exception, or something," Wil explained. "Or maybe a crash. The idea is: I don't want Lathe to bother checking for nil."

"How is language level nil represented?" Stu asked.

"That's an immediate value, yp::i_nil, shown now in the peg api and later in imm," Wil replied.

"I see it's equal to constant 2," Zé noticed. "Immediates have at least one nonzero bit in the low two bits?"

ybox.cpp «

"That's right," Wil nodded. "But format of immediates won't figure in the rest of the box material. Let's look a two error logging methods for ybox."

void ybox::badb(const void* b, const char* where) { « // on false goodb ylog(1, "badb(b=%#lx, at=%s) box is NOT 4-byte ALIGNED\n", (long) b, where); }

void ybox::badn(n32 len, const char* where) { « // len NOT multiple of 4 ylog(1, "badn(len=%#lx, at=%s) len is NOT 4-byte ALIGNED\n", (long) len, where); }

"These will never get called unless someone screws up," Wil explained. "So they're not really interesting."

"Do all boxes subclass ybox?" Zé asked. "Some of them? None? There's not much api to inherit."

"None of the box types inherit from ybox," Wil said. "Just about all of them define the btag() method again themselves. I like that better than inheriting btag()."

"Why not?" Zé agreed. "Inlines are cheap."

"Exactly," Wil chimed. "Let's look at a box now. Let's start with one used to track space for box allocation."

ytocb «

"Let me guess: TOC stands for table of contents," Zé anticipated. "Reminds me of Bento a little."

"Bingo," Wil pointed. "Box ytocb is the first box allocated in every book of a gc address space."

"To say how much book space is used?" Stu asked.

"Correct," Wil nodded. "The run named b_v describes space at book's end not yet allocated. To allocate N bytes, where N must be a multiple of four, you just call b_v.vtake(N)."

"Oh my god," Stu blurted. "You just showed me how boxes are allocated. It's trivial pointer bumping."

Wil scratched his ear. "Yes, except when vtake() returns nil, it means b_v has insufficient space, and a new book must be allocated — happening seldom when boxes are small."

"Could that cause gc?" Zé hazarded.

"I don't want to get into garbage collection early," Wil pleaded. "But I think the answer is no. I'd rather gc happens at well defined times, not at any random box alloc."

// ytocb is expected as first box put into box allocated space struct ytocb { // table of contents box « yv b_v; // yv describes unused space (in book) «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_toc, e_bt = (sizeof(yv)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; }

ytocb(yv const& v) : b_v(v) { } « ytocb() : b_v() { } };

"Hey, Wil," Zé interrupted. "What's with the b suffix on the end of the class name? Does it mean box?"

Wil confirmed quickly, "Yes, every box ends with b for box, and methods and members typically also begin with b for box. This should help clarify when gc memory is used in C++."

"Didn't you also use b for buf?" Stu remembered, rubbing his chin. "Won't that cause some confusion?"

"Yes, but yb buffers and out stream ybo don't appear often," Wil rationalized. "And it's hard to confuse them with boxes: one's too short and the other doesn't end in b."

"I think you just have a fetish for b and p because they together they make þ for briarpig," Zé teased.

Wil shook his head in exasperation. "Whatever."

"It looks like constant e_bt is the value used by every ytocb box as it's tag," Zé changed subjects. "What's with the 16 bit shift shown? And why sizeof(yv)?"

"The high 16 bits of every tag is a length field," Wil explained. "For a vector box of N parts, the length is the value of N. Constant sized boxes like ytocb put their size in bytes in the length field instead. Stu, you want to know why?"

"Why put constant sizes in the length field, Wil?" Stu asked gamely at Wil's prompt. "Isn't it redundant?"

"Yes! In constant sized boxes, size in the length field is redundant," Wil gestured excitedly. "It can be wrong: I can assert the expected size is present to detect corruption."

"Detecting corruption sounds so exciting," Zé mocked.

"You know what I mean," Wil smiled. "Notice variations from expected values as soon as possible to see when the runtime goes foul. Kinda like a soft SEGV."

"Why expect a runtime to go foul?" Stu wondered.

Wil shrugged. "It usually does. I just want to catch it faster so Darwinian selection filters more bugs sooner."

"You're a pessimist," Stu accused.

Wil made a wry expression. "Do ya think??"

Zé raised a finger. "You should use a longer value than just size if that's your goal," he warned. "Maximizing grey distance might catch more corruption."

Wil raised his hands. "I know there are other options," he said. "This one fits in a pick-one-and-go-on category."

Zé dry-washed his hands like a mad scientist. "We can make a list of all options and carefully measure what works best."

"Moving right along," Wil said to Stu, "The following struct defines both the tag and ytocb box together."

tytocb «

"Wil Munny: license to overkill," Zé channeled Dex. "The name's only one letter different? You prefixed t for tag on the front, turning ytocb into tytocb."

"Yeah, it seemed fitting," Wil said, "Since state concatenates a tag and a ytocb box, the name does too."

struct tytocb { // format for ytocb + preceding tag metainfo « yt t_toc; // ytocb::e_bt « ytocb b_toc; // box for toc «

tytocb(yv const& v) : t_toc(ytocb::e_bt), b_toc(v) { } « tytocb() : t_toc(ytocb::e_bt) { }

yv* bv() { return &b_toc.b_v; } // ptr to yv in toc box « }; // struct tytocb: used as header for every book of boxes

"That's not really necessary, is it?" Stu wondered. "Oh, both the members have nearly the same name, but one has t for tag and the other b for box?"

"Yeah, that's how the names go," Wil agreed. "No, it's not necessary. But it makes it somewhat easier to envision bytes allocated at the start of each book. This way is explicit: sizeof(tytocb) bytes are allocated."

"Something tells me this is just a warmup for a more complex case," Zé guessed. "Do you have a hairy example later?"

"Yes," Wil rubbed one eye sheepishly. "I do the same thing with symbol boxes, but each is preceded by a hash box. So one struct joins all four parts like this: t+b+_+t+b."

"That must be a bitchin' name," Zé teased. "I thought you didn't like complexity? What's up?"

"I wanted symbols to look physically identical to strings," Wil explained. "But I also wanted each symbol to cache a string hash for efficiency. Two boxes were simpler than writing complex code making two different formats look like one type."

"You guys keep jumping ahead," Stu whined. "It's disturbing. Can we look at the symbol box next?"

"Let's start with something simpler," Wil suggested. "Since Lathe is a Lisp, it should have pairs for cons cells, containing two pegs. But first, here's a box with one peg only."

yp1b «

"The name yp1b means one-peg box?" Zé guessed. "A box with one peg in it? A pointer to something else."

"Or an immediate value," Wil reminded. "Member b_p can hold any valid peg value, including immediate literals."

"But what good is it?" Stu asked. "Anyone who wanted to use a box like this could instead point directly to the value desired. Right? What's the point?"

struct yp1b { « yp b_p; // one peg (refers to an imm or a box) «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_p1, e_bt = (sizeof(yp)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } }; // struct yp1b refers to exactly one imm or one boxed value

"Indirection," Zé suggested. "Two parties can share a value whose content can be updated in one place. It's like a handle if a peg is like a pointer."

"Isn't that the same thing as a vector of length one?" Stu asked. "Does this box have an advantage? Is it smaller?"

"You're right," Wil conceded. "It's virtually the same as an array of length one. And it's the same size; there's no advantage. I don't actually care what it's used for. I just wanted to define one of every plausible primitive box format."

typ1b «

"Looks like typ1b is another one of your combined tag and box deals," Zé noticed. "Whoa, check the comments about sentinel use in non-gc space. What does that mean?"

"I don't remember," Wil chewed his lip.

"You don't remember?" Zé asked incredulously.

"Happens now and then," Wil shrugged. "Apparently I planned to use boxes in non-gc space — maybe as roots — and this would be used to mark some edge or another."

// typ1b first used as dummy box in non-gc land, as sentinel struct typ1b { // format: alloc yp1b + preceding tag metainfo « yt t_p1; // yp1b::e_bt « yp1b b_p1; // box for p1 «

typ1b() : t_p1(yp1b::e_bt) { } «

yp1b* bbox() { return &b_p1; } // ptr to box: box of 1 ptr « }; // struct typ1b: single boxed ptr (as non-gc sentinel box)

"Don't all boxes have to live in gc-space?" Stu asked. "I thought all boxes had to be allocated in a book, and be garbage collected. What's the exception?"

"Any exception you like," Wil said. "Boxes outside gc space don't move, so they don't increase cost of gc — but you must treat them as roots in any gc space they reference."

"That's ... really interesting," Zé considered. "Any and every gc space can refer to boxes that aren't garbage collected. You can put standard data structures in a common place where they get shared. That's cool. It makes gc cheaper?"

"Yes," Wil smiled. "It seems an especially good idea for immutable data like symbol intern tables. Global symbols need never move, and don't intersect collected gc spaces, so all those spaces collect faster. Other types are similar."

Zé stared into space, wheels turning in his head. Wil decided to go on before the next idea popped out.

"Hey," Stu noticed. "What's the default value of the peg in both yp1b and typ1b?"

"Nil," Wil replied. "The yp peg empty constructor sets the value to immediate yp::i_nil. The same is true of any box that declares a yp peg member, like ypairb below."

ypairb «

"Box ypairb has two slots for the car and the cdr," Wil introduced. "If you only know C++, that's like first and second in std::pair. Lists are a primary use case."

"Are you going to explain the origin of the names in terms of contents of the address and decrement registers in IBM assembler way back when?" Stu asked.

"Absolutedly not," Wil said. "Besides, you just did. I'm not going to spend any time talking about Lisp names, now or later. I just use them."

"In lists," Zé offered without prompting, "a list element is held in car while cdr refers to the next pair in the list, so cdr is just a next pair pointer."

"Thanks for that very small lecture," Wil said. "Will you be giving a seminar on Lisp semantics later?"

"Sorry," Zé smiled. "I love Lisp. When will your Scheme be done? Wait, I'm kidding! Don't get upset."

struct ypairb { // pair box: a Lisp cons cell (synonym: yp2b) « yp b_car; // same as yp2b::b_p[0]; « yp b_cdr; // same as yp2b::b_p[1]; «

const yt& btag() const { return ((const yt*) this)[-1]; } «

bool bescaped() const { // getter for 'escaped' bit « return ((const yt*) this)[-1].isescaped(); }

void p2escape(bool esc) { ((yt*) this)[-1].tescape(esc); } «

"What's an 'escaped' pair?" Stu asked.

"Currently I use that bit to mean a pair should use brackets instead of parentheses when printing," Wil replied.

"That's pretty arbitrary," Zé observed. "But I suppose that's not going to be visible at the language level?"

"Don't know yet," Wil shrugged. "But it seems a good idea to expose as little as possible in, say, a Scheme view of Lathe — at least when it's arbitrary hacks like that."

enum { e_bk = yt::k_p2, e_bt = ((sizeof(yp)*2)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].vkind() == (u32) e_bk; }

bool bt() const { return e_bt == ((const u32*) this)[-1]; }

"Api above is standard box boilerplate," Wil pointed. "Constructors below let you init the slots."

ypairb() { } // both car and cdr are yp::i_nil « ypairb(yp car, yp cdr) : b_car(car), b_cdr(cdr) { }

static ypairb* notb(yp const& p); // log err, MUST ret zero static ypairb* mustb(yp const& p) { « ypairb* b = (ypairb*) p.u.p_box; return ((3 & (yp::p_t) b) == 0 && b->bkind())? b : notb(p); } static ypairb* mayb(yp const& p) { « ypairb* b = (ypairb*) p.u.p_box; return ((3 & (yp::p_t) b) == 0 && b->bkind())? b : 0; }

"Wil," Zé began in exagerrated patience. "What do those methods mean? They look like dynamic casts."

"That's exactly what they are," Wil nodded. "You call mayb() when it's okay for a peg not to have a pair as its value. But mustb() logs an error by calling notb() when the referenced box is not a pair. Zero means not a pair both ways though."

"Why bother with a notb() method?" Stu asked.

"To save inlined code size," Wil said. "The speed of the unexpected error case isn't of any concern. This way mustb() is able to log an error, but does so cheaply."

"I see blen() returns list length," Zé began. "But I can't believe the way you handle cycles is just stopping after a zillion steps. Don't you know how to detect list cycles?"

"Okay," Wil placated. "I knew you'd complain about that. I was in a hurry, and knew I wasn't going to call it on a list with cycles. Are you going to make me do the right thing?"

"Absolutely, you slacker," Zé chided. "When we get to it; there's no emergency right this second."

// true if length is exactly equal to n, otherwise false: bool beqlen(n32 n) const { « return this->blen((int) (n+1)) == n; }

"How does this beqlen() efficiently check exact list length equal to n," Stu asked. "Won't blen() iterate over all the pairs anyway? Is the argument to blen() involved?"

"Yeah," Wil confirmed. "blen() doesn't look at more than n+1 pairs, so it won't spend linear time scanning the list beyond the point of interest."

// use blen(n+1) to see if list len is lt, eq, or gt n; // neg: blen(n+1)<n; zero: blen(n+1)==n; pos: blen(n+1)>n int bcmplen(n32 n) const; // cmp blen(n+1) to n: blen(n+1)-n

"I get it," Stu said. "And if N is actual list length, then bcmplen() returns the correct sign for N-n, also without looking at too many pairs. No don't stop; let's go on."

// true iff b_car == car & blen(n+1) == n (ie bcmplen(n)==0) bool bmatch(yp const& car, n32 n) const;

// this bmatch() is easier to use when car is yyb* bool bmatch(ybox* car, n32 n) const;

"Method bmatch() returns true if a list starts with a specific value and is exactly a length of interest," Wil said.

"Oh, so like," Zé hypothesized, "you can ask, 'Is this a list of length three whose first element is symbol foo?' Like that? For simple pattern recognition?"

"That's right," Wil confirmed. "And that yyb in the comment is the symbol box type. Sorry. It's short, though."

"You abbreviated symbol to just a single y?" Zé asked, chewed his lip, then smiled. "I like it. Weird though."

// access pointer to the nth b_car, starting from zero; // returns a zero (nil) ptr when n >= length (ie blen(n+1)); // zero-based car element or nil; semantically (*this)[n] yp* bnth(n32 n) const; // &b_car of nth pair, zero-based yp* operator[](n32 n) const { return this->bnth(n); } «

"Method bnth() skips n pairs and then returns the address of the b_car of the next pair," Wil explained. "So if n is zero, no pairs are skipped and b_car of the current pair is returned."

"I suppose a null pointer is returned when the list is not long enough?" Zé guessed. "If n exceeds length?"

"Exactly," Wil said. "And operator[] is the same."

// non-nil ptr to &b_car for cadr ONLY IF length == two yp* blen2cadr() const; // cadr ONLY IF length exactly two }; // struct ypairb can be safely cast back and forth to yp2b

"Let's go over blen2cadr() when we see the code below," Wil suggested. "The comment is correct though."

"I can imagine a lot more pair methods," Zé noted.

"I know!" Wil sang. "I'll add them at need later."

ypairb.cpp «

"These ypairb methods are non-inline code," Wil introduced. "Method notb() logs when a peg is not a pair."

ypairb* ypairb::notb(yp const& p) { « // log error & ALWAYS return zero=nil ypairb* b = (ypairb*) p.u.p_box; if ((3 & (yp::p_t) b) == 0) // box? yellf(__LINE__,__FILE__,"ypairb::notb(p=0x%lx) is %s", (long) b, b->btag().tname()); else // immed yellf(__LINE__,__FILE__,"ypairb::notb(p=0x%lx) is immed", (long) b); return 0; // nil pointer }

// true iff b_car == car and blen(n+1) == n (ie bcmplen(n)==0) bool ypairb::bmatch(yp const& car, n32 n) const { « return b_car == car && this->blen((int) (n+1)) == n; }

bool ypairb::bmatch(ybox* car, n32 n) const { « // easier to use when car is yyb* return b_car == car && this->blen((int) (n+1)) == n; }

"As mentioned earlier," Wil pointed, "bmatch() is true if a list is exactly length n and starts with the value given."

// use blen(n+1) to see if length of list is lt, eq, or gt n // neg: blen(n+1)<n; zero: blen(n+1)==n; pos: blen(n+1)>n int ypairb::bcmplen(n32 n) const { « // compare blen(n+1) & n: return blen(n+1)-n return (int) this->blen((int) (n+1)) - (int) n; }

"Code for bcmplen() is self explanatory once you know what blen() returns: the list length capped to the value passed or one more. So bcmplen() returns list length ordering."

// access pointer to the nth b_car, starting from zero; // returns a zero (nil) ptr when n >= length (ie blen(n+1)); // zero-based car element or nil; semantically (*this)[n] yp* ypairb::bnth(n32 n) const { « // return &b_car of nth pair starting from zero const ypairb* p = this; // next pair to visit (zeroeth elem) do { if (0 == n) // passed n elems already? zero more to skip? return (yp*) &p->b_car; // cast away const --n; // skip another elem p = ypairb::mayb(p->b_cdr); // non-nil if it's a pair } while(p); // cdr another pair? (nb: ignore dotted lists) return (yp*) 0; // list was not long enough: return nil }

"Method blen2cadr() returns the second list element, but only if list length is exactly two," Wil summarized.

// non-nil ptr to &b_car for cadr ONLY IF length == two yp* ypairb::blen2cadr() const { « // return cadr ONLY IF length is exactly two const ypairb* p = this; // next pair to visit (first elem) yp* cadr = 0; n32 n = 0; do { if (++n == 2) // found second elem containing the cadr? cadr = (yp*) &p->b_car; // cast away const else if (n > 2) // more than two? return 0; // fail with nil when length not exactly two p = ypairb::mayb(p->b_cdr); // non-nil if it's a pair } while(p); // cdr another pair? (nb: ignore dotted lists) return cadr; }

"I see we're coming up on that lame blen() that doesn't detect cycles," Zé noticed. "Let's look at the old version first. Then I'll rewrite it for you."

"What's so big about detecting list cycles?" Stu asked.

"If you didn't stop scanning, you'd have an infinite loop," Zé explained. "Wil avoids that by stopping eventually, but only after burning more cycles than necessary."

"Note blen() returns at least one since length can't be zero when a pair passed as this is a first elem," Wil said.

// list length (safe from cycles by virtue of max length x); // x is max length targeted; if x<0, x is (100*1024*1024); // if x is zero, blen() always returns 1 (positive length); // return length if x is more than length; else x or x+1 // (length of list or x, whichever is less) n32 ypairb::blen(int x) const { « // return len of list or x, whichever is less n32 max = (x < 0)? (100 * 1024 * 1024) : (n32) x; n32 n = 0; // length must reach one: this instance is first const ypairb* p = this; // next pair in list to count do { // always perform loop at least once if (++n >= max) // length after this pair reaches the max? return n; p = ypairb::mayb(p->b_cdr); // non-nil if it's a pair } while(p); // cdr another pair? (nb: ignore dotted lists) return n; // reached end of list before max; this is length }

cycle detection «

"How do you improve blen() as shown above with cycle detection?" Stu asked.

"That's a classic interview question," Zé noted. "All you need is two cursors advancing through a list at different speeds. If the fast one sees the slow one, you have a cycle."

"That sounds simple and complex, both," Stu whined.

"If you're done beating me up for being lazy, let me take a crack at a second draft," Wil said. "If I see a cycle, I'll immediately return max+1 since actual length is 'infinite'."

n32 ypairb::blen(int x) const { // new code detects cycles « // return len of list or x, whichever is less n32 max = (x < 0)? (1024 * 1024 * 1024) : (n32) x; n32 n = 0; // length must reach one: this instance is first const ypairb* p = this; // next pair in list to count const ypairb* slow = p; // slower, half-speed cursor do { // always perform loop at least once if (++n >= max) // length after this pair reaches the max? return n; p = ypairb::mayb(p->b_cdr); // non-nil if it's a pair if (yunlikely(p && p == slow)) // cycle detected? return max + 1; // cycled list length is 'infinite' if (0 == (n & 1)) // length is even this time? slow = ypairb::mayb(slow->b_cdr); // advance half speed } while(p); // cdr another pair? (note: ignore dotted lists) return n; // reached end of list before max; this is length }

"That looks better," Zé gloated. "Wait, you didn't test it? It's not done until it's tested."

"You just saw me write it!" Wil objected. "No, I didn't test it. I promise to check it out later."

"Won't it go slower?" Stu asked. "Is that good?"

"Slightly slower," Wil agreed. "But it detects pathological states faster, saving cycles on upper bound paths. If you can't afford linear time code, you shouldn't use a list."

"What about nutballs who run micro-benchmarks?" Zé reminded. "I bet it's the first thing Dex will do."

"Why don't you knock some sense into him for me?" Wil asked. "Expand his perspective a little."

scan latency «

"What's your plan to reduce list scan latency?" Zé asked.

Stu's eyes boggled. "What are you talking about? Scanning for end of a list takes a long as it takes. Doesn't it?"

But Wil knew what Zé meant. "That's not a format problem," he excused. "We're just doing box formats now."

Zé drummed his fingers. "You were just going to let other green threads wait while blen() steps through ten million list pairs?" he demanded. "I know you better than that."

"Green threads?" Stu was lost. "What green threads?"

Wil turned to Stu and explained, "It's not fair to other flows of control to make them wait arbitrary amounts of time for more cycles. Their latency would suck."

"Oh," Stu realized. "C++ uses native threads for that problem. There's no provision for pre-emption otherwise. Are we talking about pre-emptive scheduling?"

"No," Wil corrected. "Zé means blen() should scan a list incrementally, no more than N pairs at once so time before it returns is under some reasonable upper bound."

"Cooperative scheduling," Zé told Stu. "Long running primitive methods can return with a code saying, 'I'm not done so please call me again so I can make more progress.'"

"When I do it with trampolines," Wil explained, "it will make C or C++ methods look really weird when continuation passing is simulated. Initial toy code should skip it."

"I think it's fun," Zé enthused. "Do it first."

"No," Wil glared. "It'll be too easy to write bugs. I'm thinking toy lathe code can be used to emit C or C++ trampoline code; I can rev that several times more cheaply."

"Ohhhh," Zé smiled. "That sounds even more fun. Your mindful shtick is useful sometimes."

"Are we done with boxes?" Stu wondered.

"No, I just got distracted," Wil said. "Some gc support next."

gc linkage «

yforeb «

"Okay, this yforeb box is a behind the scenes type for use in gc," Wil introduced. "It's basically the same thing as a forwarding pointer in early 90's ML."

"Wait, wait, I get it," Zé ethused. "Every time you copy an old box during gc, you overwrite the old box with an instance of yforeb pointing to the new copy."

"Ding, ding, ding," Wil congratulated. "After a collected box b is moved, the yforeb left behind tells you what new pointer replaces each future reference to b seen."

// yforeb is used to forward refs during garbage collection struct yforeb { « static const int kind = yt::k_fore; « yp b_forward; // where the box was moved «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_fore, e_bt = ((sizeof(yp)*1)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } yforeb() { } // default yp sets value to yp::i_nil « };

"Doesn't that imply a box can't be smaller than a yp pointer?" Stu asked. "Since a yforeb must fit inside any box?"

"Yes it does," Wil agreed. "So any objects like an empty vector or string that might be legitimately be zero sized must actually be at least four bytes in size."

"Except those degenerate cases should be immutable shared global instances," Zé observed, "since they can't be modified — having no state — they might as well be unique."

"Wil," Stu prodded gently, "would it have killed you to name the box yforwardb instead? What's three more letters?"

"Yes, it would have killed me," Wil said calmly. "My doctor said longer names can put me in prophylactic shock."

"Your sarcasm is stale," Stu criticized.

ybackb «

"Uh, could a ybackb box work like the yforeb forwarding pointer above?" Stu asked. "But why a backward reference?"

"Not quite," Wil said. "Early 90's ML had a backward reference to the start of a containing gc box object. This allowed you to point into the middle of a gc box."

"Oh that's right," Zé remembered. "Code continuations were done that way for code stored inside strings. Code entry point targets for return addresses were preceded by back refs."

"Yes, it effectively allows you to pretend the middle of a string is the start of a box," Wil said. "But during gc you need to figure this out and find the real box start exactly."

// ybackb embeds non-peg boxes in other non-peg boxes struct ybackb { « static const int kind = yt::k_back; « i32 b_offset; // offset to outer box holding this inner box «

ybackb() : b_offset(0) { } «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_back, e_bt = ((sizeof(i32)*1)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } };

"Is that how you're going to use ybackb too," Stu asked. "The same way ML did? Any reason not do do so?"

"I don't know yet," Wil shrugged. "I'll figure it out later and make any changes to ybackb that seem helpful."

objects and classes «

Material from this column describing yobjb object boxes and yclassb class boxes has been moved to class where

a Smalltalk style object system can be treated in one place. However, so this page includes at least summary material on every box format, abbreviated hash and symbol box api appears below. However, few methods shown here — only those in common with most box formats. Please see class for the full api.

yobjb «

The following code omits comments; see yobjb on the class page for full api and comments. An object box describes a Smalltalk style object: a record with a class dispatching methods polymorphically by duck-typed message sending.

struct yobjb { « static const int e_bk = yt::k_obj; « yp b_class; // the class for this object « yp b_slot[1]; // first of yt::t_len p slots «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_obj; } « };

yclassb «

The following code omits comments; see yclassb on the class page for full api and comments. A class box describes a Smalltalk style class or metaclass.

// yclassb must be physical yobjb subtype in terms of format struct yclassb { « static const int kind = yt::k_class; « yp b_class; // the class for this object (yobjb::b_class) « yp b_superclass; // base class « yp b_subclasses; « yp b_methodDict; « yp b_fields; « yp b_instVars; « yp b_instVarDict; « yp b_name; « yp b_classPool; « yp b_classInstance; «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_class, e_bt = ((sizeof(yp)*10)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } yclassb() { } // yp() constructor puts yp::i_nil into each « };

big integers «

Material on big integers describing yintb bigint boxes has been

moved to bigint where they can be treated in one place, and possibly other big numbers as well. However, so this page includes at least summary material on every box format, abbreviated bigint box api appears below. But few methods shown here — only those in common with most box formats. Please see bigint for the full api.

yintb «

yintb

struct yintb { « static const int kind = yt::k_int; // bigint « yp b_digits; // p to cord of byte digits «

bool neg() const { // is sign of this big int negative? « return ((const yt*) this)[-1].isescaped(); } void setneg(bool b) { ((yt*) this)[-1].tescape(b); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_int, e_bt = (sizeof(yp)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } yintb() { } // default yp for b_digits: equal to yp::i_nil « };

hashes and symbols «

The remainder of this column describing yhashb hash boxes and yyb symbol boxes has been

moved to symbol where symbols can be treated in one place, along with hashmaps used for intern tables. However, so this page includes at least summary material on every box format, abbreviated hash and symbol box api appears below. However, few methods shown here — only those in common with most box formats. Please see symbol for the full api.

yhashb «

The following code omits constructors; see yhashb on the symbol page for full api and comments.

// minimal support for hashmaps of symbols kept in ysb format // yhashb holds a hash for yyb, and a link for making lists struct yhashb { « static const int kind = yt::k_hash; « yhashb* b_next; // linked list of hashes (this is a gc peg) « u32 b_h32; // aims to be zlib crc32() hash of a symbol «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_hash, e_bt = ((sizeof(yp)*2)<<16)|yt::e_c|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } void badt(const char* where) const; // on false bt() is }; // yhashb must precede yyb, but yyb need not follow yhashb

yyb «

The following code omits many additional methods; see yyb on the symbol page for full api and comments.

// yyb looks like ysb with mandatory hash and is always const // yyb is identical in format to ysb, but preceded by yhashb struct yyb { « static const int e_bk = yt::e_c|yt::v_sym; // yt::e_c=CONST « u8 b_u8[4]; // first four of this->len() u8 slots «

u32 vblen() const { return ((const yt*) this)[-1].len(); } « u32 blen() const { return ((const yt*) this)[-1].len(); } « bool bkind() const { « return ((const yt*) this)[-1].cvkind() == (u32) e_bk; }

static u32 n2t(n32 n) { return (n<<16)|e_bk; } « // yyb differs from ysb in: // 1. always const, 2. yhashb always before

static u32 v2t(yv const& s) { « return (s.v_n<<16) | yesc(s) | e_bk; }

struct Yq { yyb const& q_y; Yq(yyb const& y): q_y(y) { } }; « Yq quote() const { return Yq(*this); } « void bprint() const; // dump to stdout via yout void bdump(yo& o) const; void bcite(yo& o) const; //void bshow(yo& o) const; n32 bcage(n32 max) const; }; // yyb (symbol box)

license «

All this code is available only under the BriarPig mu-babel license described fully on the rights page. You do not have permission to reprint this page in any way. Neither feeds nor repackaging is allowed. You can link this page if you want folks to read it.

menu

mu, toy, peg, imm, tag, box « Þ, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile

(thorn, todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node, primes, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter, ctype)

abbreviated api «

Zé scratched his jawline and pondered an imbalance he observed in code for box formats. "You know," he said. "It's odd pairs and symbols seem fleshed out, but little else has detail."

"There's a good reason for that," Stu said confidently.

"Oh yeah," Zé looked interested. "What is it?"

"I don't know," Stu admitted snickering. "But I'm sure Wil has a good reason. Or a rationalization."

"Comedian," Wil accused. "One day I was carefully putting meat on bones of all the boxes and I asked myself a question."

"'Why am I working so hard?'," Stu suggested, then wilted under Wil's glare. "I shouldn't say your lines for you?"

Wil held up a hand. "I asked myself," he continued, "why am I writing code breadth-first that I don't need to call yet?"

"Ahhh," Stu pretended to follow, then, "I still don't get it."

"When you write code you're not calling," Wil explained, "you get disconnected from evidence and feedback."

"Next thing you know," Zé contributed, "you wander off in the weeds and get lost chasing butterflies."

"Strange metaphor," Wil frowned. "I'd say you build traps to capture animals not now in evidence."

"Is that hunter thing working for you?" Zé sniped.

"In any case," Wil continued. "You start to run out of energy when you're sucking vacuum."

"Okay, that part I understand," Stu nodded.

"Once I saw the pattern was going to work if I continued," Wil explained, "I switched my attention to reading and writing."

"Then you can come back to any one box later," Zé guessed, "as soon as you want to do something with it in live code."

"Exactly," Wil grinned. "They I'll be able to execute something right after I write it. Fast turnaround is bliss."

"I'm pretty sure gold or ignorance is bliss," Stu said.

tuples «

"Does tuples mean the same thing it does in other languages?" Stu asked. "In Python tuple means a very specific thing: a kind of immutable array."

"That's a great question," Wil smiled. "The word tuple applied to a toy language box only means ordered sequence of values, including different types, mutable or not."

"So it's a very generic mathematical definition of tuple," Zé said. "You could even say a list was a tuple."

"I guess I use tuple to mean fixed format even if mutable, and lists are too variable," Wil mused. "So let's avoid saying tuple when using lists, unless you're talking about semantics."

"Well then, tuple describes practically any struct," Stu groused. "What's the point?"

"Tuple is very generic in math — much like thing, or maybe object in oo languages," Zé suggested. "Merely grouping a set of items with an order gives you a tuple."

"So pairs are tuples, vectors are tuples, and class instances are tuples?" Stu asked. "What good is that?"

"It expresses an idea you focus on the set of grouped values," Zé explained, "without weighing physical form much."

Wil nodded. "That sounds good," he said. "And tuple members are accessed by either number or symbols."

"So tuple member names are like map keys?" Stu asked. "Except when keys are integers, you can use a vector?"

"Yeah," Zé agreed. "Symbol names as keys just means someone has to lookup the symbol in a map and find an associated index or offset for that name."

"Isn't that what compilers do with struct member names?" asked Stu. "How are Smalltalk style objects different?"

"Very perceptive," Wil said. "A compiler maps names to offsets statically at compile time, and dynamic languages might delay the map lookup until runtime."

"And usually do," Zé noted. "Lookaside caches optimize away repeat map lookups for speed. Standard stuff."

"So a Smalltalk style object might physically just be an array of N slots," Wil explained. "And the class maps member symbol names to a slot index. Thus any object is a tuple."

"In Smalltalk," Zé recalled, "members are all private: only visible in class methods. So compiling a method maps names to indexes at compile time, not at runtime."

Stu stopped to think, so Wil pointed Zé at the next box. Before they could proceed, Stu blurted out another insight: "So single values are like a 1-tuple?"

"If you insist," Wil shrugged. "You can think of all single value boxes as 1-tuples of slightly different primitive format. In fact, all boxes are just basic tuple architecture."

Stu looked excited, so Zé nudged him and said, "But you knew this already, right?"

yp2b «

"Box yp2b is basically identical to ypairb, but with a different name," Wil introduced. "The reason you might bother using it? To access by integer index."

"It's name means two peg box?" Stu asked.

"Yes, I suppose the name might have been y2pb instead," Wil considered. "But I'm used to suffixing numbers."

"Just read the name as peg pair box," Zé suggested.

struct yp2b { // pair « yp b_p[2]; // (synonymous with ypairb) «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_p2, e_bt = ((sizeof(yp)*2)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } }; // struct yp2b can be safely cast back and forth to ypairb

yp3b «

"Aha, then yp3b means peg triple box?" Stu concluded.

"Exactly, and there's not much else to say about it," Wil said. "The answer to question 'what is it for?' is: I don't care. It's the same answer for all tuples: whatever you want."

struct yp3b { // triple « yp b_p[3]; // peg triple «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_p3, e_bt = ((sizeof(yp)*3)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } yp& operator[](unsigned i) { return b_p[i]; } « yp3b() { } // default yp inits each member of b_p[i] to nil « };

yp4b «

"Okay, so yp4b means a four peg box right," Stu said without enthusiam. "What's it for? Along with yp1b, yp2b, and yp3b, it's redundant with the vector box that's coming."

struct yp4b { « yp b_p[4]; «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_p4, e_bt = ((sizeof(yp)*4)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } yp4b() { } // default yp inits each member of b_p[i] to nil « };

"You're right," Wil agreed. "I guess my intent was a little fuzzy. But it basically involves one idea: using more box types in a complex graph can give you something to check."

"You mean a kind of dynamic type checking?" Zé asked. "Say, unless a box is exactly the type expected, then something must be wrong? Isn't that just a bit subtle?"

"Yes," Wil conceded. "But I can use the 7-bit alt field in a tuple's tag as a kind of extra type signature, if I build non-user-visible graphs using primitive boxes. Hypothetically."

Zé winced. "I think you should just use Smalltalk style objects for complex graphs you build," he suggested. "Otherwise you'll be writing a lot of odd one-off code."

numbers and vectors «

As described on types (under þ) many signed and unsigned integers types, as well as floating point types, are declared with specific bit widths. Boxes below declare both single instance versions and vector versions of all integer and floating point types.

"Note the circumstances under which these might be used under Lathe at the language level will not be described," Wil warned. "It suffices here to show they exist."

i128 «

"The following i128 type declares a pseudo-128 bit integer," Wil cautioned, "bigger than any native native C integer type."

"So you would have to simulate 128 bit arithmetic," Zé asked. "Almost like a big int with only 128 bits?"

"Something like that," Wil agreed. "Or you could just use it for something 128 bits in size, like an MD5 hash."

struct i128 { // 16 bytes of int (ie md5 digest 16-byte hash) « union { // to support a variety of access styles u64 i_u64[2]; « u32 i_u32[4]; « u8 i_u8[16]; « } u; « void clear() { u.i_u64[0] = u.i_u64[1] = 0; } « }; // struct i128

"No arithmetic on these is defined without more code, right?" Stu asked. "I guess asking you whether you'll do that soon is out of order? Maybe the first milestone toy draft?"

"I don't have a schedule for using it," Wil sighed. "But I do have a check already for providing space for it as a box."

yi128b «

"Box yi128b simply delares a field of type i128," Wil said.

struct yi128b { // box for 'integer' with 128 bits « static const int kind = yt::k_i128; « i128 b_i128; // twice the size of i64 «

yi128b() { b_i128.clear(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_i128, e_bt = (sizeof(i128 )<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } };

yi128vb «

"The tag for box yi128vb has the yt::e_v vector bit set," Wil said. "So length vblen() is a count of i128 instances."

struct yi128vb { « static const yt::Tvec kind = yt::v_i128; « i128 b_i128v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].isTvec(kind); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_i128; } « };

yi16vb «

"The tag for box yi16vb has the yt::e_v vector bit set," Wil said. "So length vblen() is a count of i16 instances."

"Why is there no box for a single i16?" Stu asked. "Is it too small to bother with?"

"Yes," Wil nodded. "An immediate integer requiring no box at all is 30 bits in size, which dominates 16 bits in i16."

/*struct yi16b { « static const int kind = yt::k_i16; i16 b_i16; // unused because imm int subsumes this size };*/

struct yi16vb { « static const yt::Tvec kind = yt::v_i16; « i16 b_i16v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].isTvec(kind); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_i16; } « };

yu16vb «

"I guess the same thing applies to yu16vb?" Stu asked. "Since immediate ints have 30 bits, there's no point in having a non-vector yu16b box?"

"Yes," Wil confirmed. "And the tag for box yu16vb has the yt::e_v vector bit set, so length vblen() is a count of u16 instances."

/*struct yu16b { « static const int kind = yt::k_u16; u16 b_u16; // unused because imm int subsumes this size };*/

struct yu16vb { « static const yt::Tvec kind = yt::v_u16; « u16 b_u16v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].isTvec(kind); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_u16; } « };

yi32b «

"Box yi32b is only useful for 32-bit integers that don't fit into 30-bit immediate ints," Wil remarked. "It seems a waste to alloc a box when only two more bits are needed."

struct yi32b { « static const int kind = yt::k_i32; « i32 b_i32; // signed int (normally outside imm int range) «

yi32b() : b_i32(0) { } «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_i32, e_bt = (sizeof(i32)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } };

yi32vb «

"Box yi32vb is the vector version of yi32b with a single 32-bit integer," Wil said. "And vblen() is the vector length."

struct yi32vb { « static const yt::Tvec kind = yt::v_i32; « i32 b_i32v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].isTvec(kind); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_i32; } « };

yu32b «

"Looks like box yu32b is identical to yi32b but unsigned," Zé noted. "Seems redundant. Just being thorough?"

"Sure," Wil said. "If someone has a large number of unsigned integers to store, why make them use a format with less than perfect results? A UI might be awkward."

struct yu32b { « static const int kind = yt::k_u32; « u32 b_u32; // unsigned int (normally outside imm int range) «

yu32b() : b_u32(0) { } «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_u32, e_bt = (sizeof(u32)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } };

yu32vb «

"Box yu32vb is the vector version of yu32b with a single 32-bit integer," Wil said. "And vblen() is the vector length."

"Criminy," Zé whined. "Are you going to repeat yourself for every vector type? I'm gonna fall asleep."

struct yu32vb { « static const yt::Tvec kind = yt::v_u32; « u32 b_u32v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].isTvec(kind); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_u32; } « };

yi64b and yi64vb «

"Alright, let's speed it up a little," Wil mollified. "Box yi64b and box yi64vb are single and vector versions of boxes for 64-bit signed integers. Is this any better?"

struct yi64b { // single i64 box « static const int kind = yt::k_i64; « i64 b_i64; // signed int 64-bits «

yi64b() : b_i64(0) { } «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_i64, e_bt = (sizeof(i64)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } };

"As usual," Zé kibitzed, "the vector length is vblen()."

struct yi64vb { // vector of i64 « static const yt::Tvec kind = yt::v_i64; « i64 b_i64v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].isTvec(kind); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_i64; } « };

yu64b and yu64vb «

"For unsigned 64-bit integer boxes, yu64b holds one instance, and yu64vb is the vector version," Wil summarized.

struct yu64b { // single u64 box « static const int kind = yt::k_u64; « u64 b_u64; // unsigned int 64-bits «

yu64b() : b_u64(0) { }«

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_u64, e_bt = (sizeof(u64)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } };

"My turn," Stu pounced. "yu64vb vector length is vblen()."

struct yu64vb { // vector of u64 « static const yt::Tvec kind = yt::v_u64; « u64 b_u64v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].isTvec(kind); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_u64; } « };

yr32b «

"Box yr32b holds a single 32-bit native C float," Wil explained. "See types for scalar declarations including r32."

struct yr32b { // box for 32-bit float « static const int kind = yt::k_r32; « r32 b_r32; // floating real 32-bits «

yr32b() : b_r32(0.0) { } «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_r32, e_bt = (sizeof(r32)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } };

yr32vb «

"Box yr32vb is a vector of 32-bit native C float instances," Wil continued. "And the length is vblen()."

struct yr32vb { // vector of 32-bit floats « static const yt::Tvec kind = yt::v_r32; « r32 b_r32v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const yt*) this)[-1].isTvec(kind); }

static u32 n2t(n32 n) { return (n<<16)|yt::v_r32; } « };

yr64b «

"Box yr64b holds a single 64-bit native C double," Wil explained. "See types for scalar declarations including r64."

struct yr64b { // single 64-bit double box « static const int kind = yt::k_r64; « r64 b_r64; // floating real 64-bits «

yr64b() : b_r64(0.0) { } «

const yt& btag() const { return ((const yt*) this)[-1]; } « enum { e_bk = yt::k_r64, e_bt = (sizeof(r64)<<16)|e_bk }; bool bkind() const { « return ((const yt*) this)[-1].iskind(e_bk); }

bool bt() const { return e_bt == ((const u32*) this)[-1]; } };

yr64vb «

"Box yr64vb is a vector of 64-bit native C double instances," Wil continued. "And the length is vblen()."

struct yr64vb { // vector of 64-bit doubles « static const yt::Tvec kind = yt::v_r64; « r64 b_r64v[1]; // vector of length tag().len() «

u32 vblen() const { return ((const yt*) this)[-1].len(); } «

const yt& btag() const { return ((const yt*) this)[-1]; } « bool bkind() const { « return ((const