ASDL enhancements

[andychu]

• [x] Imports / use keyword
  • implementing this will allow us to get rid of meta.UserType, which is used for Id_t. It generates a custom Python import at the top of the module.
• [x] Parameterized types for map[string, bool]
  • use cases: flag specs, maybe help text, and stdlib #750
• [ ] codegen options
  • simple_int_sum for Id and integer types for IFS state machine
  • whether to generate pretty print methods -- although this might be recursive from syntax_asdl::command_t and runtime_asdl::cell
  • maybe some hints about the e_suffix or something? This part needs to be cleaned up.
  • whether it's an exception? Inheriting from Exception is required in Python. Inheriting from std::exception in C++ is apparently only needed for what(), which we don't use.
• [ ] generate methods to support values types for Oil / Tea: deep copy, equality, hash
  • another idea: generate mark methods for a mark-and-sweep GC
• [x] add unit tests for generated code in C++ and Python
  • asdl/typed_demo.py could be renamed to gen_python_test.py
• [x] Let the variants be first class types. ("open variants", "polymorphic variants", see notes in asdl.txt). This enables a bunch of schema changes (which are minor optimizations, and make the code cleaner):
  • frontend/syntax.asdl:
  • Don't need word.TokenWord -- can just be token
  • Don't need arith_expr.ArithWord -- CompoundWord
  • Don't need bool_expr.WordTest -- CompoundWord
  • shared between expr and word_part:
    • ShCommandSub and OilCommandSub ($() and eventually $[])
    • ShArrayLiteral and ArrayLiteral ( local x=(a b) and var x = @(a b) and eventually @[a b])
  • maybe: cmd_part = compound_word | simple_redir | here_doc
  • [x] does the generated code use multiple inheritance (variants inherit from multiple sum types?) No implementation inheritance?
• Do we need globally unique IDs for the variant?
  • I think this helps "homogeneous visitors", i.e. ones that don't care about types
• problem: cell.readonly and cell.exported could be represented as a bitfield
  • but that's really the physical representation vs. logical
  • I guess we could translate them to C bitfields? does that give you an int back?
• [X] make spids field explicit with attributes mechanism
  • this is a minor size optimization
• [ ] variants without args shouldn't allocate; they should be "interned" global constants with an integer tag
  • example: in trace = External(string* argv) | ForkWait | ..., the trace.ForkWait() constructor shouldn't allocate

---

edit 9/2019: A lot of this was done. Still need to refactor the schema with new "shared variant" capability.

[andychu]

Idea for spids fields:

Develop and Oil language syntax like enum { ... }. And add common fields first, e.g. like the suggestion here:

https://www.reddit.com/r/ProgrammingLanguages/comments/cvwc7n/sum_types_vs_classes/

nitpick: I don't like putting spids first in the constructor... I want them to be optional at the end. Keyword args?

Do we allow default values like function calls / constructors do?

enum op = Plus | Minus
enum expr {
  Binary(o op = op.Plus, left expr, right expr)
}

[andychu]

Another enhancement is motivated by _Dispatch in osh/cmd_exec.py. This function has two checks for variants of command

• which ones have redirects. This also relates to "inheritance" / common fields.
• which ones are "compound" for the strict_errexit check (which other shells don't have)

It would be nice to have some way of quickly checking these types / sets? A big bitfield?

But I wanted every type in the program to have a unique integer? Maybe I can just pack the command enum into the first 32 or 64?

[andychu]

A size optimization issue:

Python's dict node is represented as:

expr = ... | Dict(expr* keys, expr* values)

I guess this is the most efficient. Except that we added implicit values, which means that the expression can be missing.

Oh I guess the best thing to do is add Implicit as a variant of expr and not create a new dict_val type.

OK that solves this problem. I was wondering if

expr = ... | Dict(dict_pair* pairs)

would be better.

[andychu]

Now talking about this on a new channel #zephyr-asdl on Zulip:

https://oilshell.zulipchat.com/#narrow/stream/208950-zephyr-asdl

[andychu]

Idea: combine cell and value. cell only needs 3 bits. (And honestly -n and -x don't apply to anything except strings, though I guess -x applies to Undef too.)

• problem: you can't have implementation inheritance in value? because of the multiple inheritance problem? But that doesn't happen to apply in the value_t case. Maybe you can make a special case for it.

class value_t {
  uint16_t tag;
  uint16_t cell_flags
};  // 4 bytes

And then:

• Str can inline the length and pointer. That's really inlining mylib.
• MaybeStrArray could be a pointer and length too? Although it also needs a capacity.
• AssocArray could store length? Not sure if you need it right there.

---

• Then could we also make value_t a 16-byte value type instead of an 8-byte pointer type?
  • Would require cooperation from mycpp. It would have to generate val.s instead of val->s, etc.
  • the "inlining" of Str fields would too. But value__Str with inline cell is still valuable. So there are 2 optimizations available.