Forth
http://www.fforum.winglion.ru/

локальные фреймы данных
http://www.fforum.winglion.ru/viewtopic.php?f=25&t=2354
Страница 1 из 3

Автор:  mOleg [ Вс дек 20, 2009 22:42 ]
Заголовок сообщения:  локальные фреймы данных

в Форте существует слово PICK , позволяющее положить на вершину стека данных копию значения, лежащего глубоко под вершиной стека. Практика его использования показала, что механизм неудобный, постоянное перемещение вершины указателя стека данных приводит к необходимости постоянного "пересчета" местоположения данных, а получаемые алгоритмы очень запутаны и практически не модифицируемы. В итоге, использование слова PICK стало неким нехорошим правилом. В результате в Форте сложилась ситуация, когда работать можно только с тремя - четырьмя числами на вершине стека данных, что с одной стороны не плохо, так как заставляет (принуждает) писать короткие определения, а с другой стороны усложняет работу программиста на алгоритмах, работающих с большим количеством данных.

Для примера можно взять какую-нибудь форумулу: y = (a+b)*(b+c)*(a+c)
видно, что каждый из параметров используется дважды. Предположим, что числа лежат на стеке данных ( a b c --> y ), код будет выглядеть следующим образом(без использования PICK):
: f ( a b c --> y ) 
DDUP + \ a b c b+c
>R ROT TUCK + \ b a c+a
>R + R> * R> *
;

похожим образом с использованием PICK
: f ( a b c --> y )
DDUP + \ a b c b+c
>R 2 PICK + \ a b c+a
>R + R> * R> *
;

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

Решений у проблемы было найдено несколько. Одним из стандартных решений стало использование локальных переменных:
: f { a b c }
a b + b c + a c + * *
;

что выглядит значительно лучше.
Однако локальные переменные работают не самым лучшим образом.
В первую очередь, локальные данные хранятся на вершине стека данных, а это значит, что действительны только внутри одного определения. Во-вторую очередь, каждый используемый локальный параметр переносится на стек возвратов, что отнимает время.
Кроме того, сами по себе локальные переменные реализуются достаточно сложным образом. Ну и использование стека возвратов тоже не слишком приятно. Локальные переменные в таком виде выглядят несколько инородными и черезмерно сложными в реализации.

Другие решения конечно же есть. Например, стековые фреймы Хищника.
Идея здравая (хотя признаюсь, сразу я ее не понял, каюсь).

А действительно, зачем пермещать данные на стек возвратов? зачем лишние движения, когда можно несколько модифицировать работу PICK убрав известные существующие в нем проблемы!
Для этого нужно, чтобы PICK работал не относительно подвижной вершины стека данных, а относительно какого-то другого перегружаемого указателя. То есть напрашивается примерно следующий код:

USER-VALUE marker

\ запомнить начало текущего фрейма в пользовательскую переменную
: PIN ( --> ) SP@ TO marker ;

\ определить адрес элемента относительно начала фрейма данных
: ITEM ( ix # --> ix n ) CELLS marker SWAP - @ ;

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

Уже лучше, механизм проще, данные не перемещаются, сложная библиотека не нужна, и работать с параметрами можно внутри любого определения. НО! механизм нельзя использовать во вложениях, то есть нереентерабелен, что несомненно плохо.

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

Но еще один стек заводить не хочется!
Да и возможность использовать механизм фреймов данных во вложенных определениях (то есть не на одном уровне) несколько сомнительна и черевата отчаянными "зевами". Значит можно попробовать обойтись без дополнительного стека данных:

USER marker

\ запомнить текущий указатель стека данных в переменную marker
\ для последующей работы с данными, адресуемые от этого указателя
: pin ( --> )
SP@ marker ACHANGE
AR> SWAP A>R JUMP ;

\ удалить указатель на локальный фрейм
: sever ( --> ) AR> AR> marker A! JUMP ;

\ вернуть адрес локальной переменной
: item ( # --> addr ) CELLS marker A@ SWAP - ;


Вот такие мысли.
P.S.
да, стоит добавить, что введение дополнительного стека плохо еще и тем, что отражается на работе механизма CATHC THROW , то есть работы с исключениями. А именно: необходимо модифицировать эти слова таким образом, чтобы отслеживалась актуальная глубина стек указателей фреймов на момент каждого отката. Поэтому использование стека возвратов видится более подходящим для сохранения старых значений.

Автор:  вопрос [ Вс дек 20, 2009 22:57 ]
Заголовок сообщения: 

Цитата:
USER-VALUE marker

явно что-то не то
из стандартa
Цитата:
6.2.1850 MARKER CORE EXT
( "<spaces>name" -- )
Skip leading space delimiters. Parse name delimited by a space. Create
a definition for name with the execution semantics defined below.
name Execution: ( -- )
Restore all dictionary allocation and search order pointers to the state
they had just prior to the definition of name. Remove the definition of
name and all subsequent definitions. Restoration of any structures
still existing that could refer to deleted definitions or deallocated
data space is not necessarily provided. No other contextual information
such as numeric base is affected.
See: 3.4.1 Parsing, 15.6.2.1580 FORGET.

Автор:  mOleg [ Вс дек 20, 2009 23:10 ]
Заголовок сообщения: 

вопрос писал(а):
явно что-то не то

из стандартa

Цитата:6.2.1850 MARKER

на стандарт забей, он тут не причем.
Форт различает регистр, поэтому MARKER <> marker

Автор:  dynamic-wind [ Вс дек 20, 2009 23:38 ]
Заголовок сообщения: 

етить! фортерами изобретен frame pointer!

pin:
push ebp
mov ebp,esp

item:
mov eax,[ebp+eax]

sever:
mov esp,ebp
pop ebp

Автор:  mOleg [ Вс дек 20, 2009 23:45 ]
Заголовок сообщения: 

dynamic-wind писал(а):
етить! фортерами изобретен frame pointer!

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

Автор:  Hishnik [ Вс дек 20, 2009 23:45 ]
Заголовок сообщения: 

frame pointer за ненадобностью обычно не реализуется. Но что он есть, фортер не может не знать.

Автор:  mOleg [ Пн дек 21, 2009 00:20 ]
Заголовок сообщения: 

dynamic-wind писал(а):
етить! фортерами изобретен frame pointer!

да, забыл сказать, что по сути такая работа с данными чужда Форту.
Стек не всегда доступен на чтение в глубину, и фреймы данных ни на одном из стеков просто не получится (и форт без этого механизма прекрасно обходится). Данный вопрос больше актуален для оптимизации работы с данными на регистровых архитектурах.

Автор:  mOleg [ Пн дек 21, 2009 23:28 ]
Заголовок сообщения: 

да, стоит добавить, что введение дополнительного стека плохо еще и тем, что отражается на работе механизма CATHC THROW , то есть работы с исключениями. А именно: необходимо модифицировать эти слова таким образом, чтобы отслеживалась актуальная глубина стек указателей фреймов на момент каждого отката. Поэтому использование стека возвратов видится более подходящим для сохранения старых значений.

Автор:  mOleg [ Ср дек 23, 2009 23:01 ]
Заголовок сообщения: 

так, возник вопрос, который не могу решить, а именно, в какую сторону надо отсчитывать значения для item
вариантов-то всего два:
от места метки в глубину, то есть, предполагается, что данные уже лежат на стеке,
от места метки вверх, то есть предполагается, что данных еще нет.

Автор:  вопрос [ Чт дек 24, 2009 00:45 ]
Заголовок сообщения: 

исходить из здравого смысла - обе

Автор:  Hishnik [ Чт дек 24, 2009 15:56 ]
Заголовок сообщения: 

mOleg писал(а):
так, возник вопрос, который не могу решить, а именно, в какую сторону надо отсчитывать значения для item
вариантов-то всего два:
от места метки в глубину, то есть, предполагается, что данные уже лежат на стеке,
от места метки вверх, то есть предполагается, что данных еще нет.

А все сведется к тому, какой знак будут иметь индексы.

Автор:  mOleg [ Чт дек 24, 2009 20:07 ]
Заголовок сообщения: 

Хищник писал(а):
А все сведется к тому, какой знак будут иметь индексы.

угу, и запрещать ли отрицательные смещения.

Автор:  mOleg [ Сб мар 17, 2012 19:31 ]
Заголовок сообщения:  Re: локальные фреймы данных

продолжаемс
source file: loc.fts
\ 01.11.2011 ~mOleg
\ Copyright [C] 2011 _Harry , mOleg mOlegg@ya.ru
\ низкоуровневая поддержка работы с лок. переменными с стеке данных

\ при вызове удаляет указатель на кадр данных
: fex ( r: n --> ) [ 0x5A B, ] ;

\ запоминает текущий указатель на вершину стека данных в стеке возвратов,
\ как начало кадра данных
: {{ ( --> r: addr 'fex )
[ 0x5B B,
0x8D B, 0x55 B, 0xFC B,
0x52 B,
0x68 B, ' fex , \ удаление указателя по EXIT
0xFF B, 0xE3 B, ] ;

\ удаляет с вершины стека возвратов 'fex и адрес кадра данных
: }} ( r: addr 'fex --> )
[ 0x5B B, 0x5A B, 0x5A B,
0xFF B, 0xE3 B,
0xCC B, 0xE3 B, ] ;

\ возвращает адрес внутри кадра данных со смещением,
\ скомпилированным в коде за {*}
: {A} ( --> addr )
[ 0x8D B, 0x6D B, 0xFC B,
0x89 B, 0x45 B, 0x00 B,
0x5B B,
0x8B B, 0x03 B,
0x8B B, 0x54 B, 0x24 B, 0x04 B,
0x8D B, 0x04 B, 0x10 B,
0x8D B, 0x5B B, 0x04 B,
0xFF B, 0xE3 B,
] ;

\ возвращает значение, хранимое внутри кадра данных
\ со смещением, скомпилированным в коде за {^}
: {@} ( --> )
[ 0x8D B, 0x6D B, 0xFC B,
0x89 B, 0x45 B, 0x00 B,
0x5B B,
0x8B B, 0x03 B,
0x8B B, 0x54 B, 0x24 B, 0x04 B,
0x8B B, 0x04 B, 0x10 B,
0x8D B, 0x5B B, 0x04 B,
0xFF B, 0xE3 B,
] ;

\ сохраняет значение n внутрь кадра данных
\ со смещением, скомпилированным в коде за {#}
: {!} ( n --> )
[ 0x5B B,
0x8B B, 0x13 B,
0x03 B, 0x54 B, 0x24 B, 0x04 B,
0x89 B, 0x02 B,
0x8B B, 0x45 B, 0x00 B,
0x8D B, 0x6D B, 0x04 B,
0x8D B, 0x5B B, 0x04 B,
0xFF B, 0xE3 B,
] ;

\ вызывает xt, адрес которого находится внутри кадра данных
\ со смещением, скомпилированным в коде за {e}
: {E} ( --> )
[
0x8D B, 0x6D B, 0xFC B,
0x89 B, 0x45 B, 0x00 B,
0x5B B,
0x8B B, 0x13 B,
0x03 B, 0x54 B, 0x24 B, 0x04 B,
0x8D B, 0x5B B, 0x04 B,
0x53 B,
0x8B B, 0x45 B, 0x00 B,
0x8D B, 0x6D B, 0x04 B,
0xFF B, 0x22 B,
] ;

?ABSENT test{ \EOF -- тестовая секция ---------------------------------------
test{

util/ stest.fts


: t0 1 2 3 4 {{ {A} [ 4 , ] @ {A} [ 0 , ] @ {A} [ 8 , ] @ {A} [ 12 , ] @ }} ;
: t1 1 2 3 4 {{ {@} [ 4 , ] {@} [ 0 , ] {@} [ 8 , ] {@} [ 12 , ] }} 333 ;
: t2 1 2 3 4 {{ 123 {!} [ 4 , ] 345 {!} [ 0 , ] 567 {!} [ 12 , ] 789 {!} [ 8 , ] }} 555 ;

:> aaa 1234 ;
:> bbb 3456 ;
:> ccc 6789 ;

: t3 aaa bbb ccc {{ {E} [ 0 , ] {E} [ CELL , ] {E} [ 2 CELLS , ] }} 8901 ;

D( t0 --> 1 2 3 4 3 4 2 1 )D
D( t1 --> 1 2 3 4 3 4 2 1 333 )D
D( t2 --> 567 789 123 345 555 )D
D( t3 --> aaa bbb ccc 6789 3456 1234 8901 )D

}test


\EOF
\ при вызове удаляе указатель на кадр данных
CODE fex ( r: n --> )
rpop temp
exit
END-CODE unfeasible

\ запоминает текущий указатель на вершину стека данных в стеке возвратов,
\ как начало кадра данных
CODE {{ ( --> r: addr )
rpop addr
LEA temp , -CELL [top]
rpush temp \ указатель на кадр
rpush # t' fex \ контроль выхода по EXIT
JMP addr
END-CODE

\ удаляет с вершины стека возвратов 'fex и адрес кадра данных
CODE }} ( r: addr --> )
rpop addr
rpop temp
rpop temp
JMP addr
END-CODE

\ вернуть адрес внутри кадра данных со смещением, скомпилированным в коде за {*}
CODE {A} ( --> addr )
dpush tos
rpop addr
MOV tos , [addr]
MOV temp , CELL [rtop]
LEA tos , [tos] [temp]
LEA addr , CELL [addr]
JMP addr
END-CODE

\ вернуть значение, хранимое внутри кадра данных
\ со смещением, скомпилированным в коде за {^}
CODE {@} ( --> n )
dpush tos
rpop addr
MOV tos , [addr]
MOV temp , CELL [rtop]
MOV tos , [tos] [temp]
LEA addr , CELL [addr]
JMP addr
END-CODE

\ сохраняет значение n внутрь кадра данных
\ со смещением, скомпилированным в коде за {#}
CODE {!} ( n --> )
rpop addr
MOV temp , [addr]
ADD temp , CELL [rtop]
MOV [temp] , tos
dpop tos
LEA addr , CELL [addr]
JMP addr
END-CODE

\ вызвать xt, адрес которого находится внутри кадра данных
\ со смещением, скомпилированным в коде за {e}
CODE {E} ( --> )
dpush tos
rpop addr
MOV temp , [addr]
ADD temp , CELL [rtop]
LEA addr , CELL [addr]
rpush addr
dpop tos
JMP [temp]
END-CODE


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

Автор:  gudleifr [ Сб мар 17, 2012 20:19 ]
Заголовок сообщения:  Re: локальные фреймы данных

когда я был молодой и глупый, я тоже писал подобную хрень:
Код:
                                                  Screen 9
  0 N.( Стековые списки ARENE: связь+данные)
  1 VARIABLE ARENE
  2 \ New: Stack <= Arene; Arene <- Stack; Stack <= N(0);
  3 : ARENE-NEW ( N->SA,N*0) SP@ ARENE @ >R ARENE ! R> SWAP
  4  0 DO 0 LOOP ;
  5 \ Free: Stack <- Arene; Arene <= Stack;
  6 : ARENE-FREE ( SA,...->) ARENE @ SP! ARENE ! ;
  7 : (ARENE) ( N->SA) 2* ARENE @ + ;
  8 : ARENE@ ( N->W) (ARENE) S@ ; : ARENE! ( W,N->) (ARENE) S! ;
  9 \ Link: Stack <= Arene[N1]; Arene[N1] <- Stack; Stack <= N2(0);
10 : ARENE-LINK ( N1,N2->SA,N1*0) >R >R R@ ARENE@ SP@ R> ARENE!
11  R> 0 DO 0 LOOP ;
12 \ List: For(; SA; CFA(SA), SA <- Stack[SA-2]);
13 : ARENE-LIST ( CFA,SA->) BEGIN ?DUP WHILE 2DUP
14  S@ SWAP EXECUTE ( W->) 2- S@ REPEAT DROP ;
15                                                                 Ok
Но практика показала, что двух проектов, для которых подобная хрень будет выглядеть одинаково, нет. Например, сейчас, когда я гружу в стек параметры для Win-подпрограмм (включая структуры), ARENE используется совсем для другого - обрамления Win-вызова:
Код:
\ ФОРМИРОВАНИЕ КАДРА СТЕКА
CODE SP@ ( -- wa) B PUSHR, /DW MOV, B SP [RG] NEXT, END-CODE
CODE SP! ( ..., wa -- ) /DW MOV, SP B [RG] B POPR, NEXT, END-CODE
CODE ARENE ( R: -- wa) ( Т.Е. SP@ >R)
B PUSHR, /WO MOV, SP BP [8] 0 C, /SW ADDD, BP [RG] 4 C,
B POPR, NEXT, END-CODE
CODE ARENE-DROP ( ... -- w; R: wa -- ) ( Т.Е. R> SP! )
/SW SUBD, BP [RG] 4 C, /DW MOV, SP BP [8] 0 C,
B POPR, NEXT, END-CODE
CODE ARENE-RET ( ..., w -- w; R: wa -- ) ( Т.Е. R> SWAP >R SP! R> )
/SW SUBD, BP [RG] 4 C, /DW MOV, SP BP [8] 0 C,
A POPR, NEXT, END-CODE
Я, конечно, за то, что бы тут все хвастались наработками, но в случае локальных переменных требуется не "самая быстрая и универсальная" реализация, а взвешенное решения вотроса на@#$ они @#$ нам @#$cь? Это что, единственная известная нам модель временного хранения результатов вычислений?

Автор:  mOleg [ Вс мар 18, 2012 08:03 ]
Заголовок сообщения:  Re: локальные фреймы данных

gudleifr писал(а):
но в случае локальных переменных требуется не "самая быстрая и универсальная" реализация, а взвешенное решения вотроса

да пожалуйста, просто альтернатива с локальными данными на стеке данных (а не возвратов, как в локалсах стандартных) удобнее, быстрее и как бы фортовее, т.е. логичнее.

Страница 1 из 3 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/