src/Doc/Codegen/Refinement.thy
changeset 69660 2bc2a8599369
parent 69597 ff784d5a5bfb
child 69697 4d95261fab5a
equal deleted inserted replaced
69659:07025152dd80 69660:2bc2a8599369
    29 text \<open>
    29 text \<open>
    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 \<close>
    32 \<close>
    33 
    33 
    34 text %quotetypewriter \<open>
    34 text %quote \<open>
    35   @{code_stmts fib (consts) fib (Haskell)}
    35   @{code_stmts fib (consts) fib (Haskell)}
    36 \<close>
    36 \<close>
    37 
    37 
    38 text \<open>
    38 text \<open>
    39   \noindent A more efficient implementation would use dynamic
    39   \noindent A more efficient implementation would use dynamic
    66 
    66 
    67 text \<open>
    67 text \<open>
    68   \noindent The resulting code shows only linear growth of runtime:
    68   \noindent The resulting code shows only linear growth of runtime:
    69 \<close>
    69 \<close>
    70 
    70 
    71 text %quotetypewriter \<open>
    71 text %quote \<open>
    72   @{code_stmts fib (consts) fib fib_step (Haskell)}
    72   @{code_stmts fib (consts) fib fib_step (Haskell)}
    73 \<close>
    73 \<close>
    74 
    74 
    75 
    75 
    76 subsection \<open>Datatype refinement\<close>
    76 subsection \<open>Datatype refinement\<close>
   159 
   159 
   160 text \<open>
   160 text \<open>
   161   \noindent The resulting code looks as expected:
   161   \noindent The resulting code looks as expected:
   162 \<close>
   162 \<close>
   163 
   163 
   164 text %quotetypewriter \<open>
   164 text %quote \<open>
   165   @{code_stmts empty enqueue dequeue Queue case_queue (SML)}
   165   @{code_stmts empty enqueue dequeue Queue case_queue (SML)}
   166 \<close>
   166 \<close>
   167 
   167 
   168 text \<open>
   168 text \<open>
   169   The same techniques can also be applied to types which are not
   169   The same techniques can also be applied to types which are not
   258 
   258 
   259 text \<open>
   259 text \<open>
   260   \noindent Then the corresponding code is as follows:
   260   \noindent Then the corresponding code is as follows:
   261 \<close>
   261 \<close>
   262 
   262 
   263 text %quotetypewriter \<open>
   263 text %quote \<open>
   264   @{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 \<close>
   265 \<close>
   266 
   266 
   267 text \<open>
   267 text \<open>
   268   See further @{cite "Haftmann-Kraus-Kuncar-Nipkow:2013:data_refinement"}
   268   See further @{cite "Haftmann-Kraus-Kuncar-Nipkow:2013:data_refinement"}