5 ms·
Languages that use types for elaborate proofs always seem to me like they only prove the most uninteresting properties of programs, namely the parts that deal w
by pron 12y ago
Languages that use types for elaborate proofs always seem to me like they only prove the most uninteresting properties of programs, namely the parts that deal with data transformations. Not that data transformations aren't important, but the properties they need to preserve are usually easy to be convinced of without any assistance by the compiler.
At the end of the day, programs are written for their side effects (unless your program is a compiler, which is the classical example of an "interesting", non-trivial data transformation, and possibly the only example). What I'm most interested in is proofs that, say, in a concurrent environment, a function that closes a socket will never be called as long as there are pending tasks to write to the socket. Or, because I write concurrent data structures, I'm interested to prove that a certain function will eventually release all locks it acquires. Are there any such languages?
I've heard of effect systems, but I couldn't find enough information on them. Are effect systems capable of the kind of proofs I'm interested in? Are there practical programming languages with powerful effect systems?
EDIT: Some Googling yielded this: http://lambda-the-ultimate.org/node/4768 http://lambda-the-ultimate.org/node/4768 tldr: Not yet.
EDIT: At least the lock proof seems to be implemented as one of Java 8's pluggable type systems: http://types.cs.washington.edu/checker-framework/current/checker-framework-manual.html#lock-checker http://types.cs.washington.edu/checker-framework/current/che...
It lets you add a type (Java 8's pluggable types are intersection types) to a function called @EnsuresLockHeld(locks...) that proves some locks will be held when a function returns and even @EnsuresLockHeldIf(locks..., result) that proves a function grabs certain locks if its boolean result is equal to the one specified in the type.
- michaelsbradley 12y agoSounds like you are interested in applications of temporal logic for formal verification in software development, which is an area of active research. Prof. David Harel works in that field: http://www.wisdom.weizmann.ac.il/~harel/papers.html http://www.wisdom.weizmann.ac.il/~harel/papers.html Do an in-page search for terms like temporal, behavioral, scenario, LSC, live sequence. By the way, I'm no expert but am interested in similar applications.
- pron 12y agoI'm actually about to integrate some aspects of behavioral programming in a concurrency library I'm maintaining. I also vaguely recall taking a class with Prof. Harel many years ago...
- pseudonom- 12y agoIt's not exactly what you're asking for but Ur/Web puts an expressive type system to some slightly unusual ends: http://www.impredicative.com/ur/ http://www.impredicative.com/ur/.
- pron 12y agoOh, nice! Indeed I'm not sure that's what I want, but this seems like the first statically-typed FP language I like. I especially like how you can program the type level with constructs similar to the program level.
- kyllo 12y agoWhoa, this is pretty horrifying: app code, queries and markup all mixed together, like typed-checked PHP. I know this is just a demo but "separation of concerns" does not appear to have been a concern. fun list () = rows <- queryX (SELECT * FROM tab AS T) (fn (fs : {T : $([Id = int] ++ map fst M.cols)}) => <xml> <tr> <td>{[fs.T.Id]}</td> {@mapX2 [fst] [colMeta] [tr] (fn [nm :: Name] [t ::_] [rest ::_] [[nm] ~ rest] v col => <xml> <td>{col.Show v}</td> </xml>) M.fl (fs.T -- #Id) M.cols} <td> <a link={upd fs.T.Id}>[Update]</a> <a link={confirm fs.T.Id}>[Delete]</a> </td> </tr> </xml>);
- foobarbaz1234 12y agoKeep also in mind, that it is ultra-fast (http://www.techempower.com/benchmarks/#section=data-r9&hw=peak&test=json http://www.techempower.com/benchmarks/#section=data-r9&hw=pe...).
- berbc 12y agoGiven formal semantics of your programming language and some time, I think you can use Agda to prove interesting properties about correct programs you write in that language. Semantics, the behaviour of objects such as sockets, can be encoded in types the theorem prover can understand. It can look like this for a basic imperative language: https://github.com/Twey/imp-agda/blob/master/IMP/Semantics/Operational.agda https://github.com/Twey/imp-agda/blob/master/IMP/Semantics/O.... You can then define the property you are interested in and get your proof by combining these types together. This is often tedious but can be automated to some extent and has already led to significant achievements. See http://sel4.systems http://sel4.systems, a proven kernel, done with Isabelle, a tool similar to Agda. Maybe you are looking for a language with a type system that will force you to write your program in a safe way regarding sockets and the like. This can also be achieved with static analysis, another way of automatically proving properties about programs. I do not know of any for distributed programs but it is probably possible. I would say this is still a research topic as such programs are still so hard to get right.
- deleted 12y ago[deleted]
- solomatov 12y ago> Languages that use types for elaborate proofs always seem to me like they only prove the most uninteresting properties of programs, namely the parts that deal with data transformations. You can proof almost anything in agda. Even the most complicated mathematical theorems. >What I'm most interested in is proofs that, say, in a concurrent environment, a function that closes a socket will never be called as long as there are pending tasks to write to the socket. Or, because I write concurrent data structures, I'm interested to prove that a certain function will eventually release all locks it acquires. Are there any such languages? You can do this in agda, however, you need to specify semantics of the language you use.
- rspeer 12y ago>You can proof almost anything in agda. Even the most complicated mathematical theorems. And I think that's the thing that makes Agda interesting. If you limit Agda to proving things about computer programs, it doesn't sound that special. People are using Agda to prove things about, for example, topology.
- chriswarbo 12y ago> Languages that use types for elaborate proofs always seem to me like they only prove the most uninteresting properties of programs, namely the parts that deal with data transformations. > At the end of the day, programs are written for their side effects The reason for such a focus on data transformation is that it's very easy to do in these purely functional languages (Agda included). It's so easy, in fact, that "other" things, like side effects, event handling, etc. are represented as data transformations. This is most obvious in Haskell, since laziness decouples definition from computation; eg. making it trivial to represent event streams as infinite lists. > What I'm most interested in is proofs that, say, in a concurrent environment, a function that closes a socket will never be called as long as there are pending tasks to write to the socket. The usual approach is to define a datatype of operations you might want to perform (eg. `Write String`, `Read Length`, etc.). Next you define a datatype which can combine these operations together in ways you may want (eg. something like a rose tree, if you want threads firing off threads). This forms an "embedded domain-specific language". We then write a bunch of helper functions for manipulating these datastructures (eg. a "combinator library"), then we use these to write down what we actually want as a combination of operations. Next we write an interpreter function which opens a socket, performs all of the operations in the tree (possibly in multiple threads), waits for them to finish then closes the socket. > Or, because I write concurrent data structures, I'm interested to prove that a certain function will eventually release all locks it acquires. Are there any such languages? You can do the same thing as with the socket example, except you can strengthen the type of your program (operation-combining) datastructure to enforce that locks are released. As a simplified example, we can force a serial computation to release locks by only allowing AQUIRE and RELEASE to be inserted together: data Op = Foo | Bar | Aquire ID | Release ID data SafeOp = SFoo | SBar data Program : Type where NoOp : Program -- Empty Program WithLock : Program -> Program -- Add lock ops to a Program PrefixOp : SafeOp -> Program -> Program -- Add a non-lock Op to a Program Interleave : Program -> Program -> Program -- Combine two Programs -- Part of the interpreter, not exposed to the world progToOps : Program -> [Op] progToOps NoOp = [] progToOps (WithLock id p) = [Aquire id] ++ progToOps p ++ [Release id] progToOps (PrefixOp SFoo p) = [Foo] ++ progToOps p progToOps (PrefixOp SBar p) = [Bar] ++ progToOps p progToOps (Interleave p1 p2) = interleave (progToOps p1) (progToOps p2) interleave [] ys = ys interleave (x:xs) ys = [x] ++ interleave ys xs Notice that progToOps can never output a list containing Aquire without also containing a Release with the same ID. Also notice that we can define arbitrary combinations of the other ops: [] is NoOp [Foo, Bar] is PrefixOp SFoo (PrefixOp SBar NoOp) [Foo, Aquire A, Bar, Aquire B, Release A, Foo, Release B] is Interleave (PrefixOp SFoo (PrefixOp SBar NoOp)) (Interleave (WithLock A NoOp) (WithLock B (PrefixOp SFoo NoOp))) Of course these datastructures would be build up by helper functions instead of by hand, would be tree-like for concurrency, would probably provide guarantees per sub-tree, would allow arbitrary functions (of some suitable type) in place of Foo, Bar, etc.
- platz 12y agoHere Idris uses its effect system to verify correct usage of a protocol between a client and a server http://www.youtube.com/watch?v=vkIlW797JN8&t=53m35s http://www.youtube.com/watch?v=vkIlW797JN8&t=53m35s
- dom96 12y agoYou may interested in Nim (http://nim-lang.org/ http://nim-lang.org/). A practical programming language with an effect system.
- sklogic 12y agoYou'd be surprised how many different things can be represented as "compilers" (i.e., as sequences of transforms of some languages). Starting from the relatively obvious things like computer algebra systems, CADs, CAE, and going into unexpected areas like even CRUD and computer games. tl;dr: side effects are overrated.
- szabba 12y agoCould you expand upon this?
- sklogic 12y agoSure. Take a look at all the mathematical theories and models out there. They're all languages, and solving problems within a framework of any given mathematical theory is pretty similar to a process of compilation - a source language should be transformed into another language in which the solution can be "executed". Let's take CAD as an example. We've got a source language: a constructive solid geometry, for simplicity. Pretty much everything a CAD does boils down to various transforms of this language - into an optimised octree for rendering purposes, into G-code slices for production, into, say, SVG for blueprints, etc. CRUD stuff boils down to transforms between different semantic domains - a relational structure at one end and workflow graphs and document trees on another. It's really hard to come up with any practically important problem domain which would not benefit from being represented in terms of languages and transforms.