¿Es posible que un lenguaje de programación basado en pila sea concurrente?

14

He estado leyendo sobre lenguajes de programación basados ​​en pila, como FORTH y Cat , y parece que dada su naturaleza, solo pueden ejecutar una acción a la vez, independientemente de su paradigma (FORTH es imprescindible mientras que Cat es funcional).

Un lenguaje imperativo modificaría la pila, y un lenguaje puramente funcional, como Joy , devolvería una nueva pila, pero el punto es que solo se usa una pila a la vez.

Entonces, ¿pueden los lenguajes de programación basados ​​en pila ser concurrentes? ¿Podrían lograr la concurrencia mediante el uso de múltiples pilas al mismo tiempo o algo similar?

¿Es posible implementar una evaluación diferida en un lenguaje de programación basado en pila?

Corríjame si no entiendo algo sobre los idiomas y conceptos mencionados anteriormente.

Armando H.
fuente
55
¿Cómo puede cualquier lenguaje imperativo ser concurrente?
Bergi
¿Realmente te refieres a la concurrencia (que no es tan difícil de lograr, solo usa múltiples hilos ejecutándose con pilas independientes más memoria compartida) o paralelismo?
Daniel Jour
@DanielJour si entiendo bien, el paralelismo significa ejecución simultánea, mientras que la concurrencia significa ejecución independiente, entonces sí, me refiero a la concurrencia. ¿Podría elaborar más sobre las pilas independientes para cada hilo?
Armando H.

Respuestas:

16

Entonces, ¿pueden los lenguajes de programación basados ​​en pila ser concurrentes?

Seguro.

¿Podrían lograr la concurrencia mediante el uso de múltiples pilas al mismo tiempo o algo similar?

Ya para los idiomas normales, el subprocesamiento múltiple generalmente significa tener múltiples pilas de "llamadas". Sería completamente natural dar a cada hilo su propia pila de datos. Sería sencillo tener un actor, digamos, cuyo cuerpo fue implementado por código en un lenguaje basado en la pila. El paralelismo explícito a las paranotaciones de la GHC debe ser razonablemente sencillo. El problema principal con la ejecución de cosas en paralelo es que no sabes cuál será el efecto de pila del código hasta que lo ejecutes. Sin embargo, usando una sintaxis similar a la Alegría, uno podría imaginarse [a b c] parejecutandoa b cya sea contra una pila vacía o una copia de la pila y solo manteniendo el elemento superior de la pila al finalizar (o presionando algún valor ficticio si la pila está vacía). Podrías imaginar variaciones. El paralelismo implícito sería más difícil de hacer ingenuamente en comparación con, por ejemplo, un lenguaje puramente funcional, pero ciertamente también podría hacerse. El código compilado de un combinador definido por el usuario a menudo no es muy diferente del código "normal".

¿Es posible implementar una evaluación diferida en un lenguaje de programación basado en pila?

Los efectos de pila desconocidos son nuevamente la parte difícil. Si diseña el lenguaje de manera que todos los efectos de la pila puedan determinarse estáticamente, entonces no parece demasiado difícil. Si tienes pereza, sé explícito, entonces también parece relativamente sencillo y se parecería más o menos a las citas de Joy y i. Un lenguaje que se llama a sí mismo un lenguaje concatenante perezoso parece hacer una mezcla de los dos enfoques anteriores de lo que puedo decir. Realmente no veo cómo un lenguaje de concatenación implícitamente vago funcionaría frente a los efectos dinámicos de la pila, al menos no de una manera vagamente utilizable, pero eso podría ser solo una falta de imaginación por mi parte.

Por cierto, no es raro que los lenguajes basados ​​en pila tengan múltiples pilas, por ejemplo, Forth tiene una pila de datos y una pila de retorno en la que también puede colocar datos arbitrarios.

Derek Elkins dejó SE
fuente
8

Sé un poco sobre FORTH, así que me limitaré a eso. Es un lenguaje de bajo nivel, que le brinda acceso como programador a todos los recursos de hardware. Entonces puedes hacer lo que quieras.

Concurrencia

Para tener programas en paralelo (editar: usado para decir programas concurrentes reales) necesita al menos dos unidades de ejecución (CPU-s). Sería bastante trivial implementar una palabra en FORTH que diga, por ejemplo, "ejecuta esta palabra en el procesador 2 usando estos dos argumentos". La palabra asignaría las dos pilas necesarias en el procesador 2 y comenzaría a ejecutar la palabra. Tendría que restringirse un poco en exactamente qué construcciones puede usar en ese programa.

Si el número de programas simultáneos es mayor que el número de unidades de ejecución, optaría por los programas "pseudo paralelos". Básicamente, hay dos formas de hacerlo: corutinas o multitarea preventiva. En cualquier caso, es posible (no es fácil, pero está bien descrito en la literatura) cómo lograr esto y FORTH le permite acceder a todas las cosas de bajo nivel que necesita.

Evaluación perezosa

Por supuesto, puede hacer esto en FORTH como en casi cualquier lenguaje de programación. No será tan elegante o "incorporado" como en decir Haskell. Usaré un ejemplo muy ingenuo.

La idea es que defina una "función" (usada libremente aquí) que devuelve un conjunto de cosas. Un ejemplo sería una función que devuelve todos los enteros. Luego realiza operaciones en este conjunto y cuando haya terminado, dé el resultado. Como ejemplo, es posible que desee sumar todos los enteros hasta que la suma sea mayor que 1000. Una evaluación no perezosa en primer lugar asignaría todos los enteros como un conjunto, lo cual es imposible ya que hay un número infinito de enteros. Entonces comenzaría a funcionar en este conjunto. Una implementación perezosa tendría una forma de "darme el siguiente valor en el conjunto". Hacer esto realmente solo necesita una variable en la función "último valor dado".

Haskell hace las cosas de esta manera. Por supuesto, maneja situaciones más complicadas, pero la idea es la misma. Endulza la evaluación de una manera que le permite a usted como programador concentrarse en el problema, no en cómo resolverlo.

ghellquist
fuente
44
"Para tener programas concurrentes reales, necesita al menos dos unidades de ejecución". Esto es simplemente un problema de implementación. Desde la perspectiva del lenguaje de programación, casi no hay diferencia entre dos subprocesos que se ejecutan en una sola CPU o en dos. En cierto sentido, cada hilo puede considerarse una 'unidad de ejecución' propia.
Lagarto discreto
1
A veces, los detalles de implementación deben tenerse en cuenta. Un ejemplo es cuando interactúa con el mundo real fuera de una computadora real. En tiempo real difícil, según "la respuesta correcta demasiado tarde es incorrecta", el tiempo puede ser diferente cuando compara la ejecución en dos unidades de ejecución con la ejecución entremezclada en una unidad.
ghellquist
A veces lo hacemos. Sin embargo, dudo que sea así. Por ejemplo, la pregunta no menciona los requisitos de programación en tiempo real.
Lagarto discreto
3
"Concurrencia"! = "Paralelismo". Se puede decir que varios subprocesos que se ejecutan en una máquina con una sola CPU se ejecutan simultáneamente entre sí, a pesar de que no se está procesando en paralelo.
Solomon Slow
Punto tomado sobre concurrencia vs paralelos. Cambiaré el texto.
ghellquist