DEV Community: Evan Typanski

This C++ code doesn't look ambiguous to me

Evan Typanski — Mon, 23 Oct 2023 15:05:33 +0000

Look at this C++ code:

class B;
class A { public: A (B&);};
class B { public: operator A(); };
class C { public: C (B&); };
void f(A) { }
void f(C) { }

int main() {
  B b;
  f(b);
}

Do you think this compiles? Well, probably not because I'm asking. So here's the error message from Clang 13:

etyp:fun/ $ clang++ test.cpp
test.cpp:10:3: error: call to 'f' is ambiguous
  f(b);
  ^
test.cpp:5:6: note: candidate function
void f(A) { }
     ^
test.cpp:6:6: note: candidate function
void f(C) { }
     ^
1 error generated.

Okay so it's ambiguous which conversion gets done for the object b (of type B). So what options are there?

1) Call f(A). We can call A's constructor which takes a reference to a B

2) Call f(C). We can call C's constructor which takes a reference to a B

3) Call f(A). We can call operator A() in the class B

But, 1 and 3 are ambiguous because we can't find a better one to call f(A). But f(C) is still not ambiguous - we know how to call it without any ambiguity. Trying to call f(A) is ambiguous so obviously it shouldn't be chosen.

It turns out in this case, the ambiguity between 1 and 3 is ranked equal priority as the user defined conversion in 2. From the C++20 standard section 12.4.2.10:

For the purpose of ranking implicit conversion sequences as described in 12.4.3.2, the ambiguous conversion sequence is treated as a user-defined conversion sequence that is indistinguishable from any other user-defined conversion sequence.

I find this surprising because I could easily determine that option 2 is the unambiguous way to make this compile.

Not all compilers...

It turns out, MSVC actually accepts the code. You can even see in the assembly it calls f(C).

I believe no matter how silly the standard is with its rules (which this particular point may have a very good reason), C++ compilers should aim to conform to the standard. This case was pulled exactly from the standard as a case that should not compile. MSVC should not compile this.

But that's a whole other rant.

Thanks for looking at that C++ code.

Zig is for me - is it for you?

Evan Typanski — Tue, 04 Apr 2023 15:54:41 +0000

There has been a ton of Zig content lately. So I'll add to the swarm beating this dead horse, but only because I want to introduce some stuff that I'm working on :)

Also, I wanted to write more off-the-cuff style posts.

Zig?

Zig is a modern programming language meant to "replace C." There are a ton of those. There does seem to be a worrying trend where every programmer under the sun believes that they will be the one to destroy C. Despite that, I see legacy C code every day that is run in safety-critical contexts. That code is untouchable. We all know that the second you touch something, it all will crumble. So why would you look at Zig?

There are a lot of reasons. One of the posts I linked above probably does a better job than I will at explaining this. Let's go through some requirements in a C successor:

A successor must have simple, easy control over memory. I believe this one of the main reasons C is so prominent - few other languages let you do what C does with memory with such simplicity. Most C applications work so closely with buffers and hardware that this is essential.
A successor must do number 1) more safely than C. If you've ever touched a C codebase, you've seen crazy segfaults where one corner of the application doesn't properly set memory where the other side assumes it's set. To make a language more appealing than C, you must make it easier to be safe.
A successor must be able to interact easily with C. If you are looking for a language to take over C, you probably have a lot of C sitting around. You don't want to rewrite all of that.
A successor must be able to compile to a lot of hardware, including proprietary hardware. Many devices you see use C for firmware. Many of these have no other choice. The ability to whip up a C compiler for your specific hardware is very important.
A successor must not be ugly. Ugly code isn't fun to write.

How does Zig deal with each of these?

Zig gives you control over allocators to chose how and where memory gets allocated. You also have access to suspiciously C like control over pointers...
Zig still requires manual memory management. If you allocate something, you free it. Or, if another function returns allocated memory, you will free it. Zig's allocators help you do this. First, the allocator pattern is generally implemented by you passing an allocator into a function, so you know it may allocate memory. Programmers should also make it clear that their function allocates memory. Second, you can have special allocators, like std.testing.allocator, which will tell you if you have memory leaks in a unit test. Neat!
Zig has my favorite thing: a transpiler from C (I really like those). Just run zig translate-c and you get Zig code where you had C code. You can use this to include C libraries or upgrade your code base to Zig!
Zig is based on LLVM, so you get a lot of hardware for free. I'd worry a bit about this point, since it seems a lot harder to make a good Zig compiler than a good C compiler. It's not super common to make a brand new C compiler for each piece of hardware (that's what a compiler backend is for), but there certainly are specialized C compilers. Stay tuned for this one.
Zig is mostly pretty. You have to get over stuff like .{} for anonymous structs (I find the anonymous structs syntax satisfying). But some things are great. Say your program returns some enum that can be RED, BLUE, or GREEN. You can return just by saying return .BLUE; - I think that's really cute. No need to even specify the enum name! (which is really convenient considering the enum could be anonymous...)

Zig is special

I admit, not everyone has my sensibilities. Zig isn't the next Python, and many people conflate high level web development with programming in general. So you may hate it. That's okay. Any worthy art has those who don't like it.

What contexts would you use Zig? Obviously wherever C would be used. That could be operating systems, microcontrollers, or even game development. Zig also seems to be adding good support for WebAssembly targets - great for efficient web code. If you're like me, it may also be a good language for compilers, as it gives you a no nonsense, quick language for a compiler or interpreter. Certainly better than Python for that, in my opinion.

Zig is beautiful. It has cool ideas, almost none of which I covered. Just take a look at it, I think it has room to make a splash in certain spaces.

What's next?

I've done a few things in Zig so far, but not as much as I want.

My current pet project takes Zig and puts it on the Arduino. I've gotten LEDs blinking, LCD panels with easy to use libraries, reading from sensors, pulse width modulation... all of that. Under the hood it uses microzig to provide the heavy lifting, I'm just providing an abstraction on top of that abstraction.

Right now, Zig is in a pretty unstable place (it is pre-1.0 after all). Libraries you use won't always work with a new release. But, I think this time is crucial to build libraries and tools. Even if the project isn't a brand new library, just using Zig is extremely helpful for the community. If you have a new project, consider using Zig, to give exposure to the language. Maybe not for your fancy new website, though, unless you're DHH (for all of you Rails lovers).

I plan on making arduzig just as easy to use as the Arduino IDE for whatever Arduino projects you have. I will probably (?) write examples and more posts to make it as understandable as possible. Probably don't try it yet. But once Zig 0.11 is out and I've brought it up to date? Please.

By the way, take a look at the posts I linked in the first sentence if you haven't. They're better than this one.

Rust will `never` do that!

Evan Typanski — Fri, 02 Sep 2022 17:09:01 +0000

That is, the Rust never type (!).

Everything is an expression

Rust is kind of an "everything is an expression" type of language. An expression is something that produces a value. Not everything is an expression, but basically everything that is in a Rust body (executable code) is an expression. Actually, one thing that isn't are locals, like:

let x = 5;

That is its own statement! But you can have an expression with a let statement, just take:


if let Some(num) = func_that_returns_option() {}

The let statement in there isn't a local, it's a let expression.

Let's go over a few other things that are also expressions:

{ 1 }

loop { break 1; }

if true { 1 } else { return; }

This last one is what we'll be interested in.

The `never` type

So if we look into the last example I gave, you know the if block evaluates to 1. But what about the else block? return; doesn't produce a value, it actually leaves the function. So what is its type?

That's right, the never type!

The point of the never type is to say "this computation will not complete." That way, if you assign something to that value:

let x = if true { 1 } else { return; }

The type of x is based on the if block. But, that doesn't mean the never type is ignored. How the compiler figures that out is never can be coerced into any type. That means, when trying to infer the type for x, the compiler sees the if block has type i32. Then the else block has type never, so to make it consistent, it says "never can convert to i32" and it's all okay!

What does this mean for the user?

Well, not much. It's mostly a fun compiler intricacy. But, if you want to see it mentioned in your diagnostics, try the new let else syntax (currently only available with nightly). This syntax lets you use a pattern for a let binding that may not always be true, like:

let Ok(x) = returns_result() else { warn!("This is bad!"); return; };

So, if returns_result returns Ok, then we assign x to the value in Ok. But, if it's not, we warn and return. Pretty easy!

The type of that else block has to be never, though.

So try making it not, with this minimal example:

#![feature(let_else)]

fn opt() -> Option<i32> {
    Some(1)
}

fn main() {
    let Some(x) = opt() else { 1 };
}

This will error:

error[E0308]: `else` clause of `let...else` does not diverge
 --> letelse.rs:7:30
  |
7 |     let Some(x) = opt() else { 1 };
  |                              ^^^^^ expected `!`, found integer
  |
  = note: expected type `!`
             found type `{integer}`
  = help: try adding a diverging expression, such as `return` or `panic!(..)`
  = help: ...or use `match` instead of `let...else`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0308`.

We expect that else block to diverge, so it has to be the never type!

Cool.

Rust will never return from that.

The Art of Transpilers - From One Programming Language to Another

Evan Typanski — Thu, 30 Jun 2022 14:35:27 +0000

Compilers are cool, they take code you write and make code the machine can understand. Transpilers are cooler, they take code you write and make code in another programming language that machines can't understand (yet). But why?

Let's take a quick tour around the world of transpilers!

JavaScript Clones

JavaScript is one of the top use cases for transpilers. JavaScript can run natively in any major browser. So, instead of making a new language and asking browsers to support that natively in the browser, many want to reuse what's already there.

The problem is, JavaScript is crazy. There are many more examples of that. Even with perfect knowledge of JavaScript internals, bugs will happen because of just how dynamic the language is. So, to get around that, we have...

TypeScript

TypeScript is a superset of JavaScript that allows explicit type information. TypeScript solves many of JavaScript's biggest woes with dynamic typing. I will not provide examples so I don't go insane.

So, how does TypeScript do it? It's a transpiler! You can just transpile your TypeScript to JavaScript then run that in the web browser.

So take this example in TypeScript, ruthlessly stolen from the handbook on everyday types:

// test.ts
// Parameter type annotation
function greet(name: string) {
  console.log("Hello, " + name.toUpperCase() + "!!");
}

So we can see our name parameter has the type string. We can then compile this with tsc test.ts to get...

// test.js
// Parameter type annotation
function greet(name) {
  console.log("Hello, " + name.toUpperCase() + "!!");
}

... The same thing without the type in name! Okay that's not interesting, but try adding a call like greet(1); and you'll see an error:

test.ts:6:7 - error TS2345: Argument of type '1' is not assignable to parameter of type 'string'.

6 greet(1);
        ~


Found 1 error.

The type guarantee lets you call toUpperCase() and declines anything that's not a string type. You may be able to see the bugs that could be caught from this. That's why TypeScript has made such a splash.

CoffeeScript

CoffeeScript tries to solve a slightly different problem. Instead of providing a superset that makes your code less prone to bugs, CoffeeScript makes JavaScript prettier.

However, I've always considered CoffeeScript its own language. Once learned, it's a pleasure to write, which is a nice break from JavaScript, in my opinion. But, it seems to be in some middle ground between JavaScript and a standalone language.

In fact, as stated on the CoffeeScript site, NodeJS can natively run CoffeeScript. It doesn't need to transpile down to JavaScript; it is its own language. What if we went more pure, with no intent to replace the syntax of some other language?

Nim

Nim can transpile to C, C++, or JavaScript. That would make Nim our lone example of a language whose purpose is to transpile to multiple other languages. For systems programming, use its C support with dependency-free executables. For frontend development, target JavaScript.

Let's try an example:

// test.nim
echo "Hello World!"

If we compile this to C with nim cc --nimcache:nimcache test.nim, we get.. an executable. So did it compile? Or transpile?

Well, if we check the nimcache directory I specifically included, we'll find a fair few C files. These C files are what get compiled to create the executable we see. I won't include these, since they're a fair bit of code.
But, we see a pretty major difference from the JavaScript-like transpilers we looked at: Nim only uses the transpilation as a means to an end.

C2Rust

But what if you want to permanently change your codebase? That's the idea behind C2Rust. There's value in updating legacy codebases to safer, more secure languages like Rust. So, if you want to do it, try a transpiler!

The value in transpilers stretches far beyond just writing simpler code, or code that targets some other language for backend work. Transpilers can change your codebase and make modernizing the code far easier. In the process, your code becomes safer.

Many frontends, one backend

Imagine you have a tool that you want to support many languages, like for static analysis. But, you don't want to write different analyses for every language's internal representation. What can you do? Introduce a new language, then transpile to that!

That's what I currently work on every day. I make translators that go from many source languages and produce one proprietary language as its output. Then, we run checks based on that internal language.

This can have a pretty high barrier to entry because you have to design a new language and your transpiler. But, depending on the use case, it may be an interesting solution.

Those familiar with LLVM may wonder why this is different from compilation? Many compilers, from Rust to Clang, generate LLVM from your source code. Then, the LLVM generates the machine code. But, that's a compiler, not a transpiler. Don't be silly.

Why?

I don't really have profound conclusions about transpilers. I just think they're cool and underappreciated. And, when you work with them, you get to see the internals of two languages at once, rather than just one!

Two is better than one!

So write more transpilers... And compilers.

References to Literals in Rust?!

Evan Typanski — Sat, 08 Jan 2022 17:59:22 +0000

One day messing around with Rust, I found that the following code is valid:

fn main() {
    let x = &0;
}

That's assigning a variable to a reference to the literal 0 - how?! Why?! This absolutely shocked me. Just try doing this in C++ and you'll see why:

error: non-const lvalue reference to type 'int' cannot bind to a temporary of type 'int'
    int &r = 0;
         ^   ~

The literal is a temporary - you can't have a reference to that! String literals are lvalues in C++, but that's a weird special case. That's why you can assign it to a pointer like const char *, but can't get a const int * from an integer literal.

Why is this shocking?

This may not seem that shocking to some. Literals are generally temporary and don't really live anywhere in memory - they're essentially hard coded constants in the program. A reference points to some place in memory. How do we point to something that doesn't live in memory? Well, we can't, and we don't!

Rvalue Static Promotion

This concept in Rust is called rvalue static promotion. We can look at each part to see what that means:

Rvalue: Something that can only be on the right hand side of an assignment. For example, you can't do 1 = x because the literal 1 is an rvalue.

Static: Something that is valid for the whole lifetime of the program.

So we promote the rvalue to a static value in order to take a reference to it. Looking at the program earlier, we can see this in action in Rust's playground. We can see the MIR (one of the intermediate representations of Rust) is:

fn main() -> () {
    let mut _0: ();                      // return place in scope 0 at src/main.rs:1:11: 1:11
    let _1: &i32;                        // in scope 0 at src/main.rs:2:9: 2:10
    let mut _2: &i32;                    // in scope 0 at src/main.rs:2:13: 2:15
    scope 1 {
        debug x => _1;                   // in scope 1 at src/main.rs:2:9: 2:10
    }

    bb0: {
        _2 = const main::promoted[0];    // scope 0 at src/main.rs:2:13: 2:15
                                         // ...
        _1 = _2;                         // scope 0 at src/main.rs:2:13: 2:15
        return;                          // scope 0 at src/main.rs:3:2: 3:2
    }
}

promoted[0] in main: &i32 = {
    let mut _0: &i32;                    // return place in scope 0 at src/main.rs:2:13: 2:15
    let mut _1: i32;                     // in scope 0 at src/main.rs:2:14: 2:15

    bb0: {
        _1 = const 0_i32;                // scope 0 at src/main.rs:2:14: 2:15
        _0 = &_1;                        // scope 0 at src/main.rs:2:13: 2:15
        return;                          // scope 0 at src/main.rs:2:13: 2:15
    }
}

This is a little weird to look at if you've never seen MIR before, but the important part is the line promoted[0] in main: &i32 - that's where we see the promoted variable! Then in the main program we assign with _2 = const main::promoted[0];. So we lift the literal out to a static lifetime in order to return a reference, pretty neat.

Why did they do this?

I find this the interesting part. We can see a lot of the motivation for this in the feature:

The necessary changes in the compiler did already get implemented as part of codegen optimizations (emitting references-to or memcopies-from values in static memory instead of embedding them in the code).

It seems like it was just an easy thing to implement, so they did it. Their drawback is pretty interesting:

One more feature with seemingly ad-hoc rules to complicate the language...

I found this funny. Seems like they just thought "it's easy enough, could be useful, why not?" So, they added a new feature to the Rust language. So many languages get by without this, but the Rust devs said, why not?

It's useful!

You can see this exact thing in action in Rust's source code! At the time of writing, you can see this here:

    dump_mir(infcx.tcx, None, "renumber", &0, body, |_, _| Ok(()));

The fourth parameter is a reference to the literal 0!

Well, I don't know how useful you'd say it is. But, it's an interesting thing in a common compiler that not many languages have.

Writing a Simple Programming Language from Scratch - Part 3

Evan Typanski — Thu, 30 Dec 2021 22:47:49 +0000

Part 1

Part 2

Source code found here, for much easier running and compiling.

We've gotten a compiler to bring code in our source language, ectlang, to a language most are familiar with, C++. Now, we're going to change our target to something a real compiler may use: LLVM!

What's LLVM?

LLVM is an intermediate representation (or IR) of the source code. Think of the C++ code we wrote earlier: some other tool grabbed it from that point to get it down to the machine code we can run. Now, we'll target LLVM, a language that's meant to be used as an IR.

This is a common pattern in compilers because it allows for you to separate your concerns. The compiler we're writing is actually only the front-end: it changes based on the language (language specific), but doesn't change when we move it over to some other architecture (platform agnostic). LLVM is one of the most common ways to bring your compiler from its frontend to people's computers. Thus, we don't have to worry about targeting all of those different architectures, it's done for us!

And, luckily for us, LLVM has its own API, easily usable from C++.

Using LLVM

There are many tutorials, such as the amazing Kaleidoscope, that does a much better job of explaining LLVM and what it can do for you. The goal for me is to stick our foot in the door. LLVM is actually pretty accessible - far more than assembly! It's just, at this point, we're writing code with code.

So, to start, you'll need to install LLVM to your computer - like on Ubuntu, you can use sudo apt install llvm-12-dev. If that doesn't work, just google it, it shouldn't be too hard. We'll take a break from our compiler for a bit and just compile some straight up C++ code.

I'm going to take this bit by bit, then dump the full code for our prototype at the end, just to not overwhelm anybody.

First, LLVM programs will start with three main objects: LLVMContext, Module, and IRBuilder. Here's about how you'll instantiate each:

// Context - Owns the types and constants we'll use.
llvm::LLVMContext context;

// Module - Contains functions and global variables that we generate.
std::unique_ptr<llvm::Module> mod;
mod = std::make_unique<llvm::Module>("ECTLang module", context);

// IR Builder - what we'll add instructions to. More of a helper class.
llvm::IRBuilder<> builder(context);

Understanding each of these isn't incredibly important, but I'll explain some. The context is where we'll grab, say, an int type, or float type, or the constant 1. We treat it as a black box: it knows how to make things we want, that's about it.

The module stores the information that we make. So, if we make a function, that function is owned by the module.

The IR builder is just an object we use to make creating instructions for basic blocks easier. To create a basic block...

// Function returns void.
llvm::FunctionType *functionReturnType =
    llvm::FunctionType::get(llvm::Type::getVoidTy(context), false);

// Our main function.
llvm::Function *mainFunction =
    llvm::Function::Create(functionReturnType,
                           llvm::Function::ExternalLinkage,
                           "main",
                           mod.get());

// Now make a basic block inside of mainFunction.
llvm::BasicBlock *body = llvm::BasicBlock::Create(context, "body", mainFunction);
builder.SetInsertPoint(body);

Easy enough. We make a function, call it main, then make a new basic block with that function as its parent. Then, we let our builder know we're going to insert instructions in the new basic block.

Basic blocks are hugely important it control flow analysis and compilers. Rust explains them extremely concisely here. All they are is a bunch of commands that run sequentially. When leaving a basic block, then it can jump to some other basic block based on whatever conditions. But, we're writing a language that doesn't even have if statements, we'll be fine without much more than knowing to put our instructions in a basic block.

Now, we have a function that contains a basic block. Let's write our first instructions!!

llvm::Constant *x = llvm::ConstantInt::getSigned(llvm::Type::getInt32Ty(context), 5);
llvm::Constant *y = llvm::ConstantInt::getSigned(llvm::Type::getInt32Ty(context), -6);
llvm::Value *add = builder.CreateAdd(x, y, "addtest");

And that's how you'd make a simple add instruction. Easy, right? The first argument get getSigned shows how the context is used to get types. To finally see your output LLVM, you can add a return statement and output the program to standard out:

builder.CreateRetVoid();
mod->print(llvm::outs(), nullptr);

If you run what we have so far (which is just a function with 5 + -6 in it) you get the following LLVM:

; ModuleID = 'ECTLang module'
source_filename = "ECTLang module"

define void @main() {
body:
  ret void
}

Our main function doesn't have anything resembling what we wrote in it! That's because we never actually added our add to the body. We're going to settle this by printing it.

First, we'll make the function prototype. Here's what printf looks like in C:

int printf(const char *format, ...)

And here's how we can put that in our LLVM program:

    std::vector<llvm::Type *> params;
    params.push_back(llvm::Type::getInt8PtrTy(context));
    llvm::FunctionType *printfType =
            llvm::FunctionType::get(builder.getInt32Ty(), params, /*isVarArg=*/true);
    llvm::Function::Create(printfType, llvm::Function::ExternalLinkage, "printf",
                       mod.get());

It's pretty trivial to use a search engine to find whatever function you may need's prototype. Just figure out how they map to LLVM and you have an easy job. For the function llvm::FunctionType::get, the first argument is the return type (int), the second is a vector of parameters (this can be omitted if there are no parameters), and the last is whether the function is variadic or not.

We created the actual prototype in our module with the function call llvm::Function::Create. The only really interesting part here is that we specified the function is externally linked (via llvm::Function::ExternalLinkage). That just specifies that the linker will find the correct function to use, given we gave the correct information to find it (that is, the prototype).

Now for the fun part, we need to output our add call to printf. You can construct this just like you would in C, just via code. We want to make the following:

printf("%d\n", 5 + -6);

And here's how we construct that function call in LLVM:

    std::vector<llvm::Value *> printArgs;
    llvm::Value *formatStr = builder.CreateGlobalStringPtr("%d\n");
    printArgs.push_back(formatStr);
    printArgs.push_back(add);
    builder.CreateCall(mod->getFunction("printf"), printArgs);

Pretty straightforward! We create an argument for the format string, an argument for the add instruction that we created earlier, then create the function call. The module holds the function that we need, so we can just grab it by name.

Finally, just add a return statement and output the program the standard output. Here's the full program, for reference:

// main.cpp
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"

int main() {
    llvm::LLVMContext context;

    std::unique_ptr<llvm::Module> mod;
    mod = std::make_unique<llvm::Module>("ECTLang module", context);

    // Build IR for this block.
    llvm::IRBuilder<> builder(context);

    // Function returns void.
    llvm::FunctionType *functionReturnType =
        llvm::FunctionType::get(llvm::Type::getVoidTy(context), false);

    // Our main function.
    llvm::Function *mainFunction =
        llvm::Function::Create(functionReturnType,
                               llvm::Function::ExternalLinkage,
                               "main",
                               mod.get());

    // Now make a basic block inside of mainFunction.
    llvm::BasicBlock *body = llvm::BasicBlock::Create(context, "body", mainFunction);
    builder.SetInsertPoint(body);
    llvm::Type *intTy = llvm::Type::getInt32Ty(context);
    // Make a simple add with two constants.
    llvm::Constant *x = llvm::ConstantInt::getSigned(llvm::Type::getInt32Ty(context), 5);
    llvm::Constant *y = llvm::ConstantInt::getSigned(llvm::Type::getInt32Ty(context), -6);
    llvm::Value *add = builder.CreateAdd(x, y, "addtest");

    std::vector<llvm::Type *> params;
    // Pointer to int8 would be like char *
    params.push_back(llvm::Type::getInt8PtrTy(context));

    llvm::FunctionType *printfType =
            llvm::FunctionType::get(builder.getInt32Ty(), params, /*isVarArg=*/true);
    llvm::Function::Create(printfType, llvm::Function::ExternalLinkage, "printf",
                       mod.get());

    // Function call arguments
    std::vector<llvm::Value *> printArgs;
    llvm::Value *formatStr = builder.CreateGlobalStringPtr("%d\n");
    printArgs.push_back(formatStr);
    printArgs.push_back(add);
    builder.CreateCall(mod->getFunction("printf"), printArgs);

    builder.CreateRetVoid();
    mod->print(llvm::outs(), nullptr);

    return 0;
}

Now to compile this program, use your favorite compiler with some extra LLVM tooling help. When you install LLVM, you also get a tool llvm-config which will help with compiler and linker options for your LLVM install. You can use it with GCC like so (mine is called llvm-config-12 for the LLVM version I installed):

$ g++ main.cpp $(llvm-config-12 --ldflags --libs --cxxflags) -o testllvm.out
$ ./testllvm.out

Running the output, we get the following LLVM:

; ModuleID = 'ECTLang module'
source_filename = "ECTLang module"

@0 = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1

define void @main() {
body:
  %0 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @0, i32 0, i32 0), i32 -1)
  ret void
}

declare i32 @printf(i8*, ...)

Being able to read that LLVM isn't important, but we can see the structure seems about right. We have a call to printf with -1 as our add output being passed in. We get the result of the add as an argument because we used constants, which works for our super simple language well enough.

We can compile this LLVM directly with Clang into something we can run! Put that code in a file (I'll call it test.ll) and compile it:

$ clang++ test.ll -o test.out
$ ./test.out

We see -1 is printed, which happens to be the result of 5 + -6!

Since our language has floats, let's also make sure we can do that. If we want to add two floats, it's actually pretty easy. We need to change x and y to be double types:

    llvm::Constant *x = llvm::ConstantFP::get(llvm::Type::getDoubleTy(context), 5.5);
    llvm::Constant *y = llvm::ConstantFP::get(llvm::Type::getDoubleTy(context), -6.5);

Switch our add call to be the floating variant:

    llvm::Value *add = builder.CreateFAdd(x, y, "addtest");

Then change our format string to accept %f to format it at as a float:

    llvm::Value *formatStr = builder.CreateGlobalStringPtr("%f\n");

And if we run/compile that like before, we get a similar result, but floaty:

-1.000000

Generating LLVM

Now that we understand LLVM a bit better, we need to generate LLVM from our small compiler. We'll use the visitor that we made in part 2 to generate some LLVM!

I'm going to skip setup such as initializing the visitor with the required LLVM context and module, along with other minor details. I'll use code to explain concepts, but if you want working code, check out the Github repo at the top.

Building "return" Values

Our visitor we made in the last part doesn't have a return type! Because of this, the more obvious pattern of returning the llvm::Value at each step isn't feasible. But, we can make each visit make a "promise" to fill a variable. Then, we can just treat that variable as the return value. Here's an example for the integer literal type:

// llvmvisitor.cpp
void LLVMVisitor::visit(IntegerNode *node) {
    // Return the LLVM int value.
    ret = llvm::ConstantInt::getSigned(llvm::Type::getInt32Ty(context), node->getValue());
}

Then, if we want to use that value in the visit function for plus:

// llvmvisitor.cpp
void LLVMVisitor::visit(PlusNode *node) {
    // Get the return value from the left side.
    node->getLeft()->accept(*this);
    llvm::Value *lhs = ret;

    // Get the return value from the right side.
    node->getRight()->accept(*this);
    llvm::Value *rhs = ret;

    // Return the add.
    ret = builder.CreateAdd(lhs, rhs);
}

And with that we can have add working! Just do that for the rest of the operations, then we come into another problem.

Dealing with floats

Floats are weird. We can't add an int and a float natively in LLVM. So, instead, we're going to promote everything as soon as we see a float. The logic around this can be a bit more complicated, but we'll try to keep it simple for demonstration purposes. So, if we see a float, we need to promote both sides to a float, then use the float method associated with the operation (eg builder.CreateFAdd). This is what that may look like for add:

// llvmvisitor.cpp
    if (floatInst) {
        // Promote RHS or LHS if we're dealing with floats and they're not a float.
        // (except we use doubles)
        if (!lhs->getType()->isDoubleTy())
            lhs = builder.CreateSIToFP(lhs, llvm::Type::getDoubleTy(context));
        if (!rhs->getType()->isDoubleTy())
            rhs = builder.CreateSIToFP(rhs, llvm::Type::getDoubleTy(context));

        ret = builder.CreateFAdd(lhs, rhs);
    } else {
        // Otherwise we're just doing an integer add.
        ret = builder.CreateAdd(lhs, rhs);
    }

Easy! We have some variable floatInst which gets set when we see a float, then gets reset when we see a StatementNode. This tells us we need to promote the remaining values that are not floats and use float instructions. We check each side to see if it's a double (since we're setting the type to llvm::Type::getDoubleTy(context), works the same with Float and isFloatTy()), then we promote if it's not.

Note, remember to change the format string in the printf call when using a float.

A complete visitor

With that, we have a complete visitor! I put maybe a quarter of the work in this post, with the remaining work already explained, just slightly different. If it's unclear, feel free to check out the repo at the top.

Here's how you can compile it and run some program you make source.ect:

$ bison parser.ypp
$ flex -o scanner.c scanner.lex
$ g++ main.cpp parser.tab.cpp nodes/*.cpp $(llvm-config-12 --ldflags --libs) $(llvm-config-12 --cxxflags) -o ectfrontend.out
$ ./ectfrontend.out < source.ect
$ clang++ test.ll
$ ./a.out

This Language Sucks

Okay, now that we have a "working" language, I want to explain many of the reasons this language sucks. The fundamentals I tried to show in this post remain valid, but everything else is just a tool for getting those fundamentals out with the least amount of background knowledge I could muster. But, knowing some of the shortcomings could help us all not make these mistakes when we actually decide to build a compiler.

No semantic analysis
- We don't check to see that the code is valid, other than it parses. Turns out this could not be horrible for our toy language, but checking for overflows, valid casts, etc. are super important for a compiler.
No warnings, diagnostics, assertions...
- If your program is ill formed, you probably should tell the user why. Depending on how it's ill formed, our compiler may say "syntax error" or just segfault. That's pretty bad design.
- We also don't have assertions. These are pretty useful in any program, so when you build debug you can make sure your assumptions are valid. For example, if we trust our assumption that ret is set for each arithmetic operation, we should add an assertion to express that assumption.
No unary minus
- Yeah, you can't add 5 + -6. Even though I use that as an example up when explaining the LLVM API. Oops. You can still have negative numbers, though?
We expose the IR
- Not a big deal, but most people don't want to compile LLVM directly from a file afterwards. Ideally, you'd continue to use the API for LLVM (or whatever intermediate representation you're using) to create the executable.
Bad CLI
- Our command line interface sucks. You have to pass the program directly in rather than just calling with the file name. You can't specify the output file's name. There's no command line options, even like --help. If anyone ever uses your CLI, these are not just helpful, they're necessary.
We abuse C++
- I purposefully did this to rant about C++ a little. If you noticed, we actually assume that ret is set when we set the lhs and rhs variables. If it's not set, we'd segfault. This is such an incredible amount of trust to give to the functions you're calling. If you get a pointer, always check for null.

I could have fixed these, but I tried to keep everything bite sized for the average reader. It already took me years (!) to write these posts because I had to decide what to keep and what to cut, using experience working with a few real compilers in my job and class to help with that. There are plenty of things that discuss every little detail or have extremely well written, correct code. Those are generally textbooks.

But, thank you so much for reading! Feel free to contact me and get in touch if you have questions or concerns. I hope that compilers seem a little more like regular code now.

Behind C++ Lambda Functions

Evan Typanski — Sat, 12 Jun 2021 16:45:55 +0000

Lambda functions are not just pointers to a function. This is obvious when you think about it: if they're anonymous, and declared completely differently, something must be different. But, we can assign a pointer to a function to a lambda easily:

void (*ptr)() = [](){};

So how does that work? We know we're just assigning to a pointer. But a lambda function isn't just a pointer. So what is it?

Note, we're going to use Clang as an example. A lot of things in C++ are up to compiler dev's imagination, also known as implementation specific. So if I say "lambdas have 12 toes," that is because Clang defines lambdas as having 12 toes, not because they have to have 12 toes.

Lambdas are classes

When you define a lambda function, you're really making a C++ class. This class implements the method operator(). When you call the lambda, you're just calling that operator implementation.

Here's a simple C++ program to show that:

int main() {
  [](){}();
}

That line in main is just defining a lambda with no captures ([]), that takes no argument (()), with no body ({}), then calling it (()). We can actually look at what Clang develops as the AST with:

clang++ -Xclang -ast-dump lambda.cpp

We'll walk through the lambda function piece by piece.

Looking at the AST

The AST is just the internal representation of the code that the compiler looks at. Let's look at the most obvious part of the Lambda shenanigans (note, obvious is relative):

`-CXXOperatorCallExpr 0x17238c8 <col:3, col:10> 'void':'void'
  |-ImplicitCastExpr 0x1723858 <col:9, col:10> 'void (*)() const' <FunctionToPointerDecay>
  | `-DeclRefExpr 0x17237d8 <col:9, col:10> 'void () const' lvalue CXXMethod 0x1723190 'operator()' 'void () const'
  `-ImplicitCastExpr 0x17238b0 <col:3, col:8> 'const (lambda at lambda.cpp:2:3)' lvalue <NoOp>
    `-MaterializeTemporaryExpr 0x1723898 <col:3, col:8> '(lambda at lambda.cpp:2:3)' lvalue
      `-LambdaExpr 0x17236a0 <col:3, col:8> '(lambda at lambda.cpp:2:3)'

Alright. What we have here is a call expression - that's the last () in our lambda. Then, we have some gibberish that is Clang doing internal conversions in order to make the types right. Finally, we have our trusted LambdaExpr - our lambda! Let's look at what's in that.

`-LambdaExpr 0x17236a0 <col:3, col:8> '(lambda at lambda.cpp:2:3)'
  |-CXXRecordDecl 0x1723050 <col:3> col:3 implicit class definition
  | |-DefinitionData lambda pass_in_registers empty standard_layout trivially_copyable can_const_default_init
  | | |-DefaultConstructor defaulted_is_constexpr
  | | |-CopyConstructor simple trivial has_const_param needs_implicit implicit_has_const_param
  | | |-MoveConstructor exists simple trivial needs_implicit
  | | |-CopyAssignment trivial has_const_param needs_implicit implicit_has_const_param
  | | |-MoveAssignment
  | | `-Destructor simple irrelevant trivial
  | |-CXXMethodDecl 0x1723190 <col:6, col:8> col:3 used operator() 'void () const' inline
  | | `-CompoundStmt 0x1723240 <col:7, col:8>
  | |-CXXConversionDecl 0x1723538 <col:3, col:8> col:3 implicit operator void (*)() 'void (*() const noexcept)()' inline
  | |-CXXMethodDecl 0x17235e8 <col:3, col:8> col:3 implicit __invoke 'void ()' static inline
  | `-CXXDestructorDecl 0x17236d0 <col:3> col:3 implicit referenced ~ 'void () noexcept' inline default trivial
  `-CompoundStmt 0x1723240 <col:7, col:8>

Oh, gosh. We'll go piece by piece through this, but here's our class. A CXXRecordDecl in Clang represents a C++ struct, union, or class. So our lambda actually contains that class in its node.

We can even see that in Clang documentation. If we go to the documentation for LambdaExpr in Clang, we can actually see a bunch of useful functions. Notably, we can see getLambdaClass(), which will "retrieve the class that corresponds to the lambda." Neat!

We'll skip the DefinitionData part of the class, since that's just defining some default constructors and whatnot. Let's look at the operator() definition:

| |-CXXMethodDecl 0x1723190 <col:6, col:8> col:3 used operator() 'void () const' inline
| | `-CompoundStmt 0x1723240 <col:7, col:8>

Here we have our call operator. It's empty, and returns void, so it's not like we expect to see much. But, let's make it have something. If we change our lambda function to:

[](){int i = 1;}();

We now have something in our function body, so we expect to see it in the call operator:

| |-CXXMethodDecl 0x171f190 <col:6, col:18> col:3 used operator() 'void () const' inline
| | `-CompoundStmt 0x171f2f8 <col:7, col:18>
| |   `-DeclStmt 0x171f2e0 <col:8, col:17>
| |     `-VarDecl 0x171f258 <col:8, col:16> col:12 i 'int' cinit
| |       `-IntegerLiteral 0x171f2c0 <col:16> 'int' 1

And there we have it, our call operator has a body, just nested in the AST. How about a return type?

[](){return 1;}();

In the AST:

| |-CXXMethodDecl 0x1f88190 <col:6, col:17> col:3 used operator() 'int () const' inline
| | `-CompoundStmt 0x1f883b8 <col:7, col:17>
| |   `-ReturnStmt 0x1f883a8 <col:8, col:15>
| |     `-IntegerLiteral 0x1f88240 <col:15> 'int' 1

As we can see, our CXXMethodDecl changed from void () const to int () const, showing our change in return type!

Finally, how about adding a parameter?

[](int i){}(1);

AST:

| |-CXXMethodDecl 0xe84220 <col:11, col:13> col:3 used operator() 'void (int) const' inline
| | |-ParmVarDecl 0xe83fc8 <col:6, col:10> col:10 i 'int'
| | `-CompoundStmt 0xe842d8 <col:12, col:13>

We can see that the CXXMethodDecl is now void (int) const and we have a ParmVarDecl (just a function parameter) inside of the method decl. Awesome.

But, lambdas also let you capture a variable. This means that if I have a variable i outside of the lambda, capture it, change it, then call the lambda, we should see that variable change. Let's try it out:

#include <iostream>

int main() {
  int i;
  auto lambda = [&i](){
    std::cout << "i is: " << i << std::endl;
  };
  i = 42;
  lambda();
}

And here's our output:

i is: 42

Awesome. How does this work in the AST? If we look at it, we actually have one key difference:

| |-FieldDecl 0x18ec440 <col:5> col:5 implicit 'int &'

We have a field inside of our lambda's class now! It's a reference to an int, namely to i declared outside. Then, when we use our lambda, we just use that field! Neat.

Now, we don't take a parameter, we still return void, can we assign this to a C function pointer like we did at the beginning?

int main() {
  int i;
  void (*ptr)() = [&i](){};
}

The compiler errors!

lambda.cpp:5:10: error: no viable conversion from '(lambda at lambda.cpp:5:19)' to 'void (*)()'
  void (*ptr)() = [&i](){};
         ^        ~~~~~~~~

It's weird because we still have all the qualifications of that function pointer. But, if we look at the AST, we'll see something missing from the Lambda's class, particularly:

| |-CXXConversionDecl 0x142f7b8 <col:19> col:19 implicit used operator void (*)() 'void (*() const noexcept)()' inline
| | `-CompoundStmt 0x142fba0 <col:19>
| |   `-ReturnStmt 0x142fb90 <col:19>
| |     `-ImplicitCastExpr 0x142fb78 <col:19> 'void (*)()' <FunctionToPointerDecay>
| |       `-DeclRefExpr 0x142fb58 <col:19> 'void ()' lvalue CXXMethod 0x142f868 '__invoke' 'void ()'

Clang actually refuses to generate a conversion to the function pointer if we have any captures! That makes sense because the function now relies on that variable i.

Let's say we're really curious and need to know why this happened. How can we do that?

Diving into Clang's code

Luckily, Clang's source code is open source. You can find it, along with LLVM and more, on Github. Furthermore, if you want to know something high level about Clang's code, check out the Clang internals manual.

But, our job is simple: find out where it refuses to generate the conversion function.

The first place to start requires a bit of compiler knowledge. Clang has a Sema library for certain semantic actions. This Sema library is what builds the AST. Considering that, we probably have a good place to start, since we noticed a difference in the AST.

At this time, you can find the Sema library on the Github under llvm-project/clang/lib/Sema/

Now that we're here, we want to see what creates the lambda function. A solid way to do this would be to look up the constructor in the documentation and see what calls it and when. But, our case is lucky: there's a file called SemaLambda.cpp, so let's check that out.

If we dig around here, we find the function BuildLambdaExpr. Seems promising.

From there, let's just look through the function.

First we do some setup from previously gathered info:

CallOperator = LSI->CallOperator;
Class = LSI->Lambda;
IntroducerRange = LSI->IntroducerRange;
ExplicitParams = LSI->ExplicitParams;
ExplicitResultType = !LSI->HasImplicitReturnType;
LambdaCleanup = LSI->Cleanup;
ContainsUnexpandedParameterPack = LSI->ContainsUnexpandedParameterPack;
IsGenericLambda = Class->isGenericLambda();

Then, we do some logic checking if captures are used and getting them in a good form for our AST.

Next, we can see why we don't get our conversion function:

if (Captures.empty() && CaptureDefault == LCD_None)
  addFunctionPointerConversions(*this, IntroducerRange, Class,
                                CallOperator);

So, we only add the function pointer conversion if we have no captures and the capture default is none!

If you really want to dive into the weeds, the Clang devs also often comment the part of the standard they took from:

// C++11 [expr.prim.lambda]p6:
//   The closure type for a lambda-expression with no lambda-capture
//   has a public non-virtual non-explicit const conversion function
//   to pointer to function having the same parameter and return
//   types as the closure type's function call operator.

You can find this yourself too! Just look around for C++ standards (like through open-std.org or just a search engine) and find the section with expr.prim.lambda. You'll see numbering, find number 6, and you'll find identical or similar wording to that.

Was this about lambdas?

Not really. Lambdas were just a mechanism for showing how to find out more about C++ by digging into it. This applies to any language or compiler too, especially if they let you dump ast (or some intermediate representation). It's also just fun to look at complex code.

So there you go. Try this out the next time you see a weird construct in your favorite language. Sometimes, you'll get surprised and fall into a fun rabbit hole. It's worth every hour.

Writing a Simple Programming Language from Scratch - Part 2

Evan Typanski — Mon, 03 May 2021 23:29:56 +0000

Part 1 found here!!

Source code found here, for much easier running and compiling.

Up to this point, we made part of a compiler front end, namely the lexer and parser. Now, we'll adapt the parser and add some steps to make.. more code! Also known as an intermediate representation of the source code. More on that later.

To do this, we'll use a visitor pattern.

Visitors

The visitor software pattern is very useful, especially in compiler design. Visitors can essentially implement new methods on each node while traversing a tree. Or a not tree, but we'll use a tree.

Let's make a basic visitor!

// nodes.cpp
#include <iostream>

class Node {
public:
    virtual void accept(class Visitor &v) = 0;
};


class IntegerNode: public Node {
public:
    IntegerNode(int value);
    void accept(Visitor &v);
    int value;
};

class Visitor {
public:
    void visit(IntegerNode *node);
};

IntegerNode::IntegerNode(int value) : value(value) {}

void IntegerNode::accept(Visitor &v) {
    v.visit(this);
}

void Visitor::visit(IntegerNode *node) {
    std::cout << node->value << std::endl;
}

int main() {
    IntegerNode node(5);
    Visitor visitor;
    node.accept(visitor);
}

Then here's the output when this program is called:

evan:ectlang/ $ g++ nodes.cpp
evan:ectlang/ $ ./a.out
5
evan:ectlang/ $

What's happening here is pretty simple. The node "accepts" the visitor, which prompts the visitor to visit that particular node. accept will call IntegerNode's accept because of the virtual method. Then, the visitor can do whatever it wants with that object, knowing its type exactly. If we had a PlusNode that accepted a visitor, then we would call that accept method, thus we would visit the PlusNode instead.

I won't bore by going through all of the nodes, it's mostly just busy work to set it all up. There are ways to write those classes without all of the busy work (tools, metaprogramming). Useful, but writing a simple set of nodes isn't too much work. Sometimes people go through a lot of effort to automate a process that would take less time to just do manually.

So now we can add any number of nodes that we want. I'll show how we could do some recursion in this using the plus node, then hopefully extrapolating out will be a bit more simple.

// nodes.cpp
/* Keeping all IntegerNode references in code */

class PlusNode: public Node {
public:
    PlusNode(IntegerNode left, IntegerNode right);
    void accept(Visitor &v);
    IntegerNode left, right;
};

class Visitor {
public:
    void visit(PlusNode *node);
};

PlusNode::PlusNode(IntegerNode left, IntegerNode right) :
    left(left), right(right) {}

void PlusNode::accept(Visitor &v) {
    v.visit(this);
}

void Visitor::visit(PlusNode *node) {
    node->left.accept(*this);
    std::cout << "+";
    node->right.accept(*this);
    std::cout << "=" << node->left.value + node->right.value << std::endl;
}


int main() {
    IntegerNode leftInt(1), rightInt(2);
    PlusNode plus(leftInt, rightInt);
    Visitor visitor;
    plus.accept(visitor);
}

This will recursively use your new PlusNode and output the added numbers! Here's the output:

evan:ectlang/ $ g++ nodes.cpp
evan:ectlang/ $ ./a.out
1+2=3
evan:ectlang/ $

The only nodes we'll add that aren't obvious are ProgramNode and StatementNode. A "program" will be a collection of statements for our simple language, and a "statement" is a bunch of math followed by a semicolon. Really a statement can be seen as a command, like return 0;

So how will we use this? The program can actually be represented easily as a tree. This is often represented as an abstract syntax tree (AST). We will then visit each node in the AST, and the visitor will generate some code. This generated code is an intermediate representation of the code - we don't write this code by hand, but the computer also doesn't use it. It's mainly used by the language to facilitate optimizations and compiling for different computers with different architectures.

We can also have other kinds of visitors! One class Visitor could be inherited by your type checker, or what makes your symbol table, then each of these visitors can be run. This example will only use one visitor - the one that generates code.

Lexer and Parser Updates

Now let's update our parser from part 1 to return nodes instead of doing the calculations itself. We'll also rename the file the parser.ypp to generate C++. Here is what we'll use for our C declarations:

// parser.ypp

%{
  #include <assert>
  #include <iostream>
  #include "nodes/node.h"
  #include "nodes/minusnode.h"
  #include "nodes/plusnode.h"
  #include "nodes/multnode.h"
  #include "nodes/divnode.h"
  #include "nodes/expnode.h"
  #include "nodes/integernode.h"
  #include "nodes/floatnode.h"
  #include "nodes/programnode.h"
  #include "nodes/statementnode.h"
  #include "scanner.c"

  using namespace std;
  extern "C" int yylex(void);
  extern int yylineno;

  void yyerror(char *s) {
    cerr << s << endl;
  }

  ProgramNode *program;
%}

There are some basic changes here, but two main ones for understanding how this works: first, we import all of the nodes we'll use inside the parser. Second, we declare a variable *program to point to the initial node. We'll build everything off of this, then use it in a different file.

Here are the Bison declarations that we'll use. We changed the union to include nodes that we want to be exchanged between grammar rules, and put the return values in their type definitions.

// parser.ypp

%union{
  int intVal;
  float floatVal;
  class Node *node;
  class ExpNode *expNode;
  class StatementNode *statementNode;
}

%start program

%token <intVal> INTEGER_LITERAL
%token <floatVal> FLOAT_LITERAL
%token SEMI
%type <expNode> exp
%type <statementNode> statement
%type <node> program
%left   PLUS MINUS
%left   MULT DIV

This is similar to what we did in part 1 - just including the nodes!

Finally, here are the grammar rules:

// parser.ypp

program: { program = new ProgramNode(yylineno); }
    | program statement { assert(program); program->addStatement($2); }
    ;

statement: exp SEMI { $$ = new StatementNode(yylineno, $1); }
    ;

exp:
   INTEGER_LITERAL  { $$ = new IntegerNode(yylineno, $1); }
    | FLOAT_LITERAL { $$ = new FloatNode(yylineno, $1); }
    | exp PLUS exp  { $$ = new PlusNode(yylineno, $1, $3); }
    | exp MINUS exp { $$ = new MinusNode(yylineno, $1, $3); }
    | exp MULT exp  { $$ = new MultNode(yylineno, $1, $3); }
    | exp DIV exp   { $$ = new DivNode(yylineno, $1, $3); }
    ;

Each rule returns a new node that we can access in another program as an object - after we finish parsing, we'll only touch these nodes, we don't care about the source code. So, when we parse a division, we'll create a DivNode to represent that division, then don't touch that source code again.

Now we also add a yylineno variable to keep track of line numbers. Most programming languages have some way of managing where in the source file certain nodes came from in order to emit diagnostics, telling the programmer what they did wrong. We're not going to do much with that, but if you ever want good diagnostics, consider including some source information.

Finally, program has a bit of interesting logic. If we get to the first, empty case for the program nonterminal, we make a new ProgramNode to use. If we get to the point where we have a statement, we'll also have a program, so we add the statement (where a program is just a std::vector of statements in implementation). We also assert if we don't have a program - some kind of null check is SO important in C++ code, preferably more than an assert since it doesn't apply in production! Never underestimate the power of humans to segfault a C/C++ program.

Our lexer didn't change much, just adding a couple options, but I'll put it here anyway:

// scanner.lex

%{
#include "parser.tab.hpp"
  extern "C" int yylex();
%}
%option noyywrap
%option yylineno

%%
[0-9]+        { yylval.intVal = atoi(yytext); return INTEGER_LITERAL; }
[0-9]+.[0-9]+ { yylval.floatVal = atof(yytext); return FLOAT_LITERAL; }
"+"           { return PLUS; }
"-"           { return MINUS; }
"*"           { return MULT; }
"/"           { return DIV; }
";"           { return SEMI; }
[ \t\r\n\f]   ; /* ignore whitespace */

Now that we have that, let's make a file that runs this! This was moved from the bottom of the parser from part 1.

// main.cpp

#include "nodes/programnode.h"
#include "nodes/visitor.h"

using namespace std;

extern ProgramNode* program;
extern int yyparse();

int main(int argc, char **argv) {
    yyparse();
    Visitor v;
    program->accept(v);
    return 0;
}

All this does is it calls some method yyparse() which we get as an extern function from the Bison files we generated. That populates our program variable. From this, we can visit the program we parsed!

Let's run it on a program with one line - 3 + 3.2;

evan:ectlang/ $ flex -o scanner.c scanner.lex
evan:ectlang/ $ bison parser.ypp
evan:ectlang/ $ g++ parser.tab.cpp main.cpp nodes/*.cpp
evan:ectlang/ $ ./a.out < source.ect
Program
STATEMENT
3+3.2%

This is good! We visited the program, then the statement, then the 3+3.2 in our code. This proves we have a parser which creates the AST, then a visitor which goes through and visits the nodes.

Code Generation

Now, we have an accurate AST for our program. We want to use this AST in order to write code that our computer can run. Normally, we'll do this with a true intermediate representation (like LLVM). We won't be doing that quite yet. Instead, we'll go with something easier to understand, that way the concept of code generation and visitors aren't blurred by the complexity of another foreign language. So, instead, we'll just turn our code into C++. It pains me to do this, but it's a good tool to use since we know what proper C++ code looks like.

Another consequence of writing C++ code is we're going to make it human readable. This won't be the case for most languages - once it gets to this point, the machine tends to be one of the only things actually reading the code, so it won't care much for readability. We're humans and C++ is a human programming language, so it's relatively easy to understand! LLVM is somewhat readable, but it's not super easy.

How will we do this? We'll make a new visitor that generates .cpp files! Here's the implementation file for that (let's ignore the header files):

// cppvisitor.cpp

CPPVisitor::CPPVisitor(const char *filename) {
    // Open the file we are going to write to.
    file.open(filename, std::fstream::out);
}

void CPPVisitor::visit(ProgramNode *node) {
    // Write out the information we need to actually run the C program
    // This is hardcoded. It shouldn't be in most cases, but education!!
    file << "#include <iostream>\n";
    file << "int main() {\n";
    node->getStatement()->accept(*this);
    file << "}\n";
    file.close();
}

void CPPVisitor::visit(StatementNode *node) {
    // We want to print our statements when the generated C++ code is run.
    file << "\tstd::cout << ";
    node->getExp()->accept(*this);
    file << " << std::endl;\n";
}

void CPPVisitor::visit(IntegerNode *node) {
    // Append the integer to the file.
    file << node->getValue();
}

void CPPVisitor::visit(FloatNode *node) {
    // Append the float to the file.
    file << node->getValue();
}

void CPPVisitor::visit(PlusNode *node) {
    // Append the addition to the file.
    node->getLeft()->accept(*this);
    file << " + ";
    node->getRight()->accept(*this);
}

void CPPVisitor::visit(MinusNode *node) {
    // Append the subtraction to the file.
    node->getLeft()->accept(*this);
    file << " - ";
    node->getRight()->accept(*this);
}

void CPPVisitor::visit(MultNode *node) {
    // Append the multiplication to the file.
    node->getLeft()->accept(*this);
    file << " * ";
    node->getRight()->accept(*this);
}

void CPPVisitor::visit(DivNode *node) {
    // Append the division to the file.
    node->getLeft()->accept(*this);
    file << " / ";
    node->getRight()->accept(*this);
}

Basically, if you understood what was going on before with us printing out each statement, you'll understand this. Instead of using std::cout directly, we make a C++ program that calls them. Each statement (which, in our language, is just some math followed by a semicolon) will go into an std::cout call in another file - very, very useful! Okay maybe not but you can see the potential.

What's amazing about this isn't that we wrote a program that (kind of) writes C++ programs, it's that you can write your visitor to generate many different languages - it's not too much harder to just make it generate assembly! It's really easy to compile/run C++ code to see the fruits of your labor, so that's what we use here.

Let's run on this file (called source.ect):

3 + 3.2;
5 + 2 * 3 - 8;
1.1 - 1.1 + 1.1 - 1.1 * 1;

One last run!

evan:ectlang/ $ flex -o scanner.c scanner.lex
evan:ectlang/ $ bison parser.ypp
evan:ectlang/ $ g++ parser.tab.cpp main.cpp nodes/*.cpp
evan:ectlang/ $ ./a.out < source.ect

From that, we get the following file created (in test.cpp):

#include <iostream>
int main() {
    std::cout << 3 + 3.2 << std::endl;
    std::cout << 5 + 2 * 3 - 8 << std::endl;
    std::cout << 1.1 - 1.1 + 1.1 - 1.1 * 1 << std::endl;
}

And if we run that...

evan:ectlang/ $ g++ test.cpp -o ect-program
evan:ectlang/ $ ./ect-program
6.2
3
0

Exactly as we'd expect. Good job, folks!

So What?

So we created C++ code. Who cares? Why didn't we just write the C++ program? Well, the intermediate representation won't really be so high level - it'd be more like assembly in the end. We don't want to constantly write assembly for obvious reasons, so we write programs that transform our code into that - the whole purpose of a compiler. While here we made the intermediate representation a C++ file, that will never happen in a real language, but it's not too far off from it. That's why there's a bit more to the puzzle we have yet to cover.

With that being said, that's everything! You now should at least have a basis for doing some operations on your source code, eventually creating an intermediate representation that can be used. Congrats!

Onwards to part 3!

Writing a Simple Programming Language from Scratch - Part 1

Evan Typanski — Sun, 07 Jul 2019 13:03:45 +0000

If you're a developer, you've used programming languages. They're awesome ways to make a computer do what you want it to. Maybe you've even dove deep and programmed in assembly or machine code. Many never want to come back. But some wonder, how can I torture myself more by doing more low level programming? I want to know more about how programming languages are made! All joking aside, writing a new language isn't as bad as it sounds, so if you have even a mild curiosity, I would suggest you stick around and see what it's about.

This post is meant to give a simple dive into how a programming language can be made, and how you can make your own special language. Maybe even name it after yourself. Who knows.

I also bet that this seems like an incredibly daunting task to take on. Do not worry, for I have considered this. I did my best to explain everything relatively simply without going on too many tangents. By the end of this post, you will be able to create your own programming language (there will be a few parts), but there's more. Knowing what goes on under the hood will make you better at debugging. You'll better understand new programming languages and why they make the decisions that they do. You can have a programming language named after yourself, if I didn't mention that before. Also, it's really fun. At least to me.

Compilers and Interpreters

Programming languages are generally high-level. That is to say, you're not looking at 0s and 1s, nor registers and assembly code. But, your computer only understands 0s and 1s, so it needs a way to move from what you read easily to what the machine can read easily. That translation can be done through compilation or interpretation.

Compilation is the process of turning an entire source file of the source language into a target language. For our purposes, we'll think about compiling down from your brand new, state of the art language, all the way down to runnable machine code.

My goal is to make the "magic" disappear

Interpretation is the process of executing code in a source file more or less directly. I'll let you think that's magic for this.

So, how do you go from easy-to-read source language to hard-to-understand target language?

Phases of a Compiler

A compiler can be split up into phases in various ways, but there's one way that's most common. It makes only a small amount of sense the first time you see it, but here it goes:

Oops, I picked the wrong diagram, but this will do. Basically, you get the source file, you put it into a format that the computer wants (removing white space and stuff like that), change it into something the computer can move around well in, and then generate the code from that. There's more to it. That's for another time, or for your own research if your curiosity is killing you.

Lexical Analysis

AKA "Making source code pretty"

Consider the following completely made up language that's basically just a calculator with semicolons:


 r
  // source.ect
  3 + 3.2;
  5.0 / 1.9;
  6 * 2;

The computer doesn't need all of that. Spaces are just for our petty minds. And new lines? No one needs those. The computer turns this code that you see into a stream of tokens that it can use instead of the source file. Basically, it knows that 3 is an integer, 3.2 is a float, and + is something that operates on those two values. That's all the computer really needs to get by. It's the lexical analyzer's job to provide these tokens instead of a source program.

How it does that is really quite simple: give the lexer (a less pretentious sounding way of saying lexical analyzer) some stuff to expect, then tell it what to do when it sees that stuff. These are called rules. Here's an example:


 cpp
int     cout << "I see an integer!" << endl;

When an int comes through the lexer and this rule is executed, you will be greeted with a quite obvious "I see an integer!" exclamation. That's not how we'll be using the lexer, but it's useful to see that the code execution is arbitrary: there aren't rules that you have to make some object and return it, it's just regular old code. Can even use more than one line by surrounding it with braces.

By the way, we'll be using something called FLEX to do our lexing. It makes things pretty easy, but nothing is stopping you from just making a program that does this yourself.

To get an understanding of how we'll use flex, look at this example:


 cpp
    // scanner.lex
    /* Definitions */
    %{
      #include <iostream>
      using namespace std;
      extern "C" int yylex();
    %}

    /* Rules next */
    %%
    [0-9]+.[0-9]+ cout << "FLOAT: (" << yytext << ")" << endl;
    [0-9]+        cout << "INT: (" << yytext << ")" << endl;
    "+"           cout << "PLUS" << endl;
    "-"           cout << "MINUS" << endl;
    "*"           cout << "TIMES" << endl;
    "/"           cout << "DIVIDED BY" << endl;
    ";"           cout << "SEMICOLON" << endl;
    [\t\r\n\f]    ; /* ignore whitespace */

    %%
    /* Code */

    int main() {
      yylex();
    }

This introduces a few new concepts, so let's go over them:

%% is used to separate sections of the .lex file. The first section is declarations - basically variables to make the lexer more readable. It's also where you import, surrounded by %{ and %}.

Second part is the rules, which we saw before. These are basically a large if else if block. It will execute the line with the longest match. Thus, even if you change the order of the float and int, the floats will still match, as matching 3 characters of 3.2 is more than 1 character of 3. Note that if none of these rules are matched, it goes to the default rule, simply printing the character to standard out. You can then use yytext to refer to what it saw that matched that rule.

Third part is the code, which is simply C or C++ source code that is run on execution. yylex(); is a function call which runs the lexer. You can also make it read input from a file, but by default it reads from standard input.

Say you created these two files as source.ect and scanner.lex. We can create a C++ program using the flex command (given you have flex installed), then compile that down and input our source code to reach our awesome print statements. Let's put this into action!


 bash
evan:ectlang/ $ flex scanner.lex
evan:ectlang/ $ g++ lex.yy.c -lfl
evan:ectlang/ $ ./a.out < source.ect
INT: (3)
PLUS
FLOAT: (3.2)
SEMICOLON
FLOAT: (5.0)
DIVIDED BY
FLOAT: (1.9)
SEMICOLON
INT: (6)
TIMES
INT: (2)
SEMICOLON
evan:ectlang/ $

Hey, cool! You're just writing C++ code that matches input to rules in order to do something.

Now, how do compilers use this? Generally, instead of printing something, each rule will return something - a token! These tokens can be defined in the next part of the compiler...

Syntax Analyzer

AKA "Making pretty source code usable"

It's time to have fun! Once we get here, we start to define the structure of the program. The parser is just given a stream of tokens, and it has to match elements in this stream in order to make the source code have structure that's usable. To do this, it uses grammars, that thing you probably saw in a theory class or heard your weird friend geeking out about. They're incredibly powerful, and there's so much to go into, but I'll just give what you need to know for our sorta dumb parser.

Basically, grammars match non-terminal symbols to some combination of terminal and non-terminal symbols. Terminals are leaves of the tree; non-terminals have children. Don't worry about it if that doesn't make sense, the code will probably be more understandable.

We'll be using a parser generator called Bison. This time, I'll split the file up into sections for explanation purposes. First, the declarations:


 cpp
    // parser.y
    %{
      #include <iostream>
      using namespace std;
      extern "C" void yyerror(char *s);
      extern "C" int yyparse();
    %}

    %union{
      int intVal;
      float floatVal;
    }

    %start program

    %token <intVal> INTEGER_LITERAL
    %token <floatVal> FLOAT_LITERAL
    %token SEMI
    %type <floatVal> exp
    %type <floatVal> statement
    %left PLUS MINUS
    %left MULT DIV

The first part should look familiar: we're importing stuff that we want to use. After that it gets a little more tricky.

The union is a mapping of a "real" C++ type to what we're going to call it throughout this program. So, when we see intVal, you can replace that in your head with int, and when we see floatVal, you can replace that in your head with float. You'll see why later.

Next we get to the symbols. You can divide these in your head as terminals and non-terminals, like with the grammars we talked about before. Capital letters means terminals, so they don't continue to expand. Lowercase means non-terminals, so they continue to expand. That's just convention.

Each declaration (starting with %) declares some symbol. First, we see that we start with a non-terminal program. Then, we define some tokens. The <> brackets define the return type: so the INTEGER_LITERAL terminal returns an intVal. The SEMI terminal returns nothing. A similar thing can be done with non-terminals using type, as can be seen when defining exp as a non-terminal that returns a floatVal.

Finally we get into precedence. We know PEMDAS, or whatever other acronym you may have learned, which tells you some simple precedence rules: multiplication comes before addition, etc. Now, we declare that here in a weird way. First, lower in the list means higher precedence. Second, you may wonder what the left means. That's associativity: pretty much, if we have a op b op c, do a and b go together, or maybe b and c? Most of our operators do the former, where a and b go together first: that's called left associativity. Some operators, like exponentiation, do the opposite: a^b^c expects that you raise b^c then a^(b^c). However, we won't deal with that. Look at the Bison page if you want more detail.

Okay I probably bored you enough with declarations, here's the grammar rules:


 cpp
    // parser.y
    %%
    program: /* empty */
        | program statement { cout << "Result: " << $2 << endl; }
        ;

    statement: exp SEMI

    exp:
        INTEGER_LITERAL { $$ = $1; }
        | FLOAT_LITERAL { $$ = $1; }
        | exp PLUS exp  { $$ = $1 + $3; }
        | exp MINUS exp { $$ = $1 - $3; }
        | exp MULT exp  { $$ = $1 * $3; }
        | exp DIV exp   { $$ = $1 / $3; }
        ;

This is the grammar we were talking about before. If you're not familiar with grammars, it's pretty simple: the left hand side can turn into any of the things on the right hand side, separated with | (logical or). If it can go down multiple paths, that's a no-no, we call that an ambiguous grammar. This isn't ambiguous because of our precedence declarations - if we change it so that plus is no longer left associative but instead is declared as a token like SEMI, we see that we get a shift/reduce conflict. Want to know more? Look up how Bison works, hint, it uses an LR parsing algorithm.

Okay, so exp can become one of those cases: an INTEGER_LITERAL, a FLOAT_LITERAL, etc. Note it's also recursive, so exp can turn into two exp. This allows us to use complex expressions, like 1 + 2 / 3 * 5. Each exp, remember, returns a float type.

What is inside of the brackets is the same as we saw with the lexer: arbitrary C++ code, but with more weird syntactic sugar. In this case, we have special variables prepended with $. The variable $$ is basically what is returned. $1 is what is returned by the first argument, $2 what is returned by the second, etc. By "argument" I mean parts of the grammar rule: so the rule exp PLUS exp has argument 1 exp, argument 2 PLUS, and argument 3 exp. So, in our code execution, we add the first expression's result to the third.

Finally, once it gets back up to the program non-terminal, it will print the result of the statement. A program, in this case, is a bunch of statements, where statements are an expression followed by a semicolon.

Now let's write the code part. This is what will actually be run when we go through the parser:


 cpp
    // parser.y
    %%
    int main(int argc, char **argv) {
      if (argc < 2) {
        cout << "Provide a filename to parse!" << endl;
        exit(1);
      }
      FILE *sourceFile = fopen(argv[1], "r");

      if (!sourceFile) {
        cout << "Could not open source file " << argv[1] << endl;
        exit(1);
      }

      // Sets input for flex to the file instead of standard in
      yyin = sourceFile;
      // Now let's parse it!
      yyparse();
    }

    // Called on error with message s
    void yyerror(char *s) {
      cerr << s << endl;
    }

Okay, this is starting to get interesting. Our main function now reads from a file provided by the first argument instead of from standard in, and we added some error code. It's pretty self explanatory, and comments do a good job of explaining what's going on, so I'll leave it as an exercise to the reader to figure this out. All you need to know is now we're back to the lexer to provide the tokens to the parser! Here is our new lexer:


 cpp
    // scanner.lex
    %{
      extern "C" int yylex();
      #include "parser.tab.c"  // Defines the tokens
    %}

    %%
    [0-9]+        { yylval.intVal = atoi(yytext); return INTEGER_LITERAL; }
    [0-9]+.[0-9]+ { yylval.floatVal = atof(yytext); return FLOAT_LITERAL; }
    "+"           { return PLUS; }
    "-"           { return MINUS; }
    "*"           { return MULT; }
    "/"           { return DIV; }
    ";"           { return SEMI; }
    [ \t\r\n\f]   ; /* ignore whitespace */

Hey, that's actually smaller now! What we see is that instead of printing, we're returning terminal symbols. Some of these, like ints and floats, we're first setting the value before moving on (yylval is the return value of the terminal symbol). Other than that, it's just giving the parser a stream of terminal tokens to use at its discretion.

Cool, lets run it then!


 bash
evan:ectlang/ $ bison parser.y
evan:ectlang/ $ flex scanner.lex
evan:ectlang/ $ g++ lex.yy.c -lfl
evan:ectlang/ $ ./a.out source.ect
Result: 6.2
Result: 2.63158
Result: 12

There we go - our parser prints the correct values! But this isn't really a compiler, it just runs C++ code that executes what we want. To make a compiler, we want to turn this into machine code. To do that, we need to add a little bit more...

Until Next Time...

I'm realizing now that this post will be a lot longer than I imagined, so I figured I'd end this one here. We basically have a working lexer and parser, so it's a good stopping point.

I've put the source code on my Github, if you're curious about seeing the final product. As more posts are released, that repo will see more activity.

Given our lexer and parser, we can now generate an intermediate representation of our code that can be finally converted into real machine code, and I'll show you exactly how to do it.

Part 2 is up!

Additional Resources

If you happen to want more info on anything covered here, I've linked some stuff to get started. I went right over a lot, so this is my chance to show you how to dive into those topics.

Flex codebase: https://github.com/westes/flex - the lexical analysis tool we used.
Bison documentation: https://www.gnu.org/software/bison/ - the parser generator we used. Awesome documentation here.
LALR parsing: https://web.cs.dal.ca/~sjackson/lalr1.html - a well made explanation on how LALR(1) parsers (like what Bison generates!) work.
Resolving parsing conflicts: http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/conflict.html - how to fix shift/reduce or reduce/reduce conflicts, like the one we saw before.
Chomsky hierarchy: https://en.wikipedia.org/wiki/Chomsky_hierarchy - didn't go much in detail about this, but we were using a context-free grammar so Bison can compile it. If you want context sensitivity, that's for later phases.
Symbol table: https://www.tutorialspoint.com/compiler_design/compiler_design_symbol_table.htm - using symbol tables, how compilers deal with variables.

Oh, by the way, if you didn't like my phases of a compiler, here's an actual diagram. I still left off the symbol table and error handler. Also note that a lot of diagrams are different from this, but this best demonstrates what we're concerned with.

Lessons from My First Internship

Evan Typanski — Mon, 13 Aug 2018 16:49:01 +0000

I'm currently a student at the University of Virginia, having just finished my first internship. The company has a relatively small engineering department, but one that has been around for a while. This internship taught me a lot more than I thought it would, ranging from technical experience to what I should focus on. These are the lessons I learned from one summer away from school.

Lesson 1: Learn how to interview

Interviewing went both well and terribly. The first time, I would say that I did well. The second time, however, felt terrible. I struggled to answer any question that had any technical capacity, from data modeling to Rails to Javascript. After that, I felt like I had no chance. However, about a month later, I got the offer for an internship, which I essentially accepted on the spot.

During my time, I got to sit in on two technical interviews. This was incredibly enlightening. With no disrespect to those interviewed, I got to see people fail in exactly the same way I failed. I also got to see them do far better than I had done. Then, I got to sit in on the discussion about the candidates, where they seemed to want to attribute as much positivity as they could to the candidates. Both got job offers and accepted them. Interviewing wasn't meant to be a test with right or wrong answers; interviewing was a way to see if that person would work well in the company. A simple distinction, but this is astonishing to someone just starting out in the industry.

Why is this important? Because if you can't interview, then nobody can tell if you fit the role or not. It's not about being able to ace it like a test, it's about being able to effectively communicate what you are and are not knowledgable of. I failed to give any idea that I might even be okay for the job. However, I still got an offer. It still feels like I never deserved the job from my performance on the interview, but I can definitely say that it turned out pretty okay.

Lesson 2: Ask questions

I know, everyone says this. No matter where you go, whether it's a job or internship, people say that you should ask questions. At the start of my internship, I was suffering pretty severe imposter syndrome, like I was only asked to join them because I knew what Rails was. I didn't want people to realize that I didn't know very much about Rails, or Javascript for that matter. My first bit of actual work on the job was secluded; I feared people realizing that I Googled things like how to check if an element is in an array in Javascript.

This got completely flipped on its head. I have no idea when or how, but suddenly I decided that I will ask every question I had. Now, obviously I consulted Google first and tried to figure it out on my own. But, if that wasn't helping in a reasonable amount of time, I would ask. This also goes for pull requests, where I would put comments in my code that asked if there were other, better ways of doing what I wanted to do. From then on out, I became a far better developer. Just like anyone, I got worried that I was asking too many questions. That shouldn't matter. I focused on my learning and development, so long as the other engineers were willing to help.

Parallel: Don't spend too long on a problem

One small story at about my second week at the internship, I was writing tests for essentially the first time ever. Large testing frameworks and setups were new to me, but Rails tests were especially new to me. I was told to write a simple controller test to determine whether or not an element was showing up on a page, so I went through with writing the test and came to a dilemma: I needed to test what an instance variable was assigned to.

Now, this seems pretty simple to most: spend a few minutes Googling, if you can't figure it out, ask. But, for some reason I insisted on figuring it out myself, stressing out and continuing to Google from home. This made my imposter syndrome feel incredibly real; I couldn't figure out such a simple answer. After a time too embarassing to tell spent researching, I asked someone. Turns out there's something that can be used to get any assigned variables. It's a pretty simple method called assigns.

Lesson 3: Everyone is human

It's pretty well known that software developers are (mostly) human. But, for some reason, I got into the habbit of seeing these people like they're constantly annoyed at the intern. They just want to sit there and code. Any time they said "we can pair on that after lunch" just meant "why can't this guy do that?" The longer I went through my internship the more I realized that nobody would act like that. I put myself in their shoes and realized that if an intern came into my company, I would want to help them as much as possible, make them feel as comfortable as possible. It's not just a nicety to treat others with respect, it's a natural human reaction.

This realization largely happened when my engineering manager would have one on ones with me, continuously asking for feedback. Furthermore, he genuinely seemed to care about what I had been doing, how I was feeling, and what I wanted from the internship. I wasn't just a slave to do the small tickets that nobody wanted to do anymore; I was part of the team, someone to have lunch with.

Lesson 4: You're important

It's pretty weird to think that some intern is important to the company. It felt more like a ploy at first to trick people into doing annoying, boring tasks. What it turned out to be was a lot more complicated. There's obvious reasons that a company would want to hire an intern, none of which surprise me, such as cheaper labor than a normal employee and fewer strings attached. However, that's all I thought I was at first. In reality, you're important to the company even if you are an intern, especially at a smaller tech company. You work alongside real developers in order to deliver real products. You're a part of the team.

This extends beyond an internship as well. Any company that doesn't treat you like you're important is not worth your time. Much like how everybody has a story to tell, every person has leverage based on the simple fact that they're human and important. But, then again, maybe I'm just a young idealist.

Conclusions

I went into my first internship as a conflicted twenty year old, both with a large ego and massive imposter syndrome. There was no doubt in my mind that I would work the summer, make some decent money, then move on to the next school year. I thought that I had no more to learn about the real world. In retrospect, that seems so stupid. The summer of 2018 held a lot for me, from meeting some of the best people to working on cool projects. I also learned a lot about Rails, Javascript, testing, you name it. But, what I got most from my internship was the lessons I never thought I needed. As cliché as it sounds, this cocky 20 year old learned a lot about life from one summer internship.

The Art of a Personal Website

Evan Typanski — Sat, 14 Jul 2018 20:01:54 +0000

When I first started studying computer science, I felt as if a personal website was for web developers. That wasn't me, I wasn't about to devote my life to Ruby on Rails, so I left it at that. About a year later, I started college and realized it's more than that. Your personal website is far more than a showcase that you can program a website: in fact, my website is made using Jekyll, so all it's showing is html, css, and a tiny bit of Javascript. Nobody really cares that I can write some mean html.

My website uses a very simple system: about once or twice a year, I'll remake it. This may be making it using a different framework, like switching from Rails to Jekyll, or it may just be a visual overhaul. Each iteration I simply change the repository name to personal_site_x, where x is just the number of my current iteration. I didn't expect that to go on for more than 2 or 3 times, but I'm now at 4, and definitely looking to keep the trend going.

The variations are not simply because I stop liking the website. The variations in my website come about by the understanding that my website isn't just a branding tool, nor a display of my development prowess. In fact, those are some of the last things I want to show off with my website - I find portfolio sites to be bland, entirely free from personality. As a developer we have the freedom to push far beyond this, making a website that creates a timeline. The website is not the important part; the timeline is what's important.

Homepage of iteration 1 of my personal website: personal_site_1

The development timeline in a personal website is a simple display of what you've become as a developer. For example, the first iteration of my website was in Rails, when I was very much trying to learn as many skills as possible. Now, my website uses Jekyll, showing a maturity where I don't need to use an overkill solution in order to fulfill my desires to learn new skills. My first website in Jekyll used bootstrap, had pretty bad UX, and was bloated just in the html. My current version uses css grid, better programming practices, and a lot more useful technologies in order to achieve a similar goal. Each step shows an increase in maturity - it may not affect the end user very much, like the switch from Rails to Jekyll, but it's a way to see myself in the past.

A timeline then becomes a sandbox with each iteration. Your personal website is where you have the most freedom as a developer; the greatest ability to do whatever you want. I didn't get this at first. My first iteration was a shot at being noticed by employers - what first years had decent personal websites at UVA, much less using a powerful web framework like Rails? Well, not many, and it may have helped land an internship, but it really didn't get me much more from there. What the website became was a way to see a new website and say, "Wow, I really want to do something like that!" So, I did. That keeps happening, and it should never be stopped. My website is the sandbox that I can create something just because I thought it'd be cool to build. It's one of few places I can create that content and push it out for the public eye.

But, isn't a personal website great for employers and for branding? It is, I won't deny it. Especially if you're in web development or UX design, having a personal website is a must. This branding, however, tends to comes with the territory. I remade my website recently, largely because I wanted to make the code better, but also because I wanted to make the website more me. This is also why a personal website works wonders - it can show off who you really are. My old website was very safe and bland, mostly because I considered myself a safe and bland person. I'm stepping a little bit out of the box with the most recent iteration, and the next iteration will likely be a lot further out of the box, but we'll have to wait and see for that.

Homepage of iteration 3 of my personal website: personal_site_3

I'm no expert, but your personal website shouldn't just be for an employer. You shouldn't just care about what an employer thinks if they see your website. I wouldn't say go all out with an obnoxious pink background and unicorns everywhere, even if that is you. Just put less thought into how an employer would think and more thought into how your website helps you improve as a developer. Your growth and development through time is far more valuable than a safe site with your resume on it, and that's worth keeping in mind.

A Look At My Notes

Evan Typanski — Thu, 26 Apr 2018 14:46:24 +0000

Notetaking is a hotly debated topic, with many saying that taking notes by hand is simply better than digitally. This seems to be because the actual process of transcription tends to be more important than rereading the notes. I don't find that all that surprising - I hardly read back my notes simply because it doesn't seem to benefit me. I believe many (but not all) feel the same.

The actual process of writing is far slower than typing. I'll use myself as an example - I tested myself using this paragraph from a random typing speed site and made entirely sure not to try more than once. When I wrote the paragraph by hand, it took 2 minutes 20 seconds. Typing it with a fair number of corrections (21 according to the site) took 55 seconds, clocking at 79 words per minute, which is slower than normal. The takeaway? My typing speed is over twice as fast as my writing speed.

That doesn't even account for the messiness of my handwriting. I write like a five year old - my base line is all over the place and I need to look at the page. I clench the pencil too hard so it hurts. Typing, on the other hand, is always neat and comfortable. Since switching to Dvorak keyboard layout (see my other blog post), I have found that I am much more comfortable typing than with QWERTY. Basically, I get incredibly tired writing, but not typing.

We can keep going on how much better typing is because you can relay more information in a neater format. But, what's the benefit of writing? I said previously that I don't write my notes to reread them. I write notes to retain information the second I learn it. Studies show that writing notes simply lets you retain more information. I would likely agree with that finding for most individuals. The primary reasons seem not to be a product of the laptop, but instead a product of how the individuals use the laptop.

How I Take Notes

A short history, I learned LaTeX in Fall 2016 in order to take notes and do homeworks more efficiently in my discrete math class. This was the beginning of my first year at college. Before I learned LaTeX, I took notes using my laptop, but generally in simple Microsoft products. This was incredibly cumbersome for equations and prettiness. I downloaded MikTex for Windows and struggled through the first month of not knowing how to do practically anything. By the end of my first year, most of my notes were typed with LaTeX and generally were pretty ok.

Here's an example of some discrete math that I took my first year. These notes were often rewritten to make more clear as well (part of how I study):

I'm definitely not going to claim these are perfect notes, but it certainly provided a good reference as well as forcing me to write down what each law was. I likely did this after the class that we learned it, but this was very common for my notes: to have every piece of information.

My more recent notes are different based on the class. For example, in algorithms, pictures are often very useful, but I'm not about to draw a flow graph and scan it into my notes. Thus, I just describe it. The key is, however, I ensure that I learn the content and then write my translation of the lecture. It's similar to what you have to do when hand writing notes, but I do it voluntarily while typing. The following is an example of the result:

These notes seem obviously less curated than my discrete math notes - I take that as a sign of maturity. I've learned that I can't just write everything down. I could make a table with definitions and have a huge professional notebook that can essentially also be a textbook. But, I'm not going to look back at these notes that much, so why would I? I might ensure that my intuition now matches my intuition when I first learned the concepts, but other than that these notes will likely just have their use from my writing them in the first place. I don't need to make it awesome and pretty - I need to make it easy to do what I need to do.

The main increase in benefit occured when I switched from using MikTex to using Vim on a Linux environment. The main reason is that Vim helps me write notes even more efficiently, should I need to change something. This created a problem because I didn't know how to create a PDF efficiently other than just compiling the notes with pdflatex algo.tex. This was fixed when I found Vim Latex Live Preview, a Vim plugin that recompiles the PDF document as you type (after a certain amount of inactivity at least). It doesn't use a ton of computing power and it feels very natural. This has been what's changed my notetaking from being pretty to being efficient as well. Combine this with a tiling window manager and this setup is perfect for ensuring your notes serve their purpose, compile correctly, and look how you want them to look.

I won't go too much into how I organize sections and lecture dates, mostly because that's unimportant. It's loosely correlated with the textbook in most cases. But, I will say that taking my notes in LaTeX has made it more likely for me to look back at my notes, as I feel more comfortable grabbing an equation from my notes rather than lecture slides. This gives me the best of both worlds: so long as I do not get distracted during class and I make an effort to write the notes in my own words, I've found this works for me. It might not work for everyone, but it definitely works for me.