Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: M Joshua Ryan <luser.droog@gmail.com>
Newsgroups: comp.lang.c
Subject: [PC] Lazy list
Date: Sun, 10 Mar 2019 05:56:37 -0500
Organization: A noiseless patient Spider
Lines: 112
Message-ID: <vriu36nvro9m.fsf@gmail.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="a73bbf7b71076add54f66823869852d7"; logging-data="16810"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/AzntpUGeK5cXAQzCGy8DvRNESVs1eYtQ="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (cygwin)
Cancel-Lock: sha1:+4UdEUjkKR8epctSlmn7Ugcxk6Y= sha1:ADJg8R8aOXPBFvBu8UL5Xm9ACpk=
Xref: csiph.com comp.lang.c:141861

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;
}