doc-src/Codegen/Thy/Refinement.thy
changeset 39683 f75a01ee6c41
parent 39664 0afaf89ab591
child 39745 3aa2bc9c5478
equal deleted inserted replaced
39682:066e2d4d0de8 39683:f75a01ee6c41
    29 text {*
    29 text {*
    30   \noindent The runtime of the corresponding code grows exponential due
    30   \noindent The runtime of the corresponding code grows exponential due
    31   to two recursive calls:
    31   to two recursive calls:
    32 *}
    32 *}
    33 
    33 
    34 text %quote {*
    34 text %quote %typewriter {*
    35   \begin{typewriter}
    35   @{code_stmts fib (consts) fib (Haskell)}
    36     @{code_stmts fib (consts) fib (Haskell)}
       
    37   \end{typewriter}
       
    38 *}
    36 *}
    39 
    37 
    40 text {*
    38 text {*
    41   \noindent A more efficient implementation would use dynamic
    39   \noindent A more efficient implementation would use dynamic
    42   programming, e.g.~sharing of common intermediate results between
    40   programming, e.g.~sharing of common intermediate results between
    69 
    67 
    70 text {*
    68 text {*
    71   \noindent The resulting code shows only linear growth of runtime:
    69   \noindent The resulting code shows only linear growth of runtime:
    72 *}
    70 *}
    73 
    71 
    74 text %quote {*
    72 text %quote %typewriter {*
    75   \begin{typewriter}
    73   @{code_stmts fib (consts) fib fib_step (Haskell)}
    76     @{code_stmts fib (consts) fib fib_step (Haskell)}
       
    77   \end{typewriter}
       
    78 *}
    74 *}
    79 
    75 
    80 
    76 
    81 subsection {* Datatype refinement *}
    77 subsection {* Datatype refinement *}
    82 
    78 
   159 
   155 
   160 text {*
   156 text {*
   161   \noindent The resulting code looks as expected:
   157   \noindent The resulting code looks as expected:
   162 *}
   158 *}
   163 
   159 
   164 text %quote {*
   160 text %quote %typewriter {*
   165   \begin{typewriter}
   161   @{code_stmts empty enqueue dequeue (SML)}
   166     @{code_stmts empty enqueue dequeue (SML)}
       
   167   \end{typewriter}
       
   168 *}
   162 *}
   169 
   163 
   170 text {*
   164 text {*
   171   The same techniques can also be applied to types which are not
   165   The same techniques can also be applied to types which are not
   172   specified as datatypes, e.g.~type @{typ int} is originally specified
   166   specified as datatypes, e.g.~type @{typ int} is originally specified
   257 
   251 
   258 text {*
   252 text {*
   259   \noindent Then the corresponding code is as follows:
   253   \noindent Then the corresponding code is as follows:
   260 *}
   254 *}
   261 
   255 
   262 text %quote {*
   256 text %quote %typewriter {*
   263   \begin{typewriter}
   257   @{code_stmts Dlist.empty Dlist.insert Dlist.remove list_of_dlist (Haskell)}
   264     @{code_stmts Dlist.empty Dlist.insert Dlist.remove list_of_dlist (Haskell)}
       
   265   \end{typewriter}
       
   266 *} (*(types) dlist (consts) dempty dinsert dremove list_of List.member insert remove *)
   258 *} (*(types) dlist (consts) dempty dinsert dremove list_of List.member insert remove *)
   267 
   259 
   268 text {*
   260 text {*
   269   Typical data structures implemented by representations involving
   261   Typical data structures implemented by representations involving
   270   invariants are available in the library, e.g.~theories @{theory
   262   invariants are available in the library, e.g.~theories @{theory