On Sat, Jan 5, 2013 at 3:44 PM, Jonathan S. Shapiro <[email protected]> wrote:
>
> 1. Is this worth it? It seems to be driven by the desire to mix imperative
> and pure programming without an explosion of type definition variations (due
> to case analysis getting embedded at the type level).
It seems to me that one property lost due to the mix of imperative and
pure when data structures
are built this way is the notion of persistence, although I guess
maybe its quasi persistent or immutably persistent or something.
http://en.wikipedia.org/wiki/Persistent_data_structure
FWIW i've previously thought about this but only really to the extent
of implementing a queue in this style (attached).
being in C i don't think the language really lends itself to this, so
it suffers some type explosion, I haven't really looked at it in a
year
or so, but looking at it it doesn't seem like it implements the notion
of aliases containing a different or previous invariant of the actual
type
anyhow i guess its just another variation of the list example.
> 2. How do we think about object sharing across concurrency *without* some
> ability to talk about this?
> 3. Any pointers on things I might read?
I never really found anything
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>
/* In general the 'type structures' must have union like semantics
* But because they undergo metamorphosis we need to specify unused fields
* so that the fields end up at the same memory locations e.g. in the case of
* head_t and tail_t, where not specifying them would be ambiguous.
*
* The whole idea of relying that these structure layouts are equal is probably
* not the best of ideas.
*/
struct node {
void *item;
struct node *prev;
struct node *next;
};
/* shadow_ variables are essentially undefined,
* they take up space but may/may not point to anything in particular.
*/
struct lone_t
{
void *item;
void *shadow_prev;
void *shadow_next;
};
struct head_t {
void *item;
void *shadow_prev;
struct node *next;
};
struct tail_t {
void *item;
struct node *prev;
void *shadow_next;
};
struct rest_t {
void *item;
struct node *prev;
struct node *next;
};
union head {
struct lone_t *l;
struct head_t *h;
};
union tail {
struct lone_t *l;
struct tail_t *t;
};
enum node_type
{
next_only_type,
prev_only_type,
next_prev_type,
empty_type,
lone_type,
};
struct dequeue
{
/* it is worth noting that an object does not carry its type.
but merely has a type.
What I mean by that is that head may be the same while head_type may be different.
*/
enum node_type head_type;
union head head;
size_t rest_count;
/* rest_type is the type of _all_ objects in the rest_t list
* It is kind of unused, since they are all of the same type.
* the reason this is important is it points to the idea that I need 'native list type'
*
* the weirdness here is that the last item in rest points to the tail which is of tail_type.
* we could get rid of this I suppose by making 'a prev_of_tail node'
* which is a union of prev_only_type and lone type
*/
enum node_type rest_type;
struct rest_t *rest;
enum node_type tail_type;
union tail tail;
};
struct dequeue *dequeue_push(struct dequeue *to, void *item)
{
struct dequeue *new_deq = malloc (sizeof (*new_deq));
assert(to == NULL
|| (to->head_type == lone_type
&& to->tail_type == lone_type)
|| (to->head_type == next_only_type
&& to->tail_type == prev_only_type));
if (to == NULL) {
struct lone_t *new_node = malloc(sizeof (*new_node));
memset(new_deq, 0, sizeof(*new_deq));
new_node->item = item;
new_node->shadow_next = NULL;
new_node->shadow_prev = NULL;
new_deq->head.l = new_node;
new_deq->tail.l = new_node;
new_deq->head_type = new_deq->tail_type = lone_type;
new_deq->rest_type = empty_type;
new_deq->rest_count = 0;
} else {
/* transition from:
* head/tail to head->next/tail->prev. */
switch(to->head_type) {
case lone_type:
{
struct head_t *new_node = malloc(sizeof (*new_node));
new_node->item = item;
new_deq->head_type = next_only_type;
/* fields can only morph once.
this is kind of a hack we could make each node carry a mutable type
and have 'struct dequeue' carry immutable 'alias types'. */
assert(to->head.l->shadow_prev == NULL);
to->head.l->shadow_prev = new_node;
new_node->next = NULL;
new_deq->head.h = new_node;
new_deq->rest_type = next_prev_type;
new_deq->rest = (struct rest_t *)to->head.l;
}
break;
case next_only_type:
{
struct head_t *new_node = malloc(sizeof (*new_node));
new_node->item = item;
new_deq->head_type = next_only_type;
new_deq->head.h = (struct head_t *)new_node;
/* fields can only morph once.
this is kind of a hack we could make each node carry a mutable type
and have 'struct dequeue' carry immutable 'alias types'. */
assert(to->head.l->shadow_prev == NULL);
to->head.h->shadow_prev = new_node;
new_node->next = NULL;
new_deq->rest = (struct rest_t *)to->head.l;
}
break;
}
switch(to->tail_type) {
case prev_only_type:
case lone_type:
new_deq->tail_type = prev_only_type;
new_deq->tail = to->tail;
break;
}
new_deq->rest_count = to->rest_count + 1;
}
return new_deq;
}
struct dequeue *dequeue_pop (struct dequeue *from, void **item)
{
struct dequeue *ret;
assert(from != NULL
&& (from->head_type == lone_type
&& from->tail_type == lone_type)
|| (from->head_type == next_only_type
&& from->tail_type == prev_only_type));
switch(from->head_type) {
case lone_type:
ret = NULL;
break;
case next_only_type:
ret = malloc (sizeof (*ret));
ret->head = from->head;
switch (from->rest_count) {
case 1:
/* transition from:
* head->next/tail->prev to head/tail. */
ret->tail.l = (struct lone_t *)from->tail.t->prev;
ret->tail_type = ret->head_type = lone_type;
ret->rest_type = empty_type;
ret->rest_count = from->rest_count - 1;
break;
default:
ret->tail.t = (struct tail_t *)from->tail.t->prev;
ret->tail_type = prev_only_type;
ret->head_type = next_only_type;
ret->rest_count = from->rest_count - 1;
break;
}
break;
}
*item = from->tail.l->item;
return ret;
}
int main(int argc, const char **argv)
{
int i;
struct dequeue *deq = NULL;
struct dequeue *deq2 = NULL;
for (i = 0; i < argc; i++) {
deq = dequeue_push(deq, (void *)strdup(argv[i]));
deq2 = dequeue_push(deq2, deq);
}
for (i = 0; i < argc; i++) {
char *foo;
printf("%p %i: ", deq, deq->rest_count);
deq = dequeue_pop(deq, (void **)&foo);
if (deq)
deq2 = dequeue_push(deq2, deq);
printf("%s\n", foo);
}
while (deq2) {
int first = 0;
char *foo;
deq2 = dequeue_pop(deq2, (void **)&deq);
while (deq) {
deq = dequeue_pop(deq, (void **)&foo);
if (first)
printf(", %s", foo);
else
{
printf("%s", foo);
first++;
}
}
printf("\n");
}
return 0;
}
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
