--- /dev/null
+# Furface is a great cat
+print('Hello, world\n')
--- /dev/null
+Hello, world
--- /dev/null
+def outer() do
+ hi = 'Hello, world\n'
+
+ def inner() do
+ hi
+ end
+
+ inner
+end
+
+get_greeting = outer()
+
+print(get_greeting())
+
+
--- /dev/null
+Hello, world
--- /dev/null
+# Environment A is created here
+
+# outer references environment A
+def outer() do
+ # Environment B is created here referencing A
+
+ # middle references environment B
+ def middle() do
+ # Environment C is created here referencing B
+
+ # inner references environment C
+ def inner() do
+ # This is never executed
+ 42
+ end
+
+ inner
+ # At this point, environment C falls out of scope
+ # However, environment C is still referenced by inner, which is being returned
+ end
+
+ variable = middle()
+ # Now environment B -> variable -> inner -> C -> B
+
+ 42
+ # Nothing from the cycle is returned and B falls out of scope
+ # All references are lost, but reference counts are still > 0 because of the cycle
+end
+
+print(outer())
--- /dev/null
+42
\ No newline at end of file
--- /dev/null
+def increment(n) do
+ n + 1
+end
+
+def add(a, b) do
+ a + b
+end
+
+print(increment(41), '\n')
+print(add(40, 2), '\n')
--- /dev/null
+def make_incrementer(increment_amount) do
+ def result(i) do
+ increment_amount + i
+ end
+
+ result
+end
+
+increment_by_one = make_incrementer(1)
+increment_by_two = make_incrementer(2)
+
+print(increment_by_one(41), '\n')
+print(increment_by_two(40), '\n')
def generate_constant_expression(c_constant_expression):
return CONSTANT_EXPRESSION_MAPPING[c_constant_expression.value]
-def generate_symbol_expression(c_symbol_expression):
+def generate_symbol_expression(symbol_expression):
return 'Environment_get(environment, SYMBOL_LIST[{}] /* symbol: {} */)'.format(
- c_symbol_expression.symbol_list_index,
- c_symbol_expression.symbol,
+ symbol_expression.symbol_list_index,
+ symbol_expression.symbol,
)
def generate_variable_expression(expression):
)
def generate_function_call(function_call):
- return 'Environment_get(environment, "{}").instance.closure(environment, {}, {})'.format(
+ # TODO This gets called twice, which is really inefficient--normalization would also allow other clauses besides a variable reference
+ get_closure_clause = 'Environment_get(environment, "{}").instance.closure'.format(
function_call.name,
+ )
+ return '{}.call(environmentPool, {}.closed, {}, {})'.format(
+ get_closure_clause,
+ get_closure_clause,
function_call.argument_count,
# TODO This is just a single item containing a reference to the items list--make that clearer
generate_expression(function_call.argument_items),
# TODO Do we need to garbage collect the results of arbitrary statements?
return '{};'.format(generate_expression(statement.expression))
-def generate_symbol_assignment_statement(c_assignment_statement):
+def generate_symbol_assignment_statement(statement):
return 'Environment_set(environment, SYMBOL_LIST[{}] /* symbol: {} */, {});'.format(
- c_assignment_statement.target_symbol_list_index,
- c_assignment_statement.target,
- generate_expression(c_assignment_statement.expression),
+ statement.target_symbol_list_index,
+ statement.target,
+ generate_expression(statement.expression),
)
def generate_array_variable_initialization_statement(statement):
return generated_if_clause + generated_if_statements + generated_else_statements
def generate_function_declaration(statement):
- return 'Environment_set(environment, "{}", user${});'.format(statement.name, statement.name)
+ return 'Environment_set(environment, "{}", (Object){{ CLOSURE, (Instance)(Closure){{ environment, user${}$implementation }} }});'.format(statement.name, statement.name)
def generate_statement(statement):
return {
],
)
+NormalAssignmentStatement = collections.namedtuple(
+ 'NormalAssignmentStatement',
+ [
+ 'target',
+ 'expression',
+ ],
+)
+
NormalIfElseStatement = collections.namedtuple(
'NormalIfElseStatement',
[
'NormalFunctionDefinitionStatement',
[
'name',
+ 'argument_name_list',
'statement_list',
],
)
(),
NormalFunctionDefinitionStatement(
name=statement.name,
+ argument_name_list=statement.argument_name_list,
statement_list=normalize_statement_list(statement.statement_list),
),
)
+def normalize_assignment_statement(counter, statement):
+ counter, prestatements, normalized_expression = normalize_expression(counter, statement.expression)
+ return (
+ counter,
+ prestatements,
+ NormalAssignmentStatement(
+ target=statement.target,
+ expression=normalized_expression,
+ ),
+ )
+
def normalize_statement(counter, statement):
return {
- parsing.FurAssignmentStatement: fake_normalization, # TODO unfake this
+ parsing.FurAssignmentStatement: normalize_assignment_statement,
parsing.FurExpressionStatement: normalize_expression_statement,
parsing.FurFunctionDefinitionStatement: normalize_function_definition_statement,
}[type(statement)](counter, statement)
'or_level',
)(index, tokens)
-def _comma_separated_list_parser(index, tokens):
- start_index = index
+def _comma_separated_list_parser(subparser):
+ def result_parser(index, tokens):
+ start_index = index
- expressions = []
+ items = []
- success, index, expression = _expression_parser(index, tokens)
+ success, index, item = subparser(index, tokens)
- if success:
- expressions.append(expression)
- else:
- return (True, start_index, ())
+ if success:
+ items.append(item)
+ else:
+ return (True, start_index, ())
- while success and index < len(tokens) and tokens[index].type == 'comma':
- success = False
+ while success and index < len(tokens) and tokens[index].type == 'comma':
+ success = False
- if index + 1 < len(tokens):
- success, try_index, expression = _expression_parser(index + 1, tokens)
+ if index + 1 < len(tokens):
+ success, try_index, item = subparser(index + 1, tokens)
- if success:
- expressions.append(expression)
- index = try_index
+ if success:
+ items.append(item)
+ index = try_index
- return True, index, tuple(expressions)
+ return True, index, tuple(items)
+ return result_parser
+
+def _comma_separated_expression_list_parser(index, tokens):
+ return _comma_separated_list_parser(_expression_parser)(index, tokens)
FurFunctionCallExpression = collections.namedtuple(
'FurFunctionCallExpression',
'FurFunctionDefinitionStatement',
[
'name',
+ 'argument_name_list',
'statement_list',
],
)
return failure
index += 1
- success, index, arguments = _comma_separated_list_parser(index, tokens)
+ success, index, arguments = _comma_separated_expression_list_parser(index, tokens)
if not success:
return failure
tokens[index].line,
))
+ success, index, argument_name_list = _comma_separated_list_parser(_symbol_expression_parser)(
+ index,
+ tokens,
+ )
+
if tokens[index].type == 'close_parenthese':
index += 1
else:
else:
return failure
- return True, index, FurFunctionDefinitionStatement(name=name, statement_list=statement_list)
+ return True, index, FurFunctionDefinitionStatement(
+ name=name,
+ argument_name_list=tuple(an.value for an in argument_name_list),
+ statement_list=statement_list,
+ )
def _statement_parser(index, tokens):
_, index, _ = consume_newlines(index, tokens)
#include <stdlib.h>
#include <string.h>
+/* Some terminology used in function names:
+ * - initialize: These functions take a pointer and potentially some other arguments, and use those
+ * to initialize the value pointed to by self. Initialize functions DO NOT allocate the function,
+ * so they can be used to initialize stack-allocated variables.
+ * - construct: This allocates a value for a pointer, initializes it, and returns it. This is for
+ * heap-allocated values. It may be as simple as allocating the memory, calling an initialize, and
+ * returning it.
+ * - deinitialize: These functions dereference or free any objects pointed to by the self pointer's
+ * value, but they don't actually free the self pointer. This is useful for stack-allocated objects
+ * which point to heap-allocated objects.
+ * - destruct: This dereferences or frees memory pointed to by the self argument, and all the
+ * pointers on the self argument.
+ */
+
{% for standard_library in standard_libraries %}
#include <{{standard_library}}>
{% endfor %}
typedef struct EnvironmentNode EnvironmentNode;
struct Environment;
typedef struct Environment Environment;
+struct EnvironmentPool;
+typedef struct EnvironmentPool EnvironmentPool;
const char* const STRING_LITERAL_LIST[] = {
{% for string_literal in string_literal_list %}
STRING
};
+struct Closure;
+typedef struct Closure Closure;
+struct Closure
+{
+ Environment* closed;
+ Object (*call)(EnvironmentPool*, Environment*, size_t, Object*);
+};
+
union Instance
{
bool boolean;
- Object (*closure)(Environment*, size_t, Object*);
+ Closure closure;
int32_t integer;
const char* string;
};
struct Environment
{
- size_t referenceCount;
+ bool mark;
+ bool live;
+
Environment* parent;
EnvironmentNode* root;
};
-Environment* Environment_construct(Environment* parent)
+void Environment_initialize(Environment* self, Environment* parent)
{
- Environment* result = malloc(sizeof(Environment));
- result->referenceCount = 1;
- result->parent = parent;
- result->root = NULL;
- return result;
+ self->parent = parent;
+ self->root = NULL;
+
+ // We are currently only ever initializing environments at the beginning of running functions, so
+ // for now at least we can assume that we want it to be live immediately.
+ self->live = true;
}
-void Environment_destruct(Environment* self)
+void Environment_deinitialize(Environment* self)
{
- self->referenceCount--;
+ EnvironmentNode* next;
+ for(EnvironmentNode* node = self->root; node != NULL; node = next)
+ {
+ next = node->next;
+ free(node);
+ }
+}
- if(self->referenceCount == 0)
+void Environment_setLive(Environment* self, bool live)
+{
+ self->live = live;
+}
+
+void Environment_mark(Environment* self)
+{
+ if(self == NULL) return;
+ if(self->mark) return; // Prevents infinite recursion in the case of cycles
+
+ self->mark = true;
+
+ Environment_mark(self->parent);
+
+ for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
{
- EnvironmentNode* next;
- for(EnvironmentNode* node = self->root; node != NULL; node = next)
+ switch(node->value.type)
{
- // No objects are allocated on the heap (yet!) so we don't need to free anything else
- next = node->next;
- free(node);
+ case BOOLEAN:
+ case INTEGER:
+ case STRING:
+ break;
+
+ case CLOSURE:
+ Environment_mark(node->value.instance.closure.closed);
+ break;
+
+ default:
+ assert(false);
}
- free(self);
}
}
assert(false);
}
+# define POOL_SIZE 64
+struct EnvironmentPool
+{
+ int8_t freeIndex;
+ bool allocatedFlags[POOL_SIZE];
+ Environment environments[POOL_SIZE];
+ EnvironmentPool* overflow;
+};
+
+EnvironmentPool* EnvironmentPool_construct();
+void EnvironmentPool_initialize(EnvironmentPool*);
+void EnvironmentPool_deinitialize(EnvironmentPool*);
+void EnvironmentPool_destruct(EnvironmentPool*);
+
+EnvironmentPool* EnvironmentPool_construct()
+{
+ EnvironmentPool* result = malloc(sizeof(EnvironmentPool));
+ EnvironmentPool_initialize(result);
+ return result;
+}
+
+void EnvironmentPool_initialize(EnvironmentPool* self)
+{
+ self->overflow = NULL;
+ self->freeIndex = 0;
+
+ for(size_t i = 0; i < POOL_SIZE; i++)
+ {
+ self->allocatedFlags[i] = false;
+ self->environments[i].live = false;
+ }
+}
+
+void EnvironmentPool_deinitialize(EnvironmentPool* self)
+{
+ // We can assume if this is being called, none of the Environments are live
+ for(int8_t i = 0; i < POOL_SIZE; i++)
+ {
+ if(self->allocatedFlags[i]) Environment_deinitialize(&(self->environments[i]));
+ }
+
+ EnvironmentPool_destruct(self->overflow);
+}
+
+void EnvironmentPool_destruct(EnvironmentPool* self)
+{
+ if(self == NULL) return;
+ EnvironmentPool_deinitialize(self);
+ free(self);
+}
+
+void EnvironmentPool_GC(EnvironmentPool* self)
+{
+ // Unmark all the environments
+ for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
+ {
+ for(int8_t i = 0; i < POOL_SIZE; i++)
+ {
+ current->environments[i].mark = false;
+ }
+ }
+
+ // Mark live enviroments and environments referenced by live environments
+ for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
+ {
+ for(int8_t i = 0; i < POOL_SIZE; i++)
+ {
+ if(current->environments[i].live)
+ {
+ Environment_mark(&(current->environments[i]));
+ }
+ }
+ }
+
+ // TODO We never free pools until the very end--we could free a pool if two pools are empty
+ for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
+ {
+ for(int8_t i = POOL_SIZE - 1; i >= 0; i--)
+ {
+ if(!current->environments[i].mark && current->allocatedFlags[i])
+ {
+ Environment_deinitialize(&(current->environments[i]));
+ current->allocatedFlags[i] = false;
+ current->freeIndex = i;
+ }
+ }
+ }
+}
+
+Environment* EnvironmentPool_allocate(EnvironmentPool* self)
+{
+ for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
+ {
+ for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
+ {
+ if(!current->allocatedFlags[current->freeIndex])
+ {
+ current->allocatedFlags[current->freeIndex] = true;
+ return &(current->environments[current->freeIndex]);
+ }
+ }
+ }
+
+ EnvironmentPool_GC(self);
+
+ EnvironmentPool* previous;
+ for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
+ {
+ for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
+ {
+ if(!current->allocatedFlags[current->freeIndex])
+ {
+ current->allocatedFlags[current->freeIndex] = true;
+ return &(current->environments[current->freeIndex]);
+ }
+ else
+ {
+ previous = current;
+ }
+ }
+ }
+
+ previous->overflow = EnvironmentPool_construct();
+ return EnvironmentPool_allocate(previous->overflow);
+}
+
Object integerLiteral(int32_t literal)
{
Object result;
{% endfor %}
{% if 'pow' in builtins %}
-Object builtin$pow$implementation(Environment* parent, size_t argc, Object* args)
+Object builtin$pow$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Object* args)
{
assert(argc == 2);
return result;
}
-Object builtin$pow = { CLOSURE, (Instance)builtin$pow$implementation };
+Object builtin$pow = { CLOSURE, (Instance)(Closure){ NULL, builtin$pow$implementation } };
{% endif %}
{% if 'print' in builtins %}
-Object builtin$print$implementation(Environment* parent, size_t argc, Object* args)
+Object builtin$print$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Object* args)
{
for(size_t i = 0; i < argc; i++)
{
fputs(output.instance.boolean ? "true" : "false", stdout);
break;
+ case CLOSURE:
+ // TODO Print something better
+ printf("<Closure>");
+ break;
+
case INTEGER:
printf("%" PRId32, output.instance.integer);
break;
return FALSE;
}
-Object builtin$print = { CLOSURE, (Instance)builtin$print$implementation };
+Object builtin$print = { CLOSURE, (Instance)(Closure){ NULL, builtin$print$implementation } };
{% endif %}
{% for function_definition in function_definition_list %}
-Object user${{function_definition.name}}$implementation(Environment* parent, size_t argc, Object* args)
+Object user${{function_definition.name}}$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Object* args)
{
- Environment* environment = Environment_construct(parent);
+ assert(argc == {{ function_definition.argument_name_list|length }});
+
+ Environment* environment = EnvironmentPool_allocate(environmentPool);
+ Environment_initialize(environment, parent);
+
+ {% for argument_name in function_definition.argument_name_list %}
+ Environment_set(environment, "{{ argument_name }}", args[{{ loop.index0 }}]);
+ {% endfor %}
{% for statement in function_definition.statement_list[:-1] %}
{{ generate_statement(statement) }}
{% endfor %}
Object result = {{ generate_statement(function_definition.statement_list[-1]) }}
- Environment_destruct(environment);
+
+ Environment_setLive(environment, false);
return result;
}
-Object user${{function_definition.name}} = { CLOSURE, (Instance)user${{function_definition.name}}$implementation };
{% endfor %}
-
int main(int argc, char** argv)
{
- Environment* environment = Environment_construct(NULL);
+ EnvironmentPool* environmentPool = EnvironmentPool_construct();
+ Environment* environment = EnvironmentPool_allocate(environmentPool);
+ Environment_initialize(environment, NULL);
// TODO Use the symbol from SYMBOL_LIST
{% for builtin in builtins %}
{{ generate_statement(statement) }}
{% endfor %}
- Environment_destruct(environment);
-
+ Environment_setLive(environment, false);
+ EnvironmentPool_destruct(environmentPool);
return 0;
}
index += 1
continue
+ if source[index] == '#':
+ while index < len(source) and source[index] != '\n':
+ index += 1
+
+ continue
+
success = False
for matcher in _TOKEN_MATCHERS:
'CFunctionDefinition',
[
'name',
+ 'argument_name_list',
'statement_list',
],
)
if expression.value in ['true', 'false']:
return CConstantExpression(value=expression.value)
- if expression.value not in accumulators.symbol_list:
- symbol_list.append(expression.value)
+ try:
+ symbol_list_index = accumulators.symbol_list.index(expression.value)
+ except ValueError:
+ symbol_list_index = len(accumulators.symbol_list)
+ accumulators.symbol_list.append(expression.value)
return CSymbolExpression(
symbol=expression.value,
- symbol_list_index=accumulators.symbol_list.index(expression.value),
+ symbol_list_index=symbol_list_index,
)
CInfixDeclaration = collections.namedtuple(
def transform_symbol_assignment_statement(accumulators, assignment_statement):
# TODO Check that target is not a builtin
- if assignment_statement.target not in accumulators.symbol_list:
+ try:
+ symbol_list_index = accumulators.symbol_list.index(assignment_statement.target)
+ except ValueError:
+ symbol_list_index = len(accumulators.symbol_list)
accumulators.symbol_list.append(assignment_statement.target)
return CSymbolAssignmentStatement(
target=assignment_statement.target,
- target_symbol_list_index=accumulators.symbol_list.index(assignment_statement.target),
+ target_symbol_list_index=symbol_list_index,
expression=transform_expression(
accumulators,
assignment_statement.expression,
)
def transform_expression_statement(accumulators, statement):
- # TODO At some point we can verify that all expression types are supported and just call transform_expression
- expression = {
- parsing.FurFunctionCallExpression: transform_function_call_expression,
- parsing.FurInfixExpression: transform_expression,
- parsing.FurIntegerLiteralExpression: transform_expression,
- parsing.FurSymbolExpression: transform_expression,
- normalization.NormalFunctionCallExpression: transform_function_call_expression,
- normalization.NormalVariableExpression: transform_expression,
- }[type(statement.expression)](accumulators, statement.expression)
-
return CExpressionStatement(
- expression=expression,
+ expression=transform_expression(accumulators, statement.expression),
)
def transform_if_else_statement(accumulators, statement):
if any(fd.name == statement.name for fd in accumulators.function_definition_list):
raise Exception('A function with name "{}" already exists'.format(statement.name))
+ # TODO Add argument names to the symbol table
accumulators.function_definition_list.append(CFunctionDefinition(
name=statement.name,
+ argument_name_list=statement.argument_name_list,
statement_list=tuple(transform_statement(accumulators, s) for s in statement.statement_list)
))
def transform_statement(accumulators, statement):
return {
- parsing.FurAssignmentStatement: transform_symbol_assignment_statement,
parsing.FurExpressionStatement: transform_expression_statement,
normalization.NormalArrayVariableInitializationStatement: transform_array_variable_initialization_statement,
+ normalization.NormalAssignmentStatement: transform_symbol_assignment_statement,
normalization.NormalExpressionStatement: transform_expression_statement,
normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement,
normalization.NormalIfElseStatement: transform_if_else_statement,
projects / fur / commitdiff