lazy.c

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

/*
 * TODO
 * - Maybe write some macros to facilitate writing the thunks
 *   - Lazy-cons macro? (can't have lazy-cons as a function due to CbV)
 * - Make sure my memory management strategy isn't shit
 *   - I already know that if you use malloced ptrs in the Generic
 *     it'll fuck shit up
 *   - Maybe use the void* as the only ptr type in the union, and
 *     add metadata to know if something is allocated? e.g.:
 *     typedef struct generic_t {
 *       union {...} val;
 *       char alloc;//boolean if val is malloced
 *     } Generic;
 *   - This adds another level of "indirection hell" though
 *   - Maybe add Generic helper functions/macros to help with indirection
 *   - Make sure to deep copy Generic during a take!
 * - Maybe have a type enum in Generic:
 *   typedef struct generic_t {
 *     union{...} val;
 *     ENUM metadata;//or something
 *   } Generic;
 * - Make an infinite seq of all 1's
 * - Make an infinite seq of the natural numbers
 */

typedef union generic_t {
  char charval;
  char* charptr;
  short shortval;
  short* shortptr;
  int intval;
  int* intptr;
  long longval;
  long* longptr;
  void* voidptr;//Mostly useful for data structures
} Generic;

typedef struct thunk_t {
  Generic* env;
  void* (*func)(Generic*);
} Thunk;

typedef struct lazy_t {
  Generic car;
  Thunk cdr;
} LazySeq;



//Really returns LazySeq
void* range(Generic* env) {
  int curr;
  int limit;
  Generic* nextenv;
  LazySeq* nextseq;
  if (env == NULL) {
    fprintf(stderr, "ERROR IN RANGE THUNK");
    exit(1);
  } else {
    curr = env[0].intval;
    limit = env[1].intval;
    if (curr == limit) {
      return NULL;
    } else {
      nextenv = malloc(sizeof(Generic) * 2);
      nextenv[0].intval = curr + 1;
      nextenv[1].intval = limit;
      
      nextseq = malloc(sizeof(LazySeq));
      nextseq->car.intval = curr;//!!
      nextseq->cdr.env = nextenv;
      nextseq->cdr.func = range;
      return nextseq;
    }
  }
}

/*//TODO: Fix this using my new structs etc
LazySeq* natural_numbers(int curr) {
  LazySeq* next = malloc(sizeof(LazySeq));
  next->car = curr + 1;
  next->cdr = naturalNumbers;
  return next;
}
*/
LazySeq* lazy_range(int min, int max) {
  Generic* env = malloc(sizeof(Generic) * 2);
  LazySeq* seq = malloc(sizeof(LazySeq));
  
  env[0].intval = min + 1;
  env[1].intval = max;

  seq->car.intval = min;
  seq->cdr.env = env;
  seq->cdr.func = range;

  return seq;
}

Generic lazy_car(LazySeq * seq) {
  return(seq->car);
}

LazySeq* lazy_cdr(LazySeq* seq) {
  Thunk cdr;
  void* (*fp)(Generic*);
  Generic* env;
  LazySeq* next;
  if (seq == NULL) {
    return(NULL);//seq terminated
  } else {
    cdr = seq->cdr;
    
    env = cdr.env;
    fp = cdr.func;
    next = (LazySeq*) (*fp)(env);
    
    free(seq->cdr.env);
    free(seq);
    return(next);
  }
}

typedef struct strict_t {
  Generic car;
  struct strict_t* cdr;
} StrictSeq;

StrictSeq* take(int num, LazySeq* lz) {
  int i;
  StrictSeq* head;
  StrictSeq* iter;
  
  head = (StrictSeq*) malloc(sizeof(StrictSeq));
  head->car = lazy_car(lz);
  head->cdr = NULL;
  iter = head;
  //should also check of (null? lz)
  for (i = 1; i < num; i++) {
    lz = lazy_cdr(lz);
    iter->cdr = malloc(sizeof(StrictSeq));
    iter->cdr->car = lazy_car(lz);
    iter->cdr->cdr = NULL;
    iter = iter->cdr;
  }

  //MANAGE MEMORY!
  free(lz->cdr.env);
  free(lz);
  return(head);
}

//They only print ints atm
void lazy_print(LazySeq* lz) {
  while (lz != NULL) {
    printf("%d\n", lazy_car(lz).intval);
    lz = lazy_cdr(lz);
  }
}

void strict_print(StrictSeq* ls) {
  while (ls != NULL) {
    printf("%d\n", ls->car.intval);
    ls = ls->cdr;
  }
}

void strict_destroy(StrictSeq* ls) {
  StrictSeq* next;
  while (ls != NULL) {
    next = ls->cdr;
    free(ls);
    ls = next;
  }
}

int main (int argc, char ** argv) {
  LazySeq* lz = lazy_range(0,10);
  StrictSeq* ls;

  printf("LAZY ITERATION\n");
  lazy_print(lz);

  printf("\nTAKE 3\n");
  ls = take(3, lazy_range(0,10));
  strict_print(ls);

  strict_destroy(ls);
  return EXIT_SUCCESS;
}

lazy.ss

(define lazy-car
  (lambda (lz)
    (car lz)))

(define lazy-cdr
  (lambda (lz)
    ((cdr lz))))

(define take
  (lambda (n lz)
    (if (or (zero? n) (null? lz))
	'()
	(cons (lazy-car lz)
	      (take (- n 1) (lazy-cdr lz))))))

(define inf-1s-strict
  (lambda ()
    (cons 1 (inf-1s-strict))))

(define inf-1s-lazy
  (lambda ()
    (cons 1 (lambda () (inf-1s-lazy)))))

(define count-up-strict
  (lambda (start)
    (cons start (count-up-strict (+ start 1)))))

(define count-up-lazy
  (lambda (start)
    (cons start (lambda () (count-up-lazy (+ start 1))))))

(define range
  (lambda (mn mx)
    (if (= mn mx)
	'()
	(cons mn (lambda () (range (+ mn 1) mx))))))