Skip to main content


Showing posts from 2013

Learning typed functional programming: obstacles & inroads

Yesterday, there was a discussion on a mailing list I'm on about a perception of gender diversity problems in the communities around functional programming, type theory, and programming language theory, even relative to other areas of computer science. After some speculation about education barriers and community approachability, I decided to conduct an informal survey on Twitter:

if you think typed/functional programming is harder/more intimidating than other kinds, can you say why in a tweet? won't argue just curious
— chrisamaphone (@chrisamaphone) December 17, 2013 You can read several of the (filtering for sarcasm/criticisms of languages) collected responses on Storify. I left "typed", "functional", and the combination thereof intentionally ambiguous because I was interested in how people interpreted those words as well as their reactions to whatever programming constructs they associated with them.

Because I promised not to argue with anyone who repli…

Post-proposal reading list

I passed my thesis proposal!

As I've spoken to more and more people about my work, I'm learning about a bunch of exciting related systems, and now I have a big pile of reading to do! Here's what's currently on my stack:

The Oz Project: Bob Harper and Roger Dannenberg brought to my attention a defunct CMU interactive fiction project called Oz, which efforts had some brief extra-academic fame through the Façade game. I've printed out the following papers which seem most relevant to my work:

Hap: A Reactive, Adaptive Architecture for Agents
A. Bryan Loyall and Joseph Bates. Technical Report CMU-CS-91-147, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, June 1991.

An Architecture for Action, Emotion, and Social Behavior
Joseph Bates, A. Bryan Loyall, and W. Scott Reilly. Techical Report CMU-CS-92-144, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. May 1992. Also appearing in Artificial Social Systems: Fourth European Workshop…

Some classes of effectful programs

I'm going to do something unusual for this blog and talk about functional programming for a bit.

Jessica Kerr wrote a blog post about the concept of idempotence as it's used in math and programming, and I decided I wanted to lay the ideas out in more familiar terms to me.

So, consider a pure mini-ML with functions, products, numbers, lists, polymorphism, and let-binding, but no references (or other effects -- for the duration of this post I'm going to limit my notion of "effect" to references into a store). This is Language 1 (L1). Now consider adding references and sequencing to this language (i.e. new expressions are ref v, r := v, !r, and (e; e)). This is Language 2 (L2).

The operational semantics of Language 2 includes a store mapping references to values, for which I'll use the metavariable S. In addition to giving types T -> T' to L2 functions, we can give them store specifications S -o S' (using the linear implication symbol -o suggestively …

Paper draft: Linear Logic Programming for Narrative Generation

Gwenn Bosser, João Ferreira, and I have just submitted a paper to LPNMR '13!

Linear Logic Programming for Narrative Generation

In this paper, we explore the use of Linear Logic programming for story generation. We use the language Celf to represent narrative knowledge, and its own querying mechanism to generate story instances, through a number of proof terms. Each proof term obtained is used, through a resource-flow analysis, to build a directed graph where nodes are narrative actions and edges represent inferred causality relationships. Such graphs represent narrative plots structured by narrative causality. Building on previous work evidencing the suitability of Linear Logic as a conceptual model of action and change for narratives, we explore the conditions under which these representations can be operationalized through Linear Logic Programming techniques. This approach is a candidate technique for narrative generation which unifies declarative representations and gene…

Modeling gameplay in Celf, Part 3

(This is another iteration of the example I developed in Part 1 and Part 2, but barring incrementally understanding the code, I think this post is relatively self-contained. Celf-contained, if you will.)

When I took a simple choice-based ("CYOA") game with a few bits of inventorial state and tried to add handles onto the rules so as to specify a specific sequence of player choices, something interesting happened: I had to make new decisions about which parts of the game the player could control, and how. For instance, whether they win or get eaten by a grue depends on a prior choice to take the lamp from the den or not; they cannot control their fate after that point. This makes clear that "getting the lamp" and "opening the door" are player-facing game controls, whereas "getting eaten by a grue" is a choice made by the game. We wound up enumerating those actions as follows.

'start : action.
'opendoor : action.
'getlamp : action.

Modeling gameplay in Celf, Part 2: Simulating Interactivity

Where I last left off, I gave a toy example of using Celf to specify a game's causal structure, summarized by the following ruleset:
start_to_den_or_cellar : start -o {den & cellar}. den_to_cellar_lamp_or_key : den -o         {cellar          & (nolamp -o {getlamp})          & (nokey -o {getkey})}. get_lamp : getlamp -o {gotlamp * den}. get_key : getkey -o {gotkey * den}. cellar_to_den_or_door : cellar -o {den & opendoor}. open_door_without_key : opendoor * nokey -o {cellar * nokey}. open_door_with_key : opendoor * gotkey -o {dark}. dark_with_lamp : dark * gotlamp -o {win}. dark_without_lamp : dark * nolamp -o {lose}. init : type = {nokey * nolamp * start}. As presented, this is effectively "half a game", with no delineation between player choice and game logic -- a fact that allowed us to randomly sample the space of all possible play sequences by querying any final gameplay state -- but that's ultimately uninformative about interactivity.

The key i…

How to create the PL culture I'd like to believe we deserve

I herein interrupt my (ir)regular schedule to post about something sociological rather than metalogical.

I considered relegating this content to my personal blog, but honestly I think these words need to fall on the ears of exactly the folks who are mired enough in the technical community to follow research blogs. This is a post about "PL culture". What I mean by that is the characteristics, defined by the perceptions of its constituents, of "the PL community" -- or any subset of active programming languages researchers who find themselves in each others' company, perhaps at a conference or within a research group at a particular university.

In particular, I want to understand how PL might be failing as a community, and by that I mean either (1) fostering attitudes that make people within it feel othered/alienated/estranged or (2) serving as a barrier to the potential people and ideas it could include but doesn't. I want to cast some attention on the experi…

Modeling gameplay in Celf, Part 1: Fuzz Testing

I'm hereby resolving to stop biting off more than I can chew wrt blog posts - I've got two behemoths in drafts over just the past few days and nothing to show for them (yet). So right now I'm going to try to carefully explain a tiny example that I just worked out over the past half hour and I think nicely encapsulates a few ideas about using Celf and linear logic in the context of interactivity.

Assumed background for this post: familiarity with linear logic connectives, some familiarity with logic programming and the forward/backward chaining distinction.

Here's an informal spec for a simple branching game with a couple pieces of global state that track whether certain paths have been taken:

The cellar and the den are connected rooms. The lamp and the key are in the den. The cellar contains a door, which is locked and must be opened with the key. Once the door is unlocked, the player enters darkness, and if they have a lamp, they win; otherwise, they are eaten by a gr…