Skip to content

Instantly share code, notes, and snippets.

@takoeight0821 takoeight0821/main.c
Last active Apr 13, 2019

Embed
What would you like to do?
スタックマシンっぽい何か
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <gc.h>
union value;
struct env;
struct closure;
union value;
struct env
{
union value *array;
size_t length;
size_t max_length;
};
typedef void (*Code)(void);
struct closure
{
Code entry;
struct env env;
};
union value {
int integer;
struct closure clos;
};
void dump_value(union value v)
{
printf("%d(%p)", v.integer, v.clos.entry);
}
#define CHUNK 16
#define MARGIN (CHUNK * 2)
union value *Base;
union value *Current;
size_t stack_size;
void dump_stack()
{
printf("STACK [");
for (size_t i = 0; i < Current - Base; i++)
{
dump_value(*Current);
printf(", ");
}
printf("]");
}
struct env *Env;
void dump_env(struct env env)
{
printf("ENV (%lu): ", env.length);
for (size_t i = 0; i < env.length; i++)
{
printf("%d, ", env.array[i].integer);
}
printf("\n");
}
void push(union value value)
{
// メモリが足りなくなったら+CHUNK
if (Current - Base >= stack_size)
{
// printf("extend %ld %ld (+%d)\n", Current - Base, stack_size, CHUNK);
stack_size += CHUNK;
ptrdiff_t diff = Current - Base;
Base = realloc(Base, stack_size * sizeof(union value));
Current = Base + diff;
}
*Current = value;
Current++;
}
union value pop(void)
{
Current--;
// メモリがMARGIN余ったら-CHUNK
if (stack_size > MARGIN && Current - Base < stack_size - MARGIN - 1)
{
// printf("shorten %ld %ld (-%d)\n", Current - Base, stack_size, CHUNK);
stack_size -= CHUNK;
ptrdiff_t diff = Current - Base;
Base = realloc(Base, stack_size * sizeof(union value));
Current = Base + diff;
}
return *Current;
}
void push_env(struct env *env, union value value)
{
if (env->length >= env->max_length) {
// printf("extend env %ld %ld (+%d)\n", env->length, env->max_length, CHUNK);
env->max_length += CHUNK;
env->array = GC_REALLOC(env->array, sizeof(union value) * env->max_length);
}
env->array[env->length] = value;
env->length++;
}
void ldi(int val)
{
union value value = {.integer = val};
push(value);
}
void access(size_t i)
{
push(Env->array[Env->length - i - 1]);
}
struct env copy_env(void)
{
struct env new_env = { .array = GC_MALLOC(Env->max_length * sizeof(union value)), .length = Env->length, .max_length = Env->max_length };
for (size_t i = 0; i < Env->length; i++)
{
new_env.array[i] = Env->array[i];
}
return new_env;
}
void closure(Code f)
{
union value closure = {.clos = {.entry = f, .env = copy_env()}};
push(closure);
}
void apply(void)
{
union value closure = pop();
union value val = pop();
union value save = {.clos = {.entry = (Code)0xc105, .env = copy_env()}};
push(save);
*Env = closure.clos.env;
push_env(Env, closure);
push_env(Env, val);
closure.clos.entry();
}
void return_clos(void)
{
union value ret = pop();
struct env saved = pop().clos.env;
*Env = saved;
push(ret);
}
void let(void)
{
union value v = pop();
push_env(Env, v);
}
void endlet(void)
{
Env->length--;
}
void test(Code c1, Code c2)
{
if (pop().integer)
{
c1();
}
else
{
c2();
}
}
void add(void)
{
int n1 = pop().integer;
int n2 = pop().integer;
union value n3 = {.integer = n1 + n2};
push(n3);
}
void eq(void)
{
int n1 = pop().integer;
int n2 = pop().integer;
union value n3 = {.integer = n1 == n2};
push(n3);
}
void c1(void)
{
ldi(1);
}
void c2(void)
{
ldi(-1);
access(0);
add();
access(1);
apply();
access(0);
add();
}
void f(void)
{
ldi(1);
access(0);
eq();
test(c1, c2);
return_clos();
}
void entry(void)
{
closure(f);
let();
ldi(1000);
access(0);
apply();
endlet();
}
int main()
{
GC_INIT();
Base = malloc(sizeof(union value) * CHUNK);
Current = Base;
stack_size = CHUNK;
struct env e = {NULL, 0, CHUNK};
e.array = GC_MALLOC(sizeof(union value) * CHUNK);
Env = &e;
entry();
printf("\n");
/* dump_stack(*Stack); */
dump_value(*Current);
printf("\n");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.