00:00:07.520
Thank you, okay, it's going to be weird because I have two devices in my hands, so I need to get used to that. I might switch the microphone and the remote control.
00:00:11.080
Hello, everybody. I still find Polish a little bit funny. It always sounds cute and humorous to us, and you greet each other with honor. My name is Dávid. I come from the Czech Republic, from the city of Brno. I guess you know where it is; it's just a four-hour drive from here.
00:00:21.000
I work for a company called Red Hat, which you've probably heard about. I work on a small Ruby project there, and I also do some research. Since college, I decided that I should do something interesting alongside my work. So, I research how machines will trust each other in the future. We can talk about that later at the party, maybe.
00:00:34.920
Now, who studied computer science here? Hands up, please. Oh no, it's not going to be new for you, then. My excuse is that Andre made me do it. If you know the big guy—small on the picture but the big guy of the conference—yes, that's him. So, let's begin with the first chapter: how computers work.
00:01:01.960
Okay, so how do computers work? This will be a crash course for Ruby programmers. You have some instructions. I need to look closer to see them because some demonic force might reorganize my slides. So, you have an instruction class, and you have a pointer. Every time you execute an instruction, you increase the pointer.
00:01:35.520
Then you have instructions that are subclasses of this instruction class, such as 'jump', where you set the pointer to an actual number. You might also have classes like 'add', where you add two operands and yield back to the pointer by calling 'super'. This increases the pointer, and then you might have 'subtract' and other operations as well. This is how a Ruby programmer would envision what assembly looks like or how computer instructions are structured. The computer is essentially just an iteration on those instructions.
00:02:41.239
I guess now everybody knows how computers work, right? So let’s move on to chapter two.
00:02:49.120
Let's talk about languages—not the spoken ones, but formal languages. I apologize for bringing back your nightmares from computer science classes. You're going to relive that experience because Andre made me do it again.
00:03:06.440
Languages consist of alphabets that use some kind of letters, just like in a normal language. In this case, you have digits from 0 to 9, plus and minus signs. The words form subsets that are simply iterations of these letters. For example, you might have sentences like '1 plus 1', '2 plus 2', '3 plus 3', '4 plus 4'. Those are our language, and they don't contain anything beyond this domain.
00:03:24.680
Then, there are other formal parts called grammars, where you have a symbol and non-terminal symbols. You iterate through this, which can get complicated, but in simplified terms, it means you have a symbol and a non-terminal symbol that iterate together. To make things easier to understand, let's say you have an alphabet with three symbols: two non-terminals 'D' and 'O'. One rule of the grammar could be that 'O' translates to a plus sign.
00:04:15.799
For instance, 'O' can also translate to a minus sign, and 'D' can translate to either '1' or '2'. This generates a language that can express combinations such as '1 + 1', '1 + 2', '1 - 1', '1 - 2', along with various others. This illustrates how our language operates using these rules.
00:05:05.279
As we categorize languages, the simplest are called regular languages. They usually follow regular grammars, where the grammar is straightforward, placing a non-terminal symbol on the left and a combination of symbols on the right. Such languages can be parsed by finite state machines.
00:05:36.280
You can also parse these languages using regular expressions. In programming, you might already be familiar with what a regular expression is. If anyone here doesn’t know, please let me know. Is everyone familiar? Great! Regular languages can be defined for which you can construct a finite state machine.
00:06:47.720
This machine captures languages that start with a specific character and end with another. We can relate this to regular expressions as well. Everything else lies outside this domain, and thus is not part of the language. It is also true that all finite languages are regular because you can construct automata to parse them through all possible combinations.
00:08:57.520
More complicated languages follow a context-free grammar model where only one symbol is present on the left side, while the right side contains a combination of terminal and non-terminal symbols. In this context, it is crucial that there's just one non-terminal symbol on the left. Furthermore, two types of languages exist: deterministic and non-deterministic.
00:10:29.240
An example would be when parsing palindrome structures, such as identifying words where reversing the string produces a match. In such cases, a non-deterministic machine could distinguish the palindrome structure sufficiently but would be unable to parse a more complicated case using simple techniques.
00:11:45.160
As with earlier discussions on expression power, these properties don’t necessarily yield simple outcomes. It’s worth mentioning that determinism isn’t crucial to simpler regular languages, but it becomes essential in parsing context-free languages effectively.
00:12:59.760
Context-sensitive languages operate with grammars having multiple symbols present on the left side. This allows for an even broader range of constructs compared to context-free grammars, with recursive structures enabling complex behavior.
00:14:35.440
From here, we enter the theorems around Turing machines. Turing machines are represented with an infinite tape that serves as memory. They are mathematical devices capable of simulating computation far beyond that of a traditional computer. They can utilize finite state control and process data through reading and writing capabilities when moving left or right.
00:15:53.440
While Turing machines are theoretically powerful, they present limitations when interpreted through our existing mathematical framework. Turing machines themselves are employed primarily for mathematical proofs rather than practical computation.
00:17:25.360
Now let’s delve into algorithmic complexity, which can pertain to both space and timing. Space complexity refers to how much memory is consumed on the tape, while time complexity indicates how many movements occur on the tape.
00:18:00.799
When transitioning into understanding how compilers and interpreters function, consider the numerous phases processing your coding involves, starting with lexical analysis. Following with syntactical analysis, it ultimately leads to generating intermediate code, optimizations, and execution.
00:19:17.040
In summary, the interpreter reads through the instructions and executes them, while compilers write code to a file through assembly, enabling their translation into machine-readable formats.
00:19:58.040
I haven't mentioned virtual machines yet, which function by executing intermediate representations across various platforms. They encapsulate the running of code distinct from direct hardware execution.
00:21:16.520
The capabilities of the Ruby Virtual Machine (YARV) exemplify this, optimizing and executing Ruby code efficiently. However, remember that manually performing these tasks is often impractical, as tools are designed to automate lexer and parser generation.
00:23:20.060
Finally, understanding the theoretical foundations discussed overall prepares you to make sense of how modern programming paradigms and languages operate. Thank you for having me! If anyone has any questions or reflections on their experiences, feel free to share!