# 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


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