diff options
| -rw-r--r-- | editors/sail2-mode.el | 2 | ||||
| -rw-r--r-- | lib/ocaml_rts/sail_lib.ml | 88 | ||||
| -rw-r--r-- | src/ocaml_backend.ml | 90 | ||||
| -rw-r--r-- | src/rewriter.ml | 41 | ||||
| -rw-r--r-- | src/rewriter.mli | 2 | ||||
| -rw-r--r-- | src/type_check.ml | 22 |
6 files changed, 194 insertions, 51 deletions
diff --git a/editors/sail2-mode.el b/editors/sail2-mode.el index c2f77801..2958af21 100644 --- a/editors/sail2-mode.el +++ b/editors/sail2-mode.el @@ -8,7 +8,7 @@ "else" "match" "in" "return" "register" "forall" "operator" "effect" "overload" "cast" "sizeof" "constraint" "default" "assert" "pure" "infixl" "infixr" "infix" "scattered" "end" "try" "catch" "and" - "throw" "clause" "as")) + "throw" "clause" "as" "repeat" "until" "while" "do")) (defconst sail2-kinds '("Int" "Type" "Order" "inc" "dec" diff --git a/lib/ocaml_rts/sail_lib.ml b/lib/ocaml_rts/sail_lib.ml index a0d6bc5f..88217ddf 100644 --- a/lib/ocaml_rts/sail_lib.ml +++ b/lib/ocaml_rts/sail_lib.ml @@ -2,12 +2,26 @@ open Big_int type 'a return = { return : 'b . 'a -> 'b } +let trace_depth = ref 0 +let random = ref false + let with_return (type t) (f : _ -> t) = let module M = struct exception Return of t end in - let return = { return = (fun x -> raise (M.Return x)); } in - try f return with M.Return x -> x + let return = { return = (fun x -> decr trace_depth; raise (M.Return x)); } in + try + let result = f return in + decr trace_depth; + result + with M.Return x -> x + +let trace str = + if !trace_depth < 0 then trace_depth := 0 else (); + prerr_endline (String.make (!trace_depth * 2) ' ' ^ str) + +let trace_call str = + trace str; incr trace_depth type bit = B0 | B1 @@ -19,6 +33,11 @@ let or_bit = function | B0, B0 -> B0 | _, _ -> B1 +let xor_bit = function + | B1, B0 -> B1 + | B0, B1 -> B1 + | _, _ -> B0 + let and_vec (xs, ys) = assert (List.length xs = List.length ys); List.map2 (fun x y -> and_bit (x, y)) xs ys @@ -31,10 +50,19 @@ let or_vec (xs, ys) = let or_bool (b1, b2) = b1 || b2 +let xor_vec (xs, ys) = + assert (List.length xs = List.length ys); + List.map2 (fun x y -> xor_bit (x, y)) xs ys + +let xor_bool (b1, b2) = (b1 || b2) && (b1 != b2) + let undefined_bit () = - if Random.bool () then B0 else B1 + if !random + then (if Random.bool () then B0 else B1) + else B0 -let undefined_bool () = Random.bool () +let undefined_bool () = + if !random then Random.bool () else false let rec undefined_vector (start_index, len, item) = if eq_big_int len zero_big_int @@ -46,10 +74,16 @@ let undefined_string () = "" let undefined_unit () = () let undefined_int () = - big_int_of_int (Random.int 0xFFFF) + if !random then big_int_of_int (Random.int 0xFFFF) else zero_big_int + +let undefined_nat () = zero_big_int + +let undefined_range (lo, hi) = lo let internal_pick list = - List.nth list (Random.int (List.length list)) + if !random + then List.nth list (Random.int (List.length list)) + else List.nth list 0 let eq_int (n, m) = eq_big_int n m @@ -70,6 +104,11 @@ let subrange (list, n, m) = let m = int_of_big_int m in List.rev (take (n - (m - 1)) (drop m (List.rev list))) +let slice (list, n, m) = + let n = int_of_big_int n in + let m = int_of_big_int m in + List.rev (take m (drop n (List.rev list))) + let eq_list (xs, ys) = List.for_all2 (fun x y -> x == y) xs ys let access (xs, n) = List.nth (List.rev xs) (int_of_big_int n) @@ -319,3 +358,40 @@ let debug (str1, n, str2, v) = prerr_endline (str1 ^ string_of_big_int n ^ str2 let eq_string (str1, str2) = String.compare str1 str2 == 0 let lt_int (x, y) = lt_big_int x y + +let set_slice (out_len, slice_len, out, n, slice) = + update_subrange(out, n, sub_big_int n (big_int_of_int (List.length slice - 1)), slice) + +let set_slice_int (_, _, _, _) = assert false + +let eq_real (x, y) = Num.eq_num x y +let lt_real (x, y) = Num.lt_num x y +let gt_real (x, y) = Num.gt_num x y +let lteq_real (x, y) = Num.le_num x y +let gteq_real (x, y) = Num.ge_num x y + +let round_down x = Num.big_int_of_num (Num.floor_num x) +let round_up x = Num.big_int_of_num (Num.ceiling_num x) +let quotient_real (x, y) = Num.div_num x y +let mult_real (x, y) = Num.mult_num x y +let real_power (x, y) = Num.power_num x (Num.num_of_big_int y) +let add_real (x, y) = Num.add_num x y +let sub_real (x, y) = Num.sub_num x y + +let lt (x, y) = lt_big_int x y +let gt (x, y) = gt_big_int x y +let lteq (x, y) = le_big_int x y +let gteq (x, y) = gt_big_int x y + +let pow2 x = power_big_int_positive_int x 2 + +let max_int (x, y) = max_big_int x y +let min_int (x, y) = min_big_int x y + +let undefined_real () = Num.num_of_int 0 + +(* Not a very good sqrt implementation *) +let sqrt_real x = Num.num_of_string (string_of_float (sqrt (Num.float_of_num x))) + +let print_int (str, x) = + prerr_endline (str ^ string_of_big_int x) diff --git a/src/ocaml_backend.ml b/src/ocaml_backend.ml index dc8c056e..74fb6e4c 100644 --- a/src/ocaml_backend.ml +++ b/src/ocaml_backend.ml @@ -5,12 +5,14 @@ open Type_check type ctx = { register_inits : tannot exp list; - externs : id Bindings.t + externs : id Bindings.t; + val_specs : typ Bindings.t } let empty_ctx = { register_inits = []; - externs = Bindings.empty + externs = Bindings.empty; + val_specs = Bindings.empty } let zchar c = @@ -47,7 +49,10 @@ let ocaml_typ_id ctx = function | id when Id.compare id (mk_id "list") = 0 -> string "list" | id when Id.compare id (mk_id "bit") = 0 -> string "bit" | id when Id.compare id (mk_id "int") = 0 -> string "big_int" + | id when Id.compare id (mk_id "nat") = 0 -> string "big_int" | id when Id.compare id (mk_id "bool") = 0 -> string "bool" + | id when Id.compare id (mk_id "unit") = 0 -> string "unit" + | id when Id.compare id (mk_id "real") = 0 -> string "Num.num" | id -> zencode ctx id let rec ocaml_typ ctx (Typ_aux (typ_aux, _)) = @@ -84,6 +89,7 @@ let ocaml_lit (L_aux (lit_aux, _)) = | L_num n -> parens (string "big_int_of_int" ^^ space ^^ string (string_of_int n)) | L_undef -> failwith "undefined should have been re-written prior to ocaml backend" | L_string str -> dquotes (string (String.escaped str)) + | L_real str -> parens (string "Num.num_of_string" ^^ space ^^ dquotes (string (String.escaped str))) | _ -> string "LIT" let rec ocaml_pat ctx (P_aux (pat_aux, _) as pat) = @@ -110,10 +116,10 @@ let rec ocaml_exp ctx (E_aux (exp_aux, _) as exp) = | E_app (f, [x]) when Env.is_union_constructor f (env_of exp) -> zencode_upper ctx f ^^ space ^^ ocaml_atomic_exp ctx x | E_app (f, [x]) -> zencode ctx f ^^ space ^^ ocaml_atomic_exp ctx x | E_app (f, xs) when Env.is_union_constructor f (env_of exp) -> - zencode_upper ctx f ^^ space ^^ parens (separate_map (comma ^^ space) (ocaml_exp ctx) xs) + zencode_upper ctx f ^^ space ^^ parens (separate_map (comma ^^ space) (ocaml_atomic_exp ctx) xs) | E_app (f, xs) -> - zencode ctx f ^^ space ^^ parens (separate_map (comma ^^ space) (ocaml_exp ctx) xs) - | E_vector_subrange (exp1, exp2, exp3) -> string "subrange" ^^ space ^^ parens (separate_map (comma ^^ space) (ocaml_exp ctx) [exp1; exp2; exp3]) + zencode ctx f ^^ space ^^ parens (separate_map (comma ^^ space) (ocaml_atomic_exp ctx) xs) + | E_vector_subrange (exp1, exp2, exp3) -> string "subrange" ^^ space ^^ parens (separate_map (comma ^^ space) (ocaml_atomic_exp ctx) [exp1; exp2; exp3]) | E_return exp -> separate space [string "r.return"; ocaml_atomic_exp ctx exp] | E_assert (exp, _) -> separate space [string "assert"; ocaml_atomic_exp ctx exp] | E_cast (_, exp) -> ocaml_exp ctx exp @@ -140,8 +146,19 @@ let rec ocaml_exp ctx (E_aux (exp_aux, _) as exp) = ^/^ ocaml_exp ctx exp | E_internal_let (lexp, exp1, exp2) -> separate space [string "let"; ocaml_atomic_lexp ctx lexp; - equals; string "ref"; ocaml_atomic_exp ctx exp1; string "in"] + equals; string "ref"; parens (ocaml_atomic_exp ctx exp1 ^^ space ^^ colon ^^ space ^^ ocaml_typ ctx (Rewriter.simple_typ (typ_of exp1))); string "in"] ^/^ ocaml_exp ctx exp2 + | E_loop (Until, cond, body) -> + let loop_body = + (ocaml_atomic_exp ctx body ^^ semi) + ^/^ + separate space [string "if"; ocaml_atomic_exp ctx cond; + string "then loop ()"; + string "else ()"] + in + (string "let rec loop () =" ^//^ loop_body) + ^/^ string "in" + ^/^ string "loop ()" | E_loop (While, cond, body) -> let loop_body = separate space [string "if"; ocaml_atomic_exp ctx cond; @@ -152,11 +169,22 @@ let rec ocaml_exp ctx (E_aux (exp_aux, _) as exp) = ^/^ string "in" ^/^ string "loop ()" | E_lit _ | E_list _ | E_id _ | E_tuple _ -> ocaml_atomic_exp ctx exp + | E_for (id, exp_from, exp_to, exp_step, _, exp_body) -> + let loop_var = separate space [string "let"; zencode ctx id; equals; string "ref"; ocaml_atomic_exp ctx exp_from; string "in"] in + let loop_mod = string "add_big_int" ^^ space ^^ zencode ctx id ^^ space ^^ ocaml_atomic_exp ctx exp_step in + let loop_body = + separate space [string "if"; zencode ctx id; string "<="; ocaml_atomic_exp ctx exp_to] + ^/^ separate space [string "then"; + parens (ocaml_atomic_exp ctx exp_body ^^ semi ^^ space ^^ string "loop" ^^ space ^^ parens loop_mod)] + ^/^ string "else ()" + in + (string ("let rec loop " ^ zencode_string (string_of_id id) ^ " =") ^//^ loop_body) + ^/^ string "in" + ^/^ (string "loop" ^^ space ^^ ocaml_atomic_exp ctx exp_from) | _ -> string ("EXP(" ^ string_of_exp exp ^ ")") and ocaml_letbind ctx (LB_aux (lb_aux, _)) = match lb_aux with | LB_val (pat, exp) -> separate space [ocaml_pat ctx pat; equals; ocaml_atomic_exp ctx exp] - | _ -> failwith "Ocaml: Explicit letbind found" and ocaml_pexps ctx = function | [pexp] -> ocaml_pexp ctx pexp | pexp :: pexps -> ocaml_pexp ctx pexp ^/^ ocaml_pexps ctx pexps @@ -166,7 +194,7 @@ and ocaml_pexp ctx = function separate space [bar; ocaml_pat ctx pat; string "->"] ^//^ group (ocaml_exp ctx exp) | Pat_aux (Pat_when (pat, wh, exp), _) -> - separate space [bar; ocaml_pat ctx pat; string "when"; ocaml_atomic_exp ctx exp; string "->"] + separate space [bar; ocaml_pat ctx pat; string "when"; ocaml_atomic_exp ctx wh; string "->"] ^//^ group (ocaml_exp ctx exp) and ocaml_block ctx = function | [exp] -> ocaml_exp ctx exp @@ -182,7 +210,8 @@ and ocaml_atomic_exp ctx (E_aux (exp_aux, _) as exp) = match Env.lookup_id id (env_of exp) with | Local (Immutable, _) | Unbound -> zencode ctx id | Enum _ | Union _ -> zencode_upper ctx id - | Register _ | Local (Mutable, _) -> bang ^^ zencode ctx id + | Register _ -> parens (string ("trace \"REG: " ^ string_of_id id ^ "\";") ^^ space ^^ bang ^^ zencode ctx id) + | Local (Mutable, _) -> bang ^^ zencode ctx id end | E_list exps -> enclose lbracket rbracket (separate_map (semi ^^ space) (ocaml_exp ctx) exps) | E_tuple exps -> parens (separate_map (comma ^^ space) (ocaml_exp ctx) exps) @@ -234,15 +263,25 @@ let rec ocaml_funcl_matches ctx = function | [clause] -> ocaml_funcl_match ctx clause | (clause :: clauses) -> ocaml_funcl_match ctx clause ^/^ ocaml_funcl_matches ctx clauses +let first_function = ref true + +let function_header () = + if !first_function + then (first_function := false; string "let rec") + else string "and" + let ocaml_funcls ctx = function | [] -> failwith "Ocaml: empty function" | [FCL_aux (FCL_Funcl (id, pat, exp),_)] -> - separate space [string "let rec"; zencode ctx id; ocaml_pat ctx pat; equals; string "with_return (fun r ->"] + let Typ_aux (Typ_fn (typ1, typ2, _), _) = Bindings.find id ctx.val_specs in + let annot_pat = parens (ocaml_pat ctx pat ^^ space ^^ colon ^^ space ^^ ocaml_typ ctx typ1) in + let dbg = string ("trace_call \"Calling: " ^ string_of_id id ^ "\";") in + separate space [function_header (); zencode ctx id; annot_pat; colon; ocaml_typ ctx typ2; equals; dbg; string "with_return (fun r ->"] ^//^ ocaml_exp ctx exp ^^ rparen | funcls -> let id = funcls_id funcls in - separate space [string "let rec"; zencode ctx id; equals; string "function"] + separate space [function_header (); zencode ctx id; equals; string "function"] ^//^ ocaml_funcl_matches ctx funcls let ocaml_fundef ctx (FD_aux (FD_function (_, _, _, funcls), _)) = @@ -303,15 +342,35 @@ let get_externs (Defs defs) = let ocaml_def_end = string ";;" ^^ twice hardline +let nf_group doc = + first_function := true; + group doc + let ocaml_def ctx def = match def with - | DEF_reg_dec ds -> group (ocaml_dec_spec ctx ds) ^^ ocaml_def_end - | DEF_fundef fd -> group (ocaml_fundef ctx fd) ^^ ocaml_def_end - | DEF_type td -> group (ocaml_typedef ctx td) ^^ ocaml_def_end + | DEF_reg_dec ds -> nf_group (ocaml_dec_spec ctx ds) ^^ ocaml_def_end + | DEF_fundef fd -> group (ocaml_fundef ctx fd) ^^ twice hardline + | DEF_type td -> nf_group (ocaml_typedef ctx td) ^^ ocaml_def_end + | DEF_val lb -> nf_group (string "let" ^^ space ^^ ocaml_letbind ctx lb) ^^ ocaml_def_end | _ -> empty +let val_spec_typs (Defs defs) = + let typs = ref (Bindings.empty) in + let val_spec_typ (VS_aux (vs_aux, _)) = + match vs_aux with + | VS_val_spec (TypSchm_aux (TypSchm_ts (_, typ), _), id, _, _) -> typs := Bindings.add id typ !typs + in + let rec vs_typs = function + | DEF_spec vs :: defs -> val_spec_typ vs; vs_typs defs + | _ :: defs -> vs_typs defs + | [] -> [] + in + vs_typs defs; + !typs + let ocaml_defs (Defs defs) = let ctx = { register_inits = get_initialize_registers defs; - externs = get_externs (Defs defs) + externs = get_externs (Defs defs); + val_specs = val_spec_typs (Defs defs) } in let empty_reg_init = @@ -333,6 +392,7 @@ let ocaml_main spec = ^//^ (string "Random.self_init ();" ^/^ string "load_elf ();" ^/^ string "initialize_registers ();" + ^/^ string "Printexc.record_backtrace true;" ^/^ string "zmain ()") ] diff --git a/src/rewriter.ml b/src/rewriter.ml index bcc4e60a..9b3e7635 100644 --- a/src/rewriter.ml +++ b/src/rewriter.ml @@ -2526,6 +2526,26 @@ let rewrite_undefined = let rewrite_exp_undefined = { id_exp_alg with e_aux = (fun (exp, annot) -> rewrite_e_aux (E_aux (exp, annot))) } in rewrite_defs_base { rewriters_base with rewrite_exp = (fun _ -> fold_exp rewrite_exp_undefined) } +let rec simple_typ (Typ_aux (typ_aux, l) as typ) = Typ_aux (simple_typ_aux typ_aux, l) +and simple_typ_aux = function + | Typ_wild -> Typ_wild + | Typ_id id -> Typ_id id + | Typ_app (id, [_; _; _; Typ_arg_aux (Typ_arg_typ typ, l)]) when Id.compare id (mk_id "vector") = 0 -> + Typ_app (mk_id "list", [Typ_arg_aux (Typ_arg_typ (simple_typ typ), l)]) + | Typ_app (id, [_]) when Id.compare id (mk_id "atom") = 0 -> + Typ_id (mk_id "int") + | Typ_app (id, [_; _]) when Id.compare id (mk_id "range") = 0 -> + Typ_id (mk_id "int") + | Typ_app (id, args) -> Typ_app (id, List.concat (List.map simple_typ_arg args)) + | Typ_fn (typ1, typ2, effs) -> Typ_fn (simple_typ typ1, simple_typ typ2, effs) + | Typ_tup typs -> Typ_tup (List.map simple_typ typs) + | Typ_exist (_, _, Typ_aux (typ, l)) -> simple_typ_aux typ + | typ_aux -> typ_aux +and simple_typ_arg (Typ_arg_aux (typ_arg_aux, l)) = + match typ_arg_aux with + | Typ_arg_typ typ -> [Typ_arg_aux (Typ_arg_typ (simple_typ typ), l)] + | _ -> [] + (* This pass aims to remove all the Num quantifiers from the specification. *) let rewrite_simple_types (Defs defs) = let is_simple = function @@ -2537,26 +2557,6 @@ let rewrite_simple_types (Defs defs) = | TypQ_no_forall -> TypQ_aux (TypQ_no_forall, annot) | TypQ_tq quants -> TypQ_aux (TypQ_tq (List.filter (fun q -> is_simple q) quants), annot) in - let rec simple_typ (Typ_aux (typ_aux, l) as typ) = Typ_aux (simple_typ_aux typ_aux, l) - and simple_typ_aux = function - | Typ_wild -> Typ_wild - | Typ_id id -> Typ_id id - | Typ_app (id, [_; _; _; Typ_arg_aux (Typ_arg_typ typ, l)]) when Id.compare id (mk_id "vector") = 0 -> - Typ_app (mk_id "list", [Typ_arg_aux (Typ_arg_typ (simple_typ typ), l)]) - | Typ_app (id, [_]) when Id.compare id (mk_id "atom") = 0 -> - Typ_id (mk_id "int") - | Typ_app (id, [_; _]) when Id.compare id (mk_id "range") = 0 -> - Typ_id (mk_id "int") - | Typ_app (id, args) -> Typ_app (id, List.concat (List.map simple_typ_arg args)) - | Typ_fn (typ1, typ2, effs) -> Typ_fn (simple_typ typ1, simple_typ typ2, effs) - | Typ_tup typs -> Typ_tup (List.map simple_typ typs) - | Typ_exist (_, _, Typ_aux (typ, l)) -> simple_typ_aux typ - | typ_aux -> typ_aux - and simple_typ_arg (Typ_arg_aux (typ_arg_aux, l)) = - match typ_arg_aux with - | Typ_arg_typ typ -> [Typ_arg_aux (Typ_arg_typ (simple_typ typ), l)] - | _ -> [] - in let simple_typschm (TypSchm_aux (TypSchm_ts (typq, typ), annot)) = TypSchm_aux (TypSchm_ts (simple_typquant typq, simple_typ typ), annot) in @@ -3510,6 +3510,7 @@ let rewrite_defs_lem = [ let rewrite_defs_ocaml = [ (* ("top_sort_defs", top_sort_defs); *) ("undefined", rewrite_undefined); + ("tuple_vector_assignments", rewrite_tuple_vector_assignments); ("tuple_assignments", rewrite_tuple_assignments); ("simple_assignments", rewrite_simple_assignments); ("remove_vector_concat", rewrite_defs_remove_vector_concat); diff --git a/src/rewriter.mli b/src/rewriter.mli index 1c3e8fae..70b8faf5 100644 --- a/src/rewriter.mli +++ b/src/rewriter.mli @@ -59,6 +59,8 @@ val rewrite_defs : tannot defs -> tannot defs val rewrite_defs_ocaml : (string * (tannot defs -> tannot defs)) list (*Perform rewrites to exclude AST nodes not supported for ocaml out*) val rewrite_defs_lem : (string * (tannot defs -> tannot defs)) list (*Perform rewrites to exclude AST nodes not supported for lem out*) +val simple_typ : typ -> typ + (* the type of interpretations of pattern-matching expressions *) type ('a,'pat,'pat_aux,'fpat,'fpat_aux) pat_alg = { p_lit : lit -> 'pat_aux diff --git a/src/type_check.ml b/src/type_check.ml index 3b13abb8..d1621223 100644 --- a/src/type_check.ml +++ b/src/type_check.ml @@ -2027,16 +2027,15 @@ let rec check_exp env (E_aux (exp_aux, (l, ())) as exp : unit exp) (Typ_aux (typ | E_throw exp, _ -> let checked_exp = crule check_exp env exp exc_typ in annot_exp_effect (E_throw checked_exp) typ (mk_effect [BE_escape]) + | E_internal_let (lexp, bind, exp), _ -> + let E_aux (E_assign (lexp, bind), _), env = bind_assignment env lexp bind in + let checked_exp = crule check_exp env exp typ in + annot_exp (E_internal_let (lexp, bind, checked_exp)) typ | E_vector vec, _ -> - begin - let (start, len, ord, vtyp) = destruct_vec_typ l env typ in - let checked_items = List.map (fun i -> crule check_exp env i vtyp) vec in - match nexp_simp len with - | Nexp_aux (Nexp_constant lenc, _) -> - if List.length vec = lenc then annot_exp (E_vector checked_items) typ - else typ_error l "List length didn't match" (* FIXME: improve error message *) - | _ -> typ_error l "Cannot check list constant against non-constant length vector type" - end + let (start, len, ord, vtyp) = destruct_vec_typ l env typ in + let checked_items = List.map (fun i -> crule check_exp env i vtyp) vec in + if prove env (nc_eq (nconstant (List.length vec)) (nexp_simp len)) then annot_exp (E_vector checked_items) typ + else typ_error l "List length didn't match" (* FIXME: improve error message *) | E_lit (L_aux (L_undef, _) as lit), _ -> annot_exp_effect (E_lit lit) typ (mk_effect [BE_undef]) (* This rule allows registers of type t to be passed by name with type register<t>*) @@ -2981,6 +2980,11 @@ and propagate_exp_effect_aux = function let p_lexp = propagate_lexp_effect lexp in let p_exp = propagate_exp_effect exp in E_assign (p_lexp, p_exp), union_effects (effect_of p_exp) (effect_of_lexp p_lexp) + | E_internal_let (lexp, bind, exp) -> + let p_lexp = propagate_lexp_effect lexp in + let p_bind = propagate_exp_effect bind in + let p_exp = propagate_exp_effect exp in + E_internal_let (p_lexp, p_bind, p_exp), union_effects (effect_of_lexp p_lexp) (collect_effects [p_bind; p_exp]) | E_sizeof nexp -> E_sizeof nexp, no_effect | E_constraint nc -> E_constraint nc, no_effect | E_exit exp -> |
