Mercurial > cpdt > repo

comparison src/Match.v @ 356:50e1d338728c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First draft of full prose for GeneralRec
author Adam Chlipala <adam@chlipala.net>
date Fri, 28 Oct 2011 17:43:53 -0400
parents 23b06f87bd30
children 549d604c3d16
comparison
equal deleted inserted replaced
355:62fdf0993e05 356:50e1d338728c
463 << 463 <<
464 Error: variable n should be bound to a term. 464 Error: variable n should be bound to a term.
465 >> *) 465 >> *)
466 Abort. 466 Abort.
467 467
468 (** What is going wrong here? The answer has to do with the dual status of Ltac as both a purely functional and an imperative programming language. The basic programming language is purely functional, but tactic scripts are one %``%#"#datatype#"#%''% that can be returned by such programs, and Coq will run such a script using an imperative semantics that mutates proof states. Readers familiar with %\index{monads}\index{Haskell}%monadic programming in Haskell%~\cite{monads,IO}% may recognize a similarity. Side-effecting Haskell programs can be thought of as pure programs that return %\emph{%#<i>#the code of programs in an imperative language#</i>#%}%, where some out-of-band mechanism takes responsibility for running these derived programs. In this way, Haskell remains pure, while supporting usual input-output side effects and more. Ltac uses the same basic mechanism, but in a dynamically typed setting. Here the embedded imperative language includes all the tactics we have been applying so far. 468 (** What is going wrong here? The answer has to do with the dual status of Ltac as both a purely functional and an imperative programming language. The basic programming language is purely functional, but tactic scripts are one %``%#"#datatype#"#%''% that can be returned by such programs, and Coq will run such a script using an imperative semantics that mutates proof states. Readers familiar with %\index{monad}\index{Haskell}%monadic programming in Haskell%~\cite{monads,IO}% may recognize a similarity. Side-effecting Haskell programs can be thought of as pure programs that return %\emph{%#<i>#the code of programs in an imperative language#</i>#%}%, where some out-of-band mechanism takes responsibility for running these derived programs. In this way, Haskell remains pure, while supporting usual input-output side effects and more. Ltac uses the same basic mechanism, but in a dynamically typed setting. Here the embedded imperative language includes all the tactics we have been applying so far.
469 469
470 Even basic [idtac] is an embedded imperative program, so we may not automatically mix it with purely functional code. In fact, a semicolon operator alone marks a span of Ltac code as an embedded tactic script. This makes some amount of sense, since pure functional languages have no need for sequencing: since they lack side effects, there is no reason to run an expression and then just throw away its value and move on to another expression. 470 Even basic [idtac] is an embedded imperative program, so we may not automatically mix it with purely functional code. In fact, a semicolon operator alone marks a span of Ltac code as an embedded tactic script. This makes some amount of sense, since pure functional languages have no need for sequencing: since they lack side effects, there is no reason to run an expression and then just throw away its value and move on to another expression.
471 471
472 The solution is like in Haskell: we must %``%#"#monadify#"#%''% our pure program to give it access to side effects. The trouble is that the embedded tactic language has no [return] construct. Proof scripts are about proving theorems, not calculating results. We can apply a somewhat awkward workaround that requires translating our program into %\index{continuation-passing style}\emph{%#<i>#continuation-passing style#</i>#%}%, a program structuring idea popular in functional programming. *) 472 The solution is like in Haskell: we must %``%#"#monadify#"#%''% our pure program to give it access to side effects. The trouble is that the embedded tactic language has no [return] construct. Proof scripts are about proving theorems, not calculating results. We can apply a somewhat awkward workaround that requires translating our program into %\index{continuation-passing style}\emph{%#<i>#continuation-passing style#</i>#%}%, a program structuring idea popular in functional programming. *)
473 473