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

Groups > comp.lang.c > #141861 > unrolled thread

[PC] Lazy list

Back to article view | Back to comp.lang.c

Contents

  [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

#141861 — [PC] Lazy list

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.


#include <stdlib.h>
#include <stdio.h>

typedef union object *object;
typedef enum tag { INT, ID, CONS, LAZY, } tag;
union object { tag t;
      struct { tag t; int    i;                } int_;
      struct { tag t; char  *s;                } id;
      struct { tag t; object a,b;              } cons;
      struct { tag t; object a,(*f)( object ); } lazy;
};
object new_object( union object o ){
  object p = malloc( sizeof o );
  return  p ? *p = o, p : 0;
}

object int_( int i ){ return  new_object( (union object){ .int_ = { INT, i } } ); }
object id( char *s ){ return  new_object( (union object){ .id = { ID, s } } ); }
object cons( object a, object b ){ return  new_object( (union object){ .cons = { CONS, a, b } } ); }
object lazy( object a, object (*f)( object ) ){
  return  new_object( (union object){ .lazy = { LAZY, a, f } } );
}

object at( object a ){ return  a->t == LAZY ? at( a->lazy.f( a->lazy.a ) ) : a; }

object rep( object a ){
  return  cons(a, lazy( a, rep ) );
}

object take( object a, int n ){
  return  n == 0 ? NULL : (a = at( a ), cons( a->cons.a, take( a->cons.b, n - 1 ) ) );
}

object add1( object a ){
  return  a ? a = at( a ), cons( int_( a->cons.a->int_.i + 1 ), lazy( a->cons.b, add1 ) ): NULL;
}

void print( object a ){
  if(  !a  ) return;
  switch( a->t ){
  case INT: printf("%d ", a->int_.i ); break;
  case ID:  printf("%s ", a->id.s ); break;
  case CONS: print( a->cons.a ); print( a->cons.b ); break;
  case LAZY: printf("... "); break;
  }
}

int main(){
  print( int_(4) ), puts("");
  print( cons( id("name"), id("value") ) ), puts("");
  print( rep( int_(1) ) ), puts("");
  print( take( rep( int_(1) ), 5 ) ), puts("");
  print( take( add1( rep( int_(1) ) ) , 5 ) ), puts("");
  return 0;
}

[toc] | [next] | [standalone]

#141916

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

[toc] | [prev] | [next] | [standalone]

#142171

M Joshua Ryan <luser.droog@gmail.com> writes:
<cut>
> 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

I think lazy lists and parsing combiner are best implemented in other
languages.  I know this is rather trivial advice (which you must likely
already know), but I did not want you to think that I had not studied
your posts.  I just don't think I can add much to how I'd manage this is
C because I probably simply wouldn't!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#142172

W dniu czwartek, 21 marca 2019 12:23:12 UTC+1 użytkownik Ben Bacarisse napisał:
> M Joshua Ryan <luser.droog@gmail.com> writes:
> <cut>
> > 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
> 
> I think lazy lists and parsing combiner are best implemented in other
> languages.  I know this is rather trivial advice (which you must likely
> already know), but I did not want you to think that I had not studied
> your posts.  I just don't think I can add much to how I'd manage this is
> C because I probably simply wouldn't!
> 
ye that kind of topics are hard to follow if you didnt do close things before

but i think it is good to post it even if it brings not much of the follow reaction
(becouse it is at least post on come real program 'content' not only endles language basics)

[toc] | [prev] | [next] | [standalone]

#142173

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> M Joshua Ryan <luser.droog@gmail.com> writes:
> <cut>
>> 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
>
> I think lazy lists and parsing combiner are best implemented in other
s/combiner/combinators/
> languages.  I know this is rather trivial advice (which you must likely
> already know), but I did not want you to think that I had not studied
> your posts.  I just don't think I can add much to how I'd manage this is
> C because I probably simply wouldn't!

(Amongst my many typos, this one is probably one of the most confusing,
so a correction seems in order.)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#142213

On Thursday, March 21, 2019 at 6:23:12 AM UTC-5, Ben Bacarisse wrote:
> M Joshua Ryan <luser.droog@gmail.com> writes:
> <cut>
> > 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
> 
> I think lazy lists and parsing combiner are best implemented in other
> languages.  I know this is rather trivial advice (which you must likely
> already know), but I did not want you to think that I had not studied
> your posts.  I just don't think I can add much to how I'd manage this is
> C because I probably simply wouldn't!
> 

Understood. :) All the papers I'm reading use other languages, with one
exception: Daan Leijen[1], "Implementing Algebraic Effects in C".

  https://www.microsoft.com/en-us/research/publication/implementing-algebraic-effects-in-c/

This paper (which I have not fully digested yet) claims to offer the 
ability to implement Monads in C. Another paper, Hutton and Meijer, 
"Monadic Parser Combinators",

  http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf

suggests that Monads make the parsers easier to work with. Particularly,
the 'into(p,q)' combinator which does the same as 'then(p,q)' (simple 
sequencing) but 'into' makes the (tree) result of parser p available to
parser q (and any attached code). Without Monads, passing the result of
p to q requires storing it in a variable which q can access. But with
monadic parser, apparently the result can just be passed as a function
argument. 

[1] Why are Scandinavians so good at this stuff?

[toc] | [prev] | [next] | [standalone]

#142215

luser droog <luser.droog@gmail.com> writes:
<cut>
> All the papers I'm reading use other languages, with one
> exception: Daan Leijen[1] ...
<cut>
> Another paper, Hutton and Meijer ...
<cut>
> [1] Why are Scandinavians so good at this stuff?

I think you mean the Dutch (or Nederlanders).  I don't know the full
biographies of everyone you cite, but I don't think any are
Scandinavian.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#142448

On Thursday, March 21, 2019 at 6:35:44 PM UTC-5, Ben Bacarisse wrote:
> luser droog <luser.droog@gmail.com> writes:
> <cut>
> > All the papers I'm reading use other languages, with one
> > exception: Daan Leijen[1] ...
> <cut>
> > Another paper, Hutton and Meijer ...
> <cut>
> > [1] Why are Scandinavians so good at this stuff?
> 
> I think you mean the Dutch (or Nederlanders).  I don't know the full
> biographies of everyone you cite, but I don't think any are
> Scandinavian.
> 

Point taken. I think I was confusing the Dutch and the Danes 
and lumping them all together. For spectators, some further 
misadventures of mine are documented in recent postings in
comp.lang.postscript. (You don't have to read the code, but
you *do* have to admire its brevity and simplicity.)
I got the monadic combinators to work, and (after some struggle)
it has made the regex builder much nicer and shorter.
I think I'm almost ready to translate to C. Maybe a nap first. yawn.

[toc] | [prev] | [next] | [standalone]

#142457

On 26/03/2019 01:29, luser droog wrote:
> On Thursday, March 21, 2019 at 6:35:44 PM UTC-5, Ben Bacarisse wrote:
>> luser droog <luser.droog@gmail.com> writes:
>> <cut>
>>> All the papers I'm reading use other languages, with one
>>> exception: Daan Leijen[1] ...
>> <cut>
>>> Another paper, Hutton and Meijer ...
>> <cut>
>>> [1] Why are Scandinavians so good at this stuff?
>>
>> I think you mean the Dutch (or Nederlanders).  I don't know the full
>> biographies of everyone you cite, but I don't think any are
>> Scandinavian.
>>
> 
> Point taken. I think I was confusing the Dutch and the Danes 
> and lumping them all together.

It's off-topic here, but you might like to sit down with an atlas for a
bit.  "Scandinavia" is not very well defined, but always encompasses
Norway, Sweden and Denmark.  Some people also include Finland and
Iceland, others don't.  But think "Vikings", and you are on the right
track.  The Netherlands is in a different place altogether.

There has been a strong tradition for computer science and theory in
Dutch universities.  Many key developments in programming theory came
from the work of folks like Dijkstra in the late 1960's and 1970's.
Dijkstra was particularly involved in structured programming (he is the
guy behind "Goto considered harmful") and multi-threading issues.  Other
famous Dutch computer people include Andrew Tannenbaum (developer of
Minix, inspiration for Linux), and Guido van Rossum (of Python fame).

Scandinavia has had fewer great contributors to the computing world.
Ole Johan Dahl (Norway) developed object oriented programming, and of
course Bjarne Stroustrup (Denmark) is the key man behind C++.  (Some
people in this group might not see that as a positive contribution to
computing...)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web