cps/cpstransform/expression.ml

Module Expression



open Base

module List = Extensions.List

module AstVarMap = Ast.Variable.Map

module Rules_Make = Rules.Make

module rec Rules : RULES = Rules_Make(Expression)

and Expression: EXPRESSION = struct

transform ?v exp map kcontext returns a CPS expression obtained from the AST expression exp. map contains a map from AST variables to CPS variables (several AST variables can correspond to the same CPS variables). The CPS expression is "returned" as a CPS (normal) variable var, such that if the CPS expression and the AST expression were both evaluated, var would contain the result of the evaluation of exp.

CPS transformation is written itself in CPS style, so it takes a continuation argument kcontext to which var is returned. kcontext represents the context that will use the result of the transformation.

When a v argument is given, then this v is the var bound to the result of the CPS expression and is returned. This is used when compiling recursive occurrences.


  
let rec transform ?v exp map kcontext =
    
let (exp_,_) = exp in

Only lambda is handled when given an explicit v for now. We could also handle data structures with a pointer indirection, such as injections.


    
assert( v ≡ None ∨ match exp_ with
    
∣ Ast.Expression.Lambda _ → true
    
∣ _ → false);

match exp_ with

2. Base cases. Note that the implementation takes advantage of the higher-order abstract syntax (CPS-style friendly) interface of the Cpsbuild module: often it suffices to pass kcontext as the continuation argument of the Cpsbuild functions.


    
∣ Ast.Expression.Variable(var) → 
      
let v = try AstVarMap.find var map
        
(∗  Should not happen: any unbound variable error should have
been already caught by the type checker.  ∗)
        
with Not_found → Log.Cps_transformation.raise_compiler_error
          
"Unbound variable %s" (Ast.Variable.to_string var) in
      
kcontext v
    
∣ Ast.Expression.Constant(c) → Build.let_constant c kcontext
    
∣ Ast.Expression.External(name, _) → Build.let_external name kcontext
    
∣ Ast.Expression.Injection(j,n,x) →
      
transform x map (fun injectedv →
        
Build.let_inj j n injectedv kcontext)

Casts are just forgotten for now; if the transformation was typed, we would have to change the type too.


    
∣ Ast.Expression.Cast(_,x) → transform x map kcontext

Fold on all elements in the tuple, CPS-style.


    
∣ Ast.Expression.Tuple(l) →
      
let f accu exp k = transform exp map (fun expv → k (expv::accu)) in
      
List.foldk f [ ] l (fun vs →
        
Build.let_tuple (List.rev vs) kcontext)

3. Detection of primitive operations.


    
∣ Ast.Expression.Apply(((Ast.Expression.Constant c),_),
                            
[(Ast.Expression.Tuple([a;b]),_)]) →
      
transform a map (fun av →
        
transform b map (fun bv →
          
let buildf = match c with
            
∣ Constant.Integer_binary_operation(op) →
              
Build.let_integer_binary_operation op
            
∣ Constant.Integer_binary_predicate(pred) →
              
Build.let_integer_binary_predicate pred in
          
buildf av bv kcontext))

end

let transform = Expression.transform