This is a long over due follow-up of my original blog about the programming language, Vader, I’m currently developing. Vader Compiler is implemented in C#, and it’s under active development under this repo. My original goal was to develop it into a mature language with it’s own ecosystem, but given the man power and number of other languages available out there, that goal seems unlikely to reach. This does, however, makes me think of another idea for where Vader can go.
Progress
In the last post, I discussed about the compilation process from lexer, to tokens and tokens to expressions. It seems like it’s compilation is just a number of loops that makes us understand more each time we go through the code. Lexer makes strings of code into tokens like if-token or for-token. Tokens tell us what the symbols are, but nothing more. We then go through the list of tokens and parse for expressions and then statements.
Statements are fun, they look more closely resemble what we know as programming languages. A if-statement may contain information about the ‘if’ key word, the condition, the then-statement that we execute if the condition is true and maybe a else statement if the programmer feels like it.
However, statements are still not expressive enough to express what the code is really describing. Let’s take if-statement (as a statement object in the compilation process) , for example, it may include the ‘if’ keyword token, the condition as an expression that can be evaluated into a Boolean, and a body statement, but to execute the if-statement, we don’t really need to know the ‘if’ keyword. We already know it’s an if-statement. What we really need to know is the condition and the body. Well, maybe you think that’s not that different, but this difference also applies to other kinds of statements or expressions. A literal expression normally contains the value and the original text, but we also need to know the type of the value and maybe more. For a binary expression, it may contain the left expression, the operator and the right expression, but we also need to know if the left expression and right expression are compatible with the operator. For example, if the binary expression is ‘3==true’, the binary expression would have no way to know that it’s invalid because it doesn’t know what to expect. In other words, we need more information. We need to go through the loop one more time to generate more information.
Binding
A very standard concept for this is binding. A statement or a expression contains tokens and their respective values. We can then bind them with more information about themselves. For example, a ‘==’ (EqualEqualOperator) in a statement or expression is just a token with the type and the original text, but a bound operator will also include what left or right value the operator expect and what the respective evaluation type would be.
For example, the EqualEqualOperator can accept left and right expressions both being the same type, and the result type will always be boolean. The bitwise operators like the AndOperator can accept or output both numbers or booleans.
internal sealed class BoundBinaryOperator
{
public SyntaxKind SyntaxKind { get; }
public BoundBinaryOperatorKind Kind { get; }
public Type ResultType { get; }
public Type LeftType { get; }
public Type RightType { get; }
private BoundBinaryOperator(SyntaxKind syntaxKind, BoundBinaryOperatorKind kind, Type type)
: this(syntaxKind, kind, type, type, type)
{
}
private BoundBinaryOperator(SyntaxKind syntaxKind, BoundBinaryOperatorKind kind, Type operandType, Type resultType)
: this(syntaxKind, kind, operandType, operandType, resultType)
{
}
private BoundBinaryOperator(SyntaxKind syntaxKind, BoundBinaryOperatorKind kind, Type leftType, Type rightType, Type resultType)
{
RightType = rightType;
LeftType = leftType;
ResultType = resultType;
Kind = kind;
SyntaxKind = syntaxKind;
}
private static BoundBinaryOperator[] _operators =
{
new BoundBinaryOperator(SyntaxKind.PlusToken, BoundBinaryOperatorKind.Addition, typeof(int)),
new BoundBinaryOperator(SyntaxKind.MinusToken, BoundBinaryOperatorKind.Subtraction, typeof(int)),
new BoundBinaryOperator(SyntaxKind.StarToken, BoundBinaryOperatorKind.Multiplication, typeof(int)),
new BoundBinaryOperator(SyntaxKind.SlashToken, BoundBinaryOperatorKind.Division, typeof(int)),
new BoundBinaryOperator(SyntaxKind.AmpersandAmpersandToken, BoundBinaryOperatorKind.LogicalAnd, typeof(bool)),
new BoundBinaryOperator(SyntaxKind.AmpersandToken, BoundBinaryOperatorKind.BitWiseAnd, typeof(bool)),
new BoundBinaryOperator(SyntaxKind.AmpersandToken, BoundBinaryOperatorKind.BitWiseAnd, typeof(int)),
new BoundBinaryOperator(SyntaxKind.PipePipeToken, BoundBinaryOperatorKind.LogicalOr, typeof(bool)),
new BoundBinaryOperator(SyntaxKind.PipeToken, BoundBinaryOperatorKind.BitWiseOr, typeof(bool)),
new BoundBinaryOperator(SyntaxKind.PipeToken, BoundBinaryOperatorKind.BitWiseOr, typeof(int)),
new BoundBinaryOperator(SyntaxKind.CaretToken, BoundBinaryOperatorKind.BitWiseExclusiveOr, typeof(bool)),
new BoundBinaryOperator(SyntaxKind.CaretToken, BoundBinaryOperatorKind.BitWiseExclusiveOr, typeof(int)),
new BoundBinaryOperator(SyntaxKind.EqualEqualToken, BoundBinaryOperatorKind.Equals, typeof(int), typeof(bool)),
new BoundBinaryOperator(SyntaxKind.BangEqualToken, BoundBinaryOperatorKind.NotEquals, typeof(int), typeof(bool)),
new BoundBinaryOperator(SyntaxKind.EqualEqualToken, BoundBinaryOperatorKind.Equals, typeof(bool)),
new BoundBinaryOperator(SyntaxKind.BangEqualToken, BoundBinaryOperatorKind.NotEquals, typeof(bool)),
new BoundBinaryOperator(SyntaxKind.LessToken, BoundBinaryOperatorKind.Less, typeof(int), typeof(bool)),
new BoundBinaryOperator(SyntaxKind.LessOrEqualsToken, BoundBinaryOperatorKind.LessOrEquals, typeof(int), typeof(bool)),
new BoundBinaryOperator(SyntaxKind.GreaterToken, BoundBinaryOperatorKind.Greater, typeof(int), typeof(bool)),
new BoundBinaryOperator(SyntaxKind.GreaterOrEqualsToken, BoundBinaryOperatorKind.GreaterOrEquals, typeof(int), typeof(bool)),
};
public static BoundBinaryOperator Bind(SyntaxKind syntaxKind, Type leftType, Type rightType)
{
foreach (var op in _operators)
{
if (op.SyntaxKind == syntaxKind && op.LeftType == leftType && op.RightType == rightType)
return op;
}
return null;
}
}
What binding gives us is a more information packed representation of our code, and it’s essential to the next part of the compiling process. Now that we know what exactly each blocks are and the their validity, we can start lowering them.
Lowering
Lowering is another standard concept in compilation. It’s where we start thinking about emitting binary instead of evaluating the code. However, lowering is not generating binary, it’s the step before it.
In a high level language like C or Java, there are syntax sugars like the if-statement, for-statement and while-statement, but anyone who learned assembly language knows that they are just glorified go-to-statements with conditions. Lowering is the process to convert these syntax sugars back into go-to-statements. If-statements, for-statements and while-statements will be go-to-statements with labels, and block-statements will be flattened so that at the end, everything will just be a long list of “instructions”.
internal sealed class Lowerer : BoundTreeRewriter
{
private int _labelCount;
private Lowerer()
{}
private LabelSymbel GenerateLabel()
{
var name = $"Label {++_labelCount}";
return new LabelSymbel(name);
}
public static BoundBlockStatement Lower(BoundStatement statement)
{
var lowerer = new Lowerer();
var result = lowerer.RewriteStatement(statement);
return Flatten(result);
}
private static BoundBlockStatement Flatten(BoundStatement statement)
{
var builder = ImmutableArray.CreateBuilder<BoundStatement>();
var stack = new Stack<BoundStatement>();
stack.Push(statement);
while (stack.Count > 0)
{
var current = stack.Pop();
if (current is BoundBlockStatement block)
{
foreach (var s in block.Statements.Reverse())
stack.Push(s);
}
else
{
builder.Add(current);
}
}
return new BoundBlockStatement(builder.ToImmutable());
}
protected override BoundStatement RewriteIfStatement(BoundIfStatement node)
{
if (node.ElseStatement == null)
{
// if <condition>
// <then>
//
// --> becomes
//
// gotoIfFalse <condition> end
// <then>
// end:
var endLabel = GenerateLabel();
var gotoFalse = new BoundConditionalGotoStatement(endLabel, node.Condition, false);
var endLabelStatement = new BoundLabelStatement(endLabel);
var result = new BoundBlockStatement(ImmutableArray.Create<BoundStatement>(gotoFalse, node.ThenStatement, endLabelStatement));
return RewriteStatement(result);
}
else
{
// if <condition>
// <then>
// else
// <else>
//
// --> becomes
//
// gotoIfFalse <condition> else
// <then>
// goto end
// else:
// <else>
// end:
var elseLabel = GenerateLabel();
var endLabel = GenerateLabel();
var gotoFalse = new BoundConditionalGotoStatement(elseLabel, node.Condition, false);
var gotoEndStatement = new BoundGoToStatement(endLabel);
var elseLabelStatement = new BoundLabelStatement(elseLabel);
var endLabelStatement = new BoundLabelStatement(endLabel);
var result = new BoundBlockStatement(ImmutableArray.Create<BoundStatement>(
gotoFalse,
node.ThenStatement,
gotoEndStatement,
elseLabelStatement,
node.ElseStatement,
endLabelStatement
));
return RewriteStatement(result);
}
}
protected override BoundStatement RewriteWhileStatement(BoundWhileStatement node)
{
// while <condition>
// body
//
// --> becomes
//
// goto check
// continue:
// <body>
// check:
// gotoTrue <condition> continue
// end:
var continueLabel = GenerateLabel();
var checkLabel = GenerateLabel();
var endLabel = GenerateLabel();
var gotoLabel = GenerateLabel();
var gotoCheck = new BoundGoToStatement(checkLabel);
var continueLabelStatement = new BoundLabelStatement(continueLabel);
var checkLabelStatement = new BoundLabelStatement(checkLabel);
var ebdLabelStatement = new BoundLabelStatement(endLabel);
var gotoTrue = new BoundConditionalGotoStatement(continueLabel, node.Condition);
var endLabelStatement = new BoundLabelStatement(endLabel);
var result = new BoundBlockStatement(ImmutableArray.Create<BoundStatement>(
gotoCheck,
continueLabelStatement,
node.Body,
checkLabelStatement,
gotoTrue,
endLabelStatement
));
return RewriteStatement(result);
}
protected override BoundStatement RewriteForStatement(BoundForStatement node)
{
//For Statements are now all While Statements
var variableDeclaration = new BoundVariableDeclaration(node.Variable, node.LowerBound);
var variableExpression = new BoundVariableExpression(node.Variable);
var upperBoundSymbol = new VariableSymbol("upperBound", true, typeof(int));
var upperBoundDeclaration = new BoundVariableDeclaration(upperBoundSymbol, node.UpperBound);
var condition = new BoundBinaryExpression(
variableExpression,
BoundBinaryOperator.Bind(SyntaxKind.LessOrEqualsToken, typeof(int), typeof(int)),
new BoundVariableExpression(upperBoundSymbol)
);
var increment = new BoundExpressionStatement(
new BoundAssignmentExpression(
node.Variable,
new BoundBinaryExpression(
variableExpression,
BoundBinaryOperator.Bind(SyntaxKind.PlusToken, typeof(int), typeof(int)),
new BoundLiteralExpression(1)
)
)
);
var whileBody = new BoundBlockStatement(ImmutableArray.Create<BoundStatement>(node.Body, increment));
var whileStatement = new BoundWhileStatement(condition, whileBody);
var result = new BoundBlockStatement(ImmutableArray.Create<BoundStatement>(
variableDeclaration,
upperBoundDeclaration,
whileStatement
));
return RewriteStatement(result);
}
}
I have not yet get into generating binaries, but this step makes it closer than ever.
Use Case
The end game of Vader is an light weight IDE for itself only, but it’s probably it’s where it will stop as a general purpose language. If I have the energy and time to really develop it more, I’d probably do, but I do have another use case for it. One of my many side projects is the chat app. From the original proof of concept built with Meteor to the refactored version 2 built with Express, React, PostgresSQL and TypeScript, I learned how to engineer a chat app with rich feature. However, it’s never a product since it has nothing to distinguish itself from existing chat services. I do have an idea for the chat app, but that required a built-in compiler for running code. I did not foresee myself building a language for real at the time, but this is the best place for Vader.
The idea is a chat app for programmers where they can write snippets of code for controlling aspects of a chat thread. For example, a for loop can help sending a lot of messages. There are more features this built-in compiler can bring, especially with APIs to access data like chat history, contact list, passive message listeners and etc.
The code name for this project is DevChat, and I tried to plan it immediately. However, there are somethings that are in the way. Normally when I try to build a new project, I like to start from a web implementation since it’s fast to implement and native to the backend service, but Vader Compiler is in C# instead of JavaScript. This means whenever I need to run a code snippet, I need to run it in the backend and send the result over to the client. This is somewhat acceptable or even preferred in some situation, but it does limit the ability of running Vader in the browser. As a result, I’ve decided to say goodbye to my religiously beloved framework, React, for the time being.
Blazor
Well, if I’m not using JavaScript, then what am I using? The answer is WebAssembly. It’s a merging technology that allows any language that compiles to WebAssembly to run in the browser. Most, if not all, modern browsers already support this feature. Languages like C++ or Rust can run in the browser in near metal performance, which is a big improvement over JavaScript. However, speed is not what I’m truly after. Moreover, most people think JavaScript is slow because it’s interpreted instead of compiled, but that not true anymore. Modern browsers now only run JavaScript interpreted the first time it runs, then it compiles JS to a common runtime language just like how JVM works. As much performance as WebAssembly brings to the table, it’s not the game changer that some people may have hoped.
What WebAssembly does bring, is the ability to run C# code in the browser, which is a big deal for this project. The framework for building SPA in C# is called Blazor, and it’s part of .NET Core. This means that Blazor has access to the rich ecosystem in Nuget, and I can include my compiler code in the client side project.
As suitable as Blazor is to this project, it’s still a new framework to me and to the world even. Diving into it with a complicated app service like DevChat is not wise. Engineering mistakes can easily be made, so I decided to do some simply CRUD first to get myself familiarized with the framework before moving on. As a result, I decided to rebuild another one of my side project Jagra Task Manager using Blazor. The first version of Jagra was built using React and Meteor. When I out grew Meteor and non-TypeScript projects, I picked up ASP.NET Core and React with TypeScript for version 2. Since the backend for the Blazor version will also be in ASP.NET Core, I can reuse bunch of the code, which is always welcome.
The learning of Blazor and journey of rebuilding Jagra will also be documented in a blog post later.
Closing
Vader is growing strong, and I have found a home for it. Building everything in C# means I can focus on language feature and business logic instead of dealing with compatibility and compiling errors all day. This is not the best home for a programming language, but it’s a nice one. I feel like it’s sort of a right direction for it as well since the world today are seeing more and more apps with plug-ins and mini-apps that call themselves a platform instead of an app. I do feel like making a chat service with rich extensibility is really interesting. Let’s see how far this one goes.
Enjoy my content? Buy me a coffee.
I regularly post blogs about programming, film or technology in general. If you wish to see more content like this, feel free to support me with a cup of coffee.
$2.99
nzlog 