Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #34937

Re: A stack oriented garbage collector.

Show all headers | View raw

On 10/15/14 10:13 AM, Albert van der Horst wrote:
> Thinking about regular expression filters, look at this:
>
> [...]
>
> a typical filter looks like this
>
>
>      1 ARG[] GET-FILE    ( -- s)
>
>      "pattern1" "replace-pattern1" GLOBAL   ( s1 -- s2 )
>      "pattern2" "replace-pattern2" GLOBAL   ( s1 -- s2 )
>      "pattern3" "replace-pattern3" GLOBAL   ( s1 -- s2 )
>      ...
>      "patternk" "replace-patternk" GLOBAL   ( s1 -- s2 )
>
>      1 ARG[] PUT-FILE   ( s -- )
>
> Now each global replacement eats into the dictionary space
> for the length of the input file. For a practical example
> (chapter 5 of Brody's thinking Forth ) this is 20 K.
> So we will run out of space very fast (not really on my
> 8 Gbyte Forth but anyway).
>
> Now we can ALLOCATE those strings but that doesn't really
> help if we can't FREE them. (I ruthlessly put those pattern
> string in the dictionary, I'm talking about the file strings
> here.)
>
> A solution would be a garbage collector that goes through
> the allocator space and only keeps those chunks that are pointed
> to, by an item either on the data stack or the return stack.
>
> Now I can replace the line
>      STREAM@
> with
>      STREAM@ garbage-collect
> and get it over with.
>
> What do you think?

Below is a possibility using garbage-collected dynamic strings.  It
can be done just as well with the pattern and replacement strings kept
on the string or data stack instead of in string variables.  Stack
juggling is no harder on the string stack than on the data stack, and
taking advantage of the two stacks could result in a net reduction.

Here are links for the ANS Forth libraries used:

http://www.umich.edu/~williams/archive/forth/strings/parsing.fs
http://www.umich.edu/~williams/archive/forth/strings/parsing.html

http://www.umich.edu/~williams/archive/forth/strings/dstrings.fs
http://www.umich.edu/~williams/archive/forth/strings/dstrings.html

In the code below, "$" refers to dynamic strings and the string stack,
and "s" refers to Forth strings representated by ( addr len) on the data
stack.

Maybe this example showcases a bit the claim from dstrings.html above:

   ANS Forth strings are roughly complementary to dynamic strings in the
   following way:  the former are especially good for analysis and
   parsing of strings and substrings, while the latter are especially
   good for putting pieces of strings together and keeping them available
   while they're needed, then reclaiming their memory when they're not.

-- David

--- file: global-replace.fs ----------------------------------------------
( Albert van der Horst's global substitution using dynamic strings.
   David N. Williams
   December 15, 2014
)

s" parsing.fs"  INCLUDED  \ for S-SEPARATE
s" dstrings.fs" INCLUDED

$variable pattern$
$variable replacement$

\ Prevent concatenation of a string represented as ( addr len) from
\ triggering a garbage collection that could invalidate the data stack
\ representation.
: safe-s+  $gc-off s+ $gc-on ;

: GLOBAL  ($: old$ pattern$ replacement$ -- new$ )
(
Replace all occurrences of the pattern$ body in old$ by the replacement$
body, leaving new$.  The input old$ may be either dynamic or external.
)
   replacement$ $!
   pattern$     $!
   ($: old$) $s> ( old.s)
   BEGIN
     ( prev.s) pattern$ $@ $s> s-separate
     ( after.s before.s true | prev.s false)
   WHILE
     safe-s+ replacement$ $@ $+
   REPEAT
   ( prev.s) safe-s+ ENDCAT ($: new$) ;

\ Test
$` This string has "a%" and "b%" 3 more times each: b%-a%-a% a%-b%-b%`
$" a%"  $" foo"  GLOBAL
$" b%"  $" bar"  GLOBAL
cr cr $. cr
--------------------------------------------------------------------------

[dirac:~/forth/vanderhorst] dnwills% pfe global-replace.fs
\ Portable Forth Environment 0.33.71 (Aug 12 2011 13:00:41)
Copyright (C) Dirk Uwe Zoller  1993 - 1995.
Copyright (C) Tektronix, Inc.  1998 - 2003.
Copyright (C) Guido U. Draheim 2005 - 2008.
ANS/ffa ITC Forth - Please enter LICENSE and WARRANTY.

This string has "foo" and "bar" 3 more times each: bar-foo-foo foo-bar-bar

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

A stack oriented garbage collector. albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-10-15 14:13 +0000
  Re: A stack oriented garbage collector. humptydumpty <ouatubi@gmail.com> - 2014-10-15 12:48 -0700
    Re: A stack oriented garbage collector. albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-10-16 08:59 +0000
  Re: A stack oriented garbage collector. "David N. Williams" <williams@umich.edu> - 2014-12-15 14:51 -0500
    Re: A stack oriented garbage collector. albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-12-16 11:51 +0000
      Re: A stack oriented garbage collector. "David N. Williams" <williams@umich.edu> - 2014-12-16 09:38 -0500
        Re: A stack oriented garbage collector. albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-12-17 01:07 +0000

csiph-web