Comment by chubot | Hacker News Reader

Comment by chubot | Hacker News Reader

Parent Full thread

FWIW I find this is especially important for compilers and interpreters.

It's not an exaggeration to say that such programs are basically big data structures, full of compromises to accomodate the algorithms you need to run on them.

For example LLVM IR is just a big data structure. Lattner has been saying for awhile that a major design mistake in Clang is not to have its own IR (in the talks on the new MLIR project).

SSA is data structure with some invariants that make a bunch of algorithms easier to write (and I think it improves their computational complexity over naive algorithms in several cases)

----

In Oil I used a DSL to describe an elaborate data structure that describes all of shell:

What is Zephyr ASDL? http://www.oilshell.org/blog/2016/12/11.html

https://www.oilshell.org/release/0.8.pre9/source-code.wwz/fr...

I added some nice properties that algebraic data types in some language don't have, e.g. variants are "first class" unlike in Rust.

Related: I noticed recently that Rust IDE support has a related DSL for its data structure representation: https://internals.rust-lang.org/t/announcement-simple-produc...

> FWIW I find this is especially important for compilers and interpreters.

Totally. I'm building a relational language and start to get very obvious why RDBMS not fit certain purity ideals of the relational model (like all relations are sets, not bags).

I'm stuck in deciding which structures provide by default. Dancing between flat vectors or ndarrays or split between flat vectors (columns), and HashMaps/BTree with n-values (this is my intuition now).

--- > I added some nice properties that algebraic data types in some language don't have, e.g. variants are "first class" unlike in Rust.

This sound cool, where I can learn about this?

FWIW I found this post thought provoking in thinking about data models of languages.

https://news.ycombinator.com/item?id=13293290

---

About first class variants:

https://lobste.rs/s/77nu3d/oil_s_parser_is_160x_200x_faster_...

https://github.com/rust-lang/rfcs/pull/2593

Another way I think of this is "types vs. tags": https://oilshell.zulipchat.com/#narrow/stream/208950-zephyr-... (Zulip, requires login)

Basically variant can types stand alone, and have a unique tag. Tags are discriminated at RUNTIME with "pattern matching".

But a variant can belong to multiple sum types, and that's checked statically. This is modeled with multiple inheritance in OOP, but there's no implementation inheritance. Related: https://pling.jondgoodwin.com/post/when-sum-types-inherit/

So basically in the ASDL and C++ and Python type system I can model:

- a Token type is a leaf in an arithmetic expression

- a Token type is a leaf in an word expression

But it's not a leaf in say what goes in a[i], or dozens of other sum types. Shell is a big composition of sublanguages, so this is very useful and natural. Another construct that appears in multiple places is ${x}.

So having these invariants modeled by the type system is very useful, and actually C++ and MyPy are surprisingly more expressive than Rust! (due to multiple inheritance)

Search for %Token here, the syntax I made up for including a first class variant into a sum type:

https://www.oilshell.org/release/0.8.pre9/source-code.wwz/fr...

There is a name for the type, and a name for the tag (and multiple names for the same integer tag). Tags (dynamic) and types (static) are decoupled.

Reply on news.ycombinator.com