[ASP.NET Web API] Autenticación basada en tokens y líos con el CORS

No era la primera vez que implementaba este tipo de autenticación en un proyecto de ASP.NET Web Api + ASP.NET MVC + OWIN y ya sabía (o al menos creo saber) los retos de trabajar con estos pipelines, digo, líneas como config.SuppressDefaultHostAuthentication(); en el  WebApiConfig hacen su magia, conocí la clase OAuthAuthorizationServerProvider y en su momento dejé en mis favoritos entradas como esta como fuente de consulta. Con el tema de CORS creí que todo estaba resuelto con el uso del atributo EnableCors que hizo esto más sencillo.

La semana pasada este requerimiento surgió de nuevo pero con un componente adicional: El token es solicitado en un cliente desde otro dominio. De entrada parece que nada cambia, pero si que lo hace, o al menos si hay que agregar unas cuantas líneas. Sabía que en mis favoritos aún estaban los enlaces a las fuentes que había usado como referencia en implementaciones anteriores, así que volví a consultar una serie de tutoriales muy, muy completos de este blog. Y por primera vez me percaté que existen dos “enable cors”! (o algo así) uno a nivel del pipeline de OWIN y el que siempre uso en Web API. El que siempre uso, el de Web API, viene en el paquete Microsoft.AspNet.WebApi.Cors y el que no conocía, el de Katana, viene en el paquete Microsoft.Owin.Cors.

¿Qué diferencia tienen WebApi.Cors y Owin.Cors?

No encontré nada en la documentación oficial, pero viendo el nombre, entendiendo algo de OWIN y habiendo usado Katana, se puede suponer que el primero es solo para el Framework Web API y lo que hay en el, es decir, los ApiControllers. El segundo es un middleware que agrega soporte para el resto del pipeline, como el middleware para generar los tokens! Igual apliqué un poco de GOD (google oriented development) y encontré una explicación similar en Stack Overflow.

¿Y cómo se usan los dos?

Lo primero que hice, desde el desconocimiento, fue agregar en el Startup la línea app.UseCors(CorsOptions.AllowAll); y en el momento de probar surgió el primer error, error que rompe la parte que ya funcionaba (mensaje en la consola de Chrome):
Control-Allow-Origin' header contains multiple values 'https://foo.com, https://foo.com', but only one is allowed. Origin 'https://foo.com' is therefore not allowed access. ¡Y tiene todo el sentido! pues en dos puntos del pipeline estamos agregando estas cabeceras.

Una solución puede ser quitar la configuración del CORS en el WebAPIConfig, es decir, la línea config.EnableCors(); y dejar que el OWIN se configure global con con Katana. ¡Pero no me gusta! no me gusta por el AllowAll (least privilage), aunque parece claro que se puede cambiar (más sobre esto a continuación), y porque se supone que la configuración del CORS de Web API es para el Framework! digo, por algo existe, no?

Como el único  lugar donde necesito el CORS es en el endpoint que genera el token, pensé que era más fácil y mejor quitar el UseCors() del Startup y agregar las cabeceras directamente en el response, sabía que no podía ser el primero que hacía esto y así fue, la segunda solución la encontré en Stack Overflow y pasa por sobrescribir el método MatchEndpoint del OAuthAuthorizationServerProvider, yo terminé con una implementación como la siguiente:

        private static void SetOriginHeaders(IOwinContext context)
        {
            if (!context.Response.Headers.Keys.Contains("Access-Control-Allow-Origin"))
                context.Response.Headers.AppendCommaSeparatedValues("Access-Control-Allow-Origin", "https://localhost:44369");
            if (!context.Response.Headers.Keys.Contains("Access-Control-Allow-Headers"))
                context.Response.Headers.AppendCommaSeparatedValues("Access-Control-Allow-Headers", "Accept", "Content-Type", "Authorization", "Cache-Control", "Pragma", "Origin");
            if (!context.Response.Headers.Keys.Contains("Access-Control-Allow-Methods"))
                context.Response.Headers.AppendCommaSeparatedValues("Access-Control-Allow-Methods", "GET", "POST", "PUT", "DELETE", "OPTIONS");
        }

        public override Task MatchEndpoint(OAuthMatchEndpointContext context)
        {
            if (context.IsTokenEndpoint &&
                (context.Request.Method.Equals("OPTIONS", StringComparison.InvariantCultureIgnoreCase)
                || context.Request.Method.Equals("POST", StringComparison.InvariantCultureIgnoreCase)))
            {
                SetOriginHeaders(context.OwinContext);
                context.MatchesTokenEndpoint();
                //context.RequestCompleted();
                return Task.CompletedTask;
            }

            return base.MatchEndpoint(context);
        }

        public override async Task ValidateClientAuthentication(OAuthValidateClientAuthenticationContext context)
        {
            context.Validated();
        }

        public override async Task GrantResourceOwnerCredentials(OAuthGrantResourceOwnerCredentialsContext context)
        {		
            //Se valida el usuario...

            SetOriginHeaders(context.OwinContext);
        }

Con el código anterior funciona sin problemas, pero nuevamente pensé: ¡Esto debe poderse hacer desde el middleware!

Configurar el Owin.Cors

Después de dar muchas vueltas llegué a esta solución, que ahora me parece muy sencilla y obvia. Se puede crear una instancia de CorsOptions y usar un PoliciResolver, que no es más que una función que permite tener acceso a la información del request (IOwinRequest) y retornar un objeto que encapsula los Headers HTTP en cómodas propiedades. El código del Startup se así (el orden de los middlewares SI altera el resultado):

    public partial class Startup
    {
        public void Configuration(IAppBuilder app)
        {
            app.UseCors(new CorsOptions
            {
                PolicyProvider = new CorsPolicyProvider
                {
                    PolicyResolver = PolicyResolver
                }
            });
            ConfigureAuth(app);
        }

        private static Task<CorsPolicy> PolicyResolver(IOwinRequest request)
        {
            if (request.Path.Value == "/api/token")
            {
                //Estos valores pueden ser recuperados de un archivo de configuracion
                var corsPolicy = new CorsPolicy
                {
                    Headers = { "Accept", "Content-Type", "Authorization", "Cache-Control", "Pragma", "Origin" },
                    Methods = { "POST", "OPTIONS" },
                    Origins = { "https://localhost:44369" }
                };
                return Task.FromResult(corsPolicy);
            }
            return Task.FromResult<CorsPolicy>(null);
        }
    }

Conclusiones

  • Existe un middleware de Katana que habilita CORS en todo el pipeline de OWIN, Microsoft.Owin.Cors
  • Owin.Cors y WebApi.Cors pueden existir en el mismo proyecto
  • El OAuthTokenProvider no hace parte de WebApi, por eso se necesita el Owin.Cors

Referencias y enlaces de interés

Espero les sea de utilidad.

Hasta el próximo post.

[ASP.NET Web API] Autenticación basada en tokens y líos con el CORS

[Evento] Dando un giro a nuestra arquitectura, de capas a verticales

En el tiempo que llevo desarrollando software para empresas he notado que, sin importar el negocio, todas las soluciones terminan siendo similares en su diseño, ¡sí! siempre se termina con algo en capas, con toneladas de abstracciones e indirecciones muchas veces innecesarias que terminan haciendo más complicado el desarrollo, evolución y mantenimiento de estas soluciones. Este ha sido el tema de conversaciones y cervezas con mi amigo Jhonnys, un loco con el que he trabajado implementando varios proyectos con este diseño “tradicional”, analizando las ventajas, desventajas y ahora cómo mejorar.

En una de esas conversaciones y con la pretensión de aportar algo a la comunidad, hemos decidido abrir un espacio para mostrar una forma diferente de trabajar, verticales en lugar de capas horizontales. No es algo de nuestra invención, pero hemos tenido la oportunidad de trabajar y aplicarlo en algunos proyectos con muy buenos resultados.

Nuestra idea es compartir, de manera practica, nuestras inconformidades y preocupaciones con estos diseños tradicionales (tradicionales al menos en el mundo de las empresas colombianas que usan .NET), escuchar opiniones al respecto y compararlas con el diseño en verticales.

El evento lo haremos de manera presencial y gratuita con la comunidad de C# Colombia, serán cuatro sesiones para compartir conocimiento y mejorar entre todos.

Toda la información de fechas y registro la podrán encontrar en el meetup de la comunidad.

Nos vemos.

[Evento] Dando un giro a nuestra arquitectura, de capas a verticales

Azure Functions y múltiples archivos de script en F#

Nota 1: Realmente no tiene nada que ver con los Azure Functions pero como aquí se usan Scripts de F# fue la excusa perfecta para aprenderlo.

La semana pasada se anunció un nuevo release de Azure Functions donde destacan el soporte mejorado para F#

image

Y esta misma semana un colega se tomó el tiempo para escribir un excelente tutorial (en inglés) con su respectivo ejemplo de código, donde muestra cómo crear una Azure Function con F# desde cero.

Ayer me animé a migrar el proyecto que había inspirado la anterior entrada a esta nueva versión con soporte mejorado para F# y esto fue lo que aprendí.

En la versión anterior, como había comentado, tenía un fsproj que ahora debía moverse a archivos de script de F# (aka .fsx). Mover los archivos a la nueva carpeta y cambiarles la extensión es la parte fácil. Ahora que hay archivos de Script en lugar de namespaces es necesario cargar los scripts a reutilizar con la directiva #load (como lo haríamos en los Scripts de C#) y abrir los módulos que se necesiten… pero esto solo es en teoría… porque me costó un poco más.

Trabajar con múltiples archivos de Script de F#

Nota 2: Esto no es solo para los fsx, es en general de F#, pero con los namespaces en  los fsproj y con las ayuda de VS no me era claro y lo desconocía.

Suponiendo una estructura de archivos como la siguiente:

operaciones.fsx
tiposOps.fsx (carga operaciones.fsx)

Si el código en operaciones.fsx quedara así

module Basicas =
    let sumar x y = x + y

El código en tiposOps.fsx genera el error

image

¿Por qué? Pues esto me pasa por obviar paginas de la documentación. Resulta que hay dos tipos de módulos, los top-level y los locales. Los top-level pueden aparecer únicamente como la primera declaración en un archivo1 y no llevan el signo igual, signo que si llevan los locales o anidados. Cuando no se usa un modulo top-level todo el código dentro del archivo se agrupa en un modulo creado automáticamente con el mismo nombre del archivo, sin extensión y con la primera letra en mayúscula.

Solo puede haber una función Run

Nota 3: Esto si tiene que ver con Azure Functions

Solo se puede nombrar una función run, de lo contrario recibiremos el mensaje de error error AF002: Multiple methods named 'Run'. Consider renaming methods.

Conclusiones

Con esta información podemos concluir que:

  • El código en el archivo operaciones.fsx usa un modulo local y al intentar usarlo se debería hacer de la forma open Operaciones.Basicas o mejor, cambiar la declaración del modulo para que sea un top-level. En lo personal no me gusta usar el modulo que se crea automáticamente y prefiero hacerlo explicito.
  • La documentación está para leerla :c

Referencias y enlaces de interés

1 Modules, Microsoft Docs

Defining Modules VS.NET vs F# Interactive, SO

Interactive Programming with F#, Microsoft Docs

Should F# functions be placed in modules, classes, or another structure?, SO

Espero les sea de utilidad.

Hasta el próximo post.

Azure Functions y múltiples archivos de script en F#

How To: Despliegue de Azure Function desde VSTS usando Kudu

En los Azure Functions existe la posibilidad de configurar integración continua desde alguno de los repositorios soportados, y funciona muy bien en el escenario normal (con la estructura de la función y los archivos de script). Sin embargo, puede darse el caso que se necesite compilar previamente un proyecto para usar sus ensamblados desde el script de la función. Suena un poco raro, pero este fue mi caso la semana pasada dado el estado actual de soporte para F# (en el que se está avanzando). La situación era un proyecto de consola (.exe) que será llamado desde una función (Powershell) con un TimerTrigger.

Al final es muy fácil, pero perdí algo de tiempo poniendo las piezas juntas, así que dejo aquí el procedimiento solo por si me vuelve a ocurrir o le es de utilidad a alguien más:

1- A la definición del Build de Visual Studio de VSTS agregar un paso de copia de archivos con las propiedades como se ven en la imagen. Esto copiará la función (el archivo run y el function.json) al lugar donde ha sido ubicado el binario previamente (en mi caso, la función no hace parte del proyecto)

image

 

2- Agregar un paso para crear el zip que será enviado al endpoint de Kudu. Las propiedades las he dejado como están en la imagen:

image

3- Al repositorio se le debe agregar un archivo de Powershell, en mi caso lo he nombrado deploy.ps1 con el siguiente código:

Param(
    [Parameter(Mandatory = $true)]
    [string]$websiteName,

    [Parameter(Mandatory = $true)]
    [string]$buildZip,

    [Parameter(Mandatory = $true)]
    [string]$username,

    [Parameter(Mandatory = $true)]
    [string]$password,

    [string]$destinationPath = "/site/wwwroot/{nombre de la funcion}",
    [int]$timeout = 600
)

$ErrorActionPreference = "Stop"

Function JoinParts {
    param ([string[]] $Parts, [string] $Separator = '/')

    $search = '(?<!:)' + [regex]::Escape($Separator) + '+'
    ($Parts | Where-Object {$_ -and $_.Trim().Length}) -join $Separator -replace $search, $Separator
}

#Select-AzureSubscription -SubscriptionId $subscriptionId

$website = Get-AzureWebsite -Name $websiteName

#$username = $website.PublishingUsername
#$password = $website.PublishingPassword

$base64Auth = [Convert]::ToBase64String([Text.Encoding]::ASCII.GetBytes(("{0}:{1}" -f $username, $password)))
$authHeader = @{Authorization=("Basic {0}" -f $base64Auth)}

$baseUri = ($website.SiteProperties.Properties | Where-Object { $_.Name -eq "RepositoryUri" } | Select-Object -First 1).Value

$commandApiUri = JoinParts ($baseUri, "/api/command")
$commandBody = @{
    command = "rmdir {nombre de la funcion} /q /s && mkdir {nombre de la funcion}"
    dir = "site\wwwroot"
}

Write-Output "Removing previous build..."
Invoke-RestMethod -Uri $commandApiUri -Headers $authHeader -Method POST -ContentType "application/json" -Body (ConvertTo-Json $commandBody) -TimeoutSec $timeout | Out-Null

Write-Output ("Publishing to URI '{0}'..." -f $deployApiUri)
$deployApiUri = JoinParts ($baseUri, "api/zip", $destinationPath) '/'
Invoke-RestMethod -Uri $deployApiUri -Headers $authHeader -Method PUT -InFile $buildZip -ContentType "multipart/form-data" -TimeoutSec $timeout | Out-Null

Este código no es mío, lo he adaptado de este articulo que me aclaró bastante el panorama.

Básicamente lo que hace es:

3.1- Usar algunos cmdlets del Azure PowerShell para recuperar un Azure WebSite a partir de su nombre (si, un Azure Website). Estos cmdlets los tenemos disponibles en VSTS.

3.2- A partir de sus propiedades recupera la url del scm

3.3- Hace una petición POST al endpoint command para eliminar el contenido de la función anterior

3.4- Hace un PUT al endpoint zip con el zip que creamos en el paso anterior.

Nota: Agregué el usuario y el password como parámetros del script porque, al parecer, ya no hacen parte de las propiedades del Website. Este usuario y contraseña son los deployment credentials del sitio.

4- Vincular el Azure con VSTS

5- Agregar un paso de Azure PowerShell con las propiedades como se ven en la imagen:

image

 

Referencias

Deploying to Azure Using Kudu

Deploy to azure functions using powershell

Espero les sea de utilidad.

Hasta el próximo post.

How To: Despliegue de Azure Function desde VSTS usando Kudu

Serverless Microservices con Azure Functions y Api Management

Hace ya un tiempo que Amazon liberó el servicio Lambda, en ese entonces no lo entendí muy bien, me pareció entender que respondía a eventos, lo comparé con los Azure WebSites + Azure Web Jobs y dejé el tema hasta ahí. En las ultimas semanas Microsoft anunció el servicio Azure Functions, y en la web ya se veían comparaciones con AWS Lambda, vi la documentación y la presentación en su momento, pero no entendí que plus había frente a los ya conocidos Azure WebSites + Azure Web Jobs. La semana pasada se llevó a cabo el Dev Days Latam en la ciudad de Lima, un evento sin presentes en la región al que tuve la oportunidad de asistir, y donde por primera vez escuché este concepto en una de las sesiones.

Decir que son los microservicios me resulta tan difícil como decir que es la programación funcional, si bien puedo decir algunas características no tengo una definición precisa y desconozco si la hay. En una ocasión un colega dijo “son Bounded Contexts as a Service” y es una definición que me gusta, pues de ahí se desprende lo de las pequeñas unidades de despliegue y la posibilidad de usar un lenguaje para cada necesidad y etc. etc. Imaginar que son los Serverless Microservices me hizo pensar en unidades de despliegue que no van a un “server” (?) ¿imágenes de Docker auto gestionadas en un host que yo no controlo? al googlear el termino para ver alguna definición o implementación veo que, para sorpresa mía, los primeros resultados son implementaciones hechas en AWS Lambda. ¿Pero no es lo mismo que un Azure WebSite + Web Job?

Desconozco mucho de la oferta de computo en la nube de Amazon así que traduzco la documentación de AWS Lambda a los Azure Web Sites y Web Jobs, pues me ofrece muchas de las características que allí se muestran. Pero si Azure ya tenía estos dos servicios ¿Para qué crear uno nuevo, si de hecho, lo Functions están basados en el Azure WebJob SDK?

Rescato algunos de los conceptos: Compute on-demand, que incluye un nuevo modelo de cobro y la posibilidad de responder a eventos de servicios de terceros (Http – WebHooks (?)). Y por último, pero no menos importante, el modelo de programación: Un Function App es una carpeta que contiene un archivo host.json y carpetas con las funciones. Estas funciones (carpetas) son archivos de código (en los lenguajes soportados) y un archivo function.json que define la función. La documentación completa está aquí.

Podemos entonces definir un Function App como el siguiente:

MyService
|host.json
|Membershib
|| node_modules
|| function.json
|| index.js
|SayHello
|| function.json
|| project.json
|| run.csx

En la estructura de este ejemplo he dejado dos funciones en lenguajes distintos dentro del mismo Function App (ahora mismo no sé si escala por función o por App), pero se puede mejorar esta implementación teniendo un servicio independiente de membership y uno “por cada necesidad”

Cómo cada Función tiene su propio endpoint… ¿Cómo hacemos para “unificarlo”? Azure tiene el servicio de Api Management que nos viene perfecto para exponerla como un Api, además de otros plus del servicio.

Así como los microservicios voy a dejar este post corto, solo con el concepto y sin más detalles de la implementación. Ya luego si me animo sigo con algo más parecido a un tutorial.

He dejado algo de código, con la estructura del proyecto que mostré aquí, en mi GitHub.

Serverless Microservices con Azure Functions y Api Management

ASP.NET 5, Owin y Katana

Con todo esto del ASP.NET5, ASP.NET 4.6, MVC6, DNX, DNX Core, etc. No queda muy claro donde encajan ciertos componentes que antes ya nos resultaban familiares. Como el caso de Owin y Katana que, con el anuncio de ASP.NET 5, no supe donde quedaron o qué iba a pasar con ellos.

Afortunadamente el equipo de ASP.NET documentó el tema y solo tenía que buscar un poco.

Con la información obtenida en el articulo me quedaron claras algunas cosas:

  • En el repositorio de Katana ya habían dicho que la siguiente versión sería parte de “vNext” y que el proyecto se movería de codeplex a GitHub, en el mismo repo de ASP.NET. Además renombraron todo para alinearlo con ASP.NET 5 y la versión sería de nuevo la 1.0.katanaroadmap
  • Con esta movida no solo cambiaron de nombre las cosas, también cambió el cómo funcionaban, es el caso del IAppBuilder, que ahora es IApplicationBuilder, y que usa un AppFunc diferente. O el IOwinContext, que ahora es HttpContext.
  • Si hay forma de usar los viejos (Katana 3.0) middlewares en ASPNET 5.

Algo de código

Hasta aquí he comentado lo que entendí de aquel articulo. Pero unas cuantas lineas de código nos mostrara que quiere decir esto y nos aportará nuevas dudas.

¿Cómo luce un middleware hoy?

Para crear un middleware compatible con el pipeline de Katana basta con definir una clase que use el AppFunc y tenga un método Invoke, algo de la forma:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;

namespace MisMiddelwares
{
    using AppFunc = Func<IDictionary<string, object>, Task>;

    public class DebugMiddleware
    {
        private readonly AppFunc _next;

        public DebugMiddleware(AppFunc next)
        {
            _next = next;
        }

        public async Task Invoke(IDictionary<string, object> enviroment)
        {
            var path = (string) enviroment["owin.RequestPath"];
            Debug.WriteLine("--Incoming request. Path: " + path);
            await _next(enviroment);
            Debug.WriteLine("--Outgoing request. Path: " + path);
        }
    }
}

¿Cómo se usa un middleware hoy?

El middleware anterior lo podemos integrar en el pipeline de Katana 3.0 de manera muy, muy sencilla:

    using Owin;
    using MisMiddlewares;
    public class Startup
    {        
        //... Configure Web API for self-host. 
        var config = new HttpConfiguration();
	appBuilder.Use<DebugMiddleware>();
        appBuilder.UseWebApi(config);      
    }

Si quisiéramos agregar nuestro middleware usando la forma app.UseXXX, deberíamos agregar una clase estática al ensamblado del middleware, agregar una dependencia a Katana (Microsoft.Owin) y usar el siguiente código

namespace MisMiddlewares
{
    using Owin;

    public static class DebugMiddlewareExtensions
    {
        public static void UseDebug(this IAppBuilder app)
        {
            app.Use<DebugMiddleware>();
        }
    }
}

Usar mi middleware en ASP.NET 5

Ahora viene lo nuevo, en un proyecto de ASP.NET 5 (DNX) vamos a intentar usar el middleware que acabamos de crear. Para ello lo primero que haré será remover el dnxcore50 de la sección frameworks del project.json, esto porque no lo usaré y necesito una referencia al middleware (cproj). Una vez hecho esto agrego una referencia al proyecto (con todo lo que hace por detrás), esto lo hago solo para ver que pasaría en el caso de querer reutilizar el componente sin tener que escribir nada más, además de ver que tiene el nuevo Katana que nos permita reutilizar lo anterior.

En el startup vemos que el nuevo IApplicationBuilder aún expone un método Use, pero con una firma muy diferente para el AppFunc que no nos sirve en nuestra anterior implementación. Podríamos intentar construir uno (AppFunc) a partir de este, o mejor aún, usar lo que ya tiene Katana vnext (el vnext se lo puse yo :P) para esto. En el articulo hay un enlace a un repo que contiene un ejemplo, algo engorroso, que muestra cómo hacerlo. Pero en ese mismo repositorio hay otro ejemplo un poco más claro. Partiendo de este ejemplo, si queremos usar de nuevo nuestro middleware empezaremos por instalar el paquete Microsoft.AspNet.Owin, que nos expone el método UseOwin, y, en la clase Startup ya podemos agregarlo al pipeline:

        public void Configure(IApplicationBuilder app, IHostingEnvironment env)
        {
            app.UseOwin(addToPiepline =>
            {
                addToPiepline(next =>
                {
                    var middleware = new DebugMiddleware(next);
                    return middleware.Invoke;
                });
            });

Inquietudes

Con esta implementación me queda la inquietud de cómo harán las personas que mantienen este tipo de proyectos para dar soporte a las aplicaciones DNX y a las tradicionales, cómo será el tema del código compartido… o si será algo automático

Ejemplo

He dejado el código de este artículo aquí

Espero les sea de utilidad esta breve aclaración

Hasta el próximo post.

ASP.NET 5, Owin y Katana

[F#] Tail Recursion y el Stack

En la entrada anterior veíamos cómo, de manera sencilla, podíamos razonar y entender las funciones recursivas. Pero ¿Cómo funcionan estas llamadas recursivas en .NET?

Empecemos por aclarar algo. Cuando se llama a una función, el computador debe recordar el lugar desde donde fue llamada, la dirección de retorno, de modo que pueda volver a ese lugar con el resultado una vez la llamada se ha completado¹. Estas direcciones son almacenadas en el call stack. Una vez la función retorna un valor la pila de llamadas se borra y el programa continúa desde la función llamadora.

Si una función recursiva se llama a si misma una y otra vez, como un loop, el stack se irá llenando con dichas direcciones (las llamadas a si mismo). El problema es que el stack no es infinito y podemos recibir una conocida excepción, si, la Stack Overflow Exception.

Podemos comprobar este comportamiento si escribimos una función que calcule el factorial de un número de manera recursiva, algo de la forma:

    let rec factorial =
        function
        | x when x > 1 -> x * factorial (x-1)
        | _ -> 1

Usando Visual Studio, podemos poner un breakpoint en el otherwise, donde esta el “1“, llamar la función y ver que pasa:

factorial

Ahora podemos probar calculando el factorial de Int32.MaxValue y ver que pasa… Process is terminated due to StackOverflowException.

Entonces, ¿Es posible escribir funciones recursivas que no llenen el call stack? La respuesta es si, y es lo que llamamos tail recursion (lo dejo en inglés porque recursión de cola no me gusta). Este tipo de recursión se basa en que todas las llamadas recursivas aplicarán la optimización de tail call. Esta optimización la obtenemos cuando la función llamadora retorna directamente el valor de la función llamada sin aplicar ninguna transformación/operación/reducción sobre dicho valor de retorno. Entonces, si todas las llamadas de la función recursiva son tail calls tendremos tail call recursion.

¿Pero cómo podemos lograr esto? Si analizamos de nuevo el tail call la respuesta pasa por retornar directamente la llamada a la función sin aplicar la función x*. Pero… ¿Y por cual valor multiplicamos? pues tendremos que usar un valor inicial (seed/acumulador/…). Con lo que la función factorial, tail recursive, puede ser definida así:

    let factorial' =
        let rec fact acc = 
            function
            | x when x > 1 -> fact (acc*x) (x-1)
            | _ -> 1
        fact 1

Cómo podemos ver ahora hay una nueva función dentro de la definición de factorial'. Esta función recibirá el valor del acumulador, que será 1 y el parámetro n. Si ponemos nuevamente un breakpoint en el otherwise, donde está el “acc“. Y usamos la función con Int32.MaxValue, esta vez veremos un call stack como el siguiente:

factorial1

De esta forma retornamos directamente la función sin hacer ninguna operación (x*) sobre la función.

En lenguajes funcionales, como F#, es común que el compilador optimice este código, y lo convierta a loops cómo los que tendríamos en lenguajes imperativos, logrando así el mismo comportamiento y performance.

Por el contrario, si queremos aplicar esta tipo de recursión en lenguajes como C# veremos que no hay ninguna optimización y el call stack se irá llenando con cada llamada a la función. El por qué en C# no se hace esta optimización es un misterio para mi, pero para eso esta F#.

Espero les sea de utilidad.

Hasta el próximo post.

Referencias

¹ Véase Wikipedia, Tail call, consultado: 7/11/2015.

MSDN Blog, Tail calls in F#

MSDN Blog, Understanding Tail Recursion

StackOverflow, Why doesn’t .NET/C# optimize for tail-call recursion?

[F#] Tail Recursion y el Stack