Qué pregunta tan cargada. Pueden! Los métodos son incipientes y aún no se escalan, pero existen. Este es un campo de investigación muy interesante que se ha vuelto significativamente más activo recientemente: la síntesis de programas .
Por supuesto, todavía necesita alguna forma de decirle a la computadora qué escribir. Hay algunos enfoques diferentes: trabajar en un dominio restringido o consultar interactivamente al usuario o incluso simplemente tomar algún tipo de especificación lógica.
Si solo apunta a un dominio muy específico, puede generar automáticamente programas útiles sin mucha información. Un gran ejemplo es en el campo de la optimización de compiladores: escribir las diversas reglas de optimización de mirilla es una tarea difícil que generalmente realizan los expertos. Pero también está muy bien definido: solo tiene que escribir reglas que toman algún ensamblaje como entrada y asignarlo a un ensamblaje más eficiente que haga lo mismo. ¡Oye, resulta que puedes hacer que una computadora escriba estas reglas por ti! Echa un vistazo a la generación automática de superópticos de mirilla para un sistema que hace exactamente esto. Puede tardar mucho tiempo en ejecutarse, digamos semanas de tiempo de procesador, pero también ofrece muchas más reglas de optimización que los humanos. ¡Esto se traduce en mejoras reales en el optimizador generado sobre uno escrito por expertos! Incluso han utilizado este mismo enfoque para la traducción binaria: Traducción binaria usando superepéptidos de mirilla .
- Los matones rompieron mi computadora, ¿qué hago?
- ¿Cómo recupero archivos de una unidad flash USB?
- ¿Qué piensan los usuarios de diferentes distribuciones de Linux sobre Ubuntu?
- ¿Cómo puedo hacer una copia de seguridad de todos los datos de mi computadora portátil de la mejor manera posible?
- ¿Mi PC de repente se volvió lenta (cuando tiene temperatura media)?
Si desea un sistema más general para la escritura automática de algoritmos, puede solicitar interactivamente a un usuario entradas y salidas de muestra. Esto se llama “programación por ejemplo”. Un gran ejemplo es Flash Fill, que pasó de ser un proyecto de investigación de MSR a ser una característica en Excel 2013. Esto genera y ejecuta programas de manipulación de cadenas basados en datos en una hoja de cálculo. A menudo, solo uno o dos ejemplos son suficientes para generar un programa correcto; sin embargo, el sistema también puede solicitar al usuario entradas adicionales. Incluso lo hace de manera inteligente: utiliza algo de aprendizaje automático para adivinar qué entradas tienen más probabilidades de causar problemas y le pregunta al usuario sobre esas entradas. Ahora, en lugar de escribir este código de manipulación de cadenas manualmente, puede generarlo haciendo algunos ejemplos a mano. El mismo equipo de MSR también ha utilizado la síntesis del programa para muchas otras cosas interesantes.
Los dos enfoques anteriores pueden escalar relativamente bien y requieren una entrada limitada del usuario; en ambos casos, esto funciona porque apuntan a dominios muy especializados. Sin embargo, también hay enfoques más generales. Un ejemplo es Program Synthesis by Sketching , un enfoque que utiliza técnicas de síntesis para llenar los “agujeros” en los programas. Escribes un resumen de tu programa, pero dejas fragmentos difíciles para el sintetizador. En la práctica, también debe especificar lo que está buscando, que puede ser un conjunto de casos de prueba para pasar o un algoritmo escrito ingenuamente. Por ejemplo, supongamos que desea escribir una transposición matricial eficiente utilizando la instrucción SIMD. Primero, escribe una especificación no optimizada:
int [16] transposición (int [16] M) {
int [16] T = 0;
para (int i = 0; i <4; i ++)
para (int j = 0; j <4; j ++)
T [4 * i + j] = M [4 * j + i]
volver T
}
A continuación, descubres la estructura aproximada del código. En particular, la idea es que podemos usar la instrucción shufps para mezclar primero la matriz de entrada en una matriz temporal S y barajar S en T. La instrucción shufps toma tres argumentos: dos vectores de cuatro números y un vector de bits que controlan cómo se barajan. . Resolver estos argumentos es muy difícil, ¡pero felizmente el sintetizador puede hacerlo por usted! Simplemente escriba la estructura general del código, dejando (??) para agujeros:
int [16] transpose_simd (int [16] M) implementa la transposición {
int [16] S = 0, T = 0;
repetir (??) S [?? :: 4] = shufps (M [?? :: 4], M [?? :: 4], ??);
repetir (??) T [?? :: 4] = shufps (S [?? :: 4], S [?? :: 4], ??);
devolver T;
}
Aquí repeat es una directiva de sintetizador que le dice que copie la línea varias veces en lugar de usar un bucle; el ?? puede tomar diferentes valores cada vez que se copia la línea.
El sintetizador luego escupe el código correcto, lo que habría tomado una eternidad para escribir a mano:
int [16] transpose_simd (int [16] M) implementa la transposición {
int [16] = S = 0, T = 0;
S [4 :: 4] = shufps (M [6 :: 4], M [2 :: 4], 11001000b);
S [0 :: 4] = shufps (M [11 :: 4], M [6 :: 4], 10010110b);
S [12 :: 4] = shufps (M [0 :: 4], M [2 :: 4], 10001101b);
S [8 :: 4] = shufps (M [8 :: 4], M [12 :: 4], 11010111b);
T [4 :: 4] = shufps (M [11 :: 4], M [1 :: 4], 10111100b);
T [12 :: 4] = shufps (M [3 :: 4], M [8 :: 4], 11000011b);
T [8 :: 4] = shufps (M [4 :: 4], M [9 :: 4], 11100010b);
T [0 :: 4] = shufps (M [12 :: 4], M [0 :: 4], 10110100b);
devolver T;
}
Tomé este ejemplo de las diapositivas (http://www.cs.berkeley.edu/~bodi…) en un curso para programar síntesis que vale la pena leer.
Los sintetizadores pueden incluso crear sus propios algoritmos para problemas. Por ejemplo, comenzando con la función para la multiplicación de Montgomery de OpenSSL, un superoptimizador llamado STOKE escribió un programa x86_64 1.6 veces más rápido que GCC con -O3, ¡un poco más rápido que el ensamblaje escrito por expertos y usando un algoritmo diferente al de la entrada!
Esto es solo una muestra de herramientas de síntesis. Ya existen muchos y cada día salen más. En este momento, tienen un alcance limitado o solo pueden sintetizar pequeños programas, pero sus capacidades se están expandiendo rápidamente. Es un campo bastante emocionante.
