Design Patterns - Compiler Case Study - Hands-on Examples

Compiler Case Study -
Design Patterns in C#
Ganesh Samarthyam
ganesh@codeops.tech

Design Patterns - Introduction

“Applying design principles is the key to creating
high-quality software!”
Architectural principles:
Axis, symmetry, rhythm, datum, hierarchy, transformation

How to Apply Principles in Practice?
Design principles
Code
How to bridge
the gap?

What are Smells?
“Smells'are'certain'structures'
in'the'code'that'suggest'
(some4mes'they'scream'for)'
the'possibility'of'refactoring.”''

What is Refactoring?
Refactoring (noun): a change
made to the internal structure of
software to make it easier to
understand and cheaper to
modify without changing its
observable behavior
Refactor (verb): to restructure
software by applying a series
of refactorings without
changing its observable
behavior

What are Design Patterns?
recurrent solutions
to common
design problems
Pattern Name
Problem
Solution
Consequences

Principles to Patterns
Expr expr = Addition.Make(
Multiplication.Make(
Constant.Make(10),
Constant.Make(20)),
Constant.Make(10));
Expr expr = new ExprBuilder().Const(10).Mult(20).Plus(30).Build();
Encapsulate object creation
Builder pattern

Why Care About Patterns?
❖ Patterns capture expert
knowledge in the form of
proven reusable solutions
❖ Better to reuse proven
solutions than to “re-invent”
the wheel
❖ When used correctly, patterns
positively inﬂuence software
quality
❖ Creates maintainable,
extensible, and reusable code

Design Patterns - Catalog
Source: “Design Patterns: Elements of Reusable Object-Oriented Software”, Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, Addison-Wesley,1994

Design Patterns - Catalog
Creational
Deals with controlled
object creation
Factory method, for
example
Structural
Deals with
composition of classes
or objects
Composite, for example
Behavioral
Deals with interaction
between objects/
classes and
distribution of
responsibility
Strategy, for example

3 Principles Behind Patterns
Design'principles'
behind'pa0erns'
Program'to'an'
interface,'not'to'an'
implementa7on''
Favor'object'
composi7on''
over'inheritance'
Encapsulate'what'
varies'

Case Study Overview
❖ Smelly code segments (specially if-else based on types
and switch statements) used ﬁrst
❖ They are “refactored” using design patterns
❖ The case study shows code-snippets; compilable, self-
contained source code ﬁles shared with you

What You Need to Know
❖ Understand essential object oriented constructs such as runtime
polymorphism (virtual functions), and principles (such as
encapsulation)
❖ Know essential C# language features - classes, inheritance, etc
❖ Data structures and algorithms (especially binary trees, tree
traversals, and stacks)
❖ NO background in compilers needed
❖ Extremely simpliﬁed compiler code example; purposefully
done to make best use of this case study

Simple Expression Tree Example
+
* 30
10 20
Expression: ((10 * 20) + 30)

Post-order Traversal: Simulating Code Gen
10 20 * 30 +
post-order
traversal
result
+
* 30
10 20

Front-end
Intermediate code (CIL, Java bytecodes, …)
Interpreter (Virtual
Machine)

Using Stack for Evaluation
Initial
empty
10
push 10
10
push 20
20
200
perform
10 * 20
push
200
200
push 30
30
230
perform
200 +
30
push
230
End
result
= 230
10 20 * 30 +

Mnemonic Names in Java and .NET
10 20 * 30 +
push 10
push 20
multiply
push 30
add
.NET CIL Instructions Java Bytecode Instructions
ldc.i4.s 0x0a
ldc.i4.s 0x14
mul
ldc.i4.s 0x1e
add
(ldc => load constant ;
i4 => integer of 32 bits;
s => signed)
bipush 10
bipush 20
imul
bipush 30
iadd
(bipush stands for “byte integer push”)

Hands-on Exercise
Use the ildasm tool to disassemble the Expr.cs code
// Expr.cs
using System;
class Test {
    public static void Main() {
        int a = 10, b = 20, c = 30;
        int r = ((a * b) + c);
        Console.WriteLine(r);
    }
}

((10 * 20) + 30)Source Code
C#
Compiler
.NET CLR
(Common
Language
Runtime)
ldc.i4.s 0x0a
ldc.i4.s 0x14
mul
ldc.i4.s 0x1e
add
+
* 30
10 20

Facade Pattern
Provide a uniﬁed interface to a set of interfaces in a subsystem. Facade deﬁnes a
higher-level interface that makes the subsystem easier to use.

Facade Pattern in Compilers
“The Compiler class acts as a facade: It offers clients a single,
simple interface to the compiler subsystem.”

Facade Pattern in Compilers
public virtual void Compile(StreamReader input, BytecodeStream output) {
Scanner scanner = new Scanner(input);
var builder = new ProgramNodeBuilder();
Parser parser = new Parser();
parser.Parse(scanner, builder);
RISCCodeGenerator generator = new RISCCodeGenerator(output);
ProgramNode parseTree = builder.GetRootNode();
parseTree.Traverse(generator);
}

Procedural (conditional) Code
How to get rid of
conditional statements?
public void GenCode()
{
if (_left == null && _right == null)
{
Console.WriteLine("ldc.i4.s " + _value);
}
else
{
// its an intermediate node
_left.GenCode();
_right.GenCode();
switch (_value)
{
case "+":
Console.WriteLine("add");
break;
case "-":
Console.WriteLine("sub");
break;
case "*":
Console.WriteLine("mul");
break;
case "/":
Console.WriteLine("div");
break;
default:
Console.WriteLine("Not implemented yet!");
break;
}
}
}

Hands-on Exercise
Refactor the “../Composite/Before/Compiler.cs” to
get rid of conditional statements and use runtime
polymorphism instead

Hands-on Exercise
internal abstract class Expr
{
public abstract void GenCode();
}
internal class Constant : Expr
{
private readonly int _val;
public Constant(int val)
{
_val = val;
}
public override void GenCode()
{
Console.WriteLine("ldc.i4.s " + _val);
}
}
internal class BinaryExpr : Expr
{
private readonly Expr _left;
private readonly Expr _right;
public BinaryExpr(Expr arg1, Expr arg2)
{
_left = arg1;
_right = arg2;
}
{
_left.GenCode();
_right.GenCode();
}
}
internal class Plus : BinaryExpr
{
public Plus(Expr arg1, Expr arg2) : base(arg1, arg2)
{
}
{
base.GenCode();
}
}

Composite Pattern

Composite Pattern: Discussion
❖ There are many situations where
a group of components form
larger components
❖ Simplistic approach: Make
container component contain
primitive ones
❖ Problem: Code has to treat
container and primitive
components differently
Compose objects into tree structures to represent part-whole hierarchies. Composite
lets client treat individual objects and compositions of objects uniformly.
❖ Perform recursive
composition of
components
❖ Clients don’t have to
treat container and
primitive components
differently

BTW, Did You Observe?
// ((10 * 20) + 30)
var expr = new Expr(
new Expr(
new Expr(null, "10", null), "*", new Expr(null, "20", null)),
"+",
new Expr(null, "30", null));
expr.GenCode();
// ((10 * 20) + 10)
Expr expr = new Plus(
new Multiply(
new Constant(10),
new Constant(20)),
new Constant(30));
expr.GenCode();

Hands-on Exercise
function interpret(node: binary expression tree)
| if node is a leaf then
return (node.value)
| if node is binary operator op then
return interpret(node.left) op interpret(node.right)
Rewrite the code to “evaluate” the expression instead
of generating the code - here is the “pseudo-code”

Solution
{
public Constant(int arg)
{
_val = arg;
}
public override int Interpret()
{
return _val;
}
}
internal class Plus : Expr
{
private readonly Expr _left;
private readonly Expr _right;
public Plus(Expr arg1, Expr arg2)
{
_left = arg1;
_right = arg2;
}
public override int Interpret()
{
return _left.Interpret() + _right.Interpret();
}
}

Register-Based Instructions (x86)
movl $10, -8(%rbp)
movl $20, -12(%rbp)
movl $30, -16(%rbp)
movl -8(%rbp), %eax
imull -12(%rbp), %eax
addl -16(%rbp), %eax
popq %rbp
retq
int main() {
int a = 10;
int b = 20;
int c = 30;
return ((a * b) + c);
}
cc -S expr.c

Register-Based Instructions (Android)
((a * b) + c);
javac -source 1.7 -target 1.7 expr.java
dx --dex --output=expr.dex expr.class
dexdump -d expr.dex
const/16 v1, #int 10 // #a
const/16 v2, #int 20 // #14
const/16 v3, #int 30 // #1e
mul-int v0, v1, v2
add-int/2addr v0, v3
return v0

Hands-on Exercise
Generate register-based instructions for the given
expression ((10 * 20) + 30)
You can generate for an imaginary machine (i.e., a
virtual machine like Dalvik/Android) or a real-
machine (like x86-64)

Solution
internal class Register
{
private readonly int _index;
private Register(int index)
{
_index = index;
}
public static Register GetRegister(int index)
{
return new Register(index);
}
// FreeRegister to be implemented
// not implemented for now for the sake of simplicity
public int GetIndex()
{
return _index;
}
}

Solution
abstract class Expr {
public abstract Register GenCode();
}
class Constant : Expr {
int val;
public Constant(int arg) {
val = arg;
}
public override Register GenCode() {
Register targetRegister = RegisterAllocator.GetNextRegister();
Console.WriteLine("const/16 v{0}, #int {1}", targetRegister.GetIndex(), val);
return targetRegister;
}
}
class Plus : Expr {
private Expr left, right;
public Plus(Expr arg1, Expr arg2) {
left = arg1;
right = arg2;
}
public override Register GenCode() {
Register firstRegister = left.GenCode();
Register secondRegister = right.GenCode();
Register targetRegister = RegisterAllocator.GetNextRegister();
Console.WriteLine("add-int v{0}, v{1}, v{2}", targetRegister.GetIndex(), firstRegister.GetIndex(),
secondRegister.GetIndex());
return targetRegister;
}
}

Solution
((10 + 20) + 30);
Assuming inﬁnite registers from v0,
with target register as the ﬁrst argument,
here is the mnemonic code generated for our
imaginary (i.e., virtual) machine
const/16 v0, #int 10
add-int v2, v0, v1
add-int v4, v2, v3

How to Improve the Tree Creation?
var expr = Addition.Make(
Constant.Make(10),
Constant.Make(20)),
Constant.Make(10));
Expr expr = new Plus(
new Multiply(
new Constant(10),
new Constant(20)),
new Constant(30));

Hands-on Exercise: Solution
{
private Constant(int val)
{
_val = val;
}
public static Constant Make(int arg)
{
return new Constant(arg);
}
{
}
}
{
{
_val = val;
}
{
}
}

Factory Method Pattern: Structure

Factory Method Pattern: Discussion
❖ A class cannot anticipate the
class of objects it must create
❖ A class wants its subclasses to
specify the objects it creates
Deﬁne an interface for creating an object, but let subclasses decide which class to
instantiate. Factory method lets a class defer instantiation to subclasses.
❖ Delegate the responsibility
to one of the several helper
subclasses
❖ Also, localize the
knowledge of which
subclass is the delegate

Scenario
{
{
_val = val;
}
{
}
{
}
}
For expressions like ((10 * 20)
+ 10), why should we create
different Constant objects?
Can we reuse them?

Hands-on Exercise
Improve this code to reuse immutable objects (for the
ones with the same values) instead of creating
duplicate objects.
{
}

{
private static readonly
Dictionary<int, Constant> Pool = new Dictionary<int, Constant>();
{
_val = val;
}
{
if (!Pool.ContainsKey(arg)) Pool[arg] = new Constant(arg);
return Pool[arg];
}
{
}
}

Flyweight Pattern: Structure

Flyweight Pattern: Discussion
❖ When an application uses a
large number of small objects,
it can be expensive
❖ How to share objects at
granular level without
prohibitive cost?
Use sharing to support large numbers of ﬁne-grained objects efﬁciently
❖ When it is possible to share
objects (i.e., objects don't
depend on identity)
❖ When object’s value
remain the same
irrespective of the contexts
- they can be shared
❖ Share the commonly used
objects in a pool

Scenario
// ((10 * 20) + 10)
Constant.Make(10),
Constant.Make(20)),
Constant.Make(10));
expr.GenCode();
This code still sucks - if the
expression becomes more
complex, can you really read
it? Can we simplify this?

Hands-on Exercise
Improve this code to use “builder pattern”.
// ((10 * 20) + 10)
Constant.Make(10),
Constant.Make(20)),
Constant.Make(10));
expr.GenCode();
var expr = new ExprBuilder().Const(10).Mult(20).Plus(30).Build();

internal class ExprBuilder
{
private Expr _expr;
public ExprBuilder Const(int arg)
{
_expr = Constant.Make(arg);
return this;
}
public ExprBuilder Plus(int arg)
{
_expr = new Addition(_expr, Constant.Make(arg));
return this;
}
public ExprBuilder Mult(int arg)
{
_expr = new Multiplication(_expr, Constant.Make(arg));
return this;
}
public Expr Build()
{
return _expr;
}
}

Builder Pattern: Structure

Builder Pattern: Discussion
❖ Creating or assembling a
complex object can be tedious
Separate the construction of a complex object from its representation so that the same
construction process can create different representations.
❖ Make the algorithm for
creating a complex object
independent of parts that
make up the object and
how they are assembled
❖ The construction process
allows different
representations for the
object that is constructed

Scenario
Provide the ability to traverse
the aggregate structure
without exposing
implementation details (also
use iteration instead of
recursion)
{
{
_val = val;
}
{
}
}
internal class Plus : BinaryExpr
{
public Plus(Expr arg1, Expr arg2) : base(arg1, arg2)
{
}
{
base.GenCode();
}
}

Hands-on Exercise
Traverse the expression tree using “external” iteration
{
base.GenCode();
}

internal class ExprIterator
{
public static IEnumerable<Expr> Traverse(Expr node)
{
if (node != null)
{
foreach (var left in Traverse(node.GetLeft())) yield return left;
foreach (var right in Traverse(node.GetRight())) yield return right;
yield return node;
}
}
}
foreach (var node in ExprIterator.Traverse(expr))
node.GenCode();

Iterator Pattern: Structure

Iterator Pattern: Discussion
❖ How to provide a way to
traverse an aggregate structure
in different ways, but without
exposing its implementation
details?
Provide a way to access the elements of an aggregate object sequentially without
exposing its underlying representation.
❖ Take the responsibility for
access and traversal out of
the list object and put it
into an iterator object
❖ Let the iterator keep track
of the element visited,
traversal order, etc

Scenario
How to separate:
a) code generation logic
from node types?
b) how to support different
target types?
class Plus extends Expr {
left = arg1;
right = arg2;
}
public void genCode() {
left.genCode();
right.genCode();
if(t == Target.JVM) {
System.out.println("iadd");
}
else { // DOTNET
System.out.println("add");
}
}
}

Hands-on Exercise
Refactor this code to remove the if-else condition check
(explicit type-checking code) and use runtime
polymorphism instead
if(t == Target.JVM) {
System.out.println("iadd");
}
else { // DOTNET
}

Hands-on Exercise
internal abstract class Target
{
public abstract void GenCode(Constant constant);
public abstract void GenCode(Plus plus);
public abstract void GenCode(Mult mult);
}
internal class JvmTarget : Target
{
public override void GenCode(Constant constant)
{
Console.WriteLine("bipush " + constant.GetValue());
}
public override void GenCode(Plus plus)
{
Console.WriteLine("iadd");
}
public override void GenCode(Mult mult)
{
Console.WriteLine("imul");
}
}

Strategy Pattern: Structure

Strategy Pattern: Discussion
❖ Useful when there is a set of
related algorithms and a client
object needs to be able to
dynamically pick and choose
an algorithm that suits its
current need
Deﬁnes a family of algorithms, encapsulates each one, and makes
them interchangeable. Strategy lets the algorithm vary
independently from clients that use it
❖ The implementation of each of the
algorithms is kept in a separate
class referred to as a strategy.
❖ An object that uses a Strategy
object is referred to as a context
object.
❖ Changing the behavior of a
Context object is a matter of
changing its Strategy object to the
one that implements the required
algorithm

Solution Using Visitor pattern
class Plus extends Expr {
left = arg1;
right = arg2;
}
public Expr getLeft() {
return left;
}
public Expr getRight() {
return right;
}
public void accept(Visitor v) {
v.visit(this);
}
}
class DOTNETVisitor extends Visitor {
public void visit(Constant arg) {
System.out.println("ldarg " + arg.getVal());
}
public void visit(Plus plus) {
genCode(plus.getLeft());
genCode(plus.getRight());
}
public void visit(Sub sub) {
genCode(sub.getLeft());
genCode(sub.getRight());
System.out.println("sub");
}
public void genCode(Expr expr) {
expr.accept(this);
}
}

Visitor Pattern: Structure

Visitor Pattern: Call Sequence

Visitor Pattern: Discussion
❖ Many distinct and unrelated
operations need to be
performed on objects in an
object structure, and you want
to avoid “polluting” their
classes with these operations
Represent an operation to be performed on the elements of an object structure.
Visitor lets you deﬁne a new operation without changing the classes of the
elements on which it operations
❖ Create two class
hierarchies:
❖ One for the elements
being operated on
❖ One for the visitors that
deﬁne operations on the
elements

Procedural (conditional) Code
How to get rid of
conditional statements?
internal class Interpreter
{
private static readonly Stack<int> ExecutionStack = new Stack<int>();
private static int Interpret(byte[] byteCodes)
{
var pc = 0;
while (pc < byteCodes.Length)
switch (byteCodes[pc++])
{
case (byte) BYTECODE.ADD:
ExecutionStack.Push(ExecutionStack.Pop() + ExecutionStack.Pop());
break;
case (byte) BYTECODE.LDCI4S:
ExecutionStack.Push(byteCodes[pc++]);
break;
}
return ExecutionStack.Pop();
}
// rest of the code elided ...
}

Hands-on Exercise
Refactor this code to remove the switch statements and
use runtime polymorphism instead
switch (byteCodes[pc++])
{
case (byte) BYTECODE.ADD:
ExecutionStack.Push(ExecutionStack.Pop() + ExecutionStack.Pop());
break;
case (byte) BYTECODE.LDCI4S:
ExecutionStack.Push(byteCodes[pc++]);
break;
}

Command Pattern: Solution
internal class Interpreter
{
private readonly Stack<int> _evalStack = new Stack<int>();
public int Interpret(ByteCode[] byteCodes)
{
foreach (var byteCode in byteCodes) byteCode.Exec(_evalStack);
return _evalStack.Pop();
}
}
internal abstract class ByteCode
{
public abstract void Exec(Stack<int> evalStack);
}
internal class ADD : ByteCode
{
public override void Exec(Stack<int> evalStack)
{
var lval = evalStack.Pop();
var rval = evalStack.Pop();
evalStack.Push(rval + lval);
}
}

Command Pattern: Structure

Command Pattern: Discussion
❖ Want to issue requests or
execute commands without
knowing anything about the
operation being requested or
the receiver of the request
Encapsulate a request as an object, thereby letting you parameterize clients with
different requests, queue or log requests, and support undoable operations.
❖ Parameterize objects by an
action to perform, with a
common method such as
Execute
❖ Can be useful to specify,
queue, and execute
requests at different times;
also to support undo or
logging

Patterns Discussed in this Case-Study
✓ Facade
✓ Composite
✓ Factory method
✓ Flyweight
✓ Builder
✓ Iterator pattern
✓ Strategy
✓ Visitor
✓ Command

BTW, What Architecture Style is it?
Lexical Analysis
Parsing
Semantic Analysis
Program ﬁle
Intermediate Code
Generation
Optimization
Native Code
Generation
Native assembly/machine code
Token stream
AST (Abstract Syntax Tree)
Attributed tree/
augmented syntax tree
Intermediate code
Optimized
intermediate code

Its “pipe-and-filter” Style!
sediment
pre-
carbon
ultra-ﬁlter
post-
carbon
Filtered
water
Real-world “pipes and ﬁlters”

Pattern Oriented Software Architecture (POSA)

ganesh@codeops.tech @GSamarthyam
www.codeops.tech slideshare.net/sgganesh
+91 98801 64463 bit.ly/sgganesh

Design Patterns - Compiler Case Study - Hands-on Examples

Recommended

More Related Content

What's hot (20)

Similar to Design Patterns - Compiler Case Study - Hands-on Examples (20)

More from Ganesh Samarthyam (20)

Recently uploaded (20)

Design Patterns - Compiler Case Study - Hands-on Examples