aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--inc/term.h3
-rw-r--r--makefile12
-rw-r--r--readme.md4
-rw-r--r--src/main.c24
-rw-r--r--src/parse.c31
-rw-r--r--src/reducer.c22
-rw-r--r--src/term.c114
7 files changed, 153 insertions, 57 deletions
diff --git a/inc/term.h b/inc/term.h
index 855d9cf..6ce204b 100644
--- a/inc/term.h
+++ b/inc/term.h
@@ -24,6 +24,9 @@ struct term {
struct term *new_term(term_type type);
void print_term(struct term *term);
+void print_scheme(struct term *term);
void free_term(struct term *term);
+void to_barendregt(struct term *term);
+void to_bruijn(struct term *term);
#endif
diff --git a/makefile b/makefile
index 31ac46d..3e39b22 100644
--- a/makefile
+++ b/makefile
@@ -11,16 +11,14 @@ INC = $(PWD)/inc
SRCS = $(wildcard $(SRC)/*.c)
OBJS = $(patsubst $(SRC)/%.c, $(BUILD)/%.o, $(SRCS))
-# I need the following on my machine. Look it up though before using it.
-# export ASAN_OPTIONS=verify_asan_link_order=0
-CFLAGS_DEBUG = -Wno-error -s -ggdb3 -Og -Wno-unused -fsanitize=address -fsanitize=undefined -fstack-protector-all $(CFLAGS_TEST)
-CFLAGS_WARNINGS = -Wall -Wextra -Werror -Wshadow -Wpointer-arith -Wwrite-strings -Wredundant-decls -Wnested-externs -Wformat=2 -Wmissing-declarations -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wswitch-default -Wswitch-enum -Wunreachable-code -Wundef -Wold-style-definition -Wvla -pedantic -Wno-switch-enum
+CFLAGS_DEBUG = -Wno-error -g -Og -Wno-unused -fsanitize=address -fsanitize=undefined -fstack-protector-all $(CFLAGS_TEST)
+CFLAGS_WARNINGS = -Wall -Wextra -Wshadow -Wpointer-arith -Wwrite-strings -Wredundant-decls -Wnested-externs -Wformat=2 -Wmissing-declarations -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wswitch-default -Wswitch-enum -Wunreachable-code -Wundef -Wold-style-definition -Wvla -pedantic -Wno-switch-enum
CFLAGS = $(CFLAGS_WARNINGS) -std=c99 -fno-profile-generate -fno-omit-frame-pointer -fno-common -fno-asynchronous-unwind-tables -mno-red-zone -Ofast -D_DEFAULT_SOURCE -I$(INC) #$(CFLAGS_DEBUG)
all: compile sync
-compile: $(BUILD) $(OBJS) $(BUILD)/milcr
+compile: $(BUILD) $(OBJS) $(BUILD)/calm
clean:
@rm -rf $(BUILD)/*
@@ -28,13 +26,13 @@ clean:
test:
sync: # Ugly hack
- @$(MAKE) $(BUILD)/milcr --always-make --dry-run | grep -wE 'gcc|g\+\+' | grep -w '\-c' | jq -nR '[inputs|{directory:".", command:., file: match(" [^ ]+$$").string[1:]}]' >compile_commands.json
+ @$(MAKE) $(BUILD)/calm --always-make --dry-run | grep -wE 'gcc|g\+\+' | grep -w '\-c' | jq -nR '[inputs|{directory:".", command:., file: match(" [^ ]+$$").string[1:]}]' >compile_commands.json
@$(TG) -R --exclude=.git --exclude=build .
$(BUILD)/%.o: $(SRC)/%.c
@$(CC) -c -o $@ $(CFLAGS) $<
-$(BUILD)/milcr: $(OBJS)
+$(BUILD)/calm: $(OBJS)
@$(CC) -o $@ $(CFLAGS) $^
.PHONY: all compile clean sync
diff --git a/readme.md b/readme.md
index 1a4837a..9fac6be 100644
--- a/readme.md
+++ b/readme.md
@@ -1,6 +1,6 @@
-# CALM
+# calm
-> **C**all-by-Need **A**bstract **L**ambda **M**achine
+> **c**all-by-need **a**bstract **l**ambda **m**achine
- Strong reduction (reduction inside abstractions) of call-by-need
lambda calculus
diff --git a/src/main.c b/src/main.c
index 45de94e..7e6b2e1 100644
--- a/src/main.c
+++ b/src/main.c
@@ -1,3 +1,5 @@
+// vim: nowrap
+
#include <stdio.h>
#include <parse.h>
@@ -6,15 +8,25 @@
int main(void)
{
- struct term *term =
- parse("([((1 0) 0)] ([[([0] 0)]] [([(0 0)] [(0 0)])]))");
+ /* struct term *term = */
+ /* parse("([((1 0) 0)] ([[([0] 0)]] [([(0 0)] [(0 0)])]))"); */
// 1-2-6-1-1-4-9-3-1-2-6-2-5-7-1-2-6-3-4-5-11-5-10-9-4-8-10
- print_term(term);
+
+ /* struct term *term = parse( */
+ /* "(([[(([([[((1 0) [[[0]]])]] ((((0 [[(((0 ([([(0 [[0]])] ((((0 (([[[((0 2) 1)]]] [[[[3]]]]) [[[[(2 3)]]]])) [(0 [[(([[[((0 2) 1)]]] ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] 0))]])]) [(0 [[(([[[((0 2) 1)]]] ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] 1))]])]) [(0 [[(([[[((0 2) 1)]]] ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] 1))]])]))] (([(0 0)] [[((((0 [[[[3]]]]) [([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))]) [([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))]) [([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))])]]) 1))) ([([(0 [[0]])] ((((0 (([[[((0 2) 1)]]] [[[[3]]]]) [[[[(1 3)]]]])) [(0 [[(([[[((0 2) 1)]]] ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] 1))]])]) [(0 [[(([[[((0 2) 1)]]] ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] 0))]])]) [(0 [[(([[[((0 2) 1)]]] ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] 1))]])]))] (([(0 0)] [[((((0 [[[[3]]]]) [([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))]) [([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))]) [([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))])]]) 1))) (([(0 0)] [[((((0 [[[[3]]]]) [([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))]) [([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))]) [([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ([((3 3) 0)] 0))])]]) 1))]]) [[[((((1 ([(((1 ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[2]]]))) ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]]))) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]])))] 1)) [(((1 ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[2]]]))) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]]))) ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[2]]])))]) [(([[[[[[((((5 2) 1) 0) ((((4 3) 2) 1) 0))]]]]]] 1) ((3 0) [[[0]]]))]) [(((1 ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[2]]]))) ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]]))) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]])))])]]]) [[[((((1 ([(((1 ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]]))) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[1]]]))) ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]])))] 1)) [(([[[[[[((((5 2) 1) 0) ((((4 3) 2) 1) 0))]]]]]] 1) ((3 0) [[[0]]]))]) [(((1 ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]]))) ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[1]]]))) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[1]]])))]) [(((1 ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]]))) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[1]]]))) ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]])))])]]]) [[[((((1 ([(([[[[[[((((5 2) 1) 0) ((((4 3) 2) 1) 0))]]]]]] 1) ((3 0) [[[0]]]))] 1)) [(((1 ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[2]]]))) ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]]))) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]])))]) [(((1 ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]]))) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[1]]]))) ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] ((3 0) [[[0]]])))]) [(([[[[[[((((5 2) 1) 0) ((((4 3) 2) 1) 0))]]]]]] 1) ((3 0) [[[0]]]))])]]]))] 1) ([((((0 [[[[3]]]]) [[[[[(2 4)]]]]]) [[[[[(1 4)]]]] ]) [[[[[(0 4)]]]]])] 0))]] [[[[(2 (2 (1 3)))]]]]) [[[[(1 3)]]]])"); */
+ // 1-1-2-6-2-6-1-1-2-6-1-2-6-2-6-1-1-3-1-1-1-1-3-3-2-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-5-6-2-6-1-1-1-1-3-3-1-2-6-1-1-1-1-3-3-2-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-5-5-6-2-6-2-6-2-6-1-3-2-5-6-1-1-2-6-2-6-2-7-2-7-2-7-2-7-1-1-1-1-3-3-2-5-5-6-2-6-2-6-3-4-5-9-1-1-1-1-3-1-1-3-1-4-6-2-5-6-2-6-1-1-1-1-3-3-3-3-2-5-5-5-5-6-2-6-2-6-2-6-3-1-2-6-1-1-1-3-2-5-6-2-6-2-6-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-9-1-1-1-1-3-1-1-3-1-3-2-5-6-2-5-6-2-6-1-1-1-1-3-3-4-5-5-6-2-6-2-6-2-6-3-1-2-6-1-1-1-3-2-5-6-2-6-2-6-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-4-5-5-9-1-1-1-1-3-1-1-3-3-2-5-5-6-2-6-1-1-1-3-2-5-6-2-6-2-6-3-1-1-2-6-1-3-2-5-6-2-6-1-1-1-1-3-3-3-4-5-5-5-6-2-6-2-6-2-6-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-4-5-5-5-10-10-10-11-5-11-5-11-5-11-5
+
+ struct term *term = parse(
+ "((([([(1 [((1 1) 0)])] [(1 [((1 1) 0)])])] [[[((([((0 [[[[[0]]]]]) [[1]])] 0) [[0]]) ((([((((0 [[1]]) [[[0]]]) [[[0]]]) [0])] 1) [[0]]) (([[[((0 2) 1)]]] ([(0 [[1]])] 0)) ((2 ([([(0 [[0]])] ((((0 (([[[((0 2) 1)]]] [[[[3]]]]) [[[[(2 3)]]]])) [(0 [[(([[[((0 2) 1)]]] ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] 0))]])]) [(0 [[(([[[((0 2) 1)]]] ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] 1))]])]) [(0 [[(([[[((0 2) 1)]]] ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] 1))]])]))] 1)) ([(0 [[0]])] 0)))))]]]) [[[[(0 (2 (1 3)))]]]]) (([([(1 [((1 1) 0)])] [(1 [((1 1) 0)])])] [[((([([(1 [((1 1) 0)])] [(1 [((1 1) 0)])])] [[[((([((0 [[[[[0]]]]]) [[1]])] 1) 0) (([[[((0 2) 1)]]] ([(0 [[1]])] 1)) ((2 ([(0 [[0]])] 1)) 0)))]]]) 0) (1 0))]]) [((0 [((0 [[1]]) [((0 [[0]]) [((0 [[0]]) [((0 [[0]]) [((0 [[0]]) [((0 [[1]]) [((0 [[1]]) [((0 [[0]]) [[0]])])])])])])])])]) [((0 [((0 [[0]]) [((0 [[1]]) [((0 [[0]]) [((0 [[0]]) [((0 [[0]]) [((0 [[1]]) [((0 [[1]]) [((0 [[0]]) [[0]])])])])])])])])]) [[0]])])]))");
+ // 1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-1-2-6-1-2-6-1-3-2-5-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-2-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-2-5-5-6-2-6-2-6-2-6-1-3-2-5-6-3-1-3-2-5-6-2-5-6-2-6-3-1-1-2-6-2-6-2-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-AAH-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1
+ // 1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-1-2-6-1-2-6-1-3-2-5-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-2-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-2-5-5-6-2-6-2-6-2-6-1-3-2-5-6-3-1-3-2-5-6-2-5-6-2-6-3-1-1-2-6-2-6-2-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-AAH-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-3-2-5-6-1-3-1-3-2-5-6-1-3-3-1-1-2-6-2-6-2-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-2-6-3-2-5-6-2-6-3-3-3-3-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-3-4-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-3-2-5-5-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-3-2-5-5-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-2-5-5-6-2-5-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-2-6-3-2-5-6-2-6-3-3-3-3-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-3-4-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-4-6-2-6-2-6-2-6-1-3-3-2-5-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-4-5-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-2-5-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-3-2-5-5-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-2-6-3-2-5-6-2-6-3-3-3-3-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-3-4-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-2-5-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-2-5-5-5-5-5-5-5-6-2-6-3-2-5-5-5-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5
+
+ /* print_scheme(term); */
printf("\nReduced:\n");
- struct term *reduced = reduce(term);
- print_term(reduced);
+ reduce(term);
+ /* print_term(reduced); */
printf("\n");
free_term(term);
- free_term(reduced);
+ /* free_term(reduced); */
return 0;
}
diff --git a/src/parse.c b/src/parse.c
index 016b5e9..23b6a2f 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -6,12 +6,6 @@
#include <parse.h>
#include <term.h>
-static int name_generator(void)
-{
- static int current = 0x424242; // TODO: idk?
- return current++;
-}
-
static struct term *rec(const char **term)
{
struct term *res = 0;
@@ -38,32 +32,9 @@ static struct term *rec(const char **term)
return res;
}
-// TODO: WARNING: This might not be 100% correct! Verify!
-static void to_barendregt(struct term *term, int level, int replacement)
-{
- switch (term->type) {
- case ABS:
- term->u.abs.name = name_generator();
- to_barendregt(term->u.abs.term, level + 1, term->u.abs.name);
- break;
- case APP:
- to_barendregt(term->u.app.lhs, level, replacement);
- to_barendregt(term->u.app.rhs, level, replacement);
- break;
- case VAR:
- if (term->u.var.type == BRUIJN_INDEX) {
- term->u.var.name = replacement - term->u.var.name;
- term->u.var.type = BARENDREGT_VARIABLE;
- }
- break;
- default:
- fprintf(stderr, "Invalid type %d\n", term->type);
- }
-}
-
struct term *parse(const char *term)
{
struct term *parsed = rec(&term);
- to_barendregt(parsed, -1, -name_generator());
+ to_barendregt(parsed);
return parsed;
}
diff --git a/src/reducer.c b/src/reducer.c
index cd05ebd..2f3c559 100644
--- a/src/reducer.c
+++ b/src/reducer.c
@@ -61,7 +61,6 @@ static int name_generator(void)
static struct stack *stack_push(struct stack *stack, void *data)
{
struct stack *new = malloc(sizeof(*new));
- /* printf("NEW: %p -> %p\n", (void *)new, (void *)stack); */
new->data = data;
new->next = stack;
return new;
@@ -69,7 +68,6 @@ static struct stack *stack_push(struct stack *stack, void *data)
static struct stack *stack_next(struct stack *stack)
{
- /* printf("NEXT %p -> %p\n", (void *)stack, (void *)stack->next); */
return stack->next;
}
@@ -79,7 +77,6 @@ static struct store *store_push(struct store *store, int key, void *data)
struct store_data *keyed = malloc(sizeof(*keyed));
keyed->key = key;
keyed->data = data;
- /* printf("STORE STACK\n"); */
elem->stack = stack_push(elem->stack, keyed);
return store;
}
@@ -171,16 +168,17 @@ static int transition(struct conf *conf)
} else if (conf->type == COMPUTED) {
struct stack *stack = conf->u.cconf.stack;
struct term *term = conf->u.cconf.term;
- if (!stack || !stack->next || !stack->data)
+ if (!stack) {
+ fprintf(stderr, "Invalid stack!\n");
return 1;
+ }
struct term *peek_term = stack->data;
- if (peek_term->type == CACHE) { // (5)
+ if (peek_term && peek_term->type == CACHE) { // (5)
struct cache *cache = peek_term->u.other;
struct term *cache_term = cache->term;
if (cache_term->type == VAR &&
!cache_term->u.var.name) {
printf("(5)\n");
- /* print_term(term); */
cache->box->state = DONE;
cache->box->data = term;
conf->type = COMPUTED;
@@ -189,7 +187,7 @@ static int transition(struct conf *conf)
return 0;
}
}
- if (peek_term->type == APP &&
+ if (peek_term && peek_term->type == APP &&
peek_term->u.app.lhs->type == VAR &&
!peek_term->u.app.lhs->u.var.name && term->type == CACHE &&
((struct cache *)term->u.other)->term->type == CLO) { // (6)
@@ -251,9 +249,8 @@ static int transition(struct conf *conf)
conf->u.cconf.term = box->data;
return 0;
}
- // TODO: #:when??
}
- if (peek_term->type == APP &&
+ if (peek_term && peek_term->type == APP &&
peek_term->u.app.lhs->type == VAR &&
!peek_term->u.app.lhs->u.var.name &&
peek_term->u.app.rhs->type == CLO) { // (9)
@@ -269,7 +266,7 @@ static int transition(struct conf *conf)
stack_push(stack_next(stack), app);
return 0;
}
- if (peek_term->type == APP &&
+ if (peek_term && peek_term->type == APP &&
peek_term->u.app.rhs->type == VAR &&
!peek_term->u.app.rhs->u.var.name) { // (10)
printf("(10)\n");
@@ -281,7 +278,7 @@ static int transition(struct conf *conf)
conf->u.cconf.term = app;
return 0;
}
- if (peek_term->type == ABS &&
+ if (peek_term && peek_term->type == ABS &&
peek_term->u.abs.term->type == VAR &&
!peek_term->u.abs.term->u.var.name) { // (11)
printf("(11)\n");
@@ -293,6 +290,8 @@ static int transition(struct conf *conf)
conf->u.cconf.term = abs;
return 0;
}
+ if (!peek_term)
+ return 1;
}
fprintf(stderr, "Invalid transition state\n");
return 1;
@@ -316,6 +315,7 @@ struct term *reduce(struct term *term)
};
for_each_state(&conf);
assert(conf.type == COMPUTED);
+ to_bruijn(conf.u.cconf.term);
print_term(conf.u.cconf.term);
return term;
}
diff --git a/src/term.c b/src/term.c
index d13ec9f..52f606b 100644
--- a/src/term.c
+++ b/src/term.c
@@ -1,8 +1,94 @@
#include <stdlib.h>
+#include <assert.h>
#include <stdio.h>
#include <term.h>
+static int name_generator(void)
+{
+ static int current = 0x424242; // TODO: idk?
+ return current++;
+}
+
+#define MAX_CONVERSION_VARS 256
+static void to_barendregt_helper(struct term *term, int *vars, int size)
+{
+ assert(size < MAX_CONVERSION_VARS);
+ switch (term->type) {
+ case ABS:
+ vars[size] = name_generator();
+ term->u.abs.name = vars[size];
+ to_barendregt_helper(term->u.abs.term, vars, size + 1);
+ break;
+ case APP:
+ to_barendregt_helper(term->u.app.lhs, vars, size);
+ to_barendregt_helper(term->u.app.rhs, vars, size);
+ break;
+ case VAR:
+ if (term->u.var.type == BARENDREGT_VARIABLE)
+ break;
+ int ind = size - term->u.var.name - 1;
+ if (ind < 0) {
+ fprintf(stderr, "Unbound variable %d\n",
+ term->u.var.name);
+ term->u.var.name = name_generator();
+ } else {
+ term->u.var.name = vars[size - term->u.var.name - 1];
+ }
+ term->u.var.type = BARENDREGT_VARIABLE;
+ break;
+ default:
+ fprintf(stderr, "Invalid type %d\n", term->type);
+ }
+}
+
+static void to_bruijn_helper(struct term *term, int *vars, int size)
+{
+ assert(size < MAX_CONVERSION_VARS);
+ switch (term->type) {
+ case ABS:
+ vars[size] = term->u.abs.name;
+ to_bruijn_helper(term->u.abs.term, vars, size + 1);
+ term->u.abs.name = 0;
+ break;
+ case APP:
+ to_bruijn_helper(term->u.app.lhs, vars, size);
+ to_bruijn_helper(term->u.app.rhs, vars, size);
+ break;
+ case VAR:
+ if (term->u.var.type == BRUIJN_INDEX)
+ break;
+ int ind = -1;
+ for (int i = 0; i < size; i++) {
+ if (vars[i] == term->u.var.name) {
+ ind = i;
+ break;
+ }
+ }
+ if (ind < 0) {
+ fprintf(stderr, "Unbound variable %d\n",
+ term->u.var.name);
+ }
+ term->u.var.name = size - ind - 1;
+ term->u.var.type = BRUIJN_INDEX;
+ break;
+ default:
+ fprintf(stderr, "Invalid type %d\n", term->type);
+ }
+}
+
+void to_barendregt(struct term *term)
+{
+ int vars[MAX_CONVERSION_VARS] = { 0 };
+ to_barendregt_helper(term, vars, 0);
+}
+
+void to_bruijn(struct term *term)
+{
+ int vars[MAX_CONVERSION_VARS] = { 0 };
+ to_bruijn_helper(term, vars, 0);
+}
+
struct term *new_term(term_type type)
{
struct term *term = calloc(1, sizeof(*term));
@@ -38,7 +124,10 @@ void print_term(struct term *term)
{
switch (term->type) {
case ABS:
- printf("[{%d} ", term->u.abs.name);
+ if (term->u.abs.name)
+ printf("[{%d} ", term->u.abs.name);
+ else
+ printf("[");
print_term(term->u.abs.term);
printf("]");
break;
@@ -56,3 +145,26 @@ void print_term(struct term *term)
fprintf(stderr, "Invalid type %d\n", term->type);
}
}
+
+void print_scheme(struct term *term)
+{
+ switch (term->type) {
+ case ABS:
+ printf("(*lam \"%d\" ", term->u.abs.name);
+ print_scheme(term->u.abs.term);
+ printf(")");
+ break;
+ case APP:
+ printf("(*app ");
+ print_scheme(term->u.app.lhs);
+ printf(" ");
+ print_scheme(term->u.app.rhs);
+ printf(")");
+ break;
+ case VAR:
+ printf("(*var \"%d\")", term->u.var.name);
+ break;
+ default:
+ fprintf(stderr, "Invalid type %d\n", term->type);
+ }
+}