Summary Files Commits Branches @commit @diff @stats
path: root / src / blog
diff options
context:
space:
mode:
Commit1c12358c1afb9a38138ed6c07667638e9d621426 (patch)
Author
 Syndamia <kamen@syndamia.com>
2025-08-18 10:05:44 +0300
Committer
 Syndamia <kamen@syndamia.com>
2025-08-18 10:05:44 +0300
Files94c686e5405a3e78b3dbcf54ac437e6621cf556e /src/blog
syndamia.com-1c12358c1afb9a38138ed6c07667638e9d621426.tar
syndamia.com-1c12358c1afb9a38138ed6c07667638e9d621426.tar.gz
syndamia.com-1c12358c1afb9a38138ed6c07667638e9d621426.zip
Parent3e42b21587d675736439d9240c8389c22efa1a5f (diff)
feat(blog): Converted all posts to dunbar
16 files changed, 995 insertions, 916 deletions
-rw-r--r--src/blog/mundus-first-shot-at-gamedev/basic-concepts.du (renamed from src/blog/mundus-first-shot-at-gamedev/basic-concepts.md)42
-rw-r--r--src/blog/mundus-first-shot-at-gamedev/index.du55
-rw-r--r--src/blog/mundus-first-shot-at-gamedev/index.md44
-rw-r--r--src/blog/mundus-first-shot-at-gamedev/introduction.du55
-rw-r--r--src/blog/mundus-first-shot-at-gamedev/introduction.md44
-rw-r--r--src/blog/mundus-first-shot-at-gamedev/timeline.du (renamed from src/blog/mundus-first-shot-at-gamedev/timeline.md)35
-rw-r--r--src/blog/mundus-first-shot-at-gamedev/user-interface.du92
-rw-r--r--src/blog/mundus-first-shot-at-gamedev/user-interface.md85
-rw-r--r--src/blog/plan9-in-linux-mouse-menus/index.du (renamed from src/blog/plan9-in-linux-mouse-menus/index.md)172
-rw-r--r--src/blog/sane-explanation-of-compilers/index.du (renamed from src/blog/sane-explanation-of-compilers/index.md)3
-rw-r--r--src/blog/sane-explanation-of-compilers/part-1.du (renamed from src/blog/sane-explanation-of-compilers/part-1.md)794
-rw-r--r--src/blog/switchut-izgorq/index.du (renamed from src/blog/switchut-izgorq/index.md)17
-rw-r--r--src/blog/taming-the-fun-too/index.du (renamed from src/blog/taming-the-fun-too/index.md)66
-rw-r--r--src/blog/the-physics-behind-a-black-hole-shader/index.du (renamed from src/blog/the-physics-behind-a-black-hole-shader/index.md)274
-rw-r--r--src/blog/thinkpad-x270-my-favorite-machine/index.du (renamed from src/blog/thinkpad-x270-my-favorite-machine/index.md)96
-rw-r--r--src/blog/when-a-language-forces-simpler-thinking/index.du (renamed from src/blog/when-a-language-forces-simpler-thinking/index.md)37
diff --git a/src/blog/mundus-first-shot-at-gamedev/basic-concepts.md b/src/blog/mundus-first-shot-at-gamedev/basic-concepts.du
index ef8995e..c09c44f 100644
--- a/src/blog/mundus-first-shot-at-gamedev/basic-concepts.md
+++ b/src/blog/mundus-first-shot-at-gamedev/basic-concepts.du
@@ -1,18 +1,25 @@
# Basic Concepts - Mundus: My first shot at game development
-## [*Due for rework*](/rework.html)
+'define expected-reading 5 min
+'define created 21 July 2020
+'define edited 25 November 2020
+[$pagenav]
-[`<<`](./) || [`< User Interface`](./user-interface.html)
+'define start_url ./
+'define prev_link [url ./user-interface.html User Interface]
+[$pagination_end]
-<br>
+[$due_for_rework]
-## Contents
+\n
-1. [Tiles](#tiles)
-2. [Layers and superlayers](#layers-and-superlayers)
-3. [Inventory](#inventory)
-4. [Crafting](#crafting)
-5. [Event logs](#event-logs)
+.contents
+.numbered
+1. [url #tiles Tiles]
+2. [url #layers-and-superlayers Layers and superlayers]
+3. [url #inventory Inventory]
+4. [url #crafting Crafting]
+5. [url #event-logs Event logs]
Even though the game is quite unfinished, there are still a fair bit of mechanics I've developed.
@@ -20,8 +27,9 @@ Even though the game is quite unfinished, there are still a fair bit of mechanic
The in game world (map) is composed of squares, called tiles. Everything is a type of tile. There are two main categories of tiles: items and mobs. Mobs (mobile object for short) are the creatures in the game, while items are everything else, from the tools, to the trees.
-There is only one type of mob tile and that is `MobTiles`. All mobs, with the exception of the player, have the same functionality and properties:
+There is only one type of mob tile and that is `[MobTiles]`. All mobs, with the exception of the player, have the same functionality and properties:
+:unordered
- health - if it drops to or below 0, they die
- defence - reduces or completely negates certain amounts of damage
@@ -46,6 +54,7 @@ Items, however, are divided into:
- Tool tiles: used for interacting (changing) the environment of the world. In your inventory they are surrounded in blue. There are four types, depending on their capabilities:
+ :unordered
- Shovels: you dig up (remove) ground tiles from ground layer
- Axes: used to break (remove) wooden structures (trees, ladders, ...)
@@ -54,28 +63,34 @@ Items, however, are divided into:
- Swords: used for damaging (killing) mobs
+
+
## Layers and superlayers
The in game world (map) is composed of superlayers. Superlayers represent each elevation level in the world. Conceptually, there are in total 5 superlayers: Space, Sky, Land, Underground and ???, although only Sky, Land and Underground are implemented.
Each superlayer is composed of 3 layers: Structure, Mob and Ground. Each one of them contains a specific type of tiles, meaning structure tiles are only stored in "structure" layer, ground tiles only in "ground" layer and mob tiles only in "mob" layer. Even though, they are different layers, there are some rules for the interaction between them:
-- **Mobs cannot be on top of structures**, except if the structure is marked as "walkable"
+:unordered
+- =[Mobs cannot be on top of structures]=, except if the structure is marked as "walkable"
+
+- =[Structures cannot be placed on top of mobs]=. "Walkable" structures can be placed below a mob.
-- **Structures cannot be placed on top of mobs**. "Walkable" structures can be placed below a mob.
+- =[Structures cannot be placed on top of holes]= (empty spots in the ground layer), =[except if they are "climable"]=, in which case they will be placed in the structure layer on the superlayer below. Mobs also cannot reside on top of holes (they fall to the superlayer below)
-- **Structures cannot be placed on top of holes** (empty spots in the ground layer), **except if they are "climable"**, in which case they will be placed in the structure layer on the superlayer below. Mobs also cannot reside on top of holes (they fall to the superlayer below)
## Inventory
Each mob can store certain amount of item tiles. That is done in it's inventory. The inventory is comprised of 4 parts:
+:unordered
- Hotbar: a place for having access to a small amount of items at all times. It can contain all item tiles, except groundtiles
- Items: used for bulk storage, it can hold any type of item tile and is the largest part of the inventory
- Accessories and Gear: used only for storing gear tiles
+
## Crafting
Creating new item tiles is done through crafting. Each craftable item requires one to five different materials in different quantities. The item tiles must be inside the "items" part of your inventory.
@@ -83,4 +98,3 @@ Creating new item tiles is done through crafting. Each craftable item requires o
## Event logs
Certain actions you do in the game are stored in memory as messages (logs). They are also used to give you information that you couldn't get otherwise, for example, there is a log when you can't climb up a superlayer because a mob is blocking the way, or when you damage/kill a structure or mob.
-
diff --git a/src/blog/mundus-first-shot-at-gamedev/index.du b/src/blog/mundus-first-shot-at-gamedev/index.du
new file mode 100644
index 0000000..4da40e0
--- /dev/null
+++ b/src/blog/mundus-first-shot-at-gamedev/index.du
@@ -0,0 +1,55 @@
+# Introduction - Mundus: My first shot at game development
+
+'define expected-reading 2 min
+'define created 21 July 2020
+'define edited 25 November 2020
+[$pagenav]
+
+'define next_link [url ./timeline.html Timeline]
+[$pagination_start]
+
+[$due_for_rework]
+
+\n
+
+:contents
+:numbered
+1. [url ./timeline.html Timeline]
+2. [url ./user-interface.html User Interface]
+ .numbered
+ 1. [url ./user-interface.html#main-screen Main screen]
+ 2. [url ./user-interface.html#create-new-game Create new game]
+ 3. [url ./user-interface.html#game-window Game Window]
+ 4. [url ./user-interface.html#map-menu Map menu]
+ 5. [url ./user-interface.html#inventory-menu Inventory menu]
+ 6. [url ./user-interface.html#crafting-menu Crafting menu]
+
+3. [url ./basic-concepts.html Basic Concepts]
+ .numbered
+ 1. [url ./basic-concepts.html#tiles Tiles]
+ 2. [url ./basic-concepts.html#layers-and-superlayers Layers and superlayers]
+ 3. [url ./basic-concepts.html#inventory Inventory]
+ 4. [url ./basic-concepts.html#crafting Crafting]
+ 5. [url ./basic-concepts.html#event-logs Event logs]
+
+
+
+I have been toying with the idea of making a game ever since my first exposure to programming. The [url https://gitlab.com/Syndamia/Shower/-/tree/master/ARK%20(2015 earliest piece of code]) I ever wrote was about replicating a computer boot up sequence from the video game [url https://store.steampowered.com/app/282140/SOMA/ SOMA]. I developed it in 2015, solid 3 years before my first proper introduction to software development.
+
+Five years later, in early 2020, I had to make a project for an exam. I (initially) had about a month to complete it and the only requirements were technical: utilize a database with at least x tables, employ a specific design pattern, etc. Fairly quickly I decided upon making a "minecraftian" game: 2D sandbox where you could fight, craft, build, eat and explore.
+
+I called it [url https://gitlab.com/Syndamia/Mundus Mundus] and it took me around 3 months to complete and consisted of more than 2000 lines of code. Although these metrics aren't very impressive in the real world, they were a monumental achievement for me. In the beginning I planned on developing it into a fully fledged game, but that never happened.
+
+Nevertheless, this journey was very important to me, hence writing this multi-page article.
+
+=[Link to the source code]=: [url https://gitlab.com/Syndamia/Mundus GitLab]
+
+## Screenshots
+
+<div style="display: flex; overflow-x: scroll; align-items: center">
+ <img src="./img/small-game-window.png" style="height: 100%; flex: 1; margin-right: 0.5em">
+ <img src="./img/map-menu.png" style="height: 100%; flex: 1; margin-right: 0.5em">
+ <img src="./img/inventory-menu.png" style="height: 100%; flex: 1;">
+</div>
+
+*[Screenshots are made on Linux Mint Cinnamon with the Mint-Y theme]*
diff --git a/src/blog/mundus-first-shot-at-gamedev/index.md b/src/blog/mundus-first-shot-at-gamedev/index.md
deleted file mode 100644
index 2c623e5..0000000
--- a/src/blog/mundus-first-shot-at-gamedev/index.md
+++ /dev/null
@@ -1,44 +0,0 @@
-# Introduction - Mundus: My first shot at game development
-
-[`Timeline >`](./timeline.html)
-
-<br>
-
-[*Due for rework*](/rework.html)
-
-## Contents
-
-1. [Timeline](./timeline.html)
-2. [User Interface](./user-interface.html)
- 1. [Main screen](./user-interface.html#main-screen)
- 2. [Create new game](./user-interface.html#create-new-game)
- 3. [Game Window](./user-interface.html#game-window)
- 4. [Map menu](./user-interface.html#map-menu)
- 5. [Inventory menu](./user-interface.html#inventory-menu)
- 6. [Crafting menu](./user-interface.html#crafting-menu)
-3. [Basic Concepts](./basic-concepts.html)
- 1. [Tiles](./basic-concepts.html#tiles)
- 2. [Layers and superlayers](./basic-concepts.html#layers-and-superlayers)
- 3. [Inventory](./basic-concepts.html#inventory)
- 4. [Crafting](./basic-concepts.html#crafting)
- 5. [Event logs](./basic-concepts.html#event-logs)
-
-I have been toying with the idea of making a game ever since my first exposure to programming. The [earliest piece of code](https://gitlab.com/Syndamia/Shower/-/tree/master/ARK%20(2015)) I ever wrote was about replicating a computer boot up sequence from the video game [SOMA](https://store.steampowered.com/app/282140/SOMA/). I developed it in 2015, solid 3 years before my first proper introduction to software development.
-
-Five years later, in early 2020, I had to make a project for an exam. I (initially) had about a month to complete it and the only requirements were technical: utilize a database with at least x tables, employ a specific design pattern, etc. Fairly quickly I decided upon making a "minecraftian" game: 2D sandbox where you could fight, craft, build, eat and explore.
-
-I called it [Mundus](https://gitlab.com/Syndamia/Mundus) and it took me around 3 months to complete and consisted of more than 2000 lines of code. Although these metrics aren't very impressive in the real world, they were a monumental achievement for me. In the beginning I planned on developing it into a fully fledged game, but that never happened.
-
-Nevertheless, this journey was very important to me, hence writing this multi-page article.
-
-**Link to the source code**: [GitLab](https://gitlab.com/Syndamia/Mundus)
-
-## Screenshots
-
-<div style="display: flex; overflow-x: scroll; align-items: center">
- <img src="./img/small-game-window.png" style="height: 100%; flex: 1; margin-right: 0.5em">
- <img src="./img/map-menu.png" style="height: 100%; flex: 1; margin-right: 0.5em">
- <img src="./img/inventory-menu.png" style="height: 100%; flex: 1;">
-</div>
-
-*Screenshots are made on Linux Mint Cinnamon with the Mint-Y theme*
diff --git a/src/blog/mundus-first-shot-at-gamedev/introduction.du b/src/blog/mundus-first-shot-at-gamedev/introduction.du
new file mode 100644
index 0000000..4da40e0
--- /dev/null
+++ b/src/blog/mundus-first-shot-at-gamedev/introduction.du
@@ -0,0 +1,55 @@
+# Introduction - Mundus: My first shot at game development
+
+'define expected-reading 2 min
+'define created 21 July 2020
+'define edited 25 November 2020
+[$pagenav]
+
+'define next_link [url ./timeline.html Timeline]
+[$pagination_start]
+
+[$due_for_rework]
+
+\n
+
+:contents
+:numbered
+1. [url ./timeline.html Timeline]
+2. [url ./user-interface.html User Interface]
+ .numbered
+ 1. [url ./user-interface.html#main-screen Main screen]
+ 2. [url ./user-interface.html#create-new-game Create new game]
+ 3. [url ./user-interface.html#game-window Game Window]
+ 4. [url ./user-interface.html#map-menu Map menu]
+ 5. [url ./user-interface.html#inventory-menu Inventory menu]
+ 6. [url ./user-interface.html#crafting-menu Crafting menu]
+
+3. [url ./basic-concepts.html Basic Concepts]
+ .numbered
+ 1. [url ./basic-concepts.html#tiles Tiles]
+ 2. [url ./basic-concepts.html#layers-and-superlayers Layers and superlayers]
+ 3. [url ./basic-concepts.html#inventory Inventory]
+ 4. [url ./basic-concepts.html#crafting Crafting]
+ 5. [url ./basic-concepts.html#event-logs Event logs]
+
+
+
+I have been toying with the idea of making a game ever since my first exposure to programming. The [url https://gitlab.com/Syndamia/Shower/-/tree/master/ARK%20(2015 earliest piece of code]) I ever wrote was about replicating a computer boot up sequence from the video game [url https://store.steampowered.com/app/282140/SOMA/ SOMA]. I developed it in 2015, solid 3 years before my first proper introduction to software development.
+
+Five years later, in early 2020, I had to make a project for an exam. I (initially) had about a month to complete it and the only requirements were technical: utilize a database with at least x tables, employ a specific design pattern, etc. Fairly quickly I decided upon making a "minecraftian" game: 2D sandbox where you could fight, craft, build, eat and explore.
+
+I called it [url https://gitlab.com/Syndamia/Mundus Mundus] and it took me around 3 months to complete and consisted of more than 2000 lines of code. Although these metrics aren't very impressive in the real world, they were a monumental achievement for me. In the beginning I planned on developing it into a fully fledged game, but that never happened.
+
+Nevertheless, this journey was very important to me, hence writing this multi-page article.
+
+=[Link to the source code]=: [url https://gitlab.com/Syndamia/Mundus GitLab]
+
+## Screenshots
+
+<div style="display: flex; overflow-x: scroll; align-items: center">
+ <img src="./img/small-game-window.png" style="height: 100%; flex: 1; margin-right: 0.5em">
+ <img src="./img/map-menu.png" style="height: 100%; flex: 1; margin-right: 0.5em">
+ <img src="./img/inventory-menu.png" style="height: 100%; flex: 1;">
+</div>
+
+*[Screenshots are made on Linux Mint Cinnamon with the Mint-Y theme]*
diff --git a/src/blog/mundus-first-shot-at-gamedev/introduction.md b/src/blog/mundus-first-shot-at-gamedev/introduction.md
deleted file mode 100644
index f88abff..0000000
--- a/src/blog/mundus-first-shot-at-gamedev/introduction.md
+++ /dev/null
@@ -1,44 +0,0 @@
-# Introduction - Mundus: My first shot at game development
-
-[`Timeline >`](./timeline.html)
-
-<br>
-
-## Contents
-
-[*Due for rework*](/rework.html)
-
-1. [Timeline](./timeline.html)
-2. [User Interface](./user-interface.html)
- 1. [Main screen](./user-interface.html#main-screen)
- 2. [Create new game](./user-interface.html#create-new-game)
- 3. [Game Window](./user-interface.html#game-window)
- 4. [Map menu](./user-interface.html#map-menu)
- 5. [Inventory menu](./user-interface.html#inventory-menu)
- 6. [Crafting menu](./user-interface.html#crafting-menu)
-3. [Basic Concepts](./basic-concepts.html)
- 1. [Tiles](./basic-concepts.html#tiles)
- 2. [Layers and superlayers](./basic-concepts.html#layers-and-superlayers)
- 3. [Inventory](./basic-concepts.html#inventory)
- 4. [Crafting](./basic-concepts.html#crafting)
- 5. [Event logs](./basic-concepts.html#event-logs)
-
-I have been toying with the idea of making a game ever since my first exposure to programming. The [earliest piece of code](https://gitlab.com/Syndamia/Shower/-/tree/master/ARK%20(2015)) I ever wrote was about replicating a computer boot up sequence from the video game [SOMA](https://store.steampowered.com/app/282140/SOMA/). I developed it in 2015, solid 3 years before my first proper introduction to software development.
-
-Five years later, in early 2020, I had to make a project for an exam. I (initially) had about a month to complete it and the only requirements were technical: utilize a database with at least x tables, employ a specific design pattern, etc. Fairly quickly I decided upon making a "minecraftian" game: 2D sandbox where you could fight, craft, build, eat and explore.
-
-I called it [Mundus](https://gitlab.com/Syndamia/Mundus) and it took me around 3 months to complete and consisted of more than 2000 lines of code. Although these metrics aren't very impressive in the real world, they were a monumental achievement for me. In the beginning I planned on developing it into a fully fledged game, but that never happened.
-
-Nevertheless, this journey was very important to me, hence writing this multi-page article.
-
-**Link to the source code**: [GitLab](https://gitlab.com/Syndamia/Mundus)
-
-## Screenshots
-
-<div style="display: flex; overflow-x: scroll; align-items: center">
- <img src="./img/small-game-window.png" style="height: 100%; flex: 1; margin-right: 0.5em">
- <img src="./img/map-menu.png" style="height: 100%; flex: 1; margin-right: 0.5em">
- <img src="./img/inventory-menu.png" style="height: 100%; flex: 1;">
-</div>
-
-*Screenshots are made on Linux Mint Cinnamon with the Mint-Y theme*
diff --git a/src/blog/mundus-first-shot-at-gamedev/timeline.md b/src/blog/mundus-first-shot-at-gamedev/timeline.du
index cb3da01..49ef2fc 100644
--- a/src/blog/mundus-first-shot-at-gamedev/timeline.md
+++ b/src/blog/mundus-first-shot-at-gamedev/timeline.du
@@ -1,56 +1,65 @@
# Timeline - Mundus: My first shot at game development
-[`< Introduction`](./) || [`User Interface >`](./user-interface.html)
+'define expected-reading 6 min
+'define created 21 July 2020
+'define edited 25 November 2020
+[$pagenav]
-<br>
+'define prev_link [url ./ Introduction]
+'define next_link [url ./user-interface.html User Interface]
+[$pagination_second]
+
+[$due_for_rework]
+
+\n
As mentioned, I had big plans for Mundus, so I wanted to make sure it would be well planned. But at the same time, the project took too much energy and I often had holes of no development time. This is an overview of the development "cycle" I went through.
-> ***08.02.2020***&emsp;Day 0, Hour 0
+.quote *[=[08.02.2020]=]*&emsp;Day 0, Hour 0
At this point of time, I was still studying software development in a national program. On this exact day, we had the first lecture of a new module, where it was announced we would have to make a project for the exam. Up until this point of time, our exams constituted of predefined programming exercises for which we would be given a couple of hours to complete and would be checked by an online platform.
I immediately began brainstorming and by the end of the day, I had decided upon the project I would be developing.
-> ***12.02.2020***&emsp;Day 4
+.quote *[=[12.02.2020]=]*&emsp;Day 4
Before Mundus I had experimented with making games, but mostly in the command line. This time was going to be different. Up until this day, I was only researching and trying out different technologies to make my game with.
-Initially I spent a lot of time with Unity, but the original time constraints and my lack of knowledge with the game engine discouraged me from continuing with it. Subsequently, I got discouraged from using any game engine and settled for `GtkSharp 2.0`. Now, this is widget toolkit, not even close to a game engine, but hey, it was much better than the command line, it was simple and shipped with the IDE I was using at the time.
+Initially I spent a lot of time with Unity, but the original time constraints and my lack of knowledge with the game engine discouraged me from continuing with it. Subsequently, I got discouraged from using any game engine and settled for `[GtkSharp 2.0]`. Now, this is widget toolkit, not even close to a game engine, but hey, it was much better than the command line, it was simple and shipped with the IDE I was using at the time.
This decision proved to have been a mistake down the road, but the clock was ticking and I had no more time to waste. Besides, I also believed that in the end, moving it to something like Unity wouldn't pose too much trouble.
Finally, it was time to plan the actual game.
-> ***27.02.2020***&emsp;Day 19
+.quote *[=[27.02.2020]=]*&emsp;Day 19
So far I have only done preparation but on this day, I started actual programming. The UI and most of the mechanics were completely sketched.
-Around a week later I also drew the first proper textures for the game world: a [tile of grass](https://gitlab.com/Syndamia/IT-kariera/-/blob/a100f71372496ba89e26fedc520edcefd2442848/Year%202/Software%20development/Mundus/Mundus/Icons/Land/Ground/grass.png) <img src="./img/grass-tile.png" class="pixelated-render"> and a [tile of grass with a boulder on top](https://gitlab.com/Syndamia/IT-kariera/-/blob/a100f71372496ba89e26fedc520edcefd2442848/Year%202/Software%20development/Mundus/Mundus/Icons/Land/Ground/boulder.png) <img src="./img/boulder-tile.png" class="pixelated-render">. These replaced the [grass](https://gitlab.com/Syndamia/IT-kariera/-/blob/7b2c8cbc1d6adb874ca6a41f2871ea1950866d70/Year%202/Software%20development/Project/Mundus/Mundus/Views/Icons/Land/Ground/grass.jpg) <img src="./img/placeholder-grass-tile.jpg" class="pixelated-render"> and [rock](https://gitlab.com/Syndamia/IT-kariera/-/blob/7b2c8cbc1d6adb874ca6a41f2871ea1950866d70/Year%202/Software%20development/Project/Mundus/Mundus/Views/Icons/Land/Ground/rock.jpg) <img src="./img/placeholder-rock-tile.jpg" class="pixelated-render"> placeholder textures I made on the 29th.
+Around a week later I also drew the first proper textures for the game world: a [url https://gitlab.com/Syndamia/IT-kariera/-/blob/a100f71372496ba89e26fedc520edcefd2442848/Year%202/Software%20development/Mundus/Mundus/Icons/Land/Ground/grass.png tile of grass] <img src="./img/grass-tile.png" class="pixelated-render"> and a [url https://gitlab.com/Syndamia/IT-kariera/-/blob/a100f71372496ba89e26fedc520edcefd2442848/Year%202/Software%20development/Mundus/Mundus/Icons/Land/Ground/boulder.png tile of grass with a boulder on top] <img src="./img/boulder-tile.png" class="pixelated-render">. These replaced the [url https://gitlab.com/Syndamia/IT-kariera/-/blob/7b2c8cbc1d6adb874ca6a41f2871ea1950866d70/Year%202/Software%20development/Project/Mundus/Mundus/Views/Icons/Land/Ground/grass.jpg grass] <img src="./img/placeholder-grass-tile.jpg" class="pixelated-render"> and [url https://gitlab.com/Syndamia/IT-kariera/-/blob/7b2c8cbc1d6adb874ca6a41f2871ea1950866d70/Year%202/Software%20development/Project/Mundus/Mundus/Views/Icons/Land/Ground/rock.jpg rock] <img src="./img/placeholder-rock-tile.jpg" class="pixelated-render"> placeholder textures I made on the 29th.
Concerning the temporary textures, I just drew them in half an hour in GIMP, so I could test out some of the code.
The proper textures, I believe, turned out fairly well, given that I've never been good at drawing and this is my very first time trying to draw pixel art. There is no magic behind the process, after scouring the internet for pixel art that looked kinda close to what I imagined, I tried to utilize and mix whatever I found fitting and then just messed around for hours. As you can imagine, this wasn't a very efficient process, and it took me around 1-2 days for both textures.
-> ***28.03.2020***&emsp;Day 49
+.quote *[=[28.03.2020]=]*&emsp;Day 49
Slowly and steadily I had been making fine progress, but a lot of issues started to surface. As it turns out, I hadn't thought everything completely through, so I mostly went back to the drawing board.
-But at the very least, I had some important systems in place, like breaking and placing stuff, proper movement through the map and using items. Also, I had drawn my favorite texture from the whole projects: [the tree](https://gitlab.com/Syndamia/Mundus/-/blob/c47a34847e52ef76361394dba2c4f524a56d1b92/Mundus/Icons/Land/Items/tree.png) <img src="./img/tree-tile.png" class="pixelated-render">.
+But at the very least, I had some important systems in place, like breaking and placing stuff, proper movement through the map and using items. Also, I had drawn my favorite texture from the whole projects: [url https://gitlab.com/Syndamia/Mundus/-/blob/c47a34847e52ef76361394dba2c4f524a56d1b92/Mundus/Icons/Land/Items/tree.png the tree] <img src="./img/tree-tile.png" class="pixelated-render">.
-> ***06.04.2020***&emsp;Day 58
+.quote *[=[06.04.2020]=]*&emsp;Day 58
Things started to take a turn for the better, I had planned everything I needed to plan and spring break had began. A solid week of no high-school made me more productive than ever. Some days I coded for 8 or even 10 hours straight, from morning to evening. Tools, multiple layers and climbing between them, new items and many bug improvements.
And then, they extended the break for one more week, the productivity boost could've continued even further, but, alas, I was burned out. The productivity boost, as good as it was, it tired me out very fast. There were still a couple of days with progress, but this time I actually took a break.
-<br>
+\n
However, remember how they extended the spring break by a week? Well, this was caused by the emergence of the COVID-19 pandemic in Europe and Bulgaria. Subsequently, after the break, we didn't go back to school. Due to the emergent situation, development on Mundus became increasingly sporadic and progress slowed down drastically. At least the exam got pushed back by a month/month and a half.
-<br>
+\n
-> ***23.05.2020***&emsp;Day 105
+.quote *[=[23.05.2020]=]*&emsp;Day 105
Finally, after so much time, and relative amount of hiccups, Mundus was finished. Or at least, finished enough so I could present it on the exam. And this happened just in the nick of time too, the exam date was in 8 days, on the 31st.
diff --git a/src/blog/mundus-first-shot-at-gamedev/user-interface.du b/src/blog/mundus-first-shot-at-gamedev/user-interface.du
new file mode 100644
index 0000000..7dbb8e6
--- /dev/null
+++ b/src/blog/mundus-first-shot-at-gamedev/user-interface.du
@@ -0,0 +1,92 @@
+# User Interface - Mundus: My first shot at game development
+
+'define expected-reading 4 min
+'define created 21 July 2020
+'define edited 25 November 2020
+[$pagenav]
+
+'define start_url ./
+'define prev_link [url ./timeline.html Timeline]
+'define next_link [url ./basic-concepts.html Basic Concepts]
+[$pagination_middle]
+
+[$due_for_rework]
+
+\n
+
+.contents
+.numbered
+1. [url #main-screen Main screen]
+2. [url #create-new-game Create new game]
+3. [url #game-window Game Window]
+4. [url #map-menu Map menu]
+5. [url #inventory-menu Inventory menu]
+6. [url #crafting-menu Crafting menu]
+
+The user interface shows how unfinished the whole thing is, you can find many unimplemented options and features. Even then, there is a lot you can do.
+
+A lot of the topics covered are explained in more detail in [url ./basic-concepts.html Basic Concepts].
+
+=[Note:]= all screenshots are made in Linux Mint Cinnamon with Mint-Y theme.
+
+## Main screen
+
+[image ./img/main-screen.png]
+
+We start off with the main screen.
+
+Only the `[Create a new game]` button is implemented, although the `[Settings]` one does open a blank window.
+
+## Create new game
+
+[image ./img/create-new-game.png]
+
+Creating a game gives you a couple of options:
+
+`[Game Mode]` - Survival is the only implemented option, where you start with almost no items and have to gather food and materials. Creative was supposed to be the opposite, giving you access to all items and making you invincible.
+
+`[Difficulty]` - Higher the difficulty, the more your energy gets depleted and the less trees, boulders and mobs there are.
+
+`[Screen & Inventory size]` - The screen is where you navigate the in game world. The way the user interface works, both are linked.
+
+`[Map size]` - Map size (in survival mode) is determined by the Screen & Inventory size, the higher the size, the smaller the map.
+
+=[Note:]= all game window screenshots are made with the `[Small Game Window]`.
+
+## Game Window
+
+[image ./img/small-game-window.png]
+
+After the world is generated, the game window opens.
+
+At the top you have your (game) screen. Here you interact with the in-game world. Navigation is done by clicking on a place you want to go to. If you want to alter the environment, first click on an item, that can modify the world and click the thing you want to alter.
+
+Below that is your energy bar. Each mob, including the player, has an energy bar. Each action you do takes energy. If your energy gets depleted, you start taking damage for everything you do. Eating meat from killing mobs is the only way to replenish it.
+
+Then you have your health. It represents how much life you have. If it drops to zero, you die, although no end screen is developed.
+
+Underneath that, there is your hotbar. It is a part of your inventory.
+
+After that, you have the `[Event log]` button and some of the most recent events. Clicking the button opens a window from which you can checkout everything that has happened. On the sides, you can find the `[Map]` and `[Inv]` toggle buttons and the `[Pause]` and `[Music]` menu buttons. The `[Music]` menu can only play and stop WAV files.
+
+## Map menu
+
+[image ./img/map-menu.png]
+
+The Map menu is an extension (to the left) of the normal game window. It cannot be opened at the same time as the inventory menu.
+
+At the top, you can see the ground layer tiles. Below it you can find the name of the superlayer you're currently in and your coordinates. At the bottom there are the structure layer tiles and `[There is a hole above player]` field, where you can check whether you are able to ascent a superlayer.
+
+## Inventory menu
+
+[image ./img/inventory-menu.png]
+
+The Inventory menu is an extension (to the right) of the normal game window. From here you can store your items, organize them, craft and see information about a given item.
+
+## Crafting window
+
+[image ./img/crafting-window.png]
+
+Every time you open the crafting menu, it automatically finds all items that you can craft using the items in your "Items inventory".
+
+At the top it shows you what items and how much of them you need to craft the currently selected item. Below that it shows the item that you can craft and the `[Prev]` and `[Next]` buttons for navigating available items to craft. Finally, there is the `[Craft]` button. Clicking it removes the required items and adds the crafted item to your inventory.
diff --git a/src/blog/mundus-first-shot-at-gamedev/user-interface.md b/src/blog/mundus-first-shot-at-gamedev/user-interface.md
deleted file mode 100644
index 45fe7d1..0000000
--- a/src/blog/mundus-first-shot-at-gamedev/user-interface.md
+++ /dev/null
@@ -1,85 +0,0 @@
-# User Interface - Mundus: My first shot at game development
-
-## [*Due for rework*](/rework.html)
-
-[`<<`](./) || [`< Timeline`](./timeline.html) || [`Basic Concepts >`](./basic-concepts.html)
-
-<br>
-
-## Contents
-
-1. [Main screen](#main-screen)
-2. [Create new game](#create-new-game)
-3. [Game Window](#game-window)
-4. [Map menu](#map-menu)
-5. [Inventory menu](#inventory-menu)
-6. [Crafting menu](#crafting-menu)
-
-The user interface shows how unfinished the whole thing is, you can find many unimplemented options and features. Even then, there is a lot you can do.
-
-A lot of the topics covered are explained in more detail in [Basic Concepts](./basic-concepts.html).
-
-**Note:** all screenshots are made in Linux Mint Cinnamon with Mint-Y theme.
-
-## Main screen
-
-![](./img/main-screen.png)
-
-We start off with the main screen.
-
-Only the `Create a new game` button is implemented, although the `Settings` one does open a blank window.
-
-## Create new game
-
-![](./img/create-new-game.png)
-
-Creating a game gives you a couple of options:
-
-`Game Mode` - Survival is the only implemented option, where you start with almost no items and have to gather food and materials. Creative was supposed to be the opposite, giving you access to all items and making you invincible.
-
-`Difficulty` - Higher the difficulty, the more your energy gets depleted and the less trees, boulders and mobs there are.
-
-`Screen & Inventory size` - The screen is where you navigate the in game world. The way the user interface works, both are linked.
-
-`Map size` - Map size (in survival mode) is determined by the Screen & Inventory size, the higher the size, the smaller the map.
-
-**Note:** all game window screenshots are made with the `Small Game Window`.
-
-## Game Window
-
-![](./img/small-game-window.png)
-
-After the world is generated, the game window opens.
-
-At the top you have your (game) screen. Here you interact with the in-game world. Navigation is done by clicking on a place you want to go to. If you want to alter the environment, first click on an item, that can modify the world and click the thing you want to alter.
-
-Below that is your energy bar. Each mob, including the player, has an energy bar. Each action you do takes energy. If your energy gets depleted, you start taking damage for everything you do. Eating meat from killing mobs is the only way to replenish it.
-
-Then you have your health. It represents how much life you have. If it drops to zero, you die, although no end screen is developed.
-
-Underneath that, there is your hotbar. It is a part of your inventory.
-
-After that, you have the `Event log` button and some of the most recent events. Clicking the button opens a window from which you can checkout everything that has happened. On the sides, you can find the `Map` and `Inv` toggle buttons and the `Pause` and `Music` menu buttons. The `Music` menu can only play and stop WAV files.
-
-## Map menu
-
-![](./img/map-menu.png)
-
-The Map menu is an extension (to the left) of the normal game window. It cannot be opened at the same time as the inventory menu.
-
-At the top, you can see the ground layer tiles. Below it you can find the name of the superlayer you're currently in and your coordinates. At the bottom there are the structure layer tiles and `There is a hole above player` field, where you can check whether you are able to ascent a superlayer.
-
-## Inventory menu
-
-![](./img/inventory-menu.png)
-
-The Inventory menu is an extension (to the right) of the normal game window. From here you can store your items, organize them, craft and see information about a given item.
-
-## Crafting window
-
-![](./img/crafting-window.png)
-
-Every time you open the crafting menu, it automatically finds all items that you can craft using the items in your "Items inventory".
-
-At the top it shows you what items and how much of them you need to craft the currently selected item. Below that it shows the item that you can craft and the `Prev` and `Next` buttons for navigating available items to craft. Finally, there is the `Craft` button. Clicking it removes the required items and adds the crafted item to your inventory.
-
diff --git a/src/blog/plan9-in-linux-mouse-menus/index.md b/src/blog/plan9-in-linux-mouse-menus/index.du
index a231a4a..ea1345f 100644
--- a/src/blog/plan9-in-linux-mouse-menus/index.md
+++ b/src/blog/plan9-in-linux-mouse-menus/index.du
@@ -1,21 +1,33 @@
# Plan 9 in Linux: Mouse menus
-## Contents
+'define expected-reading 17 min
+'define created 10 January 2023
+'define edited 28 March 2023
+[$pagenav]
-1. [Usefulness in Linux](#usefulness-in-linux)
-2. [Going about it](#going-about-it)
- - [\#1](#1)
- - [\#2](#2)
- - [\#3](#3)
- - [\#4](#4)
- + [Open files](#open-files)
- + [Send](#send)
- + [Window management](#window-management)
+.contents
+.numbered
+1. [url #usefulness-in-linux Usefulness in Linux]
+2. [url #going-about-it Going about it]
+ .bulleted
+ - [url #1 \#1]
+ - [url #2 \#2]
+ - [url #3 \#3]
+ - [url #4 \#4]
+ .bulleted
+ - [url #open-files Open files]
+ - [url #send Send]
+ - [url #window-management Window management]
-Let's begin with an introduction to Plan 9 (from Bell Labs): it is an old UNIX-like operating system from the 90s, where[^plan9-vs-rio] everything is pretty much either text, image or some sort of rectangular box.
+'footnote plan9-vs-rio When I say "Plan 9" in the context of graphical stuff, I usually refer to the default window system [url https://9p.io/magic/man2html/1/rio rio]. Similarly to most UNIX-like OSs, it can be changed, but there doesn't seem to be any others out there*[^[citation ^needed]]*.
+
+Let's begin with an introduction to Plan 9 (from Bell Labs): it is an old UNIX-like operating system from the 90s, where[$plan9-vs-rio] everything is pretty much either text, image or some sort of rectangular box.
There are no fancy graphical menus of any kind, no title bars, no file managers and nothing utilizes icons, but the window manager is still stacked.
+
+'footnote acme acme actually changes how the three mouse buttons work. Paraphrasing the [url https://9p.io/wiki/plan9/Using_acme/index.html official page], button 2 "executes things" and button 3 gets or searches for things.
+
Everything is done with text, actions in a window can be done by "clicking" any text inside that corresponds to an available action.
-For example, in the main text editor "acme", you open a file by just pressing[^acme] on a string "New", which for convenience is always available up top:
+For example, in the main text editor "acme", you open a file by just pressing[$acme] on a string "New", which for convenience is always available up top:
<video width="376" height="194" controls>
<source src="./vid/acme-demo.mp4" type="video/mp4">
@@ -30,7 +42,7 @@ The left mouse button (button 1), works as expected: you use it to select text.
Pressing and holding down the right mouse button (button 3), shows all possible window options:
-![](./img/plan9-mouse3-menu.png)
+[image ./img/plan9-mouse3-menu.png]
For example, if you release it while hovering "New", you cursor will change, and after holding it down again, dragging out will result in a grey rectangle representing the dimensions (and position) of a new terminal window (releasing the button creates that new window).
@@ -39,17 +51,21 @@ For example, if you release it while hovering "New", you cursor will change, and
Your browser doesn't support the video tag
</video>
-"Opening" an application is always done via a command in the terminal, where the program will ["take over the window"](https://9p.io/wiki/plan9/Using_rio/index.html).
+"Opening" an application is always done via a command in the terminal, where the program will [url https://9p.io/wiki/plan9/Using_rio/index.html "take over the window"].
Finally, the middle mouse button (button 2), shows text-control options, which can be executed on selected text:
-![](./img/plan9-mouse2-menu.png)
+[image ./img/plan9-mouse2-menu.png]
+
+'footnote snarf It's hard to deduce why exactly it was named like this, but the most probable explanation comes from [url https://unix.stackexchange.com/questions/308943/why-does-plan-9-use-snarf-instead-of-copy/309350 unix.stackexchange]: copying might've been seen as a two step action, obtain the contents you want to copy and paste them somewhere. So to copy something you need a duplicate of itself to be created, and either putting it in the "clipboard" isn't considered duplicating, or an optimization makes "the clipboard" store some sort of reference to what you snarfed, but not the exact thing itself. \n On an unrelated note, this might have played a part in the reasoning behind vim using the word "yank" for copy.
+
+'footnote plumber-in-apps Technically, a plumber just passes messages between applications, so you can configure it to not open a URL but do something else with it in a certain application. However, the aforementioned way is how it works most of the time.
-You'll recognise `cut`, `paste` and `snarf`[^snarf], the latter being just another word for copy.
-Since every modern window manager supports those in some form, I'll concentrate on the others.
-`plumb` is the most interesting: it sends the selection to a "plumber" application, which practically[^plumber-in-apps] tries to open or execute it.
-For example, a selected URL will open in the browser, but a selected image file will open in an image viewer.
-`send` enters the selected text as a command in the current shell.
+You'll recognise `[cut]`, `[paste]` and `[snarf]` [$snarf], the latter being just another word for copy.
+Since every modern window manager supports those in some form, I'll concentrate on the others.\n
+`[plumb]` is the most interesting: it sends the selection to a "plumber" application, which practically[$plumber-in-apps] tries to open or execute it.
+For example, a selected URL will open in the browser, but a selected image file will open in an image viewer.\n
+`[send]` enters the selected text as a command in the current shell.
### Usefulness in Linux
@@ -75,49 +91,48 @@ Most importantly, this works in any application, any time, any where, as long as
### Going about it
-This could all be done with a C program, but writing the code would take way too much time (if you do it like that, [tell me about it](/about)), so everything should be contained in a couple of shell scripts.
+This could all be done with a C program, but writing the code would take way too much time (if you do it like that, [url /about tell me about it]), so everything should be contained in a couple of shell scripts.
Another "constraint" is that I use openbox, an X11 window manager, so my solution will be oriented around tools that work with it.
The result should be simple enough that adapting it to your window manager shouldn't take too much effort.
-Looking around, you would first find a video by Luke Smith, where he creates a small plumber in bash ([YouTube link](https://www.youtube.com/watch?v=RlMxbQmMz_4), [Odysee link](https://odysee.com/@Luke:7/plumbing-in-linux-la-plan-9-from-bell:e)) and an [expansion of it](https://tatsumoto-ren.github.io/blog/plumbing-for-language-learners.html) by Ren Tatsumoto (surprisingly enough from around 3 months before I started).
+Looking around, you would first find a video by Luke Smith, where he creates a small plumber in bash ([url https://www.youtube.com/watch?v=RlMxbQmMz_4 YouTube link], [url https://odysee.com/@Luke:7/plumbing-in-linux-la-plan-9-from-bell:e Odysee link]) and an [url https://tatsumoto-ren.github.io/blog/plumbing-for-language-learners.html expansion of it] by Ren Tatsumoto (surprisingly enough from around 3 months before I started).
These posts served as a good base and inspiration.
Following their steps, everything will be done via one shell script that does something on the text selection, effectively allowing the menus, plumber and all other possible actions to be managed by that script.
The overall life cycle is split into four parts:
-
+.numbered
1. Run script
2. Get selection
3. Open menu
4. Execute action
-#### \#1
+#### #1
Since we're emulating Plan 9, I wanted the script to be ran with the mouse, with potentially different parameters depending on button.
Ideally, if you quickly press and release a button (button 2 or 3), the click should be sent to the application below the cursor, but if you hold it, the script should be ran.
-A tool that allows that (mentioned in Ren Tatsumoto's [blog post](https://tatsumoto-ren.github.io/blog/plumbing-for-language-learners.html)) is [sxhkd](https://github.com/baskerville/sxhkd).
-Sparing you the details, unfortunately sxhkd cannot pass the mouse press to the application below, if you want something to also happen on key-down ([Issue 198](https://github.com/baskerville/sxhkd/issues/198), and the workaround in didn't work).
+A tool that allows that (mentioned in Ren Tatsumoto's [url https://tatsumoto-ren.github.io/blog/plumbing-for-language-learners.html blog post]) is [url https://github.com/baskerville/sxhkd sxhkd].
+Sparing you the details, unfortunately sxhkd cannot pass the mouse press to the application below, if you want something to also happen on key-down ([url https://github.com/baskerville/sxhkd/issues/198 Issue 198], and the workaround in didn't work).
This means that the original idea isn't really feasible, but I couldn't really find any other good tool that does what I wanted.
Plan B: execute the plumbing script on KeyboardKey + Button, but what key should I choose, especially when we're binding the right click?
Ctrl + Button3 is used for opening links, Alt + Button3 is reserved for resizing the current window and binding with the Super (Windows) key causes issues with opening of my application menu.
-After a lot of research, I found out there is actually a fourth modifier key, called `Hyper`, which X11 still supports.
-It's inception come from 1978 with the [Space-cadet keyboard](https://en.wikipedia.org/wiki/Space-cadet_keyboard), but thanks to the popularity of the [Model M](https://en.wikipedia.org/wiki/Model_M_keyboard), modern keyboards don't include it.
+After a lot of research, I found out there is actually a fourth modifier key, called `[Hyper]`, which X11 still supports.
+It's inception come from 1978 with the [url https://en.wikipedia.org/wiki/Space-cadet_keyboard Space-cadet keyboard], but thanks to the popularity of the [url https://en.wikipedia.org/wiki/Model_M_keyboard Model M], modern keyboards don't include it.
-All that was left was to assign `Hyper` to some key that I don't use, and what better than Caps Lock!
-There are [many ways to do it](https://en.jveweb.net/archives/2010/11/making-better-use-of-the-caps-lock-key-in-linux.html), but I prefer using [setxkbmap](https://gitlab.freedesktop.org/xorg/app/setxkbmap):
+All that was left was to assign `[Hyper]` to some key that I don't use, and what better than Caps Lock!
+There are [url https://en.jveweb.net/archives/2010/11/making-better-use-of-the-caps-lock-key-in-linux.html many ways to do it], but I prefer using [url https://gitlab.freedesktop.org/xorg/app/setxkbmap setxkbmap]:
```
setxkbmap -option "caps:hyper"
-```
-This line is needs to be ran at start of openbox, so it's placed inside `~/.config/openbox/autostart`.
+This line is needs to be ran at start of openbox, so it's placed inside `[~/.config/openbox/autostart]`.
-Now, finally, our sxhkd config looks something like this (I named the script `plumb.sh`):
+Now, finally, our sxhkd config looks something like this (I named the script `[plumb.sh]`):
-```
+:code
# Hyper_L + Middle mouse button
mod4 + button2
$HOME/.a/plumb.sh 1
@@ -125,50 +140,48 @@ mod4 + button2
# Hyper_L + Right mouse button
mod4 + button3
$HOME/.a/plumb.sh
-```
-For details about these options, refer to the [manpage](https://github.com/baskerville/sxhkd/blob/master/doc/sxhkd.1.asciidoc).
+
+For details about these options, refer to the [url https://github.com/baskerville/sxhkd/blob/master/doc/sxhkd.1.asciidoc manpage].
What you might notice is that on middle mouse button, "1" is passed to the script.
Since the window options aren't very useful, I've configured the script to execute a "default" action on Hyper\_L+Button2, but show me a list of all possible on Hyper\_L+Button3.
Feel free to change this behaviour.
-#### \#2
+#### #2
Getting the current selection turns out to be easy, X11's selections (clipboard) is split into a primary, secondary and a clipboard, where the primary is the current selection you've done with your mouse, the secondary isn't used, and the clipboard is what you know and love.
-[uninformativ.de](https://www.uninformativ.de/) has a great blog post about [X11's "clipboard"](https://www.uninformativ.de/blog/postings/2017-04-02/0/POSTING-en.html), I recommend it, even though it dives more into C than one would like.
+[url https://www.uninformativ.de/ uninformativ.de] has a great blog post about [url https://www.uninformativ.de/blog/postings/2017-04-02/0/POSTING-en.html X11's "clipboard"], I recommend it, even though it dives more into C than one would like.
-As for getting it inside our script, [xclip](https://github.com/astrand/xclip) is a perfect choice.
+As for getting it inside our script, [url https://github.com/astrand/xclip xclip] is a perfect choice.
In the very beginning, we'll just store the selection in a variable and work from there:
```bash
selection="$(xclip -o)"
-```
-#### \#3
+#### #3
With that out of the way, all we now need is an actual menu to appear.
-Luke Smith and Ren Tatsumoto both used [dmenu](https://tools.suckless.org/dmenu/), which is keyboard driven.
-As for a mouse-oriented standalone menu, that could be easily configured, all I could find was my current application menu: [jgmenu](https://jgmenu.github.io/).
+Luke Smith and Ren Tatsumoto both used [url https://tools.suckless.org/dmenu/ dmenu], which is keyboard driven.
+As for a mouse-oriented standalone menu, that could be easily configured, all I could find was my current application menu: [url https://jgmenu.github.io/ jgmenu].
-Generally it is meant to serve as an application menu, but with `--simple` you can directly echo and pipe to it all menu option and what they do.
+Generally it is meant to serve as an application menu, but with `[--simple]` you can directly echo and pipe to it all menu option and what they do.
Menu options are formatted as comma-separated (CSV) text, where each option is on a new line, the first item being the name, and the second, the executed command upon press:
```
Send,echo 1
Resize,echo 2
Move,echo 3
-```
In this case I'm echo-ing a number, rather than doing an action, for readability and formatting sake.
The number is parsed by a switch statement, so all actions are in a single place and can be more easily formatted than if they were inlined in the string.
-Via `--at-pointer` the menu can spawn right under the pointer.
+Via `[--at-pointer]` the menu can spawn right under the pointer.
Unfortunately it always spawns in such a way that the pointer is at the top-left corner, I couldn't find a way to make it appear in a way that the first option is below the pointer.
Finally, since I use it as an application menu too, I specify a config file which makes it look more like Plan 9's menu (though I've personally omitted the color scheme, since it doesn't fit my normal theme):
-```
+:code
menu_width = 1
arrow_width = 1
icon_size = 0
@@ -187,13 +200,13 @@ color_menu_border = #88cc88 100
color_norm_fg = #000000 100
color_sel_bg = #448844 100
color_sel_fg = #000000 100
-```
-More info on these options can be found in the [manpage](https://jgmenu.github.io/jgmenu.1.html).
+
+More info on these options can be found in the [url https://jgmenu.github.io/jgmenu.1.html manpage].
Putting it all together, it looks something like this:
-```bash
+:code_bash
action=$(echo -ne "Send,echo 1\nResize,echo 2\nMove,echo 3\n" | jgmenu --at-pointer --simple --config-file="$HOME/.config/jgmenu/jgmenusimplerc")
case "$action" in
@@ -207,18 +220,18 @@ case "$action" in
...
;;
esac
-```
+
An important aspect of our menu options is that they can change depending on context.
For example, if we have a URL we might want the options "Open it in browser" and "Download", which we wouldn't want in case of a .docx file.
Or we might want it "ship" it with a lot of possible menu options and let the user decide which ones they need.
This is very simple to do, and can be done in many ways.
-My preferred way is to have a variable `menu` to which different options are appended depending on a regular expression or "flag" (variable).
+My preferred way is to have a variable `[menu]` to which different options are appended depending on a regular expression or "flag" (variable).
To work with regular expressions more easily, I've made a function which returns a status code depending on matching.
All in all, it would look something like this:
-```bash
+:code_bash
menu=""
windowOptions=0
@@ -226,7 +239,7 @@ function matches() {
echo "$selection" | grep "$1" >/dev/null 2>&1
}
-[ windowOptions -eq 1 ] && menu+="Resize,echo 3\nMove,echo 4\nDelete,echo 5\n,....."
+[ windowOptions -eq 1 && menu+="Resize,echo 3\nMove,echo 4\nDelete,echo 5\n,....."
matches ".*\.cpp" && menu+="Compile and run,echo 10\n"
action=$(echo -ne "$menu" | jgmenu --at-pointer --simple --config-file="$HOME/.config/jgmenu/jgmenusimplerc")
@@ -234,24 +247,23 @@ action=$(echo -ne "$menu" | jgmenu --at-pointer --simple --config-file="$HOME/.c
case "$action" in
...
esac
-```
-#### \#4
-Finally, we need to execute a selected option, aka put commands in each case of `$action`.
+#### #4
+
+Finally, we need to execute a selected option, aka put commands in each case of `[\$action]`.
##### Open files
-Opening a file is very simple, `xdg-open` handles opening files by name, with the default program for that file extension.
+Opening a file is very simple, `[xdg-open]` handles opening files by name, with the default program for that file extension.
However, the script is ran completely independently from the current program, so when we're given only a part of the file path, we need to figure out the rest.
-This problem was solved somewhat by Luke Smith, he figured out a way to find (and `cd` into) the current directory of the active window (`pid1` should be `pid`, but you'll see later why I did that change):
+This problem was solved somewhat by Luke Smith, he figured out a way to find (and `[cd]` into) the current directory of the active window (`[pid1]` should be `[pid]`, but you'll see later why I did that change):
```bash
pid=$(xprop -id "$(xprop -root | awk '/_NET_ACTIVE_WINDOW\(WINDOW\)/{print $NF}')" | grep -m 1 PID | cut -d " " -f 3)
pid1=$(pstree -lpA "$pid" | tail -n 1 | awk -F'---' '{print $NF}' | sed -re 's/[^0-9]//g')
cd "$(readlink /proc/"$pid1"/cwd)"
-```
Still, one important situation where this doesn't work is tabs, but those are handled differently from application to application.
I figured out tabs only for terminal emulators, since that's where text actions can be the most useful.
@@ -261,13 +273,17 @@ We only get the active window, but there is no way to get the active/currently "
Additionally, pretty much all terminal emulators have different shell, not terminal, processes for the different tabs.
Terminal plugins/extensions and special application were considered, but they would take too much effort and/or couldn't work.
+'footnote shell-cwd You could make a proper mechanism, which waits for the file to get updated ([url https://github.com/inotify-tools/inotify-tools inotify-wait]), or for there to be a lockfile, but the overall way it works is the same. I couldn't think of anything better, mostly because the plumber script is a completely separate process from the shell you're in. Maybe there is a way for them to communicate between each other, a bit like microservices?
+
In the end, I settled on a hack: the shell would do the heavy lifting.
-My right-click menu combination would be passed to the terminal (and therefore to the shell), and the shell will simultaneously store it's working directory in a file inside `/tmp`, which could then be parse by the script.
-This isn't ideal, since if the shell is being slow, the script might not wait long enough for the file to get updated, but I couldn't think of anything much better[^shell-cwd] and it does the job.
+My right-click menu combination would be passed to the terminal (and therefore to the shell), and the shell will simultaneously store it's working directory in a file inside `[/tmp]`, which could then be parse by the script.
+This isn't ideal, since if the shell is being slow, the script might not wait long enough for the file to get updated, but I couldn't think of anything much better[$shell-cwd] and it does the job.
+
+'footnote escape-sequences The terminal emulator passes keyboard presses to the shell via [url https://en.wikipedia.org/wiki/ANSI_escape_code ANSI escape sequences], which don't support `[Hyper]` bindings. I settled for the next best thing, which is create a different key combination that isn't in use, and make our script "press" that combination upon running.
I use zsh, so I implemented it by creating a zsh widget: certain functionality that can be ran by the shell itself and (usually) doesn't need to be executed like a normal program.
Examples include key binds, completion, navigation through history, undo and redo.
-User-defined widgets are just zsh functions, so we create a function that stores the current directory, add it as a widget and bind it to our keyboard combination[^escape-sequences]:
+User-defined widgets are just zsh functions, so we create a function that stores the current directory, add it as a widget and bind it to our keyboard combination[$escape-sequences]:
```bash
plumb-store-cwd () {
@@ -275,29 +291,26 @@ plumb-store-cwd () {
}
zle -N plumb-store-cwd
bindkey "^[[5;7~" plumb-store-cwd # Ctrl+Alt+Page_Up
-```
Finally, in our script, we want to read that file, only if we're inside a terminal:
```bash
wname="$(cat /proc/"$pid"/comm)"
-if [ $wname == "TERMINAL" ]; then # Replace with your terminal emulator name
+if [ $wname == "TERMINAL"; then # Replace with your terminal emulator name
xdotool key Control+Alt+Page_Up # Execute the shell-compatible combination
sleep 0.1 # Rework with inotify?
cd "$(cat /tmp/plumb-cwd)"
fi
-```
-For the uninitiated, [xdotool](https://github.com/jordansissel/xdotool) is a general X11 tool, which allows (amongst other things) to "execute" key presses via commands.
+For the uninitiated, [url https://github.com/jordansissel/xdotool xdotool] is a general X11 tool, which allows (amongst other things) to "execute" key presses via commands.
##### Send
Sending the command to the current shell is by far the simplest action.
-`xdotool` supports "typing out" text, so I'll give it the selection and let it do it's thing:
+`[xdotool]` supports "typing out" text, so I'll give it the selection and let it do it's thing:
```bash
xdotool type --delay 0 "$selection"
-```
It could be optimized if there was a way to make the selection be "pasted" into the shell (without being added to the clipboard), since that would mostly eliminate waiting times.
Sadly I couldn't figure out how to do anything like that.
@@ -311,29 +324,14 @@ For example, normally resizing is done via Alt+RightClick, so I'll just do this:
xdotool keydown Alt
xdotool mousedown 3
xdotool keyup Alt
-```
After this is executed, moving the mouse will cause the screen to be resized, the same way if I did the original combination.
-Pressing and releasing the mouse button will stop resizing (that's why `keyup Alt` is done, because otherwise you would need to also press Alt).
+Pressing and releasing the mouse button will stop resizing (that's why `[keyup Alt]` is done, because otherwise you would need to also press Alt).
Though it work, it's kind of clunky and the normal Alt+RightClick is arguably simpler and easier to work with.
-<br>
+\n
With this our script if finished.
-You can find the whole thing (including some personal modifications) in my [dotfiles](https://gitlab.com/Syndamia/dotfiles/-/blob/main/.a/plumb.sh).
+You can find the whole thing (including some personal modifications) in my [url https://gitlab.com/Syndamia/dotfiles/-/blob/main/.a/plumb.sh dotfiles].
I'll try to use it as much as I can and I might create a blog post or an appendix on how I feel about it.
-
-[^plan9-vs-rio]: When I say "Plan 9" in the context of graphical stuff, I usually refer to the default window system [rio](https://9p.io/magic/man2html/1/rio). Similarly to most UNIX-like OSs, it can be changed, but there doesn't seem to be any others out there*^[citation ^needed]*.
-
-[^acme]: acme actually changes how the three mouse buttons work. Paraphrasing the [official page](https://9p.io/wiki/plan9/Using_acme/index.html), button 2 "executes things" and button 3 gets or searches for things.
-
-[^snarf]: It's hard to deduce why exactly it was named like this, but the most probable explanation comes from [unix.stackexchange](https://unix.stackexchange.com/questions/308943/why-does-plan-9-use-snarf-instead-of-copy/309350): copying might've been seen as a two step action, obtain the contents you want to copy and paste them somewhere. So to copy something you need a duplicate of itself to be created, and either putting it in the "clipboard" isn't considered duplicating, or an optimization makes "the clipboard" store some sort of reference to what you snarfed, but not the exact thing itself. <br> On an unrelated note, this might have played a part in the reasoning behind vim using the word "yank" for copy.
-
-[^plumber-in-apps]: Technically, a plumber just passes messages between applications, so you can configure it to not open a URL but do something else with it in a certain application. However, the aforementioned way is how it works most of the time.
-
-[^9wm]: [9wm](https://github.com/9wm/9wm) is a window manager for X11, so if you use it these functionalities will be available, but I'm referring to (almost; 9wm has forks) every other window manager
-
-[^shell-cwd]: You could make a proper mechanism, which waits for the file to get updated ([inotify-wait](https://github.com/inotify-tools/inotify-tools)), or for there to be a lockfile, but the overall way it works is the same. I couldn't think of anything better, mostly because the plumber script is a completely separate process from the shell you're in. Maybe there is a way for them to communicate between each other, a bit like microservices?
-
-[^escape-sequences]: The terminal emulator passes keyboard presses to the shell via [ANSI escape sequences](https://en.wikipedia.org/wiki/ANSI_escape_code), which don't support `Hyper` bindings. I settled for the next best thing, which is create a different key combination that isn't in use, and make our script "press" that combination upon running.
diff --git a/src/blog/sane-explanation-of-compilers/index.md b/src/blog/sane-explanation-of-compilers/index.du
index cd0cf4b..40c6cff 100644
--- a/src/blog/sane-explanation-of-compilers/index.md
+++ b/src/blog/sane-explanation-of-compilers/index.du
@@ -3,4 +3,5 @@
This blogpost is split into multiple parts.
More information is available in the first part.
-- [Part 1](./part-1.html): Introduction and The frontend (aka How do we understand code)
+.bulleted
+- [url ./part-1.html Part 1]: Introduction and The frontend (aka How do we understand code)
diff --git a/src/blog/sane-explanation-of-compilers/part-1.md b/src/blog/sane-explanation-of-compilers/part-1.du
index 80426db..d9b58ba 100644
--- a/src/blog/sane-explanation-of-compilers/part-1.md
+++ b/src/blog/sane-explanation-of-compilers/part-1.du
@@ -1,26 +1,44 @@
# Sane explanation of compilers: Part 1
-## Contents
+'define expected-reading 48 min
+'define created 30 March 2023
+'define edited 24 April 2023
+[$pagenav]
+
+:contents
+:numbered
+1. [url #preface Preface]
+2. [url #i.-how-do-we-understand-code I. How do we understand code?]
+ :numbered
+ 1. [url #math Math]
+ .numbered
+ 1. [url #regular-expressions Regular expressions]
+ 2. [url #grammars Grammars]
+
+ 2. [url #lexers-and-parsers Lexers and parsers]
+ :numbered
+ 1. [url #implementational-difficulties-with-grammars Implementational difficulties with grammars]
+ 2. [url #practical-usage Practical usage]
+ 3. [url #parsing-algorithms Parsing algorithms]
+ .numbered
+ 1. [url #ll LL]
+ 2. [url #lr LR]
+ 3. [url #lrs-family LR's family]
+ 4. [url #more-info More info]
+
+ 4. [url #abstract-syntax-tree Abstract syntax tree]
+
+
+ 3. [url #implementing-a-front-end Implementing a front-end]
+ .numbered
+ 1. [url #lex lex]
+ 2. [url #yacc yacc]
+ 3. [url #doing-it-properly Doing it properly]
+
+
+3. [url #appendix Appendinx]
+
-1. [Preface](#preface)
-2. [I. How do we understand code?](#i.-how-do-we-understand-code)
- 1. [Math](#math)
- 1. [Regular expressions](#regular-expressions)
- 2. [Grammars](#grammars)
- 2. [Lexers and parsers](#lexers-and-parsers)
- 1. [Implementational difficulties with grammars](#implementational-difficulties-with-grammars)
- 2. [Practical usage](#practical-usage)
- 3. [Parsing algorithms](#parsing-algorithms)
- 1. [LL](#ll)
- 2. [LR](#lr)
- 3. [LR's family](#lrs-family)
- 4. [More info](#more-info)
- 4. [Abstract syntax tree](#abstract-syntax-tree)
- 3. [Implementing a front-end](#implementing-a-front-end)
- 1. [lex](#lex)
- 2. [yacc](#yacc)
- 3. [Doing it properly](#doing-it-properly)
-3. [Appendinx](#appendix)
Recently I signed up for a small university course about compilers.
As I found out, most materials on the topic are either so surface level you barely learn anything, or so specific you need to already know the subject.
@@ -32,10 +50,13 @@ Processors work with numbers, every action (instruction) a processor can do is d
However, writing code only with numbers is tedious, error-prone and simple stuff sometimes take ages to implement.
That is why, over time, programmers have tried to abstract sets of instructions into words and text constructions that are easier to work with.
+'footnote how-did-we-get-here Though it's obvious, I would like to point out that modern compilers are most often written in languages that are themselves compiled. You might ask yourself "where did the first compiler come from?" The answer is simple: it was written with "numbers", with direct instructions to the processor, from the time when computers were simple enough that *[all]* programming was done with CPU instructions.
+
Thanks to abstraction, programmers have been able to create more and more complicated projects with less and less work, that is more portable and compatible with different machines.
The trade-off is that we need to translate our nice programmer code to numbers a CPU would understand.
-This job is delegated to a special type of program, called a compiler[^how-did-we-get-here], which is separated into three main layers/components:
+This job is delegated to a special type of program, called a compiler[$how-did-we-get-here], which is separated into three main layers/components:
+.numbered
1. Front-end: it understands the program, what the code is trying to do
2. Middle: does optimizations and simplifications, though this part is often inside the back-end
3. Back-end: generates the actual machine instructions
@@ -44,22 +65,22 @@ In this post, we'll be looking only at the first one.
## I. How do we understand code?
-Syntax in current programming languages can be quite sophisticated and ambiguous. For example (taken from [wikipedia](https://en.wikipedia.org/wiki/Most_vexing_parse)) this C++ snippet
+Syntax in current programming languages can be quite sophisticated and ambiguous. For example (taken from [url https://en.wikipedia.org/wiki/Most_vexing_parse wikipedia]) this C++ snippet
```
void f(double d) {
int i(int(d));
}
-```
could be interpreted either as a:
-1. declaration of variable `i`, which is initialized with the value of `int(d)` (which just casts `d` to an integer), or
-2. function declaration, since superfluous parenthesis around function parameter declarations are allowed (meaning it is treated as `int i(int d)`)
+.numbered
+1. declaration of variable `[i]`, which is initialized with the value of `[int(d)]` (which just casts `[d]` to an integer), or
+2. function declaration, since superfluous parenthesis around function parameter declarations are allowed (meaning it is treated as `[int i(int d)]`)
Note that I'm talking about syntax, the valid selection and layouts of characters, and not semantics, the underlying meaning.
Compiled programming languages associate specific templates of code (text) to their "corresponding" machine instructions, there isn't anything special you need to understand in a piece of code.
-In natural languages, you could construct a sentence which follows all grammatical rules, but is absolute nonsense, like ["Colorless green ideas sleep furiously"](https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously).
+In natural languages, you could construct a sentence which follows all grammatical rules, but is absolute nonsense, like [url https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously "Colorless green ideas sleep furiously"].
The problem of semantics is extremely difficult, however in our case we only care about syntax.
And this is where math comes into play.
@@ -69,8 +90,8 @@ And this is where math comes into play.
A word of caution, I'll use a decent amount of fancy names, so I have a way to more easily refer to different concepts.
Don't be scared and skip over them if they're confusing you.
-There is a special field in mathematics that deals with syntactical analysis: [formal language theory](https://en.wikipedia.org/wiki/Formal_language).
-Although even the basics merit a whole university course, I'll still try to roughly explain what's important, for those that haven't studied it.
+There is a special field in mathematics that deals with syntactical analysis: [url https://en.wikipedia.org/wiki/Formal_language formal language theory].
+Although even the basics merit a whole university course, I'll still try to roughly explain what's important, for those that haven't studied it.\n
This field works primarily with strings via the help of two (relevant for our purposes) instruments: regular expressions and grammars.
#### Regular expressions
@@ -81,146 +102,152 @@ When a word can be "generated" from the pattern, we say the regex matches the wo
At their very base, such a pattern is created with the following rules:
-- [concatenation](https://en.wikipedia.org/wiki/Concatenation) - you can put characters next to each other to form strings, so a normal string like `accent` is also a regex.
+:unordered
+- [url https://en.wikipedia.org/wiki/Concatenation concatenation] - you can put characters next to each other to form strings, so a normal string like `[accent]` is also a regex.\n
With braces we can group stuff.
- For example, in `a(cc)ent` the two "c"s are grouped together.
- This is used to form more sophisticated structures later on, but currently it doesn't alter anything, like the braces in `(1+2)+3` and `1+(2+3)` don't alter the result sum.
-- [alternation](https://en.wikipedia.org/wiki/Alternation_%28formal_language_theory%29) - allow different (alternative) strings in the same spot.
+ For example, in `[a(cc)ent]` the two "c"s are grouped together.
+ This is used to form more sophisticated structures later on, but currently it doesn't alter anything, like the braces in `[(1+2)+3]` and `[1+(2+3)]` don't alter the result sum.
+
+- [url https://en.wikipedia.org/wiki/Alternation_%28formal_language_theory%29 alternation] - allow different (alternative) strings in the same spot.\n
We do so with vertical bars (which signify an "or" relationship), the group can be "replaced" with either value.
- For example `acce(n | p)t`, matches both "acce**n**t" or "acce**p**t".
+ For example `[acce(n | p)t]`, matches both "acce=[n]=t" or "acce=[p]=t".\n
There is no limit on how many alternatives you can have and what their lengths are:
```regex
acc(ordingly | ent | urate)
- ```
matches
- + "acc**ordingly**"
- + "acc**ent**" and
- + "acc**urate**".
+ .bulleted
+ - "acc=[ordingly]="
+ - "acc=[ent]=" and
+ - "acc=[urate]=".
There is no limit on how many groups (with alternation) you can have:
```regex
ac(quirem | c | hievem)en(t | ts)
- ```
matches
- + "ac**quirem**en**t**"
- + "ac**quirem**en**ts**"
- + "ac**c**en**t**
- + "ac**c**en**ts**
- + "ac**hievem**en**t**" and
- + "ac**hievem**en**ts**".
+ .bulleted
+ - "ac=[quirem]=en=[t]="
+ - "ac=[quirem]=en=[ts]="
+ - "ac=[c]=en=[t]=
+ - "ac=[c]=en=[ts]=
+ - "ac=[hievem]=en=[t]=" and
+ - "ac=[hievem]=en=[ts]=".
-- [Kleene star](https://en.wikipedia.org/wiki/Kleene_star) - repeat the preceding letter or group, 0 or more times.
- An asterisk is used to mark this operation (hence the name, "Kleene **star**").
+- [url https://en.wikipedia.org/wiki/Kleene_star Kleene star] - repeat the preceding letter or group, 0 or more times.\n
+ An asterisk is used to mark this operation (hence the name, "Kleene =[star]=").
```regex
accents*
- ```
+
will match
- + "accent"
- + "accent**s**
- + "accent**ss**
- + "accent**sss**
- + and so on
+ .bulleted
+ - "accent"
+ - "accent=[s]=
+ - "accent=[ss]=
+ - "accent=[sss]=
+ - and so on
Of course, the asterisk could also be in the middle of the regex, like
```regex
ac*ent
- ```
-
+
which matches
- + "acent"
- + "ac**c**ent"
- + "ac**cc**ent"
- + ...
+ .bulleted
+ - "acent"
+ - "ac=[c]=ent"
+ - "ac=[cc]=ent"
+ - ...
With a group we can repeat entire strings,
```regex
acc(ent)*s
- ```
matches
- + "accs"
- + "acc**ent**s"
- + "acc**entent**s
- + "acc**ententent**s"
- + ...
+ .bulleted
+ - "accs"
+ - "acc=[ent]=s"
+ - "acc=[entent]=s
+ - "acc=[ententent]=s"
+ - ...
- An alternation allows any alternative to be chosen at any point, so
+ An alternation allows any alternative to be chosen at any point, so
```regex
acce(n | p)*t
- ```
matches
- + "accet"
- + "acce**n**t
- + "acce**p**t
- + "acce**nn**t
- + "acce**np**t"
- + "acce**pn**t"
- + "acce**pp**t"
- + "acce**nnn**t"
- + ...
+ .bulleted
+ - "accet"
+ - "acce=[n]=t
+ - "acce=[p]=t
+ - "acce=[nn]=t
+ - "acce=[np]=t"
+ - "acce=[pn]=t"
+ - "acce=[pp]=t"
+ - "acce=[nnn]=t"
+ - ...
-In the modern day, regular expressions permit [additional constructions](https://en.wikipedia.org/wiki/Regular_expression#Syntax) like matching the start or end of a string, matching character groups or character classes.
-There are also sometimes features which significantly increase the matching capabilities of normal regexes, like [lookahead and lookbehind assertions](https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages).
+
+In the modern day, regular expressions permit [url https://en.wikipedia.org/wiki/Regular_expression#Syntax additional constructions] like matching the start or end of a string, matching character groups or character classes.
+There are also sometimes features which significantly increase the matching capabilities of normal regexes, like [url https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages lookahead and lookbehind assertions].
#### Grammars
However, even then regular expressions are fairly weak, they can't match recursive structures.
Let's say you want to be able to have math expressions in your language, you can have braces inside braces as much as you like, but in a certain manner:
-- `1+2` is a valid expression
-- `(9-8)+2` also is valid
-- `((3*3)-(2^3))+2` is too
-- however `()3*3)-(2^3()+2` isn't valid
+.bulleted
+- `[1+2]` is a valid expression
+- `[(9-8)+2]` also is valid
+- `[((3*3)-(2^3))+2]` is too
+- however `[()3*3)-(2^3()+2]` isn't valid
-Such a structure is recursive, because it can contain "itself", `1+2` can be a standalone math expression, but it can also be contained in another expression, like `(1+2)*3`, which itself could be inside another bigger expressions and so on.
+Such a structure is recursive, because it can contain "itself", `[1+2]` can be a standalone math expression, but it can also be contained in another expression, like `[(1+2)*3]`, which itself could be inside another bigger expressions and so on.
For this task we have a whole separate tool: grammars.
+'footnote terminals-and-nonterminals Formally, we call the rule "names" nonterminals, the idea being that all normal characters, that could appear in our string, are called terminals, since they would terminate replacement and string generation. For the purposes of this post, I won't use the formal names, with the hope that using less terminology will increase understandability.
+
The syntax is different from regexes: a grammar is divided into (production) rules, each rule is named and specifies an expression.
-Expressions are a concatenation of strings and/or names[^terminals-and-nonterminals].
+Expressions are a concatenation of strings and/or names[$terminals-and-nonterminals].
Names won't appear in our matched strings, the idea is that a name will be replaced with it's expression, kind of like a placeholders.
Additionally, there can be multiple rules with the same name, meaning a rule can be replaced by different stuff at any point of the string generation.
+'footnote grammar-syntax This is pretty much the mathematical notation, often in CS the Backus-Naur form is used, but I find that a bit harder to read. You might also make the argument that I should use a proper unicode arrow symbol, like `[→]`, but `[->]` is way more convinient.
+
Always one name is chosen to be the starting point, and generation continues from there.
-In math literature, generally we write rules in the form `Name -> Expression`[^grammar-syntax], and often names are a single capital letter.
-Additionally, often the starting name is called `S`.
-Finally, in future examples, I'll use the arrow `⇒` to show derivations, how the generated string looks after one or two replacements of the name with one of it's expressions.
+In math literature, generally we write rules in the form `[Name -> Expression]` [$grammar-syntax], and often names are a single capital letter.
+Additionally, often the starting name is called `[S]`.
+Finally, in future examples, I'll use the arrow `[⇒]` to show derivations, how the generated string looks after one or two replacements of the name with one of it's expressions.
For an example, with the grammar
```grammar
S -> aSb
S -> cc
-```
-we can generate the string `aaaaccbbbb` (remember, our starting point is `S`):
+we can generate the string `[aaaaccbbbb]` (remember, our starting point is `[S]`):
```grammar+
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaaSbbbb ⇒ aaaaccbbbb
-```
-or `accb`:
+or `[accb]`:
```grammar+
S ⇒ aSb ⇒ accb
-```
where a, b and c are just English characters.
-To simplify our lives, often rules with the same name are merged into one rule, separated by vertical bars (`S -> aSb | cc`).
+To simplify our lives, often rules with the same name are merged into one rule, separated by vertical bars (`[S -> aSb | cc]`).
This is practically alternation but in a different context.
As for our math expressions, we could create something like this:
@@ -228,33 +255,32 @@ As for our math expressions, we could create something like this:
```grammar
N -> 0 | 1 | 2 | ... all possible numbers
E -> N | (E) | E + E | E - E | E * E | E / E | E ^ E
-```
-which will successfully be able to match (generate) `((3 * 3) - (2 ^ 3)) + 2`:
+which will successfully be able to match (generate) `[((3 * 3) - (2 ^ 3)) + 2]`:
```grammar+
E ⇒ E + E ⇒ (E) + N ⇒ (E - E) + 2 ⇒ ((E) - (E)) + 2 ⇒ ((E * E) - (E ^ E)) + 2 ⇒ ((N * N) - (N ^ N)) + 2 ⇒ ((3 * 3) - (2 ^ 3)) + 2
-```
-but there are no expressions (rules) that allow `()3+3()` or `)3(-6` to be "matched".
+but there are no expressions (rules) that allow `[()3+3()]` or `[)3(-6]` to be "matched".
### Lexers and parsers
-You might've noticed that for `N` I use three dots and the note "all possible numbers" to signify that N can be any positive whole number.
+You might've noticed that for `[N]` I use three dots and the note "all possible numbers" to signify that N can be any positive whole number.
In practice we need formally define that grammar:
```grammar
N -> 0 | 1 | 2 | ... | 9 | 0N | 1N | 2N | ... | 9N
-```
-With this you might've realised that grammars can do anything a regular expressions can: concatenation and alternation are "built-in", and the Kleene star can be done with another rule in the form `R -> strR | str`[^regular-grammars].
+'footnote regular-grammars Such grammars are called [url https://en.wikipedia.org/wiki/Regular_grammar regular grammars], more formally, every rule has to contain at most one name and that name must be at the start or end of the string characters.
+
+With this you might've realised that grammars can do anything a regular expressions can: concatenation and alternation are "built-in", and the Kleene star can be done with another rule in the form `[R -> strR | str]` [$regular-grammars].
The reason we use both is that grammars are significantly slower and more complicated in code than regexes.
#### Implementational difficulties with grammars
-Implementing (very roughly) the regular expression `acce(n | p)*t` is quite easy:
+Implementing (very roughly) the regular expression `[acce(n | p)*t]` is quite easy:
-```cpp
+:code_cpp
bool matchesp(string str) {
string regex = "acce_t";
@@ -271,16 +297,16 @@ bool matchesp(string str) {
}
return true;
}
-```
+
In brief, for concatenated characters we do a simple comparison per character.
-When we reach "\_", which I use to specify we're in the `(n | p)*` part of the regex, we do comparisons with the characters n and p as much as we can, after which we continue as normal.
+When we reach "\_", which I use to specify we're in the `[(n | p)*]` part of the regex, we do comparisons with the characters n and p as much as we can, after which we continue as normal.
Of course, this version only supports one regular expressions, however a "proper" implementation would look conceptually similar: a couple of different loops and equality checks, with maybe an additional array or two.
-The huge benefit is that that loops and arrays are stupid fast, a (simple) C++ for loop could be translated into [a handful of processor instructions](https://godbolt.org/#g:!%28%28g:!%28%28g:!%28%28h:codeEditor,i:%28filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:%28endColumn:16,endLineNumber:6,positionColumn:16,positionLineNumber:6,selectionStartColumn:16,selectionStartLineNumber:6,startColumn:16,startLineNumber:6%29,source:'//+Type+your+code+here,+or+load+an+example.%0Aint+f%28int+num%29+%7B%0A++++for+%28int+i+%3D+1%3B+i+%3C+100%3B+i%2B%2B%29+%7B%0A++++++++num+*%3D+100%3B%0A++++%7D%0A++++return+num%3B%0A%7D'%29,l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29,%28g:!%28%28h:compiler,i:%28compiler:g122,deviceViewOpen:'1',filters:%28b:'0',binary:'1',binaryObject:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'%29,flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!%28%29,options:'',selection:%28endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1%29,source:1%29,l:'5',n:'0',o:'+x86-64+gcc+12.2+%28Editor+%231%29',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29%29,l:'2',n:'0',o:'',t:'0'%29%29,version:4).
+The huge benefit is that that loops and arrays are stupid fast, a (simple) C++ for loop could be translated into [url https://godbolt.org/#g:!%28%28g:!%28%28g:!%28%28h:codeEditor,i:%28filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:%28endColumn:16,endLineNumber:6,positionColumn:16,positionLineNumber:6,selectionStartColumn:16,selectionStartLineNumber:6,startColumn:16,startLineNumber:6%29,source:'//+Type+your+code+here,+or+load+an+example.%0Aint+f%28int+num%29+%7B%0A++++for+%28int+i+%3D+1%3B+i+%3C+100%3B+i%2B%2B%29+%7B%0A++++++++num+*%3D+100%3B%0A++++%7D%0A++++return+num%3B%0A%7D'%29,l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29,%28g:!%28%28h:compiler,i:%28compiler:g122,deviceViewOpen:'1',filters:%28b:'0',binary:'1',binaryObject:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'%29,flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!%28%29,options:'',selection:%28endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1%29,source:1%29,l:'5',n:'0',o:'+x86-64+gcc+12.2+%28Editor+%231%29',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29%29,l:'2',n:'0',o:'',t:'0'%29%29,version:4 a handful of processor instructions].
On the other hand, usually grammars are more complicated and resource-intensive.
-Certain ones are simple enough to implement, like `S -> aSb | cc`:
+Certain ones are simple enough to implement, like `[S -> aSb | cc]`:
```cpp
bool matchesp(string str) {
@@ -291,47 +317,48 @@ bool matchesp(string str) {
else
return false;
}
-```
-However think about more complicated cases[^context-free-grammars], like `S -> aSbSa | cc`.
-Implementing this one is quite a bit more difficult, since we don't know where `b` is located on the first iteration, it could either be the 4th character `accb...a` or the 9th `aaccbccab...a`.
-Searching for it is also complicated, it could be the first, the last or any other `b` in the middle of the string.
+'footnote context-free-grammars Be careful about cases that are too complicated, the grammar I'm showing is "context-free", but that topic is way beyond the scope of this post.
+
+However think about more complicated cases[$context-free-grammars], like `[S -> aSbSa | cc]`.
+Implementing this one is quite a bit more difficult, since we don't know where `[b]` is located on the first iteration, it could either be the 4th character `[accb...a]` or the 9th `[aaccbccab...a]`.
+Searching for it is also complicated, it could be the first, the last or any other `[b]` in the middle of the string.
Another difficulty with grammars is ambiguity, let's look at
```grammar
E -> E + E | E * E | n
-```
-how would it generate `n + n * n`?
+how would it generate `[n + n * n]`?
There are two completely valid ways to do so:
```grammar+
E ⇒ E + E ⇒ n + E * E ⇒ n + n * n
-```
```grammar+
E ⇒ E * E ⇒ E + E * n ⇒ n + n * n
-```
How exactly we deal with these problems comes later, for now the takeaway is that we have to try and use regular expressions wherever we can, and leave grammars as a bit of a last resort.
#### Practical usage
+'footnote static-typing Yeah yeah, in a statically typed language you might not be able to do operations on doubles and integers at the same time, but you get the point.
+
Let's think a bit more about grammars: they're really good at handling structure, especially recursive structure, so it's best if we use them only for that.
-Our math expression grammar (from [here](#grammars)) shouldn't really care if we're trying to sum integers or floats or chars[^static-typing], it's important how everything is laid out and that our operations are done with numbers.
+Our math expression grammar (from [url #grammars here]) shouldn't really care if we're trying to sum integers or floats or chars[$static-typing], it's important how everything is laid out and that our operations are done with numbers.
-This is why we're going to separate and generalize the code into [tokens](https://en.wikipedia.org/wiki/Lexical_analysis#Token), basically into building blocks.
-As a rough example, we want `1 + (2 * 3)` to be transformed into `NUMBER MATHOP LBRACE NUMBER MATHOP NUMBER RBRACE`, `int var = 13;` into `TYPE NAME ASSIGNMENT NUMBER` and so on, where "TYPE", "NUMBER", "NAME", ... are tokens.
+This is why we're going to separate and generalize the code into [url https://en.wikipedia.org/wiki/Lexical_analysis#Token tokens], basically into building blocks.
+As a rough example, we want `[1 + (2 * 3)]` to be transformed into `[NUMBER MATHOP LBRACE NUMBER MATHOP NUMBER RBRACE]`, `[int var = 13;]` into `[TYPE NAME ASSIGNMENT NUMBER]` and so on, where "TYPE", "NUMBER", "NAME", ... are tokens.
Now we're reducing the amount of "objects" our grammars need to work on: from all characters to many (but significantly fewer) tokens.
Also we're simplifying our work, since we're trying to figure out the overall structure, it doesn't matter if we're multiplying or summing numbers, it's important that we're doing a mathematical operation on them.
Of course, each token will actually be a pair, containing it's name (NUMBER, TYPE, ...) and it's value, but our grammars will work with the names only and output the actual values at the very end.
Usually we identify at least six token types:
+.bulleted
- identifiers: variable and function names for example
-- keywords: `if`, `while`, `for`, `return`, ...
-- separators: braces, `;`
-- operators: `+`, `-`, `<=`
+- keywords: `[if]`, `[while]`, `[for]`, `[return]`, ...
+- separators: braces, `[;]`
+- operators: `[+]`, `[-]`, `[<=]`
- literals: numbers, strings, characters
- comments
@@ -346,11 +373,13 @@ In the last section we already talked about how easy implementing regexes (lexer
Proper algorithms that "implement" grammars are kind of complicated, and most can handle only specific types of grammars.
Generally we categorize them into:
-- [top-down](https://en.wikipedia.org/wiki/Top-down_parsing) algorithms, which work in the way we've been talking about grammars: start with a name and replace it with it's expression, and continue replacements until we have no more names
-- [bottom-up](https://en.wikipedia.org/wiki/Bottom-up_parsing) algorithms, where we do the opposite: for each substring we find from which rule it could've come from, replace it with the corresponding name, and continue upwards like that, until we reach the starting name
+.bulleted
+- [url https://en.wikipedia.org/wiki/Top-down_parsing top-down] algorithms, which work in the way we've been talking about grammars: start with a name and replace it with it's expression, and continue replacements until we have no more names
+- [url https://en.wikipedia.org/wiki/Bottom-up_parsing bottom-up] algorithms, where we do the opposite: for each substring we find from which rule it could've come from, replace it with the corresponding name, and continue upwards like that, until we reach the starting name
Furthermore, if our algorithms allow for ambiguity (meaning we can replace a name with any one of multiple expressions), we divide them into:
+.bulleted
- left-most derivation algorithms, where we choose the left-most valid expression
- right-most derivation algorithms, where we chose the right-most valid expression
@@ -359,7 +388,7 @@ Looking at some of the more famous ones:
##### LL
-[LL](https://en.wikipedia.org/wiki/LL_parser): top-down left-most derivations algorithm that can parse only specific types of grammars.
+[url https://en.wikipedia.org/wiki/LL_parser LL]: top-down left-most derivations algorithm that can parse only specific types of grammars.
In these grammars, every expression is uniquely identifiable by just looking at the characters (tokens) in the very beginning.
The amount of token we need to look for is very important, so we usually define LL(k) as an LL grammar that needs to look at k amount of tokens.
An "LL(k) grammar" is, by extension, a grammar which can be parsed with an LL(k) parser.
@@ -367,63 +396,63 @@ An "LL(k) grammar" is, by extension, a grammar which can be parsed with an LL(k)
So, the way we'll check if an expression matches our grammar, is by starting with the start name and reading the next k character from the input.
We check the first k character of all expressions, and if anyone of them is a name, we try with substitution for every possibility with that name, essentially peeking into the name's possibilities.
+:unordered
- As an example, the grammar:
```grammar
F -> a
S -> F | (S + F)
- ```
is LL(1).
- Let's read the input `(a + a)` (the "v" points to the symbol we're looking/peeking at):
+ Let's read the input `[(a + a)]` (the "v" points to the symbol we're looking/peeking at):
- ```
+ :code
I v
Input: (a + a)
I v
Production: S
- ```
- we start with `S`, we peek and get the `(`, in our production we're looking at a name, S.
+
+ we start with `[S]`, we peek and get the `[(]`, in our production we're looking at a name, S.
Let's check the first character of every expression of S.
- In the first expression, the first "character" is `F`, a name, so we look at every expression for `F`.
+ In the first expression, the first "character" is `[F]`, a name, so we look at every expression for `[F]`.
There is only one, which is "a", different than "(", no dice.
Now we check the second expression for S, it's first character is "(", success!
We replace:
- ```
+ :code
I v
Input: (a + a)
-
- I v
+
+ I v
Production: (S + F)
- ```
- Now the first symbol in our production is also `(`, so we increment the symbols we're looking/peeking at
- ```
+ Now the first symbol in our production is also `[(]`, so we increment the symbols we're looking/peeking at
+
+ :code
I v
Input: (a + a)
-
- I v
+
+ I v
Production: (S + F)
- ```
- we peek and get the `a`, in our production the second "character" is the name `S`, `S` has to become `a`.
- We do that same check from before, first expression for `S` is `F`, whose first (and only) expression is `a`, success!
- ```
+ we peek and get the `[a]`, in our production the second "character" is the name `[S]`, `[S]` has to become `[a]`.
+ We do that same check from before, first expression for `[S]` is `[F]`, whose first (and only) expression is `[a]`, success!
+
+ :code
I v
Input: (a + a)
-
+
I v
Production: (a + F)
- ```
- The middle characters " + " are matched and at the second `F` we check it's expressions, it has only `a`, success, replace, end of input, we're done.
- Another LL(1) example can be found in [Karl R. Abrahamson notes](http://www.cs.ecu.edu/karl/5220/spr16/Notes/Top-down/LL1.html).
+ The middle characters " + " are matched and at the second `[F]` we check it's expressions, it has only `[a]`, success, replace, end of input, we're done.
+
+ Another LL(1) example can be found in [url http://www.cs.ecu.edu/karl/5220/spr16/Notes/Top-down/LL1.html Karl R. Abrahamson notes].
- The grammar
@@ -431,43 +460,43 @@ We check the first k character of all expressions, and if anyone of them is a na
B -> b
C -> c
S -> aaB | aaC
- ```
is LL(3).
- For the input `aab`, if we look at the first two "a"s, we still don't know which rule to use: `aaB` or `aaC`.
- However if we look at the third symbol, "b", then we can determine that we need `aaB`.
+ For the input `[aab]`, if we look at the first two "a"s, we still don't know which rule to use: `[aaB]` or `[aaC]`.
+ However if we look at the third symbol, "b", then we can determine that we need `[aaB]`.
+
+- Usually parsers that implement this procedure are called [url https://en.wikipedia.org/wiki/Recursive_descent_parser recursive descent parsers]
-- Usually parsers that implement this procedure are called [recursive descent parsers](https://en.wikipedia.org/wiki/Recursive_descent_parser)
##### LR
-[LR](https://en.wikipedia.org/wiki/LR_parser): bottom-up right-most derivations algorithm.
+[url https://en.wikipedia.org/wiki/LR_parser LR]: bottom-up right-most derivations algorithm.
Conceptually, LR works in the exact opposite way to LL: for every character in the input, we find a rule that substitutes it (or that substitutes the current collection of names and character) and do so until we've reached the starting name.
Figuring out an approach isn't as intuitive and easy as with LL, but it still isn't too hard.
It all boils down to using a whole bunch of conditional statements and tracing where we "came" from.
+:unordered
- Let's look at the first LL example:
-
+
```grammar
F -> a
S -> F | (S + F)
- ```
We need to track the current state of the string, because imagine we've just read an "a", it could either be from the left or right handside of "a + a", and that changes what character to expect next.
We're going to track the state with different numbers, defined like this:
- |State (number)|Current expression ends with|
- |------|---------------|
- |0 |Nothing; this is the start|
- |1 |The name `S`; the final number should be this|
- |2 |The name `F`|
- |3 |The character "("|
- |4 |The character "a"|
- |5 |"(S"|
- |6 |"(S + "|
- |7 |"(S + F"|
- |8 |"(S + F)"; this is the one before the final|
+ .table
+ |=State (number)=||=Current expression ends with=|
+ |:0 :||:Nothing; this is the start:|
+ |:1 :||:The name `[S]`; the final number should be this:|
+ |:2 :||:The name `[F]`:|
+ |:3 :||:The character "(":|
+ |:4 :||:The character "a":|
+ |:5 :||:"(S":|
+ |:6 :||:"(S + ":|
+ |:7 :||:"(S + F":|
+ |:8 :||:"(S + F)"; this is the one before the final:|
You can think of every state number as the valid, but "unfinished" state of the current string.
For now don't think about the way this table is defined, it'll make sense later.
@@ -475,25 +504,22 @@ It all boils down to using a whole bunch of conditional statements and tracing w
Keep in mind that the way I'll show the algorithm step by step isn't really correct, but will suffice for the current moment.
Reading a character from the input means appending it to the right of String:
-
+
```
String : (
State : 0
- ```
We've read "(", so our string "ends" on a "(".
```
String : (a
State : 3
- ```
We've read "a", our string "ends" on an "a".
```
String : (a
State : 4
- ```
Here comes the clever bit, for certain states, we'll stop reading forward and do something else.
If we're on state 4, our string ends on an "a", so we're going to go backwards and replace it with an F, meaning the current state should be 2.
@@ -501,7 +527,6 @@ It all boils down to using a whole bunch of conditional statements and tracing w
```
String : (F
State : 2
- ```
Here is another such rule, if our state is 2, our string ends with an "F" and we replace it with an S, now the state is 5.
That's why we have a different state for "(S + F", if we didn't, our state would become 2 and we would make "(S + S", which isn't valid.
@@ -510,15 +535,13 @@ It all boils down to using a whole bunch of conditional statements and tracing w
```
String : (S
State : 5
- ```
We have a different state for "(S", because if we didn't, we would've gone to state 1, and could've ended the algorithm then and there, without reading the rest of the input.
- Otherwise, we continue as normal, we read the `+` and the spaces around it, going to state 6.
+ Otherwise, we continue as normal, we read the `[+]` and the spaces around it, going to state 6.
```
String : (S + a
State : 6
- ```
Now, our string ends with an "a", it's tempting to change our state to 4, but we shouldn't, this would remove our progress so far!
Better yet, this state will also be special, if we have a 6 and we end with "a", rather than going to 4, we'll substitute "a" with F now and change state to 7.
@@ -526,41 +549,39 @@ It all boils down to using a whole bunch of conditional statements and tracing w
```
String : (S + F
State : 7
- ```
And now it's trivial, we read ")", so we go to state 8.
But if we're at state 8, don't continue reading, replace with state 1.
Now that we're at state 1, if we read any character (including end of string), we'll say the string up to now matches and we're done!
-
+
It's also helpful to put what we do in different situations in another table:
- |State|If ends on|Change state to|Also do|
- |------|----------|----------------|-------|
- |0 |"(" |3 | |
- |1 | | |Nothing, we matched|
- |2 | |5 |Replace "F" with "S"|
- |3 |"a" |4 ||
- |4 | |2 |Replace "a" with "F"|
- |5 |" + " |6 | |
- |6 |"a" |7 |Replace "a" with "F"|
- |7 |")" |8 | |
- |8 | |1 |Replace "(S + F)" with "S"|
+ .table
+ |=State=||=If ends on=||=Change state to=||=Also do=|
+ |:0 :||:"(" :||:3 :||: :|
+ |:1 :||: :||: :||:Nothing, we matched:|
+ |:2 :||: :||:5 :||:Replace "F" with "S":|
+ |:3 :||:"a" :||:4 :||::|
+ |:4 :||: :||:2 :||:Replace "a" with "F":|
+ |:5 :||:" + " :||:6 :||: :|
+ |:6 :||:"a" :||:7 :||:Replace "a" with "F":|
+ |:7 :||:")" :||:8 :||: :|
+ |:8 :||: :||:1 :||:Replace "(S + F)" with "S":|
where, if there is a value in "If ends on", we read the next character, while otherwise we don't and we just execute "Change state to" and "Also do".
- You're probably wondering why the table works so weird, like why on state 3 we don't directly replace "a" with "S" and change to state 5 for example.
The reason is that the way I showed the algorithm isn't exactly how it normally works.
- Rather than tracing the current state in a variable, we trace it with a [stack](https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29).
+ Rather than tracing the current state in a variable, we trace it with a [url https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29 stack].
When you read a character and have to go to another state, the state is added to the stack (this operation is called "shift").
When we have to change characters from String (without reading anything), with a string (expression) of length j, we remove the last j added states and do a normal shift from the last state and character in String (this operation is called "reduce").
- Let's look at the same example, done with shift and reduce operations (without me showing the proper table), where pushing and popping items from the stack is done from the right side of the array:
-
+
```
String : (
State : [0]
- ```
We've read "(", add 3 on top of the stack aka shift(3).
Then we read the "a", shift(4).
@@ -568,28 +589,24 @@ It all boils down to using a whole bunch of conditional statements and tracing w
```
String : (a
State : [0, 3, 4]
- ```
With 4 we'll do a reduction, "a" gets replaced by F, 4 is removed:
```
String : (F
State : [0, 3]
- ```
If last state is 3 and last character is "F", we're doing shift(2).
```
String : (F
State : [0, 3, 2]
- ```
Now, we'll be doing a reduction, where F is replaced by S:
```
String : (S
State : [0, 3]
- ```
If last state is 3 and last character is "S", we're dong shift(5).
@@ -598,24 +615,27 @@ It all boils down to using a whole bunch of conditional statements and tracing w
This way we avoid doing different things on different states and we don't need to store the whole string, only the last few characters.
Additionally, in the real world nobody makes this table by hand, it is generated by a program, and this method makes table generation easier.
-- As for the complete table, you can view it on the [Context Free Grammar Checker](https://smlweb.cpsc.ucalgary.ca/lr0.php?grammar=S+-%3E+F+%7C+%28+S+%2B+F+%29.%0AF+-%3E+a.&substs=),
- or with a more pretty styling on [Grammophone](https://mdaines.github.io/grammophone/?s=UyAtPiBGIHwgIigiIFMgIisiIEYgIikiLgpGIC0+IGEu#/), opening "Parsing table" on the row "LR(0)".
+- As for the complete table, you can view it on the [url https://smlweb.cpsc.ucalgary.ca/lr0.php?grammar=S+-%3E+F+%7C+%28+S+%2B+F+%29.%0AF+-%3E+a.&substs= Context Free Grammar Checker],\n
+ or with a more pretty styling on [url https://mdaines.github.io/grammophone/?s=UyAtPiBGIHwgIigiIFMgIisiIEYgIikiLgpGIC0+IGEu#/ Grammophone], opening "Parsing table" on the row "LR(0)".
To read the table, remember that:
+ .bulleted
- on every row you have each state
- on every column you have each possible value in the string and "$" which signifies the end of the string
- - with `sr` or `shift` (or just with a number) you go to another state
- - with `r` or `reduce` you make the substitution in the current string and go back one state
- - `acc` or `accept` means you've reached the end and the string is valid
+ - with `[sr]` or `[shift]` (or just with a number) you go to another state
+ - with `[r]` or `[reduce]` you make the substitution in the current string and go back one state
+ - `[acc]` or `[accept]` means you've reached the end and the string is valid
+
##### LR's family
LR is more of a family of algorithms, because there are multiple different ways to generate the table, each with it's own benefits and drawbacks.
This subject is a really big can of beans, which I'm not knowledgeable enough to talk about.
-What you need to know is that there are 3 often used types: [CLR](https://en.wikipedia.org/wiki/Canonical_LR_parser), [SLR](https://en.wikipedia.org/wiki/Simple_LR_parser) and [LALR](https://en.wikipedia.org/wiki/LALR_parser).
+What you need to know is that there are 3 often used types: [url https://en.wikipedia.org/wiki/Canonical_LR_parser CLR], [url https://en.wikipedia.org/wiki/Simple_LR_parser SLR] and [url https://en.wikipedia.org/wiki/LALR_parser LALR].
-- CLR is an LR parser with 1 character lookahead (LR(1)), following [Knuth](TODO)'s original theory.
+.bulleted
+- CLR is an LR parser with 1 character lookahead (LR(1)), following [url TODO Knuth]'s original theory.
It requires a lot of memory for table generation, so Frank DeRemer created two simplifications:
- the SLR and LALR, which use significantly less memory but work with a bit less grammars
@@ -625,26 +645,29 @@ LALR is the most commonly used LR parser, however most compilers are custom-tail
If you want to learn more, I would highly suggest:
-- [LL and LR Parsing Demystified](https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html) and [LL and LR in Context: Why Parsing Tools Are Hard](https://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html) by [Josh Haberman](https://blog.reverberate.org/about/)
-- [Parsing: Top-down versus bottom-up](http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2014/11/ll.html) by [Jeffrey Kegler](https://jeffreykegler.github.io/personal/)
-- [Which Parsing Approach?](https://tratt.net/laurie/blog/2020/which_parsing_approach.html) by [Laurence Tratt](https://tratt.net/laurie/)
-- [A Guide to Parsing: Algorithms and Terminology](https://tomassetti.me/guide-parsing-algorithms-terminology/) by [Gabriele Tomassetti](https://inre.me/)
-- [Parsing](http://www.cs.ecu.edu/karl/5220/spr16/Notes/Parsing/index.html), [Top-Down Parsers](http://www.cs.ecu.edu/karl/5220/spr16/Notes/Top-down/index.html) and [Bottom-Up Parsers](http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/index.html) from [Karl R. Abrahamson](http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/index.html)'s notes
-- [How to Impement an LR(1) Parser](https://serokell.io/blog/how-to-implement-lr1-parser) by Kirill Andreev
+.bulleted
+- [url https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html LL and LR Parsing Demystified] and [url https://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html LL and LR in Context: Why Parsing Tools Are Hard] by [url https://blog.reverberate.org/about/ Josh Haberman]
+- [url http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2014/11/ll.html Parsing: Top-down versus bottom-up] by [url https://jeffreykegler.github.io/personal/ Jeffrey Kegler]
+- [url https://tratt.net/laurie/blog/2020/which_parsing_approach.html Which Parsing Approach?] by [url https://tratt.net/laurie/ Laurence Tratt]
+- [url https://tomassetti.me/guide-parsing-algorithms-terminology/ A Guide to Parsing: Algorithms and Terminology] by [url https://inre.me/ Gabriele Tomassetti]
+- [url http://www.cs.ecu.edu/karl/5220/spr16/Notes/Parsing/index.html Parsing], [url http://www.cs.ecu.edu/karl/5220/spr16/Notes/Top-down/index.html Top-Down Parsers] and [url http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/index.html Bottom-Up Parsers] from [url http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/index.html Karl R. Abrahamson]'s notes
+- [url https://serokell.io/blog/how-to-implement-lr1-parser How to Impement an LR(1) Parser] by Kirill Andreev
#### Abstract syntax tree
We already decided that the lexer will output tokens (and characters) to the parser, but we didn't talk about what the parser is supposed to output.
-It definitely has to be some sort of structural representation of the overall code, for example, for `3 + 1 * 2` we have to be able to easily find out what the left and right handsides of the `+` and `*` are.
+It definitely has to be some sort of structural representation of the overall code, for example, for `[3 + 1 * 2]` we have to be able to easily find out what the left and right handsides of the `[+]` and `[*]` are.
-Let's draw out[^nomnoml] this relationship, where the left arrow connects to the left handside and the right accordingly:
+'footnoe nomnoml The graphics are made with [url https://nomnoml.com/ nomnoml] by [url https://github.com/skanaar Daniel Kallin]
-![](./img/tree-simple.svg)
+Let's draw out[$nomnoml] this relationship, where the left arrow connects to the left handside and the right accordingly:
-Hey, that looks an awful lot like a [tree](https://en.wikipedia.org/wiki/Tree_%28data_structure%29)!
-Trees are nodes, some sort of elements, where there is a connection from one element to some other elements, with the only rule being that cycles **aren't** allowed:
+[image ./img/tree-simple.svg]
-![](./img/tree-cycle.svg)
+Hey, that looks an awful lot like a [url https://en.wikipedia.org/wiki/Tree_%28data_structure%29 tree]!
+Trees are nodes, some sort of elements, where there is a connection from one element to some other elements, with the only rule being that cycles =[aren't]= allowed:
+
+[image ./img/tree-cycle.svg]
Great, but can we represent everything else with a tree?
Why, of course, for example we can represent:
@@ -654,11 +677,10 @@ if (a > b)
c = 5;
else
d += 10;
-```
as
-![](./img/tree-if.svg)
+[image ./img/tree-if.svg]
You might ask how we generate the tree, and the answer is simple: on every step we add nodes to the tree, depending on the situation.
Let's look at a familiar example:
@@ -666,72 +688,73 @@ Let's look at a familiar example:
```grammar
N -> 1 | 2 | 3
E -> N | (E) | E + E | E * E
-```
-Let's look at the input string `2 * (1 + 3)`, while abstracting ourselves from any particular algorithm:
+Let's look at the input string `[2 * (1 + 3)]`, while abstracting ourselves from any particular algorithm:
-- we read the `2`, that is a number, we add it as a node
+:unordered
+- we read the `[2]`, that is a number, we add it as a node
- ![](./img/tree-building-1.svg)
+ .p [image ./img/tree-building-1.svg]
-- then we read the `*`, we now know our expression is in the form `E * E`.
+- then we read the `[*]`, we now know our expression is in the form `[E* E]`.
If you think about it, up to this point, we've basically been building a tree for the left handside.
- **If** the topmost element in that tree is a brace,
+ =[If]= the topmost element in that tree is a brace,
- ![](./img/tree-building-ex1.svg)
+ .p [image ./img/tree-building-ex1.svg]
- we connect it to the left handside of `*`:
+ we connect it to the left handside of `[*]`:
- ![](./img/tree-building-ex2.svg)
+ .p [image ./img/tree-building-ex2.svg]
- **Otherwise** (when it's `+` or `*` or a number), because of precedence, we'll attach the latest number to the left handside.
- However we have to be careful, if something connects to the number, we now need it to connect to the `*`.
- For example, let's say we had `1 + 2 * 3`, and we've just read the `*`.
+ =[Otherwise]= (when it's `[+]` or `[*]` or a number), because of precedence, we'll attach the latest number to the left handside.
+ However we have to be careful, if something connects to the number, we now need it to connect to the `[*]`.\n
+ For example, let's say we had `[1 + 2 * 3]`, and we've just read the `[*]`.
The tree up to this point would look like,
- ![](./img/tree-building-ex3.svg)
+ .p [image ./img/tree-building-ex3.svg]
- where the latest number we've found was `2`, but the `+` connects to it.
- So, we need to make the `2` connect to the left handside of `*`, and make `+` connect to `*` instead of `2`
+ where the latest number we've found was `[2]`, but the `[+]` connects to it.
+ So, we need to make the `[2]` connect to the left handside of `[*]`, and make `[+]` connect to `[*]` instead of `[2]`
- ![](./img/tree-building-ex4.svg)
+ .p [image ./img/tree-building-ex4.svg]
- In our original case, nothing connects to the `2` in `2 * (1 + 3)`, so we can just connect it to the left handside of `*`
+ In our original case, nothing connects to the `[2]` in `[2 * (1 + 3)]`, so we can just connect it to the left handside of `[*]`
- ![](./img/tree-building-2.svg)
+ .p [image ./img/tree-building-2.svg]
where the three dots signify there isn't anything there (but we expect there to be).
Somewhere we'll store that the next element we find has to be connected to the right handside.
-- now we read `(`, we cannot have it by itself, so we directly decide we're working with `(E)` (in our full algorithm we would need a check for existance of matching brace).
- We'll create a `()` node and because of the last step, we'll connect it to the right handside.
+- now we read `[(]`, we cannot have it by itself, so we directly decide we're working with `[(E)]` (in our full algorithm we would need a check for existance of matching brace).
+ We'll create a `[()]` node and because of the last step, we'll connect it to the right handside.
- ![](./img/tree-building-3.svg)
+ .p [image ./img/tree-building-3.svg]
- Now, moving forward, we'll be creating a subtree, essentially making a second tree, and after that is done, we'll connect it's topmost element (root) to the `()` node.
+ Now, moving forward, we'll be creating a subtree, essentially making a second tree, and after that is done, we'll connect it's topmost element (root) to the `[()]` node.
- and so on.
+
The overall algorithm is to add and change nodes every time you match something with a grammar rule, and the adding and changing is done, depending on the language, the current structure and so on.
-When discussing the middle and back-end layers, we'll talk about how to work with a generated AST, but for now your clue is the [visitor pattern](https://en.wikipedia.org/wiki/Visitor_pattern).
+When discussing the middle and back-end layers, we'll talk about how to work with a generated AST, but for now your clue is the [url https://en.wikipedia.org/wiki/Visitor_pattern visitor pattern].
### Implementing a front-end
If you want, you could implement your own lexer and parser manually, but as a start, it's worthwhile to try and use already created stuff.
-[Compiler-compilers](https://en.wikipedia.org/wiki/Compiler-compiler) are tools that create parsers (and more) from their normal formal definition.
+[url https://en.wikipedia.org/wiki/Compiler-compiler Compiler-compilers] are tools that create parsers (and more) from their normal formal definition.
The two popular ones from the old days are lex and yacc.
lex is a lexer generator and yacc is a LALR parser generator, both of which generate a corresponding C implementation of the given regular expressions and grammars.
#### lex
-Lex is the original program, from 1975, in the modern day it's successor/implementation is the open-source [flex](https://github.com/westes/flex).
+Lex is the original program, from 1975, in the modern day it's successor/implementation is the open-source [url https://github.com/westes/flex flex].
A lex source file is divided into three parts:
-```lex
+:code_lex
%{
// C code that will be put in the program verbatim
%}
@@ -745,19 +768,19 @@ A lex source file is divided into three parts:
%%
// C code
-```
-where `%{%}` is used for includes and declarations, the rules are your regular expressions and the C code is the general logic of the lexer.
-Usually you wouldn't write anything in the C code section, the defaults are fine, but you'll probably need to do one or two includes in the `%{%}` section.
-Rules are in the form `regex { C_code }`.
+where `[%{%}]` is used for includes and declarations, the rules are your regular expressions and the C code is the general logic of the lexer.
+Usually you wouldn't write anything in the C code section, the defaults are fine, but you'll probably need to do one or two includes in the `[%{%}]` section.
+
+Rules are in the form `[regex { C_code }]`.
To simplify your life, you can write only the regex or a part of it inside the "definitions" part of the file, and give it a name to use later.
-Referencing those names in later regexes is done by surrounding them in curly braces.
-Usually the `C_code` in the regex would be a return (more commonly called "emit") of a token, which will be available in a header file, but more on that later.
+Referencing those names in later regexes is done by surrounding them in curly braces.
+Usually the `[C_code]` in the regex would be a return (more commonly called "emit") of a token, which will be available in a header file, but more on that later.
Let's look at a very simple example program: every whole number is printed as "NUMBER", while everything else is printed as-is:
-```lex
+:code_lex
%{
%}
@@ -767,112 +790,107 @@ Let's look at a very simple example program: every whole number is printed as "N
[A-z]+ { printf("%s", yytext); }
%%
-```
-The syntax `[0-9]` is the same as `(0 | 1 | ... | 9)`, it works for any letters and is available in all modern regexes.
-Note that inside every regex's "body" you have an assortment of variables already set, one of them being `yytext` which is just the whole match.
-Additionally lex matches the longest possible match, so if we had a rule `[0-z]`, only it will be matched.
-If this file is located in `lexer.l`, we can transform it into a C file with:
+The syntax `[[0-9]]` is the same as `[(0 | 1 | ... | 9)]`, it works for any letters and is available in all modern regexes.
+Note that inside every regex's "body" you have an assortment of variables already set, one of them being `[yytext]` which is just the whole match.
+Additionally lex matches the longest possible match, so if we had a rule `[[0-z]]`, only it will be matched.
+
+If this file is located in `[lexer.l]`, we can transform it into a C file with:
```bash
flex lexer.l
-```
-Usually the result file is always named `lex.yy.c`.
+Usually the result file is always named `[lex.yy.c]`.
Afterwards, we can compile the C code into a working compiler:
```bash
gcc lex.yy.c -lfl
-```
-Without the `-lfl` flag, we would get a linking error, because of the `main` and `yywrap` function, which are required but aren't defined in our generated code.
+Without the `[-lfl]` flag, we would get a linking error, because of the `[main]` and `[yywrap]` function, which are required but aren't defined in our generated code.
There are three ways to fix this problem:
-1. The one I've opted for, use the `-lfl` flag to compile our C code with a (flex) library which provides both functions.
- Usually the lexer isn't meant to be ran by itself, so for the current time being, `-lfl` is the best option, the other two are fine when we get to `yacc`.
-2. Put `%option noyywrap` in the definitions section, which means the lexer will only read one file.
+:numbered
+1. The one I've opted for, use the `[-lfl]` flag to compile our C code with a (flex) library which provides both functions.
+ Usually the lexer isn't meant to be ran by itself, so for the current time being, `[-lfl]` is the best option, the other two are fine when we get to `[yacc]`.
+
+2. Put `[%option noyywrap]` in the definitions section, which means the lexer will only read one file.
+
3. Define it ourselves.
It should return 0 if our lexer should continue with the next given file, after finishing with the current one, or 1 if it should stop execution.
The function could be written in either "C code" section, but I personally prefer the last one.
```lex
int yywrap() { return 0; }
- ```
+
Of course, you can use your lex implementation or C compiler of choice, and there this might not be a problem.
-Now, if you run `./a.out` you would get a prompt, every line you write will be lexically analyzed and in our case, everything will be printed out.
+Now, if you run `[./a.out]` you would get a prompt, every line you write will be lexically analyzed and in our case, everything will be printed out.
Entering
```
The number 10 changed to 8, 38, and 19 sequentially, before becoming 0.
-```
will output
```
The number NUMBER changed to NUMBER, NUMBER, and NUMBER sequentially, before becoming NUMBER.
-```
Now let's try something more sophisticated, let's surround numbers and strings in HTML tags, the stuff that power webpages.
We would want numbers to be in the format:
```
<span class="num">number</span>
-```
and strings:
```
<span class="str">string</span>
-```
We'll define numbers as both whole digits and floating point numbers (with sign) and strings can be surrounded in either single or double quotes.
-```lex
+:code_lex
%{
%}
-/* Only multiline comments are supported, not comments that start with // */
-/* This is a definition, it's in the format "NAME regex" */
+/* Only multiline comments are supported, not comments that start with // */
+/* This is a definition, it's in the format "NAME regex" */
DIGIT [0-9]
%%
/* Comments in here have to be indented, otherwise you'll get an error */
- /* ? means 0 or 1 of the preceding group*/
- /* + means 1 or more of the preceding group*/
- /* the backward slashes are used because . and + have special meaning in regexes*/
+ /* ? means 0 or 1 of the preceding group */
+ /* + means 1 or more of the preceding group */
+ /* the backward slashes are used because . and + have special meaning in regexes */
[\+-]?{DIGIT}+(\.{DIGIT}+)? { printf("<span class=\"num\">%s</span>", yytext); }
- /* [^] is a group of characters, like [], however it specifies "all characters except the ones given"*/
- /* this way if we have "This is a string with " three quotes" it's not going to match the whole thing*/
+ /* [^] is a group of characters, like [], however it specifies "all characters except the ones given" */
+ /* this way if we have "This is a string with " three quotes" it's not going to match the whole thing */
\"[^"]*\"|'[^']*' { printf("<span class=\"str\">%s</span>", yytext); }
%%
-```
+
With the input
```
John said 10 times "2 + 2 = 5" but '2 + 2 = 4'!
-```
we'll get
```
John said <span class="num">10</span> times <span class="str">"2 + 2 = 5"</span> but <span class="str">'2 + 2 = 4'</span>!
-```
You've probably already noticed that the number inside the strings aren't matched, because the string rule results in a longer match.
-In certain programming languages, that don't have [string interpolation](https://en.wikipedia.org/wiki/String_interpolation) this is fine, but for others our regexes have to be a lot more complicated.
+In certain programming languages, that don't have [url https://en.wikipedia.org/wiki/String_interpolation string interpolation] this is fine, but for others our regexes have to be a lot more complicated.
#### yacc
-Similarly to lex, yacc originates from 1975, and it's modern replacement is [GNU Bison](https://www.gnu.org/software/bison/).
+Similarly to lex, yacc originates from 1975, and it's modern replacement is [url https://www.gnu.org/software/bison/ GNU Bison].
A yacc file looks very similarly to a lex one:
-```yacc
+:code_yacc
%{
// C code that will be put in the program verbatim
%}
@@ -886,25 +904,23 @@ A yacc file looks very similarly to a lex one:
%%
// C code
-```
+
however rather than definitions you have declarations, and the rules are in a completely different format (because they're grammars).
-Token names are defined in `declarations`, in the format
+Token names are defined in `[declarations]`, in the format
```yacc
%token NAME1 NAME2 ...
-```
-You can also define precedence with `%left` and `%right`.
-There are also other options you can set, like the start name with `%start`.
+You can also define precedence with `[%left]` and `[%right]`.
+There are also other options you can set, like the start name with `[%start]`.
Grammars are in the form
```yacc
name : TOKEN1 TOKEN2 ...
;
-```
where alternation is defined like
@@ -913,9 +929,8 @@ name : TOKEN1
| TOKEN2
| TOKEN3
;
-```
-and it always must end with a `;`.
+and it always must end with a `[;]`.
On each alternation, you can (should) specify a body, which will contain C code to be executed, if this rule is reached
```yacc
@@ -923,52 +938,51 @@ name : TOKEN1 { C code here }
| TOKEN2
| TOKEN3 { C code here }
;
-```
Another difference is that, since the parser needs a list of tokens, you cannot run it by itself, you'll also need to setup a lexer.
-Let's implement a parser for the grammar[^shift-reduce-conflicts]:
+'footnote shift-reduce-conflicts You might be tempted to try and make one for the grammar inside the [url #abstract-syntax-tree AST] section, but that one is ever so slightly problematic, because it's ambiguous (I showed why at the end of [url #implementational-difficulties-with-grammars Implementational difficulties with grammars]). Bison [url https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html can handle ambiguity by always choosing to shift], but I didn't want to complicate things.
+
+Let's implement a parser for the grammar[$shift-reduce-conflicts]:
```grammar
N -> 1 | 2 | 3
S -> N | (S + S) | (S * S)
-```
First, our tokens, we want to replace all characters with a token.
-For 1, 2 and 3, let's use the token name "NUMBER", for "(" and ")", LBRACE and RBRACE accordingly, and since there is no precedence with this grammar, we don't actually care if we have `(S + S)` or `(S * S)`, so we can assign both `+` and `*` to the token MATHOP.
+For 1, 2 and 3, let's use the token name "NUMBER", for "(" and ")", LBRACE and RBRACE accordingly, and since there is no precedence with this grammar, we don't actually care if we have `[(S + S)]` or `[(S * S)]`, so we can assign both `[+]` and `[*]` to the token MATHOP.
Meaning, our grammar would behave more like this:
```grammar
N -> 1 | 2 | 3
M -> + | *
S -> N | (S M S)
-```
-First, we need to make our `lexer.l`, it is going to be very simple:
+First, we need to make our `[lexer.l]`, it is going to be very simple:
-```lex
+:code_lex
%{
#include "parser.tab.h"
%}
%%
- /* Remember, [] is a group, [abcd] behaves like "(a | b | c | d)" and "\" escapes characters */
+ /* Remember, [] is a group, [abcd] behaves like "(a | b | c | d)" and "\\" escapes characters */
[123] { return NUMBER: }
-[\+\*] { return MATHOP; }
+[\+\\*] { return MATHOP; }
\( { return LBRACE; }
\) { return RBRACE: }
%%
-```
+
Now, tokens (names) are defined inside grammars, however our lexer needs to emit (return) them.
-That's why, when running bison on our `parser.y`, we'll also create a C header file, which contains those names already defined, so they're accessible inside `lexer.l`.
-This file is in the format `FILENAME.tab.h`, where `FILENAME.y` is our source yacc file.
+That's why, when running bison on our `[parser.y]`, we'll also create a C header file, which contains those names already defined, so they're accessible inside `[lexer.l]`.
+This file is in the format `[FILENAME.tab.h]`, where `[FILENAME.y]` is our source yacc file.
-Second, we need to make our `parser.y`:
+Second, we need to make our `[parser.y]`:
-```yacc
+:code_yacc
%{
#include "stdio.h"
int yylex();
@@ -986,16 +1000,16 @@ expr : NUMBER
%%
int yyerror(char *s) {
- printf("Error: %s\n", s);
+ printf("Error: %s\\n", s);
return 0;
}
int main() {
yyparse();
}
-```
-A quirk with GNU Bison is that you need to declare the function `yylex` and `yyerror` beforehand, manually define `yyerror` and run `yyparse` in the main function.
+
+A quirk with GNU Bison is that you need to declare the function `[yylex]` and `[yyerror]` beforehand, manually define `[yyerror]` and run `[yyparse]` in the main function.
These are precisely the first 5 and the last 8 lines of code, but for now you don't need to think about them.
Let's get to compiling.
@@ -1003,82 +1017,76 @@ First, the lexer:
```bash
flex lexer.l
-```
then our parser:
```bash
bison -d parser.y
-```
-where the `-d` option means we'll also output the `parser.tab.h` header file.
+where the `[-d]` option means we'll also output the `[parser.tab.h]` header file.
Finally, we compile both of them together into one executable:
```bash
gcc lex.yy.c parse.tab.c -lfl
-```
-Now when you run `./a.out`, if you enter a valid string, you'll see a blank line, but if it isn't valid, you'll get "Error: syntax error".
+Now when you run `[./a.out]`, if you enter a valid string, you'll see a blank line, but if it isn't valid, you'll get "Error: syntax error".
#### Doing it properly
The way we created that lexer and parser worked, but it wasn't very useful and has multiple issues we have to address:
+:ordered
1. When entering a string that isn't matched at all, it gets printed back like nothing happened.
- For example, if we enter the letter `a` or any string which doesn't have `(`, `)`, `1`, `2`, `3`, `+` or `-` characters, it will just get printed back.
- Ideally, we want to raise an error, so we're going to add one rule which catches any (non-special) character and throws an error with the built-in `yy_fatal_error`:
+ For example, if we enter the letter `[a]` or any string which doesn't have `[(]`, `[)]`, `[1]`, `[2]`, `[3]`, `[+]` or `[-]` characters, it will just get printed back.
+ Ideally, we want to raise an error, so we're going to add one rule which catches any (non-special) character and throws an error with the built-in `[yy_fatal_error]`:
```lex
. { yy_fatal_error("Bad character"); }
- ```
This rule must be the last rule, since we don't want it to be matched, if there is another rule that matches.
Remember that lex matches the longest possible string and if there are multiple rules which match the same amount of characters, only the first one is matched.
2. For every token name, returned by the lexer, we also need to have it's actual value.
- We could make a `struct`, which holds both a token name and it's value, but there is another ["built-in" mechanism](https://www.gnu.org/software/bison/manual/html_node/Token-Values.html) for that in yacc/Bison.
- We would set the global variable `yylval` to the token value, and it will be changed for every token.
+ We could make a `[struct]`, which holds both a token name and it's value, but there is another [url https://www.gnu.org/software/bison/manual/html_node/Token-Values.html "built-in" mechanism] for that in yacc/Bison.
+ We would set the global variable `[yylval]` to the token value, and it will be changed for every token.
- By default it's type is `int` (in Bison), but usually you would want it to be a [union](https://en.wikipedia.org/wiki/Union_type#C/C++).
+ By default it's type is `[int]` (in Bison), but usually you would want it to be a [url https://en.wikipedia.org/wiki/Union_type#C/C++ union].
Let's make it a union of int and char, though the first part is kind of useless, since we're only working with single digit numbers.
-
+ \n
```yacc
%union {
int num;
char chr;
}
- ```
Now, inside our lexer, rules would look like:
```yacc
RULE1 { yylval.num = 129; return TOKEN; }
RULE2 { yylval.chr = 'a'; return TOKEN; }
- ```
- Inside C blocks for grammar rules we can reference the token values with `$i`, where `i` is the i'th "token" in the expression.
- For example, in this rule, `$1` would be `(`, `$3` would be value of token `B` and `$5` would be the value of the rule name:
+ Inside C blocks for grammar rules we can reference the token values with `[$i]`, where `[i]` is the i'th "token" in the expression.
+ For example, in this rule, `[$1]` would be `[(]`, `[$3]` would be value of token `[B]` and `[$5]` would be the value of the rule name:
```yacc
rule : ( A B ) rule
;
- ```
- You can set rule "return" values by setting the variable `$$`:
+ You can set rule "return" values by setting the variable `[$$]`:
```yacc
rule : LBRACE rule RBRACE { $$ = 10; }
- ```
The way you set it's type is discussed later.
- However, `$i` isn't of type union, we cannot do something like `$i.num`, it is the precise value that was set for the token.
- Therefore, we also need to define which value from the union every token will set, which is done by adding `<PROPERTY>` before every defined token (and `PROPERTY` is a property name inside the union):
+ However, `[$i]` isn't of type union, we cannot do something like `[$i.num]`, it is the precise value that was set for the token.
+ Therefore, we also need to define which value from the union every token will set, which is done by adding `[<PROPERTY>]` before every defined token (and `[PROPERTY]` is a property name inside the union):
```yacc
%token <num> NUMBER <chr> MATHOP <chr> LBRACE <chr> RBRACE
- ```
-3. If we enter one valid math expression, we'll get no error, but when we enter another, we'll get a "syntax error"[^better-bison-errors].
+ 'footnote better-bison-errors You can add `[%define parse.error verbose]` inside definitions of your yacc file, and it will tell you what character was expected and what character was read.
+
+3. If we enter one valid math expression, we'll get no error, but when we enter another, we'll get a "syntax error"[$better-bison-errors].
That is because we try to match only one expression, after it is matched our parser is waiting for an end of file character.
Let's make it so we would try to match an expression on every line:
@@ -1086,17 +1094,15 @@ The way we created that lexer and parser worked, but it wasn't very useful and h
start : expr
| expr start
;
- ```
- A rule like `expr : expr expr` will produce shift/reduce conflicts.
- Another option is duplicating our `expr` rules and adding `expr` in the beginning or end, but that is cumbersome if we want to make changes.
+ A rule like `[expr : expr expr]` will produce shift/reduce conflicts.
+ Another option is duplicating our `[expr]` rules and adding `[expr]` in the beginning or end, but that is cumbersome if we want to make changes.
4. We're getting input from the user, but our source text (code) will be in a file.
- First, our `main` function needs to take program parameters:
+ First, our `[main]` function needs to take program parameters:
```yacc
int main(int argc, char* argv[])
- ```
Then we need to take the first argument, and open a file.
Additionally, we have to check if the file was successfully opened, and print an error and stop execution if so:
@@ -1107,30 +1113,27 @@ The way we created that lexer and parser worked, but it wasn't very useful and h
yyerror("cannot read input file!");
return 1;
}
- ```
- Now for the clever bit, actual parsing in generated code is done on the file `yyin`, which by default is the standard user input.
+ Now for the clever bit, actual parsing in generated code is done on the file `[yyin]`, which by default is the standard user input.
To read a file, all we need to do is change the value of that variable.
Also, that variable is defined externally, so first we need to add to (the top) C section:
```yacc
extern FILE* yyin;
- ```
- and then put in our `main`:
+ and then put in our `[main]`:
```yacc
yyin = input;
- ```
- On \*NIX systems (Linux, MacOS, OpenBSD, ...) you can still use user input by passing the file `/dev/stdin`.
- If you want your front-end to support multiple files, you would just need to wrap the whole body of main in a `for` loop, iterating over the whole `argv` array (remember that `argc` is the length of the array).
+ On \*NIX systems (Linux, MacOS, OpenBSD, ...) you can still use user input by passing the file `[/dev/stdin]`.
+ If you want your front-end to support multiple files, you would just need to wrap the whole body of main in a `[for]` loop, iterating over the whole `[argv]` array (remember that `[argc]` is the length of the array).
5. We need to construct an AST.
Since the exact tree structure depends on your needs, I'll make the simplest possible tree in pure C that works for this grammar.
I won't explain this in much detail, since it is just normal C code.
- ```c
+ :code_c
#include <stdlib.h>
#include <stdio.h>
@@ -1147,7 +1150,7 @@ The way we created that lexer and parser worked, but it wasn't very useful and h
out->right = right;
return out;
}
-
+
void printTree(node *n, int level) {
if (n == NULL) return;
// %*s will add level amounts of spaces (but with the "" string)
@@ -1155,18 +1158,18 @@ The way we created that lexer and parser worked, but it wasn't very useful and h
printTree(n->left, level + 1);
printTree(n->right, level + 1);
}
-
+
void freeNode(node *n) {
if (n == NULL) return;
freeNode(n->left);
freeNode(n->right);
free(n);
}
- ```
- However, all of this is quite a lot, and it would take a lot of space in `parser.y`, so let's separate it into `tree.c` and add a header file `tree.h` which contains the definitions:
- ```c
+ However, all of this is quite a lot, and it would take a lot of space in `[parser.y]`, so let's separate it into `[tree.c]` and add a header file `[tree.h]` which contains the definitions:
+
+ :code_c
#include <stdlib.h>
#include <stdio.h>
@@ -1179,35 +1182,37 @@ The way we created that lexer and parser worked, but it wasn't very useful and h
node* newNode(char val, node *left, node *right);
void printTree(node *n, int level);
void freeNode(node *n);
- ```
+
Of course, we should add some ifndef-def precompiler code, but that isn't relevant for now.
- The way we're going to use trees in our grammar is as follows: for the `NUMBER` expression of `expr`, we'll create a node with the (char) value of the number and "return" it.
- For the expression of `expr` we'll "return" a node with the value of the math operator and left and right will be the returned values.
- Inside start, after we've parsed an `expr`, we'll print out the "returned" tree and free it's memory.
+ The way we're going to use trees in our grammar is as follows: for the `[NUMBER]` expression of `[expr]`, we'll create a node with the (char) value of the number and "return" it.
+ For the expression of `[expr]` we'll "return" a node with the value of the math operator and left and right will be the returned values.
+ Inside start, after we've parsed an `[expr]`, we'll print out the "returned" tree and free it's memory.
+
+ I'm putting returned in quotes, because (as mentioned), we'll just be setting the value of `[$$]`.
+ `[$$]`'s type is set with the `[%type]` option, which works exactly like `[%token]`, but with grammar rule names.
+ However, this means that `[node]` must be available in `[%union]`, which is unfortunate but isn't a problem, we'll just add it.
- I'm putting returned in quotes, because (as mentioned), we'll just be setting the value of `$$`.
- `$$`'s type is set with the `%type` option, which works exactly like `%token`, but with grammar rule names.
- However, this means that `node` must be available in `%union`, which is unfortunate but isn't a problem, we'll just add it.
+ Now, finally, it's time to include our `[tree.h]` in `[parser.y]`, but we'll also need to include it in `[lexer.l]`.
+ The reason is that the `[%union]` appears in `[parser.tab.h]`, which means our node structure is referenced in `[parser.tab.h]`, but `[tree.h]` isn't included there.
- Now, finally, it's time to include our `tree.h` in `parser.y`, but we'll also need to include it in `lexer.l`.
- The reason is that the `%union` appears in `parser.tab.h`, which means our node structure is referenced in `parser.tab.h`, but `tree.h` isn't included there.
All in all, we'll have 4 source files for our simple front-end:
-- `lexer.l`
+:unordered
+- `[lexer.l]`
- ```lex
+ :code_lex
%{
#include "tree.h"
#include "parser.tab.h"
%}
-
+
%option noyywrap
-
+
%%
-
+
[123] { yylval.num = atoi(yytext); return NUMBER; }
[\+\*] { yylval.chr = yytext[0] ; return MATHOP; }
\( { yylval.chr = '(' ; return LBRACE; }
@@ -1215,13 +1220,13 @@ All in all, we'll have 4 source files for our simple front-end:
\ { } /* Don't do anything on spaces */
. { yy_fatal_error("Bad character"); }
-
+
%%
- ```
-- `parser.y`
- ```yacc
+- `[parser.y]`
+
+ :code_yacc
%{
#include <stdio.h>
#include "tree.h"
@@ -1231,7 +1236,7 @@ All in all, we'll have 4 source files for our simple front-end:
int yylex();
int yyerror(const char *s);
%}
-
+
%union {
int num;
char chr;
@@ -1239,61 +1244,61 @@ All in all, we'll have 4 source files for our simple front-end:
}
%token <num> NUMBER <chr> MATHOP <chr> LBRACE <chr> RBRACE
%type <n> expr
-
+
%%
-
+
start : expr { printTree($1, 0); freeNode($1); }
| expr start { printTree($1, 0); freeNode($1); }
;
-
+
expr : NUMBER { $$ = newNode($1 + '0', NULL, NULL); }
| LBRACE expr MATHOP expr RBRACE { $$ = newNode($3, $2, $4); }
;
-
+
%%
-
+
int yyerror(const char *s) {
printf("Error: %s\n", s);
return 0;
}
-
+
int main(int argc, char* argv[]) {
FILE* input = fopen(argv[1], "r");
if (input == NULL) {
yyerror("reading input file!");
return 1;
}
-
+
yyin = input;
yyparse();
}
- ```
-- `tree.h`
- ```c
+- `[tree.h]`
+
+ :code_c
#ifndef TREE
#define TREE
-
+
#include <stdlib.h>
#include <stdio.h>
-
+
typedef struct node {
char val;
struct node *left;
struct node *right;
} node;
-
+
node* newNode(char val, node *left, node *right);
void printTree(node *n, int level);
void freeNode(node *n);
-
+
#endif
- ```
-- `tree.c`
- ```c
+- `[tree.c]`
+
+ :code_c
#include "tree.h"
node* newNode(char val, node *left, node *right) {
@@ -1303,39 +1308,37 @@ All in all, we'll have 4 source files for our simple front-end:
out->right = right;
return out;
}
-
+
void printTree(node *n, int level) {
if (n == NULL) return;
printf("%*s|-%c\n", level, "", n->val);
printTree(n->left, level + 1);
printTree(n->right, level + 1);
}
-
+
void freeNode(node *n) {
if (n == NULL) return;
freeNode(n->left);
freeNode(n->right);
free(n);
}
- ```
+
+
We compile everything:
```bash
flex lexer.l && bison parser.y && gcc lex.yy.c parse.tab.c tree.c
-```
-Now, let's create the file `test.txt`:
+Now, let's create the file `[test.txt]`:
```
((1+1) * ((3+3) * 2))
-```
and run our front-end on it:
```bash
./a.out test.txt
-```
Our output will be:
@@ -1349,7 +1352,6 @@ Our output will be:
|-3
|-3
|-2
-```
Perfect, we have a good looking tree!
@@ -1359,22 +1361,4 @@ Originally I planned to put everything in one blog post, but writing the front-e
Additionally, while doing research, I found out the course actually skipped over a lot of important topics, which I'll first need to research.
Future parts will be linked right below the title at the very top, but it will probably be quite a while until I write them.
-Many thanks to [Dimitar Tagarev](https://github.com/dtagarev) for his help with reviewing this post.
-
-[^how-did-we-get-here]: Though it's obvious, I would like to point out that modern compilers are most often written in languages that are themselves compiled. You might ask yourself "where did the first compiler come from?" The answer is simple: it was written with "numbers", with direct instructions to the processor, from the time when computers were simple enough that *all* programming was done with CPU instructions.
-
-[^terminals-and-nonterminals]: Formally, we call the rule "names" nonterminals, the idea being that all normal characters, that could appear in our string, are called terminals, since they would terminate replacement and string generation. For the purposes of this post, I won't use the formal names, with the hope that using less terminology will increase understandability.
-
-[^grammar-syntax]: This is pretty much the mathematical notation, often in CS the Backus-Naur form is used, but I find that a bit harder to read. You might also make the argument that I should use a proper unicode arrow symbol, like `→`, but `->` is way more convinient.
-
-[^regular-grammars]: Such grammars are called [regular grammars](https://en.wikipedia.org/wiki/Regular_grammar), more formally, every rule has to contain at most one name and that name must be at the start or end of the string characters.
-
-[^context-free-grammars]: Be careful about cases that are too complicated, the grammar I'm showing is "context-free", but that topic is way beyond the scope of this post.
-
-[^static-typing]: Yeah yeah, in a statically typed language you might not be able to do operations on doubles and integers at the same time, but you get the point.
-
-[^nomnoml]: The graphics are made with [nomnoml](https://nomnoml.com/) by [Daniel Kallin](https://github.com/skanaar)
-
-[^shift-reduce-conflicts]: You might be tempted to try and make one for the grammar inside the [AST](#abstract-syntax-tree) section, but that one is ever so slightly problematic, because it's ambiguous (I showed why at the end of [Implementational difficulties with grammars](#implementational-difficulties-with-grammars)). Bison [can handle ambiguity by always choosing to shift](https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html), but I didn't want to complicate things.
-
-[^better-bison-errors]: You can add `%define parse.error verbose` inside definitions of your yacc file, and it will tell you what character was expected and what character was read.
+Many thanks to [url https://github.com/dtagarev Dimitar Tagarev] for his help with reviewing this post.
diff --git a/src/blog/switchut-izgorq/index.md b/src/blog/switchut-izgorq/index.du
index c86e3ed..4df8f6b 100644
--- a/src/blog/switchut-izgorq/index.md
+++ b/src/blog/switchut-izgorq/index.du
@@ -1,27 +1,32 @@
# Суичът изгоря!
+'define expected-reading 2 min
+'define created 18 November 2024
+'define edited 18 November 2024
+[$pagenav]
+
Преди няколко месеца, интернетът у-нас спря.
Все още ползваме интернет "по медна свързаност", така че проблемът почти винаги се свежда до мрежовия шкаф на улицата, който всички компании оставят в безразбор.
Обаче, тъкмо като интернетът се върна и мрежарят беше готов да си тръгне, услугата взе че спря отново.
Вече доста изнервен, след като провери шкафът още един път, влезе в сградата, изтръгна старият суич (комутатор, но аз съм отраснал с английските наименования), замени го с нов и всичко тръгна.
-Неговият отговор, разбира се, беше че "Суичът е изгорял", заедно с един *любезен* коментар как "Тази инсталация вече е стара, трябва да си купите оптичен интернет, за да не ви горят суичовете и да не трябва да идвам аз!"
+Неговият отговор, разбира се, беше че "Суичът е изгорял", заедно с един *[любезен]* коментар как "Тази инсталация вече е стара, трябва да си купите оптичен интернет, за да не ви горят суичовете и да не трябва да идвам аз!"
Предвидимо, самият суич ни го беше оставил и си тръгна по пътя.
-Та по-късно през деня седнах с един [стар AC/DC адаптер](https://www.globalsources.com/AC-DC-adapter/plug-in-AC-DC-Adapter-1188075760p.htm) и какво намирам: устройството си работи перфектно.
+Та по-късно през деня седнах с един [url https://www.globalsources.com/AC-DC-adapter/plug-in-AC-DC-Adapter-1188075760p.htm стар AC/DC адаптер] и какво намирам: устройството си работи перфектно.
-![](./img/switch-on.JPG "Разбира се, тествах и самите портове дали пускат данни")
+[image ./img/switch-on.JPG "Разбира се, тествах и самите портове дали пускат данни"]
Отдолу си има етикет на който пише, че приема 12V на 0.5A, единствено не пише дали центърът е положителен или отрицателен.
След малко бърникане с мултицедът, лесно се вижда че първото е вярно.
-![](./img/switch-back.JPG "Хартиеното тиксо с полярността е моя добавка")
+[image ./img/switch-back.JPG "Хартиеното тиксо с полярността е моя добавка"]
-Благодарение на етикетът, бързо се намира и оригиналната [уебстраница на която NetworkPartner са го продавали](https://networkpartner.eu/product/8-port-gb-switch/).
+Благодарение на етикетът, бързо се намира и оригиналната [url https://networkpartner.eu/product/8-port-gb-switch/ уебстраница на която NetworkPartner са го продавали].
Единственият въпрос който остава, е какво е накарало интернетът да спре втория път?
-Оригиналната инсталация идва от М-Тел, и техния *талант* е решил да остави суичът да си виси във въздуха, държан само от кабелите, които се свързват към него, включително кабела за захранване.
+Оригиналната инсталация идва от М-Тел, и техния *[талант]* е решил да остави суичът да си виси във въздуха, държан само от кабелите, които се свързват към него, включително кабела за захранване.
Моето предположение е, че захранването просто се е изплъзнало с малко от буксата докато са го оглеждали.
diff --git a/src/blog/taming-the-fun-too/index.md b/src/blog/taming-the-fun-too/index.du
index 46ce820..bbaa677 100644
--- a/src/blog/taming-the-fun-too/index.md
+++ b/src/blog/taming-the-fun-too/index.du
@@ -1,46 +1,55 @@
# Taming the Fun-too
-Let's set the scene: it's October of last year and I just began my first year as a university student. For the first time in my life, I was able to meet people who were significantly ~~nerdier~~ cooler than me.
-One particular dude I met introduced me to [Funtoo](https://funtoo.org), a boutique fork of [Gentoo](https://gentoo.org).
+'define expected-reading 7 min
+'define created 04 December 2022
+'define edited 04 December 2022
+[$pagenav]
+
+Let's set the scene: it's October of last year and I just began my first year as a university student. For the first time in my life, I was able to meet people who were significantly ~[nerdier]~ cooler than me.
+One particular dude I met introduced me to [url https://funtoo.org Funtoo], a boutique fork of [url https://gentoo.org Gentoo].
Now, I'm not a very big fan of distro hopping, it takes too much time and you often find yourself not liking the finished product, resulting in further distro hopping.
-However, at that time I was a bit softened by my growing pains with Fedora, the sweat promises of improved efficiency and usability, and the fact that fun is in the name! *What could go wrong* :)
+However, at that time I was a bit softened by my growing pains with Fedora, the sweat promises of improved efficiency and usability, and the fact that fun is in the name! *[What could go wrong]* :)
-So, about a month later I bit the bullet, and installed it on my main computer. It has now been a tad more than a year later and I can comfortably say: *a lot could go wrong...*
+So, about a month later I bit the bullet, and installed it on my main computer. It has now been a tad more than a year later and I can comfortably say: *[a lot could go wrong...]*
-<br>
+\n
In the same way that a distro is made to solve a certain problem, every distro introduces a fundamental flaw in it's design. Ubuntu solves the "it's too complicated" problem, but introduces issues with performance. Arch solves "my packages are too old and what I need isn't there" issue, but introduces "my packages are too new and something just broke".
-Then there's Funtoo. You might reason, since it's a fork of Gentoo, it's big flaw is the fact that you need to compile every package, with the prize being unparalleled efficiency. So did I, but as it turns out there is another, much larger flaw: **packages**.
-The distribution is a lot smaller than it's big brother so a lot of stuff, understandably, cannot be tested. However, the real kicker is that package ebuilds[^ebuilds] are generated in a different way from Gentoo.
+'footnote ebuilds Files with instructions and settings for the package manager (portage) on how to build a specific package
+
+Then there's Funtoo. You might reason, since it's a fork of Gentoo, it's big flaw is the fact that you need to compile every package, with the prize being unparalleled efficiency. So did I, but as it turns out there is another, much larger flaw: =[packages]=.
+The distribution is a lot smaller than it's big brother so a lot of stuff, understandably, cannot be tested. However, the real kicker is that package ebuilds[$ebuilds] are generated in a different way from Gentoo.
This often means that using a Gentoo ebuild will make the problem even worse, but sometimes it does work out.
-<br>
+\n
The first such problem child was QtWebEngine. As the name suggests, it gives the ability for graphical applications, made with the Qt framework, to render webpages.
-I don't *need* it for my setup, but there are a couple of useful programs that required it.
+I don't *[need]* it for my setup, but there are a couple of useful programs that required it.
-What would happen is, after about 3 hours of compiling, the compilation would just stop, without any errors, anywhere. To add insult to injury, because I hadn't set up [ccache](https://ccache.dev/) at the time, everything would have to be compiled *all over again*.
+What would happen is, after about 3 hours of compiling, the compilation would just stop, without any errors, anywhere. To add insult to injury, because I hadn't set up [url https://ccache.dev/ ccache] at the time, everything would have to be compiled *[all over again]*.
A fairly deep dive into different forums led me to the wondrous conclusion that I needed to remove a certain build flag, which wasn't enabled in the first place...
-After *much* tweaking and trying, I found out there just wasn't enough memory, the package needed at least 32 GiB (including swap) of memory for a successful compilation... D'oh!
-And here comes the really bad part: I had setup a swapfile of adequate size! However, as it turned out, in the configuration I tried loading it before loading the drive it was stored in... **Double D'OH!!**
+After *[much]* tweaking and trying, I found out there just wasn't enough memory, the package needed at least 32 GiB (including swap) of memory for a successful compilation... D'oh!
+And here comes the really bad part: I had setup a swapfile of adequate size! However, as it turned out, in the configuration I tried loading it before loading the drive it was stored in... =[Double D'OH!!]=
-<br>
+\n
Then came the big boss: python. Now, I wasn't planning on doing any software development with it, but as it turned out, other people had, so certain packages had building issues.
And what was the exact issue you might ask?
-Well, to put it simply, Funtoo had official ebuilds for python 3.7, but a lot of packages needed at least version 3.8. This time however, I had a *brilliant* idea: I would copy Gentoo's python 3.8 ebuilds!
+Well, to put it simply, Funtoo had official ebuilds for python 3.7, but a lot of packages needed at least version 3.8. This time however, I had a *[brilliant]* idea: I would copy Gentoo's python 3.8 ebuilds!
+
+'footnote circular-dependency To build package A you'll need to have package B installed. But to build package B, you'll need package A installed.
What I didn't realize, was that I had unknowingly opened Pandora's box.
-Over time I needed to install more and more python packages from Gentoo, until one day I created an *unsolvable* circular dependency[^circular-dependency].
-Usually there are solutions to such situations, but I kid you not, I had tried **everything** and **nothing worked**.
+Over time I needed to install more and more python packages from Gentoo, until one day I created an *[unsolvable]* circular dependency[^circular-dependency].
+Usually there are solutions to such situations, but I kid you not, I had tried =[everything]= and =[nothing worked]=.
This time, there isn't even a solution, I just made sure to never upgrade these packages again.
Which proved problematic, since these packages were important and over time other stuff broke, but that wouldn't be relevant for long.
-<br>
+\n
Not too soon after, armageddon struck: glibc, GNU's C library. All I wanted to do was try out Ungoogled Chromium, but not as a flatpak.
The only thing standing in the way was the requirement of "glibc 3.4.29", while all I had was 2.70.0.
@@ -52,25 +61,20 @@ That didn't work and there was another compiling issue (that I can't remember) w
Sanity check to keep you from breaking your system:
Downgrading glibc is not supported and a sure way to destruction.
Aborting to save your system.
-```
+
"Umm what?" was my reaction too. For reasons not completely clear to me, this turns out to be yet another roadblock. Did I mention a couple applications also stopped working after the upgrade?
Unfortunately my believes and ego were firmly set in stone, "Yeah, but I know what I'm doing, I'm downgrading from a non-Funtoo glibc, it will be fine!"
-A sanity check override and a package downgrade later, *it wasn't...*
+A sanity check override and a package downgrade later, *[it wasn't...]*
Yes, my system was broken. Very broken. So broken in fact, portage wasn't working, so un-downgrading was not an option. And, of course, booting successfully my machine up ever again wasn't an option either...
-Thank goodness for [Timeshift](https://github.com/linuxmint/timeshift)'s system restore functionality or I would've had to rebuild my whole system.
+Thank goodness for [url https://github.com/linuxmint/timeshift Timeshift]'s system restore functionality or I would've had to rebuild my whole system.
-<br>
+\n
-There are **a lot** of other situations in which Funtoo's package difficulties and my sheer incompetence have led to wasted time and broken stuff, but these are the main ones that stand out in my mind (or more accurately, the ones that I still remember). Nowadays I use the distro in a much smarter fashion, with a much tighter grip.
+There are =[a lot]= of other situations in which Funtoo's package difficulties and my sheer incompetence have led to wasted time and broken stuff, but these are the main ones that stand out in my mind (or more accurately, the ones that I still remember). Nowadays I use the distro in a much smarter fashion, with a much tighter grip.
-Although I still need Gentoo packages, I install them from Funtoo's portage Gentoo kit.
-Although I still have issues with packages not being able to be built, I just mask[^mask] them until I have adequate time/energy (or until someone fixes it).
-Although everything that has happened, for now, I'm still sticking with Funtoo.
-
-
-[^ebuilds]: Files with instructions and settings for the package manager (portage) on how to build a specific package
+'footnote mask All ebuilds that are "masked", will not be used (therefore, corresponding package will not be compiled and installed/upgraded)
-[^mask]: All ebuilds that are "masked", will not be used (therefore, corresponding package will not be compiled and installed/upgraded)
-
-[^circular-dependency]: To build package A you'll need to have package B installed. But to build package B, you'll need package A installed.
+Although I still need Gentoo packages, I install them from Funtoo's portage Gentoo kit.\n
+Although I still have issues with packages not being able to be built, I just mask[$mask] them until I have adequate time/energy (or until someone fixes it).\n
+Although everything that has happened, for now, I'm still sticking with Funtoo.
diff --git a/src/blog/the-physics-behind-a-black-hole-shader/index.md b/src/blog/the-physics-behind-a-black-hole-shader/index.du
index 13ca197..cd9f779 100644
--- a/src/blog/the-physics-behind-a-black-hole-shader/index.md
+++ b/src/blog/the-physics-behind-a-black-hole-shader/index.du
@@ -1,27 +1,38 @@
# The physics behind a black hole shader
-## Contents
+'define expected-reading 22 min
+'define created 12 December 2023
+'define edited 06 October 2024
+[$pagenav]
+
+:contents
+:numbered
+1. [url #what-do-the-physics-say What do the physics say?]
+ .numbered
+ 1. [url #what-is-gravity What is gravity?]
+ 2. [url #what-does-it-mean-to-bend-space What does it mean to bend space?]
+ 3. [url #how-to-handle-the-EFEs How to handle the EFEs?]
+ 4. [url #what-is-a-black-hole What is a black hole?]
+ 5. [url #what-about-speed-and-time What about speed and time?]
+
+2. [url #finding-a-formula Finding a formula]
+3. [url #applying-the-formula-to-bend-lights-path Applying the formula to “bend” light’s path]
+ .numbered
+ 1. [url #properties-of-a-black-hole Properties of a black hole]
+
+4. [url #light-bending-algorithm Light-bending algorithm]
+5. [url #appendix Appendix]
+
-1. [What do the physics say?](#what-do-the-physics-say)
- 1. [What is gravity?](#what-is-gravity)
- 2. [What does it mean to bend space?](#what-does-it-mean-to-bend-space)
- 3. [How to handle the EFEs?](#how-to-handle-the-EFEs)
- 4. [What is a black hole?](#what-is-a-black-hole)
- 5. [What about speed and time?](#what-about-speed-and-time)
-2. [Finding a formula](#finding-a-formula)
-3. [Applying the formula to “bend” light’s path](#applying-the-formula-to-bend-lights-path)
- 1. [Properties of a black hole](#properties-of-a-black-hole)
-4. [Light-bending algorithm](#light-bending-algorithm)
-5. [Appendix](#appendix)
Back in August 2023 I had to submit a project for an elective WebGL programming course in university.
I chose to create an interactive and animated black hole demo.
The primary idea was to show how the gravitational pull of black holes "bends" light and how the result looks from different points of view.
Then in the December of that same year, I sat down and started writing a blog post (as you may notice from the "Created" date), explaining how some of the more complicated parts were made.
-Funnily enough, I started finding errors... a *lot* of errors.
+Funnily enough, I started finding errors... a *[lot]* of errors.
-As it turned out, my implementation was completely wrong, but somehow I fudged the formulas around in just the right way to make it *look* correct.
+As it turned out, my implementation was completely wrong, but somehow I fudged the formulas around in just the right way to make it *[look]* correct.
So the post got delayed and sparsely rejuvenated over the following months.
For this reason I chose to take up two related electives this year: one on general relativity and one on ray tracing, with the hopes of gaining enough understanding of the material to rework the original solution into something proper.
@@ -36,13 +47,13 @@ I'll assume you don't know much about physics, but are familiar with mathematics
The "big words" version of what we're going to explore is:
-Using [Einstein's field equations][EFE], we can precisely calculate the curvatures in space(time) at every point around a black hole.
-Obviously we're going to use [Schwarzschild metric](https://en.wikipedia.org/wiki/Schwarzschild_metric) on a (Schwarzschild) black hole.
-To further simplify our calculations, we can make approximations using [celestial mechanics](https://en.wikipedia.org/wiki/Celestial_mechanics).
+'define EFE https://en.wikipedia.org/wiki/Einstein_field_equations
-[EFE]: https://en.wikipedia.org/wiki/Einstein_field_equations
+Using [url [$EFE] Einstein's field equations], we can precisely calculate the curvatures in space(time) at every point around a black hole.
+Obviously we're going to use [url https://en.wikipedia.org/wiki/Schwarzschild_metric Schwarzschild metric] on a (Schwarzschild) black hole.
+To further simplify our calculations, we can make approximations using [url https://en.wikipedia.org/wiki/Celestial_mechanics celestial mechanics].
-This is not *necessary* to understand, but it will make our goal **much** clearer.
+This is not *[necessary]* to understand, but it will make our goal =[much]= clearer.
Now, let's try and unravel everything.
@@ -51,70 +62,70 @@ Now, let's try and unravel everything.
Everything with mass applies a "pulling" force to everything else with mass.
It's easy to see this is true, but we get into trouble when trying to find a formula which predicts/calculates that force.
-Newton gave it a good shot, with his [3 laws of motion](https://en.wikipedia.org/wiki/Newton%27s_laws_of_motion), which proved to be correct for about a century and a half.
+Newton gave it a good shot, with his [url https://en.wikipedia.org/wiki/Newton%27s_laws_of_motion 3 laws of motion], which proved to be correct for about a century and a half.
They even helped the discovery of Neptune, since measurements showed that the orbit of Uranus didn't meet expectations if there wasn't another planet meddling with things.
-The real crux of the issue came when the same problem occurred with [Mercury's orbit](https://en.wikipedia.org/wiki/Mercury_%28planet%29#Advance_of_perihelion), but no new planet was found.
+The real crux of the issue came when the same problem occurred with [url https://en.wikipedia.org/wiki/Mercury_%28planet%29#Advance_of_perihelion Mercury's orbit], but no new planet was found.
-As it turned out, Newton's formulae had only been approximations, they worked when light (and therefore [causality, or the speed at which changes propagate](https://www.youtube.com/watch?v=msVuCEs8Ydo)) had infinite speed.
+As it turned out, Newton's formulae had only been approximations, they worked when light (and therefore [url https://www.youtube.com/watch?v=msVuCEs8Ydo causality, or the speed at which changes propagate]) had infinite speed.
-Albert Einstein's general theory of relativity showed that gravity wasn't a "force which pulled", it was actually an effect which **bent** space.
-And that only happened because the (**constant**) speed of light wasn't infinite.
+Albert Einstein's general theory of relativity showed that gravity wasn't a "force which pulled", it was actually an effect which =[bent]= space.
+And that only happened because the (=[constant]=) speed of light wasn't infinite.
### What does it mean to bend space?
+'footnote line-definition This is the mathematical definition of a line, obviously in conversation we refer to a line segment as a line. But this distinction will be useful.
+
Think of a flat surface, like a table.
What is the shortest distance between two points?
Obviously, that's a straight line segment.
-If you then extend that segment, so it has an infinite length, it becomes a line[^line-definition].
-
-[^line-definition]: This is the mathematical definition of a line, obviously in conversation we refer to a line segment as a line. But this distinction will be useful.
+If you then extend that segment, so it has an infinite length, it becomes a line[$line-definition].
However, what if our surface isn't flat?
Imagine two points on a sphere, what is the shortest distance between them?
-Obviously, it's an arc of a circle and extending it to it's maximum possible length, we get a [great circle](https://en.wikipedia.org/wiki/Great_circle).
+Obviously, it's an arc of a circle and extending it to it's maximum possible length, we get a [url https://en.wikipedia.org/wiki/Great_circle great circle].
-![](./img/Illustration_of_great-circle_distance.svg.png)
-*Image by CheCheDaWaff on [Wikipedia](https://commons.wikimedia.org/w/index.php?curid=48187293)*
+[image ./img/Illustration_of_great-circle_distance.svg.png]\n
+*[Image by CheCheDaWaff on [url https://commons.wikimedia.org/w/index.php?curid=48187293 Wikipedia]]*
Now, what does it mean to go "forwards"?
On a flat surface, we can define it as "following a (straight) line segment", on our sphere we can say "following an arc of a great circle".
-Better yet, in geometry there are [geodesics](https://en.wikipedia.org/wiki/Geodesic), the general term for a curve on any surface which is the shortest[^geodesics-are-local] path between any two points.
+'footnote geodesics-are-local This actually isn't completely true, a geodesic is the "locally shortest distance", I've skipped the details since they aren't really that important for our purposes. More info can be found on [url https://en.wikipedia.org/wiki/Geodesic#Introduction Wikipedia].
+
+Better yet, in geometry there are [url https://en.wikipedia.org/wiki/Geodesic geodesics], the general term for a curve on any surface which is the shortest[$geodesics-are-local] path between any two points.
So now we can say "going forwards means going along a geodesic".
-[^geodesics-are-local]: This actually isn't completely true, a geodesic is the "locally shortest distance", I've skipped the details since they aren't really that important for our purposes. More info can be found on [Wikipedia](https://en.wikipedia.org/wiki/Geodesic#Introduction).
+'footnote parallels-of-latitude You might think about the latitudinal lines on a globe, they are indeed parallel (equidistant), but if you take any two points on the same such line, the distance between them won't be the smallest.
It's important to note that an arbitrary geodesic doesn't have most properties you might be used to.
-For example, on a flat surface, we can have parallel lines, but on our sphere, great circles will always intersect[^parallels-of-latitude].
+For example, on a flat surface, we can have parallel lines, but on our sphere, great circles will always intersect[$parallels-of-latitude].
-[^parallels-of-latitude]: You might think about the latitudinal lines on a globe, they are indeed parallel (equidistant), but if you take any two points on the same such line, the distance between them won't be the smallest.
-
-This is what gravity does, it doesn't pull or push, it *bends*, and more precisely, it **bends geodesics**.
-Furthermore, we live in three spacial dimensions, so we can move in three *different directions*.
+This is what gravity does, it doesn't pull or push, it *[bends]*, and more precisely, it =[bends geodesics]=.
+Furthermore, we live in three spacial dimensions, so we can move in three *[different directions]*.
The resultant effect is that if you travel perfectly forwards in a spaceship and pass by an object with mass (like a planet) from a close enough distance, your path will be curved, without you steering your ship.
-Although not yet mentioned, you need to know that **photons** (light) **don't have mass**!
+Although not yet mentioned, you need to know that =[photons]= (light) =[don't have mass]=!
In effect, in a universe where there is only light bouncing around, Newton's equations still work.
-On that note, the point that light **doesn't** travel at an infinite speed is significant.
+On that note, the point that light =[doesn't]= travel at an infinite speed is significant.
When the opposite is true, General Theory of Relativity collapses into the Newtonian equations!
-Going back on track, Einstein gives us the necessary equations for those geodesics, the [Einstein Field Equations][EFE].
+Going back on track, Einstein gives us the necessary equations for those geodesics, the [url [$EFE] Einstein Field Equations].
### How to handle the EFEs?
Although they're called equations the result/output we get from solving them isn't a number!
-It's a function, which *more or less* takes the parameters of objects in the universe and returns *how* they will all behave.
-To be more precise, the output isn't *really* a function, it's a "metric", which is a distinctly different mathematical object.
+It's a function, which *[more or less]* takes the parameters of objects in the universe and returns *[how]* they will all behave.
+To be more precise, the output isn't *[really]* a function, it's a "metric", which is a distinctly different mathematical object.
-In the 1910s Schwarzschild solved the equations for a universe where there is only one non-rotating[^schwm-assumptions] particle with mass, then in the 1960s the equations were solved when that particle could rotate, that's it.
-There are plenty of other mathematical solutions, but we have been able to relate the "real" world to only those two.
+'footnote schwm-assumptions He also assumed the body didn't have an electric charge and the [url https://en.wikipedia.org/wiki/Cosmological_constant cosmological constant] is zero.
-[^schwm-assumptions]: He also assumed the body didn't have an electric charge and the [cosmological constant](https://en.wikipedia.org/wiki/Cosmological_constant) is zero.
+In the 1910s Schwarzschild solved the equations for a universe where there is only one non-rotating[$schwm-assumptions] particle with mass, then in the 1960s the equations were solved when that particle could rotate, that's it.
+There are plenty of other mathematical solutions, but we have been able to relate the "real" world to only those two.
This may sound unsatisfactory, but in practice, it's quite enough.
-In the solar system, [>99.86% of mass is in the Sun](https://en.wikipedia.org/wiki/Solar_System), so assuming all other objects are massless, we get enough precision to explain Mercury's orbit.
+In the solar system, [url https://en.wikipedia.org/wiki/Solar_System >99.86% of mass is in the Sun], so assuming all other objects are massless, we get enough precision to explain Mercury's orbit.
We can apply the same idea to our simulation, leaving all objects which aren't our black hole without mass.
Schwarzschild's metric and accompanying black hole properties are the simplest possible solution, so we'll use that.
@@ -123,8 +134,8 @@ Schwarzschild's metric and accompanying black hole properties are the simplest p
Let's imagine atoms as a set of glass marbles, scattered on a table:
-![](https://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Marbles_from_Indonesia.jpg/1280px-Marbles_from_Indonesia.jpg)
-*Image from By Okkisafire on [Wikipedia](https://commons.wikimedia.org/w/index.php?curid=30338734)*
+[image https://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Marbles_from_Indonesia.jpg/1280px-Marbles_from_Indonesia.jpg]\n
+*[Image from By Okkisafire on [url https://commons.wikimedia.org/w/index.php?curid=30338734 Wikipedia]]*
Now, start pushing from all sides of the table to it's center.
In the beginning, you'll mostly roll them, until they all get in contact with each other.
@@ -134,37 +145,37 @@ By increasing the force with which you push on them, after a certain threshold,
Those shards will still have some fight in them, so after increasing your force by another level, you'll turn all of those shards into tiny glass granules.
A similar occurrence happens with atoms.
-Normally atoms are spread apart, by pushing them together, at a certain point (ignoring the orbiting electrons) all nuclei will be "touching" and the [nuclear force](https://en.wikipedia.org/wiki/Nuclear_force) will keep them together.
+Normally atoms are spread apart, by pushing them together, at a certain point (ignoring the orbiting electrons) all nuclei will be "touching" and the [url https://en.wikipedia.org/wiki/Nuclear_force nuclear force] will keep them together.
By further increasing your pushing force you can overwhelm the nuclear force and "shatter" the nuclei into their subatomic particles.
-Assuming an enormous explosion doesn't happen, and you can keep increasing your force, it's also possible to overwhelm the "subatomic forces" that keep those subatomic particles "together"[^matter-together].
-However, those subatomic particles are more commonly referred to as [elementary particles](https://en.wikipedia.org/wiki/Elementary_particle), meaning there are no "granules" into which the elementary particles can break down.
+'footnote matter-together Technically, it's more accurate to say "matter apart", since after the collapse matter is as close together as physically possible, and the nuclear forces keep everything in order but also separated. However, considering the intuitive approach I'm striving for, "matter together" is simpler to understand.
-[^matter-together]: Technically, it's more accurate to say "matter apart", since after the collapse matter is as close together as physically possible, and the nuclear forces keep everything in order but also separated. However, considering the intuitive approach I'm striving for, "matter together" is simpler to understand.
+Assuming an enormous explosion doesn't happen, and you can keep increasing your force, it's also possible to overwhelm the "subatomic forces" that keep those subatomic particles "together"[$matter-together].
+However, those subatomic particles are more commonly referred to as [url https://en.wikipedia.org/wiki/Elementary_particle elementary particles], meaning there are no "granules" into which the elementary particles can break down.
It's not possible for those particle to be completely unbreakable, since that would mean they could theoretically sustain infinite amounts of force.
Such an assumption is unthinkable.
Then that leaves us with only one solution: laws of matter "break".
If nothing can keep the elementary particles "together", so keep matter "together", then the result is a sort of "collapse", all of that matter just "deflates" into a single, infinitely small point (but the amount of mass isn't infinite, it's the sum of mass from the particles that collapsed).
-That point is called a **black hole**.
+That point is called a =[black hole]=.
This object is very bizarre, generally it doesn't have too much properties, but the ones it has are really unique.
In our case, the only important part is it's effect on gravity, and more precisely, light.
-Since a black hole is a single infinitely small point, then all of it's mass is concentrated on that point, making it alter the geodesics in a relatively small area of space **a lot**.
+Since a black hole is a single infinitely small point, then all of it's mass is concentrated on that point, making it alter the geodesics in a relatively small area of space =[a lot]=.
So much so, if you get too close, you will not be able to overwhelm gravity and "merge" into that infinitesimal point:
-![](https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/CNX_UPhysics_13_07_spacetime.png/800px-CNX_UPhysics_13_07_spacetime.png?20171124170318)
-*The white lines are our geodesics*
-*Image by OpenStax University Physics on [Wikipedia](https://commons.wikimedia.org/w/index.php?curid=64307901)*
+[image https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/CNX_UPhysics_13_07_spacetime.png/800px-CNX_UPhysics_13_07_spacetime.png?20171124170318]\n
+*[The white lines are our geodesics]*\n
+*[Image by OpenStax University Physics on [url https://commons.wikimedia.org/w/index.php?curid=64307901 Wikipedia]]*
A fascinating realization is that light always travels along geodesics ("forwards"), therefore this extreme bending allows us to view otherwise obstructed objects.
-We call that effect [gravitational lensing](https://en.wikipedia.org/wiki/Gravitational_lens).
+We call that effect [url https://en.wikipedia.org/wiki/Gravitational_lens gravitational lensing].
Though not unique to black holes, that's when the effect is strongest:
-![](https://upload.wikimedia.org/wikipedia/commons/0/02/Gravitational_lens-full.jpg)
-*Notice how the gray arrows show the path light travels from a galaxy that is behind (obstructed by) the black hole*
+[image https://upload.wikimedia.org/wikipedia/commons/0/02/Gravitational_lens-full.jpg]\n
+*[Notice how the gray arrows show the path light travels from a galaxy that is behind (obstructed by) the black hole]*
I'll abstain from explaining the specifics of light, but you may think of it as a small particle, "similar" to an electron, travelling through space.
In fact, Newton understood light to be just that, and called the underlying particle a "corpuscle".
@@ -176,38 +187,39 @@ Two of the most significant things Einstein's theory shows, which I've left out
Which also signifies that our geodesics are actually four dimensional, or in other words, gravity also bends the observed passage of time!
This is relevant for light, since it's speed is constant and it always travels along a geodesic, but to an outside observer it doesn't look that way.
-However, in our simulation, we **only** care about how thing look, so it will make our live much simpler if we try to ignore reality wherever we can.
+However, in our simulation, we =[only]= care about how thing look, so it will make our live much simpler if we try to ignore reality wherever we can.
Therefore, to calculate by how much light will move and change, we'll start with the EFEs and then simplify and approximate until we get something useable.
## Finding a formula
-Let's get down to business, our starting point, the [Schwarzschild metric](https://en.wikipedia.org/wiki/Schwarzschild_metric), in Schwarzschild coordinates, looks like this:
+Let's get down to business, our starting point, the [url https://en.wikipedia.org/wiki/Schwarzschild_metric Schwarzschild metric], in Schwarzschild coordinates, looks like this:
-![](./img/Schwarzschild-metric-in-Schwarzschild-coordinates-wikipedia.png)
+[image ./img/Schwarzschild-metric-in-Schwarzschild-coordinates-wikipedia.png]
-**YOUCH!**
+=[YOUCH!]=
-The variables themselves aren't that bad: `c` is the speed of light, <code>&tau;</code> is time, <code>&Omega;</code>, `t` and `r` are Schwarzschild coordinates.
+The variables themselves aren't that bad: `[c]` is the speed of light, <code>&tau;</code> is time, <code>&Omega;</code>, `[t]` and `[r]` are Schwarzschild coordinates.
-However, as you can see, there are two big problems: we have to calculate derivatives (that's what the `d` signifies) and convert from Schwarzschild coordinates to normal (euclidean) coordinates, that the computer understands "natively".
-This would be **too slow** to render in real time.
+However, as you can see, there are two big problems: we have to calculate derivatives (that's what the `[d]` signifies) and convert from Schwarzschild coordinates to normal (euclidean) coordinates, that the computer understands "natively".
+This would be =[too slow]= to render in real time.
-Thankfully [Riccardo Antonelli](https://github.com/rantonels) was able to do all of our coordinate conversions and use Newton's ideas to simplify the living crap out of that monster, turning it into something digestible:
+Thankfully [url https://github.com/rantonels Riccardo Antonelli] was able to do all of our coordinate conversions and use Newton's ideas to simplify the living crap out of that monster, turning it into something digestible:
-![](./img/riccardo-antonelli-schwarzschild-black-hole-force-field-formula.png)
+[image ./img/riccardo-antonelli-schwarzschild-black-hole-force-field-formula.png]
Explaining his steps and the formula is way beyond the scope of my understanding and this post.
-He explains it in more mathematical detail [here](http://spiro.fisica.unipd.it/~antonell/schwarzschild/).
+He explains it in more mathematical detail [url http://spiro.fisica.unipd.it/~antonell/schwarzschild/ here].
But now, finally, we can get a plan for our simulation:
+.bulleted
- represent light as particles
- move each particle in a direction and amount specified by the EFE-based formula
- rinse and repeat until the light hits something
Question now is: what do all of those letters represent?
-This turned out to be a much harder problem than it should have, I actually had to refer [Ricardo Antonelli's](https://github.com/rantonels/starless/blob/7a0c3c4efdc0666f53dcfa48d310fb2164be2d1a/tracer.py) and [Dmitry Brant's](https://dmitrybrant.com/2018/12/11/ray-tracing-black-holes) implementation in their projects, alongside copious articles on Wikipedia to fully grasp how to put it to work.
+This turned out to be a much harder problem than it should have, I actually had to refer [url https://github.com/rantonels/starless/blob/7a0c3c4efdc0666f53dcfa48d310fb2164be2d1a/tracer.py Ricardo Antonelli's] and [url https://dmitrybrant.com/2018/12/11/ray-tracing-black-holes Dmitry Brant's] implementation in their projects, alongside copious articles on Wikipedia to fully grasp how to put it to work.
## Applying the formula to "bend" light's path
@@ -215,68 +227,82 @@ The direction, alongside the amount by which the particle moves, can be represen
Referring to the formula again:
-![](./img/riccardo-antonelli-schwarzschild-black-hole-force-field-formula.png)
+[image ./img/riccardo-antonelli-schwarzschild-black-hole-force-field-formula.png]
-<code>F<sup>&rarr;</sup></code> returns a force vector (`F` for "force" and <code><sup>&rarr;</sup></code> for "vector"): any force acting on an object has a strength (magnitude) and a direction.
+`[F^[&rarr;]^]` returns a force vector (`[F]` for "force" and `[^[&rarr;]^]` for "vector"): any force acting on an object has a strength (magnitude) and a direction.
Imagine you are pushing a box: you are applying some force to it in a "forward" direction.
If you pull the box, you'll apply some force in a "backward" direction.
This force vector conveys how much and in what direction exactly the black hole is "pulling" on the corpuscle.
-Although the function takes in only one argument, `r`, that doesn't mean that `h` or <code>r<sup>\^</sup></code> aren't also arguments:
+Although the function takes in only one argument, `[r]`, that doesn't mean that `[h]` or `[r^[^]^]` aren't also arguments:
+
+:unordered
+- `[r]` is the distance from the center of the black hole (the singularity) to the =[current]= position of the corpuscle.
-- `r` is the distance from the center of the black hole (the singularity) to the **current** position of the corpuscle.
+- `[h]` is the magnitude of the [url https://en.wikipedia.org/wiki/Specific_angular_momentum "specific angular momentum"] of the light "particle".
-- `h` is the magnitude of the ["specific angular momentum"](https://en.wikipedia.org/wiki/Specific_angular_momentum) of the light "particle".
-
+ .p
"Normal" linear momentum specifies how much "force" at what speed it takes to stop (or change) the speed and direction of an object in linear motion (that's why it's in kg\*m/s).
Imagine a big heavy train on a perfectly straight rails going at a fast speed.
How do you forcefully stop it?
-
- You can put a *really* heavy barrier on the tracks, in front of the train.
+
+ .p
+ You can put a *[really]* heavy barrier on the tracks, in front of the train.
Since the train is moving at a really great speed, this barrier will have to be much much heavier (with much more mass) than the train itself.
-
+
+ 'footnote hitting-trains Of course, I'm assuming the trains are strong enough they won't break upon the collision.
+
+ .p
Alternatively, you can "launch" something against the train, meaning you can put a second train, moving in the opposite direction of the first train, so they hit head-on.
- Since the second train would also be moving, if it's travelling at the same speed and has the same mass as the first train, upon collision they would both stop[^hitting-trains].
+ Since the second train would also be moving, if it's travelling at the same speed and has the same mass as the first train, upon collision they would both stop[$hitting-trains].
If the second travels at twice the speed, then it can have half of the mass of the first to produce the same effect.
-
+
+ .p
The property with which we can "prove" why both a larger mass at no speed, and a smaller mass at a faster speed, can stop the train, is the momentum.
-
+
+ .p
Angular momentum specifies how much "force" at what speed it takes to stop (or change) the speed and direction of a rotating object.
Imagine the train scenario but on a circular track.
-
+
+ .p
The specific angular momentum is the angular momentum of an object, divided by it's mass.
It's magnitude kind of tells us which property is more prevalent in the momentum, the mass or the speed.
- For the same angular momentum, a long (big magnitude) *specific* angular momentum means our object is small and moves fast, while for a short (small magnitude) *specific* angular momentum out object is large and moves slowly.
-
- Another simplification we need to is **make our black hole stationary**!
- Then, rather than finding the angular momentum[^angular-momentum] and dividing by the mass[^light-has-no-mass], we'll use another formula:
+ For the same angular momentum, a long (big magnitude) *[specific]* angular momentum means our object is small and moves fast, while for a short (small magnitude) *[specific]* angular momentum out object is large and moves slowly.
+
+ 'footnote angular-momentum Angular momentum is actually [url https://en.wikipedia.org/wiki/Specific_angular_momentum#Definition defined using the cross product]
+ 'footnote light-has-no-mass As mentioned, light has no mass, so this version of the formula wouldn't work.
+
+ .p
+ Another simplification we need to is =[make our black hole stationary]=!
+ Then, rather than finding the angular momentum[$angular-momentum] and dividing by the mass[$light-has-no-mass], we'll use another formula:
+
+ .p [image ./img/specific-angular-momentum-wikipedia.png]
+
+ .p
+ where =[in this specific formula only]= `[r]` is the vector from the singularity to the corpuscle and `[v]` is light's velocity.
- ![](./img/specific-angular-momentum-wikipedia.png)
-
- where **in this specific formula only** `r` is the vector from the singularity to the corpuscle and `v` is light's velocity.
-
+ .p
The cross product returns a vector, so we'll need to take the magnitude of the result and plug that into the formula.
- It's also important that **we calculate it only once, in the beginning**.
+ It's also important that =[we calculate it only once, in the beginning]=.
So, we shouldn't be calculating the magnitude of the specific angular momentum every time the light "particle" is moved, rather we calculate it once, after it gets close enough to be affected by the black hole.
-[^hitting-trains]: Of course, I'm assuming the trains are strong enough they won't break upon the collision.
-[^angular-momentum]: Angular momentum is actually [defined using the cross product](https://en.wikipedia.org/wiki/Specific_angular_momentum#Definition)
-[^light-has-no-mass]: As mentioned, light has no mass, so this version of the formula wouldn't work.
+ .p
You might think that makes no sense, since we cannot divide by zero, so the specific angular momentum shouldn't exist, but then with the cross product we find a value for it.
You would be correct: Antonelli does some funky approximations, combining Newtonian physics with General theory of relativity, to make the formula that simple.
-
-- <code>r<sup>&#94;</sup></code> is the normalized ([unit](https://en.wikipedia.org/wiki/Unit_vector), hence the `^` on top) vector from the center of the black hole to the light particle:
-
- ![](./img/normalize-vector-wikipedia.png)
+
+- `[r^[&#94;]^]` is the normalized ([url https://en.wikipedia.org/wiki/Unit_vector unit], hence the `[^]` on top) vector from the center of the black hole to the light particle:
+
+ .p [image ./img/normalize-vector-wikipedia.png]
+
Finally, putting all needed variables together in one proper function, we get:
-![Refer to "Antonelli’s formula - explained" in the Appendix](./img/variables-expanded.png)
+[image ./img/variables-expanded.png Refer to "Antonelli’s formula - explained" in the Appendix]
-As you may notice, this can be simplified, if we substitute <code>r<sup>&#94;</sup></code>:
+As you may notice, this can be simplified, if we substitute `[r^[&#94;]^]`:
-![Refer to "Antonelli’s formula - simplified" in the Appendix](./img/antonelli-formula-expanded.png)
+[image ./img/antonelli-formula-expanded.png Refer to "Antonelli’s formula - simplified" in the Appendix]
In effect, we pass the distance from the black hole to the corpuscle and the function returns how light's velocity changes.
@@ -286,44 +312,45 @@ For that we'll need to get even more familiar with black holes.
### Properties of a black hole
+'footnote no-hair-theorem The [url https://en.wikipedia.org/wiki/No-hair_theorem no-hair theorem] states that stationary black holes are characterized by only their mass, angular momentum and electric charge. By definition of a Schwarzschild black hole, the last two are null.
+
To summarize, we're working with a stationary Schwarzschild black hole.
-Meaning our black hole has only one property: mass[^no-hair-theorem].
+Meaning our black hole has only one property: mass[$no-hair-theorem].
Everything else can be derived from it.
-[^no-hair-theorem]: The [no-hair theorem](https://en.wikipedia.org/wiki/No-hair_theorem) states that stationary black holes are characterized by only their mass, angular momentum and electric charge. By definition of a Schwarzschild black hole, the last two are null.
-
-There are three radii, which will be the backbone of our black hole: the event horizon, the photon sphere and [ISCO](https://en.wikipedia.org/wiki/Innermost_stable_circular_orbit).
+There are three radii, which will be the backbone of our black hole: the event horizon, the photon sphere and [url https://en.wikipedia.org/wiki/Innermost_stable_circular_orbit ISCO].
The event horizon, also called the Schwarzschild radius, is the distance from the singularity, which once passed, nothing can return and escape.
The formula for it is:
-![r_s = (2GM)/(c^2)](./img/Schwarzschild-radius-wikipedia.png)
+[image ./img/Schwarzschild-radius-wikipedia.png r_s = (2GM)/(c^2)]
-where `G` is the [gravitational constant](https://en.wikipedia.org/wiki/Gravitational_constant) and `M` is the mass of the black hole (in kg).
+where `[G]` is the [url https://en.wikipedia.org/wiki/Gravitational_constant gravitational constant] and `[M]` is the mass of the black hole (in kg).
The photon sphere is the distance from the singularity, in which photons start orbiting the black hole (and can either escape or pass the event horizon).
Formula:
-![r = r_s * 3/2](./img/photon-sphere-wikipedia.png)
+[image ./img/photon-sphere-wikipedia.png r = r_s * 3/2]
+
+where `[G]` and `[M]` are the same as before, `[c]` is the speed of light in vacuum and `[r^[s]^]` is the aforementioned Schwarzschild radius.
-where `G` and `M` are the same as before, `c` is the speed of light in vacuum and <code>r<sub>s</sub></code> is the aforementioned Schwarzschild radius.
+'footnote isco It's not really true that gravity stopps affecting spacetime after the ISCO, even though things can orbit Earth that doesn't mean that Earth doesn't bend spacetime. However, for the purposes of a simple shader, this assumption produces perfectly useable results.
Finally, the innermost stable circular orbit (ISCO), formally it's the distance, before which you can orbit the black hole, but once passed, you'll get sucked in and either get shot out or be forever lost past the event horizon.
-For our purposes, it's fine to approximate it as the maximum radius after which space-time isn't bent[^isco] and objects aren't affected.
+For our purposes, it's fine to approximate it as the maximum radius after which space-time isn't bent[$isco] and objects aren't affected.
Formula:
-[^isco]: It's not really true that gravity stopps affecting spacetime after the ISCO, even though things can orbit Earth that doesn't mean that Earth doesn't bend spacetime. However, for the purposes of a simple shader, this assumption produces perfectly useable results.
-
-![](./img/isco-wikipedia.png)
+[image ./img/isco-wikipedia.png]
Putting them all together, we should expect light to travel like this:
-![](https://upload.wikimedia.org/wikipedia/commons/2/27/Black_Hole_Shadow.gif)
-*Animation by Hugo Spinelli on [Wikipedia](https://commons.wikimedia.org/w/index.php?curid=138168679)*
+[image https://upload.wikimedia.org/wikipedia/commons/2/27/Black_Hole_Shadow.gif]
+*[Animation by Hugo Spinelli on [url https://commons.wikimedia.org/w/index.php?curid=138168679 Wikipedia]]*
## Light-bending algorithm
Finally, now we have everything we need to devise an algorithm for our simulation.
+.bulleted
- For light we'll store two vectors: one for it's position and one for it's velocity.
- For the black hole we'll store a vector and a quantity: the position of the black hole's center and it's mass.
For convenience, we could just store the Schwarzschild radius, since all of our radii can be expressed only by it.
@@ -339,13 +366,13 @@ The simplest way to "track" this is just to limit how many times we can move the
An algorithm doing this would look a bit like this (in pseudocode, inspired by Python):
-![Refer to "Algorithm" section of the Appendix](./img/algorithm.png)
+[image ./img/algorithm.png Refer to "Algorithm" section of the Appendix]
-as a reminder, here is the definition of <code>F<sup>&rarr;</sup></code>:
+as a reminder, here is the definition of `[F^[&rarr;]^]`:
-![](./img/antonelli-formula-expanded.png)
+[image ./img/antonelli-formula-expanded.png]
-<br>
+\n
That's it!
We have all of our theoretical background, formulae and algorithm to start work on our actual program.
@@ -356,7 +383,7 @@ To Be Continued!
### LaTeX source for equations
-The images for my custom LaTeX equations were created on [latexeditor.lagrida.com](https://latexeditor.lagrida.com/), by using Firefox's built-in ability to screenshot HTML nodes, in particular the [MathJax](https://www.mathjax.org/) node with the equation.
+The images for my custom LaTeX equations were created on [url https://latexeditor.lagrida.com/ latexeditor.lagrida.com], by using Firefox's built-in ability to screenshot HTML nodes, in particular the [url https://www.mathjax.org/ MathJax] node with the equation.
#### Antonelli's formula - explained
@@ -369,7 +396,6 @@ The images for my custom LaTeX equations were created on [latexeditor.lagrida.co
& r_l = \text{vector from black hole center to light "particle"}\\
& v_l = \text{velocity of light "particle"}
\end{align*}
-```
#### Antonelli's formula - simplified
@@ -381,7 +407,6 @@ The images for my custom LaTeX equations were created on [latexeditor.lagrida.co
& r_l = \text{vector from black hole center to light "particle"}\\
& v_l = \text{velocity of light "particle"}
\end{align*}
-```
#### Algorithm
@@ -411,4 +436,3 @@ The images for my custom LaTeX equations were created on [latexeditor.lagrida.co
& \qquad v_l = v_l + \overrightarrow{F}(r_l,h) \quad \text{(update light velocity)} \\
& \quad \text{return "Light stuck in photon sphere, never escapes"}
\end{align*}
-```
diff --git a/src/blog/thinkpad-x270-my-favorite-machine/index.md b/src/blog/thinkpad-x270-my-favorite-machine/index.du
index 6e958cc..978d8b4 100644
--- a/src/blog/thinkpad-x270-my-favorite-machine/index.md
+++ b/src/blog/thinkpad-x270-my-favorite-machine/index.du
@@ -1,32 +1,41 @@
# ThinkPad X270 - my favorite machine
-## Contents
+'define expected-reading 17 min
+'define created 30 August 2023
+'define edited 30 August 2023
+[$pagenav]
+
+:contents
+:numbered
+1. [url #context Context]
+2. [url #what-i-think What I Think]
+ .numbered
+ 1. [url #display Display]
+ 2. [url #cpu-and-ram CPU and RAM]
+ 3. [url #hardware-support-and-chassis Hardware support and chassis]
+ 4. [url #ports Ports]
+ 5. [url #batteries Batteries]
+ 6. [url #keyboard-and-power-button Keyboard and power button]
+ 7. [url #trackpoint-and-mouse-pad Trackpoint and mouse pad]
+ 8. [url #repairability Repairability]
+ 9. [url #cooling Cooling]
+ 10. [url #pricing Pricing]
+
+3. [url #conclusion Conclusion]
+
-1. [Context](#context)
-2. [What I Think](#what-i-think)
- 1. [Display](#display)
- 2. [CPU and RAM](#cpu-and-ram)
- 3. [Hardware support and chassis](#hardware-support-and-chassis)
- 4. [Ports](#ports)
- 5. [Batteries](#batteries)
- 6. [Keyboard and power button](#keyboard-and-power-button)
- 7. [Trackpoint and mouse pad](#trackpoint-and-mouse-pad)
- 8. [Repairability](#repairability)
- 9. [Cooling](#cooling)
- 10. [Pricing](#pricing)
-3. [Conclusion](#conclusion)
ThinkPad laptops are generally well liked, a lot of people I know use them and every one that I've touched has been a pleasure to work with.
-Suffice to say, I've wanted to get one for quite a while now, so back in the middle of May I bit the bullet and spontaneously bought a second hand [Thinkpad X270](https://www.thinkwiki.org/wiki/X270_Detailed_Hardware_Information).
+Suffice to say, I've wanted to get one for quite a while now, so back in the middle of May I bit the bullet and spontaneously bought a second hand [url https://www.thinkwiki.org/wiki/X270_Detailed_Hardware_Information Thinkpad X270].
I've used it for the past 3 months, and in all honesty, it's not without it's drawback, but the X270 has easily become my favorite computer.
-*Note: this whole review was written on the aforementioned Thinkpad X270, without external devices (like keyboard or monitor) attached.*
+*[Note: this whole review was written on the aforementioned Thinkpad X270, without external devices (like keyboard or monitor) attached.]*
## Context
-My main computer is a pre built (without only major upgrades) desktop tower with an [i3-4160](https://www.intel.com/content/www/us/en/products/sku/77488/intel-core-i34160-processor-3m-cache-3-60-ghz/specifications.html), scoring [3510 on CPU mark](https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i3-4160+%40+3.60GHz&id=2317), paired with 16 gigs (for the past 9 months, otherwise I had 8 GB) of 1600 MHz memory, and a 1080p IPS monitor.
-I also own a laptop, the [Lenovo Yoga S730](https://www.lenovo.com/gb/en/p/laptops/yoga/yoga-slim-series/yoga-s730/88ygs701077) with an [i7-8565U](https://ark.intel.com/content/www/us/en/ark/products/149091/intel-core-i78565u-processor-8m-cache-up-to-4-60-ghz.html), scoring [6152](https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i7-8565U+%40+1.80GHz&id=3308), 16 GB of 2133 MHz RAM and 1080p IPS monitor.
+My main computer is a pre built (without only major upgrades) desktop tower with an [url https://www.intel.com/content/www/us/en/products/sku/77488/intel-core-i34160-processor-3m-cache-3-60-ghz/specifications.html i3-4160], scoring [url https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i3-4160+%40+3.60GHz&id=2317 3510 on CPU mark], paired with 16 gigs (for the past 9 months, otherwise I had 8 GB) of 1600 MHz memory, and a 1080p IPS monitor.
+I also own a laptop, the [url https://www.lenovo.com/gb/en/p/laptops/yoga/yoga-slim-series/yoga-s730/88ygs701077 Lenovo Yoga S730] with an [url https://ark.intel.com/content/www/us/en/ark/products/149091/intel-core-i78565u-processor-8m-cache-up-to-4-60-ghz.html i7-8565U], scoring [url https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i7-8565U+%40+1.80GHz&id=3308 6152], 16 GB of 2133 MHz RAM and 1080p IPS monitor.
Understanding my relationship with those machines is relevant to how I view the X270.
I got the desktop tower in 2015, and even at the time, it's specs were in the middle range.
@@ -35,20 +44,21 @@ Anyway, in all honesty, the only time when I wish for more power is in video gam
Summarising, 99% of the time it's hardware is more than sufficient.
The Yoga S730 was an "investment" into my future, since at the time I was going to programming lessons (which gave me a lot of the skills I have today) with my dad's laptop.
-With this new machine I could go to the lectures and write code freely on a **very** fast (considering I was doing C# programming in Visual Studio on Windows 10, speed was always needed) and physically light machine, without being slowed down by the cheap, 4 years old, 16 inch behemoth.
-From this point on, I was hooked on the 13 inch size, which as we all know is [the perfect size](https://youtu.be/Za_Ul08dtj8?t=1208) and [they should even make laptops that are any bigger](https://youtu.be/Q0h8wWlBxY0?t=1672).
+With this new machine I could go to the lectures and write code freely on a =[very]= fast (considering I was doing C# programming in Visual Studio on Windows 10, speed was always needed) and physically light machine, without being slowed down by the cheap, 4 years old, 16 inch behemoth.
+From this point on, I was hooked on the 13 inch size, which as we all know is [url https://youtu.be/Za_Ul08dtj8?t=1208 the perfect size] and [url https://youtu.be/Q0h8wWlBxY0?t=1672 they should even make laptops that are any bigger].
However, very quickly I found the ultrabook fashion of only including USB-C ports, very annoying to deal with, especially if you don't pay for an all-in-one dongle (which I didn't do for years).
-Additionally, the screen had *no* anti-gloss coating, so most of the time I was looking at my own reflection, rather than the actual screen contents.
+Additionally, the screen had *[no]* anti-gloss coating, so most of the time I was looking at my own reflection, rather than the actual screen contents.
Final thought, in the beginning battery life wasn't that much of a problem, but nowadays the battery barely holds for 3-4 hours, and I think a cell inside is failing.
## What I Think
-My dream laptop was a "fat" Yoga S730 - 13 inches diagonally (an absolute **MUST**) with USB type A ports, a non-glossy display and better battery life.
+My dream laptop was a "fat" Yoga S730 - 13 inches diagonally (an absolute =[MUST]=) with USB type A ports, a non-glossy display and better battery life.
Let's now consider the Thinkpad in question:
+.bulleted
- 13 inches in size diagonally,
-- *two* USB type A ports and more
+- *[two]* USB type A ports and more
- display with an anti-gloss coating
- both an external and internal battery (we'll talk about them later), allegedly being able to last 6-8 hours
@@ -56,17 +66,17 @@ Absolutely perfect... well, almost.
### Display
-By default, the laptop comes with a **horrible** 720p TFT display, with **horrid** color contrast, brightness and viewing angles.
-Surprisingly enough, online there were 1080p IPS drop-in replacements, and they weren't too expensive: the [one I got from amazon.de cost me 115 euro](https://www.amazon.de/dp/B07RZQ5LPW/ref=pe_27091401_487024491_TE_item) (including the 25 euro international shipping).
+By default, the laptop comes with a =[horrible]= 720p TFT display, with =[horrid]= color contrast, brightness and viewing angles.
+Surprisingly enough, online there were 1080p IPS drop-in replacements, and they weren't too expensive: the [url https://www.amazon.de/dp/B07RZQ5LPW/ref=pe_27091401_487024491_TE_item one I got from amazon.de cost me 115 euro] (including the 25 euro international shipping).
The laptop itself did cost me ~170 euro, so the screen itself was 2/3 of the laptop price, but at 285 euro total, the deal was still a steal, at least considering where I live at.
-[Replacing the display itself was dead easy](https://www.youtube.com/watch?v=hzI3U3up5xY): pop-open the bezel, disconnect the old, reconnect the new, put the bezel back on, boom!
+[url https://www.youtube.com/watch?v=hzI3U3up5xY Replacing the display itself was dead easy]: pop-open the bezel, disconnect the old, reconnect the new, put the bezel back on, boom!
The only negative is that, since it's 1080p, my battery life decreased by 30-60 minutes.
Oddly enough though, if I set the refresh rate at 58.86 (or something else that's lower than 60.00, but this is the lowest I was able to go) the display seemed to use less power and I got that battery life back.
Here are the exact Linux commands I used (make sure you don't have any external displays connected):
-```bash
+:code_bash
# find your display name, mine was eDP-1; I got this from StackExchange somewhere I think
displayname="$(xrandr | grep connected | grep -v disconnected | cut -f 1 -d ' ')"
# get the exact needed display parameters for 1920x1080 resolution at 58.90 hertz refresh rate
@@ -77,25 +87,25 @@ modename=$(echo $displayparams | cut -f 1 -d ' ')
xrandr --newmode $displayparams
xrandr --addmode $displayname $modename
xrandr --output $displayname --mode $modename
-```
+
From now on, my opinion will refer to the X270 with the upgraded display.
### CPU and RAM
-The processor is underwhelming to say the least, my machine came with the [Intel Core i5-6300U](https://www.intel.com/content/www/us/en/products/sku/88190/intel-core-i56300u-processor-3m-cache-up-to-3-00-ghz/specifications.html), which has two cores at a base frequency of 2.50 GHz.
-It's [CPU Mark is about 3240](https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i5-6300U+%40+2.40GHz&id=2609), but if you were following, it scores a little bit worse than the [CPU on my desktop](https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i3-4160+%40+3.60GHz&id=2317), so I'm used to it.
+The processor is underwhelming to say the least, my machine came with the [url https://www.intel.com/content/www/us/en/products/sku/88190/intel-core-i56300u-processor-3m-cache-up-to-3-00-ghz/specifications.html Intel Core i5-6300U], which has two cores at a base frequency of 2.50 GHz.
+It's [url https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i5-6300U+%40+2.40GHz&id=2609 CPU Mark is about 3240], but if you were following, it scores a little bit worse than the [url https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i3-4160+%40+3.60GHz&id=2317 CPU on my desktop], so I'm used to it.
But I can understand that being a deal breaker for a lot of people.
The RAM wasn't too bad actually, I got 16 GB of DDR4 memory at 2133 MHz.
My desktop runs 16 GB of DDR3 memory at 1600 MHz, so in practice, even though the CPU is slightly slower, the overall machine always performs noticeably better than my desktop.
I must mention, on some devices there seems to be an issue, where the RAM module would very slightly move in it's slot when the laptop is held in a certain way, which will cause the computer to freeze.
-[The solution is to put something beneath it, as a standoff](https://old.reddit.com/r/thinkpad/comments/jq53yt/freezing_x270x260x250_official_fix_a_bit_lmao/), but I haven't had to do this yet.
+[url https://old.reddit.com/r/thinkpad/comments/jq53yt/freezing_x270x260x250_official_fix_a_bit_lmao/ The solution is to put something beneath it, as a standoff], but I haven't had to do this yet.
### Hardware support and chassis
-ThinkPad laptops generally have [Linux drivers for just about anything](https://www.thinkwiki.org/wiki/Drivers), you can freely control the different lights on the laptop or the precise fan speed.
+ThinkPad laptops generally have [url https://www.thinkwiki.org/wiki/Drivers Linux drivers for just about anything], you can freely control the different lights on the laptop or the precise fan speed.
Since this was my first machine in the line, I found this out after getting it, which is a huge advantage to be sure.
Also, ThinkPad laptops are usually made with a thick high quality plastic and the X270 is no exception.
@@ -113,7 +123,7 @@ But this is in no way a deal-breaker, and the connector is much beefier than nor
### Batteries
-Something absolutely amazing is that the X270 comes with two, count them, **TWO** batteries - one internal and one (removable) external.
+Something absolutely amazing is that the X270 comes with two, count them, =[TWO]= batteries - one internal and one (removable) external.
The last time I saw a removable battery was on the old family laptop from 2011, and this one has an additional internal one.
Do I even need to explain why this is awesome?
@@ -126,7 +136,7 @@ The trade-off is that the 52 Wh battery is much thicker, so it's not flush with
### Keyboard and power button
-Speaking of the devil, unfortunately, the X270 doesn't have the fantastic old keyboards on older ThinkPad models (though, if you are determined, [you could probably put an old one in the laptop](https://www.youtube.com/watch?v=Fzmm87oVQ6c)).
+Speaking of the devil, unfortunately, the X270 doesn't have the fantastic old keyboards on older ThinkPad models (though, if you are determined, [url https://www.youtube.com/watch?v=Fzmm87oVQ6c you could probably put an old one in the laptop]).
However, comparing to other laptop keyboards, I would say this one isn't too bad, it's not anything amazing, but it better than a good amount of others.
Compared to the S730, it's has a much longer key travel and the keys generally feel a lot clicker.
@@ -136,7 +146,7 @@ The X270 is much more normal, though the square brackets and pipe keys are half-
The Fn key is to the left of the Ctrl key, but in the BIOS you can swap them around, so that's not a problem.
My only issue is with the spacebar, because the actual switch isn't in the center of the key, but to the left of it, and I mostly press the spacebar with my right hand, so when I don't absolutely slam it, the key press could just barely not register.
-The only reason I'm talking about the power button at all is that, baked in the firmware, to register a press you have to [hold it down for 1-3 seconds](https://bbs.archlinux.org/viewtopic.php?pid=1193137#p1193137), at least when shutting down.
+The only reason I'm talking about the power button at all is that, baked in the firmware, to register a press you have to [url https://bbs.archlinux.org/viewtopic.php?pid=1193137#p1193137 hold it down for 1-3 seconds], at least when shutting down.
This isn't a bug, it's a feature, and it has come quite in handy, I've had friends casually press the power button on my S730 and shut it off without me being able to react.
### Trackpoint and mouse pad
@@ -174,10 +184,10 @@ My only issue is that the fan curve prioritizes silence a little too much on low
It's by no means outrageous, the fan kicks in at a little bit above 45-50 degrees Celsius, which is fine, but when the CPU is close to or at those temperatures, the chassis starts getting a little warm.
During the summer my left hand stars sweating a little bit more, which can be quite uncomfortable.
-Of course, as already mentioned, we have drivers for everything, so I installed [thinkfan](https://github.com/vmatare/thinkfan).
+Of course, as already mentioned, we have drivers for everything, so I installed [url https://github.com/vmatare/thinkfan thinkfan].
With it, I configured the fan to spin up on those lower temperatures and left the automatic configuration intact when we start getting warmer:
-```
+:code
sensors:
- tpacpi: /proc/acpi/ibm/thermal
indices: [0]
@@ -190,26 +200,26 @@ levels:
- [1, 35, 38]
- [3, 38, 53]
- ["level auto", 53, 255]
-```
+
This may shorten the fan lifespan, since it will be running more, but for me it's worth it.
### Pricing
-As I already said, I got my X270 second hand from [subincho.com](https://subincho.com/index.php), with only a few cosmetic issues; it's practically brand new.
+As I already said, I got my X270 second hand from [url https://subincho.com/index.php subincho.com], with only a few cosmetic issues; it's practically brand new.
ThinkPads are quite often favorites for businesses, so now is the time when those 6 year old machines get thrown out on the second hand market.
I'll work with the final price of 340 euro, which includes the monitor upgrade and 52 Wh external battery, since that's when the machine goes from good to fantastic.
I live in Bulgaria, so depending on where you live, there might be better offers, but even with a doubled price, you won't find anything brand new that is as good.
-Let's look at the listings in [JAR computers](https://www.jarcomputers.com/), since I've found their pricing and availability to be quite normal for online shops (and the physical shops almost always offer fewer devices with a much higher price).
+Let's look at the listings in [url https://www.jarcomputers.com/ JAR computers], since I've found their pricing and availability to be quite normal for online shops (and the physical shops almost always offer fewer devices with a much higher price).
So, 340 * 2 = 640 euro, or roughly 1300 Bulgarian Lev.
-At the time of writing, [searching for a ~13 inch laptop at around that price range](https://www.jarcomputers.com/Laptopi_cat_2.html?ref=all&fprop[4413][48266]=48266&fprop[4413][48256]=48256&order=-1&&fprice[price-filter-other]=p_from-1100-p_to-1600) yields only two results: a [Microsoft Surface Laptop Go 2](https://www.jarcomputers.com/microsoft-surface-laptop-go-2-8qc-00024-prod-nbmicrosoft8qc00024.html) and [Microsoft Surface Laptop Go](https://www.jarcomputers.com/ms-surface-laptop-go-tnv-00009-prod-nbmicrosofttnv00009.html), both of which are on sale (with the second's original price being ~2300 lev, around ~1100 euro, three times the price).
+At the time of writing, [url https://www.jarcomputers.com/Laptopi_cat_2.html?ref=all&fprop[4413\][48266\]=48266&fprop[4413\][48256\]=48256&order=-1&&fprice[price-filter-other\]=p_from-1100-p_to-1600 searching for a ~13 inch laptop at around that price range] yields only two results: a [url https://www.jarcomputers.com/microsoft-surface-laptop-go-2-8qc-00024-prod-nbmicrosoft8qc00024.html Microsoft Surface Laptop Go 2] and [url https://www.jarcomputers.com/ms-surface-laptop-go-tnv-00009-prod-nbmicrosofttnv00009.html Microsoft Surface Laptop Go], both of which are on sale (with the second's original price being ~2300 lev, around ~1100 euro, three times the price).
Both have soldered on RAM with no slots, so it cannot be upgraded, both have 1536x1024 displays with no anti-glare, that are glued to the screen bezel, both miss the Ethernet and HDMI ports, and since they aren't (older) ThinkPads, you won't get the TrackPoint or mouse buttons or Linux driver support or removable battery.
-Of course, they have their own positives, the display is a touchscreen and they score [2.3](https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i5-1035G1+%40+1.00GHz&id=3558) and [3.0](https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i5-1135G7+%40+2.40GHz&id=3830) times higher on CPU mark respectively, but still, you get so much more with the ThinkPad for half the price.
+Of course, they have their own positives, the display is a touchscreen and they score [url https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i5-1035G1+%40+1.00GHz&id=3558 2.3] and [url https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i5-1135G7+%40+2.40GHz&id=3830 3.0] times higher on CPU mark respectively, but still, you get so much more with the ThinkPad for half the price.
Now, in all fairness, this is comparing a second hand laptop to a brand new one, for double the price you could get a lot more in a second hand machine.
-Looking at the same place from which I bought my X270, they currently have [a ThinkPad L13](https://subincho.com/laptopi?product_id=15309) for ~510 euro, which only misses out on the Ethernet port and external battery, but instead provides [double the CPU mark](https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i7-10510U+%40+1.80GHz&id=3549).
+Looking at the same place from which I bought my X270, they currently have [url https://subincho.com/laptopi?product_id=15309 a ThinkPad L13] for ~510 euro, which only misses out on the Ethernet port and external battery, but instead provides [url https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i7-10510U+%40+1.80GHz&id=3549 double the CPU mark].
And that's only one site, if you look around enough you could probably find even better deals, but the 340 euro is still a really good deal.
## Conclusion
diff --git a/src/blog/when-a-language-forces-simpler-thinking/index.md b/src/blog/when-a-language-forces-simpler-thinking/index.du
index baee84c..d725e3d 100644
--- a/src/blog/when-a-language-forces-simpler-thinking/index.md
+++ b/src/blog/when-a-language-forces-simpler-thinking/index.du
@@ -1,10 +1,15 @@
# When a language forces simpler thinking
-This year I decided to join the [2022 Advent of Code](https://adventofcode.com/2022) event.
-The exercise [on the 7th day](https://adventofcode.com/2022/day/7) involved storage of a folder structure: each folder would have a name, files, and other folders in itself.
+'define expected-reading 5 min
+'define created 13 December 2022
+'define edited 13 December 2022
+[$pagenav]
+
+This year I decided to join the [url https://adventofcode.com/2022 2022 Advent of Code] event.
+The exercise [url https://adventofcode.com/2022/day/7 on the 7th day] involved storage of a folder structure: each folder would have a name, files, and other folders in itself.
For the task itself, you don't actually need to store the files, just the sum of their (and of those in subfolders) size, so a folder can be represented as a name, a number and multiple other folders.
-My solutions are written purely in [Common Lisp](https://en.wikipedia.org/wiki/Common_Lisp#Syntax): a programming language where everything is represented as a list of values. A value might be another list or a non-list value, like a number.
+My solutions are written purely in [url https://en.wikipedia.org/wiki/Common_Lisp#Syntax Common Lisp]: a programming language where everything is represented as a list of values. A value might be another list or a non-list value, like a number.
So I thought I could represent each folder as a list, where the first item is it's name, second is file size sum and the rest are subfolders, something like this:
```
@@ -15,11 +20,11 @@ Name File size sum Subfolder "e" in "a"
^ ^
| |
Subfolder "a" in "/" Subfolder "d" in "/"
-```
-Now, after parsing a file, you'll need to update the file size sum in the **current** folder **and** in the **parent** folder.
+Now, after parsing a file, you'll need to update the file size sum in the =[current]= folder =[and]= in the =[parent]= folder.
To do such a thing, you would either need to
+.bulleted
- iterate from "/" to that folder, find/store all folders in between, and update them, or
- store some way to access the parent folder, and just travel upwards
@@ -43,16 +48,17 @@ Name | File size sum
Name | Name | Name |
| | |
At index 0 is parent "/" Parent is "a" Parent is "/"
-```
-Now this solution worked great! With this I was able to [solve](https://gitlab.com/Syndamia/advent-of-code/-/tree/main/2022/Day07) both tasks easily.[^day7]
+'footnote day7 A potential improvement would be to use CLOS to store each folder as it's own object, but this worked fine and I really wanted to spare reading on CLOS at that time.
+
+Now this solution worked great! With this I was able to [url https://gitlab.com/Syndamia/advent-of-code/-/tree/main/2022/Day07 solve] both tasks easily.[$day7]
#### Appendix
In the exercise, you have commands for navigating between folders.
-Going up a folder is trivial, but folders can have duplicate names if they're inside different parent folders, so going to a sub folder requires to search by it's name *and* parent index.
+Going up a folder is trivial, but folders can have duplicate names if they're inside different parent folders, so going to a sub folder requires to search by it's name *[and]* parent index.
-Surprisingly enough, in my solution [(lines 15-17)](https://gitlab.com/Syndamia/advent-of-code/-/tree/main/2022/Day07/part-one.cl#L15-17), I just search from the end to the beginning of all parsed folders for a name.
+Surprisingly enough, in my solution [url https://gitlab.com/Syndamia/advent-of-code/-/tree/main/2022/Day07/part-one.cl#L15-17 (lines 15-17)], I just search from the end to the beginning of all parsed folders for a name.
This works fine for this exact task and exact inputs, however in general this isn't correct. In a structure like this:
```
@@ -63,7 +69,6 @@ This works fine for this exact task and exact inputs, however in general this is
- b (dir)
- a (dir)
- file2.txt (file, size=2)
-```
with an input like this:
@@ -86,13 +91,9 @@ $ ls
$ cd ..
$ cd ..
$ cd a
-```
-
-The last `$ cd a` actually puts you into `/b/a/`, not `/a/`.
-The main thing that saves us (me) is that you can only change directory and list structure (in current directory), so you would only ever be visiting a folder once.
-If a folder's contents were `ls`'d more than once, or they could change (for example having an `mkfile`[^mkfile] command), a proper search would be required.
+'footnote mkfile `[mkfile]` is like `[touch]`, but you could specify a size and the file will be filled with that many zeroes. It seems to exist solely in [url https://docs.oracle.com/cd/E26502_01/html/E29031/mkfile-1m.html Solaris] (as a system administration command) and [url https://ss64.com/osx/mkfile.html MacOS]. I mentioned it and not `[touch]`, since the latter only creates empty files, which wouldn't contribute to the total file size sum.
-[^day7]: A potential improvement would be to use CLOS to store each folder as it's own object, but this worked fine and I really wanted to spare reading on CLOS at that time.
-
-[^mkfile]: `mkfile` is like `touch`, but you could specify a size and the file will be filled with that many zeroes. It seems to exist solely in [Solaris](https://docs.oracle.com/cd/E26502_01/html/E29031/mkfile-1m.html) (as a system administration command) and [MacOS](https://ss64.com/osx/mkfile.html). I mentioned it and not `touch`, since the latter only creates empty files, which wouldn't contribute to the total file size sum.
+The last `[\$ cd a]` actually puts you into `[/b/a/]`, not `[/a/]`.
+The main thing that saves us (me) is that you can only change directory and list structure (in current directory), so you would only ever be visiting a folder once.
+If a folder's contents were `[ls]`'d more than once, or they could change (for example having an `[mkfile]` [$mkfile] command), a proper search would be required.