Building Your Own Programming Language From Scratch: Part IX - Hybrid Inheritance

Welcome to the next part of creating your own programming language. In this part, we’ll continue improving our toy language by implementing inheritance for the classes introduced earlier. Here are the previous parts:

1. Building Your Own Programming Language From Scratch
2. Building Your Own Programming Language From Scratch: Part II - Dijkstra's Two-Stack Algorithm
3. Build Your Own Programming Language Part III: Improving Lexical Analysis with Regex Lookaheads
4. Building Your Own Programming Language From Scratch Part IV: Implementing Functions
5. Building Your Own Programming Language From Scratch: Part V - Arrays
6. Building Your Own Programming Language From Scratch: Part VI - Loops
7. Building Your Own Programming Language From Scratch: Part VII - Classes
8. Building Your Own Programming Language From Scratch: Part VIII - Nested Classes

The full source code is available over on GitHub.

1. Inheritance Model

Let's start by defining the inheritance rules for our classes:

1. To inherit a class, we’ll be using the colon character : similar to C++ syntax:

class Base
end

class Derived: Base
end

2. We should be able to fill the Base class’s properties with the Derived class’s properties:

class Base [base_arg]
end

class Derived [derived_arg1, derived_arg2]: Base [derived_arg2]
end

3. When we create an instance of the Derived class containing constructor statements, the statements declared in the Base class’s constructor should be executed first:

class Base
	print "Constructor of Base class called"
end

class Derived: Base
	print "Constructor of Derived class called"
end

d = new Derived

Output:

Constructor of Base class called
Constructor of Derived class called

4. Our classes will support hybrid inheritance and derive a class from multiple types:

class A
end

class B
end

class C
end

class Derived: A, B, C
end

5. To make an Upcasting or Downcasting operation for a class instance, we will use as operator:

class Base
end

class Derived: Base
end

d = new Derived
b = d as Base # Downcasting to Base
d2 = b as Derived # Upcasting to Derived

6. In order to modify the Base class’s properties, we should first downcast an object to the Base type:

class Base [base_arg]
end

class Derived [derived_arg]: Base [derived_arg]
end

d = new Derived [ 1 ]

# Directly changing a property of the Derived type
d :: derived_arg = 2

# Downcasting instance to the Base and then changing Base’s property
d as Base :: base_arg = 3

7. If we change a property in the Base class, the corresponding reference property in the Derived class should be updated as well, and vice versa, if we change the Derived class’s property that we used to construct the Base class, the corresponding property in this Base class should also be updated:

class Base [base_arg]
end

class Derived [derived_arg]: Base [derived_arg]
end

d = new Derived [ 1 ]
d as Base :: base_arg = 2
print d

d :: derived_arg = 3
print d as Base

Output:

Derived [ derived_arg = 2 ]
Base [ base_arg = 3 ]

8. We won’t be using the super keyword that we have in Java because, with hybrid inheritance, there could be multiple inherited Base classes, and there is no way to know which super class to refer to without defining it explicitly.

   
   

   For this kind of action, we will use the cast operator to point the required Base type:

class A
      fun action
           print "A action"
      end
end

class B
      fun action
             print "B action"
      end
end

class C: A, B
      fun action
           this as B :: action []
           this as A :: action []
           print "C action"
      end
end

c = new C
c :: action []

Output:

B action
A action
C action

9. Lastly, in this part, we’ll add is operator to check whether an object is an instance of a particular class or not:

class A
end

class B: A
end

fun check_instance [object]
    if object is B
        print "Object is type of B"
    elif object is A
        print "Object is type of A"
    end
end

check_instance [ new A ]
check_instance [ new B ]

Output:

Object is type of A
Object is type of B

Now with these defined rules, let’s implement the inheritance model using already created structures from the previous parts. There are two main sections we’ll cover as usual: lexical analysis and syntax analysis.

2. Lexical Analysis

In this section, we will cover lexical analysis. It’s a process to divide the source code into language lexemes, such as keywords, variables, operators, etc. To define the lexemes, I’m using the regex expressions listed in the TokenType enum.

package org.example.toylanguage.token;

public enum TokenType {
    Comment("\\#.*"),
    LineBreak("[\\n\\r]"),
    Whitespace("[\\s\\t]"),
    Keyword("(if|elif|else|end|print|input|class|fun|return|loop|in|by|break|next)(?=\\s|$)(?!_)"),
    GroupDivider("(\\[|\\]|\\,|\\{|}|\\.{2})"),
    Logical("(true|false)(?=\\s|$)(?!_)"),
    Numeric("([-]?(?=[.]?[0-9])[0-9]*(?![.]{2})[.]?[0-9]*)"),
    Null("(null)(?=,|\\s|$)(?!_)"),
    This("(this)(?=,|\\s|$)(?!_)"),
    Text("\"([^\"]*)\""),
    Operator("(\\+|-|\\*|/{1,2}|%|>=|>|<=|<{1,2}|={1,2}|!=|!|:{2}\\s+new|:{2}|\\(|\\)|(new|and|or)(?=\\s|$))(?!_)"),
    Variable("[a-zA-Z_]+[a-zA-Z0-9_]*");

    private final String regex;
}

Every line of the toy language's source code is being processed through these regex expressions; with their help, we can accumulate the list of lexemes.

Let’s add the missing lexemes required for our inheritance model:

1. First, we need to add the single colon character : to signify the class inheritance.  We can add it to the GroupDivider lexeme with the 2 backslashes before the colon to make sure it will not be treated as a special character:

GroupDivider("(\\[|\\]|\\,|\\{|}|\\.{2}|\\:)")

2. Next, we should check if we have the colon expression among already defined lexemes. And indeed, we have the Operator lexeme with the double colon character :: to signify access to a class’s property or a function. We need to make this double colon :: NOT be treated as the GroupDivider lexeme with a single colon : two times.

   
   

   The most reliable solution is to put a negative lookahead (?!\\:) after the single colon expression saying that there shouldn't be a second colon after it:

GroupDivider("(\\[|\\]|\\,|\\{|}|\\.{2}|(\\:(?!\\:)))")

3. To support Upcasting and Downcasting, we need to add as operator to the Operator lexeme:

Operator("(\\+|-|\\*|/{1,2}|%|>=|>|<=|<{1,2}|={1,2}|!=|!|:{2}\\s+new|:{2}|\\(|\\)|(new|and|or|as)(?=\\s|$)(?!_))")

4. Lastly, we put is as a type check (instance of) operator to the Operator lexeme as well:

Operator("(\\+|-|\\*|/{1,2}|%|>=|>|<=|<{1,2}|={1,2}|!=|!|:{2}\\s+new|:{2}|\\(|\\)|(new|and|or|as|is)(?=\\s|$)(?!_))")

We’ve added all the required regex expressions to the TokenType. These changes will be managed by LexicalParser, which will convert source code into tokens and handle them in the following section.

3. Syntax Analysis

In this section, we will convert lexemes received from the lexical analyzer into the final statements following our language rules.

3.1 Class Declaration

Currently, we use the StatementParser to read and transform lexemes into definitions and statements. To parse a class definition, we use the StatementParser#parseClassDefinition() method.

All we are doing here is reading the class name and its arguments within square brackets, and at the end, we build ClassDefinition:

private void parseClassDefinition() {
    // read class definition
    Token name = tokens.next(TokenType.Variable);
    
    List<String> properties = new ArrayList<>();

    if (tokens.peek(TokenType.GroupDivider, "[")) {
        tokens.next(); //skip open square bracket

        while (!tokens.peek(TokenType.GroupDivider, "]")) {
            Token propertyToken = tokens.next(TokenType.Variable);
            properties.add(propertyToken.getValue());

            if (tokens.peek(TokenType.GroupDivider, ","))
                tokens.next();
        }

        tokens.next(TokenType.GroupDivider, "]"); //skip close square bracket
    }

    // read base types
    ...

    // add class definition
    ...
    ClassDefinition classDefinition = new ClassDefinition(name, properties, …);

    // parse constructor statements
    ...
    tokens.next(TokenType.Keyword, "end");
}

For the Derived class, we should read the inherited types and corresponding reference properties.

The base class’s properties and the derived class’s properties can differ, and to store a relation between these properties, we’ll introduce an auxiliary class that will contain the class name and its properties:

package org.example.toylanguage.context.definition;

@RequiredArgsConstructor
@Getter
@EqualsAndHashCode(onlyExplicitlyIncluded = true)
public class ClassDetails {
    @EqualsAndHashCode.Include
    private final String name;
    private final List<String> properties;
}

package org.example.toylanguage.context.definition;

@RequiredArgsConstructor
@Getter
@EqualsAndHashCode(onlyExplicitlyIncluded = true)
public class ClassDefinition implements Definition {
    @EqualsAndHashCode.Include
    private final ClassDetails classDetails;
    private final Set<ClassDetails> baseTypes;
    private final ClassStatement statement;
    private final DefinitionScope definitionScope;
}

Now, let’s fill the inherited classes for our ClassDefinition. We will use LinkedHashSet to keep the order of Base types, which we’ll be using to initialize super constructors in the order defined by a developer:

private void parseClassDefinition() {
    // read class definition
    ...

    // read base types
    Set<ClassDetails> baseTypes = new LinkedHashSet<>();
    if (tokens.peek(TokenType.GroupDivider, ":")) {
        while (tokens.peek(TokenType.GroupDivider, ":", ",")) {
            tokens.next();

            Token baseClassName = tokens.next(TokenType.Variable);
            List<String> baseClassProperties = new ArrayList<>();
            if (tokens.peek(TokenType.GroupDivider, "[")) {
                tokens.next(); //skip open square bracket

                while (!tokens.peek(TokenType.GroupDivider, "]")) {
                    Token baseClassProperty = tokens.next(TokenType.Variable);
                    baseClassProperties.add(baseClassProperty.getValue());

                    if (tokens.peek(TokenType.GroupDivider, ","))
                        tokens.next();
                }

                tokens.next(TokenType.GroupDivider, "]"); //skip close square bracket
            }
            ClassDetails baseClassDetails = new ClassDetails(baseClassName.getValue(), baseClassProperties);
            baseTypes.add(baseClassDetails);
        }
    }


    // add class definition
    ...
    ClassDetails classDetails = new ClassDetails(name.getValue(), properties);
    ClassDefinition classDefinition = new ClassDefinition(classDetails, baseTypes, classStatement, classScope);

    // parse constructor statements
    ...
    tokens.next(TokenType.Keyword, "end");
}

3.2 Class Instance

After we’ve read and saved the Derived class definition, we should provide the ability to create an instance with the defined inherited types. Currently, to create an instance of a class, we use the ClassExpression and ClassValue implementations.

The first one, the ClassExpression, is being used to create a class instance in the ExpressionReader. The second one, the ClassValue, is being created by the ClassExpression during execution and used to access a class property.

Let's begin with the second, ClassValue. When we create a class instance and invoke its constructor statements, we may need to access its properties. Each Derived type can have a different set of properties that do not necessarily correspond to the Base type’s properties.

As the next requirement of our inheritance rules, where we need to provide the cast operator to the Base type, we should make an interface to easily switch between Base types and keep variables of each Base class isolated from variables of the Derived type.

We'll define the Map of relations for the Base types and the Derived type to access the ClassValue by class name:

@Getter
public class ClassValue extends IterableValue<ClassDefinition> {
    private final MemoryScope memoryScope;
    private final Map<String, ClassValue> relations;

    public ClassValue(ClassDefinition definition, MemoryScope memoryScope, Map<String, ClassValue> relations) {
        super(definition);
        this.memoryScope = memoryScope;
        this.relations = relations;
    }
    
    public ClassValue getRelation(String className) {
        return relations.get(className);
    }

    public boolean containsRelation(String className) {
        return relations.containsKey(className);
    }

    ...
}

These relations will be used for Upcasting, Downcasting, and checking object type. To simplify the process of Upcasting and Downcasting, this map will contain the same values for each Base class in the inheritance chain and will allow Upcasting from the bottom Base type to the top Derived type and vice versa.

Next, let’s modify the ClassExpression that we use to create a class instance. Inside it, we define the Map of relations a second time, which will be used to create a ClassValue and be accumulated by every supertype the Derived class has:

@RequiredArgsConstructor
@Getter
public class ClassExpression implements Expression {
    private final String name;
    private final List<? extends Expression> argumentExpressions;
    // Base classes and Derived class available to a class instance
    private final Map<String, ClassValue> relations;

    public ClassExpression(String name, List<Expression> argumentExpressions) {
        this(name, argumentExpressions, new HashMap<>());
    }
}

We should also provide consistency for reference properties. If we modify the Base type’s property, the reference property in the Derived type should also be updated to the same value, and vice versa, if we change the Derived class’s property, the reference property in the Base class should be updated as well:

class A [arg_a]
end

class B [arg_b1, arg_b2]: A [arg_b2]
end

b = new B [ 1, 2 ]
b as A :: arg_a = 3
print b

b :: arg_b2 = 4
print b as A

Output
B [ arg_b1 = 1, arg_b2 = 3 ]
A [ arg_a = 4 ]

This reference consistency can be delegated to Java by introducing a new ValueReference wrapper for the Value, a single instance of which will be used by the Derived type to initialize the reference property in the Base types:

package org.example.toylanguage.context;

/**
 * Wrapper for the Value to keep the properties relation between a Base class and a Derived class
 *
 * <pre>{@code
 * # Declare the Base class A
 * class A [a_value]
 * end
 *
 * # Declare the Derived class B that inherits class A and initializes its `a_value` property with the `b_value` parameter
 * class B [b_value]: A [b_value]
 * end
 *
 * # Create an instance of class B
 * b = new B [ b_value ]
 *
 * # If we change the `b_value` property, the A class's property `a_value` should be updated as well
 * b :: b_value = new_value
 *
 * # a_new_value should contain `new_value`
 * a_new_value = b as A :: a_value
 * }</pre>
 */
@Getter
@Setter
public class ValueReference implements Expression {
    private Value<?> value;

    private ValueReference(Value<?> value) {
        this.value = value;
    }

    public static ValueReference instanceOf(Expression expression) {
        if (expression instanceof ValueReference) {
            // reuse variable
            return (ValueReference) expression;
        } else {
            return new ValueReference(expression.evaluate());
        }
    }

    @Override
    public Value<?> evaluate() {
        return value;
    }
}

Now, let’s initialize the Base classes’ constructors inside the ClassExpression#evaluate(List<Value<?>>) method. This method accepts a list of properties to instantiate the regular classes and the nested ones:

private Value<?> evaluate(List<Value<?>> values) {
    //get class's definition and statement
    ClassDefinition definition = DefinitionContext.getScope().getClass(name);
    ClassStatement classStatement = definition.getStatement();

    //set separate scope
    MemoryScope classScope = new MemoryScope(null);
    MemoryContext.pushScope(classScope);

    try {
        //initialize constructor arguments
        ClassValue classValue = new ClassValue(definition, classScope);
        ClassInstanceContext.pushValue(classValue);
        IntStream.range(0, definition.getProperties().size()).boxed()
                .forEach(i -> MemoryContext.getScope()
                        .setLocal(definition.getProperties().get(i), values.size() > i ? values.get(i) : NullValue.NULL_INSTANCE));

        //execute function body
        DefinitionContext.pushScope(definition.getDefinitionScope());
        try {
            classStatement.execute();
        } finally {
            DefinitionContext.endScope();
        }

        return classValue;
    } finally {
        MemoryContext.endScope();
        ClassInstanceContext.popValue();
    }
}

We will modify the part after we set a separate MemoryScope. First, we need to create an instance of ClassValue, and add it to the relations map:

//set separate scope
MemoryScope classScope = new MemoryScope(null);
MemoryContext.pushScope(classScope);

//initialize constructor arguments
ClassValue classValue = new ClassValue(definition, classScope, relations);
relations.put(name, classValue);

Next, we will convert the Value<?> properties into the ValueReference:

List<ValueReference> valueReferences = values.stream()
    .map(ValueReference::instanceOf)
    .collect(Collectors.toList());

If we instantiate the Derived class’s reference property using ValueReference#instanceOf(Expression), the second time this expression will return the same ValueReference.

After that, we can fill in the missing arguments in case a developer does not provide enough properties defined in the class definition. These absent properties can be set with the NullValue:

// fill the missing properties with NullValue.NULL_INSTANCE
// class A [arg1, arg2]
// new A [arg1] -> new A [arg1, null]
// new A [arg1, arg2, arg3] -> new A [arg1, arg2]
List<ValueReference> valuesToSet = IntStream.range(0, definition.getClassDetails().getProperties().size())
        .boxed()
        .map(i -> values.size() > i ? values.get(i) : ValueReference.instanceOf(NullValue.NULL_INSTANCE))
        .collect(Collectors.toList());

Lastly, for this method, we need to create a ClassExpression for each Base class using the Derived class’s reference properties, and then execute each constructor by calling ClassExpression#evaluate():

//invoke constructors of the base classes
definition.getBaseTypes()
        .stream()
        .map(baseType -> {
            // initialize base class's properties
            // class A [a_arg]
            // class B [b_arg1, b_arg2]: A [b_arg1]
            List<ValueReference> baseClassProperties = baseType.getProperties().stream()
                    .map(t -> definition.getClassDetails().getProperties().indexOf(t))
                    .map(valuesToSet::get)
                    .collect(Collectors.toList());
            return new ClassExpression(baseType.getName(), baseClassProperties, relations);
        })
        .forEach(ClassExpression::evaluate);

With this block of code, we can instantiate each Base class we have in the inheritance chain. When we create an instance of the ClassExpression for the Base class, this Base class will behave like a Derived class, with its own inherited Base types, until we reach the Base class that does not inherit any classes.

After we initialized the Base instances, we can finish initializing the Derived instance by setting its properties with MemoryScope#setLocal(ValueReference) and executing constructor statements:

try {
    ClassInstanceContext.pushValue(classValue);
    IntStream.range(0, definition.getClassDetails().getArguments().size()).boxed()
            .forEach(i -> MemoryContext.getScope()
                    .setLocal(definition.getClassDetails().getArguments().get(i), valuesToSet.get(i)));

    //execute constructor statements
    DefinitionContext.pushScope(definition.getDefinitionScope());
    try {
        classStatement.execute();
    } finally {
        DefinitionContext.endScope();
    }

    return classValue;
} finally {
    MemoryContext.endScope();
    ClassInstanceContext.popValue();
}

With the new ValueReference class as a value wrapper, we need also to update the MemoryScope to be able to set a ValueReference directly and update the Value<?> inside it if we modify the class’ property:

public class MemoryScope {
    private final Map<String, ValueReference> variables;
    private final MemoryScope parent;

    public MemoryScope(MemoryScope parent) {
        this.variables = new HashMap<>();
        this.parent = parent;
    }

    public Value<?> get(String name) {
        ValueReference variable = variables.get(name);
        if (variable != null)
            return variable.getValue();
        else if (parent != null)
            return parent.get(name);
        else
            return NullValue.NULL_INSTANCE;
    }

    public Value<?> getLocal(String name) {
        ValueReference variable = variables.get(name);
        return variable != null ? variable.getValue() : null;
    }

    public void set(String name, Value<?> value) {
        MemoryScope variableScope = findScope(name);
        if (variableScope == null) {
            setLocal(name, value);
        } else {
            variableScope.setLocal(name, value);
        }
    }

    // set variable as a reference
    public void setLocal(String name, ValueReference variable) {
        variables.put(name, variable);
    }

    // update an existent variable
    public void setLocal(String name, Value<?> value) {
        if (variables.containsKey(name)) {
            variables.get(name).setValue(value);
        } else {
            variables.put(name, ValueReference.instanceOf(value));
        }
    }

    private MemoryScope findScope(String name) {
        if (variables.containsKey(name))
            return this;
        return parent == null ? null : parent.findScope(name);
    }
}

3.3 Function

This subsection will cover the function invocation in the inheritance model. Currently, to invoke a function, we use the FunctionExpression class.

We’re only interested in the FunctionExpression#evaluate(ClassValue) method, the one that accepts the ClassValue as a type, which we use to execute a function from:

/**
 * Evaluate class's function
 *
 * @param classValue instance of class where the function is placed in
 */
public Value<?> evaluate(ClassValue classValue) {
    //initialize function arguments
    List<Value<?>> values = argumentExpressions.stream().map(Expression::evaluate).collect(Collectors.toList());

    //get definition and memory scopes from class definition
    ClassDefinition classDefinition = classValue.getValue();
    DefinitionScope classDefinitionScope = classDefinition.getDefinitionScope();
    MemoryScope memoryScope = classValue.getMemoryScope();

    //set class's definition and memory scopes
    DefinitionContext.pushScope(classDefinitionScope);
    MemoryContext.pushScope(memoryScope);
    ClassInstanceContext.pushValue(classValue);

    try {
        //proceed function
        return evaluate(values);
    } finally {
        DefinitionContext.endScope();
        MemoryContext.endScope();
        ClassInstanceContext.popValue();
    }
}

With the inheritance, we may not have a function declared in the Derived class. This function could be available only in one of the Base classes. In the following example, the function action is only available in the definition of the B class.

class A
end

class B
	fun action
	end
end

class C: A, B
end

c = new C
c :: action []

To find the Base class containing the function with name and number of arguments, we will create the following method:

private ClassDefinition findClassDefinitionContainingFunction(ClassDefinition classDefinition, String functionName, int argumentsSize) {
    DefinitionScope definitionScope = classDefinition.getDefinitionScope();
    if (definitionScope.containsFunction(functionName, argumentsSize)) {
        return classDefinition;
    } else {
        for (ClassDetails baseType : classDefinition.getBaseTypes()) {
            ClassDefinition baseTypeDefinition = definitionScope.getClass(baseType.getName());
            ClassDefinition functionClassDefinition = findClassDefinitionContainingFunction(baseTypeDefinition, functionName, argumentsSize);
            if (functionClassDefinition != null)
                return functionClassDefinition;
        }
        return null;
    }
}

With this method and with the earlier defined ClassValue#getRelation(String), we can retrieve the ClassValue instance that we can use to invoke the function. Let’s finish the FunctionExpression#evaluate(ClassValue) implementation:

/**
 * Evaluate class's function
 *
 * @param classValue instance of class where the function is placed in
 */
public Value<?> evaluate(ClassValue classValue) {
    //initialize function arguments
    List<Value<?>> values = argumentExpressions.stream().map(Expression::evaluate).collect(Collectors.toList());

    // find a class containing the function
    ClassDefinition classDefinition = findClassDefinitionForFunction(classValue.getValue(), name, values.size());
    if (classDefinition == null) {
        throw new ExecutionException(String.format("Function is not defined: %s", name));
    }
    DefinitionScope classDefinitionScope = classDefinition.getDefinitionScope();
    ClassValue functionClassValue = classValue.getRelation(classDefinition.getClassDetails().getName());
    MemoryScope memoryScope = functionClassValue.getMemoryScope();

    //set class's definition and memory scopes
    DefinitionContext.pushScope(classDefinitionScope);
    MemoryContext.pushScope(memoryScope);
    ClassInstanceContext.pushValue(functionClassValue);

    try {
        //proceed function
        return evaluate(values);
    } finally {
        DefinitionContext.endScope();
        MemoryContext.endScope();
        ClassInstanceContext.popValue();
    }
}

3.4 Cast Type Operator

In this subsection, we will add support for the cast type as operator. We already defined this expression in the TokenType.Operator lexeme.

We need only to create the BinaryOperatorExpression implementation that will transform the initial ClassValue into the Base or Derived type using the ClassValue#relations map:

package org.example.toylanguage.expression.operator;

/**
 * Cast a class instance from one type to other
 */
public class ClassCastOperator extends BinaryOperatorExpression {
    public ClassCastOperator(Expression left, Expression right) {
        super(left, right);
    }

    @Override
    public Value<?> evaluate() {
        // evaluate expressions
        ClassValue classInstance = (ClassValue) getLeft().evaluate();
        String typeToCastName = ((VariableExpression) getRight()).getName();

        // retrieve class details
        ClassDetails classDetails = classInstance.getValue().getClassDetails();

        // check if the type to cast is different from original
        if (classDetails.getName().equals(typeToCastName)) {
            return classInstance;
        } else {
            // retrieve ClassValue of other type
            return classInstance.getRelation(typeToCastName);
        }
    }
}

And as the last step, we should plug this operator in the Operator enum with the required precedence for this operation:

@RequiredArgsConstructor
@Getter
public enum Operator {
    Not("!", NotOperator.class, 7),
    ClassInstance("new", ClassInstanceOperator.class, 7),
    NestedClassInstance(":{2}\\s+new", NestedClassInstanceOperator.class, 7),
    ClassProperty(":{2}", ClassPropertyOperator.class, 7),
    ClassCast("as", ClassCastOperator.class, 7),
    ...

    private final String character;
    private final Class<? extends OperatorExpression> type;
    private final Integer precedence;
    ...
}

This enum is also built with the regex model and will transform the list of lexemes into the operators’ implementations. The provided precedence will be taken into account with the help of Dijkstra's Two-Stack Algorithm.

Please check out the ExpressionReader implementation and the second part for more explanation.

3.5 Check Type Operator

In this last subsection of syntax analysis, we’ll define the check type operator. The implementation will be similar to the cast operator, which requires creating the OperatorExpression implementation and plugging it into the Operator enum.

The check type operator should return LogicalValue, which stands for a boolean type containing either true or false:

package org.example.toylanguage.expression.operator;

import org.example.toylanguage.exception.ExecutionException;
import org.example.toylanguage.expression.Expression;
import org.example.toylanguage.expression.VariableExpression;
import org.example.toylanguage.expression.value.ClassValue;
import org.example.toylanguage.expression.value.LogicalValue;
import org.example.toylanguage.expression.value.Value;

public class ClassInstanceOfOperator extends BinaryOperatorExpression {
    public ClassInstanceOfOperator(Expression left, Expression right) {
        super(left, right);
    }

    @Override
    public Value<?> evaluate() {
        Value<?> left = getLeft().evaluate();
        // cat = new Cat
        // is_cat_animal = cat is Animal
        if (left instanceof ClassValue && getRight() instanceof VariableExpression) {
            String classType = ((VariableExpression) getRight()).getName();
            return new LogicalValue(((ClassValue) left).containsRelation(classType));
        } else {
            throw new ExecutionException(String.format("Unable to perform `is` operator for the following operands `%s` and `%s`", left, getRight()));
        }
    }
}

@RequiredArgsConstructor
@Getter
public enum Operator {
    Not("!", NotOperator.class, 7),
    ClassInstance("new", ClassInstanceOperator.class, 7),
    NestedClassInstance(":{2}\\s+new", NestedClassInstanceOperator.class, 7),
    ClassProperty(":{2}", ClassPropertyOperator.class, 7),
    ClassCast("as", ClassCastOperator.class, 7),
    ClassInstanceOf("is", ClassInstanceOfOperator.class, 7),
    ...

    private final String character;
    private final Class<? extends OperatorExpression> type;
    private final Integer precedence;
    ...
}

You can create your own operators the same way, by defining the regex expression in the TokenType.Operator lexeme and plugging the OperatorExpression implementation in the Operator enum.

4 Wrap Up

That’s all the modifications we needed to make to implement the inheritance. In this part, we created a simple hybrid inheritance model as one more step toward making a complete programming language.

Here are a few examples you can run and test on your own with RunToyLanguage:

class Animal
    fun action
        print "Animals can run."
    end
end

class Bird
    fun action
        print "Birds can fly."
    end
end

class Parrot: Animal, Bird
    fun action
        this as Bird :: action []
        this as Animal :: action []
        print "Parrots can talk."
    end
end

new Parrot :: action[]

class Add [x, y]
    fun sum
        return "The sum of " + x + " and " + y + " is " + (x + y)
    end
end

class Mul [a, b]
    fun mul
        return "The multiplication of " + a + " and " + b + " is " + a * b
    end
end

class Sub [a, b]
    fun sub
        return "The subtraction of " + a + " and " + b + " is " + (a - b)
    end
end

class Div [m, n]
    fun div
        return "The division of " + m + " and " + n + " is " + m / n
    end
end

class Exp [m, n]
    fun exp
        return "The exponentiation of " + m + " and " + n + " is " + m ** n
    end
end

class Fib [ n ]
    fun fib
        return "The fibonacci number for " + n + " is " + fib [ n ]
    end

    fun fib [ n ]
        if n < 2
            return n
        end
        return fib [ n - 1 ] + fib [ n - 2 ]
    end
end

class Calculator [p, q]: Add [p, q], Sub [q, p],
                         Mul [p, q], Div [q, p],
                         Exp [p, q], Fib [ q ]
end

calc = new Calculator [2, 10]
print calc :: sum []
print calc :: sub []
print calc :: mul []
print calc :: div []
print calc :: exp []
print calc :: fib []

Photo by Uday Awal on Unsplash