Descartes en C# 7

“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, 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 
        {
            return int.TryParse(s, out int temp);
        }
        static bool IsValidInt7B(string s)  // C# 7
        {
            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: 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 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

“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 (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.

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í. 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)