1001 Representations of Syntax with Binding (2021)

[082349872349872]

https://jesper.cx/posts/1001-syntax-representations.html

[jasperry]

I wonder if there is any research that draws insightful connections between these theoretical models of variable binding and the usual way of writing a compiler with nested symbol tables.

[Y_Y]

De Bruijn syntax is nameless

But reordering brings changes

And really it's a graph

Not just a tree

[082349872349872 → Y_Y]

  And you may find yourself binding a parameter
  And you may find yourself with a free variable
  And you may find yourself down in subtrees equal to cousin branches
  And you may find yourself with a beautiful rep, in a beautiful type
  And you may ask yourself, "Well, how did I get here?"

Lagniappe: https://www.youtube.com/watch?v=x3EDCM461jQ

[Y_Y → 082349872349872]

I like the cut of your jib

[chrisjj]

" As a compiler developer or programming language researcher, one very common question is how to represent the syntax of a programming language in order to interpret, compile, analyze, optimize, and/or transform it.

One of the first lessons you learn is to not represent syntax as the literal string of characters written by the programmer, but rather convert it to an abstract syntax tree (AST). "

Note: AST does not "represent the syntax of a programming language", but represents a program written in the language.

Perhaps worth amendment given this article seems otherwise excellent.

[evertedsphere → chrisjj]

the AST type represents the syntax of the language, each inhabitant of which type is a representation of an individual program in the language

[chrisjj → evertedsphere]

My parse stumbled at "which type".

[bckr → chrisjj]

The AST type represents the syntax of the language.

Each instance of the AST type is a representation of an individual program in the language.

[chrisjj → bckr]

> The AST type represents the syntax of the language.

Agreed, but was not mentioned by the text in question, note.

Thing != Thing's type.

[wizzwizz4 → chrisjj]

"which" is doing double duty as a relative pronoun and a determiner. I think. Parse it as "each […] of which […]", which serves the same grammatical function as "each of which" would.

Edit: A specific procedure for understanding this part of the sentence:

(1) Replace "each inhabitant of which type" with "each of which".

(2) Parse the sentence.

(3) Interpret "each" as qualified by "inhabitant" (i.e., each of them is an inhabitant), and "which" as qualified by "type" (i.e., the referent of "which" is a type).

[chrisjj → wizzwizz4]

That leaves me stuck at "type".

EDIT: #2 gives

"The AST type represents the syntax of the language, each of which is a representation of an individual program in the language."

But "each of which" what? There's no collection for it.

[wizzwizz4 → chrisjj]

#1 is a grammatical translation, and loses meaning. If you continue to step #3 before attempting to extract meaning from the sentence, it answers your question. There's only one "type" in the reference pool ("the AST type") and, like a list, set, class or tree, it is a collection. Therefore, it is this to which "which" refers.

[chrisjj → wizzwizz4]

Ah. Now it clicks - like Rubin's vase. Thanks.

[evertedsphere → chrisjj]

"… the language. each inhabitant of this type is …"

[chrisjj → evertedsphere]

OK, so:

"The AST type represents the syntax of the language. Each inhabitant of this type is a representation of an individual program in the language."

I agree.

But my

AST does not "represent the syntax of a programming language"

stands.

Thing != Thing's type.

[evertedsphere → chrisjj]

the first sentence that you quote doesn't mention the term AST or "AST type" at all, the second sentence is clearly talking about terms (i.e. inhabitants of a type)

this is meaningless nitpicking over a problem of your own invention

[chrisjj → evertedsphere]

> the first sentence that you quote doesn't mention the term

...

> "AST type" at all.

And nor does the second. "AST type" is soley your addition.

> the second sentence is clearly talking about terms (i.e. inhabitants of a type)

It is clearly about syntax, as introduced in the first sentence. And that is a feature of the language, not program. Type, not inhabitant of type.