Friday, November 6, 2015

How to get a Ph.D. in computer science if you're me

Recently, I've been privy to a lot of advice that people give to beginning and prospective graduate students in computer science. The "grad school survival" talk given to CMU's CS department is one that's been passed down through a few generations; PLMW at SPLASH is a workshop (affiliated with a few different PL conferences, now) with similar aims. At both of these events, I served on panels to answer questions. But by watching the main presenters' talks, I quietly accumulated critiques of the standard advice, and it occurred to me that my experiences might have value to some folks if expressed in longer form.

As the title of this post suggests, all advice is subjective. The reason that I think people give "advice," even knowing this fact, is that otherwise we're telling very personal stories about experiences that might still be raw. Advice is an abstraction over experience. But abstraction yields generalization, and generalizations require care when referring to human lives --- so I'm going to try my hardest to be honest about where serendipity and immutable facts about myself played a role in my experience.

Monday, September 28, 2015

Strange Loop 2015 Highlights

I've returned from Strange Loop in St. Louis, a tech conference whose talks commonly include themes like PL, web dev, distributed systems, functional programming, and tech education. I was giving an invited talk at the Future Programming Workshop (FPW), part of the Strange Loop preconference.

This year, I had to leave early, missing half of Strange Loop proper, but fortunately there are recordings of all the talks up on YouTube! Unfortunately, the hallway track can't be recorded for delayed consumption, and I'm still bummed to've missed out on talking to a bunch of people I either failed to meet or only had one passing conversation with.

That said, even two days was enough time to come away with plenty to write and think about, and I'd like to share some of my personal highlights of the conference with you.

"I See What You Mean" by Peter Alvaro was the first keynote talk, kicking off Strange Loop. In it he tells the story of Dedalus, a temporal logic programming language inspired by Datalog, for declarative distributed programming. While the technical aspects of this talk are very close to my heart, Peter also does a fantastic job of storytelling and pontificating about the pleasures and perils of designing nice languages for messy domains.

"Unconventional Programming with Chemical Computing" by Carin Meier was the next talk I saw after Peter's, and it was rife with connections to declarative distributed computing. Chemical computing is a very linear-logic-like (in fact, multiset-rewriting) abstraction, where programs are sets of "reaction" rules that have molecules consumed and molecules produced. The main interesting difference in the simulator Carin built is that the multisets are visualized as a bunch of molecules bouncing around in 2D space, and rules fire whenever molecules "collide," which may be constrained by some geometric aspects of the simulation (although those features are not included in the semantics of the program, technically). In the video, Carin gives examples that include a (simplified) Dining Philosophers simulation and an email server network simulation.

"Strange Loops: Capturing Knots with Powerful Notations" by Kay Ye was a really delightful romp through knot theory and mathematical philosophy, with equally delightful hand-drawn slides. It tells the story of (primarily) two disparate notations for knots, one of which is significantly more "clever" and elegant, but obtains its expressive power by optimizing for certain knots (rational knots) that happen to be suited for it, yet don't seem to faithfully map onto the concerns of practicing, knot theorists. I thought this talk made an interesting bridge between the kinds of ideas in Peter Alvaro's talk (abstraction boundaries can hinder users) and the ideas in Phil Wadler's talk (which pushed for a preference of "discovered" theories and languages over "invented" ones) -- knots are a domain which seem, like distributed systems, somewhat resistant to the nice discovered interfaces that PL designers crave, and all the challenge lies in negotiating the gulf between the elegant and the useful.

"From Protesting to Programming: Becoming a Tech Activist" by Idalin Bobé was the keynote that solidified to me that Strange Loop is a conference I want to continue attending and endorsing. Idalin tells her personal story of overcoming the obstacles in her life path toward creating lifechanging tech, and even more importantly, she discusses racist police brutality and the events of Ferguson that created critical mass around public awareness of these issues as well as her own will to get involved. My favorite part of this talk was when she stated point-blank that most of the tech coming out of startups is creating bigger gaps of inequality rather than closing those gaps, and how nearly all of the tech thought to enable disempowered activists can be systematically taken away and turned against them.

"A History of Programming Languages for Two Voices" by David Nolen and Michael Bernstein is a "mixtape" of PL history paired with music history. Although I didn't catch this talk in person, I watched it as soon as it popped up online, because I knew this one would be too good to miss. The main thing I love about this talk is the "now start yr own band" attitude of it, the encouragement to the audience to make our own mixtapes celebrating the interdisciplinary connections that excite us. (I know I, for one, want to do a version of this that includes ML and riot grrl.) Also, this talk strongly reminded me of Leigh Alexander's keynote at Different Games 2013 that did a similar mixtape-style history of video games. [I can't find a video, but this article seems to be a close match to the content.]

Finally, here's the video for my FPW talk, which is about Ceptre as a proposal for prototyping language for games:

Here are the slides, too.

Tuesday, September 22, 2015

Upcoming Appearances

I'll be appearing at a few conferences soon:

  • I'm giving the last invited talk at Future Programming Workshop @ Strange Loop this Thursday, September 24th. It's an adaptation of my thesis defense with more focus on the Ceptre programming language itself.
  • I'll be on a panel at PLMW @ SPLASH, an edition of the Programming Languages Mentoring Workshop geared toward undergrads who may be interested in pursuing a Ph.D. in PL. PLMW is on Tuesday, October 27th.
  • I'll be presenting my paper on Ceptre at AIIDE in Santa Cruz, sometime in November 14-18 (the program isn't up yet). 
Say hi if you'll be around!

Wednesday, September 16, 2015

Dissertation and defense slides!

The final draft of my dissertation has been sent to the printers, and you can download the PDF via that link! I'm now on a list of people I've looked up to for a long time as research role models, which is a bit bewildering.

For the short and vague version (I rely a lot on spoken content rather than words-on-slides for talks), check out the slides for my defense talk on SpeakerDeck.

Monday, August 3, 2015

Finishing my disseration; new draft on Ceptre!

This blog has been silent for some time now due to me putting all of my writing energy into a draft of my dissertation! It has now been sent to my committee, and I defend on August 31st. For now, the draft is in private circulation, but I'm not being picky about who reads it: if you're interested in looking at a copy, let me know. I'll be sure to post a link here once the defense draft is ready.

Meanwhile, a new paper on my game modeling language Ceptre (a fundamental piece of my thesis) has been accepted to AIIDE 2015! Here's a recent draft.

In the next few weeks, I'm going to try to get Ceptre into shape with enough documentation that brave-enough souls can experiment on their own. Meanwhile, the GitHub repo is available, and I'm happy to assist anyone who's interested in playing with what's there.

Tuesday, May 5, 2015

Linear logic proof sets as split-screen hypertext

There is often some confusion when I discuss using linear logic to capture narrative structure. There are two interesting kinds of branching in linear logic, but we usually only talking about branching structure in narrative if it's interactive narrative, i.e. if the branches represent choices or alternatives between outcomes in a story scene. But there is also branching structure in many non-participatory narratives: there is a causal order of events, which is usually not a strictly total ordering. For example, scenes with different sets of characters, whose proceedings don't depend on one another's outcome, may be told in arbitrary order and still be coherent (though of course coherence isn't necessarily a narrative's goal, or its only goal).

The latter kind of branching can be thought of as spatial branching (for a sufficiently metaphorical notion of space), in the sense that different components of the narrative universe can evolve independently, then join together when they need to interact.

Spatial branching contrasts with temporal branching, which is the sort you get from hypertext and other narrative forms typically described as "branching." Choices are made, which determines one linear path through the narrative. Typically the experience of traversing such a path is oblivious to the alternative paths, just as real temporal experiences are oblivious to timelines in which we'd made different choices -- although a great deal of hypertext is designed with the intent of multiple traversals, which imparts a sort of metaexperience evocative of time travel.

In standard logical terms, spatial branching is conjunctive while temporal branching is disjunctive. Multiple independent events can happen "at once" -- "Lola asks her father for money and Manni asks his friend for money" -- but only one event from a set of alternatives can apply to a given piece of narrative state: "Lola dodges the dog on the stairs or she trips on the dog and injures her leg."

In linear logical terms, the more relevant distinction is additive vs. multiplicative branching: additive branching maps to sets of alternative routes from a single narrative state, where multiplicative branching refers to partitions of the state evolving independently.

The distinction also comes up in discussions of nondeterminism and concurrency: a program which asks for a random coin flip and says "heads" or "tails" depending on the answer can be seen as nondeterministic in a different way from a program with two threads, one of which prints "heads" and the other "tails."

Linear logic programs can have both kinds of nondeterminism/branching, but what's interesting is that after you run them -- i.e. after you create a proof a given linear logic formula -- you've selected a choice for all of the temporal branching points, but the resulting proof can still be seen as containing conjunctive, or spatial, branching structure. (I've elaborated previously on the idea of linear logic proofs' concurrent structure.)

One way of connecting linear logic to branching stories, then, is to take the one kind of branching that's left in proofs and map it to the one kind of branching in hypertext stories, which is exactly what we did for Quiescent Theater. The odd thing about this project is that there's a mismatch: we generated disjunctively branching stories from the conjunctively structured proofs. This has the kind of interesting effect that choices in the resulting stories act like "following" particular characters through their experience of the events of the story, with the ability to jump to new characters when the one you're currently following interacts with them. This is also the mechanic in the participatory theater experience Tamara, which partly inspired the experiment -- in fact, when Rob initially proposed the concept, I didn't understand it precisely because of the mismatch between types of branching; only after attending a performance of Tamara did I see the potential for that mismatch to make a kind of sense.

But I've recently been thinking about how to make a more precise correspondence between both kinds of branching structure present in branching + multi-agent narratives, and both kinds of concurrency in linear logic. I think I figured out how today. It requires that we extend traditional hypertext with a notion of compositional components that can be rendered simultaneously -- e.g. by splitting the screen. I've experimented with split-screen hypertext before, but this would require something quite a bit more sophisticated: any click in any panel of the screen could introduce new splits, merge arbitrary panels together, and depend on the state of other panels (in addition to its own state).

With that interpretation, a forward-chaining linear logic program -- or perhaps more precisely, a set of proofs generated from such a logic program -- can be rendered as follows: initialize the page with as many panels as there are atomic resources in the initial context. Provide an interface for selecting any subset of panels. For each selected subset, display a (possibly empty) set of clickable links corresponding to the set of transitions that apply to that resource set. (I originally imagined those links appearing in every relevant panel, but they could equally well appear in a completely separate global panel, modulo UX concerns.) For example, a par of rules [ r1 : a * b -o c ] and [ r2 : a * b -o d ] would render as 2 links when the [ a ] and [ b ] panels are both selected. Then a link click on [ r1 ] would merge [ a ] and [ b ] into a single panel with contents [ c ]. For first-order logic programs (i.e. ones with logic variables), we would need to disjunctively-nondeterministically generate several alternative structures and do a similar transformation on proof steps rather than on whole programs.

I think this idea has been explored in academic study of hypertext from a literary point of view before: this paper on conjunctive hypertext seems relevant, though I'm not entirely sure the structural observations I'm describing are as deep as whatever narratological points they are making.

P.S. If anyone wants to help me build the target interface I described, please let me know. My skills at making visual interfaces look the way I want are... probably not as good as someone else's reading this. ;)

Thursday, March 5, 2015

Using Twine for Games Research (Part III)

Where we last left off, I described Twine's basic capabilities and illustrated how to use them in Twine 2 by way of a tiny hack-and-slash RPG mechanic. You can play the result, and you should also be able to download that HTML file and use Twine 2's "import file" mechanism to load the editable source code/passage layout.

Notice that, in terms of game design, it's not much more sophisticated than a slot machine: the only interesting decision we've incorporated is for the player to determine when to stop pushing her luck with repeated adventures and go home with the current spoils.

What makes this type of RPG strategy more interesting to me is the sorts of decisions that can have longer-term effects, the ones where you spend an accumulation of resources on one of several things that might have a substantial payoff down the road. In a more character-based setting, this could be something like increasing skill levels or adding personality traits.

Often, the game-design goals of these features are multi-faceted: consider the shopping mode of Kim Kardashian Hollywood, for a recent and topical example.

(Screenshot via Michelle Dean.)

The clothing the player buys does have mechanical function (in terms of completing projects faster, for example), but it also has the less tangible function of giving a player a sense of control over which combination of in-game artifacts persist with their avatar as they move through the world.* Because these artifacts are subdivided into independent components (like real clothing), the player can combine them in ways that are not pre-anticipated by the game -- no one enumerated every possible combination; components have to systematically make sense in combination. In other words, clothing is a composable mechanism for customizing player experience.

Lest you think that this kind of visual composition wouldn't translate well to a textual medium, I invite you to play a few Twine games like Porpentine's UNTIL OUR ALIEN HEARTS BEAT AS ONE and Whisperbat's Candy Ant Princess.

These examples probably use an old Twine 1 macro called cyclinglink, which doesn't (AFAICT) have a great replacement in Twine 2 -- but aside from the nice in-line interface, all that's really going on is that the text that's shown once the player confirms her choices gets bound to variables that are then rendered later in the game.

Note again that, while each category of item has to be hand-enumerated by the game designer, the combinations do not. For some deeper thoughts related to this idea, take a look at the Icebound team's post on combinatorial narrative and Allison Parrish's work investigating various units of text for which it makes sense to deconstruct and recombine.

In our hack-and-slash game, we'll want to associate certain traits or properties to certain items in the game, such as a numeric damage trait to a weapon. In the rest of this post, I'll walk you through using Twine 2's datamap construct to do so. (Note: I am trying not to assume pre-existing programming experience in this tutorial, but I hope that experienced programmers can gain something from the explanation anyway.)