Language + Compiler Construction

Language + Compiler Construction
FR
  • Rejestracja:ponad 2 lata
  • Ostatnio:około rok
  • Postów:6
9

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

Kopiuj
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;
}

screenshot-20220730170628.png

Generowane jest takie IR:

screenshot-20220730164811.png
Które następnie LLVM Optimizer optymalizuje do

Kopiuj
; 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")):
screenshot-20220730165400.png

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

screenshot-20220730170417.png

Wygenerowany Graphviz dla pierwszego kodu:

screenshot-20220730170552.png


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

edytowany 14x, ostatnio: Koziołek
Aventus
  • Rejestracja:prawie 9 lat
  • Ostatnio:ponad 2 lata
  • Lokalizacja:UK
  • Postów:2235
3

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.


Na każdy złożony problem istnieje rozwiązanie które jest proste, szybkie i błędne.
edytowany 1x, ostatnio: Aventus
ZD
  • Rejestracja:około 3 lata
  • Ostatnio:ponad rok
  • Postów:2310
1
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.


If you put a million monkeys at a million keyboards, one of them will eventually write a Java program - the rest of them will write Perl
FR
  • Rejestracja:ponad 2 lata
  • Ostatnio:około rok
  • Postów:6
0

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

screenshot-20220731114208.png

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

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

Przykład po zmianach:

Kopiuj
namespace Test

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

screenshot-20220731113605.png

Kopiuj
namespace Test

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

poprawnie wywala błąd

Kopiuj
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
edytowany 8x, ostatnio: Koziołek
FR
@MarekR22: tutaj również nie ma samego kodu jako obrazek, chodzi o error message :P
MarekR22
To samo się tyczy error message. Nawet pod linkiem jest to opisane: Nie powinno się zamieszczać kodu (lub błędów/wyjątków/wiadomości, plików logów/konfiguracji/projektu, lub czegokolwiek co może być reprezentowane w postaci tekstowej) jako obrazów
FR
@MarekR22: ten cały guideline wydaje się być bardziej z perspektywy pytającego np. o pomoc z jakimś fragmentem kodu. Ja tutaj nie pytam, a chciałem pokazać również UI, aby to było tak bardziej namacalne.
MarekR22
1. Wygodniej jest tobie (łatwiej sie kopiuje tekst niż obrazki). 2. łatwiej się wyszykije (tekst jest indeksowany przez wyszukiwarki). 3. Łatwiej się czyta (ja ledwo widzę, tą czerwoną czcionkę). - po prostu przeczytaj ten cały wątek, te "wytyczne" są jasno uzasadnione. Zresztą ja tylko przetłumaczyłem wątek ze stackoveflow i dostosowałem do potrzeb tego forum.
Pixello
  • Rejestracja:prawie 10 lat
  • Ostatnio:4 miesiące
  • Lokalizacja:Podkarpacie
  • Postów:448
1

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

FR
  • Rejestracja:ponad 2 lata
  • Ostatnio:około rok
  • Postów:6
0

@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)

Kopiuj
public abstract class BaseEmitter
{
    protected readonly IMessagesPrinter _printer;

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

    public abstract Result<string> Emit(Node node);
}
edytowany 4x, ostatnio: French
Pixello
Dobra, nie doczytałem, że to całkowicie inny język jest tłumaczony na LLVM, myślałem, że C# tłumaczysz na LLVM ;)
FR
  • Rejestracja:ponad 2 lata
  • Ostatnio:około rok
  • Postów:6
0

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

edytowany 4x, ostatnio: French
FR
  • Rejestracja:ponad 2 lata
  • Ostatnio:około rok
  • Postów:6
0

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

Kopiuj
namespace Test

public container Position
{
	int X,
	int Y
}

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

	return location.X; 
}

screenshot-20220807234026.png

screenshot-20220807234905.png

Błąd gdy nie wszystko zostanie zainicjalizowane

Kopiuj
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...

edytowany 5x, ostatnio: Koziołek
FR
  • Rejestracja:ponad 2 lata
  • Ostatnio:około rok
  • Postów:6
0

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

Template:

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

Użycie:

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

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

Lowering:

Kopiuj
public container Position_Int
{
	int X,
	int Y
}

public container Position_String
{
	string X,
	string Y
}
edytowany 1x, ostatnio: French
SZ
  • Rejestracja:około 14 lat
  • Ostatnio:około 3 godziny
  • Postów:179
0

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

Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)