?

Log in

No account? Create an account
Redexing - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Redexing [Apr. 23rd, 2011|04:35 pm]
Lindsey Kuper
[Tags|, ]

For the last two weeks at work, my little PLT Redex model of Rust has been taking shape. It's been a lot of fun. I started with lambda calculus, like y' do, but it became clear that that doesn't really make sense as a language to grow Rust out of; for one thing, functions are not expressions in Rust.1 Still, one of the nice, reusable pieces to have come out of that attempt is that I implemented the λgc language from "Abstract Models of Memory Management" by Morrisett, Felleisen and Harper. This was a good way to figure out what I was doing with Redex. It was instructive to go from reading the paper to having running code for λgc. The paper didn't gloss over a lot, but it did gloss over a little! The hardest part was, as usual, Naming Things.

I was able to borrow some ideas from λgc for the Rust model, which I'm calling baby-rust. Whereas λgc models a program as an initially empty heap followed by an expression, baby-rust models a program as a list of "items" (definitions of functions and types), followed by an initially empty heap, followed by an expression. I'm still not modeling the stack explicitly, so this only takes me half as far as I need to go for a realistic model, but items, at least, are a real concept in Rust, so it's a start.

Just for fun, I threw in a baby-rust typechecker, named typeck just like the real Rust typechecker is, even though my brain still insists on pronouncing that as "type eccch". Like Rust, baby-rust has tuples and tuple indexing operations. For instance, in baby-rust you can pull bar out of the tuple (tup foo bar baz) using the expression (index (tup foo bar baz) 1). The best part was when I realized that any old thing that evaluates to a number should be able to appear where the 1 is in that expression, and that therefore, in order to determine the type of the whole expression, I needed to know not only that that thing is a number, but which number it is.2 So now the typechecker calls off to the reduction relation! Excellent!

I'm ready to start thinking seriously about self-types now, so I'm going to try to put the model on the shelf and come back to it later, but I'm a little worried that I won't be able to stay away. Building languages out of ((languages out of) ...) Scheme just feels so good.


  1. Before you flip out and stab: Rust is still mostly an expression language, and it does have something called bind expressions, which are like closures. I'm not modeling those yet, though. Okay, carry on flipping out and stabbing.
  2. In principle, I could also reject the program as ill-typed if it tried to index out of bounds. I'm actually almost already doing that: a call to Racket's list-ref raises a run-time error, but list-ref's run-time is baby-rust's typechecking time, so I'm "statically" rejecting baby-rust programs that index out of bounds before I "run" them. Dependent types haha woo? Now we just need to implement all high-assurance systems software in Redex and we're set, right?
LinkReply

Comments:
(Deleted comment)
[User Picture]From: oniugnip
2011-04-24 03:42 pm (UTC)
That's accurate! :)

It's also like this:
- Lindsey is using this Redex thing to build a model of the Rust programming language; the model will help the team experiment with new features, and maybe help prove things. (Rust is the new programming language that they're building)

- She hadn't used Redex before, so she's learning how to do that from examples, some of which are more or less like Rust, so more or less applicable. Redex is made of a Scheme dialect, and Lindsey's native language is Scheme, so it's fun and pleasant!

- Some things about programs can be known before you run the program, and some can't. If you hear people say "type checking" or "static analysis", they mean something like that.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2011-04-24 07:56 pm (UTC)
I suspect that Aarthi caught at least some of that!

Lindsey is using this Redex thing to build a model of the Rust programming language

I think a lot of people get hung up right there. It's weird to think of building a model of a programming language, because a programming language is already a model in the sense that it's one of the layers that abstract away from the hardware, saving you from having to program using a magnetized needle and a steady hand.

So why would someone make a model of a programming language? Because we want to be able to reason about the language itself. Programming languages can be thought of as mathematical objects (they're made of sets, sequences, relations...), and we'd like to be able to use all the tools that math gives us for reasoning about such objects and apply it to reasoning about programming languages, so that we can answer questions like, say, "Is this program correct?" and "Under what circumstances will this program raise an error?" and "Is this program indistinguishable from that other program?" But programming languages in their full complexity are too hard to reason about this way -- so we build models that try to capture the important features of how the language behaves but are also simple enough to reason about. If the model hits the sweet spot between accuracy and simplicity, then doing this can help us understand what programs in the real language mean, and what programs in the real language do.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: lindseykuper
2011-04-25 03:01 am (UTC)
Yeah. Modeling happens all over the place in science and engineering, of course. Another analogy that comes to mind is what economists do when they model systems of production and consumption.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: lindseykuper
2011-04-25 05:59 pm (UTC)
*makes the sekrit supply/demand gang sign*
(Reply) (Parent) (Thread)
(Deleted comment)
(Deleted comment)
[User Picture]From: lindseykuper
2011-04-26 02:36 am (UTC)
I work pretty hard to keep my writing accessible to a broad audience. But there are always going to be people (like my dad, for instance) who are utterly capable of understanding this stuff but for whom it just isn't all that interesting. (Now, if I were making economic models, hoooo boy would my dad be interested.)
(Reply) (Parent) (Thread)
(Deleted comment)