aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/parse.c19
-rw-r--r--src/targets/blc.c57
-rw-r--r--src/targets/unbblc.c5
-rw-r--r--src/targets/unblc.c4
4 files changed, 41 insertions, 44 deletions
diff --git a/src/parse.c b/src/parse.c
index 84cfcfd..018f4be 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -17,18 +17,19 @@
// 00MN -> application of M and N
// 1X0 -> bruijn index, amount of 1s in X
// 011I -> 2B index to entry
-static struct term *parse_bloc_bblc(const char *term, size_t *bit)
+static struct term *parse_bloc_bblc(const char *term, size_t length,
+ size_t *bit)
{
struct term *res = 0;
if (!BIT_AT(*bit) && BIT_AT(*bit + 1) && !BIT_AT(*bit + 2)) {
(*bit) += 3;
res = new_term(ABS);
- res->u.abs.term = parse_bloc_bblc(term, bit);
+ res->u.abs.term = parse_bloc_bblc(term, length, bit);
} else if (!BIT_AT(*bit) && !BIT_AT(*bit + 1)) {
(*bit) += 2;
res = new_term(APP);
- res->u.app.lhs = parse_bloc_bblc(term, bit);
- res->u.app.rhs = parse_bloc_bblc(term, bit);
+ res->u.app.lhs = parse_bloc_bblc(term, length, bit);
+ res->u.app.rhs = parse_bloc_bblc(term, length, bit);
} else if (BIT_AT(*bit)) {
const size_t cur = *bit;
while (BIT_AT(*bit))
@@ -49,10 +50,12 @@ static struct term *parse_bloc_bblc(const char *term, size_t *bit)
index |= BIT_AT(*bit) << i;
(*bit) += 1;
}
- res->u.ref.index = index;
+
+ // normalize to entry index
+ res->u.ref.index = length - index - 2;
} else {
(*bit)++;
- res = parse_bloc_bblc(term, bit);
+ res = parse_bloc_bblc(term, length, bit);
}
return res;
}
@@ -73,8 +76,8 @@ struct bloc_parsed *parse_bloc(const void *bloc)
const struct bloc_entry *current = (const void *)&header->entries;
for (size_t i = 0; i < parsed->length; i++) {
size_t len = 0;
- parsed->entries[i] =
- parse_bloc_bblc((const char *)current, &len);
+ parsed->entries[i] = parse_bloc_bblc((const char *)current,
+ parsed->length, &len);
current =
(const struct bloc_entry *)(((const char *)current) +
(len / 8) + (len % 8 != 0));
diff --git a/src/targets/blc.c b/src/targets/blc.c
index a1cbbf3..82e0bc4 100644
--- a/src/targets/blc.c
+++ b/src/targets/blc.c
@@ -18,20 +18,20 @@
static void fprint_blc_substituted(struct term *term, struct bloc_parsed *bloc,
size_t *positions_inv, void **closed,
- int depth, FILE *file)
+ int depth, size_t position, FILE *file)
{
switch (term->type) {
case ABS:
fprintf(file, "00");
fprint_blc_substituted(term->u.abs.term, bloc, positions_inv,
- closed, depth + 1, file);
+ closed, depth + 1, position, file);
break;
case APP:
fprintf(file, "01");
fprint_blc_substituted(term->u.app.lhs, bloc, positions_inv,
- closed, depth, file);
+ closed, depth, position, file);
fprint_blc_substituted(term->u.app.rhs, bloc, positions_inv,
- closed, depth, file);
+ closed, depth, position, file);
break;
case VAR:
for (int i = 0; i <= term->u.var.index; i++)
@@ -42,17 +42,18 @@ static void fprint_blc_substituted(struct term *term, struct bloc_parsed *bloc,
if (term->u.ref.index + 1 >= bloc->length)
fatal("invalid ref index %ld\n", term->u.ref.index);
- int reffed = bloc->length - term->u.ref.index - 2;
- if (closed[reffed]) {
- debug("closed ref %d\n", reffed);
- int index = depth + positions_inv[reffed];
+ if (closed[term->u.ref.index]) {
+ int index =
+ depth +
+ (positions_inv[term->u.ref.index] - position) -
+ 1;
for (int i = 0; i <= index; i++)
fprintf(file, "1");
fprintf(file, "0");
} else {
- fprint_blc_substituted(bloc->entries[reffed], bloc,
- positions_inv, closed, depth,
- file);
+ fprint_blc_substituted(bloc->entries[term->u.ref.index],
+ bloc, positions_inv, closed,
+ depth, position, file);
}
break;
default:
@@ -66,26 +67,25 @@ static void fprint_blc(size_t *positions, void *closed,
size_t *positions_inv =
calloc(bloc->length * sizeof(*positions_inv), 1);
+ // find abstraction count (end) and write header
size_t end = 0;
- for (size_t i = 0; i < bloc->length; i++) {
- if (!positions[i]) {
- end = i;
+ while (1) {
+ end++;
+ if (end >= bloc->length || !positions[end])
break;
- }
- positions_inv[bloc->length - positions[i]] = i;
fprintf(file, "0100"); // ([
- /* fprintf(file, "(["); */
}
- /* fprintf(file, "0"); */
+ // create inv, s.t. ref inc0 -> pos lr
+ for (size_t i = 0; i < end; i++) {
+ debug("%ld: %ld\n", positions[i] - 1, end - i - 1);
+ positions_inv[positions[i] - 1] = end - i - 1;
+ }
for (size_t i = end; i > 0; i--) {
- /* fprintf(file, "]"); // implicit */
- fprint_blc_substituted(
- bloc->entries[bloc->length - positions[i - 1]], bloc,
- positions_inv, closed, 0, file);
- /* fprintf(file, "<%ld>", bloc->length - positions[i - 1]); */
- /* fprintf(file, ")"); // implicit */
+ fprint_blc_substituted(bloc->entries[positions[i - 1] - 1],
+ bloc, positions_inv, closed, 0, end - i,
+ file);
}
free(positions_inv);
@@ -107,7 +107,7 @@ static void bitmap_deps(struct bloc_parsed *bloc, char *bitmap,
case REF:
if (term->u.ref.index + 1 >= bloc->length)
fatal("invalid ref index %ld\n", term->u.ref.index);
- bitmap[bloc->length - term->u.ref.index - 2] = 1;
+ bitmap[term->u.ref.index] = 1;
break;
default:
fatal("invalid type %d\n", term->type);
@@ -134,8 +134,7 @@ static unsigned int annotate(struct bloc_parsed *bloc, struct term *term,
case REF:
if (term->u.ref.index + 1 >= bloc->length)
fatal("invalid ref index %ld\n", term->u.ref.index);
- struct term *sub =
- bloc->entries[bloc->length - term->u.ref.index - 2];
+ struct term *sub = bloc->entries[term->u.ref.index];
return annotate(bloc, sub, depth);
default:
fatal("invalid type %d\n", term->type);
@@ -166,7 +165,7 @@ static void visit(char **bitmaps, char *marks, size_t *positions,
marks[n] &= ~TEMPORARY_MARK;
marks[n] |= PERMANENT_MARK;
- positions[*position] = length - n; // deliberate offset of +2
+ positions[*position] = n + 1;
(*position)++;
}
@@ -210,10 +209,8 @@ static void write_blc(struct bloc_parsed *bloc, FILE *file)
size_t *positions = topological_sort(bitmaps, bloc->length);
fprint_blc(positions, bitmaps, bloc, file);
- /* fprintf(file, "\n"); */
for (size_t i = 0; i < bloc->length; i++) {
- /* printf("%ld: %ld, ", i, positions[i]); */
if (bitmaps[i])
free(bitmaps[i]);
}
diff --git a/src/targets/unbblc.c b/src/targets/unbblc.c
index 57bc1cf..4c3a3c9 100644
--- a/src/targets/unbblc.c
+++ b/src/targets/unbblc.c
@@ -47,9 +47,8 @@ static void fprint_unbblc(struct term *term, struct bloc_parsed *bloc,
case REF:
if (term->u.ref.index + 1 >= bloc->length)
fatal("invalid ref index %ld\n", term->u.ref.index);
- fprint_unbblc(
- bloc->entries[bloc->length - term->u.ref.index - 2],
- bloc, file, byte, bit);
+ fprint_unbblc(bloc->entries[term->u.ref.index], bloc, file,
+ byte, bit);
break;
default:
fatal("invalid type %d\n", term->type);
diff --git a/src/targets/unblc.c b/src/targets/unblc.c
index 7e6c6e6..1b59f7f 100644
--- a/src/targets/unblc.c
+++ b/src/targets/unblc.c
@@ -30,9 +30,7 @@ static void fprint_unblc(struct term *term, struct bloc_parsed *bloc,
case REF:
if (term->u.ref.index + 1 >= bloc->length)
fatal("invalid ref index %ld\n", term->u.ref.index);
- fprint_unblc(
- bloc->entries[bloc->length - term->u.ref.index - 2],
- bloc, file);
+ fprint_unblc(bloc->entries[term->u.ref.index], bloc, file);
break;
default:
fatal("invalid type %d\n", term->type);