Victus Spiritus


Probabilistic Nondeterministic Programming

30 Mar 2011

This morning I came across an inviting link on Hacker News, Nondeterminism, part of the Teach Yourself Scheme in Fixnum Days. There are a number of chapters which help new comers to Scheme dig in and get a feel for the language. This chapter discusses McCarthy's amb operator, describes a rules based implementation, and offers several example applications.

amb takes zero or more expressions, and makes a nondeterministic (or "ambiguous'') choice among them, preferring those choices that cause the program to converge meaningfully.

What drew me to this topic is that a lack of predictability can be an advantage to solving certain types of problems. There are plenty of options for deterministic programming, but not nearly as many which implement fuzzy or unpredictable decision logic. What will a program do with a slightly malformed packet, or a combination of headers that appear to be JSON mixed with a markup language and include binary attachments? If a specific interface isn't detailed, we hope that it gracefully fails with an appropriate error message.

While browsing the post I was reminded of a fictional programming language I touched on briefly last year (Probe), and one of the goals for the language is an implicit interface selection system. A source of great complication with programming is delineating rules to cover all probable data and performance environments, ie handling the edge cases. Exhaustively going through an infinite library of perfectly matching formats is impractical to say the least. What would be helpful is an automated lookup system for machine readable specifications, a series of educated guesses based on pattern matching, and memory that persists between executions.

Can we better characterize data patterns so that a fast guessing engine could identify novel combinations of formats by recognizing tell tale signatures?

A follow up post to Probe:

Wonderful references for me to pour over later: