HOME_EXAM.md

Home Exam D7050E

Your repo

• Link to your repo here: https://gitlab.henriktjader.com/soderda/d7050e_2020/-/tree/home_exam

Your syntax

• Give an as complete as possible EBNF grammar for your language.

Program

    : Func Program
    | Func
    ;

Func

    : "fn" Id Params "->" Type Block
    | "fn" Id Params Block
    ; 

Params

    : "()"
    | "(" (Param, ",")+ ")"
    ;

Param

    : "mut" Id ":" Type
    | Id ":" Type
    ;

Block

    : "{" StmtSeq* Stmt "}"
    | "{" StmtSeq* "}"
    ;

StmtSeq

    : ";"
    | Stmt ";"
    | StmtBlock
    ;

Stmt

    : "let" "mut" Id ":" Type "=" Expr
    : "let" "mut" Id "=" Expr
    : "let" "mut" Id ":" Type
    : "let" "mut" Id
    : "let" Id ":" Type "=" Expr
    : "let" Id "=" Expr
    : "let" Id ":" Type
    : "let" Id
    : Expr "=" Expr
    : Expr1
    ;

StmtBlock

    : "while" Expr Block
    | "if" Expr Block "else" Block
    | "if" Expr Block 
    | Block
    ;

Expr

    : ExprBlock
    | Expr1
    ;

ExprBlock

    : "if" Expr Block "else" Block
    | Block
    ;

Expr1

    : Expr1 LoCode Expr2
    | Expr1 ArCode Expr2
    | Expr2
    ;

Expr2

    : Expr2 FactorCode Lit
    | Lit
    ;

Lit

    : Id Exprs
    | ArCode Lit
    | "!" Lit
    | Bool
    | Num
    | Id
    | "&" Lit
    | "&mut" Lit
    | "*" Lit
    | "(" Expr ")"
    ;

Exprs

    : "()"
    | "(" (Expr1 "," )+ ")"
    ;

ArCode

    : "+"
    | "-"
    ;

FactorCode

    : "*"
    | "/"
    ;

LoCode

    : "&&"
    | "||"
    | "=="
    | "!="
    | ">"
    | "<"
    | ">="
    | "<="
    ;

Type

    : "bool"
    | "i32"
    | "()"
    | "&" Type
    | "&mut" Type
    ;

Bool

    : "true"
    | "false"
    ;

Num

    : "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 

Id

    : (LowerL | UpperL | "_")+ (LetterLower | LetterUpper | Num | "_")*
    ;

LowerL

    : "a" | "b" | "c" | "d" | "e" | "f" | "g" 
    | "h" | "i" | "j" | "k" | "l" | "m" | "n"
    | "o" | "p" | "q" | "r" | "s" | "t" | "u"
    | "v" | "w" | "x" | "y" | "z" 

UpperL

    : "A" | "B" | "C" | "D" | "E" | "F" | "G"
    | "H" | "I" | "J" | "K" | "L" | "M" | "N"
    | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
    | "V" | "W" | "X" | "Y" | "Z" |

• Give an example that showcases all rules of your EBNF. The program should "do" something as used in the next exercise.
• For your implementation, show that your compiler successfully accepts the input program. Showcase of EBNF:

Accpeted code

    fn func(x:i32, y:i32) -> i32 {
        x+y
    }
    
    fn test() -> bool {
        let mut a = 3;
        let b = &mut a;
        *b = 0;
    
        while a < 10 {
            *b = func(*b, 1);
        }
    
        let c = a / 3;
        if (c > 0) {
            true
        } 
        else {
            false
        }
    }
    
    fn main() {
        test();
    }

• Give a set of examples that are syntactically illegal, and rejected by your compiler.

Bad code

Different kinds of syntax errors

f func(x:i32, y:i32) -> i32 {
    x-y
}

lte a = 1;

mut let a = 0;
wihle a < 10 {
    // do something
}

Mixed positions

let a mut:i32 = 0;

Not yet implemented

fn func(){
    fn func2(){
        fn func3(){
            //...
        }
    }
}

• Compare your solution to the requirements (as stated in the README.md). What are your contributions to the implementation.

Our syntax support the most basic subset of Rust:

• Primitive types such as i32 and boolean
• Functions with the primitive return types
• let, if, if else, while, assign
• Precedence of operands by dividing them into arithmetic, conditional and logical operands. This is because of left to right properties
• Possbility for ArCode (addition and subtraction) to have precedence over FactorCode(multiplication and division) by parenthesized precedence

Future implementation:

• Better error handling with location information
• More types
• Nestled functions
• Global variables
• Pretty printing

Your semantics

• Give a (simplified) Structural Operational Semantics (SOS) for your language. You don't need to detail rules that are similar (follow the same pattern). Regarding variable environment (store) you may omit details as long as the presentation is easy to follow.

• Explain (in text) what an interpretation of your example should produce, do that by dry running your given example step by step. Relate back to the SOS rules. You may skip repetitions

Symbols:

• σ, state
• σ', changed state
• →, evaluates
• c, command
• v, variable
• mv, mutable variable
• e, expression

Expression can be either a

• b, boolean
• n, number
• f, function

Command sequence

$$\frac{<c_1,σ> → σ' <c_2,σ'> → σ''}{<c_1;c_2,σ> → σ''}$$

let a = 1;
let b = 2;

Operands for integer expressions

$$\frac{<e_1,σ> → <n_1, σ'> <e_2, σ'> → <n_2, σ''>}{<e_1 - e2, σ> → <n_1 \text{ sub } n_2, σ''>}$$

Above is a subtraction operation of two integers, following integer expressions can be described in the same way:

• +, Addition
• *, Multiplication
• /, Division
• ">", Greater than
• ">=", Greater than or equals
• "<", Less than
• "<=", Less than or equals
• "==", Equal
• "!=", Not equal

(3+5)*(4-2);
5 >= 2;
2 == 2;

Operands for boolean expressions

$$\frac{<e_1,σ> → <b_1, σ'> <e_2, σ> → <b_2, σ''>}{<e_1 == e_2, σ> → <b_1 \text{ equal } b_2, σ''>}$$

Above is an equals operation of two expessions, following boolean expressions can be described in the same way:

• "!=", Not equal
• "&&", And
• "||", Or

false != true;
true || false;

Reference and Dereference

$$\frac{<e,σ> → v}{<\&e,σ> → \text{ ref } v}$$

A reference to some expression

&a;

$$\frac{<e,σ> → mv}{<\&\text{ mut }e,σ> → \text{ ref } mv}$$

A mutable reference to some expression

&mut a;

$$\frac{<e,σ> → \text{ ref } mv}{<*e,σ> → mv}$$

Dereference of a referenced expression

*a;

Function call expression

$$\frac{<e_1, σ> → <n_1, σ^1> ... <e_n, σ^{n-1}> → <n_n, σ^n> <f_{call}, σ^n[p_1=n_1, ..., p_n=n_n]> → <n, σ'>}{<f(e_1, ..., e_n), σ> → <n, σ'>}$$

fn func() -> i32 {
    1+3
}

fn main() {
    let a = func();
}

Let expression

$$\frac{<e, σ> → <n, σ'>}{<v = e,σ> → σ'[v=n]}$$

Where the expression also can be a boolean or function.

let a = 2;

Assign expression

$$\frac{<e, σ> → n}{<e, σ> → σ'[mv=n]}$$

Where the expression also can be a boolean or function.

a = 0;

If true/false expression

$$\frac{<b, σ> → true <c_1, σ> → σ'}{<\text{if } b \text{ then }c_1 \text{ else } c_2,σ> → σ'}$$

$$\frac{<b, σ> → false <c_2, σ> → σ''}{<\text{if } b \text{ then }c_1 \text{ else } c_2,σ> → σ''}$$

if 3 > 5 {
    func();
}
else {
    anotherfunc();
}

While expression

$$\frac{<b, σ> → true <c, σ> → σ' <\text{while } b \text{ do } c, σ'> → σ''}{<\text{while } b \text{ do } c, σ> → σ''}$$

$$\frac{<b, σ> → false}{<\text{while } b \text{ do } c, σ> → σ}$$

let mut a = 0;
while a < 10 {
    // something that should loop 10 times
    a = a + 1;
}

• For your implementation, give a program (or set of test programs) that cover all the semantics of your language that you have successfully implemented. (Maybe a subset of the input language accepted by the grammar.)

fn func(x:i32, y:i32) -> i32 {
        x+y
    }
    
    fn test() -> bool {
        let mut a = 3;
        let b = &mut a;
        *b = 0;
    
        while a < 10 {
            *b = func(*b, 1);
        }
    
        let c = a / 3;
        if (c > 0) {
            true
        } 
        else {
            false
        }
    }
    
    fn main() {
        test();
    }

Your type checker

• Give a simplified set of Type Checking Rules for your language (those rules look very much like the SOS rules, but over types not values). Also here you don't need to detail rules that are similar (follow the same pattern).
• Demonstrate each "type rule" by an example. You may use one or several "programs" to showcase where rules successfully apply.
• For your implementation, give a set of programs demonstrating that ill-typed programs are rejected, connect back to the Type Checking Rules to argue why these are illegal and thus should be rejected.

Symbols:

• σ, type state
• σ', changed type state
• →, evaluates
• c, command
• v, variable
• mv, mutable variable
• e, expression
• t, type

Expression can be either a

• b, boolean
• n, number
• f, function

Types

• i32
• bool
• ()
• &t
• *t
• () -Unknown

Integer type operands

$$\frac{<e_1,σ> → \text{i32} <e_2, σ> → \text{i32}}{<e_1 - e2, σ> → \text{i32}}$$

Above is a subtraction operation of two integers, these will evaluate to i32. Following operands can also be used:

• +, Addition
• *, Multiplication
• /, Division

(3+5)*(4-2);
1 / false; // Type missmatch

Boolean type operands

\frac{<e_1,σ> → \text{bool} <e_2, σ> → \text{bool}}{<e_1 != e2, σ> → \text{bool}}

Above is a not equals operation of two expessions resulting in a bool, following boolean expressions can be described in the same way:

• "==", Equal
• "&&", And
• "||", Or

These operands can also be used with the type i32 as follows:

• ">", Greater than
• ">=", Greater than or equals
• "<", Less than
• "<=", Less than or equals
• "==", Equal
• "!=", Not equal

\frac{<e_1,σ> → \text{i32} <e_2, σ> → \text{i32}}{<e_1 <= e2, σ> → \text{bool}}

true != false;
3 < 2;
false == 5; // Type missmatch
false < 2; // Type missmatch

Reference and Dereference

\frac{<e,σ> → \&t}{<*e,σ> → t}

\frac{<e,σ> → \&\text{mut } t}{<*e,σ> → \text{mut} t}

\frac{<*e,σ> → t}{<e,σ> → \&t}

let a = 0;
let b = &a;
let c = *b;
let d:bool = *b; // <-- Type missmatch

Function call

\frac{<e_1, σ> → <t_1, σ^1> ... <e_n, σ^{n-1}> → <t_n, σ^n> <f_{call}, σ^n[p_1=t_1, ..., p_n=t_n]> → <t_{res}, σ'>}{<f(e_1, ..., e_n), σ> → <f_t, σ'>}

fn example1() -> i32 {
    1+3     // This is okay return type
}

fn example2() -> i32 {
    true    // This is a type missmatch with what type is expected to return
}

Let expression

\frac{<e, σ> → t}{<{/text{let } v = e,σ> → <(), σ[v=t]>}

let a:i32 = 1;
let b:bool = 1; // Type missmatch

Assign expression

\frac{<v, σ> → \text{mut }t <e, σ> → t}{<v=t, σ>}

let mut a:bool = false;
a = 0; // Type missmatch
let b:i32 = 1;
b = false; // Non mutable

If true/false expression

\frac{<e, σ> → bool <c_1, σ> → t <c_2, σ> → t}{<\text{if } e \text{ then }c_1 \text{ else } c_2,σ> → t}

if 3 > 5 {
    func();
}
else {
    anotherfunc();
}

if 3 - 5 { // Type missmatch
    func(); 
}
else {
    anotherfunc();
}

While expression

\frac{<e, σ> → bool <c, σ> → σ'}{<\text{while } e \text{ do } c, σ> → ()}

\frac{<b, σ> → false}{<\text{while } b \text{ do } c, σ> → σ}

let mut a = 0;
while a < 10 {
    // something that should loop 10 times
    a = a + 1;
}

let mut a = 0;
while a * 10 { // Type missmatch
    // something that should loop 10 times
    a = a + 1;
}

• Compare your solution to the requirements (as stated in the README.md). What are your contributions to the implementation.

Our type checker rejects bad programs according to our rules and depending on what the error is you will get an error custom message.

Your borrrow checker

• Give a specification for well versus ill formed borrows. (What are the rules the borrow checker should check).

• Demonstrate the cases of ill formed borrows that your borrow checker is able to detect and reject.

• Compare your solution to the requirements (as stated in the README.md). What are your contributions to the implementation.

I have not implemented borrow checking.

Your LLVM/Crane-Lift backend (optional)

• Not implemented

Overall course goals and learning outcomes.

• Comment on the alignment of the concrete course goals (taken from the course description) to the theory presented, work you have done and knowledge you have gained. (I have put some comments in [...]).

Lexical analysis, syntax analysis, and translation into abstract syntax.

I have learned to better understand lexical and syntax analysis while working with LALRPOP to create a parser. The start was the most difficult part of creating a parser because of all the ambiguitys you would run into, this lead to re-writing the code several times. During all the times we had to re-do our code I got more and more knowledge of lexical and syntax anaylsis, the LALRPOP documentetation was of great help. Abstract syntax I learned from the lectures.

Regular expressions and grammars, context-free languages and grammars, lexer and parser generators. [lalr-pop is a classical parser generator, it auto generated the lexer for you based on regular expressions but allows for you to define the lexer yourself for more control]

I have learned that LALRPOP uses regular expressions to generate a lexer that can tokenize input to create terminals. This was very interesting and I had no idea it worked this way before taking the course.

Identifier handling and symbol table organization. Type-checking, logical inference systems. [SOS is a logical inference system]

SOS has given me a better insight in how our compiler (interpreter and typechecker) works, but I find it difficult to completely understand how to actually define SOS's of different pars of the compiler. I would like to learn SOS even better. Another thing I learned while we created our compiler is how type checking works and that it actually is not as complicated as I thought it would be.

Intermediate representations and transformations for different languages. [If you attended, Recall lectures relating LLVM/Crane-lift, discussions on SSA (Single Static Assignment) used in LLVM/Crane-lift, and discussions/examples on high level optimization]

I have not implemented this or anything regarding this, so I have little to no knowledge within this area.

Code optimization and register allocation. Machine code generation for common architectures. [Both LLVM/Crane-Lift does the "dirty work" of backend optimization/register allocation leveraging the SSA form of the LLVM-IR]

I have not implemented this or anything regarding this, so I have little to no knowledge within this area.