4 ms·

1001 Representations of Syntax with Binding (2021)

Y_Y 2y ago
De Bruijn syntax is nameless But reordering brings changes And really it's a graph Not just a tree
- 082349872349872 2y ago
  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 https://www.youtube.com/watch?v=x3EDCM461jQ
  - spuriouserror31 2y ago
    [flagged]
  - Y_Y 2y ago
    I like the cut of your jib
- deleted 2y ago
  [deleted]
chrisjj 2y ago
" 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 2y ago
  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 2y ago
    My parse stumbled at "which type".
    - bckr 2y ago
      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 2y ago
        > 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 2y ago
      "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 2y ago
        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.
jasperry 2y ago
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 2y ago

De Bruijn syntax is nameless But reordering brings changes And really it's a graph Not just a tree

082349872349872 2y ago
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 https://www.youtube.com/watch?v=x3EDCM461jQ
- spuriouserror31 2y ago
  [flagged]
- Y_Y 2y ago
  I like the cut of your jib
deleted 2y ago
[deleted]

" 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 2y ago
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 2y ago
  My parse stumbled at "which type".
  - bckr 2y ago
    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 2y ago
      > 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 2y ago
    "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 2y ago
      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.

jasperry 2y ago

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.