Reasoning About Program Behavior Algebraically [pdf] | Hacker News Reader

Reasoning About Program Behavior Algebraically [pdf]

dev.stephendiehl.com

113 pointsrwosync12 comments

From experience (the last time slides for a talk by Stephen Diehl made its way to the HN frontpage), there's a lot of information in the actual (recorded) talk that the slides are going to be missing.

Is the video available?

There are a lot of advanced techniques in these slides, but if you care about program behaviour, in a functional context that mostly reduces to caring about the types of your functions. E.g., in Haskell if you have a function of type `a -> a` you know that it must be the identity function (leaving aside exceptions and undefined).

Taking this further, you can define functions of types that specify your desired behaviour exactly, e.g. guess what this does:

    foo :: List a -> SortedList a

Or this:

    bar :: VerificationToken -> Email Unverified -> Email Verified

That's really the main idea. If you specify the types in the right way, you can make them describe the function quite nicely.

People like to tout this idea about a lot, but I've never seen it used in any rigorous way. It's SUGGESTIVE of program behavior, but I haven't seen any tools for (attempted) extraction of even just FSMs from basic type-level state machines like that. You want to write down a property about "Email Verified" and the paths to values of that type and have the system check it. Real programs are too large for mere suggestion to have any assurance value.

... and I think this presentation had a lot more to offer than the absolute bog-standard techniques of labeled transition systems, whether you do it in the types or not.

I don't understand your points, I guess. Your first point is that you've never seen this technique used in any rigorous way, and your second point is that it's an absolute bog-standard technique? I don't follow.

Very interesting, What is the programming language used in the code examples ?

That's Haskell. Slides 4 & 5 also hint at that, although it's easy to miss:

> Why Haskell is Interesting

Even if you never intend to use Haskell it’s well worth getting a basic understanding of it if you have an interest in CS theory just because it’s used so frequently in interesting talks and papers.

Is the talk recorded? Can we find it somewhere?

Functional Works "might release the talks soon".

https://www.reddit.com/r/haskell/comments/7l2z7d/pdf_stephen...

Sorry for being off-topic, but those slides are beautiful. Does anyone know what they're made in?

Google Slides.

Reply on news.ycombinator.com