let rec eval exp_faust dimension_tree input_beam = 




(** val interpret_par : faust_exp -> faust_exp -> beam -> beam, interprets par(e1, e2) with input beam, produces output beam.*)


let interpret_par = fun e1 -> fun e2 -> fun dimension_tree -> fun input_beam ->

        (* dimension information *)
        let n = List.length input_beam in
        let subtree1 = subtree_left dimension_tree in
        let subtree2 = subtree_right dimension_tree in
        let d1 = get_root subtree1 in
        let d2 = get_root subtree2 in

        if n = (fst d1) + (fst d2) then 
        (                
                (* segmentation of input beam *)
                let input_beam1 = sublist input_beam 0 (fst d1) in
                let input_beam2 = sublist input_beam (fst d1) (fst d2) in

                (* evaluate two expressions respectively *)
                let output_beam1 = eval e1 subtree1 input_beam1 in
                let output_beam2 = eval e2 subtree2 input_beam2 in

                (* concat two output beams *)
                if List.length output_beam1 = snd d1 && List.length output_beam2 = snd d2 
                then (output_beam1 @ output_beam2) 
                else raise (Evaluation_Error "Par")
        )
        else raise (Evaluation_Error "Par") in




(** val interpret_seq : faust_exp -> faust_exp -> beam -> beam, interprets seq(e1, e2) with input beam, produces output beam.*)


let interpret_seq = fun e1 -> fun e2 -> fun dimension_tree -> fun input_beam ->

        (* dimension information *)
        let n = List.length input_beam in
        let subtree1 = subtree_left dimension_tree in
        let subtree2 = subtree_right dimension_tree in
        let d1 = get_root subtree1 in
        let d2 = get_root subtree2 in


        if n = fst d1 then
        (
                (* evaluate the first expression *)
                let output_beam1 = eval e1 subtree1 input_beam in

                (* evaluate the second expression *)
                if List.length output_beam1 = fst d2 
                then eval e2 subtree2 output_beam1
                else raise (Evaluation_Error "Seq")
        )
        else raise (Evaluation_Error "Seq") in




(** val interpret_split : faust_exp -> faust_exp -> beam -> beam, interprets split(e1, e2) with input beam, produces output beam.*)


let interpret_split = fun e1 -> fun e2 -> fun dimension_tree -> fun input_beam ->

        (* dimension information *)
        let n = List.length input_beam in
        let subtree1 = subtree_left dimension_tree in
        let subtree2 = subtree_right dimension_tree in
        let d1 = get_root subtree1 in
        let d2 = get_root subtree2 in


        if n = fst d1 then
        (
                (* evaluate the first expression *)
                let output_beam1 = eval e1 subtree1 input_beam in

                (* beam matching *)
                let ref_output_beam1 = ref (beam_add_one_memory output_beam1) in
                let input_beam2 = List.concat 
                    (Array.to_list (Array.make ((fst d2)/(List.length output_beam1)) !ref_output_beam1)) 
                in

                (* evaluate the second expression *)
                if List.length input_beam2 = fst d2
                then eval e2 subtree2 input_beam2
                else raise (Evaluation_Error "Split")
        )
        else raise (Evaluation_Error "Split") in




(** val interpret_merge : faust_exp -> faust_exp -> beam -> beam, interprets merge(e1, e2) with input beam, produces output beam.*)


let interpret_merge = fun e1 -> fun e2 -> fun dimension_tree -> fun input_beam ->

        (* dimension information *)
        let n = List.length input_beam in
        let subtree1 = subtree_left dimension_tree in
        let subtree2 = subtree_right dimension_tree in
        let d1 = get_root subtree1 in
        let d2 = get_root subtree2 in


        if n = fst d1 then
        (
                (* evaluate the first expression *)
                let output_beam1 = eval e1 subtree1 input_beam in

                (* beam matching *)
                let input_beam2 = 
                (
                        let fois = (snd d1)/(fst d2) in
                        let ref_beam = ref (sublist output_beam1 0 (fst d2)) in
                        for i = 1 to fois - 1 do
                                let temp_beam = sublist output_beam1 (i*(fst d2)) (fst d2) in
                                ref_beam := List.map2 signal_add (!ref_beam) temp_beam;
                        done;
                        !ref_beam
                )
                in

                (* evaluate the second expression *)
                if List.length input_beam2 = fst d2
                then eval e2 subtree2 input_beam2
                else raise (Evaluation_Error "Merge")
        )
        else raise (Evaluation_Error "Merge") in




(** val interpret_rec : faust_exp -> faust_exp -> beam -> beam, interprets rec(e1, e2) with input beam, produces output beam.*)


let interpret_rec = fun e1 -> fun e2 -> fun dimension_tree -> fun input_beam ->

        (* dimension information *)
        let subtree1 = subtree_left dimension_tree in
        let subtree2 = subtree_right dimension_tree in
        let d1 = get_root subtree1 in
        let d2 = get_root subtree2 in

        (* estimate stockage size for delay *)
        let delay_int = 1 + delay e2 + delay e1 in

        (* prepare stockage *)
        let memory_hashtbl = Hashtbl.create delay_int in
        let rate_list = ref (Array.to_list (Array.make (snd d1) 0)) in

        

(** val apply_to : 'a -> ('a -> 'b) -> 'b *)


        let apply_to = fun t -> fun f -> f t in

        

(** val get_value_fun_list : (int -> (int list) * (value list)) -> (int -> value) list *)

                
        let get_value_fun_list = fun beam_fun -> 
                let tmp = fun beam_fun -> fun i -> fun t -> 
                        List.nth (snd (beam_fun t)) i in
                List.map (tmp beam_fun) (Array.to_list (Array.init (snd d1) (fun n -> n))) in

        

(** val make_signal : int -> (int -> value) -> signal, combines rate and function. *)


        let make_signal = fun rate -> fun f -> (rate, f) in

        

(** val output_beam_fun : int -> (int list) * (value list), with input : time output: rate list * value list *)


        let rec output_beam_fun = fun t ->

                (* initial value in constrctor "rec '~'" *)
                if t < 0 then
                        let init_rate_list = Array.to_list (Array.make (snd d1) 0) in
                        let value_list = Array.to_list (Array.make (snd d1) Zero) in
                        (init_rate_list, value_list)

                (* check stockage at time t *)
                else if Hashtbl.mem memory_hashtbl t then 
                        (!rate_list, Hashtbl.find memory_hashtbl t)

                (* blocks : "a ~ b", calculate rate list and value list at time t *)
                else         
                        (* mid_output_fun_list : (int -> value) list *)
                        let mid_output_fun_list = get_value_fun_list output_beam_fun in

                        (* b_input_fun_list : (int -> value) list *)
                        let b_input_fun_list = List.map 
                            (fun s -> fun t -> s (t - 1)) 
                            (sublist mid_output_fun_list 0 (fst d2)) in

                        (* b_input_beam : signal list *)
                        let b_input_beam = List.map2 make_signal 
                            (sublist !rate_list 0 (fst d2))
                            b_input_fun_list in

                        (* evaluation of block "b" *)
                        let b_output_beam = (eval e2 subtree2 b_input_beam) in

                        (* evaluation of block "a" *)
                        let a_input_beam = b_output_beam @ input_beam in
                        let mid_output_beam = eval e1 subtree1 a_input_beam in

                        (* calculate rate list and value list at time t *)
                        let mid_output_rate_list = List.map fst mid_output_beam in
                        let mid_output_value_list = List.map (apply_to t) (List.map snd mid_output_beam) in

                        (* update stockage *)
                        let () = (rate_list := mid_output_rate_list) in
                        let () = Hashtbl.add memory_hashtbl t mid_output_value_list in
                        let () = Hashtbl.remove memory_hashtbl (t - delay_int) in
                        (mid_output_rate_list, mid_output_value_list) in

        (* output_beam : signal list *)
        let output_beam = List.map2 make_signal !rate_list (get_value_fun_list output_beam_fun) in
        output_beam in


        

(** Call for previous functions *)


        match exp_faust with
        |Const v -> interpret_const v input_beam
        |Ident s -> interpret_ident s input_beam
        |Par (e1, e2) -> interpret_par e1 e2 dimension_tree input_beam
        |Seq (e1, e2) -> interpret_seq e1 e2 dimension_tree input_beam
        |Split (e1, e2) -> interpret_split e1 e2 dimension_tree input_beam
        |Merge (e1, e2) -> interpret_merge e1 e2 dimension_tree input_beam
        |Rec (e1, e2) -> interpret_rec e1 e2 dimension_tree input_beam