Voy a ver si estos scripts de Alex Gorbatchev van bien. Si es así, voy a actualizar los mensajes del LISP para que queden más bonitos.
Desafortunadamente no consigo que escape solo. Habrá que usar el escape manual.
class prueba
{
void sintactica(int a, int b, int c)
{
for(int x=a; x<b; x+=c)
std::cout << x << std::endl;
}
};
Continuamos con el intérprete LISP. Esta vez vamos a hablar más tranquilamente de las formas aplicativas y la evaluación.
Representando expresiones S con celdas
De las celdas vistas, no todas se usan para las expresiones S.
En general, si queremos calcular algo tenemos que escribirlo. Y, de lo que tengo escrito, tendré que calcular lo que desconozco. En esos cálculos usaré herramientas accesorias que no se pueden calcular de por sí (entornos y formas aplicativas).
La evaluación en LISP
Hay cuatro tipos de celdas en LISP según cómo se evalúan. Generalmente, lo que se puede evaluar es lo que puedes escribir como una expresión S y quieres saber su valor (de ahí lo de evaluar). Si no lo puedes escribir como una expresión S, no se puede evaluar.
Un poco de código
No vamos a profundizar más por ahora. Tendremos tiempo para hablar de qué se evalúa a qué. Ahora vamos a relajarnos un poco con unas pocas definiciones de código. A ver cómo hacemos una celda del montículo.
Vamos a usar un diseño a lo C. Es decir, una unión y muchos switch. Eso sí, lo meteremos todo en una clase de C++.
class Cell
{
public:
enum CELL_TYPE
{
CT_UNUSED, CT_EMPTY, CT_PAIR, CT_INTEGER, CT_REAL
, CT_STRING, CT_BOOLEAN, CT_NAME
, CT_ENVIR, CT_LAMBDA, CT_NATIVE
};
protected:
CELL_TYPE cell_type;
union
{
///CT_PAIR data
struct
{
Cell* head;
Cell* tail;
};
///CT_INTEGER data
INTEGER integer;
///CT_REAL data
REAL real;
///CT_BOOLEAN data
BOOLEAN boolean;
///CT_NAME data
///CT_STRING data
STRING string_idx;
///CT_ENVIR
Environment* environment;
///CT_LAMBDA
Lambda* lambda;
///CT_NATIVE
NATIVE native;
} value;
};
Como se vé, aún quedan por definir muchos tipos, pero la idea está clara: según la celda que tengamos en cell_type, podremos usar unos u otros valores de la unión value. Por ejemplo, un CT_INTEGER puede usar value.integer.
Voy a empezar una serie de entradas en el blog sobre cómo hacer un intérprete de LISP. Va a ser un intérprete minimal. Ni mucho menos compatible con ningún dialecto LISP. Sin embargo, va a permitirnos comprender cómo funciona por dentro el LISP.
Homoiconicidad y celdas
La homoiconicidad significa que el programa va a ser un valor en el propio lenguaje. El LISP es homoicónico. Vamos a definir los valores con los que trabaja el LISP y cómo se representan los programas con ellos.
Un valor en LISP es una celda. Las celdas son inmutables. Es decir, una vez que tienen un valor no lo pueden cambiar. Por otra parte las celdas pueden hacer referencia a otra celdas de esta manera podemos construir listas.
Los tipos de celda con los que vamos a trabajar son:
Edit: Distingo CT_LAMBDA y CT_NATIVE para hacer las cósas más fáciles luego en el código fuente.
El montículo (heap) y la recolección de basura
El montículo no es más que el conjunto de celdas con el que estamos trabajando. Cualquier celda referenciada estará en el montículo.
El montículo también tiene dos importantes misiones: crear celdas cuando hacen falta y destruirlas cuando no.
Un ejemplo de montículo podría ser.
La celda 1 representa la lista (30 "hola"). La celda 3 representa la lista ("hola"). La celda 2 representa el valor entero 30. Y así.
Las expresiones
Finalmente cerramos el círculo de la homoiconicidad. Ya hemos visto algunas expresiones que representan listas y enteros. Estas expresiones se denominan expresiones S (S-expressions). Una expresión S es...
Como ya adelantamos las expresiones son valores. De hecho, cada regla de construcción de una expresión se corresponde a una celda. La excepción es la lista que es una cadena de pares. La forma de generar la lista con los pares es mediante binarización.
En algunas variantes de LISP se expresan los pares entre corchetes []. Usaremos esta notación para facilitar ver cómo se convierte una lista a una cascada de pares. Una lista (1 2 3) se representra mediante [1 [2 [3 ()]]]. Ahora sí, cada par se corresponde a una celda.
La celda 1 del montículo de arriba era la lista (30 "hola") que si escribimos como pares sería [30 ["hola" ()] ].
Leo en varios sitios que Google ha publicado un nuevo lenguaje de programación al que ha llamado Go.
Visión preliminar
Las principales características son:
Es de la familia del C, aunque las declaraciones de variables van al revés y los tipos merecen mención aparte. Además, simplifica algo la sintaxis del C quitando cosas que sobraban (como los paréntesis del if).
El diseño del lenguaje se orienta a la compilación rápida. Es lo que más resaltan los autores. A cambio, el lenguaje es muy simple y carece de muchas cosas como excepciones o tipos paramétricos (programación genérica). Tampoco tiene sobrecarga de funciones u operadores. Aunque es un lenguaje orientado a objetos, no tiene herencia.
Usa recolección de basura aunque no es un lenguaje que funciones sobre máquina virtual.
Tiene instrucciones específicas para el paralelismo: canales y forks. Sin embargo, no tiene más soporte. No hay forma de verificar o comprobar que el programa concurrente que escribes va a funcionar.
Algunos de sus tipos de datos predefinidos son complejos: arreglos, cadenas y mapas.
Se usa la capitalización de los identificadores para introducir información semántica (exportado de símbolos).
El sistema de tipos
Merece mención especial el sistema de tipos. Es orientado a objetos, pero no tiene herencia. ¿Cómo puede ser?
Bien, es sorprendente, pero funciona y muy bien. El truco está en usar en vez de un orden parcial de herencia, usa el retículo de subconjuntos. Me explico. Cuando en un lenguaje orientado a objetos como el C++ o el Java decimos
class D : B { }
Estamos dándole dos piezas de información al compilador. La primera es que todos los miembros que tenga B los va a tener D. La segunda es que donde pueda usar B puedo usar D.
Sin embargo, la segunda se puede extraer de la primera. Puedo usar D en B porque D tiene todos los miembros de B. Así pues, si otra clase X tiene todos los miembros de B ¡también podré usarla! Esto es lo que se denomina duck typing.
Otro aspecto interesante del sistema de tipos es que los métodos se definen fuera de los tipos. De esta manera se pueden añadir métodos a tipos ya definidos, de forma similar a los extension methods de C#. Según los autores, esta forma de trabajar es ortogonal (métodos por un lados, composición de la clase por otro) y aumenta tanto el rendimiento como los tiempos de compilación.
Finalmente, y debido a que no hay herencia, han introducido un pequeño truco. Cuando una estructura (o clase sin métodos) usa otro tipo como componente, puede usarse anónimamente de forma que se importan todos sus métodos a la estructura.
type X struct {
Y; //<----
a float;
}
Como X tiene un componente anónimo de tipo Y, todos los miembros de Y pasan a X. Esto se usa en los punteros de forma que todos los miembros del tipo apuntado pasan al puntero. No hace falta entonces usar * ni ->. Me queda por descubrir cómo distingue entre copiar un puntero y copiar el objeto referenciado por el puntero.
Leo desde LtU un ensayo de W.R.Cook que explica por qué un objeto no es un tipo abstracto de datos (TAD o ADT en inglés).
Resumiendo las diferencias sería:
En general, si mi comprensión no ha fallado, los TAD ocultan la representación y muestran las operaciones. Los objetos muestran la representación y ocultan las operaciones (que pasan a ser parte de la representación via vinculación dinámica).
Viendo esta entrevista con John Hughes (creador de QuickCheck) me he quedado pensando sobre el último párrafo.
If you compare Haskell programs to C code or even C++ often, they are about an order of magnitude smaller and simpler. The same is for Erlang, those results are being validated in the industry. Where is the next order of magnitude coming from? I wish I had an answer to that question because it's hard to see almost. When you look at a beautiful Haskell program, how could this be 10 times shorter? But I think we need to be asking ourselves that kind of question. If I had a good idea there, I would spend the rest of my career working on it.
Realmente parece difícil reducir más un programa Haskell, como por ejemplo su versión de quick sort.
qsort [] = []
qsort (x:xs) = qsort (filter (<>= x) xs)
Comparada con la de C...
void qsort(int a[], int lo, int hi) {
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);
a[hi] = a[l];
a[l] = p;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
¿De dónde va a salir el siguiente orden de magnitud?
Programación genérica
La programación genérica se basa en el uso de tipos paramétricos. Esto se consigue diciendo cosas como "una lista de enteros" o "una lista de cadenas". De forma usual esto se escribe
list<int>
list<string>
Generics
Ahora bien, el significado de estos tipos puede ser distinto. En Java (y en parte en C#) lo que se hace es borrar el tipo y usar el tipo objeto.
list<int> ----> list<object>
list<string> -----> list<object>
A cambio, el compilador comprueba los tipos e introduce las conversiones convenientes en cada caso. De esta forma hay seguridad en el uso de los tipos aunque realmente estemos trabajando sobre objetos genéricos. De ahí el nombre de estos tipos: tipos genéricos (generics).
Templates
En C++ los tipos no se borran, lo que se hace es generar un tipo nuevo a partir de un patrón. Así una lista de algo no es un tipo completo en C++ es un patrón. De ahí el nombre: patrones (templates).
list<X> ----> class { void insert(X x) {..} ..}
list<int> ----> class { void insert(int x) {..} ..}
list<string> ----> class { void insert(string x) {..} ..}
Obviamente esto es mucho más pesado para el compilador que requiere crear estos tipos. Por esta razón las compilaciones de C++ son mucho más largas que las de C# o las de Java. Realmente son macros que expanden el código a compilar.
Comparativa
Esta diferencia hace que existan casos no intuitivos. Por ejemplo, en Fabulous Adventures In Coding Eric Lippert nos muestra el siguiente ejemplo en C#.
public class C
{
public static void DoIt<T>(T t) {ReallyDoIt(t);}
private static void ReallyDoIt(string s)
{System.Console.WriteLine("string");}
private static void ReallyDoIt<T>(T t)
{System.Console.WriteLine("everything else");}
}
Si llamamos a C.DoIt<string> el compilador de C# borra el tipo (generics, no templates) y cuando llama a ReallyDoIt(t) es un object por lo que el resultado es "everything else".
