3 ms·

I'm in the same boat as you -- here are the two best resources I found: https://mukulrathi.com/create-your-own-programming-language/intro-to-type-checking/ htt

by chubot 3y ago

I'm in the same boat as you -- here are the two best resources I found: https://mukulrathi.com/create-your-own-programming-language/intro-to-type-checking/ https://mukulrathi.com/create-your-own-programming-language/... https://jaked.org/blog/2021-09-07-Reconstructing-TypeScript-part-0 https://jaked.org/blog/2021-09-07-Reconstructing-TypeScript-... I read through the first 10 chapters of TAPL, and skimmed the rest. The first 10 chapters were good to remind myself of the framing. But as far as I can tell, all the stuff I care about is stuffed into one chapter (chapter 11 I think), and the rest isn't that relevant (type inference stuff that is not mainstream AFAIK) This is also good: https://github.com/golang/example/blob/master/gotypes/README.md https://github.com/golang/example/blob/master/gotypes/README... And yeah some of us had the same conversation on Reddit -- somebody needs to make a Crafting Interpreters for type checking :) Preferably with OOP and functional and nominal/structural systems. --- Also, it dawned on me that what makes TAPL incredibly difficult to read is that it lacks example PROGRAMS. It has the type checkers for languages, but no programs that pass and fail the type checker. You are left to kind of imagine what the language looks like from the definition of its type checker !! Look at chapter 10 for example. I mean I get that this is a math book, but there does seem to be a big hole in PL textbooks / literature. Also I was kinda shocked that the Dragon Book doesn't contain a type checker. For some reason I thought it would -- doesn't everyone say it's the authoritative compiler textbook? And IIRC there are like 10 pages on type checking out of ~500 or more.

zengid 3y ago
Thank you so much! This looks like some good morning-with-coffee reading!
ww520 3y ago
Are we looking at the same Dragon book? Chapter 6 the whole chapter is about type checking. 6.2 spells out a type checker for a sample language, admittedly in pseudo code. It might not have the same lingo as the modern type checking specification but most of the ideas are there. It talks about type systems, type expressions, type rules, constructed types like array/struct, type variables for unknown types, etc. It puts the type rules in the grammar productions. It stores the type info in the AST nodes. It uses the chained symbol tables as the type environments. It has sections on type conversion, operator/function overloading, polymorphic functions (parameterized types), and type unification. It has all the pieces and steps to build a type checker.
- chubot 3y ago
  I have the second edition, copyright 2007, and chapter 6 is "intermediate code generation". The whole chapter is definitely not about type checking -- is yours? https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811 https://www.amazon.com/Compilers-Principles-Techniques-Tools... It has 11 sub-sections, 2 of which are about type checking 6.3 - Types and Declarations, pages 370-378 6.5 - Type Checking - pages 386 - 398 So that's about 20 pages out of 993 pages. A fraction of a chapter! --- What I was referring to is the appendix "A Complete Front End", which contains a lexer and parser, but not a type checker! Doesn't sound complete to me. I guess they have a pass to create the three-address code, and type checking is only in service of that. But they don't give you the source code! --- Also weirdly, when you look at the intro chapter "The structure of a compiler", it goes 1.2.2 Syntax Analysis 1.2.3 Semantic Analysis (3 paragraphs that mentions type checking and coercions) 1.2.4 Intermediate Code Generation But when you look at the chapters, there's NO semantic analysis chapter! It goes from (4) Syntax analysis, (5) Syntax-directed translation, to (6) intermediate code generation. I think there's a missing chapter! (or two)
  - ww520 3y ago
    I have the 1st edition printed 1988. Chapter 6 is Type Checking, chapter 7 is Runtime Environments, and chapter 8 is Intermediate Code Generation. WTF. The 2nd edition is really butchered.
    - chubot 3y ago
      Wow yeah. So in the first edition pages 343 to 388 is a full chapter on type checking. It looks much more coherent. What the heck happened ...
      - adastra22 3y ago
        Standard thing: older textbooks are generally better. They tend to get dumbed down in new revisions, and modified to fit stupid standards about class syllabus.

by chubot 3y ago

zengid 3y ago

Thank you so much! This looks like some good morning-with-coffee reading!

ww520 3y ago

Are we looking at the same Dragon book? Chapter 6 the whole chapter is about type checking. 6.2 spells out a type checker for a sample language, admittedly in pseudo code. It might not have the same lingo as the modern type checking specification but most of the ideas are there. It talks about type systems, type expressions, type rules, constructed types like array/struct, type variables for unknown types, etc. It puts the type rules in the grammar productions. It stores the type info in the AST nodes. It uses the chained symbol tables as the type environments. It has sections on type conversion, operator/function overloading, polymorphic functions (parameterized types), and type unification. It has all the pieces and steps to build a type checker.

chubot 3y ago
I have the second edition, copyright 2007, and chapter 6 is "intermediate code generation". The whole chapter is definitely not about type checking -- is yours? https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811 https://www.amazon.com/Compilers-Principles-Techniques-Tools... It has 11 sub-sections, 2 of which are about type checking 6.3 - Types and Declarations, pages 370-378 6.5 - Type Checking - pages 386 - 398 So that's about 20 pages out of 993 pages. A fraction of a chapter! --- What I was referring to is the appendix "A Complete Front End", which contains a lexer and parser, but not a type checker! Doesn't sound complete to me. I guess they have a pass to create the three-address code, and type checking is only in service of that. But they don't give you the source code! --- Also weirdly, when you look at the intro chapter "The structure of a compiler", it goes 1.2.2 Syntax Analysis 1.2.3 Semantic Analysis (3 paragraphs that mentions type checking and coercions) 1.2.4 Intermediate Code Generation But when you look at the chapters, there's NO semantic analysis chapter! It goes from (4) Syntax analysis, (5) Syntax-directed translation, to (6) intermediate code generation. I think there's a missing chapter! (or two)
- ww520 3y ago
  I have the 1st edition printed 1988. Chapter 6 is Type Checking, chapter 7 is Runtime Environments, and chapter 8 is Intermediate Code Generation. WTF. The 2nd edition is really butchered.
  - chubot 3y ago
    Wow yeah. So in the first edition pages 343 to 388 is a full chapter on type checking. It looks much more coherent. What the heck happened ...
    - adastra22 3y ago
      Standard thing: older textbooks are generally better. They tend to get dumbed down in new revisions, and modified to fit stupid standards about class syllabus.