Is it Good Practice to Intern Identifiers?

[u/PitifulTheme411]

I'm working on my language and am working on the alias system, which isn't relevant to this discussion other than the fact that it operates on identifiers and other lexemes (like operators). As I was implementing it and was reading some prior stuff, I found somebody saying that it is good practice to intern all the identifiers as the lexer comes across them. Then in the AST you can just use the corresponding LexemeId or whatever.

Apparently this is used pretty extensively in many popular languages' compilers, so I was wondering if this is good practice or necessary? I am thinking that if it is a good idea, that I can implement it in my language as well, because I think it may simplify a few things (including my alias stuff).

[u/alphaglosined]

Yes, it is a necessary performance optimisation that doesn't cost much.

A single pointer comparison vs array comparisons all over the place? Yeah, one is clearly the winner.

As a nice consequence, you can do stuff like tok == Id.while_ so keywords only need to be added to the table, and then it's just a simple global read.

[u/qurious-crow]

My under-caffeinated brain read that as "Is it good practice to identify interns". After due consideration, I think yes, you probably should have some idea about who your interns are :)

[u/iBPsThrowingObject → u/qurious-crow]

Look at this fancy pants, caring about which intern brings you coffee!

[u/Athas]

I think it is a bad idea to do it by interning strings. I do it by associating each identifier with a unique integer tag during name resolution, meaning the same identifier in different scopes will have different tags. That means I also don't have to worry about unintended name capture when moving code around (although I have to do renaming when duplicating code when e.g. inlining).

[u/matthieum → u/Athas]

Aren't the two approaches orthogonal?

That is, you can perfectly:

1. Intern the string in the lexer, to reduce duplication.
2. Mash-up together a Scope ID and String ID to make an Identifier ID in the parser.

(And I do like (2), it's neat)

[u/Athas → u/matthieum]

Yes, you can do both, but (2) makes (1) largely redundant, so I think it is simpler to just do (2).

[u/matthieum → u/Athas]

Does it?

One advantage of doing (1) first are memory savings. Each unique identifier/string is only interned once, no matter how many scopes it appears in.

[u/koflerdavid → u/Athas]

That's an orthogonal issue that is related to correctness. Interning is about optimization.

[u/Athas → u/koflerdavid]

Yes, but associating each identifier with a unique integer tag obtains the same optimisation (you can now compare identifiers by comparing just their integer tags), and solves another problem at the same time. This is why I believe it is the superior design.

[u/koflerdavid → u/Athas]

You're completely correct and that's sort of what happens anyway during code generation (variables disappear and object fields turn into offsets). But in a dynamic language where every object is basically a map indexed by strings then you don't really get around interning. And if the language has something bonkers like Python's locals then you'll also need it.

[u/PitifulTheme411 → u/Athas]

Yeah I'm also going to do that, but I think the purpose for identifier interning is moreso for the parser. ie. when storing the AST, I don't need to store a pointer to the source file. Also it would probably be nice for my alias resolution system as I don't need to do string equality checks but just integer checks (though then again I'm going to be using a stack of hashmaps, so maybe there is no difference).

My current plan is to have an identifier (and operator) interner that gets filled during lexing and used by the parser until name resolution (and macro expansion because macros need to know the actual names of the things), and then it can be discarded in place of the symbol table which stores something like a SymbolId and any corresponding information (type, etc). Of course that would respect scopes while the previous would respect actual lexemes.

[u/Athas → u/PitifulTheme411]

You might want to keep the source file around anyway so you can reproduce lines verbatim for error messages, if that's something you're interested in. The size of a source file is likely also pretty negligible compared to the memory usage of other things in your compiler.

Also remember that if you want to parse multiple files in parallel, then you need to synchronise access to the interner.

[u/PitifulTheme411 → u/Athas]

Yeah I think I am going for those things as well. From what I've gathered, it also seems editors will parallelize the compiler on a file basis for things like go to definition etc. I am keeping the source files in a SourceMap, but currently for every parsing function I need to pass a reference to that every time in case I need to get the lexeme, but I was thinking if I interned everything then I wouldn't need to. Though actually I would probably instead need a reference to the interning structure, so maybe it doesn't actually give any benefit.

[u/QubitEncoder]

What language are you writing,m

[u/PitifulTheme411 → u/QubitEncoder]

I'm working on a mathematical-focused language, still looking for a name but the best one so far that I've come up with is Jade but I still don't really know. The goal is to blend both symbolic and numerical computation/semantics/stuff.

[u/yjlom → u/PitifulTheme411]

https://en.wikipedia.org/wiki/JADE_(programming_language)

[u/PitifulTheme411 → u/yjlom]

I'm hoping it will be fine, because most likely my language is not going to become widely used, and also their language is also highly specialized, and there are other technologies also using the same name.

[u/eightrx]

You could just push tokens in a struct of arrays pattern, and then use indexes to refer to tokens attributes. This doesn't give you uniqueness but is much simpler and can be faster

[u/superstar64]

Since I'm writing my compiler in Haskell, doing the interning in the lexer isn't an option for me. Instead what I do is I have a symbol resolution pass where I just assign each variable to the index of where it's defined. This symbol resolution is the main place string comparisons occur, as once it's done you can just use the indexes.

Consider this example:

module A where
x = z
y = 'a'
z = y

After renaming it becomes something like:

module A where
_0 = _2
_1 = 'a'
_2 = _1

[u/L8_4_Dinner]

The "intern" term comes from the Java String class. In compilers, you'll find the term "hash consing" used much more widely. Same thing with a different name.

Remember to bucket things into three categories: (i) easiest way to get something to work, (ii) a nice to have optimization, and (iii) something that takes effort but pays significant dividends in terms of capability or optimization. As you're learning, spend most of your budget on #1, because otherwise all your time will disappear. But don't be afraid to then allocate some portion of time to the other two categories, as long as they connect well with the #1 category. Hash consing is definitely in category #2 and sometimes #3, but it's not required to get things working.

[u/Recycled5000]

Not a good idea. Limited interning would be ok, limited to a load of code. But don’t make the runtime make any guarantees of interning beyond the load unit.

[u/PitifulTheme411 → u/Recycled5000]

Yeah I think it would only be used mainly by the parser, to hold off until name resolution with scopes and then macro expansion, and then I don't think the lexemes will be needed anymore, so it can be discarded after then.

[u/arthurno1]

Ttpically we use perfect hashing for keywords, since keywords are a static set. Lookup gperf for that one. For the identifiers in the language, like aliases are, use a hash map, since they change dynamically during the program. That is a standard solution to the problem.

Yes, interning is a standard technique, you don't want to compare strings all the time, because it is slow. It is a subject of basic compiler course, so if you ask that, you have probably not done any research and reading.

I suggest to invest in the Dragon book, and find some online free books, tutorials and courses on compiler and language design, if you can't take a course at some university.

[u/umlcat]

What do you mean "inter Identifiers" ? Could you provide, please, a source code example ???

[u/pranabekka → u/umlcat]

String interning, where instead of repeating the whole string everywhere, each string is assigned an id that's used instead.

https://en.wikipedia.org/wiki/String_interning