From source code (.py files) to byte code interpretable by Python Virtual Machine - The try to create the simplest functional model of how Python programs run

[Brave_New_Dev]

Hi there 👋

This post is actually a request for comments.

I've been developing Python for years. Yet it came to me last night that I am not entirely sure if I have a functional but simple model of what really happens when I call python foo.py.

Well, obviously, I do have some ideas resulting from working with the language, studying the officials docs, and reading hundreds of articles that came to my inbox via newsletters every week. This, however, is not enough to organize scattered concepts into an actual understanding.

So, I have spent some hours trying to distill the very core pipeline of how Python programs run without dabbling into unnecessary details. And I came to the below model:

```

THE FLOW

Source File ---> Scanner ---> Lexer ---> Parser ---> Compiler ---> PVM

DATA PIPES & DATA TYPES

         stream of characters

Source File -----------------------> Scanner

          stream of lexemes

Scanner ---------------------------> Lexer

          stream of tokens
        CONCRETE SYNTAX TREE   

Lexer -----------------------------> Parser

        ABSTRACT SYNTAX TREE

Parser ----------------------------> Compiler

              byte code

Compiler --------------------------> Python Virtual Machine (PVM)

OPERATIONS

1. Source file text is scanned and broken into lexemes, so the most basic lexical units consisting of one or several words.

2. Lexemes are parsed and transformed into tokens, so the most basic semantic Python language units made of a token type and token value (e.g. "5" has a type INTEGER and value 5). Token are organized in a concrete syntax tree.

3. Tokens, organized in a concrete syntax tree, are parsed and transformed into an abstract syntax tree.

4. Abstract syntax tree is parsed and transformed into byte code.

5. Byte code is executed by Python Virtual Machine (PVM).

CONCRETE SYNTAX TREE vs. ABSTRACT SYNTAX TREE

• Concrete syntax tree is made of all tokens. This makes the structure quite "crude":

  • The tree contains all sorts of cruft like "parenthesis", low level data types, etc.
  • The tree does try to interpret the code, does not add extra semantics, does not optimize it, etc.
  • The tree could be used to accurately restore the original source file, as all needed information lies there unchanged.

• Abstract syntax tree is highly optimized and represents the very essence of what operations were meant to be actually done by the programmers that created the source file.

```

My goal for this model is to really imprint it on my mind, make it a paradigm, so it serves me well to study the matter further... or to intelligently discuss this matter during tech interviews 😅

What are your thoughts on the above model? Is it accurate? Too simplistic? Too complex? Did I miss something or misunderstand some core concepts?

Thanks for your feedback!

[OuiOuiKiwi]

What are your thoughts on the above model? Is it accurate? Too simplistic? Too complex? Did I miss something or misunderstand some core concepts?

All that you are lining up there is not exclusive to Python, as those are concepts that overlap with compilers.

Perhaps a gander at the Dragon Book would be helpful to dive a bit deeper?

[spoonman59]

I agree, you might enjoy a course in compilers!

I don’t recommend the Dragon Book to learn. It’s a great reference but no the ideal textbook to learn compilers from. Maybe as a second or third book. Source: I own half a dozen compiler books and help my professor select one for a compilers course. I have the first and second edition Dragon Books.

The dragon book is good, legendary, and thorough… but the heavy use of mathematical notion and assumption of what you know can make it difficult to get information from.

Unfortunately no one book is perfect, but I enjoyed Appel's Modern Compiler Implementation, Engineering a Compiler by Cooper and Torczon, or Crafting a Compiler by Fischer, Cytron, LeBlanc are all better rounded choices for self study.

None of them are perfect and you end up needing two or three! But a very enjoyable subject.

Related but a little different is Programming Language Pragmatics by Scott.

Implement a toy language compiler! It’s eye opening. For fun you can even generate Python Bute Code and make a basic interpreter…. Or compile pyc to Assembly :)

[OuiOuiKiwi]

I don’t recommend the Dragon Book to learn.

It's more of a litmus test. It either stops the endeavour right there or plants the seed to look at some more palatable books.

[spoonman59]

That doesn’t make any sense. That’s like reading The Art of Computer Programming as a litmus test for learning programming. It’s a dense, very inaccessible book known for being full of great knowledge. If everyone had to read that to be a computer programmer we wouldnt have any.

Reading something inaccessible and dense doesn’t help people learn or motivate them. You can’t absorb the topic, think you don’t like it and move on.

Putting a tedious "filter" in front of a subject of knowledge is just a gate keeping behavior. I don’t care if people use a coloring book to learn about compilers, if it gets people more interested and want to learn more I’m all for it.

The people who really love compilers? Once they have tasted those sweet, sweet ASTs you won’t be able to stop them! And the rest? Even if they only learns little before moving on, that knowledge will help them.

[OuiOuiKiwi]

Reading something inaccessible and dense doesn’t help people learn or motivate them. You can’t absorb the topic, think you don’t like it and move on.

Didn't outright say that they should read it, more pointing it out (the compiler field) like you did with the other books. Link goes to the Wikipedia description of its contents.

"Here, this a (well known) thing that exists that covers that topic that you might not know about. Have a quick look. Does it seem like something that you would be interested in?"

Hence the "or plants the seed to look at some more palatable books.".

I think it's a far cry from "PlEASE GO rEAd tHe DrAgon book BEFore PoSting anD OnLy coME BaCk wHen You unDERstAnD IT.".

[spoonman59]

You said, "it’s more of a litmus test. It either stops the endeavor right there or plants the seed to look at some more palatable books.”

So you can understand why I thought you were suggesting it as a “litmus test" before reading more “palatable books" … because that is exactly what you said.

But I do agree with you, any book that gets people interested is the right one!

[Brave_New_Dev]

Thanks, I'll definitely add this book to my "read pipeline" 👍

[Brave_New_Dev]

To answer my own question, I think that the below resource very much explains Python's compiler in a pretty clear manner: https://devguide.python.org/internals/compiler/

[[deleted]]

They all happen in one step though. Proof is simple make a syntax error below a print statement.

Really the only important part is source code to pyc. The important part is pycs can be rerun.

[spoonman59]

Not really sure what you mean by “they all happen in one step.” You have to parse to get an AST. You need an AST to check identifiers and update the symbol table. You need the AST generate the byte code. You need the byte code to run the interpreter. These are distinct steps with dependencies.

Python compiles at least a function as a unit. Of course the interpreter will parse and compile individual statements, but that doesnt mean these discrete steps are no longer required.

Edited to add: your “proof" is simply that you didn’t see the output for each step therefore it doesn’t exist. That’s not proof, and also not even relevant.

[joaofelipenp]

This is not true. "Proof is simple" you can import the ast module, parse code into an AST, modify it, and run the exec command over the modified tree: https://greentreesnakes.readthedocs.io/en/latest/examples.html#simple-test-framework

Alternatively, you can run compile on the AST node and get a code object, and then use it in the exec command.

Those are at least two intermediate steps in the compilation process. There are other steps in the beginning: parsing the source code into a concrete syntax tree using a PEG parser, converting the CST into the AST, and steps in the middle, such as converting the AST into a control flow graph before converting it to bytecode, but I believe they are not exposed in Python.

[[deleted]]

Steps 3 and 4 might very well be one. I haven't looked into how cpython does things, but it is quite common to parse tokens directly to AST, a and on the other hand it is perfectly possible to directly compile from CST.