Administración de memoria en Forth

Question

Así que estoy aprendiendo Forth y tenía curiosidad si alguien podría ayudarme a entender cómo funciona la administración de memoria en general. Por el momento, solo tengo (algo) de experiencia con el paradigma C stack-vs-heap.

Por lo que entiendo, se puede asignar en el diccionario, o en el montón. ¿Es el diccionario más rápido/preferido como la pila en C? Pero a diferencia de C, no hay alcances y reclamo automático de pila, por lo que me pregunto si uno solo usa el diccionario para las estructuras de datos globales (si es que lo hace).

Por lo que respecta al montón, ¿se parece mucho a C? ¿La gestión de heap es un concepto estándar (ANS) o está definida por la implementación?

Answer 1

No es diccionario, o en el montón: el equivalente del montón es el diccionario. Sin embargo, con la severa limitación de que actúa más como una pila que como un montón, se agregan nuevas palabras al final del diccionario (asignación por ALLOT y liberación por OLVIDE o LIBRE (pero liberando todas las palabras más nuevas - actuando más como múltiples COPs)).

Una implementación puede controlar el diseño de la memoria y así implementar un montón tradicional (o recolección de basura). Un ejemplo es A FORTH implementation of the Heap Data Structure for Memory Mangement (1984). Otra implementación es Dynamic Memory Heaps for Quartus Forth (2000).

Mucho depende de la implementación o de las extensiones. Por ejemplo, el diseño de la memoria suele ser con los dos almacenamientos intermedios de bloques (ubicación por BLOCK y TIB), el búfer de entrada de texto y valores y funciones de bajo nivel/primitivas del lenguaje, en la parte más baja, diccionario en el medio (creciendo hacia arriba)) y la pila de retorno y la pila de parámetros en la parte superior .

La dirección del primer byte disponible sobre el diccionario es devuelto por HERE (cambia a medida que el diccionario se expande).

También hay un área de scratchpad encima del diccionario (dirección devuelta por PAD) para almacenar datos temporalmente. El área del bloc de notas se puede considerar como memoria libre.

El modo de operación preferido es usar la pila tanto como sea posible en lugar de variables locales o un montón.

p. 286 (sobre una edición particular de Forth, MMSFORTH) en el capítulo "Memoria, diccionario y vocabularios de FORTH", Adelante: Un texto y una referencia. Mahlon G. Kelly y Nicholas Spies. ISBN 0-13-326349-5/0-13-326331-2 (pbk.). 1986 por Prentice-Hall.

Answer 2

Algunas implementaciones de Forth admiten variables locales en el marco de la pila de retorno y la asignación de bloques de memoria. Por ejemplo, en SP-Forth:

lib/ext/locals.f 
lib/ext/uppercase.f 

100 CONSTANT /buf 

: test (c-addr u --) { \ len [ /buf 1 CHARS + ] buf } 
    buf SWAP /buf UMIN DUP TO len CMOVE 
    buf len UPPERCASE 
    0 buf len + C! \ just for illustration 
    buf len TYPE 
; 

S" abc" test \ --> "ABC" 

Answer 3

Peter Mortensen lo puso muy bien. Agregaré algunas notas que podrían ayudar un programador de C un poco.

La pila está más cerca de lo que C denomina variables "automáticas", y lo que comúnmente se denominan variables locales. Puede dar los nombres de sus valores de pila en algunas versiones, pero la mayoría de los programadores intentan escribir su código para que no sea necesario nombrar los valores.

El diccionario se puede ver mejor como "datos estáticos" desde una perspectiva de programación C.Puede reservar rangos de direcciones en el diccionario, pero en general usará ALLOT y palabras relacionadas para crear estructuras de datos estáticos y grupos que no cambian de tamaño después de la asignación. Si desea implementar una lista enlazada que pueda crecer en tiempo real, es posible que tenga suficiente espacio para las celdas de enlace que necesitará y escriba palabras para mantener una lista gratuita de celdas desde donde puede dibujar. Hay implementaciones naturales de este tipo de cosas disponibles, y escribir las suyas es una buena manera de perfeccionar las habilidades de administración de punteros.

La asignación de montón está disponible en muchos adelantos modernos, y el estándar define ALLOCATE, FREE y RESIZE palabras que funcionan como malloc(), free() y realloc() en C. La memoria que devuelven proviene del sistema operativo Heap, y generalmente es una buena idea almacenar la dirección en una variable u otra estructura más permanente que la pila para que no pierda el puntero inadvertidamente antes de poder liberarla. Como nota al margen, estas palabras (junto con las palabras de E/S del archivo) devuelven un estado en la pila que no es cero si se produce un error. Esta convención se adapta muy bien con el mecanismo de manejo de excepciones, y le permite escribir código como:

variable PTR 
1024 allocate throw PTR ! 
\ do some stuff with PTR 
PTR @ free throw 
0 PTR ! 

O para una más compleja si ejemplo un tanto artificial de asignar/libre:

\ A simple 2-cell linked list implementation using allocate and free 
: >link (a -- a) ; 
: >data (a -- a) cell + ; 
: newcons (a -- a) \ make a cons cell that links to the input 
    2 cells allocate throw tuck >link ! ; 
: linkcons (a -- a) \ make a cons cell that gets linked by the input 
    0 newcons dup rot >link ! ; 
: makelist (n -- a) \ returns the head of a list of the numbers from 0..n 
    0 newcons dup >r 
    over 0 ?do 
    i over >data ! linkcons (a -- a) 
    loop >data ! r> ; 
: walklist (a --) 
    begin dup >data ? >link @   dup 0= until drop ; 
: freelist (a --) 
    begin dup >link @ swap free throw dup 0= until drop ; 
: unittest 10 makelist dup walklist freelist ; 

Answer 4

La cuestión fundamental puede no se han respondido de una manera que requiera un nuevo usuario de Forth, así que me echaré a correr.

La memoria en Forth puede ser muy dependiente del objetivo, por lo que limitaré la descripción al modelo más simple, que es un espacio de memoria plano, donde el código y los datos conviven felizmente. (a diferencia de los modelos de memoria segmentada, o memoria FLASH para código y RAM para datos u otros modelos más complicados)

El diccionario normalmente comienza en la parte inferior de la memoria y se asigna hacia arriba por el sistema Forth. Las dos pilas, en un sistema simple, existirían en alta memoria y típicamente tienen dos registros de CPU apuntando hacia ellas. (Muy dependiente del sistema)

En el nivel más fundamental, la memoria se asigna simplemente al cambiar el valor de la variable del puntero del diccionario. (a veces llamado DP)

El programador no suele acceder a esta variable directamente, sino que utiliza algunas palabras de nivel superior para controlarla.

Como mencionamos, la palabra 'AQUÍ' devuelve la siguiente dirección disponible en el espacio del diccionario. Lo que no se mencionó fue que AQUÍ se define obteniendo el valor de la variable DP. (Sistema de dependencia aquí, pero útil para una descripción)

En Forth 'aquí' podría tener este aspecto:

: AQUÍ (- addr) DP @;

Eso es todo.

Para asignar algo de memoria tenemos que mover AQUÍ hacia arriba y lo hacemos con la palabra 'ALLOT'.

La cuarta definición de 'ALLOT' simplemente toma un número de la pila de parámetros y lo agrega al valor en DP. Por lo tanto, no es más que:

: ALLOT (n -) DP +! ; \ '+!' agrega n a la variable de contenido DP

ALLOT es utilizado por el sistema FORTH cuando creamos una nueva definición para que lo que creamos esté seguro dentro de la memoria 'ALLOTed'.

Algo que no es inmediatamente obvia es la que ALLOT puede tomar un número negativo por lo que es posible mover el puntero de diccionario arriba o hacia abajo. Por lo que podría destinar parte de la memoria y volver así:

HEX 100 ALLOT

y liberarla así:

HEX -100 ALLOT

Todo esto para decir que este es el la forma más simple de administración de memoria en un sistema Forth. Un ejemplo de cómo esto se usa se puede ver en la definición de la palabra 'BUFFER:'

: tampón: (n -) CREATE ALLOT;

'BUFFER:' "crea" un nuevo nombre en el diccionario (create uses allot para hacer espacio para el nombre) y luego ALLOTs n bytes de memoria justo después del nombre y cualquier octetos de limpieza asociado a su sistema Forth utilizar

Así que ahora asignar un bloque de memoria llamado simplemente Tipo:

MARCADOR FOO \ marca de donde termina la memoria en este momento

HEX 2000 BUFFER: IN_BUFFER

ahora tenemos una 8K byte buffer c alled IN_BUFFER. Si quería recuperar ese espacio en la Norma Forth podríamos escribir 'FOO' y todo lo asignado en el Diccionario FOO después se retira del sistema Forth.

Pero si quieres espacio de memoria temporal, todo por encima de 'aquí' es libre de usar!

Entonces sólo tiene que apuntar a una dirección y utilizarlo si quieres que como este

: MYMEMORY aquí + 200; \ MyMemory puntos en la memoria no-asignado por encima de aquí

     \ MYMEMORY moves with HERE. be aware. 

MYMEMORY HEX 1000 ERASE \ llenan con 2K bytes de cero

Forth normalmente se ha utilizado para aplicaciones integradas de alto rendimiento, donde la asignación de memoria dinámica puede causar la ONU -código confiable por lo que se prefirió la asignación estática usando ALLOT. Sin embargo los sistemas más grandes tienen un montón y utilizan ASIGNAR, GRATIS y cambiar el tamaño al igual que utilizamos malloc etc en C.

BF

Answer 5

Con Forth entrar en un mundo diferente.

En un Forth típico como ciforth en Linux (y suponiendo 64 bits) puede configurar su Forth para tener un espacio de memoria lineal que es tan grande como su espacio de intercambio (por ejemplo, 128 Gbyte). Eso es tuyo para completar con matrices, listas vinculadas, imágenes de lo que sea. No hay restricciones Forth solo le proporciona un puntero AQUÍ para ayudarlo a realizar un seguimiento de la memoria que ha agotado. Incluso eso puede ignorar, y no hay ni siquiera una palabra en la norma 1994 que proporciona un espacio reservado que flota en la memoria libre (PAD).

¿Existe algo así como malloc() sin()? No necesariamente en un kernel pequeño de un par de docenas de kilobytes. Pero puede incluir un archivo con una utilidad de asignación y reservar un par de Gbyte para usar en la memoria dinámica.

Como ejemplo, actualmente estoy trabajando con archivos tiff. Una imagen típica de 140 Mbytes saca una pequeña porción del diccionario que avanza AQUÍ. Las filas de píxeles se transforman, descomprimen, etc. Para eso utilizo la memoria dinámica, por lo que ASIGNO el espacio para el resultado de descompresión de una fila. Tengo que volver a liberarlos manualmente cuando los resultados se hayan utilizado para otra transformación. Se siente totalmente diferente de c. Hay más control y más peligro.

Su pregunta acerca de los ámbitos, etc. En adelante, si conoce la dirección, puede acceder a la estructura de datos. Incluso si anotó F7FFA1003 en una hoja de papel. Intentar que los programas sean más seguros mediante espacios de nombre separados no es prominente en el estilo Forth. La llamada lista de palabras (ver también VOCABULARIO) proporciona facilidades en esa dirección.