Initial version of generic code generator.
authorberghofe
Fri Aug 31 16:14:34 2001 +0200 (2001-08-31)
changeset 11520ae738c1ee155
parent 11519 0c96830636a1
child 11521 80acc6ce26c3
Initial version of generic code generator.
src/Pure/codegen.ML
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/Pure/codegen.ML	Fri Aug 31 16:14:34 2001 +0200
     1.3 @@ -0,0 +1,418 @@
     1.4 +(*  Title:      Pure/codegen.ML
     1.5 +    ID:         $Id$
     1.6 +    Author:     Stefan Berghofer
     1.7 +    Copyright   2000  TU Muenchen
     1.8 +
     1.9 +Generic code generator
    1.10 +*)
    1.11 +
    1.12 +signature CODEGEN =
    1.13 +sig
    1.14 +  val quiet_mode : bool ref
    1.15 +  val message : string -> unit
    1.16 +
    1.17 +  datatype mixfix =
    1.18 +      Arg
    1.19 +    | Ignore
    1.20 +    | Pretty of Pretty.T
    1.21 +    | Term of term;
    1.22 +
    1.23 +  val add_codegen: string ->
    1.24 +    (theory -> (exn option * string) Graph.T -> string -> bool -> term ->
    1.25 +    ((exn option * string) Graph.T * Pretty.T) option) -> theory -> theory
    1.26 +  val print_codegens: theory -> unit
    1.27 +  val generate_code: theory -> (string * string) list -> string
    1.28 +  val generate_code_i: theory -> (string * term) list -> string
    1.29 +  val assoc_consts: (xstring * string option * mixfix list) list -> theory -> theory
    1.30 +  val assoc_consts_i: (xstring * typ option * mixfix list) list -> theory -> theory
    1.31 +  val assoc_types: (xstring * string) list -> theory -> theory
    1.32 +  val get_assoc_code: theory -> string -> typ -> mixfix list option
    1.33 +  val get_assoc_types: theory -> (string * string) list
    1.34 +  val invoke_codegen: theory -> (exn option * string) Graph.T ->
    1.35 +    string -> bool -> term -> (exn option * string) Graph.T * Pretty.T
    1.36 +  val mk_const_id: Sign.sg -> string -> string
    1.37 +  val mk_type_id: Sign.sg -> string -> string
    1.38 +  val rename_term: term -> term
    1.39 +  val get_defn: theory -> string -> typ -> ((term list * term) * int option) option
    1.40 +  val is_instance: theory -> typ -> typ -> bool
    1.41 +  val parens: Pretty.T -> Pretty.T
    1.42 +  val mk_app: bool -> Pretty.T -> Pretty.T list -> Pretty.T
    1.43 +  val eta_expand: term -> term list -> int -> term
    1.44 +  val parsers: OuterSyntax.parser list
    1.45 +  val setup: (theory -> theory) list
    1.46 +end;
    1.47 +
    1.48 +structure Codegen : CODEGEN =
    1.49 +struct
    1.50 +
    1.51 +val quiet_mode = ref true;
    1.52 +fun message s = if !quiet_mode then () else writeln s;
    1.53 +
    1.54 +(**** Mixfix syntax ****)
    1.55 +
    1.56 +datatype mixfix =
    1.57 +    Arg
    1.58 +  | Ignore
    1.59 +  | Pretty of Pretty.T
    1.60 +  | Term of term;
    1.61 +
    1.62 +fun is_arg Arg = true
    1.63 +  | is_arg Ignore = true
    1.64 +  | is_arg _ = false;
    1.65 +
    1.66 +fun terms_of [] = []
    1.67 +  | terms_of (Term t :: ms) = t :: terms_of ms
    1.68 +  | terms_of (_ :: ms) = terms_of ms;
    1.69 +
    1.70 +val num_args = length o filter is_arg;
    1.71 +
    1.72 +
    1.73 +(**** theory data ****)
    1.74 +
    1.75 +(* data kind 'Pure/codegen' *)
    1.76 +
    1.77 +structure CodegenArgs =
    1.78 +struct
    1.79 +  val name = "Pure/codegen";
    1.80 +  type T =
    1.81 +    {codegens : (string * (theory -> (exn option * string) Graph.T -> string ->
    1.82 +       bool -> term -> ((exn option * string) Graph.T * Pretty.T) option)) list,
    1.83 +     consts : ((string * typ) * mixfix list) list,
    1.84 +     types : (string * string) list};
    1.85 +
    1.86 +  val empty = {codegens = [], consts = [], types = []};
    1.87 +  val copy = I;
    1.88 +  val prep_ext = I;
    1.89 +
    1.90 +  fun merge ({codegens = codegens1, consts = consts1, types = types1},
    1.91 +             {codegens = codegens2, consts = consts2, types = types2}) =
    1.92 +    {codegens = rev (merge_alists (rev codegens1) (rev codegens2)),
    1.93 +     consts   = merge_alists consts1 consts2,
    1.94 +     types    = merge_alists types1 types2};
    1.95 +
    1.96 +  fun print sg (cs:T) = Pretty.writeln
    1.97 +    (Pretty.strs ("code generators:" :: map fst (#codegens cs)));
    1.98 +end;
    1.99 +
   1.100 +structure CodegenData = TheoryDataFun(CodegenArgs);
   1.101 +val print_codegens = CodegenData.print;
   1.102 +
   1.103 +
   1.104 +(**** add new code generator to theory ****)
   1.105 +
   1.106 +fun add_codegen name f thy =
   1.107 +  let val {codegens, consts, types} = CodegenData.get thy
   1.108 +  in (case assoc (codegens, name) of
   1.109 +      None => CodegenData.put {codegens = (name, f)::codegens,
   1.110 +        consts = consts, types = types} thy
   1.111 +    | Some _ => error ("Code generator " ^ name ^ " already declared"))
   1.112 +  end;
   1.113 +
   1.114 +
   1.115 +(**** associate constants with target language code ****)
   1.116 +
   1.117 +fun gen_assoc_consts prep_type xs thy = foldl (fn (thy, (s, tyopt, syn)) =>
   1.118 +  let
   1.119 +    val sg = sign_of thy;
   1.120 +    val {codegens, consts, types} = CodegenData.get thy;
   1.121 +    val cname = Sign.intern_const sg s;
   1.122 +  in
   1.123 +    (case Sign.const_type sg cname of
   1.124 +       Some T =>
   1.125 +         let val T' = (case tyopt of
   1.126 +                None => T
   1.127 +              | Some ty =>
   1.128 +                  let val U = prep_type sg ty
   1.129 +                  in if Type.typ_instance (Sign.tsig_of sg, U, T) then U
   1.130 +                    else error ("Illegal type constraint for constant " ^ cname)
   1.131 +                  end)
   1.132 +         in (case assoc (consts, (cname, T')) of
   1.133 +             None => CodegenData.put {codegens = codegens,
   1.134 +               consts = ((cname, T'), syn) :: consts, types = types} thy
   1.135 +           | Some _ => error ("Constant " ^ cname ^ " already associated with code"))
   1.136 +         end
   1.137 +     | _ => error ("Not a constant: " ^ s))
   1.138 +  end) (thy, xs);
   1.139 +
   1.140 +val assoc_consts_i = gen_assoc_consts (K I);
   1.141 +val assoc_consts = gen_assoc_consts (fn sg => typ_of o read_ctyp sg);
   1.142 +
   1.143 +(**** associate types with target language types ****)
   1.144 +
   1.145 +fun assoc_types xs thy = foldl (fn (thy, (s, syn)) =>
   1.146 +  let
   1.147 +    val {codegens, consts, types} = CodegenData.get thy;
   1.148 +    val tc = Sign.intern_tycon (sign_of thy) s
   1.149 +  in
   1.150 +    (case assoc (types, tc) of
   1.151 +       None => CodegenData.put {codegens = codegens, consts = consts,
   1.152 +         types = (tc, syn) :: types} thy
   1.153 +     | Some _ => error ("Type " ^ tc ^ " already associated with code"))
   1.154 +  end) (thy, xs);
   1.155 +
   1.156 +fun get_assoc_types thy = #types (CodegenData.get thy);
   1.157 +         
   1.158 +
   1.159 +(**** retrieve definition of constant ****)
   1.160 +
   1.161 +fun is_instance thy T1 T2 =
   1.162 +  Type.typ_instance (Sign.tsig_of (sign_of thy), T1, Type.varifyT T2);
   1.163 +
   1.164 +fun get_assoc_code thy s T = apsome snd (find_first (fn ((s', T'), _) =>
   1.165 +  s = s' andalso is_instance thy T T') (#consts (CodegenData.get thy)));
   1.166 +
   1.167 +fun get_defn thy s T =
   1.168 +  let
   1.169 +    val axms = flat (map (Symtab.dest o #axioms o Theory.rep_theory)
   1.170 +      (thy :: Theory.ancestors_of thy));
   1.171 +    val defs = mapfilter (fn (_, t) =>
   1.172 +      (let
   1.173 +         val (lhs, rhs) = Logic.dest_equals t;
   1.174 +         val (c, args) = strip_comb lhs;
   1.175 +         val (s', T') = dest_Const c
   1.176 +       in if s=s' then Some (T', (args, rhs)) else None end) handle TERM _ =>
   1.177 +         None) axms;
   1.178 +    val i = find_index (is_instance thy T o fst) defs
   1.179 +  in
   1.180 +    if i>=0 then Some (snd (nth_elem (i, defs)),
   1.181 +      if length defs = 1 then None else Some i)
   1.182 +    else None
   1.183 +  end;
   1.184 +
   1.185 +
   1.186 +(**** make valid ML identifiers ****)
   1.187 +
   1.188 +fun gen_mk_id kind rename sg s =
   1.189 +  let
   1.190 +    val (xs as x::_) = explode (rename (space_implode "_"
   1.191 +      (NameSpace.unpack (Sign.cond_extern sg kind s))));
   1.192 +    fun check_str [] = ""
   1.193 +      | check_str (x::xs) =
   1.194 +          (if Symbol.is_letter x orelse Symbol.is_digit x orelse x="_" then x
   1.195 +           else "_" ^ string_of_int (ord x)) ^ check_str xs
   1.196 +  in
   1.197 +    (if not (Symbol.is_letter x) then "id" else "") ^ check_str xs
   1.198 +  end;
   1.199 +
   1.200 +val mk_const_id = gen_mk_id Sign.constK I;
   1.201 +val mk_type_id = gen_mk_id Sign.typeK
   1.202 +  (fn s => if s mem ThmDatabase.ml_reserved then s ^ "_type" else s);
   1.203 +
   1.204 +fun rename_term t =
   1.205 +  let
   1.206 +    val names = add_term_names (t, map (fst o fst o dest_Var) (term_vars t));
   1.207 +    val clash = names inter ThmDatabase.ml_reserved;
   1.208 +    val ps = clash ~~ variantlist (clash, names);
   1.209 +
   1.210 +    fun rename (Var ((a, i), T)) = Var ((if_none (assoc (ps, a)) a, i), T)
   1.211 +      | rename (Free (a, T)) = Free (if_none (assoc (ps, a)) a, T)
   1.212 +      | rename (Abs (s, T, t)) = Abs (s, T, rename t)
   1.213 +      | rename (t $ u) = rename t $ rename u
   1.214 +      | rename t = t;
   1.215 +  in
   1.216 +    rename t
   1.217 +  end;
   1.218 +
   1.219 +
   1.220 +(**** invoke suitable code generator for term t ****)
   1.221 +
   1.222 +fun invoke_codegen thy gr dep brack t = (case get_first
   1.223 +   (fn (_, f) => f thy gr dep brack t) (#codegens (CodegenData.get thy)) of
   1.224 +      None => error ("Unable to generate code for term:\n" ^
   1.225 +        Sign.string_of_term (sign_of thy) t ^ "\nrequired by:\n" ^
   1.226 +        commas (Graph.all_succs gr [dep]))
   1.227 +    | Some x => x)
   1.228 +
   1.229 +
   1.230 +(**** code generator for mixfix expressions ****)
   1.231 +
   1.232 +fun parens p = Pretty.block [Pretty.str "(", p, Pretty.str ")"];
   1.233 +
   1.234 +fun pretty_fn [] p = [p]
   1.235 +  | pretty_fn (x::xs) p = Pretty.str ("fn " ^ x ^ " =>") ::
   1.236 +      Pretty.brk 1 :: pretty_fn xs p;
   1.237 +
   1.238 +fun pretty_mixfix [] [] _ = []
   1.239 +  | pretty_mixfix (Arg :: ms) (p :: ps) qs = p :: pretty_mixfix ms ps qs
   1.240 +  | pretty_mixfix (Ignore :: ms) (p :: ps) qs = pretty_mixfix ms ps qs
   1.241 +  | pretty_mixfix (Pretty p :: ms) ps qs = p :: pretty_mixfix ms ps qs
   1.242 +  | pretty_mixfix (Term _ :: ms) ps (q :: qs) = q :: pretty_mixfix ms ps qs;
   1.243 +
   1.244 +
   1.245 +(**** default code generator ****)
   1.246 +
   1.247 +fun eta_expand t ts i =
   1.248 +  let
   1.249 +    val (Ts, _) = strip_type (fastype_of t);
   1.250 +    val j = i - length ts
   1.251 +  in
   1.252 +    foldr (fn (T, t) => Abs ("x", T, t))
   1.253 +      (take (j, Ts), list_comb (t, ts @ map Bound (j-1 downto 0)))
   1.254 +  end;
   1.255 +
   1.256 +fun mk_app _ p [] = p
   1.257 +  | mk_app brack p ps = if brack then
   1.258 +       Pretty.block (Pretty.str "(" ::
   1.259 +         separate (Pretty.brk 1) (p :: ps) @ [Pretty.str ")"])
   1.260 +     else Pretty.block (separate (Pretty.brk 1) (p :: ps));
   1.261 +
   1.262 +fun new_names t xs = variantlist (xs,
   1.263 +  map (fst o fst o dest_Var) (term_vars t) union
   1.264 +  add_term_names (t, ThmDatabase.ml_reserved));
   1.265 +
   1.266 +fun new_name t x = hd (new_names t [x]);
   1.267 +
   1.268 +fun default_codegen thy gr dep brack t =
   1.269 +  let
   1.270 +    val (u, ts) = strip_comb t;
   1.271 +    fun mapcode brack' gr ts = foldl_map
   1.272 +      (fn (gr, t) => invoke_codegen thy gr dep brack' t) (gr, ts)
   1.273 +
   1.274 +  in (case u of
   1.275 +      Var ((s, i), _) =>
   1.276 +        let val (gr', ps) = mapcode true gr ts
   1.277 +        in Some (gr', mk_app brack (Pretty.str (s ^
   1.278 +           (if i=0 then "" else string_of_int i))) ps)
   1.279 +        end
   1.280 +
   1.281 +    | Free (s, _) =>
   1.282 +        let val (gr', ps) = mapcode true gr ts
   1.283 +        in Some (gr', mk_app brack (Pretty.str s) ps) end
   1.284 +
   1.285 +    | Const (s, T) =>
   1.286 +      (case get_assoc_code thy s T of
   1.287 +         Some ms =>
   1.288 +           let val i = num_args ms
   1.289 +           in if length ts < i then
   1.290 +               default_codegen thy gr dep brack (eta_expand u ts i)
   1.291 +             else
   1.292 +               let
   1.293 +                 val ts1 = take (i, ts);
   1.294 +                 val ts2 = drop (i, ts);
   1.295 +                 val (gr1, ps1) = mapcode false gr ts1;
   1.296 +                 val (gr2, ps2) = mapcode true gr1 ts2;
   1.297 +                 val (gr3, ps3) = mapcode false gr2 (terms_of ms);
   1.298 +               in
   1.299 +                 Some (gr3, mk_app brack (Pretty.block (pretty_mixfix ms ps1 ps3)) ps2)
   1.300 +               end
   1.301 +           end
   1.302 +       | None => (case get_defn thy s T of
   1.303 +           None => None
   1.304 +         | Some ((args, rhs), k) =>
   1.305 +             let
   1.306 +               val id = mk_const_id (sign_of thy) s ^ (case k of
   1.307 +                 None => "" | Some i => "_def" ^ string_of_int i);
   1.308 +               val (gr', ps) = mapcode true gr ts;
   1.309 +             in
   1.310 +               Some (Graph.add_edge (id, dep) gr' handle Graph.UNDEF _ =>
   1.311 +                 let
   1.312 +                   val _ = message ("expanding definition of " ^ s);
   1.313 +                   val (Ts, _) = strip_type T;
   1.314 +                   val (args', rhs') =
   1.315 +                     if not (null args) orelse null Ts then (args, rhs) else
   1.316 +                       let val v = Free (new_name rhs "x", hd Ts)
   1.317 +                       in ([v], betapply (rhs, v)) end;
   1.318 +                   val (gr1, p) = invoke_codegen thy (Graph.add_edge (id, dep)
   1.319 +                     (Graph.new_node (id, (None, "")) gr')) id false rhs';
   1.320 +                   val (gr2, xs) = mapcode false gr1 args';
   1.321 +                 in Graph.map_node id (K (None, Pretty.string_of (Pretty.block
   1.322 +                   (Pretty.str (if null args' then "val " else "fun ") ::
   1.323 +                    separate (Pretty.brk 1) (Pretty.str id :: xs) @
   1.324 +                    [Pretty.str " =", Pretty.brk 1, p, Pretty.str ";"])) ^ "\n\n")) gr2
   1.325 +                 end, mk_app brack (Pretty.str id) ps)
   1.326 +             end))
   1.327 +
   1.328 +    | Abs _ =>
   1.329 +      let
   1.330 +        val (bs, Ts) = ListPair.unzip (strip_abs_vars u);
   1.331 +        val t = strip_abs_body u
   1.332 +        val bs' = new_names t bs;
   1.333 +        val (gr1, ps) = mapcode true gr ts;
   1.334 +        val (gr2, p) = invoke_codegen thy gr1 dep false
   1.335 +          (subst_bounds (map Free (rev (bs' ~~ Ts)), t));
   1.336 +      in
   1.337 +        Some (gr2, mk_app brack (Pretty.block (Pretty.str "(" :: pretty_fn bs' p @
   1.338 +          [Pretty.str ")"])) ps)
   1.339 +      end
   1.340 +
   1.341 +    | _ => None)
   1.342 +  end;
   1.343 +
   1.344 +
   1.345 +fun output_code gr xs = implode (map (snd o Graph.get_node gr)
   1.346 +  (rev (Graph.all_preds gr xs)));
   1.347 +
   1.348 +fun gen_generate_code prep_term thy = Pretty.setmp_margin 80 (fn xs =>
   1.349 +  let
   1.350 +    val sg = sign_of thy;
   1.351 +    val gr = Graph.new_node ("<Top>", (None, "")) Graph.empty;
   1.352 +    val (gr', ps) = foldl_map (fn (gr, (s, t)) => apsnd (pair s)
   1.353 +      (invoke_codegen thy gr "<Top>" false t)) (gr, map (apsnd (prep_term sg)) xs)
   1.354 +  in
   1.355 +    "structure Generated =\nstruct\n\n" ^
   1.356 +    output_code gr' ["<Top>"] ^
   1.357 +    space_implode "\n\n" (map (fn (s', p) => Pretty.string_of (Pretty.block
   1.358 +      [Pretty.str ("val " ^ s' ^ " ="), Pretty.brk 1, p, Pretty.str ";"])) ps) ^
   1.359 +    "\n\nend;\n\nopen Generated;\n"
   1.360 +  end);
   1.361 +
   1.362 +val generate_code_i = gen_generate_code (K I);
   1.363 +val generate_code = gen_generate_code
   1.364 +  (fn sg => term_of o read_cterm sg o rpair TypeInfer.logicT);
   1.365 +
   1.366 +fun parse_mixfix rd s =
   1.367 +  (case Scan.finite Symbol.stopper (Scan.repeat
   1.368 +     (   $$ "_" >> K Arg
   1.369 +      || $$ "?" >> K Ignore
   1.370 +      || $$ "/" |-- Scan.repeat ($$ " ") >> (Pretty o Pretty.brk o length)
   1.371 +      || $$ "{" |-- $$ "*" |-- Scan.repeat1
   1.372 +           (   $$ "'" |-- Scan.one Symbol.not_eof
   1.373 +            || Scan.unless ($$ "*" -- $$ "}") (Scan.one Symbol.not_eof)) --|
   1.374 +         $$ "*" --| $$ "}" >> (Term o rd o implode)
   1.375 +      || Scan.repeat1
   1.376 +           (   $$ "'" |-- Scan.one Symbol.not_eof
   1.377 +            || Scan.unless ($$ "_" || $$ "?" || $$ "/" || $$ "{" |-- $$ "*")
   1.378 +                 (Scan.one Symbol.not_eof)) >> (Pretty o Pretty.str o implode)))
   1.379 +       (Symbol.explode s) of
   1.380 +     (p, []) => p
   1.381 +   | _ => error ("Malformed annotation: " ^ quote s));
   1.382 +
   1.383 +structure P = OuterParse;
   1.384 +
   1.385 +val assoc_typeP =
   1.386 +  OuterSyntax.command "types_code"
   1.387 +  "associate types with target language types"
   1.388 +  OuterSyntax.Keyword.thy_decl
   1.389 +    (Scan.repeat1 (P.xname --| P.$$$ "(" -- P.string --| P.$$$ ")") >>
   1.390 +     (Toplevel.theory o assoc_types));
   1.391 +
   1.392 +val assoc_constP =
   1.393 +  OuterSyntax.command "consts_code"
   1.394 +  "associate constants with target language code"
   1.395 +  OuterSyntax.Keyword.thy_decl
   1.396 +    (Scan.repeat1
   1.397 +       (P.xname -- (Scan.option (P.$$$ "::" |-- P.string)) --|
   1.398 +        P.$$$ "(" -- P.string --| P.$$$ ")") >>
   1.399 +     (fn xs => Toplevel.theory (fn thy => assoc_consts
   1.400 +       (map (fn ((name, optype), mfx) => (name, optype, parse_mixfix
   1.401 +         (term_of o read_cterm (sign_of thy) o rpair TypeInfer.logicT) mfx))
   1.402 +           xs) thy)));
   1.403 +
   1.404 +val generate_codeP =
   1.405 +  OuterSyntax.command "generate_code" "generates code for terms"
   1.406 +  OuterSyntax.Keyword.thy_decl
   1.407 +    (Scan.option (P.$$$ "(" |-- P.string --| P.$$$ ")") --
   1.408 +     Scan.repeat1 (P.short_ident --| P.$$$ "=" -- P.string) >>
   1.409 +     (fn (opt_fname, xs) => Toplevel.theory (fn thy =>
   1.410 +        ((case opt_fname of
   1.411 +            None => use_text Context.ml_output false
   1.412 +          | Some fname => File.write (Path.unpack fname))
   1.413 +              (generate_code thy xs); thy))));
   1.414 +
   1.415 +val parsers = [assoc_typeP, assoc_constP, generate_codeP];
   1.416 +
   1.417 +val setup = [CodegenData.init, add_codegen "default" default_codegen];
   1.418 +
   1.419 +end;
   1.420 +
   1.421 +OuterSyntax.add_parsers Codegen.parsers;