$$
% Typography and symbols
\newcommand{\msf}[1]{\mathsf{#1}}
\newcommand{\ctx}{\Gamma}
\newcommand{\qamp}{&\quad}
\newcommand{\qqamp}{&&\quad}
\newcommand{\Coloneqq}{::=}
\newcommand{\proves}{\vdash}
\newcommand{\star}[1]{#1^{*}}
\newcommand{\eps}{\varepsilon}
\newcommand{\nul}{\varnothing}
\newcommand{\brc}[1]{\{{#1}\}}
\newcommand{\binopm}[2]{#1~\bar{\oplus}~#2}
\newcommand{\mag}[1]{|{#1}|}
\newcommand{\aequiv}{\equiv_\alpha}
\newcommand{\semi}[2]{{#1};~{#2}}
% Untyped lambda calculus
\newcommand{\fun}[2]{\lambda ~ {#1} ~ . ~ {#2}}
\newcommand{\app}[2]{#1 ~ #2}
\newcommand{\fix}[3]{\msf{fix}~({#1} : {#2}) ~ . ~ #3 }
\newcommand{\truet}{\msf{true}}
\newcommand{\falset}{\msf{false}}
\newcommand{\define}[2]{{#1} \triangleq {#2}}
% Typed lambda calculus - expressions
\newcommand{\funt}[3]{\lambda ~ \left(#1 : #2\right) ~ . ~ #3}
\newcommand{\lett}[4]{\msf{let} ~ \hasType{#1}{#2} = #3 ~ \msf{in} ~ #4}
\newcommand{\letrec}[4]{\msf{letrec} ~ \hasType{#1}{#2} = #3 ~ \msf{in} ~ #4}a
\newcommand{\ift}[3]{\msf{if} ~ {#1} ~ \msf{then} ~ {#2} ~ \msf{else} ~ {#3}}
\newcommand{\rec}[5]{\msf{rec}(#1; ~ #2.#3.#4)(#5)}
\newcommand{\case}[5]{\msf{case} ~ {#1} ~ \{ L(#2) \to #3 \mid R(#4) \to #5 \}}
\newcommand{\pair}[2]{\left({#1},~{#2}\right)}
\newcommand{\proj}[2]{#1 . #2}
\newcommand{\inj}[3]{\msf{inj} ~ #1 = #2 ~ \msf{as} ~ #3}
\newcommand{\letv}[3]{\msf{let} ~ {#1} = {#2} ~ \msf{in} ~ {#3}}
\newcommand{\fold}[2]{\msf{fold}~{#1}~\msf{as}~{#2}}
\newcommand{\unfold}[1]{\msf{unfold}~{#1}}
\newcommand{\poly}[2]{\Lambda~{#1}~.~ #2}
\newcommand{\polyapp}[2]{{#1}~\left[{#2}\right]}
\newcommand{\export}[3]{\msf{export}~ #1 ~\msf{without}~{#2}~\msf{as}~ #3}
\newcommand{\import}[4]{\msf{import} ~ ({#1}, {#2}) = {#3} ~ \msf{in} ~ #4}
% Typed lambda calculus - types
\newcommand{\tnum}{\msf{num}}
\newcommand{\tstr}{\msf{string}}
\newcommand{\tint}{\msf{int}}
\newcommand{\tbool}{\msf{bool}}
\newcommand{\tfun}[2]{#1 \rightarrow #2}
\newcommand{\tprod}[2]{#1 \times #2}
\newcommand{\tsum}[2]{#1 + #2}
\newcommand{\trec}[2]{\mu~{#1}~.~{#2}}
\newcommand{\tvoid}{\msf{void}}
\newcommand{\tunit}{\msf{unit}}
\newcommand{\tpoly}[2]{\forall~{#1}~.~{#2}}
\newcommand{\tmod}[2]{\exists ~ {#1} ~ . ~ #2}
% WebAssembly
\newcommand{\wconst}[1]{\msf{i32.const}~{#1}}
\newcommand{\wbinop}[1]{\msf{i32}.{#1}}
\newcommand{\wgetlocal}[1]{\msf{get\_local}~{#1}}
\newcommand{\wsetlocal}[1]{\msf{set\_local}~{#1}}
\newcommand{\wgetglobal}[1]{\msf{get\_global}~{#1}}
\newcommand{\wsetglobal}[1]{\msf{set\_global}~{#1}}
\newcommand{\wload}{\msf{i32.load}}
\newcommand{\wstore}{\msf{i32.store}}
\newcommand{\wsize}{\msf{memory.size}}
\newcommand{\wgrow}{\msf{memory.grow}}
\newcommand{\wunreachable}{\msf{unreachable}}
\newcommand{\wblock}[1]{\msf{block}~{#1}}
\newcommand{\wloop}[1]{\msf{loop}~{#1}}
\newcommand{\wbr}[1]{\msf{br}~{#1}}
\newcommand{\wbrif}[1]{\msf{br\_if}~{#1}}
\newcommand{\wreturn}{\msf{return}}
\newcommand{\wcall}[1]{\msf{call}~{#1}}
\newcommand{\wlabel}[2]{\msf{label}~\{#1\}~{#2}}
\newcommand{\wframe}[2]{\msf{frame}~({#1}, {#2})}
\newcommand{\wtrapping}{\msf{trapping}}
\newcommand{\wbreaking}[1]{\msf{breaking}~{#1}}
\newcommand{\wreturning}[1]{\msf{returning}~{#1}}
\newcommand{\wconfig}[5]{\{\msf{module}{:}~{#1};~\msf{mem}{:}~{#2};~\msf{locals}{:}~{#3};~\msf{stack}{:}~{#4};~\msf{instrs}{:}~{#5}\}}
\newcommand{\wfunc}[4]{\{\msf{params}{:}~{#1};~\msf{locals}{:}~{#2};~\msf{return}~{#3};~\msf{body}{:}~{#4}\}}
\newcommand{\wmodule}[1]{\{\msf{funcs}{:}~{#1}\}}
\newcommand{\wcg}{\msf{globals}}
\newcommand{\wcf}{\msf{funcs}}
\newcommand{\wci}{\msf{instrs}}
\newcommand{\wcs}{\msf{stack}}
\newcommand{\wcl}{\msf{locals}}
\newcommand{\wclab}{\msf{labels}}
\newcommand{\wcm}{\msf{mem}}
\newcommand{\wcmod}{\msf{module}}
\newcommand{\wsteps}[2]{\steps{\brc{#1}}{\brc{#2}}}
\newcommand{\with}{\underline{\msf{with}}}
\newcommand{\wvalid}[2]{{#1} \vdash {#2}~\msf{valid}}
\newcommand{\wif}[2]{\msf{if}~{#1}~{\msf{else}}~{#2}}
\newcommand{\wfor}[4]{\msf{for}~(\msf{init}~{#1})~(\msf{cond}~{#2})~(\msf{post}~{#3})~{#4}}
% assign4.3 custom
\newcommand{\wtry}[2]{\msf{try}~{#1}~\msf{catch}~{#2}}
\newcommand{\wraise}{\msf{raise}}
\newcommand{\wraising}[1]{\msf{raising}~{#1}}
\newcommand{\wconst}[1]{\msf{i32.const}~{#1}}
\newcommand{\wbinop}[1]{\msf{i32}.{#1}}
\newcommand{\wgetlocal}[1]{\msf{get\_local}~{#1}}
\newcommand{\wsetlocal}[1]{\msf{set\_local}~{#1}}
\newcommand{\wgetglobal}[1]{\msf{get\_global}~{#1}}
\newcommand{\wsetglobal}[1]{\msf{set\_global}~{#1}}
\newcommand{\wload}{\msf{i32.load}}
\newcommand{\wstore}{\msf{i32.store}}
\newcommand{\wsize}{\msf{memory.size}}
\newcommand{\wgrow}{\msf{memory.grow}}
\newcommand{\wunreachable}{\msf{unreachable}}
\newcommand{\wblock}[1]{\msf{block}~{#1}}
\newcommand{\wloop}[1]{\msf{loop}~{#1}}
\newcommand{\wbr}[1]{\msf{br}~{#1}}
\newcommand{\wbrif}[1]{\msf{br\_if}~{#1}}
\newcommand{\wreturn}{\msf{return}}
\newcommand{\wcall}[1]{\msf{call}~{#1}}
\newcommand{\wlabel}[2]{\msf{label}~\{#1\}~{#2}}
\newcommand{\wframe}[2]{\msf{frame}~({#1}, {#2})}
\newcommand{\wtrapping}{\msf{trapping}}
\newcommand{\wbreaking}[1]{\msf{breaking}~{#1}}
\newcommand{\wreturning}[1]{\msf{returning}~{#1}}
\newcommand{\wconfig}[5]{\{\msf{module}{:}~{#1};~\msf{mem}{:}~{#2};~\msf{locals}{:}~{#3};~\msf{stack}{:}~{#4};~\msf{instrs}{:}~{#5}\}}
\newcommand{\wfunc}[4]{\{\msf{params}{:}~{#1};~\msf{locals}{:}~{#2};~\msf{return}~{#3};~\msf{body}{:}~{#4}\}}
\newcommand{\wmodule}[1]{\{\msf{funcs}{:}~{#1}\}}
\newcommand{\wcg}{\msf{globals}}
\newcommand{\wcf}{\msf{funcs}}
\newcommand{\wci}{\msf{instrs}}
\newcommand{\wcs}{\msf{stack}}
\newcommand{\wcl}{\msf{locals}}
\newcommand{\wcm}{\msf{mem}}
\newcommand{\wcmod}{\msf{module}}
\newcommand{\wsteps}[2]{\steps{\brc{#1}}{\brc{#2}}}
\newcommand{\with}{\underline{\msf{with}}}
\newcommand{\wvalid}[2]{{#1} \vdash {#2}~\msf{valid}}
% assign4.3 custom
\newcommand{\wtry}[2]{\msf{try}~{#1}~\msf{catch}~{#2}}
\newcommand{\wraise}{\msf{raise}}
\newcommand{\wraising}[1]{\msf{raising}~{#1}}
\newcommand{\wif}[2]{\msf{if}~{#1}~{\msf{else}}~{#2}}
\newcommand{\wfor}[4]{\msf{for}~(\msf{init}~{#1})~(\msf{cond}~{#2})~(\msf{post}~{#3})~{#4}}
\newcommand{\windirect}[1]{\msf{call\_indirect}~{#1}}
% session types
\newcommand{\ssend}[2]{\msf{send}~{#1};~{#2}}
\newcommand{\srecv}[2]{\msf{recv}~{#1};~{#2}}
\newcommand{\soffer}[4]{\msf{offer}~\{{#1}\colon({#2})\mid{#3}\colon({#4})\}}
\newcommand{\schoose}[4]{\msf{choose}~\{{#1}\colon({#2})\mid{#3}\colon({#4})\}}
\newcommand{\srec}[1]{\msf{label};~{#1}}
\newcommand{\sgoto}[1]{\msf{goto}~{#1}}
\newcommand{\dual}[1]{\overline{#1}}
% Inference rules
\newcommand{\inferrule}[3][]{\cfrac{#2}{#3}\;{#1}}
\newcommand{\ir}[3]{\inferrule[\text{(#1)}]{#2}{#3}}
\newcommand{\s}{\hspace{1em}}
\newcommand{\nl}{\\[2em]}
\newcommand{\evalto}{\boldsymbol{\overset{*}{\mapsto}}}
\newcommand{\steps}[2]{#1 \boldsymbol{\mapsto} #2}
\newcommand{\evals}[2]{#1 \evalto #2}
\newcommand{\subst}[3]{[#1 \rightarrow #2] ~ #3}
\newcommand{\dynJ}[2]{#1 \proves #2}
\newcommand{\dynJC}[1]{\dynJ{\ctx}{#1}}
\newcommand{\typeJ}[3]{#1 \proves \hasType{#2}{#3}}
\newcommand{\typeJC}[2]{\typeJ{\ctx}{#1}{#2}}
\newcommand{\hasType}[2]{#1 : #2}
\newcommand{\val}[1]{#1~\msf{val}}
\newcommand{\num}[1]{\msf{Int}(#1)}
\newcommand{\err}[1]{#1~\msf{err}}
\newcommand{\trans}[2]{#1 \leadsto #2}
\newcommand{\size}[1]{\left|#1\right|}
$$
Digest - July 2017
Will Crichton
—
July 5, 2017
In which I discuss the joys of Factorio, the woes of preachy literature, and the confounding state of programming language courses.
I have two big stories in the pipeline: first, we’re about to resubmit the our paper about video analysis at scale and then I’ll probably write a blog/website/HN post about it. Stay tuned! Second, I just started my research internship at Snapchat, so more on that at the end of the summer. In the meantime, the digest:
Book: The Circle (★★★☆☆)
You’ve probably heard of The Circle by now—it’s the one that got turned into a movie with Emma Watson and Tom Hanks (I haven’t seen it, but the reviews weren’t stellar). I don’t have a stellar review for the book either. The basic premise is Mae, a young college graduate from a podunk Midwestern town lands a job at the world’s most prestigious/innovative/rich/scary/powerful tech firm, the Circle. The Circle actually covers a wide range of issues relevant to the modern tech industry, particularly within the realm of privacy, knowledge sharing, social media, and so forth; it earns at least one star from me for relevance. Its depiction of tech culture is in parallel to the TV show Silicon Valley, but is more dystopian in nature than humorous. My problem with the book is that its treatment of, well… everything is heavy-handed. None of the characters carry any emotional weight or have any notable character development. For example, while Mae adopts many of the privacy-invading Circle technologies, her foil is an ex-boyfriend who gives stump speeches and writes long letters explaining why privacy is important. I don’t feel like the ex-boyfriend is a character so much as a mouthpiece for the author, and so while I appreciate the book’s exploration of topically relevant themes, it doesn’t do much for me as a narrative.
Game: Factorio (★★★★★)
If you, dear reader, are not a software developer, but want to know what it’s like without paying $200k for a CS degree, then I have the game for you. For only $20 (10,000 times cheaper!) you can get Factorio, a software engineering simulator disguised as a Minecraft extension disguised as a Lego sandbox. The premise of the game is that you are a spaceship pilot crash landed on an alien planet with nothing but your suit and your bare hands (which, come to think of it, is basically the plot of Subnautica…). Your goal is to gather the materials necessary to build a rocket to get yourself off the planet while fending off the locals (angry dogs called Biters). However, unlike Minecraft where materials have to be gathered by hand, the point of Factorio is that everything can be automated. Everything.
- You build machines to automatically mine the resources (coal, iron, copper, etc.) for you
- You build machines to automatically combine the resources into better resources
- You build machines to build those building machines
- You build trains to deliver the building machines from one building machine to another
- You build building machines to build the trains, and so on.
Factorio is the most apt metaphor for programming that I have ever seen. It captures all of the fun of automation with all the struggles of software design—how do I lay out my base? How can I refactor my production line once it’s already in place? How can I scale up my existing designs? How can I work with my legacy code old bases? Solving these problems is what makes Factorio spectacularly fun for me. Easily the best return on investment I’ve made in recent memory.
Idea: Programming Language Pedagogy
As fate would have it, next fall I will be the instructor for cs242, Stanford’s programming language (PL) course. I’m in the process of redesigning the course from scratch (for a number of reasons), and as a part of the process I’ve been scouring the web for syllabuses (syllabi?) from PL courses at other universities such as MIT, Harvard, CMU, Berkeley, UW, Northeastern, and Brown. My first observation was that PL courses have a greater diversity in topics, direction, and philosophy than any other computer science course I’ve ever seen. Topics like computer systems and algorithms tend to be pretty homogenous across colleges, but hot damn, nobody agrees on how to teach PL. This is evidenced by the fact that everyone has their own textbook (Stanford, MIT, CMU, Northeastern), and courses that don’t have their own textbook tend to use a completely custom curriculum or a broad sampling from many of the aforementioned texts. So… why can’t anyone agree?
Well, for starters, PL is a big field. People most commonly associate PL research with type theory (and its many relations—logic, complexity theory, category theory, …), but PL also extends into compiler design and implementation, domain-specific languages, human-computer interaction, and many more subfields. Andy Ko gave a nice taxonomy of the different perspectives on PL and how they influence research in his Splash 2016 keynote. Broadly speaking, PL courses tend to focus either on formal methods and static analysis (CMU, Harvard) or programming patterns and compiler implementation (UW, Berkeley/UW). Teaching PL is still itself an active area of research: some folks from Brown presented at SNAPL 2017 about their new course design that focuses around exploring languages experimentally via “probing” (trying different code and seeing what happens) instead of the normal top-down formal approach. I’m doubtful that such an approach is the right direction long term, but it’s good that instructors are actively trying to mix it up!
As for myself, I’m still undecided as to what to teach for cs242 and how to present it. I’ll make a dedicated post for my proposed curricular design closer to the beginning of the Stanford school year for a deeper dive into the subject.
YouTube channel: Every Frame a Painting
Easily the highest quality videos on film studies that you’ll find on YouTube. Infrequent poster but highly recommended.
YouTube video: history of the entire world, i guess
The scintillating follow-up to the timeless video the history of japan.
Song: Maple Adventure - dark cat
I don’t think I’ll ever get tired of 8-bit music.
OS X Tool: Spectacle
It’s a window manager for OS X. Keyboard shortcuts for full screen, half screen, thirds, and so on. Simple and super useful!