StackOverflow exception in my F# code

Question

I am hunting for a particular method in a group of assemblies. in order to find my method, I have written this code

module MethodNameExtractor

open System
open System.IO
open System.Reflection

let ListMethodsInAssembly (input : AssemblyName) =   
  try
    let appd = AppDomain.CreateDomain("temp")
    try    
      let assm = Assembly.Load(input)
      assm.GetTypes() 
      |> Array.toSeq
      |> Seq.fold (fun accm ty -> Seq.append accm (ty.GetMethods() |> Array.toSeq)) Seq.empty
      |> Seq.filter (fun x -> x.Name <> "GetType" && x.Name <> "ToString" && x.Name <> "GetHashCode" && x.Name <> "GetType") 
    finally
      AppDomain.Unload(appd)
  with
  | :? System.Exception -> Seq.empty

let ListAllDlls = 
  let rec expandDir (parent : DirectoryInfo) accm =    
    let files = parent.GetFiles() |>  Array.toSeq |> Seq.map (fun f -> try Some(AssemblyName.GetAssemblyName f.FullName) with | :? System.Exception -> None)
    let accm = Seq.append files accm
    let subDirs = parent.GetDirectories() |> Array.toSeq
    Seq.fold (fun accm d -> expandDir d accm) accm subDirs

  let basePath = "c:\\Windows\\Microsoft.NET\\assembly\\"
  let loc = ["GAC_64"; "GAC_MSIL";] |> List.toSeq  
  Seq.fold (fun acc l ->
      let path = basePath + l
      expandDir (new DirectoryInfo(path)) acc
    ) 
    Seq.empty
    loc


[<EntryPoint>]
let main args =   
  ListAllDlls 
  |> Seq.fold (
      fun accm x -> 
        match x with 
        | Some(a) -> Seq.append accm (ListMethodsInAssembly a)
        | None -> accm
    ) Seq.empty  
  |> Seq.iter (fun x -> printfn "%s" x.Name)
  0

My hope was that since I am using Sequences and Tail Recursion.... I should not be consuming much memory and if I could leave my code running long enough, I could get a list of methods in all the assemblies.

My code is pretty straight forward... get a list of DLLs in all the directories and subdirectories.

Load DLL and get Types... and then from Types get all public methods...

But the code processes approx 2 million records and then gets StackOverflow Exception.

I am already using Tail recursion and Sequence... How can I further improve this code?

Answer 1

There are a few problems with your code:

• Your combination of Seq.fold, Seq.append and Seq.empty is a poor implementation of Seq.collect or yield! in sequence expression.
• You don't need options here, just skip generation in sequence expression or use Seq.choose.
• You don't need Array.toSeq or List.toSeq when you apply functions on sequences to lists/arrays.
  • try ... with | :? System.Exception can be shortened to try ... with _

Your expandDir function isn't tail-recursive. If you change it to use sequence expression, it is optimized using CPS so StackOverflow doesn't happen.

Here is an improved version. I think it is more readable and probably faster.

let ListMethodsInAssembly (input : AssemblyName) =   
  try
    let appd = AppDomain.CreateDomain("temp")
    try    
      let assm = Assembly.Load(input)
      assm.GetTypes()
      |> Seq.collect (fun ty -> ty.GetMethods())
      |> Seq.filter (fun x -> x.Name <> "GetType" && x.Name <> "ToString" && x.Name <> "GetHashCode" && x.Name <> "GetType") 
    finally
      AppDomain.Unload(appd)
  with _ -> Seq.empty

let ListAllDlls = 
  let rec expandDir (parent : DirectoryInfo) = 
    let getAssemblyNameFromFile (f : FileInfo) =   
        try 
           [ AssemblyName.GetAssemblyName f.FullName ]
        with _ -> []
    seq {
        for f in parent.GetFiles() do
            yield! getAssemblyNameFromFile f
        for subDir in parent.GetDirectories() do
            yield! expandDir subDir
    }

  let basePath = "c:\\Windows\\Microsoft.NET\\assembly\\"
  let loc = ["GAC_64"; "GAC_MSIL";]
  seq {
    for l in loc do  
        let path = basePath + l
        yield! expandDir (DirectoryInfo(path))
  }

[<EntryPoint>]
let main args =   
  ListAllDlls 
  |> Seq.collect ListMethodsInAssembly
  |> Seq.iter (fun x -> printfn "%s" x.Name)
  0

Answer 2

This function is not tail recursive:

let ListAllDlls = 
  let rec expandDir (parent : DirectoryInfo) accm =    
    let files = parent.GetFiles() |>  Array.toSeq |> Seq.map (fun f -> try Some(AssemblyName.GetAssemblyName f.FullName) with | :? System.Exception -> None)
    let accm = Seq.append files accm
    let subDirs = parent.GetDirectories() |> Array.toSeq
    Seq.fold (fun accm d -> expandDir d accm) accm subDirs

Notice that the result of the recursive call to expandDir is used in the calling function (specifically in the function passed to Seq.fold. This prevents tail recursion because the calling stack frame is still in use when the recursive call is made.

This is a tree recursion, so there isn't really a good way to make it tail recursive. See here for information on solving this using continuation passing. The essence of continuation passing is to maintain the list of branches you have yet to take as a lambda.