Tail call optimization for F# #649

Closed
Jand42 opened this Issue Feb 6, 2017 · 2 comments

Comments

Projects
None yet
2 participants
@Jand42
Member

Jand42 commented Feb 6, 2017

WebSharper 3 had tail call optimization which was not carried over to WebSharper 4 yet due to the common statement-based AST. But it would be easier to include tail call optimization just for the F# path by adapting the WebSharper 3 logic with the change that it is also applied on module/type level let rec definitions.

@cgravill

This comment has been minimized.

Show comment
Hide comment
@cgravill

cgravill Feb 9, 2017

This would be really useful for us. I've been testing some of our modelling tools in WebSharper 4 and a lot works. However, some of the analysis methods immediately stack overflow due to a lack of tail call optimization.

If it's also possible to make the optimization more generally applied that would be amazing, for example, heavily simplified from our code:

(* this form **is not** tail call optimised in WebSharper 3.x *)
let summer = 
    let rec sum acc list = 
        match list with
        | [] -> acc
        | x :: xs -> sum (acc + x) xs
    
    let summed = sum 0 [ 1; 2; 3 ]
    { name = "Calculation"
      answer = summed }

and I have to manually rewrite to this:

(* this form **is** tail call optimised in WebSharper 3.x *)
let summerOptimised =
    let innerSummer list =
        let rec sum acc list = 
            match list with
            | [] -> acc
            | x :: xs -> sum (acc + x) xs

        sum 0 list

    let summed = innerSummer [ 1; 2; 3 ]
    { name = "Calculation"
      answer = summed }

cgravill commented Feb 9, 2017

This would be really useful for us. I've been testing some of our modelling tools in WebSharper 4 and a lot works. However, some of the analysis methods immediately stack overflow due to a lack of tail call optimization.

If it's also possible to make the optimization more generally applied that would be amazing, for example, heavily simplified from our code:

(* this form **is not** tail call optimised in WebSharper 3.x *)
let summer = 
    let rec sum acc list = 
        match list with
        | [] -> acc
        | x :: xs -> sum (acc + x) xs
    
    let summed = sum 0 [ 1; 2; 3 ]
    { name = "Calculation"
      answer = summed }

and I have to manually rewrite to this:

(* this form **is** tail call optimised in WebSharper 3.x *)
let summerOptimised =
    let innerSummer list =
        let rec sum acc list = 
            match list with
            | [] -> acc
            | x :: xs -> sum (acc + x) xs

        sum 0 list

    let summed = innerSummer [ 1; 2; 3 ]
    { name = "Calculation"
      answer = summed }
@Jand42

This comment has been minimized.

Show comment
Hide comment
@Jand42

Jand42 Feb 16, 2017

Member

Transforming tail-recursion to loops:

  • let rec expressions with single or mutual recursion
  • module or class (in default constructor) let rec expressions with single recursive function
  • class static members, calling itself but no other members of the same class annotated with JavaScript (so inlines do not opt-out of optimization)
  • class instance members, calling itself but no other members of the same class annotated with JavaScript and also calling only on the this object

There is some possibilities for improving interplay of tail-recursion and curried/tupled argument optimizations, but runtime tests for this are passing in current state.

Member

Jand42 commented Feb 16, 2017

Transforming tail-recursion to loops:

  • let rec expressions with single or mutual recursion
  • module or class (in default constructor) let rec expressions with single recursive function
  • class static members, calling itself but no other members of the same class annotated with JavaScript (so inlines do not opt-out of optimization)
  • class instance members, calling itself but no other members of the same class annotated with JavaScript and also calling only on the this object

There is some possibilities for improving interplay of tail-recursion and curried/tupled argument optimizations, but runtime tests for this are passing in current state.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment