corbin-pydx15-typhon.lyx

#LyX 2.1 created this file. For more info see http://www.lyx.org/
\lyxformat 474
\begin_document
\begin_header
\textclass powerdot
\begin_preamble
\usepackage{tikz}
\usetikzlibrary{matrix}

% use text width & text height instead of minimum size, as that causes
% alignment issues, and since blocks require uniform sizes
\tikzstyle{tblock} = [matrix of nodes,ampersand replacement=\&,nodes={
    outer sep=0pt,text width=2em,inner ysep=1em,text centered
}]

% \tblock {input} {output} {machine}
\newcommand{\tblocktext}[3]{
    {#1} \& $\to$   \& {#2} \\
         \&  {#3}   \&      \\
}

\newcommand{\tblockoutline}[1]{
    \draw (#1-1-1.south west) |- (#1-1-3.north east) |- (#1-1-3.south west) |- (#1-2-2.south west) |- (#1-1-1.south west);
}

\tikzstyle{wblock} = [outer sep=0pt,text width=2em,inner ysep=0.5em,text centered,font=\footnotesize]

\newcommand{\wblockoutline}[1]{
    \draw (#1.south) -- (#1.north west) -- (#1.north east) -- (#1.south);
}
\end_preamble
\options style=horatio
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_math auto
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\default_output_format pdf
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Monte: Building a programming language using RPython
\end_layout

\begin_layout Author
Corbin Simpson
\end_layout

\begin_layout Date
October 10, 2015 (PyDX '15)
\end_layout

\begin_layout Slide
Hi!
\end_layout

\begin_layout Standard
I'm Corbin!
\end_layout

\begin_layout Standard
What you don't need to know:
\end_layout

\begin_layout Itemize
Monte
\end_layout

\begin_layout Itemize
RPython
\end_layout

\begin_layout Itemize
Lojban
\end_layout

\begin_layout Standard
You don't 
\series bold
need
\series default
 to know compilers, but it will help.
\end_layout

\begin_layout Slide
Some Pre-talk Thanks
\end_layout

\begin_layout Itemize
Allen, for getting me to build Typhon
\end_layout

\begin_layout Itemize
The original implementors of E
\end_layout

\begin_layout Itemize
Em and Mike, for trailblazing
\end_layout

\begin_layout Itemize
Dan Connelly for making awesome documentation (with diagrams!)
\end_layout

\begin_layout Itemize
Everybody else in 
\family typewriter
#monte
\family default
 and 
\family typewriter
#erights
\end_layout

\begin_layout Slide
The Python Side
\end_layout

\begin_layout Itemize
Twisted
\end_layout

\begin_layout Itemize
PyPy
\end_layout

\begin_layout Slide
Constant Sadness
\end_layout

\begin_layout Itemize
People don't use Twisted
\end_layout

\begin_layout Itemize
People don't use PyPy
\end_layout

\begin_layout Slide
Enter Monte
\end_layout

\begin_layout Itemize
Has syntactic and semantic features equivalent to always having Twisted
 available
\end_layout

\begin_layout Itemize
Reference implementation is built using PyPy's toolchain, 
\series bold
RPython
\end_layout

\begin_layout Section
RPython is not Python
\end_layout

\begin_layout Slide
What's RPython, Anyway?
\end_layout

\begin_layout Itemize
PyPy team: 
\begin_inset Quotes eld
\end_inset

RPython is a restricted subset of Python amenable to static analysis.
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
Allen: 
\begin_inset Quotes eld
\end_inset

RPython is OCaml with a very odd syntax and a very odd standard library.
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
RPython is a toolchain that can translate carefully crafted Python packages
 into highly efficient low-level code.
\end_layout

\begin_layout Slide
Why RPython?
\end_layout

\begin_layout Standard
You have to be writing an interpreter for a language; RPython is not easy
 to use.
\end_layout

\begin_layout Standard
If nothing else, know this: RPython turns interpreters into JIT compilers
 at a steep engineering discount.
\end_layout

\begin_layout Slide
Wait, What
\end_layout

\begin_layout Standard
Programs written in RPython are imported and then transformed from Python
 into a high-level statically-typed statically-named form (
\begin_inset Quotes eld
\end_inset

translation
\begin_inset Quotes erd
\end_inset

).
 This form is augmented:
\end_layout

\begin_layout Itemize
GC: A garbage collector, also written in RPython, is hooked in.
 The GC can be chosen at translation time.
\end_layout

\begin_layout Itemize
JIT: Based on JIT annotations written by hand, the program is turned into
 a JIT compiler which functions automatically and is correct independent
 of your program.
\end_layout

\begin_layout Standard
RPython finally performs some optimizations (malloc removal, generated switches,
 etc.) and emits an executable.
\end_layout

\begin_layout Slide
RPython Alternatives
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{description}
\end_layout

\begin_layout Plain Layout


\backslash
item[LLVM] Mediocre GC control, poor JIT technology, and writing C++ drains
 my soul
\end_layout

\begin_layout Plain Layout


\backslash
item[GHC Haskell] Speedy and terse but mutation is hard
\end_layout

\begin_layout Plain Layout


\backslash
item[Bare/NIH C++] Speedy but very difficult to write, read, and maintain
\end_layout

\begin_layout Plain Layout


\backslash
item[Truffle] Very powerful but was not mature when I started
\end_layout

\begin_layout Plain Layout


\backslash
end{description}
\end_layout

\end_inset


\end_layout

\begin_layout Section
The Tombstones of Terror
\end_layout

\begin_layout Slide
Introducing Tombstones
\end_layout

\begin_layout Standard
The old Monte compiler:
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
node(interp) [tblock] {
\backslash
tblocktext{Mt}{Py}{Py}};
\end_layout

\begin_layout Plain Layout


\backslash
tblockoutline{interp};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
The RPython translator:
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
node(rpy) [tblock] {
\backslash
tblocktext{RPy}{Exe}{Py}};
\end_layout

\begin_layout Plain Layout


\backslash
tblockoutline{rpy};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\end_inset


\end_layout

\begin_layout Slide
Untranslated & Translated
\end_layout

\begin_layout Standard
Typhon untranslated:
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
node(untrans) [tblock] {
\backslash
tblocktext{MAST}{$
\backslash
star$}{RPy}};
\end_layout

\begin_layout Plain Layout


\backslash
tblockoutline{untrans};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Typhon translated:
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
node(untrans) [tblock] {
\backslash
tblocktext{MAST}{$
\backslash
star$}{RPy}};
\end_layout

\begin_layout Plain Layout


\backslash
tblockoutline{untrans};
\end_layout

\begin_layout Plain Layout


\backslash
node(rpy) at (untrans-1-2.south east) [tblock,anchor=rpy-1-1.north west] {
\backslash
tblocktext{RPy}{Exe}{Py}};
\end_layout

\begin_layout Plain Layout


\backslash
tblockoutline{rpy};
\end_layout

\begin_layout Plain Layout


\backslash
node(trans) at (rpy-1-3.north west) [tblock,anchor=trans-1-1.south west] {
\backslash
tblocktext{MAST}{$
\backslash
star$}{Exe}};
\end_layout

\begin_layout Plain Layout


\backslash
tblockoutline{trans};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\end_inset


\end_layout

\begin_layout Slide
The Missing 'Stone
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
node(montec) [tblock] {
\backslash
tblocktext{Mt}{MAST}{Mt}};
\end_layout

\begin_layout Plain Layout


\backslash
tblockoutline{montec};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\end_inset


\end_layout

\begin_layout Section
Typhon
\end_layout

\begin_layout Slide
It's Like an Onion
\end_layout

\begin_layout Itemize
AST loader
\end_layout

\begin_layout Itemize
AST-to-bytecode compiler
\end_layout

\begin_layout Itemize
Object model
\end_layout

\begin_layout Itemize
JIT annotations
\end_layout

\begin_layout Itemize
Vats and libuv
\end_layout

\begin_layout Slide
AST Loader
\end_layout

\begin_layout Standard
The AST loader loads files into an in-memory AST.
\end_layout

\begin_layout Slide
Bytecode Compiler
\end_layout

\begin_layout Itemize
Compiles to VM based on SmallCaps for E
\end_layout

\begin_layout Itemize
Compiler implemented as AST visitor
\end_layout

\begin_layout Itemize
Simple semantics: no loops, one test, exception mini-stack
\end_layout

\begin_layout Itemize
Compiler lowers static names to frame indices, turning dicts into lists
\end_layout

\begin_layout Itemize
Unstable design: Completely internal to Typhon (so it can be changed as
 needed)
\end_layout

\begin_layout Slide
Object Model
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout

[every node/.style={fill=green!20}]
\end_layout

\begin_layout Plain Layout


\backslash
node (root) at (3,3) {root};
\end_layout

\begin_layout Plain Layout


\backslash
node (data) at (0,2) {data (Char, Int, 
\backslash
dots)};
\end_layout

\begin_layout Plain Layout


\backslash
node (collections) at (1, 0) {collections (List, Map, Set, 
\backslash
dots)};
\end_layout

\begin_layout Plain Layout


\backslash
node (user) at (5, 1) {user-defined objects};
\end_layout

\begin_layout Plain Layout


\backslash
node (runtime) at (7, 2) {runtime objects};
\end_layout

\begin_layout Plain Layout


\backslash
foreach 
\backslash
to in {data,collections,user,runtime}
\end_layout

\begin_layout Plain Layout

  
\backslash
draw (root) -- (
\backslash
to);
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\end_inset


\end_layout

\begin_layout Slide
JIT Annotations
\end_layout

\begin_layout Standard
JIT's typical usage:
\end_layout

\begin_layout Enumerate
At every JIT merge point, check whether the current code is being executed
 often (
\begin_inset Quotes eld
\end_inset

hot
\begin_inset Quotes erd
\end_inset

)
\end_layout

\begin_layout Enumerate
When code is hot, trace actions 
\series bold
of the interpreter
\series default
 from one merge point to the next
\end_layout

\begin_deeper
\begin_layout Enumerate
When value or type discrimination occurs, 
\series bold
guard
\series default
 the chosen branches
\end_layout

\begin_layout Enumerate
Trace through function calls (free inlining)
\end_layout

\end_deeper
\begin_layout Enumerate
Optimize the trace, removing superfluous operations
\end_layout

\begin_layout Enumerate
When guards fail, retrace from the failed guard and create 
\series bold
branches
\end_layout

\begin_layout Slide
JIT Annotations, Cont.
\end_layout

\begin_layout Itemize
The JIT needs to know which loops to trace.
 Place 
\family typewriter
jit_merge_point
\family default
 annotations at the head of each (user-level) loop.
\end_layout

\begin_layout Itemize
Any interpreter-level loop causes a function to be opaque to the JIT; it
 will be called and not traced.
 To fix this, use 
\family typewriter
unroll_safe
\family default
 or 
\family typewriter
look_inside_iff
\family default
, but be wary of code explosion.
\end_layout

\begin_layout Itemize
Some functions need to be opaque for performance or to avoid JIT unsafety.
 They are marked 
\family typewriter
dont_look_inside
\family default
.
\end_layout

\begin_layout Itemize
Some functions need to be opaque to preserve referential transparency.
 They are marked 
\family typewriter
elidable
\family default
.
 There's also 
\family typewriter
_immutable_fields_
\family default
 for attributes.
\end_layout

\begin_layout Itemize
\begin_inset Quotes eld
\end_inset

The trick
\begin_inset Quotes erd
\end_inset

: The JIT colors values as 
\color red
red
\color inherit
 or 
\color green
green
\color inherit
 depending on whether they are constant during the trace.
 
\family typewriter
promote(
\color red
red
\color inherit
)
\family default
 returns a 
\color green
green
\color inherit
 value; the JIT usually emits a guard.
\end_layout

\begin_layout Slide
Vats
\end_layout

\begin_layout Itemize
Monte's threads of control are called 
\series bold
vats
\series default
.
\end_layout

\begin_layout Itemize
Objects live in vats.
\end_layout

\begin_layout Itemize
Vats send messages to other vats; objects send messages to other objects.
 All vats are independently managed.
\end_layout

\begin_layout Itemize
Concurrency and parallelism should be a snap! Just gotta reinvent Twisted,
 which isn't RPython-compatible…
\end_layout

\begin_layout Slide
FFI
\end_layout

\begin_layout Itemize
RPython has FFI for C (
\begin_inset Quotes eld
\end_inset

rffi
\begin_inset Quotes erd
\end_inset

)
\end_layout

\begin_layout Itemize
Violates Monte's safety guarantees, so only used sparingly (sorry libpng)
\end_layout

\begin_layout Itemize
libuv
\end_layout

\begin_layout Itemize
libsodium, someday in the future
\end_layout

\begin_layout Section
Final Thoughts
\end_layout

\begin_layout Slide
Should you use RPython?
\end_layout

\begin_layout Standard
If you're writing an interpreter, and you want it to go fast, and you don't
 want to write Java or C++, then yes, consider it.
\end_layout

\begin_layout Standard
RPython's competitors are generally worth considering too.
\end_layout

\begin_layout Slide
Questions?
\end_layout

\begin_layout Standard
Thanks!
\end_layout

\begin_layout EndSlide

\end_layout

\end_body
\end_document