Exposing Symbols in the API

[SamirDroubi]

Currently, cursors that access variables implement a name(self) -> str function which return the name attribute of the Sym node. However, Syms don't just represent a string name, it really represents a pair of (name, id). This means that there is currently no way in user-code to (unambiguously) check if two symbols are the same. We need to expose the id information somehow to make sure we can ask questions about symbol equalities, build environments in a way that is unambiguous.

What we will want out of this API:

1. Be able to do comparisons on two symbols.
2. Be able to build environments out of symbols: it needs to be hashable.
3. Be able to introspect it is components: the name and the id

There are a few design choices here:

1. Should we just let the cursors return a free object (Symbol) or make it a navigation to another cursor SymbolCursor.
2. How can we support the functionalities above with either of those APIs.

Symbol:

class Symbol:
     _impl: Sym
     
     # wrappers around all the functions Sym implements (except for copy()): https://github.com/exo-lang/exo/blob/59ed05f2aa6ec5f76db208889a7539543adedc6f/src/exo/prelude.py#L21

SymbolCursor:
It is a bit confusing to directly implement things like __hash__ or __eq__ on a cursor when we haven't implemented for any other cursor. The meaning of equality is also ambiguous between location (cursor path) and the node. One option is to have the cursor return the Symbol object above.

class SymbolCursor:
     _impl: Sym
     
     def get_symbol(self) -> Symbol

The alternative:

class SymbolCursor:
     _impl: Sym
     
     def name() -> str
     def id() -> int
     def get_pair() -> Tuple(str, int)
     # This tuple can be used for comparison and be hashable. 

I don't think there is really a reason to be able to point to a Symbol. So, I think the free object design is what makes more sense.

[SamirDroubi]

I have originally said said that there is not much point in being able to point to a Symbol. But it might make sense to support it that way just for consistency with the rest of the API, and have that cursor return a Symbol object just as described above.

[gilbo]

This should be part of a metaprogramming API a la Terra.

1. A user-level Symbol class that wraps internal symbols is a good idea; MAYBE it's ok/better to just return symbols directly, though we should be careful about that. I suspect we don't want symbol cursors.
2. Users should never inspect the internal symbol ID. They should be able to work with them as opaque objects the same way we do inside the compiler. IDs should possibly be displayed for debugging purposes.
3. It may be possible to design this feature without full support for code quotes, but it should be designed to support that future use.

Thus, it should be possible to somehow do something like

new_sym = ExoSym() # create a new symbol, don't care what name

@proc
def foo(...):
  [[new_sym]] : f32
  new_sym = 0.0
  ...

Observe the [[...]] syntax. Is that grammatical? Can we do [...] more simply? Is this a generalizable approach to the syntax? Note, we can't merely write new_sym : f32, because then we can't distinguish between two possible intents. (intent 1) Capture the new_sym symbol and use it as this variable name in the generated code. (intent 2) create a new variable name/symbol new_sym that shadows all prior uses of the name new_sym, whether from the local Exo scope or from the enclosing Python scope.

This is a problem in Terra which is solved via the var [name] = ... syntax (intent 1) as opposed to the var name = ... syntax (intent 2).

If we support some kind of "unquote" in Exo code, then whatever syntax we choose for capturing symbols at binding sites should be consistent in style.

Again, if the issues I'm raising don't make sense, please please read the Terra tutorial. We're going to have issues having these design discussions if we don't all have at least some baseline understanding of quoting, unquoting and quasiquoting features for metaprogramming.

[SamirDroubi]

1. I mostly battled with this decision for the following reasons:
   • Let's say I wanted to get the symbol dependencies of some node, then I would write something like the following:

   # Get all the cursors in the subtree of the desired cursor -> Should this operation return the Symbols? But is it confusing to return a Symbol here when it is not a cursor?
   # If the answer is yes, filter for the Symbol type. 
   # If the answer is no, filter for the types that can have a Symbol as a child
   # Return the symbols.
   

   Which one really leads to clean code?
   • Another example is where I want to get all the accesses to some buffer given a symbol. If I return the Symbols, then I cannot really navigate back to the parent when it is not a cursor which is something I might want to do. So, I would rather in this case return the parents of the symbols for convenience. However, when I ask an operation to give me all the accesses to a symbol, I would probably expect a pointer to the symbol itself not its parent. Question is which is more intuitive?
   • Let's say we do go with a cursor to a Symbol, I would still need an object that represents a Symbol so I can check equality of symbols and build environments of symbols. Is it confusing that a SymbolCursor returns a Symbol which I can then introspect while all the other cursors are introspected directly?
2. I agree.
3. I understand your point about quoting. Yes, I will read the Terra tutorial because I don't know much about unquoting and quasiquoting.

[gilbo]

Given your specific issues in 1, if you traverse the entire tree, you need some kind of function that will extract the relevant symbols from each primitive cursor (which is not to a symbol) which requires knowing where the symbols are and how to request them. You almost certainly do not want a "symbol cursor" because if you ask for accesses to a symbol, you need to know (a) what kind of access and (b) any indices used to access a buffer, etc. In the case of globals, there will be no indices. In the case of index variables, it will be a totally different situation. So there is also the question of what "kind" of symbols (i.e. variable names) you want to extract.

---

It's worth considering what kinds of "inspection" features should be built in to the API vs. implemented on top of it. It may be the case that some of these "get definition site for variable name" or "get all free variables" (not the same as all symbols in the subtree!) or such concepts should be primitive because the implementation can potentially memoize or otherwise accelerate these primitives such that much less user code needs to waste time traversing whole ASTs.

Basically, most users should not have to write code that looks like a compiler pass to inspect commonly desired information from a proc.

Maybe we need to zoom out and get a better picture of the inspection API? My impression is that you've managed to build a lot of powerful inspection tooling on top of cursors, but that most of it is not that concise or high level. We should look for where we can potentially get massive simplifications, not just small tweaks.

Maybe it's worth thinking about query languages like JQuery or SQL. What does a mini language for querying code look like?

[SamirDroubi]

I agree with you that I was looking at why a SymbolCursor is useful from a point-of-view which makes it useful, but there are many other issues that it wouldn't solve.

I think you raise an interesting question of what should an inspection API contain. It is a question I have been thinking about mostly driven by code deduplication between the compiler and the stdlib. The issue is that the sorts of question you might ask about the a program within the compiler and outside the compiler are the same. So, yeah does it make sense to have some sorts of inspection API to achieve deduplication and as you mentioned amortize the cost of some computation.

I have been moving the things I have written more and more towards being much higher-level. However, yes that sometimes comes at the cost of extra/redundant compute. I haven't yet observed a ridiculous increase in compile time due to that, but I think it is an important concern to keep in mind.

[SamirDroubi]

I think this a summary of what the design then looks like (minus any considerations for Terra-like metaprogramming):
Cursor that previously implemented a function: def name(self) -> str would instead return an object of the following type:

class Symbol:
       _impl: Sym
       # Explicitly checks for the internal Sym type to not allow users to construct arbitrary symbols (for now since 
       # since they cannot do anything with it).
       # Similar to what's done here: https://github.com/exo-lang/exo/blob/main/src/exo/API_cursors.py#L89
      def __init__(self, nm):
      def __str__(self): # The string name
      def __repr__(self): # The string name + id for debugging
      def __hash__(self):
      def __lt__(self, rhs):
      def __eq__(self, rhs):
      def __ne__(self, rhs):
      def name(self): # same as __str__

I think there is a question of what should the function that returns a Symbol from a cursor be called. Should still be called name()? Should it be changed to symbol() since the Symbol itself will have a name() function? Within the compiler we use name interchangeably for the attribute that represents a Sym object in another AST node and for the string name within Sym object itself. But maybe that's confusing at the API?

[gilbo]

The class sketch looks fine. I recommend not punting on the metaprogramming part here. It’s a good idea to start taking the meta programming features seriously, and this is both (a) a crucial piece of that puzzle and (b) a possible candidate for a partial step towards the broader feature that doesn’t require implementing everything all at once. — Gilbert

…

On Jan 20, 2024, at 7:38 PM, Samir Droubi ***@***.***> wrote: I think this a summary of what the design then looks like (minus any considerations for Terra-like metaprogramming): Cursor that previously implemented a function: def name(self) -> str would instead return an object of the following type: class Symbol: _impl: Sym # Explicitly checks for the internal Sym type to not allow users to construct arbitrary symbols (for now since # since they cannot do anything with it). # Similar to what's done here: https://github.com/exo-lang/exo/blob/main/src/exo/API_cursors.py#L89 def __init__(self, nm): def __str__(self): # The string name def __repr__(self): # The string name + id for debugging def __hash__(self): def __lt__(self, rhs): def __eq__(self, rhs): def __ne__(self, rhs): def name(self): # same as __str__ I think there is a question of what should the function that returns a Symbol from a cursor be called. Should still be called name()? Should it be changed to symbol() since the Symbol itself will have a name() function? Within the compiler we use name interchangeably for the attribute that represents a Sym object in another AST node and for the string name within Sym object itself. But maybe that's confusing at the API? — Reply to this email directly, view it on GitHub <#549 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAKZHLFQY3DQNIGZPPFSOATYPSESFAVCNFSM6AAAAABBR3IZEKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTSMBSGQ4TCMJUHE>. You are receiving this because you commented.