evaluate() - Code Metrics - Wilfred/trifle - Measure and Improve Code Quality continuously with Scrutinizer

evaluate() F
last analyzed 2016-04-21 07:45 UTC

↳ Parent: Project

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Metric	Value
cc	16
dl	0
loc	97
rs	2

How to fix Long Method Complexity

from trifle_types import (
    List, Bytestring, Hashmap, Character, Symbol,
    Integer, Float, Fraction,
    Null, NULL,
    Function, FunctionWithEnv, Lambda, Macro, Boolean,
    Keyword, String,
    TrifleExceptionInstance, TrifleExceptionType)
from errors import (
    error, wrong_type, no_such_variable, stack_overflow,
    ArityError, wrong_argument_number, value_error)
from almost_python import zip
from environment import Scope, LetScope, special_expressions
from parameters import is_variable_arity, check_parameters


# TODO: allow users to change this at runtime.
MAX_STACK_DEPTH = 100


class Stack(object):
    def __init__(self):
        self.values = []

    def __repr__(self):
        return "<Stack: %r>\n" % "\n".join(map(repr, self.values))

    def push(self, value):
        assert len(self.values) <= MAX_STACK_DEPTH + 1, "Stack should be checked for overflow!"
        self.values.append(value)

    def pop(self):
        return self.values.pop()

    def peek(self):
        return self.values[-1]

    def is_empty(self):
        return not bool(self.values)


class Frame(object):
    def __init__(self, expression, environment, as_block=False):
        # The expression we're evaluating, e.g. (if x y 2)
        self.expression = expression

        # The lexical environment, so any variables defined in this
        # function context and any enclosing contexts.
        self.environment = environment

        # The current point we've executed up to in the expression, e.g. 2.
        self.expression_index = 0

        # Used by let to track which assignments have been evaluated.
        self.let_assignment_index = 0

        # Used to keep track of the let environment as we add bindings.
        self.let_environment = None

        # Results of parts of the expression that we have evaluated, e.g.
        # [TRUE, Integer(3)]
        self.evalled = []

        # Is this a single expression to evaluate, or a block? If it's
        # a block, we evaluate each list element and return the
        # last.
        self.as_block = as_block

        # Is this a try expression that will catch certain error types?
        self.catch_error = None

    def __repr__(self):
        return ("expession: %r,\tindex: %d,\tas_block: %s,\tevalled: %r" %
                (self.expression, self.expression_index, self.as_block,
                 self.evalled))


# TODO: Remove this function, it promotes silently ignoring exceptions.
def evaluate_all(expressions, environment):
    """Evaluate a trifle List of expressions in the given environment.

    """
    result = NULL
    
    for expression in expressions.values:
        result = evaluate(expression, environment)

        if is_thrown_exception(result, error):
            return result

    return result


def is_error_instance(error_instance, error_type):
    """Is the type of error_instance the same as error_type, or inherit from it?

    >>> is_error_instance(division_by_zero_instance, division_by_zero)
    True
    >>> is_error_instance(division_by_zero_instance, error)
    True
    >>> is_error_instance(division_by_zero_instance, no_such_variable)
    False

    """
    if not isinstance(error_instance, TrifleExceptionInstance):
        return False

    exception_type_found = error_instance.exception_type

    while exception_type_found:
        if exception_type_found == error_type:
            return True

        exception_type_found = exception_type_found.parent

    return False


def is_thrown_exception(value, exception_type):
    if not is_error_instance(value, exception_type):
        return False
    else:
        return not value.caught


def evaluate(expression, environment):
    """Evaluate the given expression in the given environment.

    """
    stack = Stack()
    stack.push(Frame(expression, environment))

    # We evaluate expressions by pushing them on the stack, then
    # iterating through the elements of the list, evaluating as
    # appropriate. This ensures recursion in the Trifle program does
    # not require recursion in the interpreter.
    while stack:

        if len(stack.values) > MAX_STACK_DEPTH:
            result = TrifleExceptionInstance(
                # TODO: write a better exception message.
                stack_overflow, u"Stack overflow"
            )
        else:
            frame = stack.peek()

            if isinstance(frame.expression, List):
                list_elements = frame.expression.values

                if list_elements:
                    head = list_elements[0]
                    raw_arguments = list_elements[1:]

                    # Handle special expressions.
                    if isinstance(head, Symbol) and head.symbol_name in special_expressions:
                        special_expression = special_expressions[head.symbol_name]

                        try:
                            result = special_expression.call(raw_arguments, frame.environment, stack)
                        except ArityError as e:
                            result = TrifleExceptionInstance(
                                wrong_argument_number, e.message)

                    else:
                        try:
                            result = evaluate_function_call(stack)
                        except ArityError as e:
                            result = TrifleExceptionInstance(
                                wrong_argument_number,
                                e.message
                            )

                else:
                    result = TrifleExceptionInstance(
                        value_error, u"Can't evaluate an empty list."
                    )

            else:
                result = evaluate_value(frame.expression, frame.environment)

        # Returning None means we have work left to do, but a Trifle value means
        # we're done with this frame.
        if not result is None:

            if is_thrown_exception(result, error):
                # We search any try blocks starting from the
                # innermost, and evaluate the first matching :catch we find.

                while not stack.is_empty():
                    # TODO: a proper condition system rather than
                    # always unwinding the stack.
                    frame = stack.pop()
                    expected_error = frame.catch_error

                    if expected_error and is_thrown_exception(result, expected_error):
                        result.caught = True
                        
                        # Execute the catch body.
                        exception_symbol = frame.expression.values[4]
                        catch_body = frame.expression.values[5]
                        
                        catch_body_scope = LetScope({
                            exception_symbol.symbol_name: result
                        })
                        catch_env = frame.environment.with_nested_scope(catch_body_scope)

                        stack.push(Frame(catch_body, catch_env))
                        break

                else:
                    # Otherwise, just propagate the error to the toplevel.
                    return result

            else:
                stack.pop()

                if not stack.is_empty():
                    frame = stack.peek()
                    frame.evalled.append(result)
                else:
                    # We evaluated a value at the top level, nothing left to do.
                    return result


# todo: this would be simpler if `values` was also a trifle List
def build_scope(name, parameters, values):
    """Build a single scope where every value in values (a python list) is
    bound to a symbol according to the parameters List given.

    If the parameters list contains `:rest foo`, any remaining arguments
    are passed a list in the named parameter.

    """
    varargs = is_variable_arity(parameters)

    if varargs:
        # The only negative slice supported by RPython is -1, so we
        # have to do it twice.
        normal_parameters = parameters.values[:-1][:-1]
    else:
        normal_parameters = parameters.values

    # Ensure we have the right number of arguments:
    check_parameters(name, parameters, List(values))

    scope = Scope({})
    for variable, value in zip(normal_parameters, values):
        scope.set(variable.symbol_name,  value)

    # todoc: varargs on macros
    # todo: consistently use the terms 'parameters' and 'arguments'
    if varargs:
        # Create a Trifle list of any remaining arguments.
        remaining_args = List(values[len(normal_parameters):])

        # Assign it to the variable args symbol.
        scope.set(parameters.values[-1].symbol_name, remaining_args)

    return scope


def expand_macro(macro, arguments, environment):
    """Expand the given macro by one iteration. Arguments should be a
    Python list of unevaluated Trifle values.

    """
    # Build a new environment to evaluate with.
    inner_scope = build_scope(macro.name, macro.arguments, arguments)
    macro_env = environment.globals_only().with_nested_scope(inner_scope)

    return evaluate_all(macro.body, macro_env)


def evaluate_function_call(stack):
    """Given a stack, where the the top element is a single Trifle call
    (either a function or a macro), execute it iteratively.

    """
    frame = stack.peek()
    environment = frame.environment
    expression = frame.expression

    if frame.expression_index == 1:
        # If the head of the list evaluated to a macro, we skip
        # evaluating the arguments. Otherwise, continue as evaluating
        # as normal.
        evalled_head = frame.evalled[-1]
        macro_arguments = frame.expression.values[1:]
        
        if isinstance(evalled_head, Macro):
            expanded = expand_macro(evalled_head, macro_arguments, environment)

            # If macro expansion throws an error, terminate, returning that error.
            if is_thrown_exception(expanded, error):
                return expanded
                
            stack.push(Frame(expanded, environment))

            # Ensure we don't evaluate any of arguments to the macro.
            frame.expression_index = len(expression.values) + 1
            return None

    if frame.expression_index < len(expression.values):
        # Evaluate the remaining elements of this list (we work left-to-right).
        raw_argument = expression.values[frame.expression_index]
        stack.push(Frame(raw_argument, environment))

        frame.expression_index += 1
        return None

    elif frame.expression_index == len(expression.values):
        # We've evalled all the elements of the list.

        # This list doesn't represent a function call, rather it's
        # just a lambda body. We just want the last result.
        if frame.as_block:
            return frame.evalled[-1]
        
        # We've evaluated the function and its arguments, now call the
        # function with the evalled arguments.
        function = frame.evalled[0]
        arguments = frame.evalled[1:]

        if isinstance(function, Function):
            return function.call(arguments)

        elif isinstance(function, FunctionWithEnv):
            return function.call(arguments, environment, stack)

        elif isinstance(function, Lambda):
            # Build a new environment to evaluate with.
            inner_scope = build_scope(u"<lambda>", function.arguments, arguments)

            lambda_env = function.env.with_nested_scope(inner_scope)

            # Evaluate the lambda's body in our new environment.
            # TODO: by replacing the stack here, we could do TCO.
            stack.push(Frame(function.body, lambda_env, as_block=True))

            frame.expression_index += 1
            return None

        else:
            # todoc: this error
            return TrifleExceptionInstance(
                wrong_type,
                u"You can only call functions or macros, but got: %s"
                % function.repr())

    else:
        # We had a lambda body or expanded macro and we've now evalled
        # it, so we're done.
        return frame.evalled[-1]


def evaluate_value(value, environment):
    if isinstance(value, Integer):
        return value
    elif isinstance(value, Float):
        return value
    elif isinstance(value, Fraction):
        return value
    elif isinstance(value, Boolean):
        return value
    elif isinstance(value, Null):
        return value
    elif isinstance(value, Keyword):
        return value
        
    # String and bytestring literals should evaluate to a copy of
    # themselves, so we can safely use string literals in function
    # bodies and then mutate them.
    elif isinstance(value, String):
        char_list = value.string
        return String([char for char in char_list])
    elif isinstance(value, Bytestring):
        byte_list = value.byte_value
        return Bytestring([byte for byte in byte_list])
    # Likewise for hashmap literals.
    # TODO: Should this be a deep copy?
    elif isinstance(value, Hashmap):
        hashmap = Hashmap()
        hashmap.dict = value.dict.copy()
        return hashmap
        
    elif isinstance(value, Character):
        return value
    elif isinstance(value, Lambda):
        return value
    elif isinstance(value, Function):
        return value
    elif isinstance(value, Macro):
        return value
    elif isinstance(value, TrifleExceptionInstance):
        return value
    elif isinstance(value, TrifleExceptionType):
        return value
    elif isinstance(value, Macro):
        return value
    elif isinstance(value, Symbol):
        symbol_name = value.symbol_name
        if environment.contains(symbol_name):
            return environment.get(symbol_name)
        else:
            # TODO: suggest variables with similar spelling.
            return TrifleExceptionInstance(
                no_such_variable,
                u"No such variable defined: '%s'" % symbol_name)
    else:
        assert False, "I don't know how to evaluate that value: %s" % value


1			from trifle_types import (
2			List, Bytestring, Hashmap, Character, Symbol,
3			Integer, Float, Fraction,
4			Null, NULL,
5			Function, FunctionWithEnv, Lambda, Macro, Boolean,
6			Keyword, String,
7			TrifleExceptionInstance, TrifleExceptionType)
8			from errors import (
9			error, wrong_type, no_such_variable, stack_overflow,
10			ArityError, wrong_argument_number, value_error)
11			from almost_python import zip
12			from environment import Scope, LetScope, special_expressions
13			from parameters import is_variable_arity, check_parameters
14
15
16			# TODO: allow users to change this at runtime.
17			MAX_STACK_DEPTH = 100
18
19
20			class Stack(object):
21			def __init__(self):
22			self.values = []
23
24			def __repr__(self):
25			return "<Stack: %r>\n" % "\n".join(map(repr, self.values))
26
27			def push(self, value):
28			assert len(self.values) <= MAX_STACK_DEPTH + 1, "Stack should be checked for overflow!"
29			self.values.append(value)
30
31			def pop(self):
32			return self.values.pop()
33
34			def peek(self):
35			return self.values[-1]
36
37			def is_empty(self):
38			return not bool(self.values)
39
40
41			class Frame(object):
42			def __init__(self, expression, environment, as_block=False):
43			# The expression we're evaluating, e.g. (if x y 2)
44			self.expression = expression
45
46			# The lexical environment, so any variables defined in this
47			# function context and any enclosing contexts.
48			self.environment = environment
49
50			# The current point we've executed up to in the expression, e.g. 2.
51			self.expression_index = 0
52
53			# Used by let to track which assignments have been evaluated.
54			self.let_assignment_index = 0
55
56			# Used to keep track of the let environment as we add bindings.
57			self.let_environment = None
58
59			# Results of parts of the expression that we have evaluated, e.g.
60			# [TRUE, Integer(3)]
61			self.evalled = []
62
63			# Is this a single expression to evaluate, or a block? If it's
64			# a block, we evaluate each list element and return the
65			# last.
66			self.as_block = as_block
67
68			# Is this a try expression that will catch certain error types?
69			self.catch_error = None
70
71			def __repr__(self):
72			return ("expession: %r,\tindex: %d,\tas_block: %s,\tevalled: %r" %
73			(self.expression, self.expression_index, self.as_block,
74			self.evalled))
75
76
77			# TODO: Remove this function, it promotes silently ignoring exceptions.
78			def evaluate_all(expressions, environment):
79			"""Evaluate a trifle List of expressions in the given environment.
80
81			"""
82			result = NULL
83
84			for expression in expressions.values:
85			result = evaluate(expression, environment)
86
87			if is_thrown_exception(result, error):
88			return result
89
90			return result
91
92
93			def is_error_instance(error_instance, error_type):
94			"""Is the type of error_instance the same as error_type, or inherit from it?
95
96			>>> is_error_instance(division_by_zero_instance, division_by_zero)
97			True
98			>>> is_error_instance(division_by_zero_instance, error)
99			True
100			>>> is_error_instance(division_by_zero_instance, no_such_variable)
101			False
102
103			"""
104			if not isinstance(error_instance, TrifleExceptionInstance):
105			return False
106
107			exception_type_found = error_instance.exception_type
108
109			while exception_type_found:
110			if exception_type_found == error_type:
111			return True
112
113			exception_type_found = exception_type_found.parent
114
115			return False
116
117
118			def is_thrown_exception(value, exception_type):
119			if not is_error_instance(value, exception_type):
120			return False
121			else:
122			return not value.caught
123
124
125			def evaluate(expression, environment):
126			"""Evaluate the given expression in the given environment.
127
128			"""
129			stack = Stack()
130			stack.push(Frame(expression, environment))
131
132			# We evaluate expressions by pushing them on the stack, then
133			# iterating through the elements of the list, evaluating as
134			# appropriate. This ensures recursion in the Trifle program does
135			# not require recursion in the interpreter.
136			while stack:
137
138			if len(stack.values) > MAX_STACK_DEPTH:
139			result = TrifleExceptionInstance(
140			# TODO: write a better exception message.
141			stack_overflow, u"Stack overflow"
142			)
143			else:
144			frame = stack.peek()
145
146			if isinstance(frame.expression, List):
147			list_elements = frame.expression.values
148
149			if list_elements:
150			head = list_elements[0]
151			raw_arguments = list_elements[1:]
152
153			# Handle special expressions.
154			if isinstance(head, Symbol) and head.symbol_name in special_expressions:
155			special_expression = special_expressions[head.symbol_name]
156
157			try:
158			result = special_expression.call(raw_arguments, frame.environment, stack)
159			except ArityError as e:
160			result = TrifleExceptionInstance(
161			wrong_argument_number, e.message)
162
163			else:
164			try:
165			result = evaluate_function_call(stack)
166			except ArityError as e:
167			result = TrifleExceptionInstance(
168			wrong_argument_number,
169			e.message
170			)
171
172			else:
173			result = TrifleExceptionInstance(
174			value_error, u"Can't evaluate an empty list."
175			)
176
177			else:
178			result = evaluate_value(frame.expression, frame.environment)
179
180			# Returning None means we have work left to do, but a Trifle value means
181			# we're done with this frame.
182			if not result is None:
183
184			if is_thrown_exception(result, error):
185			# We search any try blocks starting from the
186			# innermost, and evaluate the first matching :catch we find.
187
188			while not stack.is_empty():
189			# TODO: a proper condition system rather than
190			# always unwinding the stack.
191			frame = stack.pop()
192			expected_error = frame.catch_error
193
194			if expected_error and is_thrown_exception(result, expected_error):
195			result.caught = True
196
197			# Execute the catch body.
198			exception_symbol = frame.expression.values[4]
199			catch_body = frame.expression.values[5]
200
201			catch_body_scope = LetScope({
202			exception_symbol.symbol_name: result
203			})
204			catch_env = frame.environment.with_nested_scope(catch_body_scope)
205
206			stack.push(Frame(catch_body, catch_env))
207			break
208
209			else:
210			# Otherwise, just propagate the error to the toplevel.
211			return result
212
213			else:
214			stack.pop()
215
216			if not stack.is_empty():
217			frame = stack.peek()
218			frame.evalled.append(result)
219			else:
220			# We evaluated a value at the top level, nothing left to do.
221			return result
222
223
224			# todo: this would be simpler if `values` was also a trifle List
225			def build_scope(name, parameters, values):
226			"""Build a single scope where every value in values (a python list) is
227			bound to a symbol according to the parameters List given.
228
229			If the parameters list contains `:rest foo`, any remaining arguments
230			are passed a list in the named parameter.
231
232			"""
233			varargs = is_variable_arity(parameters)
234
235			if varargs:
236			# The only negative slice supported by RPython is -1, so we
237			# have to do it twice.
238			normal_parameters = parameters.values[:-1][:-1]
239			else:
240			normal_parameters = parameters.values
241
242			# Ensure we have the right number of arguments:
243			check_parameters(name, parameters, List(values))
244
245			scope = Scope({})
246			for variable, value in zip(normal_parameters, values):
247			scope.set(variable.symbol_name, value)
248
249			# todoc: varargs on macros
250			# todo: consistently use the terms 'parameters' and 'arguments'
251			if varargs:
252			# Create a Trifle list of any remaining arguments.
253			remaining_args = List(values[len(normal_parameters):])
254
255			# Assign it to the variable args symbol.
256			scope.set(parameters.values[-1].symbol_name, remaining_args)
257
258			return scope
259
260
261			def expand_macro(macro, arguments, environment):
262			"""Expand the given macro by one iteration. Arguments should be a
263			Python list of unevaluated Trifle values.
264
265			"""
266			# Build a new environment to evaluate with.
267			inner_scope = build_scope(macro.name, macro.arguments, arguments)
268			macro_env = environment.globals_only().with_nested_scope(inner_scope)
269
270			return evaluate_all(macro.body, macro_env)
271
272
273			def evaluate_function_call(stack):
274			"""Given a stack, where the the top element is a single Trifle call
275			(either a function or a macro), execute it iteratively.
276
277			"""
278			frame = stack.peek()
279			environment = frame.environment
280			expression = frame.expression
281
282			if frame.expression_index == 1:
283			# If the head of the list evaluated to a macro, we skip
284			# evaluating the arguments. Otherwise, continue as evaluating
285			# as normal.
286			evalled_head = frame.evalled[-1]
287			macro_arguments = frame.expression.values[1:]
288
289			if isinstance(evalled_head, Macro):
290			expanded = expand_macro(evalled_head, macro_arguments, environment)
291
292			# If macro expansion throws an error, terminate, returning that error.
293			if is_thrown_exception(expanded, error):
294			return expanded
295
296			stack.push(Frame(expanded, environment))
297
298			# Ensure we don't evaluate any of arguments to the macro.
299			frame.expression_index = len(expression.values) + 1
300			return None
301
302			if frame.expression_index < len(expression.values):
303			# Evaluate the remaining elements of this list (we work left-to-right).
304			raw_argument = expression.values[frame.expression_index]
305			stack.push(Frame(raw_argument, environment))
306
307			frame.expression_index += 1
308			return None
309
310			elif frame.expression_index == len(expression.values):
311			# We've evalled all the elements of the list.
312
313			# This list doesn't represent a function call, rather it's
314			# just a lambda body. We just want the last result.
315			if frame.as_block:
316			return frame.evalled[-1]
317
318			# We've evaluated the function and its arguments, now call the
319			# function with the evalled arguments.
320			function = frame.evalled[0]
321			arguments = frame.evalled[1:]
322
323			if isinstance(function, Function):
324			return function.call(arguments)
325
326			elif isinstance(function, FunctionWithEnv):
327			return function.call(arguments, environment, stack)
328
329			elif isinstance(function, Lambda):
330			# Build a new environment to evaluate with.
331			inner_scope = build_scope(u"<lambda>", function.arguments, arguments)
332
333			lambda_env = function.env.with_nested_scope(inner_scope)
334
335			# Evaluate the lambda's body in our new environment.
336			# TODO: by replacing the stack here, we could do TCO.
337			stack.push(Frame(function.body, lambda_env, as_block=True))
338
339			frame.expression_index += 1
340			return None
341
342			else:
343			# todoc: this error
344			return TrifleExceptionInstance(
345			wrong_type,
346			u"You can only call functions or macros, but got: %s"
347			% function.repr())
348
349			else:
350			# We had a lambda body or expanded macro and we've now evalled
351			# it, so we're done.
352			return frame.evalled[-1]
353
354
355			def evaluate_value(value, environment):
356			if isinstance(value, Integer):
357			return value
358			elif isinstance(value, Float):
359			return value
360			elif isinstance(value, Fraction):
361			return value
362			elif isinstance(value, Boolean):
363			return value
364			elif isinstance(value, Null):
365			return value
366			elif isinstance(value, Keyword):
367			return value
368
369			# String and bytestring literals should evaluate to a copy of
370			# themselves, so we can safely use string literals in function
371			# bodies and then mutate them.
372			elif isinstance(value, String):
373			char_list = value.string
374			return String([char for char in char_list])
375			elif isinstance(value, Bytestring):
376			byte_list = value.byte_value
377			return Bytestring([byte for byte in byte_list])
378			# Likewise for hashmap literals.
379			# TODO: Should this be a deep copy?
380			elif isinstance(value, Hashmap):
381			hashmap = Hashmap()
382			hashmap.dict = value.dict.copy()
383			return hashmap
384
385			elif isinstance(value, Character):
386			return value
387			elif isinstance(value, Lambda):
388			return value
389			elif isinstance(value, Function):
390			return value
391			elif isinstance(value, Macro):
392			return value
393			elif isinstance(value, TrifleExceptionInstance):
394			return value
395			elif isinstance(value, TrifleExceptionType):
396			return value
397			elif isinstance(value, Macro):
398			return value
399			elif isinstance(value, Symbol):
400			symbol_name = value.symbol_name
401			if environment.contains(symbol_name):
402			return environment.get(symbol_name)
403			else:
404			# TODO: suggest variables with similar spelling.
405			return TrifleExceptionInstance(
406			no_such_variable,
407			u"No such variable defined: '%s'" % symbol_name)
408			else:
409			assert False, "I don't know how to evaluate that value: %s" % value
410

Wilfred / trifle

evaluate() F last analyzed 2016-04-21 07:45 UTC

Complexity

Size

Duplication

How to fix Long Method Complexity

Long Method

Complexity

Duplication Side-by-Side

Filter issues like

evaluate() F
last analyzed 2016-04-21 07:45 UTC