SilvIR

[remexre]

Prose; where it differs from the Haskell, it's correct (there are a few recent tweaks I need to propagate back): https://git.sr.ht/~remexre/exps/tree/3c321e804f777f54d079f6002ba74c2964eddab8/item/silvir/README.md

---

Reposting from Slack, since I think we'll want to keep this around:

I think I've got a ready-for-review draft of SilvIR ready:

• Definition and Interpreter: https://git.sr.ht/~remexre/exps/tree/5c150286cdfad4965d49f3d2c858a73622ef9175/item/silvir/Language/SilvIR.hs
• Haddock for above: https://cdn.remexre.xyz/docs/silvir/Language-SilvIR.html
• Helpers for not having to deal with ANF: https://git.sr.ht/~remexre/exps/tree/5c150286cdfad4965d49f3d2c858a73622ef9175/item/silvir/Language/SilvIR/Helpers.hs
• Haddock for above: https://cdn.remexre.xyz/docs/silvir/Language-SilvIR-Helpers.html
• Big passing example/test case: https://git.sr.ht/~remexre/exps/tree/5c150286cdfad4965d49f3d2c858a73622ef9175/item/silvir/Language/SilvIR/Tests/STLC.hs
• Equivalent Silver to above: https://git.sr.ht/~remexre/exps/tree/5c150286cdfad4965d49f3d2c858a73622ef9175/item/silvir/example-grammars/stlc

Known issues:

• autocopy attributes: I'll probably either have the frontend generate + call some internal:forEachChild::(Self ::= (Self ::= Self)) attribute, or have special builtins for autocopy
• foreign items: Only tricky thing here is defining foreign functions that act like AExprs (e.g. the treemap functions) vs those that act like Exprs (e.g. genInt())
• lazy children: I designed this around children-are-strict before realizing that this doesn't seem to be the case in the Java translation? It seems hard/bad to decorate through a thunk, though, and if you rely on productions being lazy in their children, you're asking for trouble...
• lists: I need to implement lists the way Silver does, which implies properly grokking them... (Though, I think AppendCell is just an implementation detail, so maybe this is trivial, iunno.)
• terminals: I think these are trivial to add too, I just... haven't
• wtf haskell: I'll probably try and port it to Coq once it's finalized :) It'd be pretty neat to prove some optimizations on it correct, especially strictness analysis. The implementation Silver uses would also be in Silver, of course. (Though, I'd definitely want to keep the ability to dump it in an easily-parseable format; either JSON, S-expressions, or something else I can easily read into C++, Java, Haskell, OCaml, and Rust.)

I'm especially looking for "what Silver features seem hard to translate to this IR."

[remexre]

oh, A'StrCat, A'StrEq, V'Int and V'String will probably become foreign items; though on the other hand, they're sorta necessary to write test cases, so maybe they should stay? Or just, there's some specified set of foreign items every backend from SilvIR has to support, including "some integer type and these operations," and "some string type and these operations."

[remexre]

I forgot about having children of type Decorated Foo; updated for that:

• https://git.sr.ht/~remexre/exps/tree/0e65cf6ade4e72ee339201c5117a816dc0cb1902/item/silvir
• https://cdn.remexre.xyz/docs/silvir/0e65cf6ade4e72ee339201c5117a816dc0cb1902/Language-SilvIR.html

[remexre]

Was asked to clarify; primary goals (which I consider "on my TODO list") are:

• To make experimenting with different translations easier (eg. "can we do aggressive stack allocation a la Go to reduce GC pressure?")
• To implement "linking," which should drastically reduce startup time
• To make writing relatively low-level optimization passes (eg. and esp. strictness analysis) easier

Secondary goals (which I think are neat, but don't consider them to be on my TODO list) are:

• To write a cleaner Java translation that assumes "linking," to get AOTed binaries with SubstrateVM, which should again reduce startup time
• To write a Truffle backend, to get nicer debugging, etc., and maybe better runtime performance
• To write a JavaScript or WASM backend, as a step towards being able to do a non-cursed "try Silver in the browser" thing
• To have a stronger foundation for talking about the correctness of Silver: SilvIR is intended to be small and simple enough to write its semantics down in Coq, Lean, etc. without too much work

---

Note: when I say "linking," it might be more appropriate to say "whole-program compilation"... Though, everything but final SilvIR-to-X translation happens separately, and I intend "linking" to be optional on most backends, so maybe it's not that much of a misuse of terminology?

[RandomActsOfGrammar]

I read the description of SilvIR. I have some questions specific to sections, as well as overall comments.

Laziness and Strictness

• As an IR, which isn't written directly, why does it need to have thunks created implicitly? Shouldn't they just be inserted as necessary in compilation to the IR?
• The document mentions changing the call semantics by using a zero-argument function instead of a thunk. Wouldn't this be easier to do if there were no implicit thunks, since we could simply choose not to insert the thunk?

Decoration

• The document mentions applying functions corresponding to a tree's tag. What tag? Where does the tag come from?
• Why are functions used for computing attribute values? What do these functions do? As an IR for attribute grammars, how is a production turned into such a function?

Overall

This document doesn't provide enough detail to describe the IR. With the missing details, I have no sense of whether compiling Silver to SilvIR is reasonable. Some topics which ought to be addressed in a document with more details, in addition to the above points:

• How do inherited attributes and synthesized attributes get translated into the IR? The document says there is no distinction between the two types of attributes, but it offers no explanation of how there can be no distinction between them.
• There needs to be a discussion of forwarding, outside of the context of pattern matching. How is the forward decorated, being a special attribute, when it is treated the same as other, undecorable attributes?
• How is the overall grammar represented?

As written, this document sounds as if it is trying to describe a translation of an attribute grammar to a functional language, rather than an IR intended for attribute grammars. I need to see a document describing SilvIR in more detail before I am able to decide whether it is a good idea or offer suggestions on improving it.

[remexre]

As an IR, which isn't written directly, why does it need to have thunks created implicitly? Shouldn't they just be inserted as necessary in compilation to the IR?

They're only implicit when creating a letrec or a global variable; I suppose in both cases, instead of those implicitly creating thunks, they could require that the expression being bound is either an A'Thunk or A'Lam?
My expectation is that Silver will be creating almost all thunks explicitly, those two are just the cases where call-by-value doesn't make 100% sense.

The document mentions changing the call semantics by using a zero-argument function instead of a thunk. Wouldn't this be easier to do if there were no implicit thunks, since we could simply choose not to insert the thunk?

Yeah, I expect so. Globals and locals are already translated differently, but for letrecs, that would make sense.

The document mentions applying functions corresponding to a tree's tag. What tag? Where does the tag come from?

The tag is the ProdName value (a namespaced name) provided to A'Cons.

Why are functions used for computing attribute values? What do these functions do? As an IR for attribute grammars, how is a production turned into such a function?

A single abstract, aspect, or concrete production body turns into one function.
A propagate statement or declaration also creates these functions.
(In the Haskell reference implementation, I straight-up call these functions "productions" because of this.)

Functions are used instead of a dedicated construct to simplify the semantics of the IR.

This document doesn't provide enough detail to describe the IR.

I think I might've not been clear about this (I probably should've put it in the document itself...); this is intended as a companion to the definitions here.

How do inherited attributes and synthesized attributes get translated into the IR? The document says there is no distinction between the two types of attributes, but it offers no explanation of how there can be no distinction between them.

I suppose the difference is who sets them; inherited attributes are set after synthesized attributes are (recalling that synthesized attributes that are not known to have an empty flowtype must be thunked, so this works out fine), by the productions of their parent or by the E'Decorate that started decoration.

At access-time (and in the in-memory representation of a tree), there isn't a distinction, though.

The InhId example (based on this Silver) is a minimal example of this.

For a larger example, see the STLC example (which is a translation of this Silver grammar, but with unparse as a strict attribute, to show what that would look like).

There needs to be a discussion of forwarding, outside of the context of pattern matching. How is the forward decorated, being a special attribute, when it is treated the same as other, undecorable attributes?

Attributes aren't undecorable in SilvIR; I don't think the forward is any more special than production attributes in this regard.

grammar example;

inherited attribute i::Int;
synthesized attribute j::Int;
nonterminal Foo with i, j;

abstract production bar
top::Foo ::= n::Int
{ top.j = n + top.i; }

abstract production baz
top::Foo ::=
{ forwards to if top.i < 3 then bar(3) else bar(i); }

might translate to something like

; strawman syntax, since the haskell trees are way grosser
; also eliding ANF bits, since they're "obvious" but add noise to this example

(default-production 'example:Foo 0 (top)
  (set-attr (var top) 'example:j
            (get-attr 'example:j (force :writeback (get-attr 'silver:core:forward (var top))))
    (var top)))

(production 'example:Foo 'example:bar 10 (top)
  ; adding builtin for this example; those aren't defined yet, idk how foreign
  ; items should work and builtins seem related
  (set-attr (var top) 'example:j (builtin '+ (get-child 0 (var top))
                                             (force :writeback (get-attr 'example:i (var top))))
    (var top)))

(production 'example:Foo 'example:baz 10 (top)
  (set-attr (var top) 'silver:core:forward
            (thunk (if (builtin '< (force :writeback (get-attr 'example:i (var top)))
                                   (lit 3))
                       (decorate (cons 'example:bar (lit 3)))
                       (decorate (cons 'example:bar (force :writeback (get-attr 'example:i (var top)))))))
    (var top)))

(production 'example:Foo 'example:baz 20 (top)
  (set-attr (var top) 'silver:core:forward
            (thunk (set-attr
                     (force :writeback (get-attr 'silver:core:forward (var top)))
                     'example:i
                     (get-attr 'silver:core:i (var top))
                     (force :writeback (get-attr 'silver:core:forward (var top)))))
    (var top)))

Note that the latter example:baz production is perfectly sound, because of the aforementioned "synthesized attributes that are not known to have an empty flowtype must be thunked" restriction.

How is the overall grammar represented?

As a set (a Seq in the Haskell reference implementation, but order shouldn't matter) of TopLevelItems.

As written, this document sounds as if it is trying to describe a translation of an attribute grammar to a functional language, rather than an IR intended for attribute grammars.

Well, it's intended to make as many things as explicit as possible, which for lots of the AG part, means breaking them into primitives.

[remexre]

The worked-through translation and evaluation is here.