Þ   briarpig  » mu  » symbol

     symbol — a symbol is a kind of gc box strongly related a strings, typically used to identify other objects more efficiently than strings by using box address instead of content bytes inside as the key in some map.

     This page covers box formats and maps supporting symbols in toy programming language lathe: a lisp dialect plus smalltalk class system (using þ library under a mu-babel license — see mu for context).

     For purposes of use in Lisp and Smalltalk, it's only necessary that two symbols with the same name are identically the same object (with special exceptions allowed for uninterned symbols with different identity from any other symbol, whether or not names are the same). In Lisp dialects like Scheme, an unquoted identifier like lambda is understood to be a symbol, whereas "lambda" is a string. In Smalltalk, a literal written #lambda is a symbol, and 'lambda' is a string. (And awkward symbol names containing non-identifier letters can be understood as symbols anyway by quoting. So for example, to embed a space in a symbols one can write |foo bar| in Lisp and #"foo bar" in Smalltalk, and Lathe will support all these variants.)

     However, most of this page doesn't concern symbols as they appear in either Lisp or Smalltalk; instead a C++ representation for symbols in memory is described. Also described is an efficient hashmap for representing canonical instances of symbols with a given name: an intern table in traditional Lisp jargon.

     The format of symbols is deliberately strongly tied to that of strings, so code can use either as text.

     Lathe's primitive string box, ysb, uses pointer plus length format with string address pointing to the first octet in a string, and with length held in the tag preceding the string. A totally gratuitous redundant null byte follows content of a string, to be friendly with C runtimes, and to act as a sentinel detecting overwrites. In effect, a primitive Lathe string looks like a C string, but with a dynamic type tag in 16 bits of the immediately preceding four bytes. Any null byte found inside is not null termination; if you use null as a length marker, you'll have bugs: it's wrong. Strings contain octets, not characters — neither charset nor codepoint size are specified, and both are imposed from without at a higher, non-standard level.

     Lathe's primitive symbol box, yyb, has format identical to ysb strings with a few minor exceptions, so both symbols and strings can be used as text objects — sequences of octets — without awkward games to force similarity. Exceptions making symbols differ from strings include the following:

• the preceding yt type tag has a different kind
• symbols are always immutable with yt::e_c set
• a yhashb hash box always precedes a symbol
• symbols are usually interned in hashmaps

     The purpose of a hash box before each symbol is twofold: 1) to cache a collision resistant hash better then a symbol's address, and 2) to provide hashmap bucket list linkage without breaking format compatibility with ysb strings.

     In some revs of Wil's Lathe runtime, immutable symbols might all be packed together in shared pages in book instances devoted to immutable objecdts, which are mapped readonly (each time a page fills) to enforce the cooperative yt::e_c const bit in yt tags with greater vigor.

     The remainder of this column originally appeared on box with other gc box formats.

yvh32 «

     "Class yvh32 is just a utility — it's not a box," Wil said. "It belongs in the crc demo, and uses the yh32 api there by way of yv::vhash() to use crc32."

     "Why does it appear here?" Stu asked. "To keep it close to where it's used? Do hash boxes use it?"

     "Yes to both," Wil said. "The yvh32 constructor uses crc32 to hash the byte run; the value lands in member h_32. It's a way to use types to ensure hashing gets done."

     "Your hash demo shows why you like using crc32," Stu observed. "Tell folks they should read that."

yhashb «

     "So this yhashb box is where the crc32 hash ends up?" Zé prompted. "Why the extra b_next pointer member?"

     "The b_next link is for open/chaining hashmap buckets," Wil explained. "It might be applicable to other objects needing a hash, but I really want this for yyb symbol boxes."

     "Isn't it awkward to bundle a next link with a hash like that?" Stu asked. "Doesn't it couple state too much?"

     "Too much for what?" Wil asked. "It's only barely a hack: it doesn't say what sort of object uses a hash and link."

     "Wow, that's a lot of constructors," Stu murmurred. "Why so many? Does it make other code simpler?"

     "I like having one I want in hand already," Wil said. "It does reduce hoops to jump through when using it. As inlines, cost is negligible. And the api spec is better."

     "Hey, look," Zé pointed. "The e_bt box tag for yhasbb includes the yt::e_c const bit. Does it limit client choice?"

     "Yes, so far I intend to require a hash box be immuable," Wil said. "That fits use with const symbols better. I won't change it unless I see reason later."

     "It's disturbing the value to be hashed isn't also in the box," Stu worried. "Does it come after?"

     "It does in the case of yyb symbol boxes shown below," Wil qualified. "I have no other use for yhasbb yet; I might not bother using it again. For now it's a symbol helper."

     "So every hash box must be followed by a symbol?" Stu asked. "That seems awkward."

     "That's backwards," Wil corrected. "Every symbol must be preceded by a hash box, but not the reverse."

     "I guess a gc engine can preserve that easily enough," Zé considered. "Any time a collectable symbol is moved, gc can also ensure the preceding hash goes with it."

     "Aren't all symbols collectable?" Stu asked. "Or are all symbols not collected? I'm confused."

     "Symbols can be interned in a symbol table or not," Wil explained. "And they can be in gc space or not. Normally I'd prefer symbols not live in gc space."

     "But I guess you don't have a choice in apps that dynamically create more symbols," Zé suggested. "A sandboxed app must not create arbitrary symbols not subject to gc."

     "That's right," Wil confirmed. "Otherwise denial of service would be possible in untrusted apps. A sandbox would be able to consume memory that's not reclaimed."

     "You're getting ahead again," Stu sighed. "Are you doing it on purpose? Why not save this for the yyb box below?"

     Wil half-smiled. "An implicit message is this: things aren't tidy. It's not safe to read about symbols in one place only. You have to read the entire page. And other pages, too."

     "If you want to work on the C++ code, that is," Zé qualified. "A Lisp and Smalltalk view won't expose complexity."

     Wil squinted in thought. "I might need to make it possible to ask more about symbols in Lisp. But not required."

yhashb.cpp «

     "Non-inline methods for a yhashb only involve logging errors," Wil dimissed. "This reports invalid tags."

yhashb_t «

     "The following yhashb_t struct is a kludge for seeing distance between a hash box and the following symbol," Wil explained. "Every box is separated by a yt tag."

     "Oh, I see," Zé chimed. "Since each symbol is preceded by a hash box, you use sizeof(yhashb_t) as pointer offset."

     "Member b_t represents the tag after the hash box and before the symbol box?" Stu asked. "Oops, I see that's exactly what the comment says."

     "Dex would complain a _t suffix on the yhashb_t means 'type' and should be a synonym for yhashb," Zé observed.

     "Well here he'd be wrong," Wil grinned. "The underscore separates a tag+box pair, and the t means tag."

     "I'm just sayin'," Zé mollified. "Don't get mad."

     "I'm not mad," Wil said calmly. "Names I use are consistent. Mostly. I just cut a few corners."

yyb «

     "You mentioned yyb is a symbol box so many times already," Zé rubbed his chin, "it no longer looks as cryptically short. Was that a deliberate tactic? You sly dog."

     "Ah, yes," Wil said. "Not sneaky — just practical. The first y means thorn and the second y means symbol. The final b means box. I wanted a short name for symbols."

     "I get it," Stu nodded. "Most of your global code names begin with y to say it's a global symbol. It's a bit of a pun."

     "Let's go on," Wil suggested. "Yes, it's a good mnemonic. But at heart I think names are arbitrary."

     "Member b_u8 is the array of octets in a symbol," Wil introduced. "The number of octets in the symbol is in the high 16 bits of the tag. The first four are reserved here."

     "That you say octets here instead of characters is telling," Zé said. "Can symbols be anything? Even Unicode?"

     "Physically any byte sequence, yes," Wil nodded. "But the toy parser is still going to think keywords, for example, are octet sequences of ascii names."

     "No problem, just checking," Zé assured. "I wanted to confirm infrastructure doesn't require ascii."

     "Okay, well add two more details to your symbol model's physical representation," Wil said. "First, physical length of a box must be a multiple of four bytes to maintain alignment, so allocated space is rounded up. Four for b_u8 is a minimum."

     "Okay, and the second detail?" Zé prompted.

     "By convention," Wil continued, "each symbol is followed by a null byte, which is not part of the octet sequence. This is meant to be friendly to C runtimes, especially when debugging."

     "You can use it to help detect corruption too," Zé suggested. "For length N, you can assert the byte at index N is zero."

     "Yes, but it's not null termination," Wil reminded. "Symbols can have null bytes inside."

     "So blen() is symbol length in octets," Stu restated.

     "Yes, logical length of yyb is blen()," Wil elaborated. "And the physical length is at least one more, then rounded up to a multiple of four. And gc must do this to skip each symbol."

     "How do you figure total bytes needed?" Stu asked.

     "Right now I use bmore() to reckon number of extra bytes needed after sizeof(yyb)," Wil indicated. "It drops the low two bits of the size, rounding down to a multiple of four."

     "Hmm," Zé considered. "And since b_u8[4] covers three content bytes and a trailing null byte, that never fails to be enough."

     "But doesn't it add an extra four bytes when length is exactly a multiple of four?" Stu asked. "Wasting four bytes?"

     "Well, no," Wil said gently. "After N content bytes, you need one trailing null byte, which must be rounded up to four."

     "Ah," Stu slapped his head. "Trickier than I thought."

     "Okay, what's an escaped symbol?" Stu asked. "Does it affect printing again like it does escaped pairs?"

     "Yes," Wil confirmed. "It means a symbol name contains a value needing an explicit delimitor for a parser to read correctly."

     "You can capture that right when a symbol is created, can't you?" Zé noticed. "By scanning a symbol at instantiation?"

     "That's right," Wil nodded. "And yesc() above returns either zero or escape bit yt::e_e for the symbol's tag. I guess it should be named besc(). And it works only on ascii."

     "Huh?" Zé paused. "Oh, you're saying the escape bit only means a symbol must be escaped when it's being written for an ascii reader. I guess it depends on round trip method."

     "Yeah," Wil agreed. "And if you're using Unicode symbols, I figure you don't care how slow the system runs and I don't worry about optimizing print speed."

     "So for example," Zé wrote on a piece of paper, "if I wanted quotes in my symbol name the parser needs to use syntax |"foo"| to make a symbol whose name is "foo"?"

     "That's right," Wil nodded. "Then yesc() returns the escape bit when it sees a " quote inside the symbol name. So later it prints once again as |"foo"| with vertical bar quotes."

     "Cool," Zé smiled. "Sorry, let's go on."

     "Constructors set symbol name and trailing null," Wil commented. "But it's up to a caller to make sure a symbol is big enough with sizeof(yyb)+bmore(s.v_n) bytes."

     "Method h2y() is a non-inline dynamic cast from hash box to symbol box," Wil said. "It returns nil when anything looks wrong, such as when the following box is not a symbol."

     "Methods n2t() and v2t() return the symbol's tag needed for a given length or run of bytes," Wil said.

     "These notb(), mustb(), and mayb() methods look just like the dynamic casts for ypairb pair boxes," Zé noticed.

     "Yes, both mayb() and mustb() cast a peg pointer to the symbol box," Wil said. "Both return zero if the peg is not a symbol, and the latter logs an error for non-symbol pegs."

     "Inlines above very cheaply get the symbol's hash value," Wil explained. "It ought to be as cheap as normal member access. Type yhashb_t is only used to get distance right."

     "And inlines above convert a symbol to pointer and length representation using a yv run," Wil gestured.

     "It's actually kinda cool symbols are also C strings," Stu said.

     "I guess so," Wil agreed. "It should improve interoperation with C as long as bytes are kept immutable."

     "What's the maximum length of a symbol?" Zé asked. "Is it smaller than any other string?"

     "Darn it, I avoided discussing size limits so far," Wil mused. "Um, I think the parser imposes a limit of about 1024 bytes in one symbol name before it's split by a read buffer."

     "But outside the reader, there's no limit except what will fit inside one book instance?" Zé guessed.

     "Basically yes, and the tag's length field is only 16 bits," Wil noted. "If a book is bigger than 64K, then a tag's length field is the limit. You'll ask about string limits now, right?"

     "Hey, yeah," Stu chimed in. "How big can a string get? Is it limited to one book in size? 64K currently?"

     "As a single contiguous vector of octets, yes," Wil said. "But strings will also use discontiguous iovec formats."

     "So strings as discontiguous arrays composed of fragments can be as big as I want?" Zé asked.

     "Yes, but that's a slightly involved feature," Wil warned. "It won't be ready until I code it. Not complex though."

     "That operator looks interesting," Zé said. "It says whether a symbol equals a yvh32 argument? The key supplied has both hash and byte run, just like the symbol."

     "That's right," Wil confirmed. "This is used when searching a symbol hashmap to see if a symbol is already present."

     "So you don't have to stage a dummy yyb for comparison," Zé noted. "You can compare directly to a run where it sits."

     "Hey, you only compare content bytes when hash is equal," Stu appreciated. "So most of the time you'll only do a byte by byte comparison when a match is likely."

     "Nice analysis; and length has to match first too if you look at code for yv::operator==()," Wil expanded.

     "Above and below is the usual C++ debug printing boilerplate," Wil waved his hands. "Can I just point you at the out and quote demos? Lisp printing is separate."

     "Ah, I was going to ask about the Lisp printer," Stu explained. "Never mind, I'll wait to you reach that part."

yyb.cpp «

     "Below are yyb symbol box non-inline methods," Wil said. "Let's start with a dynamic cast from leading hash box to following symbol box. Note a symbol need not follow a hash box."

     "Basically what h2y() does is offset by sizeof(yhashb_t) and check the following box's tag to see if it's a simple," Zé read.

     "Good summary," Wil agreed. "The following globals are used by yesc() to see if symbol octets need escape when printed."

     "Is there an initialization order dependency with yum and yutm maps from the ctype demo?" Zé wondered.

     "Yes, I think there's a static init time order dependency, so it's not safe in separate compilation units," Wil confirmed. "I had most things in one file at one time."

     "You're kidding," Stu was appalled at the idea of one file.

     "No, I'm serious," Wil repeated. "I might have to put globals back in one file to ensure good init order."

     "Okay, yyb_1utm is a predicate equal to isalnum()," Wil said. "It's true for digits, lowercase, and uppercase."

     "And yyb_1v enumerates more bytes I want to use without escape in symbols" Wil said. "Maybe I need more."

     "Finally," Wil pointed, "yyb_1noescmap is a predicate containing the union of the two above. It might not init correctly unless the yutm module is ready."

     "You can make modules lazy init on first use to remove dependency issues," Zé suggested. "You've done that before."

     "Yes, I have," Wil agreed. "But I hate explaining why that works. I know, I should do it anyway."

     "Whoa, that's short," Stu marveled. "I guess yv::vall() returns true if every octet is true in the predicate?"

     "Yeah, not much else to say," Wil agreed. "And notb() below logs failure of dynamic casts mustb() shown earlier."

     "Debug printing code below just prints symbols in debug format when dumping symbol hashmaps," Wil explained.

     "Dude," Zé pointed. "What's that value stored in a symbol tag's alt field — that's seven bits in size, right?"

     "Uh," Wil tried to remember. "I think symbols that are special form keywords have a nonzero enum value, and it's stored there. An interpreter would use that value in a switch."

     "You're saying you can justify some class named ykMgbv?" Stu balked. "What does that mean?"

     "I think it means const machine global box vector," Wil replied. "That would be an array of well known immutable objects of global scope, including special form symbols."

     "You mean," Stu struggled, "if lambda is a Scheme special form symbol, an enum value meaning lambda is stored in the alt field of the yyb box for lambda in the symbol table?"

     "That's exactly what I mean," Wil confirmed. "An interpreter can tell a symbol is a special form when a nonzero value appears in the alt field, then use a switch to execute suitable code."

     "Do I shout 'computed gotos rule' now?" Stu wondered. "Or is it too early to celebrate?"

     Zé held one hand level and teetered it back and forth like the pans of a balance scale wobbling in near balance.

tyhashb_tyyb «

     "You were completely serious about naming a struct tyhashb_tyyb to combine both hash and symbol boxes together with their tags?" Zé marveled. "Symbol table use this?"

     "Yes," Wil sighed. "For a new symbol, yyb::bmore(n) plus size of tyhashb_tyyb is exactly what I need to allocate, including both hash and symbol boxes and their tags."

     "Didn't I just say that?" Zé pretended to be cross. "You keep using C++ to avoid drudgery. Isn't that poor style?"

     "You're asking me about a future C rewrite?" Wil asked. "Maybe I'll use toy lathe to generate a new infrastructure."

     "You're funny," Zé tried to elbow Wil. "You'd have to write a high level assembler in Lisp. Are you serious?"

tyhashb_tyyb.cpp «

     "You know what I hate about classes like tyhashb_tyyb?" Stu asked. "They declare stuff without showing what happens, even if it's a little interesting."

     "To see what happens," Wil suggested, "you should read the yyb symbol box constructor shown above — click on link yyb. Code below just says 'do it' and can't be faulted for brevity."

     "The don't-repeat-yourself principle implies you can't see things done in each place," Zé reminded. "You're really just saying you don't like C++ constructors because they say little."

     "Instead of tyhashb_tyyb.cpp, the constructors above actually appear right inside symbol hashmap code, next to where called," Wil corrected, "for better cache line locality."

     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.

     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)

     "Hey, Wil," interrupted Stu. "The comment next to member b_next in yhashb says it's really a peg."

     "That's what I was thinking," nodded Wil. "But it can only point to another yhashb hash box."

     "But the bucket chain in hashmap yym is zero terminated," Stu continued. "And that would put a zero pointer in the b_next member of yhashb."

     "Oops," Wil gulped. "You're right. I can either use yp::i_nil for list termination, or stop saying b_next is a peg."

     "I bet five dollars you stop saying it's a peg," Stu said.

     "Yeah," Wil agreed. "But I need to make sure it sticks: the gc engine had better know about it too."

     "Is class yym below used as an intern table for canonical symbols instances in a virtual machine?" Zé asked. "I understand from names this name must mean thorn symbol map."

     "Yes," Wil confirmed. "But I won't apologize for not naming it SymbolMap. You've got my name conventions down."

class yym «

     "How many instances of yym symbol map do you expect in a system," Stu asked. "Which is better: many or few?"

     "Few is better than many," Wil replied. "Each one can use a lot of resources, so many would be expensive."

     "And if symbols are immutable," Zé added, "Sharing of some kind ought to be easy — that's what you planned, right? Is yym part of future immutable world state?"

     "Yes, an instance of yym can be shared by each virtual macine," Wil confirmed. "It's a good place to put a canonical instance of each symbol appearing in modules for example."

     "What about symbols created dynamically at runtime?" Stu asked. "Say, unique symbols in requests to server?"

     "That's the problem case that must be solved in the long run," Wil said. "I can't let a symbol intern table permanently grow in size proportional to unique symbols in server requests."

     "So if you want tenured, global, shared symbols one place," Zé hypothesized, "and transient, local, isolated symbols elsewhere, does that imply a two tier scheme?"

     "Yes, I think it does," Wil agreed. "So one or few yym instances should be good for global sharing, and some other symbol table might be better for temp request-local symbol maps."

     "Can you guys hold off more big picture context until after we start the yym api, please?" Stu begged.

     "Private copy methods means yym can't be copied," Wil indicated. "This prevents accidental copying."

     "Pile instance m_H is the heap allocating all memory," Wil introduced, "including each book allocated by m_Bqm which keeps every book in both a list and a hashmap."

     "Looks like m_B is the current book in which new symbols are allocated," Stu chimed in. "And m_nlost counts fragmentation waste in earlier books? What's m_vfree?"

     "Aha!" shouted Zé. "I bet m_vfree points at the b_v member of the ytocb box at the start of the current book."

     "Bingo," Wil congratulated. "And m_v0 is where m_vfree points when it has no book to reference."

     "Those look like the same primes you use for hash maps like those in book and pile demos," Stu noticed.

     "Yes, one of those values goes into m_slots below," Wil said, "which is the length of the m_ypv vector of pointers to yhashb hash boxes, each of which is followed by a symbol."

     "You mean hash boxes added to a map bucket are actually b_hash members of struct tyhashb_tyyb," Zé assumed.

     "Just so," Wil agreed. "Each elem added is actually a tyhashb_tyyb instance allocated from a current book."

     "I see m_n is the number N of map symbols," Stu read. "But what is m_cue — a count of changes? What changes?"

     "Member m_cue helps me implement iterators," Wil explained. "It increments every time a pointer in the map changes that might foil an interator in the map."

     "Why do you use iterators?" Stu asked. "That's neither stylish in either Lisp nor Smalltalk, right?"

     "It's mainly for any helper code I write in C++," Wil shrugged. "I don't actually need iterators now. But it seems wrong not to permit the map to be examined."

     "Here you'll do your usual magic number thing: e_mlive stored in m_mlive while a maps is still alive," Zé noted.

     "Non-public method _mnew() is an internal mean of allocating new map elements," Wil explained. "The second taking yvh32 intializes boxes, too. The first only allocates."

     "I'm sure mheap() just returns the pile passed to the map constructor," Stu said. "But how is mfindB() useful?"

     "If it returns non-null," Wil replied, "mfindB() tells you a symbol address passed in as an argument was actually allocated by this symbol map, and not elsewhere."

     "That's a little subtle," Stu worried. "But I guess you just explained it clearly enough. Add more comments!"

     "Good and bad methods just check basic map aliveness," Wil dismissed. "Method mbad() logs an error."

     "Size and empty just refer to number of unique symbol members in this map," Wil glibly summarized.

     "You allocate all space used by yym symbol hashmaps using the yPBH passed to the constructor?" Zé asked.

     Wil nodded. "And the destructor frees everything allocated," Wil added. "Books and one large bucket vector."

     "Let me guess," Stu leaned in close, "those methods above are the main api when using yym, right?"

     "Sure looks like it," Zé agreed. "Add, find, and remove map elements. Is method ms2y() how you manage to associate a unique value denoting a special form for some symbols?"

     "Yes, it's only called at boot time," Wil confirmed. "Setting the alt field in symbols won't be exposed in high level languages — at least not usually."

     "Begin and end methods act a bit like an STL api, right?" Stu guessed. "I assume code resembles the iter demo."

     "Good call," Wil said. "The iter comes after map code. As usual, the p suffix means pointer — in cases like this, a synonym for iterator when it acts like a pointer to an elem."

     "Once again, a lot of this is my standard api for debug printing," said Wil. "And out and quote demos provide adpi detail."

     "This last operator allows you to append a new octet run as a symbol," Wil said. "It adds a symbol if not already present."

yym.cpp «

     "Non-inline methods for yym symbol maps appear below," Wil said. "The constructor gets space from the pile arg."

     "As you can see," Wil continued. "The vector of bucket pointers is allocated as one contiguous block cleared to all zero."

     "Why not use book instances for that?" Stu asked. "You have no api yet to alloc several contiguous books at once?"

     "I wanted many more than 16K buckets than would fit in one book," Wil said. "Several adjacent books might be better."

     "The destructor frees all space," Wil explained. "The mclear() method below frees all books containing symbols, and then the bucket vector is freed."

     "Maybe you should do some of mclear() directly in the destructor," Stu suggested, "to avoid the unnecessary memset() to zero. Does it happen often enough to matter?"

     "Not so far," Wil said.

     "Method _mnewB() above is only called when the current book in m_B has insufficient space," Wil said. "This is detected when zero is returned from vtake() on m_vfree."

     "It looks like you simply allocate a new book," Zé read, "then allocate a ytocb box at the start, whose b_v member is initialized to the book remainder. Then m_vfree points at b_v."

     "That's right," Wil agreed, "Then the desired box is allocated from m_vfree using vtake(), which is operation that failed on the last book. So mainly _mnewB() refills free space."

     "I see _mnew() uses _mnewB() if necessary to alloc one box," Zé analyzed. "First it figures total bytes needed, then afterward it constructs tyhashb_tyyb in space acquired."

     "Yes, and below I repeat the same tyhashb_tyyb constructors from the left column," Wil pointed.

     "Hey, Wil," Stu hestiated. "I've been comparing mfind() and madd() below, and madd() begins with the same code as mfind(). Do you need to refactor the common code?"

     "Maybe," Wil nodded. "But I'm not sure mfind() actually gets used much compared to madd() since the intent is usually to get an interned symbol in hand."

     "Adding another function might slow it down," Stu considered. "I guess we should profile things first?"

     "Above, madd() searches the bucket where a symbol should go," Wil described. "If missing, a new symbol is allocated, then pushed on top of that bucket."

     "And I see ms2y() uses madd() to find or add a symbol," Zé said. "But first it converts C string to yv. Then afterward it sets the 7-bit alt field of the tag. That's only for special forms?"

     "Yeah, only Lathe's boot code should call ms2y()," Wil expanded. "It knows which symbols are special forms, and using which alt values. Everyone else should leave it alone."

     "And mfind() looks just like the start of madd()," Stu repeated, "searching the expected bucket for a symbol."

     "Method mbegin() constructs an iterator instance," Wil said, "whose api resembles STL iterators in usage. Code involved appears a ways below (cf »)."

     "Debug printing code above does not show the contents of the hashmap," Wil warned. "But mout() below prints each symbols one per line, without extra markup."

     "I guess you could test mout() by loading yym with a dictionary, then dumping the words again using mout()," Zé considered. "Then sort and diff with the original dict."

     "That's exactly what I did," Wil beamed. "It's like you read my mind. Is that an easy skill to learn?"

     "You're easy to read," Zé dismissed.

     "Hmm," Stu glanced quickly. "Looks like mbad() is one of those boring error logging methods."

     The following iterator class yymp visits symbols in a specific yym symbol hashmap instance. An instance is returned by method yym::begin() (cf «).

class yymp «

     Almost no comments are offered for yymp because Wil thinks the code should be obvious after you read the iter demo, and because yymp is not currently used anywhere in other existing Lathe code. This implementation was written specifically for this page, mainly to clarify yym above further.

yymp.cpp «

     Note iterator code might contain bugs since little testing was done besides sample code shown further below.

sample «

     Output of main() above appears on stdout below; light editing breaks a few lines with a ¬ glyph, and elides a few object addresses and hashes with a … glyph.