---
# System prepended metadata

title: 'Proposal: Compiler overview'
tags: [juvix-project, Juvix]

---

# Proposal: Compiler overview

###### tags: `Juvix` `juvix-project`

## Objectives

- Reflect on the state of the compiler
- Understand it in a high-level, intuitive way, as well as every step involved
- Identify desirable but not-yet implemented passes
- Identify necessary vs optional passes
- Identify potential blocking parts or bottlenecks
- Modularise Core


## Compiler structure

![](https://hackmd.io/_uploads/SysYHiHwF.png)


Link to [diagram](https://q.uiver.app/?q=WzAsNDEsWzAsNSwiXFx0ZXh0e0p1dml4IGZpbGV9Il0sWzIsNCwiXFx0ZXh0e1NlcmlhbGlzZWQgKEFTVCl9Il0sWzYsNCwiXFx0ZXh0e0Rlc3VnYXJlZH0iXSxbMyw3LCJcXHRleHR7Q29yZX0iXSxbNCw5LCJcXHRleHR7Q29yZX0iXSxbMiw5LCJcXHRleHR7RXZhbH0iXSxbMSwxMSwiXFx0ZXh0e0xMVk19Il0sWzIsMTEsIlxcdGV4dHtNaWNoZWxzb259Il0sWzMsMTEsIlxcdGV4dHtQbG9ua30iXSxbMiwzLCJcXGJ1bGxldCJdLFsyLDUsIlxcdGV4dHtBU1R9Il0sWzIsMiwiXFxidWxsZXQiXSxbMiwxLCJcXGJ1bGxldCJdLFsyLDAsIlxcYnVsbGV0Il0sWzUsMCwiXFxidWxsZXQiXSxbNiwwLCJcXGJ1bGxldCJdLFs2LDEsIlxcYnVsbGV0Il0sWzYsMiwiXFxidWxsZXQiXSxbMTEsNCwiXFx0ZXh0e0NvbnRleHRpZmllZH0iXSxbNyw0LCJcXHRleHR7RGVzdWdhcmVkfSJdLFs3LDMsIlxcYnVsbGV0Il0sWzcsMSwiXFxidWxsZXQiXSxbMTEsMSwiXFxidWxsZXQiXSxbMTEsNSwiSFIiXSxbMTEsNiwiXFxidWxsZXQiXSxbMTEsNywiXFxidWxsZXQiXSxbOSw3LCJcXGJ1bGxldCJdLFs2LDcsIlxcYnVsbGV0Il0sWzgsMiwiXFxidWxsZXQiXSxbNiwzLCJcXGJ1bGxldCJdLFs5LDEyLCJcXGJ1bGxldCJdLFsxMCwxMiwiXFxidWxsZXQiXSxbOSwxMywiXFxidWxsZXQiXSxbMTAsMTMsIlxcYnVsbGV0Il0sWzExLDEyLCJcXGJ1bGxldCJdLFsxMiwxMiwiXFxidWxsZXQiXSxbMTEsMTMsIlxcYnVsbGV0Il0sWzEyLDEzLCJcXGJ1bGxldCJdLFsxMSwxNCwiXFxidWxsZXQiXSxbMTIsMTQsIlxcYnVsbGV0Il0sWzExLDMsIlxcYnVsbGV0Il0sWzEsMiwiZGVzdWdhciIsMCx7ImNvbG91ciI6WzI0MCw2MCw2MF19LFsyNDAsNjAsNjAsMV1dLFsxLDksIm1vZHVsZSBcXHRvIGZ1biIsMCx7ImNvbG91ciI6WzAsMCw1MF19LFswLDAsNTAsMV1dLFsxMCwxLCJzZXJpYWxpc2UiLDAseyJjb2xvdXIiOlsyNDAsNjAsNjBdfSxbMjQwLDYwLDYwLDFdXSxbMCwxMCwicGFyc2UiLDAseyJjb2xvdXIiOlsyNDAsNjAsNjBdfSxbMjQwLDYwLDYwLDFdXSxbOSwxMSwibGV0XFx0ZXh0ey19bW9kIFxcdG8gbGV0IiwwLHsiY29sb3VyIjpbMCwwLDUwXX0sWzAsMCw1MCwxXV0sWzEyLDEzLCJpZiBcXHJpZ2h0YXJyb3cgY2FzZSIsMCx7ImNvbG91ciI6WzAsMCw1MF19LFswLDAsNTAsMV1dLFsxMywxNCwibGV0IFxcdG8gbGV0XFx0ZXh0ey19bWF0Y2giLDAseyJjb2xvdXIiOlswLDAsNTBdfSxbMCwwLDUwLDFdXSxbMTUsMTYsImRlZlxcdGV4dHstfXNpZyArIGRlZnVuXFx0ZXh0ey19bWF0Y2ggXFx0byBkZXNpZ1xcdGV4dHstfW1hdGNoICAiLDIseyJjb2xvdXIiOlswLDAsNTBdfSxbMCwwLDUwLDFdXSxbMTYsMTcsInJlY29yZCBcXHRvIHJlY29yZFxcdGV4dHstfW5vXFx0ZXh0ey19cHVuIiwyLHsiY29sb3VyIjpbMCwwLDUwXX0sWzAsMCw1MCwxXV0sWzE0LDE1LCJkZWZ1biAgXFx0byBkZWZ1blxcdGV4dHstfW1hdGNoIiwyLHsiY29sb3VyIjpbMCwwLDUwXX0sWzAsMCw1MCwxXV0sWzExLDEyLCJjb25kIFxcdG8gaWYiLDAseyJjb2xvdXIiOlswLDAsNTBdfSxbMCwwLDUwLDFdXSxbMiwxOSwiIiwyLHsic3R5bGUiOnsiYm9keSI6eyJuYW1lIjoiZGFzaGVkIn0sImhlYWQiOnsibmFtZSI6Im5vbmUifX19XSxbMTksMjAsInJlc29sdmVcXCBvcGVuIiwyLHsiY29sb3VyIjpbMCwwLDUwXX0sWzAsMCw1MCwxXV0sWzIwLDIxLCJyZXNvbHZlTW9kdWxlIiwwLHsiY29sb3VyIjpbMCw2MCw2MF19LFswLDYwLDYwLDFdXSxbMjEsMjIsInJlY29yZERlY2xhcmF0aW9uIiwwLHsiY29sb3VyIjpbMCw2MCw2MF19LFswLDYwLDYwLDFdXSxbMTksMTgsImNvbnRleHRpZnkiLDAseyJjb2xvdXIiOlsyNDAsNjAsNjBdfSxbMjQwLDYwLDYwLDFdXSxbMTgsMjMsImRlc2VyaWFsaXNlIiwwLHsiY29sb3VyIjpbMjQwLDYwLDYwXX0sWzI0MCw2MCw2MCwxXV0sWzIzLDMsImVsYWJvcmF0aW9uIiwxLHsiY29sb3VyIjpbMjQwLDYwLDYwXX0sWzI0MCw2MCw2MCwxXV0sWzIzLDI0LCJcXHRleHRpdHtzY29wZSBjaGVja2VyfSIsMCx7ImNvbG91ciI6WzAsMCw1MF19LFswLDAsNTAsMV1dLFsyNCwyNSwiXFx0ZXh0aXR7dHlwZSBjaGVja2VyfSIsMCx7ImNvbG91ciI6WzAsMCw1MF19LFswLDAsNTAsMV1dLFsyNSwyNiwiXFx0ZXh0aXR7dW5pZmllcn0iLDAseyJjb2xvdXIiOlswLDAsNTBdfSxbMCwwLDUwLDFdXSxbMjYsMjcsIlxcdGV4dGl0e3Rlcm1pbmF0aW9uIGNoZWNrZXJ9IiwwLHsiY29sb3VyIjpbMCwwLDUwXX0sWzAsMCw1MCwxXV0sWzMsMCwiXFxtYXRoc2Z7ZGVzdGlsYXRpb259IiwxLHsiY29sb3VyIjpbMCwwLDUwXSwic3R5bGUiOnsiYm9keSI6eyJuYW1lIjoiZGFzaGVkIn19fSxbMCwwLDUwLDFdXSxbMyw0LCJcXG1hdGhzZntDUFN9IiwxLHsiY3VydmUiOi0yLCJjb2xvdXIiOlswLDAsNTBdfSxbMCwwLDUwLDFdXSxbMyw0LCJcXG1hdGhzZntBTkZ9IiwxLHsiY3VydmUiOjIsImNvbG91ciI6WzAsMCw1MF19LFswLDAsNTAsMV1dLFszLDUsImVyYXN1cmUiLDEseyJjb2xvdXIiOlsyNDAsNjAsNjBdfSxbMjQwLDYwLDYwLDFdXSxbNCw1LCJlcmFzdXJlIiwxLHsiY29sb3VyIjpbMjQwLDYwLDYwXX0sWzI0MCw2MCw2MCwxXV0sWzUsNiwiY29tcGlsZSIsMSx7ImNvbG91ciI6WzI0MCw2MCw2MF19LFsyNDAsNjAsNjAsMV1dLFs1LDcsImNvbXBpbGUiLDEseyJjb2xvdXIiOlsyNDAsNjAsNjBdfSxbMjQwLDYwLDYwLDFdXSxbNSw4LCJjb21waWxlIiwxLHsiY29sb3VyIjpbMjQwLDYwLDYwXX0sWzI0MCw2MCw2MCwxXV0sWzIwLDI4LCJyZXNvbHZlXFwgb3BlblxcIGluIiwxLHsiY3VydmUiOjIsImNvbG91ciI6WzEyMCw2MCw0MF0sInN0eWxlIjp7ImJvZHkiOnsibmFtZSI6ImRhc2hlZCJ9fX0sWzEyMCw2MCw0MCwxXV0sWzE3LDI5LCJkZWZIYW5kbGVyIFxcdG8gZGVmXFx0ZXh0ey19aGFuZGxlciIsMix7ImNvbG91ciI6WzAsMCw1MF19LFswLDAsNTAsMV1dLFsyOSwyLCJcXHRleHRpdHtyZWNvcmQtc30gXFxyaWdodGFycm93IFxcdGV4dGl0e3JlY29yZC10eX0iLDIseyJjb2xvdXIiOlsxMjAsNjAsNDBdfSxbMTIwLDYwLDQwLDFdXSxbMzAsMzEsIm1haW5cXCBzdGVwIiwwLHsiY29sb3VyIjpbMjQwLDYwLDYwXX0sWzI0MCw2MCw2MCwxXV0sWzMyLDMzLCJzZWNvbmRhcnlcXCBzdGVwIiwwLHsiY29sb3VyIjpbMCwwLDUwXX0sWzAsMCw1MCwxXV0sWzM0LDM1LCJyZW1vdmVkXFwgc3RlcCIsMCx7ImNvbG91ciI6WzAsNjAsNjBdfSxbMCw2MCw2MCwxXV0sWzM2LDM3LCJuZXdcXCBzdGVwIiwwLHsiY29sb3VyIjpbMTIwLDYwLDQwXX0sWzEyMCw2MCw0MCwxXV0sWzM4LDM5LCJyZW5hbWVkXFwgc3RlcCIsMCx7ImNvbG91ciI6WzMwLDYwLDYwXX0sWzMwLDYwLDYwLDFdXSxbNDAsMTgsIlxcdGV4dGl0e2xvb2t1cCByZWNvcmQgZmllbGRzfSIsMCx7ImNvbG91ciI6WzMwLDYwLDYwXX0sWzMwLDYwLDYwLDFdXSxbMjIsNDAsInJlc29sdmVcXCBpbmZpeCIsMCx7ImNvbG91ciI6WzMwLDYwLDYwXX0sWzMwLDYwLDYwLDFdXSxbMjgsMjEsInF1YWxpZnlcXCBuYW1lIiwxLHsiY3VydmUiOjEsImNvbG91ciI6WzEyMCw2MCw0MF0sInN0eWxlIjp7ImJvZHkiOnsibmFtZSI6ImRhc2hlZCJ9fX0sWzEyMCw2MCw0MCwxXV0sWzI3LDMsIlxcdGV4dGl0e2NsYXVzZXMgdG8gY2FzZSB0cmVlc30iLDAseyJjb2xvdXIiOlswLDAsNTBdfSxbMCwwLDUwLDFdXV0=)

### Frontend

(:white_check_mark:: Done, :new:: Changes)

- **Parse** :white_check_mark: 
    Break up Juvix syntax into an AST
- **Serialise** :white_check_mark: 
    Convert AST to S-expression
- **Desugar** :white_check_mark: 
    Translate structure to compiler-friendly terms
    
    - **Resolve Records** :new: 

- **Contextify** 
    - **Resolve Open** :white_check_mark: 
    Construct a map of terms to the modules where they were defined
    - **Resolve Open In** :new:
    
    - **Qualify Names** :new: 
    Replace term names with their qualified names
    
    - **Resolve Infix** :new: 
    Shunting-yard algorithm. Needs context for infixivity
    
    - **Lookup Record Fields** :new: 
    
- **Deserialise**
    Convert S-expression to AST
    
### Core
- **Elaboration** :new:       
    - *Scope checker*:
      Replaces bound names with de Bruijn indices 
    - *Type checker*:
        - Input: 
          - Global env
          - Unification problems
          - Declaration or signature
        - Output:
          - AST with types on each node
          - Record matches completed & reordered
          - Implicit arguments inserted as metas
          - Unification problems
          - Universe graph
  - *Unifier*:
        - Input: problems (over *values*)
        - Output: (if successful) partial subst, blocked problems
            
    If unification "fails", we need to make sure we know if it got stuck or if it *actually* failed
    
  - *Termination checker*:
      Goes after unification in case the shrinking argument is an implicit (maybe has to be in the whole-module stuff below for the same reason)
  - *Compile clauses to case trees* 
  Implementation of [this paper](https://www.cambridge.org/core/journals/journal-of-functional-programming/article/elaborating-dependent-copattern-matching-no-pattern-left-behind/F13CECDAB2B6200135D45452CA44A8B3)





## Relevant resources

https://jesper.sikanda.be/files/AIMXXXIII.html#/features-that-could-be-added-later