Language + Compiler Construction

Wrzucam kod zrealizowanego w jakoś 20% projektu języka programowania oraz implementacji kompilatora w C# - ok. 100 commitów + CI bot.

Jako compilation target wybrane jest WebAssembly, a jako język pośredni użyty jest LLVM IR.

LLVM IR jest emitowane z ręki, a WebAssembly już przy pomocy LLVMa

Parser jest handwritten

Przykładowo dla takiego kodu

namespace Test

public int Test(int a, int b)
{
	if (a > b)
	{
		return a + b;
	}
	else
	{
		return a - Qwert();
	}
}

public int Qwert()
{
	return 10 * 10;
}

Generowane jest takie IR:

Które następnie LLVM Optimizer optymalizuje do

; ModuleID = 'main.ll'
source_filename = "main.ll"

; Function Attrs: nofree norecurse nosync nounwind readnone willreturn mustprogress
define dso_local i32 @Test(i32 %0, i32 %1) local_unnamed_addr #0 {
  %3 = icmp sgt i32 %0, %1
  %4 = select i1 %3, i32 %1, i32 -100
  %5 = add i32 %4, %0
  ret i32 %5
}

; Function Attrs: nofree norecurse nosync nounwind readnone willreturn mustprogress
define dso_local i32 @Qwert() local_unnamed_addr #0 {
  ret i32 100
}

attributes #0 = { nofree norecurse nosync nounwind readnone willreturn mustprogress }

I użycie na stronie (fetch("main.wasm")):

Wrzucam to głównie po to, aby ktoś ciekawy mógł zobaczyć jak podejść do tego typu problemu, ale też aby mieć większą motywację do pisania tego.

Jako że nie oczekuje że ktoś będzie się tym chciał pobawić, co najwyżej przeglądnąć kod, to nie tracę czasu na pisanie jak to odpalić (chociaż do samego wyemitowania IR powinno działać out of the box bez żadnych konfiguracji / zabaw z LLVMem). Jeżeli będzie potrzeba, to dajcie znać .

Generalnie jest tutaj bardzo dużo czasochłonnych rzeczy do zrobienia, typu:

• CLI
• Language Server Protocol Support (VS Code)
• Zaprojektować język (OOP? FP? Other?)
• Dokumentacja Języka
• Podpięcie do repo binarek LLVMa, aby nie trzeba było samemu go kompilować
• Przepisanie niektórych rzeczy (Type Checker Pass, Expression Builder)
• Usprawnienie CI bota który po każdym commicie podnosi wersję projektu oraz wpushowuje dane z benchmarków
• Ogarnięcie Repo
• Rozważenie czy nie dodać też wsparcia dla czego innego niż WASM, aby to np. można było bezpośrednio z CLI używać jak normalne programy. Wymagałoby to dodania wsparcia dla jakichś printfów itd.
• Multi File Support (not tested yet)
• Parallel Lexer
• wiele więcej

Z rzeczy które są już w jakimś stopniu zrobione:

• Głównie fundamenty
• Jakaś infrastruktura
• Expression Builder,
• Otypowywanie drzewka,
• Passes,
• Graphviz code gen,
• LLVM IR code gen,
• Jakaś obsługa błędów,
• bieda CI do benchmarków

Wygenerowany Graphviz dla pierwszego kodu:

Czy warto w takie coś się pobawić?

Uważam że tak, pomimo tego że jest to czasochłonne gdy chcemy się na ile się da zbliżyć do prawdziwych projektów, oraz że wymaga trochę wstępu teoretycznego, to żaden inny projekt nie dał mi tyle, polecam :P

Przy okazji podczas developmentu tego projektu znalazłem różne bugi / dziwne zachowania w np. .NET CLI czy bibliotekach typu BenchmarkDotNet :D

Wypowiem się zanim przyjdą tutaj tacy, co będą chcieli Cię odwieść od pomysłu bo "po co", "na co" i "zobacz ile jest gotowych rozwiązań".

Jeśli sprawia Ci to przyjemność to chociażby dla tego warto, reszta ma drugorzędne znaczenie.

Aventus napisał(a):

Wypowiem się zanim przyjdą tutaj tacy, co będą chcieli Cię odwieść od pomysłu bo "po co", "na co" i "zobacz ile jest gotowych rozwiązań".

Jeśli sprawia Ci to przyjemność to chociażby dla tego warto, reszta ma drugorzędne znaczenie.

Można mieć frajdę w konstruowaniu języków / komplatorów, oczywiście tak. Może przyjść moment, że to *) się przyda jak najbardziej, np DSL do jakiejś aplikacji

*) wiedza i doświadczenie, a nie akurat zaimplementowany język.

Dodałem wstępne wsparcie dla var oraz przypisywania zmiennych, bo aktualnie nawet taki kod nie działał

Coś pomajstrowałem z sprawdzaniem czy expression ma znaną wartość np (var a = 5 vs function param) oraz poprawiłem generowane IR dla voida (brakowało ret void) :P

define void @bar() comdat($foo) {
  ret void
}

Przykład po zmianach:

namespace Test

public int TestVar()
{
	var q = 1;
	var w = 2;
	var c = q + w;
	return c;
}

namespace Test

public int TestVar()
{
	var q = "Asd";
	var w = 2;
	var c = q + w;
	return c;
}

poprawnie wywala błąd

Undefined operator - 'Addition' between 'Type: string' and 'Type: int32' at line number '7' at position '10' at character 'q'.
Type 'var' for variable with name 'c' is not found. at line number '8' at position '9' at character 'c'. // wypadałoby rozważyć wywalanie tego błędu, aby się nie mnożyły

Czemu IR llvm jest z ręki, a nie jako translacja c# bytekodu?

@Pixello:

Sugerujesz abym generował kod C# i zamieniał go na LLVM IR?

Ma to sens, duży, zastanawiałem się nad tym (albo jakimś innym językiem typu C), bo znacznie ułatwiłoby mi to pisanie emittera

ale z drugiej strony byłby to kolejny tool w całym chainie, na który nie miałbym wpływu, a w dodatku chciałem zdobyć trochę doświadczenia z LLVM IR.
W aktualnym podejściu czuje że mam większą kontrolę nad tym wszystkim.

Jako że Emitter to tylko taki BaseClass, to nie ma żadnego problemu aby stworzyć CsharpEmitter wygenerować kod C# i np. dodać flagę --ir=[csharp/llvm] aby użyć innego tool chainu do wygenerowania WASM (w tym przypadku C# -> LLVM -> WASM zamiast LLVM -> WASM)

public abstract class BaseEmitter
{
    protected readonly IMessagesPrinter _printer;

    protected BaseEmitter(IMessagesPrinter printer)
    {
        _printer = printer;
    }

    public abstract Result<string> Emit(Node node);
}

Kolejne kroki:

Dodanie jakiegoś kontenera na dane, ale na początek bez zachowania (brak metod/funkcji)

https://mapping-high-level-constructs-to-llvm-ir.readthedocs.io/en/latest/basic-constructs/structures.html

Przy okazji może jakieś templatki udające generyki, bo nie wiem jak zrobić prawdziwe generyki, a więc podszedłbym do tego od strony templatek, bo to jest na etapie kompilacji. Ewentualnie zobaczę do czego się kompilują inne języki

https://stackoverflow.com/questions/36347/what-are-the-differences-between-generic-types-in-c-and-java

https://docs.microsoft.com/en-us/cpp/extensions/generics-and-templates-visual-cpp

Nowe rzeczy: Data Container, New keyword, Property/Field Use -> return location.X

namespace Test

public container Position
{
	int X,
	int Y
}

public int TestVar()
{
	var location = new Position
	{
		X = 75,
		Y = 27
	};

	return location.X; 
}

Błąd gdy nie wszystko zostanie zainicjalizowane

namespace Test

public container Position
{
	int X,
	int Y
}

public int TestVar()
{
	var location = new Position
	{
		X = 75,
	};

	return location.X; 
}

You need to initialize all properties. at line number...

Czy tworzenie kodu dla każdego typu jako implementacja generyków ma sens? czy w przyszłości to może być problematyczne?

Template:

public container Position<T>
{
	T X,
	T Y
}

Użycie:

var location = new Position<int>
{
	X = 75,
};

var location2 = new Position<string>
{
	X = "75",
};

Lowering:

public container Position_Int
{
	int X,
	int Y
}

public container Position_String
{
	string X,
	string Y
}

Super pomysł!. Zazdro! Ja niestety nie mam czasu :(