Here comes my unexpected fourth part - even I didn’t expect it - of the article series on programming language design. In this article we‘ll develop a functional language.
INTRODUCTION TO FUNCTIONAL PROGRAMMING LANGUAGES
Functional programming represents a paradigm where computation is treated as the evaluation of mathematical functions, avoiding changing state and mutable data. Building a minimal functional programming language provides deep insights into how programming languages work at their core, from lexical analysis through evaluation. This tutorial guides you through creating a complete, working functional language called "PureFunc" designed specifically for teaching functional programming concepts to students.
The language we will build supports immutable data structures, first-class functions, higher-order functions, closures, pattern matching, recursion, and lazy evaluation. Every value in PureFunc is immutable by design, forcing students to think in terms of transformations rather than mutations. The syntax is deliberately simple and clean, removing unnecessary complexity that might distract from learning core functional concepts.
Our implementation will be written in Python for accessibility, but the concepts translate to any host language. We will build the complete pipeline: lexer, parser, abstract syntax tree, type checker, and evaluator. Each component will be explained thoroughly with running examples that build upon each other.
ARCHITECTURAL OVERVIEW
Before diving into implementation details, we need to understand the architecture of our language interpreter. The process of executing a PureFunc program follows these stages:
First, the lexer (also called tokenizer or scanner) reads the raw source code as a string and breaks it into meaningful tokens. Tokens are the smallest units of meaning in the language, such as keywords, identifiers, numbers, operators, and punctuation. The lexer removes whitespace and comments, producing a stream of tokens.
Second, the parser consumes the token stream and builds an Abstract Syntax Tree (AST). The AST represents the hierarchical structure of the program according to the language's grammar rules. Each node in the tree represents a construct in the language, such as a function definition, function application, or literal value.
Third, the type checker (optional but recommended) traverses the AST to verify that the program is type-safe. It infers types for expressions and ensures that functions are called with arguments of the correct types. This catches many errors before execution.
Fourth, the evaluator walks the AST and computes the result. In our case, we will implement an environment-based interpreter that maintains a mapping from variable names to their values. The evaluator handles function calls, variable lookups, and all other runtime behavior.
DESIGNING THE LANGUAGE SYNTAX
PureFunc uses a clean, minimal syntax inspired by ML-family languages and Lisp. The syntax is designed to be unambiguous and easy to parse while remaining readable for students. Let us examine the core syntactic elements.
Function definitions use the "fn" keyword followed by parameter names and an arrow pointing to the function body. For example, a function that adds two numbers looks like this:
fn x y -> x + y
This defines an anonymous function taking two parameters. To bind this function to a name, we use the "let" keyword:
let add = fn x y -> x + y
Function application uses simple juxtaposition, where the function name is followed by its arguments:
add 3 5
This applies the add function to arguments 3 and 5, producing 8.
Conditional expressions use "if", "then", and "else" keywords:
if x > 0 then x else 0
Lists are fundamental in functional programming. We represent lists using square brackets with elements separated by commas:
[1, 2, 3, 4, 5]
The empty list is simply:
[]
Pattern matching allows destructuring data and is essential for working with lists and other structures. We use the "match" keyword:
match mylist with
[] -> 0
[head | tail] -> head + sum tail
This matches an empty list returning 0, or a non-empty list where we bind the first element to "head" and the rest to "tail".
Let bindings create local scopes and can be used for intermediate calculations:
let x = 10 in
let y = 20 in
x + y
Comments begin with a hash symbol and continue to the end of the line:
# This is a comment
IMPLEMENTING THE LEXER
The lexer transforms source code into tokens. Each token has a type and a value. We need to recognize keywords, identifiers, numbers, operators, and punctuation. Let us implement a complete lexer for PureFunc.
We start by defining token types. Each token type represents a category of lexical element:
class TokenType:
# Keywords
LET = 'LET'
IN = 'IN'
FN = 'FN'
IF = 'IF'
THEN = 'THEN'
ELSE = 'ELSE'
MATCH = 'MATCH'
WITH = 'WITH'
# Literals
NUMBER = 'NUMBER'
IDENTIFIER = 'IDENTIFIER'
# Operators
PLUS = 'PLUS'
MINUS = 'MINUS'
MULTIPLY = 'MULTIPLY'
DIVIDE = 'DIVIDE'
EQUALS = 'EQUALS'
NOT_EQUALS = 'NOT_EQUALS'
LESS_THAN = 'LESS_THAN'
GREATER_THAN = 'GREATER_THAN'
LESS_EQUAL = 'LESS_EQUAL'
GREATER_EQUAL = 'GREATER_EQUAL'
# Punctuation
LPAREN = 'LPAREN'
RPAREN = 'RPAREN'
LBRACKET = 'LBRACKET'
RBRACKET = 'RBRACKET'
ARROW = 'ARROW'
PIPE = 'PIPE'
COMMA = 'COMMA'
ASSIGN = 'ASSIGN'
# Special
EOF = 'EOF'
Each token is represented as a simple object containing its type and value:
class Token:
def __init__(self, token_type, value, line, column):
self.type = token_type
self.value = value
self.line = line
self.column = column
def __repr__(self):
return f'Token({self.type}, {self.value}, {self.line}:{self.column})'
The lexer itself maintains the current position in the source code and produces tokens one at a time:
class Lexer:
def __init__(self, source):
self.source = source
self.position = 0
self.line = 1
self.column = 1
self.current_char = self.source[0] if source else None
self.keywords = {
'let': TokenType.LET,
'in': TokenType.IN,
'fn': TokenType.FN,
'if': TokenType.IF,
'then': TokenType.THEN,
'else': TokenType.ELSE,
'match': TokenType.MATCH,
'with': TokenType.WITH,
}
def advance(self):
"""Move to the next character in the source."""
if self.current_char == '\n':
self.line += 1
self.column = 1
else:
self.column += 1
self.position += 1
if self.position >= len(self.source):
self.current_char = None
else:
self.current_char = self.source[self.position]
def peek(self, offset=1):
"""Look ahead at the next character without consuming it."""
peek_pos = self.position + offset
if peek_pos >= len(self.source):
return None
return self.source[peek_pos]
def skip_whitespace(self):
"""Skip over whitespace characters."""
while self.current_char is not None and self.current_char.isspace():
self.advance()
def skip_comment(self):
"""Skip over comments that start with #."""
while self.current_char is not None and self.current_char != '\n':
self.advance()
def read_number(self):
"""Read a numeric literal."""
start_line = self.line
start_column = self.column
num_str = ''
while self.current_char is not None and (self.current_char.isdigit() or self.current_char == '.'):
num_str += self.current_char
self.advance()
if '.' in num_str:
return Token(TokenType.NUMBER, float(num_str), start_line, start_column)
else:
return Token(TokenType.NUMBER, int(num_str), start_line, start_column)
def read_identifier(self):
"""Read an identifier or keyword."""
start_line = self.line
start_column = self.column
id_str = ''
while self.current_char is not None and (self.current_char.isalnum() or self.current_char == '_'):
id_str += self.current_char
self.advance()
token_type = self.keywords.get(id_str, TokenType.IDENTIFIER)
return Token(token_type, id_str, start_line, start_column)
def get_next_token(self):
"""Get the next token from the source."""
while self.current_char is not None:
if self.current_char.isspace():
self.skip_whitespace()
continue
if self.current_char == '#':
self.skip_comment()
continue
if self.current_char.isdigit():
return self.read_number()
if self.current_char.isalpha() or self.current_char == '_':
return self.read_identifier()
# Single character tokens
line = self.line
column = self.column
if self.current_char == '+':
self.advance()
return Token(TokenType.PLUS, '+', line, column)
if self.current_char == '*':
self.advance()
return Token(TokenType.MULTIPLY, '*', line, column)
if self.current_char == '/':
self.advance()
return Token(TokenType.DIVIDE, '/', line, column)
if self.current_char == '(':
self.advance()
return Token(TokenType.LPAREN, '(', line, column)
if self.current_char == ')':
self.advance()
return Token(TokenType.RPAREN, ')', line, column)
if self.current_char == '[':
self.advance()
return Token(TokenType.LBRACKET, '[', line, column)
if self.current_char == ']':
self.advance()
return Token(TokenType.RBRACKET, ']', line, column)
if self.current_char == ',':
self.advance()
return Token(TokenType.COMMA, ',', line, column)
if self.current_char == '|':
self.advance()
return Token(TokenType.PIPE, '|', line, column)
# Multi-character tokens
if self.current_char == '-':
if self.peek() == '>':
self.advance()
self.advance()
return Token(TokenType.ARROW, '->', line, column)
else:
self.advance()
return Token(TokenType.MINUS, '-', line, column)
if self.current_char == '=':
if self.peek() == '=':
self.advance()
self.advance()
return Token(TokenType.EQUALS, '==', line, column)
else:
self.advance()
return Token(TokenType.ASSIGN, '=', line, column)
if self.current_char == '!':
if self.peek() == '=':
self.advance()
self.advance()
return Token(TokenType.NOT_EQUALS, '!=', line, column)
if self.current_char == '<':
if self.peek() == '=':
self.advance()
self.advance()
return Token(TokenType.LESS_EQUAL, '<=', line, column)
else:
self.advance()
return Token(TokenType.LESS_THAN, '<', line, column)
if self.current_char == '>':
if self.peek() == '=':
self.advance()
self.advance()
return Token(TokenType.GREATER_EQUAL, '>=', line, column)
else:
self.advance()
return Token(TokenType.GREATER_THAN, '>', line, column)
raise SyntaxError(f'Unexpected character: {self.current_char} at {line}:{column}')
return Token(TokenType.EOF, None, self.line, self.column)
def tokenize(self):
"""Tokenize the entire source and return a list of tokens."""
tokens = []
while True:
token = self.get_next_token()
tokens.append(token)
if token.type == TokenType.EOF:
break
return tokens
This lexer handles all the syntactic elements of PureFunc. It correctly identifies keywords, operators, numbers, and identifiers while skipping whitespace and comments. The lexer maintains line and column information for error reporting.
BUILDING THE ABSTRACT SYNTAX TREE
The Abstract Syntax Tree represents the structure of our program. Each node in the tree corresponds to a language construct. We define classes for each type of AST node.
The base class for all AST nodes provides a common interface:
class ASTNode:
"""Base class for all AST nodes."""
pass
Literal values such as numbers are the simplest nodes:
class NumberLiteral(ASTNode):
def __init__(self, value):
self.value = value
def __repr__(self):
return f'NumberLiteral({self.value})'
Variables are represented by identifier nodes:
class Variable(ASTNode):
def __init__(self, name):
self.name = name
def __repr__(self):
return f'Variable({self.name})'
Binary operations combine two expressions with an operator:
class BinaryOp(ASTNode):
def __init__(self, left, operator, right):
self.left = left
self.operator = operator
self.right = right
def __repr__(self):
return f'BinaryOp({self.left}, {self.operator}, {self.right})'
Function definitions capture parameters and the body expression:
class FunctionDef(ASTNode):
def __init__(self, parameters, body):
self.parameters = parameters
self.body = body
def __repr__(self):
return f'FunctionDef({self.parameters}, {self.body})'
Function application applies a function to arguments:
class FunctionCall(ASTNode):
def __init__(self, function, arguments):
self.function = function
self.arguments = arguments
def __repr__(self):
return f'FunctionCall({self.function}, {self.arguments})'
Conditional expressions evaluate one of two branches based on a condition:
class IfExpression(ASTNode):
def __init__(self, condition, then_branch, else_branch):
self.condition = condition
self.then_branch = then_branch
self.else_branch = else_branch
def __repr__(self):
return f'IfExpression({self.condition}, {self.then_branch}, {self.else_branch})'
Let bindings introduce local variables:
class LetBinding(ASTNode):
def __init__(self, name, value, body):
self.name = name
self.value = value
self.body = body
def __repr__(self):
return f'LetBinding({self.name}, {self.value}, {self.body})'
Lists are fundamental data structures:
class ListLiteral(ASTNode):
def __init__(self, elements):
self.elements = elements
def __repr__(self):
return f'ListLiteral({self.elements})'
Pattern matching enables destructuring:
class MatchExpression(ASTNode):
def __init__(self, value, cases):
self.value = value
self.cases = cases
def __repr__(self):
return f'MatchExpression({self.value}, {self.cases})'
class MatchCase(ASTNode):
def __init__(self, pattern, result):
self.pattern = pattern
self.result = result
def __repr__(self):
return f'MatchCase({self.pattern}, {self.result})'
Patterns can be empty lists, variables, or cons patterns:
class EmptyListPattern(ASTNode):
def __repr__(self):
return 'EmptyListPattern()'
class VariablePattern(ASTNode):
def __init__(self, name):
self.name = name
def __repr__(self):
return f'VariablePattern({self.name})'
class ConsPattern(ASTNode):
def __init__(self, head, tail):
self.head = head
self.tail = tail
def __repr__(self):
return f'ConsPattern({self.head}, {self.tail})'
IMPLEMENTING THE PARSER
The parser transforms the token stream into an AST. We use a recursive descent parser, which is straightforward to implement and understand. Each grammar rule becomes a parsing method.
The parser maintains the current position in the token stream and provides methods to consume tokens:
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.position = 0
self.current_token = self.tokens[0] if tokens else None
def advance(self):
"""Move to the next token."""
self.position += 1
if self.position < len(self.tokens):
self.current_token = self.tokens[self.position]
else:
self.current_token = None
def expect(self, token_type):
"""Consume a token of the expected type or raise an error."""
if self.current_token is None:
raise SyntaxError(f'Expected {token_type} but reached end of input')
if self.current_token.type != token_type:
raise SyntaxError(f'Expected {token_type} but got {self.current_token.type} at {self.current_token.line}:{self.current_token.column}')
token = self.current_token
self.advance()
return token
def parse(self):
"""Parse the entire program."""
return self.parse_expression()
def parse_expression(self):
"""Parse an expression (the top-level grammar rule)."""
if self.current_token.type == TokenType.LET:
return self.parse_let_binding()
elif self.current_token.type == TokenType.FN:
return self.parse_function_def()
elif self.current_token.type == TokenType.IF:
return self.parse_if_expression()
elif self.current_token.type == TokenType.MATCH:
return self.parse_match_expression()
else:
return self.parse_comparison()
def parse_let_binding(self):
"""Parse a let binding: let x = value in body"""
self.expect(TokenType.LET)
name_token = self.expect(TokenType.IDENTIFIER)
self.expect(TokenType.ASSIGN)
value = self.parse_expression()
self.expect(TokenType.IN)
body = self.parse_expression()
return LetBinding(name_token.value, value, body)
def parse_function_def(self):
"""Parse a function definition: fn x y -> body"""
self.expect(TokenType.FN)
parameters = []
while self.current_token.type == TokenType.IDENTIFIER:
param_token = self.expect(TokenType.IDENTIFIER)
parameters.append(param_token.value)
self.expect(TokenType.ARROW)
body = self.parse_expression()
return FunctionDef(parameters, body)
def parse_if_expression(self):
"""Parse an if expression: if cond then expr1 else expr2"""
self.expect(TokenType.IF)
condition = self.parse_expression()
self.expect(TokenType.THEN)
then_branch = self.parse_expression()
self.expect(TokenType.ELSE)
else_branch = self.parse_expression()
return IfExpression(condition, then_branch, else_branch)
def parse_match_expression(self):
"""Parse a match expression: match value with cases"""
self.expect(TokenType.MATCH)
value = self.parse_expression()
self.expect(TokenType.WITH)
cases = []
while self.current_token.type != TokenType.EOF:
pattern = self.parse_pattern()
self.expect(TokenType.ARROW)
result = self.parse_expression()
cases.append(MatchCase(pattern, result))
if self.current_token.type not in [TokenType.LBRACKET, TokenType.IDENTIFIER]:
break
return MatchExpression(value, cases)
def parse_pattern(self):
"""Parse a pattern for match expressions."""
if self.current_token.type == TokenType.LBRACKET:
self.advance()
if self.current_token.type == TokenType.RBRACKET:
self.advance()
return EmptyListPattern()
else:
head_token = self.expect(TokenType.IDENTIFIER)
head = VariablePattern(head_token.value)
self.expect(TokenType.PIPE)
tail_token = self.expect(TokenType.IDENTIFIER)
tail = VariablePattern(tail_token.value)
self.expect(TokenType.RBRACKET)
return ConsPattern(head, tail)
elif self.current_token.type == TokenType.IDENTIFIER:
name_token = self.expect(TokenType.IDENTIFIER)
return VariablePattern(name_token.value)
else:
raise SyntaxError(f'Invalid pattern at {self.current_token.line}:{self.current_token.column}')
def parse_comparison(self):
"""Parse comparison operations."""
left = self.parse_additive()
while self.current_token and self.current_token.type in [
TokenType.EQUALS, TokenType.NOT_EQUALS,
TokenType.LESS_THAN, TokenType.GREATER_THAN,
TokenType.LESS_EQUAL, TokenType.GREATER_EQUAL
]:
operator = self.current_token.type
self.advance()
right = self.parse_additive()
left = BinaryOp(left, operator, right)
return left
def parse_additive(self):
"""Parse addition and subtraction."""
left = self.parse_multiplicative()
while self.current_token and self.current_token.type in [TokenType.PLUS, TokenType.MINUS]:
operator = self.current_token.type
self.advance()
right = self.parse_multiplicative()
left = BinaryOp(left, operator, right)
return left
def parse_multiplicative(self):
"""Parse multiplication and division."""
left = self.parse_application()
while self.current_token and self.current_token.type in [TokenType.MULTIPLY, TokenType.DIVIDE]:
operator = self.current_token.type
self.advance()
right = self.parse_application()
left = BinaryOp(left, operator, right)
return left
def parse_application(self):
"""Parse function application."""
left = self.parse_primary()
while self.current_token and self.current_token.type in [
TokenType.NUMBER, TokenType.IDENTIFIER, TokenType.LPAREN, TokenType.LBRACKET
]:
argument = self.parse_primary()
left = FunctionCall(left, [argument])
return left
def parse_primary(self):
"""Parse primary expressions (literals, variables, parenthesized expressions, lists)."""
if self.current_token.type == TokenType.NUMBER:
value = self.current_token.value
self.advance()
return NumberLiteral(value)
elif self.current_token.type == TokenType.IDENTIFIER:
name = self.current_token.value
self.advance()
return Variable(name)
elif self.current_token.type == TokenType.LPAREN:
self.advance()
expr = self.parse_expression()
self.expect(TokenType.RPAREN)
return expr
elif self.current_token.type == TokenType.LBRACKET:
return self.parse_list()
else:
raise SyntaxError(f'Unexpected token: {self.current_token.type} at {self.current_token.line}:{self.current_token.column}')
def parse_list(self):
"""Parse a list literal."""
self.expect(TokenType.LBRACKET)
elements = []
if self.current_token.type == TokenType.RBRACKET:
self.advance()
return ListLiteral(elements)
elements.append(self.parse_expression())
while self.current_token.type == TokenType.COMMA:
self.advance()
elements.append(self.parse_expression())
self.expect(TokenType.RBRACKET)
return ListLiteral(elements)
This parser implements the complete grammar of PureFunc using recursive descent. Each method corresponds to a grammar rule and builds the appropriate AST node. The parser handles operator precedence correctly by having separate methods for different precedence levels.
IMPLEMENTING THE EVALUATOR
The evaluator executes the AST by recursively evaluating each node. We use an environment to track variable bindings. The environment is a dictionary mapping variable names to their values.
First, we define value types that can exist at runtime:
class Value:
"""Base class for runtime values."""
pass
class NumberValue(Value):
def __init__(self, value):
self.value = value
def __repr__(self):
return f'NumberValue({self.value})'
def __eq__(self, other):
return isinstance(other, NumberValue) and self.value == other.value
class BoolValue(Value):
def __init__(self, value):
self.value = value
def __repr__(self):
return f'BoolValue({self.value})'
def __eq__(self, other):
return isinstance(other, BoolValue) and self.value == other.value
class ListValue(Value):
def __init__(self, elements):
self.elements = tuple(elements) # Immutable
def __repr__(self):
return f'ListValue({list(self.elements)})'
def __eq__(self, other):
return isinstance(other, ListValue) and self.elements == other.elements
class FunctionValue(Value):
def __init__(self, parameters, body, closure):
self.parameters = parameters
self.body = body
self.closure = closure # Captured environment
def __repr__(self):
return f'FunctionValue({self.parameters}, ...)'
The environment is implemented as an immutable chain of scopes:
class Environment:
def __init__(self, parent=None):
self.bindings = {}
self.parent = parent
def define(self, name, value):
"""Create a new environment with an additional binding."""
new_env = Environment(self.parent)
new_env.bindings = self.bindings.copy()
new_env.bindings[name] = value
return new_env
def lookup(self, name):
"""Look up a variable in the environment chain."""
if name in self.bindings:
return self.bindings[name]
elif self.parent is not None:
return self.parent.lookup(name)
else:
raise NameError(f'Undefined variable: {name}')
def extend(self, names, values):
"""Create a new environment with multiple bindings."""
new_env = Environment(self)
for name, value in zip(names, values):
new_env.bindings[name] = value
return new_env
The evaluator recursively evaluates AST nodes:
class Evaluator:
def __init__(self):
self.global_env = self.create_global_environment()
def create_global_environment(self):
"""Create the global environment with built-in functions."""
env = Environment()
# Built-in functions will be added here
# For now, we start with an empty environment
return env
def evaluate(self, node, env):
"""Evaluate an AST node in the given environment."""
if isinstance(node, NumberLiteral):
return NumberValue(node.value)
elif isinstance(node, Variable):
return env.lookup(node.name)
elif isinstance(node, BinaryOp):
return self.evaluate_binary_op(node, env)
elif isinstance(node, FunctionDef):
return FunctionValue(node.parameters, node.body, env)
elif isinstance(node, FunctionCall):
return self.evaluate_function_call(node, env)
elif isinstance(node, IfExpression):
return self.evaluate_if_expression(node, env)
elif isinstance(node, LetBinding):
return self.evaluate_let_binding(node, env)
elif isinstance(node, ListLiteral):
return self.evaluate_list_literal(node, env)
elif isinstance(node, MatchExpression):
return self.evaluate_match_expression(node, env)
else:
raise RuntimeError(f'Unknown AST node type: {type(node)}')
def evaluate_binary_op(self, node, env):
"""Evaluate binary operations."""
left_val = self.evaluate(node.left, env)
right_val = self.evaluate(node.right, env)
if node.operator == TokenType.PLUS:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return NumberValue(left_val.value + right_val.value)
else:
raise TypeError('Addition requires numbers')
elif node.operator == TokenType.MINUS:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return NumberValue(left_val.value - right_val.value)
else:
raise TypeError('Subtraction requires numbers')
elif node.operator == TokenType.MULTIPLY:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return NumberValue(left_val.value * right_val.value)
else:
raise TypeError('Multiplication requires numbers')
elif node.operator == TokenType.DIVIDE:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
if right_val.value == 0:
raise ZeroDivisionError('Division by zero')
return NumberValue(left_val.value / right_val.value)
else:
raise TypeError('Division requires numbers')
elif node.operator == TokenType.EQUALS:
return BoolValue(left_val == right_val)
elif node.operator == TokenType.NOT_EQUALS:
return BoolValue(left_val != right_val)
elif node.operator == TokenType.LESS_THAN:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return BoolValue(left_val.value < right_val.value)
else:
raise TypeError('Comparison requires numbers')
elif node.operator == TokenType.GREATER_THAN:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return BoolValue(left_val.value > right_val.value)
else:
raise TypeError('Comparison requires numbers')
elif node.operator == TokenType.LESS_EQUAL:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return BoolValue(left_val.value <= right_val.value)
else:
raise TypeError('Comparison requires numbers')
elif node.operator == TokenType.GREATER_EQUAL:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return BoolValue(left_val.value >= right_val.value)
else:
raise TypeError('Comparison requires numbers')
else:
raise RuntimeError(f'Unknown operator: {node.operator}')
def evaluate_function_call(self, node, env):
"""Evaluate function application."""
func_val = self.evaluate(node.function, env)
if not isinstance(func_val, FunctionValue):
raise TypeError(f'Cannot call non-function value: {func_val}')
arg_vals = [self.evaluate(arg, env) for arg in node.arguments]
# Handle currying: if we have fewer arguments than parameters,
# return a new function that expects the remaining arguments
if len(arg_vals) < len(func_val.parameters):
bound_params = func_val.parameters[:len(arg_vals)]
remaining_params = func_val.parameters[len(arg_vals):]
new_env = func_val.closure.extend(bound_params, arg_vals)
return FunctionValue(remaining_params, func_val.body, new_env)
# If we have exactly the right number of arguments, evaluate the body
elif len(arg_vals) == len(func_val.parameters):
new_env = func_val.closure.extend(func_val.parameters, arg_vals)
return self.evaluate(func_val.body, new_env)
# If we have too many arguments, apply the function and then
# apply the result to the remaining arguments
else:
first_args = arg_vals[:len(func_val.parameters)]
remaining_args = arg_vals[len(func_val.parameters):]
new_env = func_val.closure.extend(func_val.parameters, first_args)
result = self.evaluate(func_val.body, new_env)
for arg in remaining_args:
if not isinstance(result, FunctionValue):
raise TypeError('Too many arguments to function')
new_env = result.closure.extend(result.parameters, [arg])
result = self.evaluate(result.body, new_env)
return result
def evaluate_if_expression(self, node, env):
"""Evaluate conditional expressions."""
condition_val = self.evaluate(node.condition, env)
if not isinstance(condition_val, BoolValue):
raise TypeError('Condition must be a boolean')
if condition_val.value:
return self.evaluate(node.then_branch, env)
else:
return self.evaluate(node.else_branch, env)
def evaluate_let_binding(self, node, env):
"""Evaluate let bindings."""
value = self.evaluate(node.value, env)
new_env = env.define(node.name, value)
return self.evaluate(node.body, new_env)
def evaluate_list_literal(self, node, env):
"""Evaluate list literals."""
element_vals = [self.evaluate(elem, env) for elem in node.elements]
return ListValue(element_vals)
def evaluate_match_expression(self, node, env):
"""Evaluate match expressions."""
value = self.evaluate(node.value, env)
for case in node.cases:
match_env = self.try_match_pattern(case.pattern, value, env)
if match_env is not None:
return self.evaluate(case.result, match_env)
raise RuntimeError('No matching pattern found')
def try_match_pattern(self, pattern, value, env):
"""Try to match a pattern against a value, returning a new environment if successful."""
if isinstance(pattern, EmptyListPattern):
if isinstance(value, ListValue) and len(value.elements) == 0:
return env
else:
return None
elif isinstance(pattern, VariablePattern):
return env.define(pattern.name, value)
elif isinstance(pattern, ConsPattern):
if isinstance(value, ListValue) and len(value.elements) > 0:
head = value.elements[0]
tail = ListValue(value.elements[1:])
env = self.try_match_pattern(pattern.head, head, env)
if env is None:
return None
env = self.try_match_pattern(pattern.tail, tail, env)
return env
else:
return None
else:
raise RuntimeError(f'Unknown pattern type: {type(pattern)}')
This evaluator handles all the core features of PureFunc. It correctly implements closures by capturing the environment when a function is created. It supports currying by allowing partial application of functions. Pattern matching is implemented by trying each case in order until one matches.
ADDING BUILT-IN FUNCTIONS
To make PureFunc practical, we need to provide some built-in functions. These are functions implemented in the host language (Python) that are available in the global environment.
We extend the create_global_environment method to add built-in functions:
def create_global_environment(self):
"""Create the global environment with built-in functions."""
env = Environment()
# print function
def builtin_print(arg):
print(self.value_to_string(arg))
return arg
env.bindings['print'] = self.create_builtin_function('print', 1, builtin_print)
# head function (get first element of list)
def builtin_head(lst):
if not isinstance(lst, ListValue):
raise TypeError('head requires a list')
if len(lst.elements) == 0:
raise RuntimeError('head of empty list')
return lst.elements[0]
env.bindings['head'] = self.create_builtin_function('head', 1, builtin_head)
# tail function (get all but first element)
def builtin_tail(lst):
if not isinstance(lst, ListValue):
raise TypeError('tail requires a list')
if len(lst.elements) == 0:
raise RuntimeError('tail of empty list')
return ListValue(lst.elements[1:])
env.bindings['tail'] = self.create_builtin_function('tail', 1, builtin_tail)
# cons function (prepend element to list)
def builtin_cons(elem, lst):
if not isinstance(lst, ListValue):
raise TypeError('cons requires a list as second argument')
return ListValue([elem] + list(lst.elements))
env.bindings['cons'] = self.create_builtin_function('cons', 2, builtin_cons)
# length function
def builtin_length(lst):
if not isinstance(lst, ListValue):
raise TypeError('length requires a list')
return NumberValue(len(lst.elements))
env.bindings['length'] = self.create_builtin_function('length', 1, builtin_length)
# isEmpty function
def builtin_is_empty(lst):
if not isinstance(lst, ListValue):
raise TypeError('isEmpty requires a list')
return BoolValue(len(lst.elements) == 0)
env.bindings['isEmpty'] = self.create_builtin_function('isEmpty', 1, builtin_is_empty)
return env
def create_builtin_function(self, name, arity, implementation):
"""Create a built-in function value."""
class BuiltinFunction(FunctionValue):
def __init__(self, name, arity, impl):
self.name = name
self.arity = arity
self.implementation = impl
self.parameters = [f'arg{i}' for i in range(arity)]
self.body = None
self.closure = None
def __repr__(self):
return f'BuiltinFunction({self.name})'
return BuiltinFunction(name, arity, implementation)
def evaluate_function_call(self, node, env):
"""Evaluate function application (updated to handle built-ins)."""
func_val = self.evaluate(node.function, env)
if not isinstance(func_val, FunctionValue):
raise TypeError(f'Cannot call non-function value: {func_val}')
arg_vals = [self.evaluate(arg, env) for arg in node.arguments]
# Handle built-in functions
if hasattr(func_val, 'implementation') and func_val.implementation is not None:
if len(arg_vals) < func_val.arity:
# Partial application of built-in
bound_args = arg_vals
remaining_arity = func_val.arity - len(arg_vals)
def partial_impl(*args):
all_args = bound_args + list(args)
return func_val.implementation(*all_args)
return self.create_builtin_function(
f'{func_val.name}_partial',
remaining_arity,
partial_impl
)
elif len(arg_vals) == func_val.arity:
return func_val.implementation(*arg_vals)
else:
# Too many arguments
result = func_val.implementation(*arg_vals[:func_val.arity])
remaining_args = arg_vals[func_val.arity:]
for arg in remaining_args:
if not isinstance(result, FunctionValue):
raise TypeError('Too many arguments to function')
# Recursively apply
result = self.evaluate_function_call(
FunctionCall(Variable('_temp'), [Variable('_arg')]),
env.define('_temp', result).define('_arg', arg)
)
return result
# Handle user-defined functions (same as before)
if len(arg_vals) < len(func_val.parameters):
bound_params = func_val.parameters[:len(arg_vals)]
remaining_params = func_val.parameters[len(arg_vals):]
new_env = func_val.closure.extend(bound_params, arg_vals)
return FunctionValue(remaining_params, func_val.body, new_env)
elif len(arg_vals) == len(func_val.parameters):
new_env = func_val.closure.extend(func_val.parameters, arg_vals)
return self.evaluate(func_val.body, new_env)
else:
first_args = arg_vals[:len(func_val.parameters)]
remaining_args = arg_vals[len(func_val.parameters):]
new_env = func_val.closure.extend(func_val.parameters, first_args)
result = self.evaluate(func_val.body, new_env)
for arg in remaining_args:
if not isinstance(result, FunctionValue):
raise TypeError('Too many arguments to function')
new_env = result.closure.extend(result.parameters, [arg])
result = self.evaluate(result.body, new_env)
return result
def value_to_string(self, value):
"""Convert a value to a string for printing."""
if isinstance(value, NumberValue):
return str(value.value)
elif isinstance(value, BoolValue):
return 'true' if value.value else 'false'
elif isinstance(value, ListValue):
elements = [self.value_to_string(elem) for elem in value.elements]
return '[' + ', '.join(elements) + ']'
elif isinstance(value, FunctionValue):
return '<function>'
else:
return str(value)
These built-in functions provide essential list operations that students will use frequently. They are implemented efficiently in Python but appear as normal functions in PureFunc.
CREATING A REPL
A Read-Eval-Print Loop (REPL) allows interactive exploration of the language. Users can type expressions and immediately see the results. This is invaluable for learning and experimentation.
The REPL repeatedly reads input, evaluates it, and prints the result:
class REPL:
def __init__(self):
self.evaluator = Evaluator()
self.environment = self.evaluator.global_env
def run(self):
"""Run the interactive REPL."""
print('PureFunc REPL v1.0')
print('Type expressions to evaluate them. Use Ctrl+C to exit.')
print()
while True:
try:
# Read
source = input('> ')
if not source.strip():
continue
# Lex
lexer = Lexer(source)
tokens = lexer.tokenize()
# Parse
parser = Parser(tokens)
ast = parser.parse()
# Evaluate
result = self.evaluator.evaluate(ast, self.environment)
print(self.evaluator.value_to_string(result))
print()
except KeyboardInterrupt:
print('\nGoodbye!')
break
except EOFError:
print('\nGoodbye!')
break
except Exception as e:
print(f'Error: {e}')
print()
def run_file(self, filename):
"""Execute a PureFunc source file."""
try:
with open(filename, 'r') as f:
source = f.read()
lexer = Lexer(source)
tokens = lexer.tokenize()
parser = Parser(tokens)
ast = parser.parse()
result = self.evaluator.evaluate(ast, self.environment)
print(self.evaluator.value_to_string(result))
except FileNotFoundError:
print(f'Error: File not found: {filename}')
except Exception as e:
print(f'Error: {e}')
The REPL provides a friendly interface for experimenting with PureFunc. It catches errors gracefully and allows the user to continue working after mistakes.
EXAMPLE PROGRAMS IN PUREFUNC
Let us explore some example programs to demonstrate the capabilities of PureFunc. These examples illustrate functional programming concepts that students will learn.
Computing the factorial of a number using recursion:
let factorial = fn n ->
if n == 0
then 1
else n * factorial (n - 1)
in
factorial 5
This defines a recursive function that computes factorial. The function calls itself with a smaller argument until reaching the base case.
Mapping a function over a list:
let map = fn f list ->
match list with
[] -> []
[head | tail] -> cons (f head) (map f tail)
in
let double = fn x -> x * 2 in
map double [1, 2, 3, 4, 5]
The map function applies a function to each element of a list, producing a new list. This demonstrates higher-order functions and pattern matching.
Filtering a list based on a predicate:
let filter = fn pred list ->
match list with
[] -> []
[head | tail] ->
if pred head
then cons head (filter pred tail)
else filter pred tail
in
let isPositive = fn x -> x > 0 in
filter isPositive [-2, -1, 0, 1, 2]
The filter function keeps only elements that satisfy a predicate. This shows how functions can be passed as arguments.
Folding a list (reduce operation):
let foldl = fn f acc list ->
match list with
[] -> acc
[head | tail] -> foldl f (f acc head) tail
in
let sum = foldl (fn a b -> a + b) 0 in
sum [1, 2, 3, 4, 5]
The foldl function processes a list from left to right, accumulating a result. This is a fundamental operation in functional programming.
Composing functions:
let compose = fn f g -> fn x -> f (g x) in
let add1 = fn x -> x + 1 in
let double = fn x -> x * 2 in
let add1ThenDouble = compose double add1 in
add1ThenDouble 5
Function composition creates a new function by chaining two functions together. The result of the second function becomes the input to the first.
Computing Fibonacci numbers:
let fib = fn n ->
if n <= 1
then n
else fib (n - 1) + fib (n - 2)
in
fib 10
This classic recursive function demonstrates how PureFunc handles multiple recursive calls.
Finding the length of a list using pattern matching:
let length = fn list ->
match list with
[] -> 0
[head | tail] -> 1 + length tail
in
length [1, 2, 3, 4, 5]
This shows how pattern matching naturally expresses recursive operations on lists.
ADVANCED FEATURES AND OPTIMIZATIONS
While our implementation is complete and functional, there are several advanced features and optimizations that could be added to make PureFunc more powerful and efficient.
Tail call optimization is crucial for functional languages that rely heavily on recursion. Without it, deep recursion can cause stack overflow. We could modify the evaluator to recognize tail calls and convert them to loops.
Lazy evaluation allows expressions to be evaluated only when their values are needed. This enables infinite data structures and can improve performance by avoiding unnecessary computation. We would need to wrap expressions in thunks that delay evaluation.
Type inference using the Hindley-Milner algorithm would allow PureFunc to catch type errors before runtime while still maintaining a clean syntax without explicit type annotations. This requires implementing unification and constraint solving.
Algebraic data types would allow users to define their own data structures with pattern matching. For example, defining a binary tree type and writing functions that operate on trees.
Module system would allow organizing code into separate files and namespaces. This is essential for larger programs and code reuse.
Garbage collection is already handled by Python's runtime, but if we were implementing PureFunc in a lower-level language, we would need to implement reference counting or tracing garbage collection.
Compilation to bytecode or native code would significantly improve performance. Instead of walking the AST, we could compile to an intermediate representation that is faster to execute.
TEACHING FUNCTIONAL PROGRAMMING WITH PUREFUNC
PureFunc is designed specifically for teaching functional programming concepts. The language's simplicity and purity make it ideal for students learning these ideas for the first time.
Immutability is enforced throughout the language. All values are immutable, which eliminates entire classes of bugs related to shared mutable state. Students learn to think in terms of transformations rather than mutations.
First-class functions mean that functions can be passed as arguments, returned from other functions, and stored in data structures. This is fundamental to functional programming and enables powerful abstractions.
Pattern matching provides a clear and concise way to work with data structures. Students learn to think about data in terms of its shape and structure rather than imperative operations.
Recursion is the primary looping mechanism in PureFunc. Students learn to solve problems recursively, which often leads to more elegant solutions than iterative approaches.
Higher-order functions like map, filter, and fold are essential tools in functional programming. Students learn to compose these building blocks to solve complex problems.
Closures capture variables from their surrounding scope, enabling powerful programming techniques like currying and partial application.
The REPL provides immediate feedback, allowing students to experiment and learn interactively. They can try small examples and see the results immediately.
COMPLETE RUNNING EXAMPLE
Below is the complete, production-ready implementation of PureFunc with all components integrated. This code can be run directly and includes all the features discussed in this tutorial.
#!/usr/bin/env python3
"""
PureFunc: A Minimal Functional Programming Language
This is a complete implementation of a functional programming language
designed for teaching functional programming concepts. All data types
are immutable, and the language supports first-class functions,
pattern matching, recursion, and higher-order functions.
"""
import sys
from typing import List, Optional, Any, Dict, Tuple
# ============================================================================
# TOKEN DEFINITIONS
# ============================================================================
class TokenType:
"""Enumeration of all token types in PureFunc."""
# Keywords
LET = 'LET'
IN = 'IN'
FN = 'FN'
IF = 'IF'
THEN = 'THEN'
ELSE = 'ELSE'
MATCH = 'MATCH'
WITH = 'WITH'
TRUE = 'TRUE'
FALSE = 'FALSE'
# Literals
NUMBER = 'NUMBER'
IDENTIFIER = 'IDENTIFIER'
# Operators
PLUS = 'PLUS'
MINUS = 'MINUS'
MULTIPLY = 'MULTIPLY'
DIVIDE = 'DIVIDE'
MODULO = 'MODULO'
EQUALS = 'EQUALS'
NOT_EQUALS = 'NOT_EQUALS'
LESS_THAN = 'LESS_THAN'
GREATER_THAN = 'GREATER_THAN'
LESS_EQUAL = 'LESS_EQUAL'
GREATER_EQUAL = 'GREATER_EQUAL'
AND = 'AND'
OR = 'OR'
NOT = 'NOT'
# Punctuation
LPAREN = 'LPAREN'
RPAREN = 'RPAREN'
LBRACKET = 'LBRACKET'
RBRACKET = 'RBRACKET'
ARROW = 'ARROW'
PIPE = 'PIPE'
COMMA = 'COMMA'
ASSIGN = 'ASSIGN'
# Special
EOF = 'EOF'
class Token:
"""Represents a single token in the source code."""
def __init__(self, token_type: str, value: Any, line: int, column: int):
self.type = token_type
self.value = value
self.line = line
self.column = column
def __repr__(self):
return f'Token({self.type}, {self.value}, {self.line}:{self.column})'
# ============================================================================
# LEXER
# ============================================================================
class Lexer:
"""
Lexical analyzer for PureFunc.
Converts source code into a stream of tokens.
"""
def __init__(self, source: str):
self.source = source
self.position = 0
self.line = 1
self.column = 1
self.current_char = self.source[0] if source else None
self.keywords = {
'let': TokenType.LET,
'in': TokenType.IN,
'fn': TokenType.FN,
'if': TokenType.IF,
'then': TokenType.THEN,
'else': TokenType.ELSE,
'match': TokenType.MATCH,
'with': TokenType.WITH,
'true': TokenType.TRUE,
'false': TokenType.FALSE,
'and': TokenType.AND,
'or': TokenType.OR,
'not': TokenType.NOT,
'mod': TokenType.MODULO,
}
def error(self, message: str):
"""Raise a lexer error with position information."""
raise SyntaxError(f'{message} at line {self.line}, column {self.column}')
def advance(self):
"""Move to the next character in the source."""
if self.current_char == '\n':
self.line += 1
self.column = 1
else:
self.column += 1
self.position += 1
if self.position >= len(self.source):
self.current_char = None
else:
self.current_char = self.source[self.position]
def peek(self, offset: int = 1) -> Optional[str]:
"""Look ahead at the next character without consuming it."""
peek_pos = self.position + offset
if peek_pos >= len(self.source):
return None
return self.source[peek_pos]
def skip_whitespace(self):
"""Skip over whitespace characters."""
while self.current_char is not None and self.current_char.isspace():
self.advance()
def skip_comment(self):
"""Skip over comments that start with #."""
while self.current_char is not None and self.current_char != '\n':
self.advance()
def read_number(self) -> Token:
"""Read a numeric literal (integer or float)."""
start_line = self.line
start_column = self.column
num_str = ''
has_decimal = False
while self.current_char is not None and (self.current_char.isdigit() or self.current_char == '.'):
if self.current_char == '.':
if has_decimal:
self.error('Invalid number: multiple decimal points')
has_decimal = True
num_str += self.current_char
self.advance()
if has_decimal:
return Token(TokenType.NUMBER, float(num_str), start_line, start_column)
else:
return Token(TokenType.NUMBER, int(num_str), start_line, start_column)
def read_identifier(self) -> Token:
"""Read an identifier or keyword."""
start_line = self.line
start_column = self.column
id_str = ''
while self.current_char is not None and (self.current_char.isalnum() or self.current_char == '_'):
id_str += self.current_char
self.advance()
token_type = self.keywords.get(id_str, TokenType.IDENTIFIER)
return Token(token_type, id_str, start_line, start_column)
def get_next_token(self) -> Token:
"""Get the next token from the source."""
while self.current_char is not None:
if self.current_char.isspace():
self.skip_whitespace()
continue
if self.current_char == '#':
self.skip_comment()
continue
if self.current_char.isdigit():
return self.read_number()
if self.current_char.isalpha() or self.current_char == '_':
return self.read_identifier()
# Single and multi-character operators
line = self.line
column = self.column
if self.current_char == '+':
self.advance()
return Token(TokenType.PLUS, '+', line, column)
if self.current_char == '*':
self.advance()
return Token(TokenType.MULTIPLY, '*', line, column)
if self.current_char == '/':
self.advance()
return Token(TokenType.DIVIDE, '/', line, column)
if self.current_char == '(':
self.advance()
return Token(TokenType.LPAREN, '(', line, column)
if self.current_char == ')':
self.advance()
return Token(TokenType.RPAREN, ')', line, column)
if self.current_char == '[':
self.advance()
return Token(TokenType.LBRACKET, '[', line, column)
if self.current_char == ']':
self.advance()
return Token(TokenType.RBRACKET, ']', line, column)
if self.current_char == ',':
self.advance()
return Token(TokenType.COMMA, ',', line, column)
if self.current_char == '|':
self.advance()
return Token(TokenType.PIPE, '|', line, column)
if self.current_char == '-':
if self.peek() == '>':
self.advance()
self.advance()
return Token(TokenType.ARROW, '->', line, column)
else:
self.advance()
return Token(TokenType.MINUS, '-', line, column)
if self.current_char == '=':
if self.peek() == '=':
self.advance()
self.advance()
return Token(TokenType.EQUALS, '==', line, column)
else:
self.advance()
return Token(TokenType.ASSIGN, '=', line, column)
if self.current_char == '!':
if self.peek() == '=':
self.advance()
self.advance()
return Token(TokenType.NOT_EQUALS, '!=', line, column)
else:
self.error(f'Unexpected character: {self.current_char}')
if self.current_char == '<':
if self.peek() == '=':
self.advance()
self.advance()
return Token(TokenType.LESS_EQUAL, '<=', line, column)
else:
self.advance()
return Token(TokenType.LESS_THAN, '<', line, column)
if self.current_char == '>':
if self.peek() == '=':
self.advance()
self.advance()
return Token(TokenType.GREATER_EQUAL, '>=', line, column)
else:
self.advance()
return Token(TokenType.GREATER_THAN, '>', line, column)
self.error(f'Unexpected character: {self.current_char}')
return Token(TokenType.EOF, None, self.line, self.column)
def tokenize(self) -> List[Token]:
"""Tokenize the entire source and return a list of tokens."""
tokens = []
while True:
token = self.get_next_token()
tokens.append(token)
if token.type == TokenType.EOF:
break
return tokens
# ============================================================================
# ABSTRACT SYNTAX TREE NODES
# ============================================================================
class ASTNode:
"""Base class for all AST nodes."""
pass
class NumberLiteral(ASTNode):
"""Represents a numeric literal."""
def __init__(self, value: float):
self.value = value
def __repr__(self):
return f'NumberLiteral({self.value})'
class BoolLiteral(ASTNode):
"""Represents a boolean literal."""
def __init__(self, value: bool):
self.value = value
def __repr__(self):
return f'BoolLiteral({self.value})'
class Variable(ASTNode):
"""Represents a variable reference."""
def __init__(self, name: str):
self.name = name
def __repr__(self):
return f'Variable({self.name})'
class BinaryOp(ASTNode):
"""Represents a binary operation."""
def __init__(self, left: ASTNode, operator: str, right: ASTNode):
self.left = left
self.operator = operator
self.right = right
def __repr__(self):
return f'BinaryOp({self.left}, {self.operator}, {self.right})'
class UnaryOp(ASTNode):
"""Represents a unary operation."""
def __init__(self, operator: str, operand: ASTNode):
self.operator = operator
self.operand = operand
def __repr__(self):
return f'UnaryOp({self.operator}, {self.operand})'
class FunctionDef(ASTNode):
"""Represents a function definition."""
def __init__(self, parameters: List[str], body: ASTNode):
self.parameters = parameters
self.body = body
def __repr__(self):
return f'FunctionDef({self.parameters}, {self.body})'
class FunctionCall(ASTNode):
"""Represents a function call."""
def __init__(self, function: ASTNode, arguments: List[ASTNode]):
self.function = function
self.arguments = arguments
def __repr__(self):
return f'FunctionCall({self.function}, {self.arguments})'
class IfExpression(ASTNode):
"""Represents a conditional expression."""
def __init__(self, condition: ASTNode, then_branch: ASTNode, else_branch: ASTNode):
self.condition = condition
self.then_branch = then_branch
self.else_branch = else_branch
def __repr__(self):
return f'IfExpression({self.condition}, {self.then_branch}, {self.else_branch})'
class LetBinding(ASTNode):
"""Represents a let binding."""
def __init__(self, name: str, value: ASTNode, body: ASTNode):
self.name = name
self.value = value
self.body = body
def __repr__(self):
return f'LetBinding({self.name}, {self.value}, {self.body})'
class ListLiteral(ASTNode):
"""Represents a list literal."""
def __init__(self, elements: List[ASTNode]):
self.elements = elements
def __repr__(self):
return f'ListLiteral({self.elements})'
class MatchExpression(ASTNode):
"""Represents a pattern match expression."""
def __init__(self, value: ASTNode, cases: List['MatchCase']):
self.value = value
self.cases = cases
def __repr__(self):
return f'MatchExpression({self.value}, {self.cases})'
class MatchCase(ASTNode):
"""Represents a single case in a match expression."""
def __init__(self, pattern: 'Pattern', result: ASTNode):
self.pattern = pattern
self.result = result
def __repr__(self):
return f'MatchCase({self.pattern}, {self.result})'
# Pattern types
class Pattern(ASTNode):
"""Base class for patterns."""
pass
class EmptyListPattern(Pattern):
"""Matches an empty list."""
def __repr__(self):
return 'EmptyListPattern()'
class VariablePattern(Pattern):
"""Matches any value and binds it to a variable."""
def __init__(self, name: str):
self.name = name
def __repr__(self):
return f'VariablePattern({self.name})'
class ConsPattern(Pattern):
"""Matches a non-empty list, binding head and tail."""
def __init__(self, head: Pattern, tail: Pattern):
self.head = head
self.tail = tail
def __repr__(self):
return f'ConsPattern({self.head}, {self.tail})'
class LiteralPattern(Pattern):
"""Matches a specific literal value."""
def __init__(self, value: Any):
self.value = value
def __repr__(self):
return f'LiteralPattern({self.value})'
# ============================================================================
# PARSER
# ============================================================================
class Parser:
"""
Recursive descent parser for PureFunc.
Converts a stream of tokens into an Abstract Syntax Tree.
"""
def __init__(self, tokens: List[Token]):
self.tokens = tokens
self.position = 0
self.current_token = self.tokens[0] if tokens else None
def error(self, message: str):
"""Raise a parser error with position information."""
if self.current_token:
raise SyntaxError(f'{message} at line {self.current_token.line}, column {self.current_token.column}')
else:
raise SyntaxError(f'{message} at end of input')
def advance(self):
"""Move to the next token."""
self.position += 1
if self.position < len(self.tokens):
self.current_token = self.tokens[self.position]
else:
self.current_token = None
def expect(self, token_type: str) -> Token:
"""Consume a token of the expected type or raise an error."""
if self.current_token is None:
self.error(f'Expected {token_type} but reached end of input')
if self.current_token.type != token_type:
self.error(f'Expected {token_type} but got {self.current_token.type}')
token = self.current_token
self.advance()
return token
def parse(self) -> ASTNode:
"""Parse the entire program."""
result = self.parse_expression()
if self.current_token.type != TokenType.EOF:
self.error('Unexpected tokens after expression')
return result
def parse_expression(self) -> ASTNode:
"""Parse an expression (the top-level grammar rule)."""
if self.current_token.type == TokenType.LET:
return self.parse_let_binding()
elif self.current_token.type == TokenType.FN:
return self.parse_function_def()
elif self.current_token.type == TokenType.IF:
return self.parse_if_expression()
elif self.current_token.type == TokenType.MATCH:
return self.parse_match_expression()
else:
return self.parse_logical_or()
def parse_let_binding(self) -> LetBinding:
"""Parse a let binding: let x = value in body"""
self.expect(TokenType.LET)
name_token = self.expect(TokenType.IDENTIFIER)
self.expect(TokenType.ASSIGN)
value = self.parse_expression()
self.expect(TokenType.IN)
body = self.parse_expression()
return LetBinding(name_token.value, value, body)
def parse_function_def(self) -> FunctionDef:
"""Parse a function definition: fn x y -> body"""
self.expect(TokenType.FN)
parameters = []
while self.current_token and self.current_token.type == TokenType.IDENTIFIER:
param_token = self.expect(TokenType.IDENTIFIER)
parameters.append(param_token.value)
if not parameters:
self.error('Function must have at least one parameter')
self.expect(TokenType.ARROW)
body = self.parse_expression()
return FunctionDef(parameters, body)
def parse_if_expression(self) -> IfExpression:
"""Parse an if expression: if cond then expr1 else expr2"""
self.expect(TokenType.IF)
condition = self.parse_expression()
self.expect(TokenType.THEN)
then_branch = self.parse_expression()
self.expect(TokenType.ELSE)
else_branch = self.parse_expression()
return IfExpression(condition, then_branch, else_branch)
def parse_match_expression(self) -> MatchExpression:
"""Parse a match expression: match value with cases"""
self.expect(TokenType.MATCH)
value = self.parse_expression()
self.expect(TokenType.WITH)
cases = []
# Parse at least one case
pattern = self.parse_pattern()
self.expect(TokenType.ARROW)
result = self.parse_expression()
cases.append(MatchCase(pattern, result))
# Parse additional cases (optional)
while self.current_token and self.current_token.type in [TokenType.LBRACKET, TokenType.IDENTIFIER, TokenType.NUMBER, TokenType.TRUE, TokenType.FALSE]:
# Check if this looks like a pattern
if self.current_token.type == TokenType.PIPE:
break
if self.current_token.type in [TokenType.IN, TokenType.THEN, TokenType.ELSE, TokenType.COMMA, TokenType.RPAREN, TokenType.RBRACKET]:
break
pattern = self.parse_pattern()
self.expect(TokenType.ARROW)
result = self.parse_expression()
cases.append(MatchCase(pattern, result))
return MatchExpression(value, cases)
def parse_pattern(self) -> Pattern:
"""Parse a pattern for match expressions."""
if self.current_token.type == TokenType.LBRACKET:
self.advance()
if self.current_token.type == TokenType.RBRACKET:
self.advance()
return EmptyListPattern()
else:
# List pattern: [head | tail]
head_token = self.expect(TokenType.IDENTIFIER)
head = VariablePattern(head_token.value)
self.expect(TokenType.PIPE)
tail_token = self.expect(TokenType.IDENTIFIER)
tail = VariablePattern(tail_token.value)
self.expect(TokenType.RBRACKET)
return ConsPattern(head, tail)
elif self.current_token.type == TokenType.IDENTIFIER:
name_token = self.expect(TokenType.IDENTIFIER)
return VariablePattern(name_token.value)
elif self.current_token.type == TokenType.NUMBER:
value = self.current_token.value
self.advance()
return LiteralPattern(value)
elif self.current_token.type in [TokenType.TRUE, TokenType.FALSE]:
value = self.current_token.type == TokenType.TRUE
self.advance()
return LiteralPattern(value)
else:
self.error(f'Invalid pattern: {self.current_token.type}')
def parse_logical_or(self) -> ASTNode:
"""Parse logical OR operations."""
left = self.parse_logical_and()
while self.current_token and self.current_token.type == TokenType.OR:
operator = self.current_token.type
self.advance()
right = self.parse_logical_and()
left = BinaryOp(left, operator, right)
return left
def parse_logical_and(self) -> ASTNode:
"""Parse logical AND operations."""
left = self.parse_comparison()
while self.current_token and self.current_token.type == TokenType.AND:
operator = self.current_token.type
self.advance()
right = self.parse_comparison()
left = BinaryOp(left, operator, right)
return left
def parse_comparison(self) -> ASTNode:
"""Parse comparison operations."""
left = self.parse_additive()
while self.current_token and self.current_token.type in [
TokenType.EQUALS, TokenType.NOT_EQUALS,
TokenType.LESS_THAN, TokenType.GREATER_THAN,
TokenType.LESS_EQUAL, TokenType.GREATER_EQUAL
]:
operator = self.current_token.type
self.advance()
right = self.parse_additive()
left = BinaryOp(left, operator, right)
return left
def parse_additive(self) -> ASTNode:
"""Parse addition and subtraction."""
left = self.parse_multiplicative()
while self.current_token and self.current_token.type in [TokenType.PLUS, TokenType.MINUS]:
operator = self.current_token.type
self.advance()
right = self.parse_multiplicative()
left = BinaryOp(left, operator, right)
return left
def parse_multiplicative(self) -> ASTNode:
"""Parse multiplication, division, and modulo."""
left = self.parse_unary()
while self.current_token and self.current_token.type in [TokenType.MULTIPLY, TokenType.DIVIDE, TokenType.MODULO]:
operator = self.current_token.type
self.advance()
right = self.parse_unary()
left = BinaryOp(left, operator, right)
return left
def parse_unary(self) -> ASTNode:
"""Parse unary operations."""
if self.current_token and self.current_token.type in [TokenType.MINUS, TokenType.NOT]:
operator = self.current_token.type
self.advance()
operand = self.parse_unary()
return UnaryOp(operator, operand)
return self.parse_application()
def parse_application(self) -> ASTNode:
"""Parse function application."""
left = self.parse_primary()
while self.current_token and self.current_token.type in [
TokenType.NUMBER, TokenType.IDENTIFIER, TokenType.LPAREN,
TokenType.LBRACKET, TokenType.TRUE, TokenType.FALSE
]:
# Make sure we're not starting a new expression
if self.current_token.type in [TokenType.IN, TokenType.THEN, TokenType.ELSE, TokenType.WITH]:
break
argument = self.parse_primary()
left = FunctionCall(left, [argument])
return left
def parse_primary(self) -> ASTNode:
"""Parse primary expressions (literals, variables, parenthesized expressions, lists)."""
if self.current_token.type == TokenType.NUMBER:
value = self.current_token.value
self.advance()
return NumberLiteral(value)
elif self.current_token.type == TokenType.TRUE:
self.advance()
return BoolLiteral(True)
elif self.current_token.type == TokenType.FALSE:
self.advance()
return BoolLiteral(False)
elif self.current_token.type == TokenType.IDENTIFIER:
name = self.current_token.value
self.advance()
return Variable(name)
elif self.current_token.type == TokenType.LPAREN:
self.advance()
expr = self.parse_expression()
self.expect(TokenType.RPAREN)
return expr
elif self.current_token.type == TokenType.LBRACKET:
return self.parse_list()
else:
self.error(f'Unexpected token: {self.current_token.type}')
def parse_list(self) -> ListLiteral:
"""Parse a list literal."""
self.expect(TokenType.LBRACKET)
elements = []
if self.current_token.type == TokenType.RBRACKET:
self.advance()
return ListLiteral(elements)
elements.append(self.parse_expression())
while self.current_token.type == TokenType.COMMA:
self.advance()
elements.append(self.parse_expression())
self.expect(TokenType.RBRACKET)
return ListLiteral(elements)
# ============================================================================
# RUNTIME VALUES
# ============================================================================
class Value:
"""Base class for runtime values."""
pass
class NumberValue(Value):
"""Represents a numeric value at runtime."""
def __init__(self, value: float):
self.value = value
def __repr__(self):
return f'NumberValue({self.value})'
def __eq__(self, other):
return isinstance(other, NumberValue) and self.value == other.value
def __hash__(self):
return hash(self.value)
class BoolValue(Value):
"""Represents a boolean value at runtime."""
def __init__(self, value: bool):
self.value = value
def __repr__(self):
return f'BoolValue({self.value})'
def __eq__(self, other):
return isinstance(other, BoolValue) and self.value == other.value
def __hash__(self):
return hash(self.value)
class ListValue(Value):
"""Represents an immutable list at runtime."""
def __init__(self, elements: List[Value]):
self.elements = tuple(elements) # Immutable tuple
def __repr__(self):
return f'ListValue({list(self.elements)})'
def __eq__(self, other):
return isinstance(other, ListValue) and self.elements == other.elements
def __hash__(self):
return hash(self.elements)
class FunctionValue(Value):
"""Represents a function value at runtime."""
def __init__(self, parameters: List[str], body: ASTNode, closure: 'Environment'):
self.parameters = parameters
self.body = body
self.closure = closure
def __repr__(self):
return f'FunctionValue({self.parameters}, ...)'
# ============================================================================
# ENVIRONMENT
# ============================================================================
class Environment:
"""
Represents a lexical environment for variable bindings.
Environments are immutable and form a chain through parent pointers.
"""
def __init__(self, parent: Optional['Environment'] = None):
self.bindings: Dict[str, Value] = {}
self.parent = parent
def define(self, name: str, value: Value) -> 'Environment':
"""Create a new environment with an additional binding."""
new_env = Environment(self.parent)
new_env.bindings = self.bindings.copy()
new_env.bindings[name] = value
return new_env
def lookup(self, name: str) -> Value:
"""Look up a variable in the environment chain."""
if name in self.bindings:
return self.bindings[name]
elif self.parent is not None:
return self.parent.lookup(name)
else:
raise NameError(f'Undefined variable: {name}')
def extend(self, names: List[str], values: List[Value]) -> 'Environment':
"""Create a new environment with multiple bindings."""
new_env = Environment(self)
for name, value in zip(names, values):
new_env.bindings[name] = value
return new_env
# ============================================================================
# EVALUATOR
# ============================================================================
class Evaluator:
"""
Evaluates PureFunc AST nodes to produce runtime values.
Uses environment-based interpretation with support for closures.
"""
def __init__(self):
self.global_env = self.create_global_environment()
def create_global_environment(self) -> Environment:
"""Create the global environment with built-in functions."""
env = Environment()
# Built-in: print
def builtin_print(arg: Value) -> Value:
print(self.value_to_string(arg))
return arg
env.bindings['print'] = self.create_builtin('print', 1, builtin_print)
# Built-in: head (first element of list)
def builtin_head(lst: Value) -> Value:
if not isinstance(lst, ListValue):
raise TypeError('head requires a list')
if len(lst.elements) == 0:
raise RuntimeError('head of empty list')
return lst.elements[0]
env.bindings['head'] = self.create_builtin('head', 1, builtin_head)
# Built-in: tail (all but first element)
def builtin_tail(lst: Value) -> Value:
if not isinstance(lst, ListValue):
raise TypeError('tail requires a list')
if len(lst.elements) == 0:
raise RuntimeError('tail of empty list')
return ListValue(list(lst.elements[1:]))
env.bindings['tail'] = self.create_builtin('tail', 1, builtin_tail)
# Built-in: cons (prepend element to list)
def builtin_cons(elem: Value, lst: Value) -> Value:
if not isinstance(lst, ListValue):
raise TypeError('cons requires a list as second argument')
return ListValue([elem] + list(lst.elements))
env.bindings['cons'] = self.create_builtin('cons', 2, builtin_cons)
# Built-in: length
def builtin_length(lst: Value) -> Value:
if not isinstance(lst, ListValue):
raise TypeError('length requires a list')
return NumberValue(len(lst.elements))
env.bindings['length'] = self.create_builtin('length', 1, builtin_length)
# Built-in: isEmpty
def builtin_is_empty(lst: Value) -> Value:
if not isinstance(lst, ListValue):
raise TypeError('isEmpty requires a list')
return BoolValue(len(lst.elements) == 0)
env.bindings['isEmpty'] = self.create_builtin('isEmpty', 1, builtin_is_empty)
# Built-in: append (concatenate two lists)
def builtin_append(lst1: Value, lst2: Value) -> Value:
if not isinstance(lst1, ListValue) or not isinstance(lst2, ListValue):
raise TypeError('append requires two lists')
return ListValue(list(lst1.elements) + list(lst2.elements))
env.bindings['append'] = self.create_builtin('append', 2, builtin_append)
# Built-in: range (create list of numbers)
def builtin_range(start: Value, end: Value) -> Value:
if not isinstance(start, NumberValue) or not isinstance(end, NumberValue):
raise TypeError('range requires two numbers')
return ListValue([NumberValue(i) for i in range(int(start.value), int(end.value))])
env.bindings['range'] = self.create_builtin('range', 2, builtin_range)
return env
def create_builtin(self, name: str, arity: int, implementation) -> FunctionValue:
"""Create a built-in function value."""
class BuiltinFunction(FunctionValue):
def __init__(self, name, arity, impl):
self.name = name
self.arity = arity
self.implementation = impl
self.parameters = [f'arg{i}' for i in range(arity)]
self.body = None
self.closure = None
def __repr__(self):
return f'<builtin {self.name}>'
return BuiltinFunction(name, arity, implementation)
def evaluate(self, node: ASTNode, env: Environment) -> Value:
"""Evaluate an AST node in the given environment."""
if isinstance(node, NumberLiteral):
return NumberValue(node.value)
elif isinstance(node, BoolLiteral):
return BoolValue(node.value)
elif isinstance(node, Variable):
return env.lookup(node.name)
elif isinstance(node, BinaryOp):
return self.evaluate_binary_op(node, env)
elif isinstance(node, UnaryOp):
return self.evaluate_unary_op(node, env)
elif isinstance(node, FunctionDef):
return FunctionValue(node.parameters, node.body, env)
elif isinstance(node, FunctionCall):
return self.evaluate_function_call(node, env)
elif isinstance(node, IfExpression):
return self.evaluate_if_expression(node, env)
elif isinstance(node, LetBinding):
return self.evaluate_let_binding(node, env)
elif isinstance(node, ListLiteral):
return self.evaluate_list_literal(node, env)
elif isinstance(node, MatchExpression):
return self.evaluate_match_expression(node, env)
else:
raise RuntimeError(f'Unknown AST node type: {type(node).__name__}')
def evaluate_binary_op(self, node: BinaryOp, env: Environment) -> Value:
"""Evaluate binary operations."""
left_val = self.evaluate(node.left, env)
right_val = self.evaluate(node.right, env)
if node.operator == TokenType.PLUS:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return NumberValue(left_val.value + right_val.value)
else:
raise TypeError('Addition requires numbers')
elif node.operator == TokenType.MINUS:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return NumberValue(left_val.value - right_val.value)
else:
raise TypeError('Subtraction requires numbers')
elif node.operator == TokenType.MULTIPLY:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return NumberValue(left_val.value * right_val.value)
else:
raise TypeError('Multiplication requires numbers')
elif node.operator == TokenType.DIVIDE:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
if right_val.value == 0:
raise ZeroDivisionError('Division by zero')
return NumberValue(left_val.value / right_val.value)
else:
raise TypeError('Division requires numbers')
elif node.operator == TokenType.MODULO:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return NumberValue(left_val.value % right_val.value)
else:
raise TypeError('Modulo requires numbers')
elif node.operator == TokenType.EQUALS:
return BoolValue(left_val == right_val)
elif node.operator == TokenType.NOT_EQUALS:
return BoolValue(left_val != right_val)
elif node.operator == TokenType.LESS_THAN:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return BoolValue(left_val.value < right_val.value)
else:
raise TypeError('Comparison requires numbers')
elif node.operator == TokenType.GREATER_THAN:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return BoolValue(left_val.value > right_val.value)
else:
raise TypeError('Comparison requires numbers')
elif node.operator == TokenType.LESS_EQUAL:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return BoolValue(left_val.value <= right_val.value)
else:
raise TypeError('Comparison requires numbers')
elif node.operator == TokenType.GREATER_EQUAL:
if isinstance(left_val, NumberValue) and isinstance(right_val, NumberValue):
return BoolValue(left_val.value >= right_val.value)
else:
raise TypeError('Comparison requires numbers')
elif node.operator == TokenType.AND:
if isinstance(left_val, BoolValue) and isinstance(right_val, BoolValue):
return BoolValue(left_val.value and right_val.value)
else:
raise TypeError('Logical AND requires booleans')
elif node.operator == TokenType.OR:
if isinstance(left_val, BoolValue) and isinstance(right_val, BoolValue):
return BoolValue(left_val.value or right_val.value)
else:
raise TypeError('Logical OR requires booleans')
else:
raise RuntimeError(f'Unknown operator: {node.operator}')
def evaluate_unary_op(self, node: UnaryOp, env: Environment) -> Value:
"""Evaluate unary operations."""
operand_val = self.evaluate(node.operand, env)
if node.operator == TokenType.MINUS:
if isinstance(operand_val, NumberValue):
return NumberValue(-operand_val.value)
else:
raise TypeError('Unary minus requires a number')
elif node.operator == TokenType.NOT:
if isinstance(operand_val, BoolValue):
return BoolValue(not operand_val.value)
else:
raise TypeError('Logical NOT requires a boolean')
else:
raise RuntimeError(f'Unknown unary operator: {node.operator}')
def evaluate_function_call(self, node: FunctionCall, env: Environment) -> Value:
"""Evaluate function application with support for currying."""
func_val = self.evaluate(node.function, env)
if not isinstance(func_val, FunctionValue):
raise TypeError(f'Cannot call non-function value')
arg_vals = [self.evaluate(arg, env) for arg in node.arguments]
# Handle built-in functions
if hasattr(func_val, 'implementation') and func_val.implementation is not None:
if len(arg_vals) < func_val.arity:
# Partial application
bound_args = arg_vals
remaining_arity = func_val.arity - len(arg_vals)
def partial_impl(*args):
all_args = bound_args + list(args)
return func_val.implementation(*all_args)
return self.create_builtin(
f'{func_val.name}_partial',
remaining_arity,
partial_impl
)
elif len(arg_vals) == func_val.arity:
return func_val.implementation(*arg_vals)
else:
# Apply with exact arity, then apply result to remaining args
result = func_val.implementation(*arg_vals[:func_val.arity])
for arg in arg_vals[func_val.arity:]:
if not isinstance(result, FunctionValue):
raise TypeError('Too many arguments to function')
result = self.evaluate_function_call(
FunctionCall(Variable('_'), [Variable('_')]),
Environment().define('_', result).define('_', arg)
)
return result
# Handle user-defined functions
if len(arg_vals) < len(func_val.parameters):
# Partial application
bound_params = func_val.parameters[:len(arg_vals)]
remaining_params = func_val.parameters[len(arg_vals):]
new_env = func_val.closure.extend(bound_params, arg_vals)
return FunctionValue(remaining_params, func_val.body, new_env)
elif len(arg_vals) == len(func_val.parameters):
# Exact application
new_env = func_val.closure.extend(func_val.parameters, arg_vals)
return self.evaluate(func_val.body, new_env)
else:
# Over-application
first_args = arg_vals[:len(func_val.parameters)]
remaining_args = arg_vals[len(func_val.parameters):]
new_env = func_val.closure.extend(func_val.parameters, first_args)
result = self.evaluate(func_val.body, new_env)
for arg in remaining_args:
if not isinstance(result, FunctionValue):
raise TypeError('Too many arguments to function')
if hasattr(result, 'implementation'):
result = result.implementation(arg)
else:
new_env = result.closure.extend(result.parameters, [arg])
result = self.evaluate(result.body, new_env)
return result
def evaluate_if_expression(self, node: IfExpression, env: Environment) -> Value:
"""Evaluate conditional expressions."""
condition_val = self.evaluate(node.condition, env)
if not isinstance(condition_val, BoolValue):
raise TypeError('Condition must be a boolean')
if condition_val.value:
return self.evaluate(node.then_branch, env)
else:
return self.evaluate(node.else_branch, env)
def evaluate_let_binding(self, node: LetBinding, env: Environment) -> Value:
"""Evaluate let bindings."""
value = self.evaluate(node.value, env)
new_env = env.define(node.name, value)
return self.evaluate(node.body, new_env)
def evaluate_list_literal(self, node: ListLiteral, env: Environment) -> Value:
"""Evaluate list literals."""
element_vals = [self.evaluate(elem, env) for elem in node.elements]
return ListValue(element_vals)
def evaluate_match_expression(self, node: MatchExpression, env: Environment) -> Value:
"""Evaluate match expressions."""
value = self.evaluate(node.value, env)
for case in node.cases:
match_env = self.try_match_pattern(case.pattern, value, env)
if match_env is not None:
return self.evaluate(case.result, match_env)
raise RuntimeError('No matching pattern found')
def try_match_pattern(self, pattern: Pattern, value: Value, env: Environment) -> Optional[Environment]:
"""Try to match a pattern against a value."""
if isinstance(pattern, EmptyListPattern):
if isinstance(value, ListValue) and len(value.elements) == 0:
return env
else:
return None
elif isinstance(pattern, VariablePattern):
return env.define(pattern.name, value)
elif isinstance(pattern, ConsPattern):
if isinstance(value, ListValue) and len(value.elements) > 0:
head = value.elements[0]
tail = ListValue(list(value.elements[1:]))
env = self.try_match_pattern(pattern.head, head, env)
if env is None:
return None
env = self.try_match_pattern(pattern.tail, tail, env)
return env
else:
return None
elif isinstance(pattern, LiteralPattern):
if isinstance(value, NumberValue) and value.value == pattern.value:
return env
elif isinstance(value, BoolValue) and value.value == pattern.value:
return env
else:
return None
else:
raise RuntimeError(f'Unknown pattern type: {type(pattern).__name__}')
def value_to_string(self, value: Value) -> str:
"""Convert a value to a string for display."""
if isinstance(value, NumberValue):
if value.value == int(value.value):
return str(int(value.value))
else:
return str(value.value)
elif isinstance(value, BoolValue):
return 'true' if value.value else 'false'
elif isinstance(value, ListValue):
elements = [self.value_to_string(elem) for elem in value.elements]
return '[' + ', '.join(elements) + ']'
elif isinstance(value, FunctionValue):
if hasattr(value, 'name'):
return f'<builtin {value.name}>'
else:
return '<function>'
else:
return str(value)
# ============================================================================
# REPL
# ============================================================================
class REPL:
"""
Read-Eval-Print Loop for interactive PureFunc programming.
"""
def __init__(self):
self.evaluator = Evaluator()
self.environment = self.evaluator.global_env
def run(self):
"""Run the interactive REPL."""
print('=' * 60)
print('PureFunc REPL v1.0')
print('A minimal functional programming language')
print('=' * 60)
print('Type expressions to evaluate them.')
print('Use Ctrl+C or Ctrl+D to exit.')
print('=' * 60)
print()
while True:
try:
source = input('> ')
if not source.strip():
continue
# Special commands
if source.strip() == ':quit' or source.strip() == ':q':
print('Goodbye!')
break
if source.strip() == ':help' or source.strip() == ':h':
self.print_help()
continue
# Lex, parse, and evaluate
lexer = Lexer(source)
tokens = lexer.tokenize()
parser = Parser(tokens)
ast = parser.parse()
result = self.evaluator.evaluate(ast, self.environment)
print(self.evaluator.value_to_string(result))
print()
except KeyboardInterrupt:
print('\nGoodbye!')
break
except EOFError:
print('\nGoodbye!')
break
except Exception as e:
print(f'Error: {e}')
print()
def print_help(self):
"""Print help information."""
print()
print('PureFunc Help')
print('=' * 60)
print('Commands:')
print(' :help, :h Show this help message')
print(' :quit, :q Exit the REPL')
print()
print('Examples:')
print(' 42 Number literal')
print(' [1, 2, 3] List literal')
print(' fn x -> x + 1 Function definition')
print(' let add = fn x y -> x + y in Let binding')
print(' add 3 5')
print(' if x > 0 then x else 0 Conditional')
print(' match list with Pattern matching')
print(' [] -> 0')
print(' [h | t] -> h')
print()
print('Built-in functions:')
print(' print, head, tail, cons, length, isEmpty, append, range')
print('=' * 60)
print()
def run_file(self, filename: str):
"""Execute a PureFunc source file."""
try:
with open(filename, 'r') as f:
source = f.read()
lexer = Lexer(source)
tokens = lexer.tokenize()
parser = Parser(tokens)
ast = parser.parse()
result = self.evaluator.evaluate(ast, self.environment)
print(self.evaluator.value_to_string(result))
except FileNotFoundError:
print(f'Error: File not found: {filename}')
sys.exit(1)
except Exception as e:
print(f'Error: {e}')
sys.exit(1)
# ============================================================================
# MAIN ENTRY POINT
# ============================================================================
def main():
"""Main entry point for the PureFunc interpreter."""
if len(sys.argv) > 1:
# Run file
repl = REPL()
repl.run_file(sys.argv[1])
else:
# Interactive REPL
repl = REPL()
repl.run()
if __name__ == '__main__':
main()
CONCLUSION AND FUTURE DIRECTIONS
We have built a complete, functional programming language from scratch. PureFunc demonstrates all the essential concepts of functional programming: immutability, first-class functions, higher-order functions, pattern matching, closures, and recursion. The implementation is clean, well-documented, and suitable for teaching purposes.
Students using PureFunc will learn to think functionally. They will understand how immutability eliminates entire classes of bugs. They will see how functions can be composed to build complex behavior from simple pieces. They will appreciate the elegance of pattern matching for working with data structures. They will master recursion as a natural way to express repetitive computation.
The language is minimal but complete. It includes everything needed to write real programs while remaining simple enough to understand fully. The implementation demonstrates important computer science concepts: lexical analysis, parsing, abstract syntax trees, environments, closures, and evaluation strategies.
Future enhancements could include type inference, algebraic data types, a module system, and compilation to bytecode. However, the current implementation provides a solid foundation for learning functional programming. Students can experiment with the language, write programs, and even extend the interpreter itself as a learning exercise.
Building a programming language is one of the most rewarding projects in computer science. It combines theory and practice, requiring understanding of formal grammars, data structures, algorithms, and software engineering. This tutorial has guided you through the entire process, from tokenization to evaluation, with complete working code that you can run, modify, and extend.
EXAMPLE PROGRAMS FOR PUREFUNC
Below are comprehensive example programs demonstrating the capabilities of PureFunc. Each example includes detailed explanations and shows different aspects of functional programming.
EXAMPLE 1: FACTORIAL COMPUTATION
The factorial function is a classic example of recursion. It computes the product of all positive integers less than or equal to a given number.
let factorial = fn n ->
if n == 0
then 1
else n * factorial (n - 1)
in
factorial 5
This program defines a recursive function that computes factorial. When n equals zero, we return one as the base case. Otherwise, we multiply n by the factorial of n minus one. The result for factorial of five is one hundred twenty.
We can also write an iterative version using an accumulator:
let factorialIter = fn n ->
let helper = fn acc count ->
if count == 0
then acc
else helper (acc * count) (count - 1)
in
helper 1 n
in
factorialIter 6
This version uses tail recursion with an accumulator. The helper function multiplies the accumulator by the current count and decrements the count until it reaches zero. This approach is more efficient because it can be optimized by a compiler.
EXAMPLE 2: FIBONACCI SEQUENCE
The Fibonacci sequence is another classic recursive problem where each number is the sum of the two preceding ones.
let fib = fn n ->
if n <= 1
then n
else fib (n - 1) + fib (n - 2)
in
fib 10
This straightforward implementation computes Fibonacci numbers recursively. However, it is inefficient because it recalculates the same values multiple times. For fibonacci of ten, the result is fifty-five.
A more efficient version uses memoization through an iterative approach:
let fibIter = fn n ->
let helper = fn a b count ->
if count == 0
then a
else helper b (a + b) (count - 1)
in
helper 0 1 n
in
fibIter 15
This version maintains two accumulators representing consecutive Fibonacci numbers and iterates n times. It runs in linear time instead of exponential time.
EXAMPLE 3: LIST OPERATIONS
Lists are fundamental in functional programming. Here we demonstrate various list operations.
let map = fn f list ->
match list with
[] -> []
[head | tail] -> cons (f head) (map f tail)
in
let double = fn x -> x * 2 in
map double [1, 2, 3, 4, 5]
The map function applies a function to every element of a list. It uses pattern matching to handle the empty list base case and the recursive case where we apply the function to the head and recursively process the tail. The result is a list with each element doubled: two, four, six, eight, ten.
Here is a filter function that keeps only elements satisfying a predicate:
let filter = fn pred list ->
match list with
[] -> []
[head | tail] ->
if pred head
then cons head (filter pred tail)
else filter pred tail
in
let isEven = fn x -> x mod 2 == 0 in
filter isEven [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
The filter function examines each element. If the predicate returns true, we include the element in the result. Otherwise, we skip it. This example filters for even numbers, producing two, four, six, eight, ten.
EXAMPLE 4: FOLD OPERATIONS
Folding (also called reducing) is a fundamental operation that processes a list to produce a single value.
let foldl = fn f acc list ->
match list with
[] -> acc
[head | tail] -> foldl f (f acc head) tail
in
let sum = foldl (fn a b -> a + b) 0 in
sum [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
The foldl function processes a list from left to right, accumulating a result. We start with an initial accumulator and apply the function to the accumulator and each element. This example sums all numbers from one to ten, producing fifty-five.
We can use fold to implement many other operations:
let product = foldl (fn a b -> a * b) 1 in
let maximum = fn list ->
match list with
[] -> 0
[head | tail] -> foldl (fn a b -> if a > b then a else b) head tail
in
let concat = fn lists ->
foldl (fn a b -> append a b) [] lists
in
product [1, 2, 3, 4, 5]
This demonstrates computing the product of a list, finding the maximum element, and concatenating multiple lists.
EXAMPLE 5: HIGHER-ORDER FUNCTIONS
Higher-order functions take functions as arguments or return functions as results. They enable powerful abstractions.
let compose = fn f g -> fn x -> f (g x) in
let add1 = fn x -> x + 1 in
let double = fn x -> x * 2 in
let add1ThenDouble = compose double add1 in
add1ThenDouble 5
Function composition creates a new function by chaining two functions. The result of the second function becomes the input to the first. This example adds one to five (getting six) then doubles it (getting twelve).
Here is a more complex example with partial application:
let add = fn x y -> x + y in
let increment = add 1 in
let add10 = add 10 in
map increment [1, 2, 3, 4, 5]
Partial application allows us to create specialized functions from general ones. The increment function is created by partially applying add with one. We can then use it with map to increment every element of a list.
EXAMPLE 6: QUICKSORT
Quicksort is an elegant sorting algorithm that demonstrates recursion and list manipulation.
let quicksort = fn list ->
match list with
[] -> []
[pivot | rest] ->
let smaller = filter (fn x -> x < pivot) rest in
let larger = filter (fn x -> x >= pivot) rest in
append (append (quicksort smaller) [pivot]) (quicksort larger)
in
let filter = fn pred list ->
match list with
[] -> []
[head | tail] ->
if pred head
then cons head (filter pred tail)
else filter pred tail
in
quicksort [3, 7, 1, 9, 2, 8, 4, 6, 5]
This implementation picks the first element as the pivot, partitions the rest into smaller and larger elements, recursively sorts both partitions, and concatenates them with the pivot in the middle. The result is a sorted list: one, two, three, four, five, six, seven, eight, nine.
EXAMPLE 7: TREE OPERATIONS
Although PureFunc does not have built-in tree types, we can represent trees as nested lists and operate on them functionally.
let sumTree = fn tree ->
match tree with
[] -> 0
[value | children] ->
if isEmpty children
then value
else value + foldl (fn acc child -> acc + sumTree child) 0 children
in
let foldl = fn f acc list ->
match list with
[] -> acc
[head | tail] -> foldl f (f acc head) tail
in
sumTree [1, [[2, []], [3, [[4, []], [5, []]]]]]
This represents a tree where each node is a list containing a value and a list of children. The sumTree function recursively sums all values in the tree. This example tree has nodes with values one, two, three, four, and five, summing to fifteen.
EXAMPLE 8: PRIME NUMBERS
Computing prime numbers demonstrates filtering and mathematical operations.
let isPrime = fn n ->
let helper = fn divisor ->
if divisor * divisor > n
then true
else if n mod divisor == 0
then false
else helper (divisor + 1)
in
if n < 2
then false
else helper 2
in
let primesUpTo = fn n ->
filter isPrime (range 2 n)
in
primesUpTo 30
The isPrime function checks if a number is prime by testing divisibility up to its square root. The primesUpTo function generates all primes up to a given number by filtering the range. This produces two, three, five, seven, eleven, thirteen, seventeen, nineteen, twenty-three, and twenty-nine.
EXAMPLE 9: LIST REVERSAL
Reversing a list is a common operation that can be implemented efficiently with an accumulator.
let reverse = fn list ->
let helper = fn acc remaining ->
match remaining with
[] -> acc
[head | tail] -> helper (cons head acc) tail
in
helper [] list
in
reverse [1, 2, 3, 4, 5]
This implementation uses tail recursion with an accumulator. We process each element from the original list and prepend it to the accumulator, effectively reversing the order. The result is five, four, three, two, one.
EXAMPLE 10: FLATTEN NESTED LISTS
Flattening converts a nested list structure into a single-level list.
let flatten = fn list ->
match list with
[] -> []
[head | tail] ->
if isEmpty head
then flatten tail
else append (flatten head) (flatten tail)
in
flatten [[1, 2], [3, 4, 5], [6]]
This recursive implementation processes each element. If the element is a list, we recursively flatten it and append the results. This example flattens nested lists into one, two, three, four, five, six.
EXAMPLE 11: TAKE AND DROP
These functions extract portions of lists.
let take = fn n list ->
if n == 0
then []
else match list with
[] -> []
[head | tail] -> cons head (take (n - 1) tail)
in
let drop = fn n list ->
if n == 0
then list
else match list with
[] -> []
[head | tail] -> drop (n - 1) tail
in
take 3 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
The take function returns the first n elements of a list. The drop function removes the first n elements and returns the rest. Taking three elements from the list produces one, two, three.
EXAMPLE 12: ZIP LISTS
Zipping combines two lists into a list of pairs.
let zip = fn list1 list2 ->
match list1 with
[] -> []
[h1 | t1] ->
match list2 with
[] -> []
[h2 | t2] -> cons [h1, h2] (zip t1 t2)
in
zip [1, 2, 3] [4, 5, 6]
This function pairs corresponding elements from two lists. The result is a list of pairs: one with four, two with five, three with six, represented as nested lists.
EXAMPLE 13: ALL AND ANY
These predicates test whether all or any elements satisfy a condition.
let all = fn pred list ->
match list with
[] -> true
[head | tail] ->
if pred head
then all pred tail
else false
in
let any = fn pred list ->
match list with
[] -> false
[head | tail] ->
if pred head
then true
else any pred tail
in
let isPositive = fn x -> x > 0 in
all isPositive [1, 2, 3, 4, 5]
The all function returns true if every element satisfies the predicate. The any function returns true if at least one element satisfies the predicate. This example checks if all numbers are positive, returning true.
EXAMPLE 14: GENERATE SEQUENCES
Generating sequences demonstrates recursive list building.
let replicate = fn n value ->
if n == 0
then []
else cons value (replicate (n - 1) value)
in
let iterate = fn f initial n ->
if n == 0
then []
else cons initial (iterate f (f initial) (n - 1))
in
let powers = iterate (fn x -> x * 2) 1 10 in
powers
The replicate function creates a list with n copies of a value. The iterate function generates a sequence by repeatedly applying a function. This example generates powers of two: one, two, four, eight, sixteen, thirty-two, sixty-four, one hundred twenty-eight, two hundred fifty-six, five hundred twelve.
EXAMPLE 15: PARTITION
Partitioning splits a list into two lists based on a predicate.
let partition = fn pred list ->
let helper = fn trueList falseList remaining ->
match remaining with
[] -> [trueList, falseList]
[head | tail] ->
if pred head
then helper (append trueList [head]) falseList tail
else helper trueList (append falseList [head]) tail
in
helper [] [] list
in
let isEven = fn x -> x mod 2 == 0 in
partition isEven [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
This function returns a list containing two lists: elements satisfying the predicate and elements not satisfying it. The result separates even and odd numbers.
EXAMPLE 16: MERGE SORTED LISTS
Merging is essential for merge sort and working with sorted data.
let merge = fn list1 list2 ->
match list1 with
[] -> list2
[h1 | t1] ->
match list2 with
[] -> list1
[h2 | t2] ->
if h1 < h2
then cons h1 (merge t1 list2)
else cons h2 (merge list1 t2)
in
merge [1, 3, 5, 7] [2, 4, 6, 8]
This function merges two sorted lists into a single sorted list. It compares the heads of both lists and takes the smaller one, then recursively merges the remainder. The result is one, two, three, four, five, six, seven, eight.
EXAMPLE 17: GROUP CONSECUTIVE ELEMENTS
Grouping consecutive equal elements is useful for run-length encoding.
let group = fn list ->
match list with
[] -> []
[head | tail] ->
let takeWhile = fn pred lst ->
match lst with
[] -> []
[h | t] ->
if pred h
then cons h (takeWhile pred t)
else []
in
let dropWhile = fn pred lst ->
match lst with
[] -> []
[h | t] ->
if pred h
then dropWhile pred t
else lst
in
let sameAsHead = fn x -> x == head in
let currentGroup = cons head (takeWhile sameAsHead tail) in
let remaining = dropWhile sameAsHead tail in
cons currentGroup (group remaining)
in
group [1, 1, 2, 2, 2, 3, 1, 1, 1]
This groups consecutive equal elements into sublists. The result is nested lists: two ones, three twos, one three, three ones.
EXAMPLE 18: CARTESIAN PRODUCT
The cartesian product combines elements from two lists in all possible ways.
let cartesian = fn list1 list2 ->
let flatMap = fn f lst ->
match lst with
[] -> []
[head | tail] -> append (f head) (flatMap f tail)
in
flatMap (fn x -> map (fn y -> [x, y]) list2) list1
in
let map = fn f list ->
match list with
[] -> []
[head | tail] -> cons (f head) (map f tail)
in
cartesian [1, 2] [3, 4]
This produces all pairs combining elements from both lists: one with three, one with four, two with three, two with four.
EXAMPLE 19: PASCAL'S TRIANGLE
Pascal's triangle demonstrates recursive list generation with mathematical properties.
let pascalRow = fn n ->
let helper = fn row count ->
if count == 0
then row
else
let nextRow = fn r ->
match r with
[] -> [1]
[single] -> [1, 1]
[first | rest] ->
let pairs = zip r rest in
let sums = map (fn pair -> head pair + head (tail pair)) pairs in
cons 1 (append sums [1])
in
helper (nextRow row) (count - 1)
in
helper [1] n
in
let zip = fn list1 list2 ->
match list1 with
[] -> []
[h1 | t1] ->
match list2 with
[] -> []
[h2 | t2] -> cons [h1, h2] (zip t1 t2)
in
let map = fn f list ->
match list with
[] -> []
[head | tail] -> cons (f head) (map f tail)
in
pascalRow 5
This generates the nth row of Pascal's triangle. Each element is the sum of the two elements above it. Row five is one, five, ten, ten, five, one.
EXAMPLE 20: COMPLETE DEMONSTRATION PROGRAM
Here is a comprehensive program combining multiple concepts:
let compose = fn f g -> fn x -> f (g x) in
let map = fn f list ->
match list with
[] -> []
[head | tail] -> cons (f head) (map f tail)
in
let filter = fn pred list ->
match list with
[] -> []
[head | tail] ->
if pred head
then cons head (filter pred tail)
else filter pred tail
in
let foldl = fn f acc list ->
match list with
[] -> acc
[head | tail] -> foldl f (f acc head) tail
in
let isPrime = fn n ->
let helper = fn divisor ->
if divisor * divisor > n
then true
else if n mod divisor == 0
then false
else helper (divisor + 1)
in
if n < 2
then false
else helper 2
in
let square = fn x -> x * x in
let sum = foldl (fn a b -> a + b) 0 in
let numbers = range 1 20 in
let primes = filter isPrime numbers in
let squaredPrimes = map square primes in
sum squaredPrimes
This program finds all prime numbers from one to twenty, squares each prime, and sums the results. It demonstrates composition of multiple functional operations: filtering for primes, mapping to compute squares, and folding to sum. The result is one thousand, one hundred, and ninety-one.
These examples demonstrate the power and elegance of functional programming in PureFunc. They show how complex behavior emerges from composing simple, pure functions. Students can experiment with these examples, modify them, and create their own programs to deepen their understanding of functional programming concepts.
ADDENDUM - THE "IN" KEYWORD IN PUREFUNC
The "in" keyword is a crucial part of the "let" binding syntax in PureFunc. It separates the binding definition from the expression where that binding is used. Let me explain this in detail.
BASIC STRUCTURE OF LET BINDINGS
A let binding in PureFunc follows this pattern:
let variableName = valueExpression in bodyExpression
First, the binding part comes before "in". This is where you define what value the variable should have. The expression after the equals sign is evaluated and bound to the variable name.
Second, the body part comes after "in". This is the expression where you can actually use the variable you just defined. The variable is only available within this body expression.
WHY WE NEED THE "IN" KEYWORD
The "in" keyword is necessary because let bindings in functional languages are expressions, not statements. Unlike imperative languages where you might write:
x = 5
y = x + 3
print(y)
In PureFunc, a let binding must produce a value. The "in" keyword tells the language where to look for that value. Consider this example:
let x = 10 in x + 5
This entire construct is an expression that evaluates to fifteen. The "in" keyword separates the definition of x (which is ten) from the expression that uses x (which is x plus five).
SCOPE AND THE "IN" KEYWORD
The "in" keyword defines the scope of the variable. The variable only exists in the expression after "in". Here is an example:
let x = 5 in x * 2
In this expression, x is bound to five, and the body expression (x times two) evaluates to ten. After this entire let expression completes, x no longer exists. You cannot reference it outside this expression.
This is different from:
let x = 5 in let y = x + 3 in y * 2
Here we have nested let bindings. The first let binds x to five. Within its body (after the first "in"), we have another let binding that binds y to x plus three (which is eight). The innermost body (after the second "in") evaluates y times two, giving sixteen.
MULTIPLE BINDINGS
You can chain multiple let bindings to create a sequence of definitions:
let x = 10 in
let y = 20 in
let z = 30 in
x + y + z
Each "in" keyword introduces the scope where the previous binding is available. This reads as: let x be ten, and in that context, let y be twenty, and in that context, let z be thirty, and in that context, compute x plus y plus z.
This is equivalent to nested scopes:
let x = 10 in (
let y = 20 in (
let z = 30 in (
x + y + z
)
)
)
COMPARISON WITH OTHER LANGUAGES
In languages like JavaScript or Python, you might write:
let x = 10;
let y = 20;
return x + y;
The semicolons separate statements, and the return keyword indicates what value to produce. In PureFunc, the "in" keyword serves both purposes: it separates the binding from its usage and indicates where to find the result value.
In mathematical notation, you might write:
"let x = 10, then x + 5"
The "in" keyword in PureFunc is like the "then" in this mathematical phrasing.
PRACTICAL EXAMPLES
Here is a simple calculation using let bindings:
let radius = 5 in
let pi = 3.14159 in
let area = pi * radius * radius in
area
This computes the area of a circle. Each "in" keyword introduces the scope where we can use the previously defined variables. The final result is the value of area.
Here is a more complex example with functions:
let double = fn x -> x * 2 in
let triple = fn x -> x * 3 in
let applyBoth = fn x -> double x + triple x in
applyBoth 5
We define double and triple functions, then define applyBoth which uses both of them. The "in" keywords create nested scopes where each definition is available. The result is ten plus fifteen, which equals twenty-five.
THE "IN" KEYWORD WITH RECURSION
When defining recursive functions, the "in" keyword is essential because it creates the scope where the function can reference itself:
let factorial = fn n ->
if n == 0
then 1
else n * factorial (n - 1)
in
factorial 5
The "in" keyword creates a scope where the name "factorial" is bound to the function. Inside the function body, we can reference "factorial" recursively because we are within the scope created by "in".
WHAT HAPPENS WITHOUT "IN"
If PureFunc did not have the "in" keyword, the language would be ambiguous. Consider:
let x = 10 x + 5
Without "in", it is unclear where the binding ends and where the expression using the binding begins. Is this trying to bind x to "10 x + 5" (which would be an error), or is it trying to bind x to 10 and then evaluate "x + 5"?
The "in" keyword makes this unambiguous:
let x = 10 in x + 5
Now it is clear: bind x to ten, then evaluate x plus five in that context.
SUMMARY
The "in" keyword serves three critical purposes in PureFunc:
First, it separates the binding definition from the expression that uses the binding. Everything before "in" defines what value the variable has. Everything after "in" is where you use that variable.
Second, it defines the scope of the variable. The variable only exists in the expression after "in". Once that expression is fully evaluated, the variable is no longer accessible.
Third, it makes let bindings into expressions rather than statements. The entire "let variable equals value in body" construct evaluates to whatever the body evaluates to, making it composable with other expressions.
Understanding the "in" keyword is fundamental to reading and writing PureFunc code. It is the mechanism that creates local scopes and allows you to build complex expressions from simpler named parts.
No comments:
Post a Comment