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

Groups > comp.lang.c > #141916

Re: [PC] Lazy list

Show all headers | View raw

M Joshua Ryan <luser.droog@gmail.com> writes:

> I've made a successful experiment in building a lazy list
> structure in PostScript by making a Lisp-like list and
> having an embedded procedure to produce new elements on
> demand. All the literature out there starts with some
> sort of functional syntax that's pretty far from the C
> worldview. So with no loss of clarity, I'm just going
> to use my PostScript implementation as the motivating
> example.
>
> Each element of the list is represented by an array of
> length 2, where the first array item is the content and
> the second array item is the link to the next element.
>
> Any part in the list may be an executable procedure body
> which may yield a value if executed. So the first helper
> function needed is a function that keeps executing the
> object until it is no longer executable.
>
>
>   /@ { { dup xcheck { exec }{ exit } ifelse } loop } def
>
> Next we need a generator to construct an infinite list.
> This code relies upon an extension to postscript described
> here: https://codereview.stackexchange.com/q/193520/5912 .
>
>   /rep {x} { { [ /x { /x rep } ] } ll } func def
>
> And a function to extract a finite portion from the
> head of the list.
>
>   /take {x n} { n 0 eq { [] }
>                        { [ x @ dup first exch  n 1 sub take ] }
>                        ifelse } func def
>
> A simple test gives the expected result:
>
>   PS> 1 rep 5 take pc
>
>   stack:
>   [1 [1 [1 [1 [1 []]]]]]
>
> The next trick from the literature is wrapping an "add 1"
> function around the list. And here's where my code starts
> to look ugly.
>
>   /add1 {x} { x @  dup length 0 eq
> 	      { [] }
> 	      { [ exch dup first 1 add  exch second /add1 cvx 2 aa cvx ] }
> 	      ifelse } func def
> 	      
> So, to emulate all this in C, I think I need a simple tag-union
> object system....
>
> A day later and it's working. Not sure what conclusions to draw.
> Any comments welcome.
>

Some further adventures on the PS side suggest that the lazy list
concept makes it fairly painless to abstract the input from my
parsers so they can operate on a string or file: have both
constructors yield a lazy list of characters.

I haven't yet done it, but I hope it's also easy to abstract over
a list of characters or a list of tokens. Then it should be
straightforward to stich up two levels of parsers and have
one level be the "lexer" reading chars and yielding tokens,
and the next level reading tokens and yielding trees.

One choice I've made in the implementation which may be
questionable is: I've made my lazy lists *mutable* so the various
views of parts of list remain synchronized. So whenever the
continuation function is executed, the result is cached back into
caller's "object".

So, in postscript if I do

   (abcdefghjiklm) string-input dup 5 take pc

So the 'dup' in there makes a copy of the "head" of the list before
'take' produces a new list of the first five. The output

   stack:
   [97 [98 [99 [100 [101 []]]]]]
   [97 [98 [99 [100 [101 [102 {(ghjiklm) string-input}]]]]]]

shows that saved pointer to the head gets the benefit of all
the evaluations that have been performed while peeling the
onion.

This seems like a useful behavior to avoid useless work on
strings or erroneous results on files. But after digesting
all of this fp literature, the word *mutable* makes me
think twice, and ... ask for advice. lol

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

Thread

[PC] Lazy list M Joshua Ryan <luser.droog@gmail.com> - 2019-03-10 05:56 -0500
  Re: [PC] Lazy list M Joshua Ryan <luser.droog@gmail.com> - 2019-03-12 21:55 -0500
    Re: [PC] Lazy list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-21 11:23 +0000
      Re: [PC] Lazy list fir <profesor.fir@gmail.com> - 2019-03-21 04:29 -0700
      Re: [PC] Lazy list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-21 11:35 +0000
      Re: [PC] Lazy list luser droog <luser.droog@gmail.com> - 2019-03-21 15:55 -0700
        Re: [PC] Lazy list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-21 23:35 +0000
          Re: [PC] Lazy list luser droog <luser.droog@gmail.com> - 2019-03-25 17:29 -0700
            Re: [PC] Lazy list David Brown <david.brown@hesbynett.no> - 2019-03-26 09:36 +0100

csiph-web