# HG changeset patch
# User Adam Chlipala <adamc@hcoop.net>
# Date 1220283027 14400
# Node ID d8363f2a3befb83b0837ff1bfdf408fc491014ad
# Parent  c2e8e9c206434f5a6182308475d4f4647e0ba18d
Target language and translation

diff -r c2e8e9c20643 -r d8363f2a3bef book/src/StackMachine.v
--- a/book/src/StackMachine.v	Mon Sep 01 11:18:58 2008 -0400
+++ b/book/src/StackMachine.v	Mon Sep 01 11:30:27 2008 -0400
@@ -92,6 +92,8 @@
 
 (** ** Target language *)
 
+(** We will compile our source programs onto a simple stack machine, whose syntax is: *)
+
 Inductive instr : Set :=
 | IConst : nat -> instr
 | IBinop : binop -> instr.
@@ -99,6 +101,10 @@
 Definition prog := list instr.
 Definition stack := list nat.
 
+(** An instruction either pushes a constant onto the stack or pops two arguments, applies a binary operator to them, and pushes the result onto the stack.  A program is a list of instructions, and a stack is a list of natural numbers.
+
+We can give instructions meanings as functions from stacks to optional stacks, where running an instruction results in [None] in case of a stack underflow and results in [Some s'] when the result of execution is the new stack [s'].  [::] is the "list cons" operator from the Coq standard library. *)
+
 Definition instrDenote (i : instr) (s : stack) : option stack :=
   match i with
     | IConst n => Some (n :: s)
@@ -109,6 +115,8 @@
       end
   end.
 
+(** With [instrDenote] defined, it is easy to define a function [progDenote], which iterates application of [instrDenote] through a whole program. *)
+
 Fixpoint progDenote (p : prog) (s : stack) {struct p} : option stack :=
   match p with
     | nil => Some s
@@ -119,9 +127,13 @@
       end
   end.
 
+(** There is one interesting difference compared to our previous example of a [Fixpoint].  This recursive function takes two arguments, [p] and [s].  It is critical for the soundness of Coq that every program terminate, so a shallow syntactic termination check is imposed on every recursive function definition.  One of the function parameters must be designated to decrease monotonically across recursive calls.  That is, every recursive call must use a version of that argument that has been pulled out of the current argument by some number of [match] expressions.  [expDenote] has only one argument, so we did not need to specify which of its arguments decreases.  For [progDenote], we resolve the ambiguity by writing [{struct p}] to indicate that argument [p] decreases structurally. *)
+
 
 (** ** Translation *)
 
+(** Our compiler itself is now unsurprising.  [++] is the list concatenation operator from the Coq standard library. *)
+
 Fixpoint compile (e : exp) : prog :=
   match e with
     | Const n => IConst n :: nil