Управление памятью в Форт

Question

Так что я только изучаю Forth и мне было любопытно, если кто-нибудь мог бы помочь мне понять, как вообще работает управление памятью.На данный момент у меня есть только (некоторый) опыт работы с парадигмой C stack-vs-heap.

Из того, что я понимаю, можно выделить в Словаре или в куче.Словарь быстрее / предпочтительнее, чем стек в C?Но в отличие от C, здесь нет областей и автоматического восстановления стека, поэтому мне интересно, если использовать только словарь для глобальных структур данных (если вообще).

Что касается кучи,это очень похоже на C?Является ли управление кучей стандартной ( ANS ) концепцией или оно определяется реализацией?

Answer 1

Это не словарь, или куча - эквивалентом кучи является словарь. Однако, с жестким ограничением, что он действует больше как стек, чем куча - новые слова добавляются в конец словаря (выделение на ALLOT и освобождение на FORGET или FREE (но освобождает все новее) слова - действующие больше как несколько СОЗ)).

Реализация может управлять макетом памяти и, таким образом, реализовывать традиционную кучу (или сборку мусора). Примером является четвертая реализация структуры данных кучи для управления памятью (1984). Другая реализация - Динамическая куча памяти для Quartus Forth (2000).

Многое зависит от реализации или расширений. Например, структура памяти часто состоит из двух блочных буферов (расположение на BLOCK и TIB), буфера ввода текста и значений, а также низкоуровневых / примитивных функций языка, в нижней части словаря в середина (растёт вверх), стек возвратов и стек параметров наверху ¹ .

Адрес первого доступного байта над словарем возвращается HERE (он изменяется по мере расширения словаря).

Существует также область блокнота над словарем (адрес, возвращаемый PAD) для временного хранения данных. Область блокнота может рассматриваться как свободная память.

Предпочтительный режим работы - максимально использовать стек вместо локальных переменных или кучи.

¹ стр. 286 (о конкретном издании Forth, MMSFORTH) в главе «Память, словарь и словари FORTH», Forth: текст и ссылка. Махлон Дж. Келли и Николас Шпионы . ISBN 0-13-326349-5 / 0-13-326331-2 (pbk.). 1986 Прентис-Холл.

Answer 2

Фундаментальный вопрос, возможно, не был получен таким образом, как этого требовал бы новый пользователь Forth, поэтому я попробую.

Память в Forth может зависеть от цели, поэтому я ограничу описаниев простейшей модели - это плоское пространство памяти, в котором код и данные счастливо живут вместе.(в отличие от моделей с сегментированной памятью или флэш-памяти для кода и ОЗУ для данных или других более сложных моделей)

Словарь обычно начинается в нижней части памяти и выделяется системой Forth вверх.Два стека в простой системе должны существовать в старшей памяти и обычно иметь два регистра ЦП, указывающие на них.(Очень зависит от системы)

На самом фундаментальном уровне память выделяется просто путем изменения значения переменной указателя словаря.(иногда называемый DP)

Программист обычно не обращается к этой переменной напрямую, а использует некоторые слова более высокого уровня для управления ею.

Как уже упоминалось, слово Forth 'HERE' возвращает следующий доступный адресв словарном пространстве.Что не было упомянуто, так это то, что ЗДЕСЬ определяется путем извлечения значения переменной DP.(системная зависимость здесь, но полезно для описания)

В Forth 'ЗДЕСЬ' может выглядеть так:

: ЗДЕСЬ (- addr) DP @;

Вот и все.

Чтобы выделить немного памяти, нам нужно переместиться ЗДЕСЬ вверх и сделать это словом «ALLOT».

Определение Forth для «ALLOT» просто берет число из стека параметров идобавляет его к значению в DP.Так что это не более чем:

: ALLOT (n -) DP +!;\ '+!'добавляет n к переменной содержимого DP

ALLOT используется системой FORTH, когда мы создаем новое определение, чтобы то, что мы создали, было безопасно в памяти «ALLOTed».

То, что не сразу очевидно, это то, что ALLOT может принимать отрицательное число, поэтому можно перемещать указатель словаря вверх или вниз.Таким образом, вы могли бы выделить немного памяти и вернуть ее так:

HEX 100 ALLOT

И освободить ее так:

HEX -100 ALLOT

Все это говорит о том, что это самая простая форма управления памятью в системе Forth.Пример того, как это используется, можно увидеть в определении слова «BUFFER:»

: BUFFER: (n -) CREATE ALLOT;

'BUFFER:' 'создает' новое имя в словаре (кстати, create использует allot, чтобы освободить место для имени), затем ALLOTs n байтов памяти сразу после имени и любых связанных служебных байтов вашего Forthсистема может использовать

Так что теперь, чтобы выделить блок именованной памяти, мы просто набираем:

MARKER FOO \ отметьте, где память заканчивается прямо сейчас

HEX 2000 BUFFER: IN_BUFFER

Теперь у нас есть 8-байтовый буфер под названием IN_BUFFER.Если бы вы захотели освободить это место в стандарте Forth, мы могли бы напечатать 'FOO', и все, что выделено в Словаре после FOO, будет удалено из системы Forth.

Но если вам нужно временное пространство памяти, ВСЕ выше 'ЗДЕСЬ'можно использовать бесплатно!

Таким образом, вы можете просто указать адрес и использовать его, если вам это нравится

: MYMEMORY здесь 200+;\ MYMEMORY указывает на нераспределенную память выше ЗДЕСЬ

                        \ MYMEMORY moves with HERE. be aware.

MYMEMORY HEX 1000 ERASE \ заполнить ее нулевыми 2 КБ

Forth обычно используется для высокопроизводительных встроенных приложений, где динамическая памятьВыделение может вызывать ненадежный код, поэтому статическое распределение с использованием ALLOT было предпочтительным.Однако большие системы имеют кучу и используют ALLOCATE, FREE и RESIZE так же, как мы используем malloc и т. Д. В C.

BF

Answer 3

Питер Мортенсен изложил это очень хорошо. Я добавлю несколько заметок, которые могут помочь программисту Си.

Стек наиболее близок к тому, что С называет «автоматическими» переменными, и тем, что обычно называют локальными переменными. Вы можете давать имена стековых значений в несколько раз, но большинство программистов стараются написать свой код так, чтобы называть значения не нужно.

Словарь лучше всего рассматривать как «статические данные» с точки зрения программирования на Си. Вы можете зарезервировать диапазоны адресов в словаре, но в целом вы будете использовать ALLOT и связанные слова для создания статических структур данных и пулов, которые не меняют размер после выделения. Если вы хотите реализовать связанный список, который может увеличиваться в режиме реального времени, вы можете выделить ВСЕГО достаточно места для ячеек ссылок, которые вам понадобятся, и написать слова, чтобы поддерживать свободный список ячеек, из которых вы можете извлечь. Естественно, существуют реализации такого рода вещей, и написание собственного - хороший способ отточить навыки управления указателями.

Распределение кучи доступно во многих современных Forths, и стандарт определяет слова ALLOCATE, FREE и RESIZE, которые работают как malloc (), free () и realloc () в C. Возвращаемая память - из системной кучи ОС и, как правило, хорошей идеей является сохранение адреса в переменной или какой-либо другой более постоянной структуре, чем в стеке, чтобы вы случайно не потеряли указатель, прежде чем сможете его освободить. Как примечание, эти слова (вместе со словами ввода / вывода файла) возвращают состояние в стеке, которое ненулевое, если произошла ошибка. Это соглашение прекрасно согласуется с механизмом обработки исключений и позволяет писать код вроде:

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

Или для более сложного, хотя и несколько искусственного, примера выделения / освобождения:

\ 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

С Forth вы попадаете в другой мир.

В типичном Forth, таком как Ciforth в Linux (и при условии 64-битного), вы можете настроить Forth, чтобы иметь линейное пространство памяти, равное вашему пространству подкачки (например, 128 Гбайт). Это ваше, чтобы заполнить массивами, связанными списками, фотографиями, что угодно. Там нет никаких ограничений. Forth только предоставляет вам указатель ЗДЕСЬ, чтобы помочь вам отслеживать память, которую вы использовали. Даже то, что вы можете игнорировать, и в стандарте 1994 года есть даже слово, которое предоставляет пространство для царапин, которое плавает в свободной памяти (PAD).

Есть ли что-то вроде malloc () free ()? Не обязательно в маленьком ядре пару десятков килобайт. Но вы можете просто включить файл с утилитой allocate и выделить пару Гбайт для использования в качестве динамической памяти.

В качестве примера я сейчас работаю с TIFF-файлами. Типичная 140-мегабайтная картинка вынимает небольшой кусок из словаря, продвигаясь ЗДЕСЬ. Строки пикселей преобразуются, распаковываются и т. Д. Для этого я использую динамическую память, поэтому Я выделяю пространство для результата распаковки строки. Я должен вручную освободить их снова, когда результаты будут использованы для другого преобразования. Это совершенно не похоже на с. Здесь больше контроля и больше опасности.

Ваш вопрос о областях и т. Д. В Forth, если вы знаете адрес, вы можете получить доступ к структуре данных. Даже если вы набросали F7FFA1003 на листе бумаги. Попытка сделать программы более безопасными с помощью отдельных пространств имен не характерна для стиля Forth. Так называемый список слов (см. Также словарь) обеспечивает возможности в этом направлении.

Answer 5

Некоторые реализации Forth поддерживают локальные переменные в кадре стека возврата и выделения блоков памяти.Например, в 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"