| View previous topic :: View next topic |
| Author |
Message |
ygrek
Joined: 04 May 2006
Posts: 449
|
 Posted: Sat Mar 08, 2008 10:18 Post subject: форт и регэкспы |
[QUOTE] |
|
http://fforum.winglion.ru/viewtopic.php?p=13214#13214
| Хищник wrote: | | Аналогично с регэкспами. Исследуются и реализуются в отрыве от языка. |
На форте регэкспы реализуются на порядок эффективнее. Всю работу по построению графа состояний или генерации машкода для сопоставления можно перенести в compile-time. И если скорость критична можно в compile-time также провести детерминизацию автомата. В "обычных" языках компиляцию RE придётся отложить до рантайма и соответственно эффективные (и ресурсоёмкие) оптимизации тоже. Либо вносить поддержку регэкспов в сам компилятор языка.
_________________
http://forth.org.ru/~ygrek |
|
| Back to top |
|
 |
Хищник
Moderator
Joined: 02 May 2006
Posts: 3002
|
| Posted: Sat Mar 08, 2008 12:08 Post subject: |
[QUOTE] |
|
| Можно подумать, регэкспы свалились с Луны. Такой же алгоритм, наряду с сотней других. И если уж говорить об автоматах, Форт тут не лучше и не хуже других языков. Точно так же можно провести подготовительную работу, насоздавать вспомогательных структур. Писать регэкспы на Форте может оказаться удобнее в рамках отдельно взятого приложения, но это и отдельный, прикладной вопрос. |
|
| Back to top |
|
|
true-grue
Joined: 05 Nov 2007
Posts: 41
|
| Posted: Sat Mar 08, 2008 12:39 Post subject: |
[QUOTE] |
|
| Хищник wrote: | | Форт тут не лучше и не хуже других языков. Точно так же можно провести подготовительную работу, насоздавать вспомогательных структур. |
"Не лучше и не хуже" языков с first-class компиляцией. Между прочим, динамическое порождение машинного кода для поиска регулярных выражений оказалось одним из самых ранних известных применений техники JIT(http://portal.acm.org/citation.cfm?id=363387&dl=GUIDE&coll=GUIDE&CFID=19283365&CFTOKEN=13597593). |
|
| Back to top |
|
|
ygrek
Joined: 04 May 2006
Posts: 449
|
|
| Back to top |
|
|
Хищник
Moderator
Joined: 02 May 2006
Posts: 3002
|
| Posted: Sat Mar 08, 2008 13:07 Post subject: |
[QUOTE] |
|
| И как это соотносится с тезисом "надо сделать ANS-совместимость, чтобы иметь возможность использовать прекрасную билиотеку, выложенную там-то"? Насколько я имею возможность наблюдать, разработка новых алгоритмов делает привлекательной как раз эволюцию языков, а не жесткую фиксацию грамматики. Алгоритм и решаемая задача в данном случае выше стандарта. |
|
| Back to top |
|
|
ygrek
Joined: 04 May 2006
Posts: 449
|
|
| Back to top |
|
|
Хищник
Moderator
Joined: 02 May 2006
Posts: 3002
|
| Posted: Sat Mar 08, 2008 14:58 Post subject: |
[QUOTE] |
|
| Вижу. Тред возник после упоминания Forthware о том, что в некоей АНС-совместимой библиотеке есть регэкспы, поэтому надо делать совместимые трансляторы, чтобы ни в коем случае не упустить сие великое богатство. Я же, напротив, считаю, что поиск новых алгоритмов должен сопровождаться соответствующими изменениями в реализациях Форта, причем именно регэкспы тому очень показательный пример (имея в виду упомянутую true-grue динамическую кодогенерацию). |
|
| Back to top |
|
|
Forthware
[+]
Joined: 02 Dec 2007
Posts: 442
|
| Posted: Sat Mar 08, 2008 17:22 Post subject: |
[QUOTE] |
|
| Хищник wrote: | | Тред возник после упоминания Forthware о том, что в некоей АНС-совместимой библиотеке есть регэкспы |
Нет. Тред возник после вашего: | Хищник wrote: | | Аналогично с регэкспами. Исследуются и реализуются в отрыве от языка. |
Читайте первый пост треда, и комментарии его автора. 
_________________
Am I evil? I'm man - yes I am! © James Hatefield |
|
| Back to top |
|
|
Forthware
[+]
Joined: 02 Dec 2007
Posts: 442
|
| Posted: Sat Mar 08, 2008 21:53 Post subject: |
[QUOTE] |
|
Насчет простоты реализации compile time варианта. Приведенный код является максимально простым, но при этом достаточно полнофункциональным (где-то на уровне JS) решением. Он также, пожалуй, самый медленный, и обладает совершенно необычным для regexp синтаксисом. Можно ли назвать такую простоту преимуществом Форта?
ЗЫ реализация regular expressions в вышеупоминавшейся библиотеке ffl совершенно не полноценна, но обладает "классическим" синтаксисом и трансляция выполняется в runtime.
| Code: | 0 VALUE OK 0 VALUE BEG 0 VALUE SRC 0 VALUE LIM
: `` ( a u -- ) OK IF LIM SRC - OVER DUP >R MIN SRC SWAP COMPARE
IF FALSE TO OK R> DROP ELSE R> SRC + TO SRC THEN THEN ;
: ` ( string` -- ) [CHAR] ` PARSE POSTPONE SLITERAL POSTPONE `` ; IMMEDIATE
: .. ( c1 c2 -- ) OK IF SRC DUP LIM < IF C@ ELSE DROP 0 THEN
-ROT 1+ WITHIN IF SRC CHAR+ TO SRC ELSE FALSE TO OK THEN ELSE 2DROP THEN ;
:NONAME DUP TO SRC TRUE TO OK ;
: | ( -- ) 1+ POSTPONE OK POSTPONE 0= POSTPONE IF LITERAL COMPILE, ; IMMEDIATE
: (( ( -- ) 0 POSTPONE OK POSTPONE IF POSTPONE SRC ; IMMEDIATE
:NONAME OK IF DROP ELSE TO SRC THEN ;
: )) ( -- ) 0 ?DO POSTPONE THEN LOOP LITERAL COMPILE, POSTPONE THEN ; IMMEDIATE
:NONAME OK IF >R SRC OVER - R> 2! ELSE DROP TO SRC THEN ;
: !)) ( d-addr -- ) 0 ?DO POSTPONE THEN LOOP LITERAL COMPILE, POSTPONE THEN ; IMMEDIATE
: {{ ( min max -- ) POSTPONE OK POSTPONE -ROT 0 POSTPONE LITERAL POSTPONE BEGIN POSTPONE (( ; IMMEDIATE
:NONAME NIP OK IF > 0= TO OK DROP ELSE DROP 0= IF TO OK ELSE DROP THEN THEN ;
:NONAME 1+ 2DUP = IF TRUE ELSE OK 0= THEN ;
: }} POSTPONE )) LITERAL COMPILE, POSTPONE UNTIL LITERAL COMPILE, ; IMMEDIATE
: EOL OK IF SRC LIM < 0= TO OK THEN ;
: ?WORD ( c -- f ) DUP [CHAR] A [CHAR] [ WITHIN OVER [CHAR] A [CHAR] { WITHIN OR
SWAP [CHAR] 0 [CHAR] : WITHIN OR ;
: ?BOUND ( -- f ) SRC BEG > SRC CHAR+ LIM < AND
IF SRC C@ ?WORD DUP SRC 1 - C@ ?WORD XOR IF DROP TRUE ELSE SRC CHAR+ C@ ?WORD XOR THEN ELSE TRUE THEN ;
: ?B OK IF ?BOUND TO OK THEN ;
: ^B OK IF ?BOUND 0= TO OK THEN ;
:NONAME ( c-addr u -- ) OVER + TO LIM DUP TO BEG TO SRC TRUE TO OK ;
: RX: : LITERAL COMPILE, POSTPONE (( ;
: ;RX POSTPONE )) POSTPONE OK POSTPONE ; ; IMMEDIATE |
_________________
Am I evil? I'm man - yes I am! © James Hatefield |
|
| Back to top |
|
|
|
ForthFAQ
Статьи
Usergroups
Memberlist
Register
Profile
Log in to check your private messages
Log in
