This is the eighth part of the YAUL series. For your convenience you can find other parts in the table of contents in Part 1 — Introduction

Today we are going to handle functions in YAUL. Let’s go.

Introduction

We are going to represent functions as blocks of code. Since we want to handle local variables, we will need to add them to scope and remove after creating the function. We also need to handle names duplicates and conflicts with functions defined in standard library. The code will be little longer today.

Parser

Let’s begin with PLY:

def p_function_decl_with_params(p):
    """function_decl : FUNCTION IDENT '(' list_param ')' block """
    p[0] = Compiler.FunctionDefinition()
    p[0].Name = p[2]
    p[0].Body = p[6]
    p[0].Parameters = System.Collections.Generic.List[Compiler.Parameter] (p[4])

def p_function_decl_with_params2(p):
    """function_decl : error FUNCTION IDENT '(' list_param ')' block """
    p[0] = Compiler.FunctionDefinition()
    p[0].Name = p[3]
    p[0].Body = p[7]
    p[0].Parameters = System.Collections.Generic.List[Compiler.Parameter] (p[5])
Comp
def p_function_decl_without_params(p):
    """function_decl : FUNCTION IDENT '(' ')' block """
    p[0] = Compiler.FunctionDefinition()
    p[0].Name = p[2]
    p[0].Body = p[5]
    p[0].Parameters = System.Collections.Generic.List[Compiler.Parameter] ( [] )

def p_function_decl_with_params(p):

"""function_decl : FUNCTION IDENT '(' list_param ')' block """

p[0] = Compiler.FunctionDefinition()

p[0].Name = p[2]

p[0].Body = p[6]

p[0].Parameters = System.Collections.Generic.List[Compiler.Parameter] (p[4])

def p_function_decl_with_params2(p):

"""function_decl : error FUNCTION IDENT '(' list_param ')' block """

p[0] = Compiler.FunctionDefinition()

p[0].Name = p[3]

p[0].Body = p[7]

p[0].Parameters = System.Collections.Generic.List[Compiler.Parameter] (p[5])

Comp

def p_function_decl_without_params(p):

"""function_decl : FUNCTION IDENT '(' ')' block """

p[0] = Compiler.FunctionDefinition()

p[0].Name = p[2]

p[0].Body = p[5]

p[0].Parameters = System.Collections.Generic.List[Compiler.Parameter] ( [] )

It looks very similar to code for loops. One additional thing is list of parameters:

def p_list_param_first(p):
    """list_param : IDENT """
    param = Compiler.Parameter()
    param.Name = p[1]
    p[0] = [param]    

def p_list_param_next(p):
    """list_param : list_param ',' IDENT """
    p[0] = p[1]
    param = Compiler.Parameter()
    param.Name = p[3]
    p[0].append(param)

def p_list_param_first(p):

"""list_param : IDENT """

param = Compiler.Parameter()

param.Name = p[1]

p[0] = [param]

def p_list_param_next(p):

"""list_param : list_param ',' IDENT """

p[0] = p[1]

param = Compiler.Parameter()

param.Name = p[3]

p[0].append(param)

However, there is a very special keyword for functions: return. We can return value or just exit the function:

def p_return_void(p):
    """return : RETURN ';' """
    p[0] = Compiler.Compiler.Return()

def p_return_value(p):
    """return : RETURN expr ';' """
    p[0] = Compiler.Return()
    p[0].ReturnedValue = p[2]

def p_return_void(p):

"""return : RETURN ';' """

p[0] = Compiler.Compiler.Return()

def p_return_value(p):

"""return : RETURN expr ';' """

p[0] = Compiler.Return()

p[0].ReturnedValue = p[2]

What’s more, we would like to be able to call our functions:

def p_proc_call(p):
    """proc_call : funct_call ';' """
    p[0] = Compiler.ProdecureCall()
    p[0].FunctionCall = p[1]

def p_funct_call_normal_none_params(p):
    """funct_call : IDENT '(' ')'"""
    p[0] = Compiler.FunctionCall()
    p[0].Name = p[1]
    p[0].Arguments = System.Collections.Generic.List[Compiler.IExpression]()

def p_funct_call_normal_with_params(p):
    """funct_call : IDENT '(' list_expr ')'"""
    p[0] = Compiler.FunctionCall()
    p[0].Name = p[1]
    p[0].Arguments = System.Collections.Generic.List[Compiler.IExpression](p[3])

def p_proc_call(p):

"""proc_call : funct_call ';' """

p[0] = Compiler.ProdecureCall()

p[0].FunctionCall = p[1]

def p_funct_call_normal_none_params(p):

"""funct_call : IDENT '(' ')'"""

p[0] = Compiler.FunctionCall()

p[0].Name = p[1]

p[0].Arguments = System.Collections.Generic.List[Compiler.IExpression]()

def p_funct_call_normal_with_params(p):

"""funct_call : IDENT '(' list_expr ')'"""

p[0] = Compiler.FunctionCall()

p[0].Name = p[1]

p[0].Arguments = System.Collections.Generic.List[Compiler.IExpression](p[3])

This is it, nothing tricky here.

C#

We start with function definition:

using System; using System.Collections.Generic; using System.Linq; using System.Linq.Expressions; namespace Compiler { public class FunctionDefinition : ISemanticObject { public StatementBlock Body { get; set; } public List< Parameter> Parameters { get; set; } public string Name { get; set; } public Expression Accept(IVisitor visitor) { var parameterExpressions = CreateParamsExpression(visitor); AddParamsToScope(visitor, parameterExpressions); DefineReturnLabel(visitor); var bodyExpression = Body.Accept(visitor); RemoveParamsFromScope(visitor, parameterExpressions); var usedVariables = GetUsedVariables(visitor); var newBodyExpression = DecorateWithReturnLabel(visitor, bodyExpression, usedVariables); var functionExpression = CreateFunctionExpression(visitor, newBodyExpression, parameterExpressions); visitor.LocalVariables.Clear(); return functionExpression; } private BinaryExpression CreateFunctionExpression(IVisitor visitor, BlockExpression newBodyExpression, IEnumerable< ParameterExpression> parameterExpressions) { var methodVar = (ParameterExpression) visitor.Functions.Single(func => func.Name.Equals(Name)).Function; var functionExpression = Expression.Assign(methodVar, Expression.Lambda(newBodyExpression, Name, parameterExpressions)); return functionExpression; } private static BlockExpression DecorateWithReturnLabel(IVisitor visitor, Expression bodyExpression, IEnumerable< ParameterExpression> usedVariables) { Expression defaultValue = Expression.Call(typeof (YaulCompiler), "ConstructSimpleObject", null, new Expression[] {Expression.Constant("", typeof (string))}); var labelExpression = Expression.Label(visitor.ReturnLabel, defaultValue); var bodyAndLabel = new List< Expression> {bodyExpression, labelExpression}; return Expression.Block(usedVariables, bodyAndLabel); } private static IEnumerable< ParameterExpression> GetUsedVariables(IVisitor visitor) { return visitor.LocalVariables.Select(variable => variable.VariableReference); } private static void RemoveParamsFromScope(IVisitor visitor, List< ParameterExpression> parameterExpressions) { for(int i = visitor.LocalVariables.Count - 1; i >= 0; --i) { if (parameterExpressions.Contains(visitor.LocalVariables[i].VariableReference)) { visitor.LocalVariables.RemoveAt(i); } } } private static void DefineReturnLabel(IVisitor visitor) { visitor.ReturnLabel = Expression.Label(typeof(SimpleObject)); } private void AddParamsToScope(IVisitor visitor, IEnumerable< ParameterExpression> parameterExpressions) { var variables = parameterExpressions.Select(CreateVariableFromParam); foreach(var variable in variables) { visitor.LocalVariables.Add(variable); } } private Variable CreateVariableFromParam(ParameterExpression parameterExpression) { return new Variable { Name = parameterExpression.Name, VariableReference = parameterExpression }; } private List< ParameterExpression> CreateParamsExpression(IVisitor visitor) { return Parameters.Select(parameter => (ParameterExpression) parameter.Accept(visitor)).ToList(); } public void FindLabels(IVisitor visitor) { } public PreparedFunction Prepare() { var type = DetermineType(); var variable = Expression.Variable(type, Name); return new PreparedFunction { Function = variable, Name = Name }; } private Type DetermineType() { var parameterExpressions = Parameters.Select(parameter => (ParameterExpression) parameter.Accept(null)).ToList(); LabelTarget returnLabel = Expression.Label(typeof (SimpleObject)); Expression defaultValue = Expression.Call(typeof (YaulCompiler), "ConstructSimpleObject", null, new Expression[] {Expression.Constant("", typeof (string))}); var simpleBody = Expression.Label(returnLabel, defaultValue); var declaration = Expression.Lambda(simpleBody, Name, parameterExpressions); return declaration.Type; } } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;

namespace Compiler
{
    public class FunctionDefinition : ISemanticObject
    {
        public StatementBlock Body { get; set; }
        public List< Parameter> Parameters { get; set; }

        public string Name { get; set; }

        public Expression Accept(IVisitor visitor)
        {
            var parameterExpressions = CreateParamsExpression(visitor);
            AddParamsToScope(visitor, parameterExpressions);

            DefineReturnLabel(visitor);

            var bodyExpression = Body.Accept(visitor);

            RemoveParamsFromScope(visitor, parameterExpressions);

            var usedVariables = GetUsedVariables(visitor);

            var newBodyExpression = DecorateWithReturnLabel(visitor, bodyExpression, usedVariables);

            var functionExpression = CreateFunctionExpression(visitor, newBodyExpression, parameterExpressions);

            visitor.LocalVariables.Clear();

            return functionExpression;
        }

        private BinaryExpression CreateFunctionExpression(IVisitor visitor, BlockExpression newBodyExpression,
                                                          IEnumerable< ParameterExpression> parameterExpressions)
        {
            var methodVar = (ParameterExpression) visitor.Functions.Single(func => func.Name.Equals(Name)).Function;
            var functionExpression = Expression.Assign(methodVar,
                                                       Expression.Lambda(newBodyExpression, Name, parameterExpressions));
            return functionExpression;
        }

        private static BlockExpression DecorateWithReturnLabel(IVisitor visitor, Expression bodyExpression, IEnumerable< ParameterExpression> usedVariables)
        {
            Expression defaultValue = Expression.Call(typeof (YaulCompiler), "ConstructSimpleObject", null,
                                                      new Expression[] {Expression.Constant("", typeof (string))});
            var labelExpression = Expression.Label(visitor.ReturnLabel, defaultValue);

            var bodyAndLabel = new List< Expression> {bodyExpression, labelExpression};
            return Expression.Block(usedVariables, bodyAndLabel);
        }

        private static IEnumerable< ParameterExpression> GetUsedVariables(IVisitor visitor)
        {
            return visitor.LocalVariables.Select(variable => variable.VariableReference);
        }

        private static void RemoveParamsFromScope(IVisitor visitor, List< ParameterExpression> parameterExpressions)
        {
            for(int i = visitor.LocalVariables.Count - 1; i >= 0; --i)
            {
                if (parameterExpressions.Contains(visitor.LocalVariables[i].VariableReference))
                {
                    visitor.LocalVariables.RemoveAt(i);
                }
            }
        }

        private static void DefineReturnLabel(IVisitor visitor)
        {
            visitor.ReturnLabel = Expression.Label(typeof(SimpleObject));
        }

        private void AddParamsToScope(IVisitor visitor, IEnumerable< ParameterExpression> parameterExpressions)
        {
            var variables = parameterExpressions.Select(CreateVariableFromParam);
            foreach(var variable in variables)
            {
                visitor.LocalVariables.Add(variable);
            }

        }

        private Variable CreateVariableFromParam(ParameterExpression parameterExpression)
        {
            return new Variable
                {
                    Name = parameterExpression.Name,
                    VariableReference = parameterExpression
                };
        }

        private List< ParameterExpression> CreateParamsExpression(IVisitor visitor)
        {
            return Parameters.Select(parameter => (ParameterExpression) parameter.Accept(visitor)).ToList();
        }

        public void FindLabels(IVisitor visitor)
        {

        }

        public PreparedFunction Prepare()
        {
            var type = DetermineType();
            var variable = Expression.Variable(type, Name);

            return new PreparedFunction
                {
                    Function = variable,
                    Name = Name
                };

        }

        private Type DetermineType()
        {
            var parameterExpressions = Parameters.Select(parameter => (ParameterExpression) parameter.Accept(null)).ToList();

            LabelTarget returnLabel = Expression.Label(typeof (SimpleObject));
            Expression defaultValue = Expression.Call(typeof (YaulCompiler), "ConstructSimpleObject", null,
                                                      new Expression[] {Expression.Constant("", typeof (string))});

            var simpleBody = Expression.Label(returnLabel, defaultValue);

            var declaration = Expression.Lambda(simpleBody, Name, parameterExpressions);

            return declaration.Type;
        }
    }
}

Let’s examin `Accept` function. First, we create expressions for parameters. Next, we add them to local scope so they can be used as local variables. Next, we visit body. Since we have local variables in scope, body is free to use them. When it is done, we remove parameters from scope. Next, we create block for function, create expression holding our function, clear local parameters, and we are done.

`PreparedFunction` looks as follows:

using System.Linq.Expressions; namespace Compiler { public class PreparedFunction { public Expression Function { get; set; } public string Name { get; set; } } }

1
2
3
4
5
6
7
8
9
10

using System.Linq.Expressions;

namespace Compiler
{
    public class PreparedFunction
    {
        public Expression Function { get; set; }
        public string Name { get; set; }
    }
}

Function’s parameters are defined as:

using System.Linq.Expressions; namespace Compiler { public class Parameter : ISemanticObject { public string Name { get; set; } public Expression Accept(IVisitor visitor) { return Expression.Parameter(typeof (SimpleObject), Name); } public void FindLabels(IVisitor visitor) { } } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

using System.Linq.Expressions;

namespace Compiler
{
    public class Parameter : ISemanticObject
    {
        public string Name { get; set; }
        public Expression Accept(IVisitor visitor)
        {
            return Expression.Parameter(typeof (SimpleObject), Name);
        }

        public void FindLabels(IVisitor visitor)
        {
        }
    }
}

And `return` instruction:

using System.Linq.Expressions; namespace Compiler { public class Return : IStatement { public IExpression ReturnedValue { get; set; } public Expression Accept(IVisitor visitor) { if (ReturnedValue != null) { var value = ReturnedValue.Accept(visitor); return Expression.Return(visitor.ReturnLabel, value, typeof(SimpleObject)); } Expression defaultValue = Expression.Call(typeof (YaulCompiler), "ConstructSimpleObject", null, new Expression[] { Expression.Constant("", typeof(string)) }); return Expression.Return(visitor.ReturnLabel, defaultValue, typeof(SimpleObject)); } public void FindLabels(IVisitor visitor) { } } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

using System.Linq.Expressions;

namespace Compiler
{
    public class Return : IStatement
    {
        public IExpression ReturnedValue { get; set; }

        public Expression Accept(IVisitor visitor)
        {
            if (ReturnedValue != null)
            {
                var value = ReturnedValue.Accept(visitor);
                return Expression.Return(visitor.ReturnLabel, value, typeof(SimpleObject));
            }
            Expression defaultValue = Expression.Call(typeof (YaulCompiler), "ConstructSimpleObject", null, new Expression[] { Expression.Constant("", typeof(string)) });
            return Expression.Return(visitor.ReturnLabel, defaultValue, typeof(SimpleObject));
        }

        public void FindLabels(IVisitor visitor)
        {
        }
    }
}

Please note, that we always return something, but in case when we want to exit the function, we simply ignore the value.

Anod now the last part, calling functions:

using System.Linq.Expressions; namespace Compiler { public class ProdecureCall : IStatement { public FunctionCall FunctionCall; public Expression Accept(IVisitor visitor) { return FunctionCall.Accept(visitor); } public void FindLabels(IVisitor visitor) { } } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

using System.Linq.Expressions;

namespace Compiler
{
    public class ProdecureCall : IStatement
    {
        public FunctionCall FunctionCall;

        public Expression Accept(IVisitor visitor)
        {
            return FunctionCall.Accept(visitor);
        }

        public void FindLabels(IVisitor visitor)
        {
        }
    }
}

using System.Collections.Generic; using System.Linq; using System.Linq.Expressions; namespace Compiler { public class FunctionCall : IExpression { public string Name { get; set; } public IList< IExpression> Arguments { get; set; } public Expression Accept(IVisitor visitor) { var function = visitor.Functions.SingleOrDefault(func => func.Name.Equals(Name)); if (function != null) { var argumentsExpression = Arguments.Select(argument => argument.Accept(visitor)); var lambda = function; return Expression.Invoke(lambda.Function, argumentsExpression); } throw new MethodNotFoundException(Name); } public void FindLabels(IVisitor visitor) { } } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;

namespace Compiler
{
    public class FunctionCall : IExpression
    {
        public string Name { get; set; }
        public IList< IExpression> Arguments { get; set; }

        public Expression Accept(IVisitor visitor)
        {
            var function = visitor.Functions.SingleOrDefault(func => func.Name.Equals(Name));
            if (function != null)
            {
                var argumentsExpression = Arguments.Select(argument => argument.Accept(visitor));
                var lambda = function;
                return Expression.Invoke(lambda.Function, argumentsExpression);
            }

            throw new MethodNotFoundException(Name);
        }

        public void FindLabels(IVisitor visitor)
        {
        }
    }
}

Summary

Function handling is the most difficult part in our language, however, there is no magic. Wee simply need to write a little more code to correctly handle and create function’s block. Next time we are going to handle standard library.