Deconstrucción en C# 7.0: cuidado con las sobrecargas!

“… You’re the reason I’m travelin’ on / Don’t think twice, it’s all right”
Bob Dylan, “Don’t think twice, it’s all right” (1963)

En nuestra entrega anterior presentamos la deconstrucción, un nuevo mecanismo que ofrece C# 7.0 para permitir desintegrar un objeto de cualquier tipo en las partes que lo componen, asignando los valores de esas partes a nuevas variables o a variables ya existentes utilizando la sintaxis incorporada al lenguaje para expresar tipos de tuplas-valor:

    var dh = new Person("Denis", new DateTime(1985, 12, 27));
    // ...
    (string name, int year, int month, int day) = dh;  // declaración
    string s;
    int y, m, d;
    (s, y, m, d) = dh;  // asignación
}

El tipo que ofrece la deconstrucción debe suministrar uno o más métodos Deconstruct con los parámetros de salida adecuados. Alternativamente, Deconstruct puede ser un método extensor (extension method), lo que hace posible utilizar el mecanismo para tipos de los cuales no disponemos del código fuente. Para que el código anterior funcione, la clase Person debe haberse definido así:

using System;
namespace ValueTuples
{
    public class Person
    {
        public string Name { get; }
        public DateTime BirthDate { get; }

        public Person(string name, DateTime birthDate)
        {
            Name = name;
            BirthDate = birthDate;
        }

        public void Deconstruct(out string name,
            out int year, out int month, out int day)
        {
            name = Name;
            year = BirthDate.Year; month = BirthDate.Month; day = BirthDate.Day;
        }
    }
}

Cuando empecé a probar esta característica, hasta aquí todo iba de maravilla. Pero entonces pensé que me gustaría poder devolver además del número del día el día de la semana, y claro, envolver toda la información sobre el día en una tupla, para poder hacer algo así:

    // Deconstrucción a varios niveles???
    (string name, _, _, (_, DayOfWeek dayOfWeek)) = dh;
    // Esto imprime: Denis was born a Friday.
    Console.WriteLine($"{name} was born a {dayOfWeek}.");
}

Cuando se me ocurrió hacer esto, probablemente estaría pensando en la unificación recursiva de Prolog (craso error :-)). La sobrecarga de Deconstruct con cuatro parámetros que permitiría una sintaxis como la anterior podría ser ésta:

    public void Deconstruct(out string name,
        out int year, out int month, 
        out (int DayNumber, DayOfWeek DayOfWeek) day)
    {
        name = Name;
        year = BirthDate.Year; month = BirthDate.Month; 
        day = (BirthDate.Day, BirthDate.DayOfWeek);
    }

Si se comenta la primera sobrecarga de Deconstruct y se incorpora ésta, todo funciona de maravilla. Pero si se activan los dos mecanismos simultáneamente, la clase Person compila correctamente (y por qué no), pero el código cliente que intenta utilizar la segunda sobrecarga es rechazado por el compilador:

The call is ambiguous between the following methods and properties:
    Person.Deconstruct(out string, out int, out int, out int) and
    Person.Deconstruct(out string, out int, out int, 
        out (int DayNumber, DayOfWeek DayOfWeek))

En este momento me quedé un poco desilusionado; esperaba que el compilador sería capaz de detectar que el patrón del lado izquierdo de la asignación utiliza una tupla en la cuarta posición, y por lo tanto la segunda sobrecarga es la única aceptable en ese caso. Buscando una respuesta rápida, planteé la pregunta en StackOverflow, y David Arno gentilmente me la respondió; en su propia respuesta me indica que ha enviado una sugerencia al equipo de desarrollo de C# porque piensa que la resolución de sobrecargas durante la deconstrucción no funciona tan finamente como podría.

Problemas como éste me hacen dudar de si las últimas novedades no se estarán añadiendo al lenguaje a un ritmo demasiado apresurado y sin tiempo para pensar dos veces (think twice) y estudiar todos los posibles casos extremos; de hecho, la especificación formal de C# 7.0 todavía se está escribiendo… ¡y ya salió C# 7.1! Pero tales son los tiempos ágiles que corren, y la mejor documentación de las características del lenguaje es, cada vez más, el código fuente de Roslyn en GitHub.

En cualquier caso, me ha quedado claro que es una mala idea dotar a un tipo de dos o más sobrecargas de Deconstruct con la misma cantidad de parámetros. ¡Queda advertido, estimado lector!


Referencia musical: Durante mi adolescencia, la vía casi exclusiva que tenía para escuchar pop y rock norteamericano eran las emisoras comerciales de la Florida, y Bob Dylan nunca fue especialmente popular por esos lares. Así que realmente solo empecé a conocer su obra bien pasados los treinta, gracias a mis queridos amigos de El Puerto de Santa María. “Don’t think twice…” es, sin dudas, uno de sus temas más reconocibles.

Deconstrucción en C# 7.0

En nuestra entrega anterior, dedicada a las tuplas-valor (value tuples) añadidas recientemente a C# 7.0, mencionamos brevemente el mecanismo de deconstrucción (deconstruction), al que dedicaremos aquí algo más de espacio. La deconstrucción es un nuevo mecanismo sintáctico que aprovecha la sintaxis incorporada al lenguaje para representar tipos de tuplas-valor para permitir, de una manera sencilla y conveniente, descomponer un objeto de cualquier tipo en las partes que lo componen, asignando los valores de esas partes a nuevas variables (en cuyo caso estamos en presencia de una declaración de deconstrucción, deconstructing declaration) o a variables ya existentes (asignación de deconstrucción, deconstructing assignment):

    var dh = new Person("Denis"new DateTime(19851227));
    // ...
    (string name, int year, int month, int day) = dh;  // declaración
    string s;
    int y, m, d;
    (s, y, m, d) = dh;  // asignación
}

Como se habrá dado cuenta el lector, en el fondo se trata de simple azúcar sintáctico que evita tener que hacer uso de múltiples asignaciones y/o llamadas con incómodos parámetros out. Para satisfacer al compilador, es necesario que el tipo a descomponer ofrezca un método Deconstruct con los parámetros adecuados (en él es donde precisamente se encapsulan esos parámetros out). Deconstruct puede incluso ser un método extensor (extension method) que esté en ámbito, lo que hace posible utilizar el mecanismo para tipos de los cuales no disponemos del código fuente. Además, se puede implementar varias sobrecargas para ofrecer varias maneras de deconstruir un objeto. Por ejemplo, el código mostrado anteriormente funciona porque las siguientes definiciones están en vigor:

using System;
namespace ValueTuples
{
    public class Person
    {
        public string Name { get; }
        public DateTime BirthDate { get; }

        public Person(string name, DateTime birthDate)
        {
            Name = name;
            BirthDate = birthDate;
        }

        public void Deconstruct(out string name,
            out int year, out int month, out int day)
        {
            name = Name;
            BirthDate.Deconstruct(out year, out month, out day);
        }
    }

    public static class Extensions
    {
        public static void Deconstruct(this DateTime dateTime,
            out int year, out int month, out int day)
        {
            year  = dateTime.Year;
            month = dateTime.Month;
            day   = dateTime.Day;
        }
    }
}

Visto todo lo anterior, solo resta mencionar algunos detalles adicionales:

  • Las tuplas-valor soportan de manera predefinida la deconstrucción en sus componentes originales sin que tengamos que hacer absolutamente nada; veremos más detalles al respecto en una próxima entrega, que ya estaba prometida :-).
  • Los descartes, que ya presentamos hace algún tiempo, pueden ser útiles en caso de que solo estemos interesados en algunos de los elementos resultantes de la deconstrucción, como se muestra en el siguiente ejemplo:
using System;
namespace ValueTuples
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var dh = new Person("Denis"new DateTime(19851227));
            // ...
            (string name, int year, _, _) = dh;
            Console.WriteLine($"Name: {name}");
            Console.WriteLine($"Year: {year}");
        }
    }
}

Es precisamente esta aplicación conjunta de la deconstrucción y los descartes lo que tanto me recuerda al lenguaje de programación lógica Prolog. Aunque hay que reconocer que, incluso con todas las novedades añadidas a C# 7.0 y 7.1, C# aún se queda bastante corto: la unificación de Prolog es bidireccional, y las variables (y los descartes) pueden situarse a cualquiera de los dos lados del símbolo de unificación (que no asignación); más aún, el mecanismo de unificación de Prolog se basa en un algoritmo de emparejamiento de patrones (pattern matching) mucho más general, y que no depende para su funcionamiento de que se definan de antemano métodos especializados o se restrinjan en modo alguno las estructuras de las tuplas a unificar.


Agradecimientos: Lo poco que sé sobre Programación Lógica y sus aplicaciones lo aprendí de un MAESTRO con mayúsculas, Don Luciano García Garrido, a quien envío desde aquí un afectuoso saludo.

Tuplas-valor en C# 7.0

“… Pero lo nuestro es pasar / Pasar haciendo caminos / Caminos sobre la mar …”
Joan Manuel Serrat, “Cantares” (1969), basada en  un poema de Antonio Machado

La idea de escribir una entrada relacionada con las tuplas-valor (value tuples) añadidas recientemente a C# 7.0 me trajo a la mente el artículo que escribí una vez para la revista dotNetManía con mi maestro y amigo Miguel Katrib cuando aparecieron las tuplas-referencia, aquellas que se sintetizan a través del uso de la clase genérica Tuple<> que fue incorporada a .NET Framework en la versión 4.0. Las nuevas tuplas-valor se introducen casi que con la idea de hacer obsoletas (“todo pasa y todo queda…“) las tuplas-referencia, resolviendo la mayor parte de los inconvenientes que éstas presentan, y algunas ideas en ese sentido ya las proponíamos en aquel lejano artículo (que el lector interesado puede encontrar, gracias a la generosidad de nuestro gran amigo Paco Marín, aquí).

El primer elemento a destacar es que para poder hacer uso de las tuplas-valor es necesario instalar el paquete de NuGet System.ValueTuple, a menos que esté usted desarrollando un proyecto basado en .NET Framework 4.7 o superior, o en .NET Core 2.0 o superior. Como tipo de datos, una diferencia crucial entre ValueTuple y System.Tuple es que el nuevo tipo es una estructura en vez de una clase y sus miembros son campos en vez de propiedades, lo que lo hace en principio más ligero y eficiente con relación a Tuple. Aparte de eso, un somero análisis de los ensamblados correspondientes le convencerá de que ambos tipos utilizan patrones de desarrollo parecidos (incluyendo el truco del “octavo pasajero” al que aludíamos en el artículo antes mencionado) y ofrecen posibilidades similares. Algunas de ellas pueden verse en la parte inicial del ejemplo que se muestra más abajo, aunque también varias diferencias:

  • Si bien por defecto el convenio de nombres para los elementos de una tupla es el mismo (Item1, Item2, etc.), para las tuplas-valor el compilador soporta el uso de nombres alternativos para los campos.
  • Como los elementos de las tuplas-valor son campos públicos, sus valores pueden ser modificados (son mutables).

Pero sin duda alguna lo más útil e interesante en relación con las tuplas-valor es que el compilador de C# las utiliza al transformar el nuevo “azúcar sintáctico” que ahora está soportado en C# 7.0. Dejaré para una próxima entrada un análisis de los “actos de magia” que utiliza el compilador para generar código basado en ValueTuple (que por supuesto no se basa en la herencia, dado que las estructuras no la soportan).

La segunda parte del código a continuación muestra un ejemplo de la que tal vez sea la aplicación más popular para las tuplas-valor: una función que devuelve varios valores. En este caso, el método FibonacciInterval determina simultáneamente el menor número de Fibonacci que es mayor o igual que el valor recibido como parámetro y el siguiente número de la secuencia. Note como se puede también utilizar nombres explícitos para hacer más legible el código que llame a la función:

using System;

namespace ValueTuples
{
    class MainClass
    {
        static void Main(string[] args)
        {
            var t1 = ValueTuple.Create("DH"ValueTuple.Create(27121985));
            var t2 = ("DH", (27121985)); // equivalente "endulzado"
            t1.Item2.Item2 = 10;
            Console.WriteLine(t1.Item2);

            var t3 = (Nombre: "Diana", Nacimiento: (Día: 2, Mes: 4, Año: 1998));
            Console.WriteLine(t3.Nacimiento.Día);

            for (uint i = 0; i < 50; i++)
                Console.WriteLine($"Fibonacci interval for {i} = " +
                    FibonacciInterval(i));
        }

        public static (uint Min, uint Max) FibonacciInterval(uint number)
        {
            (uint min, uint max) = (01);
            while (true)
            {
                if (number < max)
                    return (min, max);
                uint sum = min + max;
                min = max;
                max = sum;
            }
        }
    }
}

Observe también la simpática asignación (uint min, uint max) = (01) al inicio del método. Se trata de un ejemplo de deconstrucción (del inglés deconstruction) o desmontaje de una tupla-valor en sus componentes individuales. Esta característica de deconstrucción (que es más general y puede aplicarse a tipos que no sean tuplas-valor) me recuerda, como ya he dicho antes, al mecanismo de unificación utilizado en el lenguaje Prolog; la abordaré con más detalle en otra futura entrega.


Referencia musical: Tendría yo unos doce años cuando Joan Manuel Serrat fue a cantar a nuestra escuela en las afueras de La Habana, y desde ese entonces lo cuento entre mis favoritos. Adicionalmente, el hecho de que las letras de sus temas más populares de aquellos tiempos estuvieran basadas en poemas de Antonio Machado y Miguel Hernández me incitó a estudiar la vida y obra de esos poetas, sin saber que un día el destino me llevaría a España. ¡Gracias, Maestro!

Solving Combinatory Problems with LINQ

Originally published by MSDN in April, 2010.

The other day I ran into a very interesting blog post by Intel engineer James Cownie, Intel Parallel Studio: Great for Serial Code Too (Episode 1). The article uses as an example an application that solves the following problem (I quote):

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

  1. The number should be divisible by 9.
  2. If the rightmost digit is removed, the remaining number should be divisible by 8.
  3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
  4. And so on, until there’s only one digit (which will necessarily be divisible by 1).

While the C++ solution proposed by the author in that article runs along more “conventional” lines, I (having the enormous luck of being a C# developer) was immediately drawn to applying LINQ to tackle this problem. I find LINQ an ideal tool for solving this type of exploratory problem, where one needs to traverse a full tree of possible combinations, backtracking from unsuccessful branches as soon as they are encountered.

With LINQ queries, cascaded from clauses serve as the generators of combinations, while where clauses determine the failure points that trigger backtracking. The first time I saw this technique used was in the blog post Using LINQ to solve puzzles, by Luke Hoban, a member of the Microsoft Languages Team. I was inspired to write about the approach in my book C# 3.0 and LINQ (C# 3.0 y LINQ, Krasis Press, 2007 (in Spanish)), and then occasionally in my blog, the last time to solve a puzzle involving the generation of a magic square similar to the Dührer square mentioned in the latest Dan Brown bestseller, The Lost Symbol. The post, Buscando el símbolo perdido con LINQ, is in Spanish.

The code that follows shows my implementation of the solution to the problem, which I find a good example of the enormous expressive power of LINQ.

using System;
using System.Linq;
 
namespace Geeks
{
  // C# and LINQ solution to the numeric problem presented in: 
  // http://software.intel.com/en-us/blogs/2009/12/07/intel-parallel-studio-great-for-serial-code-too-episode-1/
  class MainClass
  {
    static void Main()
    {
      int[] oneToNine = new int[] { 123456789 };

      // the query 
      var query =
        from i1 in oneToNine
        from i2 in oneToNine
        where i2 != i1
           && (i1 * 10 + i2) % 2 == 0
        from i3 in oneToNine
        where i3 != i2 && i3 != i1
           && (i1 * 100 + i2 * 10 + i3) % 3 == 0
        from i4 in oneToNine
        where i4 != i3 && i4 != i2 && i4 != i1
           && (i1 * 1000 + i2 * 100 + i3 * 10 + i4) % 4 == 0
        from i5 in oneToNine
        where i5 != i4 && i5 != i3 && i5 != i2 && i5 != i1
           && (i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5) % 5 == 0
        from i6 in oneToNine
        where i6 != i5 && i6 != i4 && i6 != i3 && i6 != i2 && i6 != i1
          && (i1 * 100000 + i2 * 10000 + i3 * 1000 + i4 * 100 + i5 * 10 + i6) % 6 == 0
        from i7 in oneToNine
        where i7 != i6 && i7 != i5 && i7 != i4 && i7 != i3 && i7 != i2 && i7 != i1
          && (i1 * 1000000 + i2 * 100000 + i3 * 10000 + i4 * 1000 + i5 * 100 + i6 * 10 + i7) % 7 == 0
        from i8 in oneToNine
        where i8 != i7 && i8 != i6 && i8 != i5 && i8 != i4 && i8 != i3 && i8 != i2 && i8 != i1
          && (i1 * 10000000 + i2 * 1000000 + i3 * 100000 + i4 * 10000 +
              i5 * 1000 + i6 * 100 + i7 * 10 + i8) % 8 == 0
        from i9 in oneToNine
        where i9 != i8 && i9 != i7 && i9 != i6 && i9 != i5 && i9 != i4 && i9 != i3 && i9 != i2 && i9 != i1
        let number = i1 * 100000000 +
                     i2 * 10000000 +
                     i3 * 1000000 +
                     i4 * 100000 +
                     i5 * 10000 +
                     i6 * 1000 +
                     i7 * 100 +
                     i8 * 10 +
                     i9 * 1
        where number % 9 == 0
        select number;

      // run it! 
      foreach (int n in query)
        Console.WriteLine(n);
    }
  }
}

Note that no attempt at all has been made to optimize the code (for instance, applying individual divisibility criteria for the different positions). I firmly believe in Don Knuth‘s statement that “premature optimization is the root of all evil,” and the program as it stands perfectly satisfied my expectations. On my laptop, it finds the only solution to the problem (the number 381654729) in much less than a second.

Descartes en C# 7.0

“Don’t discard me / Just because you think I mean you harm …”
Elton John, “Don’t let the sun go down on me” (1974)

Entre las nuevas características de lenguaje incorporadas a C# 7.0, una relativamente sencilla que ha llamado mi atención son los descartes (discards). Según dice Matt Torgersen en las notas sobre el diseño de C#, el cambio del término que estaba previsto, wildcards, por discards (para mí tremendamente acertado), fue propuesto al equipo de C# durante el último MVP Summit celebrado en Seattle.

Creo que descarte es el término castellano que debiéramos utilizar, vistas sus acepciones en el diccionario de la Real Academia Española: “1) Acción de descartar o descartarse. 2) En varios juegos de naipes, cartas que se desechan o quedan sin repartir”. Y espero sinceramente que dentro de una o dos décadas, cuando se enseñe a programar desde la más tierna infancia, se añada al diccionario un nuevo significado para esta palabra: “En ciertos lenguajes de programación, nombre que se da a variables locales de solo escritura generadas por el compilador”.

Básicamente, los descartes nos ahorran la necesidad de asignarle explícitamente un nombre a una variable que no vamos a utilizar después de su primera aparición en el código fuente (en la que se le asigna un valor). Me recuerdan a una característica muy parecida que ofreció desde sus inicios el lenguaje de programación lógica Prolog (donde también se utiliza un simple subrayado para denotar a los descartes), aunque allí la cosa va de unificación bidireccional, y no de la simple asignación.

El ejemplo más típico de uso de los descartes es probablemente el relacionado con el parámetro out que ofrecen las diferentes implementaciones de TryParse() diseminadas a lo largo de las librerías de .NET Framework. Si nuestro único interés es validar la cadena de caracteres de entrada, entonces no es necesario que nos preocupemos por dar nombre a la variable que recibirá el valor interpretado correspondiente. El pequeño programa a continuación muestra, de hecho, dos posibles maneras de hacer más concisa la notación al trabajar con parámetros de salida en la última versión de C#:

namespace Geeks
{    
    class TestBed
    {
        static void Main(string[] args)
        {
            string test = "32A";
 
            Console.WriteLine(IsValidInt6(test));
            Console.WriteLine(IsValidInt7A(test));
            Console.WriteLine(IsValidInt7B(test));
        }
 
        static bool IsValidInt6(string s)  // C# 6 y anteriores
        {
            int temp;
            return int.TryParse(s, out temp);
        }
        static bool IsValidInt7A(string s)  // C# 7.0 
        {
            return int.TryParse(s, out int temp);
        }
        static bool IsValidInt7B(string s)  // C# 7.0
        {
            return int.TryParse(s, out _);
        }
    }
}

Otros contextos en los que los descartes pueden ser de utilidad tienen relación con otras novedades de C# 7.0: las nuevas posibilidades de la sentencia switch y el emparejamiento de patrones (pattern matching). Pero esos son temas para próximas entradas, así que lo dejaremos aquí por ahora; no sin antes mencionar que a partir de C# 7.0 el lexema _ es una nueva palabra reservada contextual, y que su utilización en contextos en los que se encuentre definida una variable local con ese mismo nombre puede provocar problemas como los que se describen aquí.


Referencia musical: ¿Qué decir sobre Elton John que no se haya escrito ya? Un genio como pocos ha habido, durante la década de los ’70 publicó (siempre con la inestimable colaboración de su letrista, Bernie Taupin) discos que hoy son clásicos del pop/rock a razón de dos por año, hasta que llegó a los diez que necesitaba para cumplir su contrato con MCA e independizarse. Y aunque, en general, los discos que siguieron no han estado a la altura de aquellos otros (¿puede la libertad ser contraproducente, amigo lector?), Elton ha conseguido mantener su popularidad hasta el presente. El tema “Don’t let the sun go down on me” apareció originalmente en el disco “Caribou” (1974); pero solo llegó al número 1 de las listas en 1991, gracias a una versión a dúo con el ya fallecido George Michael.

Abriendo una caja fuerte

“They got the money, hey / You know they got away
They headed down south and they’re still running today …”
The Steve Miller Band, “Take the Money and Run” (1976)

Como la entrada anterior trataba sobre recursividad, la técnica “divide y vencerás” y las funciones internas de C# 7, aprovecho para mostrar una solución a un problema que le plantearon a un antiguo colega que se presentó a una entrevista de trabajo en Google (debe haberle ido bien, porque lo aceptaron). El enunciado del problema es el siguiente:

Una caja fuerte está protegida mediante una combinación de cuatro dígitos decimales. La caja fuerte solo tiene en cuenta los cuatro últimos dígitos tecleados a la hora de decidir si los datos tecleados satisfacen la contraseña. Por ejemplo, si alguien teclea en la caja fuerte los dígitos 012345, con ello habrá probado las combinaciones 0123, 1234 y 2345. Obviamente, la secuencia de 40000 dígitos 0000000100020003…9999 abrirá con total seguridad la caja fuerte. Ahora bien, ¿podrían cubrirse todas las 10000 posibles combinaciones utilizando una secuencia de menor longitud? ¿Cuál es la longitud de la cadena más corta que permite probar todas las combinaciones?

Desde que mi ex-colega me lo describió, me pareció que el problema se prestaba para ser atacado mediante una función recursiva con la que se va avanzando o retrocediendo (backtracking) en el espacio de combinaciones del problema. Y como al que tiene un martillo todos los problemas se le parecen a un clavo, me puse inmediatamente a teclear y al cabo de una media hora le tenía preparado algo muy parecido al código siguiente:

using System;
using System.Linq;
 
namespace Geeks.SafeCrack
{
    static class MainClass
    {
        static void Main(string[] args)
        {
            GoForward(SafeData.InitialData);
        }

        static bool GoForward(SafeData safeData)
        {
            if (safeData.IsCracked)
            {
                PrintResults();
                return true;
            }

            var len = safeData.Sequence.Length;
            var a = (int) safeData.Sequence[len - 3] - '0';
            var b = (int) safeData.Sequence[len - 2] - '0';
            var c = (int) safeData.Sequence[len - 1] - '0';

            for (int d = 0; d <= 9; d++)
            {
                var index = SafeData.Index(a, b, c, d);
                if (safeData.Combinations[index])
                    continue;
                
                var newSequence = safeData.Sequence + (char)('0' + d);
                var newCombinations = (bool[]) safeData.Combinations.Clone();
                newCombinations[index] = true;
                if (GoForward(new SafeData(newSequence, newCombinations)))
                    return true;
            }
            return false;
 
            void PrintResults()
            {
                Console.WriteLine("Safe cracked!!!");
                var sequence = safeData.Sequence;
                Console.WriteLine("Length   = " + sequence.Length);
                Console.WriteLine("Sequence = " + sequence);
            }
        }
    }
 
    class SafeData
    {
        public SafeData(string sequence, bool[] combinations)
        {
            Sequence = sequence;
            Combinations = combinations;
        }
        public string Sequence { getprivate set; }
        public bool[] Combinations { getprivate set; }

        public bool IsCracked => Combinations.All(x => x);

        private readonly static SafeData initialData = 
            new SafeData("000"new bool[10000]);
        public static SafeData InitialData => initialData;

        public static int Index(int a, int b, int c, int d) =>
            1000 * a + 100 * b + 10 * c + d;
    }
}

Básicamente, en cada paso del algoritmo se examina con cuáles de los diez dígitos se puede extender la secuencia actual, añadiendo una nueva combinación a la lista de combinaciones ya probadas, y para cada uno de tales dígitos se avanza en profundidad. Una vez analizados los diez dígitos, se hace backtrack al contexto de la llamada inmediatamente anterior (que continuará recorriendo sus dígitos aún pendientes).

La longitud de cadena que produce el programa anterior es 10003, y dado que el programa está diseñado para retroceder masivamente una vez que se encuentra la primera solución, todo indica que navegué con mucha suerte, ya que ésta resulta ser precisamente la longitud óptima. El programa puede ser modificado fácilmente para explorar todo el espacio de combinaciones y enumerar todas las soluciones existentes, tarea que dejo al lector interesado. Pero la moraleja de esta historia no radica tanto en la utilización de la recursividad y el backtracking como en la importancia de la preparación teórica (en general) y la investigación sobre el problema (en particular) antes de ponerse a codificar como un poseso: como puede comprobarse aquí y en muchas otras fuentes, reconociendo la aplicabilidad del concepto de secuencia de De Bruijn no habría hecho falta tirar ni una sola línea de código para saber que la respuesta correcta es 10003.


Referencia musical: Uno de mis grupos favoritos de la segunda mitad de la década de los ’70 fue la banda de Steve Miller, músico recientemente incorporado al Salón de la Fama del Rock’n’Roll que desarrolló prácticamente toda su carrera en San Francisco. El tema “Take the Money and Run” fue el primer single de uno de sus discos más exitosos, “Fly Like an Eagle” (1976). Pero es probablemente el tercer éxito, el que le da el nombre al disco, el que más perdura en la memoria hoy en día; la crítica social de su letra siempre me recuerda que California (y especialmente el norte) es desde hace muchísimo tiempo una región netamente “progre”.

Funciones locales en C# 7.0

“And if my shadow is all that survives
I’m still alive …”
Meat Loaf, “Alive” (2006)

Aprovecho la suerte de que este blog sigue aún activo (¡muchas gracias por ello a mis buenos amigos de Plain Concepts!) para dar señales de vida después de hace bastante tiempo.

Revisando varios recursos online relacionados con las novedades incorporadas a C# 7.0 (incluyendo una excelente entrega de la serie Plain TV, que sigo regularmente), me pareció sumamente curioso que prácticamente ninguno de los vídeos consultados utilizaran, al presentar las funciones locales (local functions, véase descripción en MSDN), lo que para mí es el ejemplo por excelencia de uso de las mismas. Después de darle vueltas al tema por un buen rato, he llegado a la conclusión de que probablemente todo es consecuencia de varias décadas de enseñanza de la programación utilizando lenguajes que no ofrecen (u ofrecían) la posibilidad de anidar funciones (léase Java, C++ y el propio C#). Allá por los años 80, la Universidad de La Habana y muchos otros centros docentes utilizaban como vehículo de iniciación el lenguaje Pascal, que siempre ofreció esa posibilidad; no creo que ninguno de mis antiguos alumnos se haya “escapado” de haber visto algún ejemplo de utilización de esta característica para acotar el ámbito (visibilidad) de un  procedimiento/función.

El patrón de utilización de funciones anidadas al que me refiero se presenta comúnmente al programar algoritmos basados en la estrategia “divide y vencerás”, y lo ejemplificaré aquí a través de una implementación del método QuickSort1 para ordenar un array de enteros en su sitio (in place). Al aplicar esta estrategia, aparecen funciones auxiliares cuyo ámbito natural es la rutina como parte de la cual han sido concebidos; muy frecuentemente estas funciones son recursivas. En el caso de QuickSort, cuya implementación muestro más abajo, esta posibilidad de anidamiento se presenta a varios niveles:

  • Al nivel más externo, la necesidad de ofrecer una implementación “limpia” nos exige exponer un método que solo requiera como parámetro el array a ordenar. Pero la naturaleza misma del algoritmo, como se describe a continuación, nos exige disponer de otra versión que reciba los índices inferior y superior sobre los que se va a actuar en el marco de una llamada cualquiera. Una función anidada es la solución ideal, dado que esta última versión no necesita ser expuesta al exterior (ni  siquiera otros métodos de la clase).
  • La idea central del algoritmo consiste en colocar de manera económica uno de los valores en el array en su posición final, con todos los valores menores que él a su izquierda y los mayores a su derecha (un proceso que se conoce como partición), para luego aplicar recursivamente la ordenación a los dos sub-arrays situados, respectivamente, a la izquierda y la derecha de ese elemento pivote. En nuestra implementación, la versión “interna” de QuickSort hace a su vez uso de una función local a ella, Partition, para hacer la partición del fragmento de array recibido.
  • Esta idea de descomposición funcional “hacia adentro” podría extenderse tanto como fuera necesario; a riesgo de lucir pedante, en el ejemplo he creado dentro de Partition una función Swap para intercambiar los valores de dos elementos del array, dados sus índices.

Observe el lector que el uso de funciones locales no solo produce un encapsulamiento más correcto del código, sino que además permite capturar en la función anidada los parámetros y variables locales de la función que la contiene, lo que se traduce tanto en economía de expresión como en mejoras en el rendimiento.

namespace Geeks
{
   public static class Utilities
   {
      public static void QuickSort(this int[] a)
      {
         void QuickSort(int first, int last)
         {
            int Partition()
            {
               void Swap(int p, int q)
               {
                  int tmp = a[p];
                  a[p] = a[q];
                  a[q] = tmp;
               }
 
               int pivot = a[first], index = first;
               Swap(index, last);
               for (int i = first; i < last; i++) 
                  if (a[i] < pivot) Swap(index++, i);
               Swap(index, last);
               return index;
            }

            if (first < last)
            {
               int pivotIndex = Partition();
               QuickSort(first, pivotIndex - 1);
               QuickSort(pivotIndex + 1, last);
            }
         }

         QuickSort(0, a.Length - 1);
      }
   }

   class Program
   {
      static void Main(string[] args)
      {
         var x = new int[] { 75824 };
         x.QuickSort();
      }
   }
}

1 Una descripción independiente del lenguaje de QuickSort puede verse aquí, y su implementación utilizando anidamiento aquí.


Referencia musical: Por allá por la segunda mitad de la década de los 70, cuando aún era un adolescente, un artista con el estrambótico nombre de Meat Loaf llamó poderosamente mi atención gracias a un peculiar estilo operístico, que combinaba el pop/rock tradicional con elementos de rock sinfónico. Con el tiempo, el disco “Bat Out of Hell” (1977) ha llegado a convertirse en uno de los diez más vendidos de todos los tiempos, y ha dado lugar a dos secuelas (también bastante exitosas) en 1993 y 2006. El tema “Alive” pertenece al tercer disco de la trilogía.

Acerca de “Solving Combinatory Problems with LINQ”

“I saw you, I knew you, I touched you
When the world was young …”
Jimmy Page & Robert Plant, “When the World Was Young” (1998)

Hace unos días, en el contexto de una conversación con un colega de trabajo, me acordé del artículo “Solving Combinatory Problems with LINQ“, que en su día me publicó gentilmente MSDN y aún sigue por ahí (también lo he copiado aquí, con el código listo para copiar y pegar). Sin duda alguna, y por una diferencia abismal (gracias, por supuesto, a Microsoft), es el texto más leído que haya escrito yo jamás, y en su momento dio lugar a discusiones como ésta.

Revisando el artículo al cabo de todo este tiempo, se me antoja ciertamente un poco naïve; me consuela la idea de que, al fin y cabo, eran tiempos en que “el mundo era joven” y LINQ acababa de nacer.


Referencia musical: Durante la década de los 90, los líderes del inolvidable Led Zeppelin, Jimmy Page y Robert Plant, publicaron dos discos que hicieron las delicias de los numerosos fans de la banda: “No Quarter” (1994) y “Walking into Clarksdale” (1998). “When the World Was Young” pertenece al segundo de esos trabajos.

Applying LINQ to new data types

[This article was originally published in MSDN C# Developer Center, February 2008]

Given the enormous expressive power that LINQ (Language Integrated Query) puts in the hands of developers, it is not surprising that we have started to search for ways to “LINQ-enable” more and more data types and technologies. As Dinesh Kulkarni humorously put it in this post, soon we will have even “LINQ to Coffee Machine” :-). .NET Framework 3.5 and C# 3.0 offer us several ways to achieve that goal.

In many occasions, all that is needed in order to be able to apply integrated queries to objects of a certain type (of our own, or belonging to the .NET Framework class library) is to define for the type one or more entry points which could serve as the generators to which all the basic object query machinery incorporated into .NET Framework (LINQ to Objects) can be applied. This has been, for instance, the approach used in LINQ to XML, where a set of iterators (implemented as extension methods) have been defined that produce subsets of the nodes that compose an XML document as IEnumerable<T> sequences; once you call any one of these methods, you obtain an XML node generator to which the predefined implementations of the standard query operators Where(), OrderBy(), etc. can be applied. LINQ to XML also introduces several specialized query operators (“extensions”), but that’s another story.

As an example of simple “LINQ activation” of classes, here we present the implementation of an extension that will allow us to use integrated query syntax over data received through a named pipe. Pipes are a well-known inter-process communication mechanism that has been in use since very long in the DOS/Windows world; but only with .NET Framework 3.5 we will be able to use them in our managed code applications without having to recur to platform invocation. Pipes can be anonymous, conceived to be used to communicate a parent process and a child process residing on the same machine; or named, which offer much more power and can be used over a network. Specifically, named pipes offer message-oriented communications.

The following program implements a server which sends UTF8-encoded string messages to its listener through a pipe named CS3:

using System;
using System.Text;
using System.IO;
using System.IO.Pipes;

namespace Demos
{
class Server
{
static void Main(string[] args)
{
const string PipeName = “CS3”;

using (NamedPipeServerStream pipeStream =
new NamedPipeServerStream(PipeName, PipeDirection.InOut,
1, PipeTransmissionMode.Message, PipeOptions.None))
{
pipeStream.WaitForConnection();

// sending messages
UTF8Encoding encoding = new UTF8Encoding();
for (int i = 1; i <= 1000; i++)
{
string msg = i.ToString();
byte[] bytes = encoding.GetBytes(msg);
pipeStream.Write(bytes, 0, bytes.Length);
}
}
}
}
}

The client, on the other end, composes received messages:

namespace Demos
{
class Client
{
static void Main(string[] args)
{
const string Server = “.”;
const string PipeName = “CS3”;

using (NamedPipeClientStream pipeStream =
new NamedPipeClientStream(Server, PipeName, PipeDirection.InOut))
{
pipeStream.Connect();
pipeStream.ReadMode = PipeTransmissionMode.Message;

Decoder decoder = Encoding.UTF8.GetDecoder();

const int BufferSize = 256;
byte[] bytes = new byte[BufferSize];
char[] chars = new char[BufferSize];
int numBytes = 0;
StringBuilder msg = new StringBuilder();
do
{
msg.Length = 0;
do
{
numBytes = pipeStream.Read(bytes, 0, BufferSize);
if (numBytes > 0)
{
int numChars = decoder.GetCharCount(bytes, 0, numBytes);
decoder.GetChars(bytes, 0, numBytes, chars, 0, false);
msg.Append(chars, 0, numChars);
}
} while (numBytes > 0 && !pipeStream.IsMessageComplete);
decoder.Reset();
if (numBytes > 0)
{
// we’ve got a message – process it
Console.WriteLine(msg.ToString());
}
} while (numBytes != 0);
}
Console.ReadLine();
}
}
}

What if the client process needed to filter, sort, group, etc. the received strings? Traditional coding approaches to implement these tasks could be applied, of course, but a more far-sighted approach would be to define a “LINQ entry point” in the form of an extension method for the NamedPipeClientStream class, so that it can be used as source for language integrated queries:

namespace PlainConcepts.Linq
{
public static partial class Extensions
{
public static IEnumerable<string> GetMessages(
this NamedPipeClientStream pipeStream)
{
pipeStream.Connect();
pipeStream.ReadMode = PipeTransmissionMode.Message;

Decoder decoder = Encoding.UTF8.GetDecoder();

const int BufferSize = 256;
byte[] bytes = new byte[BufferSize];
char[] chars = new char[BufferSize];
int numBytes = 0;
StringBuilder msg = new StringBuilder();
do
{
msg.Length = 0;
do
{
numBytes = pipeStream.Read(bytes, 0, BufferSize);
if (numBytes > 0)
{
int numChars = decoder.GetCharCount(bytes, 0, numBytes);
decoder.GetChars(bytes, 0, numBytes, chars, 0, false);
msg.Append(chars, 0, numChars);
}
} while (numBytes > 0 && !pipeStream.IsMessageComplete);
decoder.Reset();
if (numBytes > 0)
{
// we’ve got a message – yield it!
yield return msg.ToString();
}
} while (numBytes != 0);
}
}
}

Note that thanks to the use of an iterator, queries built around this extension method will take advantage of lazy evaluation, so that messages will be retrieved on demand, as they are needed by the client application.

With such an extension method at hand, we will be able to process messages received from a named pipe stream this way:

namespace Demos
{
using PlainConcepts.Linq;

class Client
{
static void Main(string[] args)
{
const string Server = “.”;
const string PipeName = “CS3”;

using (NamedPipeClientStream pipeStream =
new NamedPipeClientStream(Server, PipeName, PipeDirection.InOut))
{
var input = from s in pipeStream.GetMessages()
where string.Compare(s, “3”) < 0
orderby s
select s;
foreach (var s in input)
Console.WriteLine(s);
}
Console.ReadLine();
}
}
}

Processing messages this way can save us a lot of coding, making at the same time our code much more elegant and readable.

Download source code (VS 2010)

Simplificando la programación asíncrona

“Parallel our sights
And we will find, that we need to be where we belong
Parallel our heights
Display our rights and wrongs, and always keep it strong.”
(“Parallels”, Yes, 1977)

Después de un buen tiempo sin escribir, “rumiando” a cada rato contra la incorporación a C# 4 del tipado dinámico y toda la parafernalia asociada, a los que sigo aún sin encontrarles la “razón de estar” (ciertos anuncios recientes parecen hasta darme la razón), la presentación de la nueva Async CTP durante la PDC 2010 ha venido a insuflarme espíritu y confianza en que no todo está perdido y quedan muchas cosas interesantes aún por venir en relación con mi lenguaje favorito. Pero el lector no debería hacerme mucho caso en lo relativo a dynamic: creo que desde hace algún tiempo me estoy haciendo conservador (aunque, pienso, sin traspasar aún la delgada línea que separa “conservador” de “reaccionario” ;-). Es algo que pensé que jamás podría ocurrirme a mí, educado en la falacia bajo el signo de la “revolución interminable”; probablemente cosas de la edad :-).

En cuanto a la recién publicada Async CTP, pienso que se trata de una propuesta excelente, que simplificará en gran medida la programación asíncrona, cuya complejidad de implementación con la versión actual de C# es alta, algo de lo que puede dar fe cualquiera que se haya enfrentado al desarrollo de una aplicación medianamente “concurrente”. A través de la introducción de dos nuevas palabras reservadas, async y await, la programación asíncrona en futuras versiones de C# se hará casi tan clara y natural como la síncrona, dejando al compilador la tarea de generar prácticamente todo el código de fontanería asociado al tratamiento de los callbacks y aprovechando al máximo las bondades que ofrece la Task Parallel Library (TPL) introducida en .NET 4.0.

Para descargar la CTP y acceder a una gran cantidad de documentación y ejemplos (incluyendo un vídeo introductorio de Anders Hejlsberg), visite http://msdn.microsoft.com/en-us/async.

NOTA: Las opiniones reflejadas en este artículo son mías propias, y no han sido revisadas ni aprobadas por la empresa en la que trabajo.


Pop/Rock tip: Para esta ocasión, he utilizado un tema de uno de los “padres” del rock progresivo, Yes; una banda que dura ya más de 40 años, durante los cuales, a pesar de los numerosos cambios de personal, ha sido capaz de mantener en todo momento un altísimo nivel interpretativo. Mis álbumes favoritos de Yes son los pertenecientes al primer ciclo de la banda, uno de cuyos máximos exponentes es “Going for the One” (1977); álbum al que pertenece el tema “Parallels”.