divip's homepage

xooooooooooooxdkkkO0KXK00K0OdxxxxxxxxxddddddddkkkkO ooolllllloxd0KXXNNXNNNNNXXXXK0Odxxxxxxxxxddddddkkkk oolllllod0KXXNNNXNNXXXXXXXXNNXXXKOkxxxxxxxxdddddkkk ollllllkXNNNXXXXKKKXXK000K0KXXXNNNXKOkxxxxxxdddddkk lllloxkXNNNNXXXXX0OO0KKK0O000KKKKXNNXX0dxxxxxddddkk llloOKXNNXXNNNNXXK000KKK0O0KOO000kOKXXKkxxxxxxddddk lcldKNNNKKKXXXXXK0OO00OOOOK0O0K0kdxk0XX0xoxxxxxdddd cco0XXXKXXKXXKXK0kxk0KOOOOOkkkdxollxdkXKkooxxxxxddd cokKKKKXK0000OO0Koldxoloc:;;;;;;;::clokXOooooxxxxdd coOKXXXKKKK000KOd:,'..... ....''',;:cco00oooooxxxdd coOXNXXXXXXXKK0x:,''.'.......''''',;:ccdOoooooxxxxd llxKXXXNXXXXK0Oo:,''..........''''',;:clkoxxxxxxxxd lllOXXXXXXKKK0Odl;,'..... ........',,;:ooxxxxxxxxd lllxKXXXKXKK000dl;,'.. .....''',;;::loxxxxxxddd llllOOolOKKKKKOl,,''......'',,,;;;codk000dxxxxxxddd lllcl:ccck0KXKx;''''';loxdOOkolc:oO0KNXKOdxxxxxxddd llcc:...;dkOK0o,''.,lxkdO00Odl;'.:Okdkkdxxxxxxxxddd llcc:...,:::d0l,'...,,;;:cc;'....'lcclllcloxxxxdddd lcccc,......cx:;,......''.........;:,,,;;cxxxxxdddd lcclcc'....':xo:;,'.. ...''......';:;;;:lxxxxxdddd lllllcc:'...:dxcc:;'...',:;,,..'..':llcccxdxxxxdddd lllllllooc:cokkool::;,;clc;,cddkkdd00dooxkkddxxdddd llllllooxxdkdkOddxolc:ldxoolcldk0000OOOkOOkkkdddddd llllooxxxxxdxdOOOkddoloxdxllcc:coodkk0000kkkkkkdddk lllloxxxxxddxldO0OOOkxlxo:,,;;:clooodOKKOkkkkkkkkkk llloxxdddk00OlldO000Oddddoc,;codkkdkOXX0OOOkkkkOOkk ooxxddddkO0X0lclxO0K0OOOOdoc::::oxxkKXXXXXK000OOOOO xdxxxdddddk0Ol:clxdO0KKK0kdxxoloddk0XNXXXXX00000OO0 dddddddxdddkdc::clodkkO0KKK0Okk00KKKKNXXXXK0000OOO0 dddxdddxdkdkdc:;:cloxdkkOO0KKXXXXKOkOXXXXXK0000OOOO dddddddddkdkdc::::clloxddkOO0KKK0OkkOXXXXXK000OOOOO ddddxdkddkdkOo:::::cccccloxddkkOkkkkKNXXKK00OOOOOO0 dddddxdOkdkdOOxc::ccllcccloxxdkkddkKXXXK00000OOOOOO kkdkkddkkdkOO00dlcclloooxxxdkkOkdk0XXKK000000OOOO00 kkdkkkddkddkOO00OxllloxxddkkkkkO0XXXKKK000000OOO000 kkkdkkddkkxkO0O0K0koooxxddkkkO0XXXXKKKK0000O00OO00K

CURRENT PROJECT - Programming as common knowledge PREVIOUS PROJECTS (selection) - At Digital Asset I was working on a distributed ledger for the Australian Securities Exchange in daml. - At Graphisoft I was working on the new versions of ArchiCAD, the company’s flagship product in C and C++. - At Prezi I was working on the co-editing infrastructure of Prezi documents in Haskell. - At Standard Chartered I was working on the front-end of an in-house tool for traders/quantitative analysts in Mu (a strict Haskell dialect). - At ATOMKI I used Haskell for scientific calculations for finding new results in Quantum Informatics. Both outgoing papers (1, 2) appeared in Phisical Review A. - At ELTE I was teaching Assembly, Functional Programming and related courses for several years. I made lots of interactive learning materials for students (mainly in Hungarian). - I helped to develop several parts of the Agda compiler (interactions frontend, JavaScript backend, generalization of declared variables). - I helped to develop the LambdaCube 3D compiler. - I was experimenting with Functional Reactive Programming several times: state-based FRP, interactive algorithms. - How to model mutable references in case of referential transparency? I tried to answer this question in my PhD thesis. You can read the summary in English (the thesis is in Hungarian, the related papers are in English). CONTACT ADDRESS let n = "divip" in n ++ "@" ++ n ++ ".hu" /\ /\ /\ /\ /\ /\ / \ /\ /\ / \ /\ /\ / \ /\ /\ / \ /\ /\ / \ /\ / \/ \/ \ / \/ \/ \ / \/ \/ \ / \/ \/ \ / \/ \/ \ / \/ \/ \/ \/ \ PROGRAMMING AS COMMON KNOWLEDGE =============================== I develop a programmable operating system with beginner-friendly building blocks. I develop a game to teach programming of the operating system and to get acquainted with programming in general. SOFTWARE IS THE BOTTLENECK Computers are inevitable, but they are not as useful as they could be. The usability of computers is limited by the hardware and by the software running on the hardware. There are less and less hardware limitations. The most notable hardware improvements recently were the addition of wireless network interfaces, better screens, camera, more computing power and memory, faster storage, shrinking size and less power consumption. The real limitation is the software which is running on the hardware. SHORTCOMINGS OF CURRENT SOFTWARE Users have little feedback about what is happening when they use the computer. For example, most users don’t know why their computer is slow when they feel so. Users who are brave enough to look into their computers find too many details which is above the complexity level which they can handle. Even if users know what the software does, they cannot restrict or alter its behaviour. Profit-oriented software companies are vital in making software for healthcare, transportation, scientific computations, administration etc. On the other hand, profit-oriented companies are counter-interested in making transparent software for users' devices. Users can lift software limitations themselves if they have programming literacy. RESTRUCTURING COMPUTATION Current software systems are so complex that it’s hard to change them even for professional programmers. How users could lift software limitations themselves? I believe that software complexity can be greatly reduced by MINIMALISM and USING THE RIGHT STRUCTURES. For example, multiplication is much easier with decimal numbers instead of Roman numerals. Asking the right questions helps to find the right structures for programming. I believe the right questions are the following: - What is an algorithm? - What is an interactive algorithm? - What is an operating system? - How can these be built up from smaller, independent pieces? I take the challenge to find practical answers to these questions such that everyone could be a programmer. TEACHING METHODOLOGY I want users gradually get acquainted with programming along the following dimensions: AUTOMATION: No automation (no programming) is the default from which one can make steps towards full automation. OPTIMIZATION: Non-optimal is the default. More optimal solutions comes with more effort. DEPTH: Be able to go down to the grounds within the same language. With predefined building blocks beginners can experience success and get into flow. Building blocks can be replaced by smaller ones as users level-up in programming knowledge. VISUALIZATION helps to make abstract concepts less mysterious. EXERCISES with the right level of difficulty is the key for teaching. I develop a mobile game for teaching programming for children. BLOG POSTS / RESULTS - What is an algorithm? - Reduce code complexity by restructuring If you are interested about the project history, read the monthly summary. You may read the questions and answers page too. /\ /\ /\ /\ /\ / \ /\ /\ /\/\ /\ /\ /\/\ /\ /\ / \ /\ /\ /\ \/ \/\/ \/ \/ \/\/ \/ \/ \ / \/ \/ \/\/ \/ \/ \/\/ \/ \/ WHAT IS AN ALGORITHM? ===================== The algorithm is the most essential concept in computer science. There are two typical definitions of it: A. An algorithm is A FINITE SEQUENCE OF INSTRUCTIONS. This is the mainstream definition. Making this definition formal, we arrive to the Turing-machine (an abstract computer) which is the theoretical base of the so-called imperative programming languages. B. An algorithm is A COMPUTABLE FUNCTION. Making this definition formal, we arrive to the Lambda-calculus (the calculus of substitutions) which is the theoretical base of the so-called functional programming languages. I chose B because its formalisation is less ad-hoc. The Turing-machine has separate memory and control logic. The Lambda-calculus is independent of computer architectures; in fact it was invented before electrical computers. There are alternatives to Lambda-calculus in formalizing computable functions. One alternative is Combinatory logic. Combinatory logic builds up functions with elementary building blocks called COMBINATORS. I chose Combinatory logic because by choosing specific combinators one can tailor the system for specific tasks like creating interactive algorithms. This is more complicated in Lambda-calculus. For a concrete set of elementary combinators I chose Categorical combinators because I found it the most intuitive and pragmatic set of combinators. So, in this blog post AN ALGORITHM IS A STRUCTURE BUILT UP WITH COMBINATORS. Let’s see what does it mean. INTRODUCTION TO CATEGORICAL COMBINATORS == Predefined combinators == Predefined combinators are be built-up with elementary combinators but for didactic reasons their definition is not shown. First we introduce the rotateRight combinator, which rotates a diagram clockwise by 90°. (The definition of diagrams is not important at this point. They will be used only in examples.) Examples of applying rotateRight on concrete diagrams: 🀲 ↦ 🁤 🁤 ↦ 🀸 The algorithm which is built-up with only one rotateRight combinator is visualised as follows: ╔═════════════╗ ║ rotateRight ║ ╚═════════════╝ == Vertical composition == Vertical composition – or just composition – is an elementary combinator with two holes in it: ╔═══════════════╗ ║╔═════════════╗║ ║║ ⟨hole₁⟩ ║║ ║╚═════════════╝║ ║╔═════════════╗║ ║║ ⟨hole₂⟩ ║║ ║╚═════════════╝║ ║ v-composition ║ ╚═══════════════╝ Simplified visualisation: ╔═══════════╗ ║ ⟨hole₁⟩ ║ ╠═══════════╣ ║ ⟨hole₂⟩ ║ ╚═══════════╝ The holes can be filled in with algorithms. Vertical composition connects the two algorithms by feeding the output of the algorithm in hole₁ into the input of the algorithm in hole₂. (Type systems can ensure that one can only fill in algorithms for which this output-to-input feeding is possible.) For example, composing rotateRight with itself reflects a diagram through its origin: ╔═════════════╗ ║ rotateRight ║ ╠═════════════╣ ║ rotateRight ║ ╚═════════════╝ 🀲 ↦ 🀸 Function composition is ASSOCIATIVE which means that the order of composition does not matter: ╔═══════╗ ╔═══════╗ ╔═════╗ ║╔═════╗║ ║ f ║ ║ f ║ ║║ f ║║ ╠═══════╣ ╠═════╣ ║╠═════╣║ ║╔═════╗║ ║ g ║ = ║║ g ║║ = ║║ g ║║ ╠═════╣ ║╚═════╝║ ║╠═════╣║ ║ h ║ ╠═══════╣ ║║ h ║║ ╚═════╝ ║ h ║ ║╚═════╝║ ╚═══════╝ ╚═══════╝ For example: ╔═════════════╗ ║ rotateRight ║ ╔═══════════════╗ ╔═══════════════╗ ╠═════════════╣ ║ reflectOrigin ║ ║ rotateRight ║ ║ rotateRight ║ = ╠═══════════════╣ = ╠═══════════════╣ ╠═════════════╣ ║ rotateRight ║ ║ reflectOrigin ║ ║ rotateRight ║ ╚═══════════════╝ ╚═══════════════╝ ╚═════════════╝ 🀲 ↦ 🁪 Another example for composition is the Fahrenheit-to-Celsius conversion algorithm: ╔════╗ ║-32 ║ ╠════╣ ║ /5 ║ ╠════╣ ║ *9 ║ ╚════╝ ----- --- ---------- 0 ↦ -17.7777 100 ↦ 37.7777 ----- --- ---------- Here (-32) is a predefined combinator which subtracts 32 from any number, (/5) is a predefined combinator which divides any number by 5, and (*9) is a predefined combinator which multiplies any number by 9. == Bidirectional algorithms == The algorithms shown so far are BIDIRECTIONAL which means that one can provide the output to get the input. For example, the Fahrenheit-to-Celsius conversion algorithm can be used to convert Celsius values to Fahrenheit values too. - The (-32) predefined combinator adds 32 to any number if it is applied in the reverse direction. - Composition of f and g applied in the reverse direction feeds inputs of g as outputs of f. == Identity combinator == The elementary combinator id gives back its input unchanged. ╔════╗ ║ id ║ ╚════╝ The identity combinator can be eliminated from composition: ╔════╗ ╔════╗ ║ id ║ ║ f ║ ╔════╗ ╠════╣ = ╠════╣ = ║ f ║ ║ f ║ ║ id ║ ╚════╝ ╚════╝ ╚════╝ == Horizontal composition == Horizontal composition is an elementary combinator with two holes: ╔═══════════════╗ ║╔═════════════╗║ ║║ ⟨hole₁⟩ ║║ ║╚═════════════╝║ ║╔═════════════╗║ ║║ ⟨hole₂⟩ ║║ ║╚═════════════╝║ ║ h-composition ║ ╚═══════════════╝ Simplified visualisation: ╔═════════╦═════════╗ ║ ⟨hole₁⟩ ║ ⟨hole₂⟩ ║ ╚═════════╩═════════╝ Horizontal composition operates on PAIRS of values. The algorithms in the holes are executed in parallel. Example: ╔════╦════╗ ║ +3 ║ *2 ║ ╚════╩════╝ -------- --- --------- (4, 5) ↦ (7, 10) (0, 0) ↦ (3, 0) -------- --- --------- Example for using horizontal and vertical composition in the same algorithm: ╔══════════════════╗ ║ dup ║ ╠════╦═════════════╣ ║ id ║ rotateRight ║ ╠════╩═════════════╣ ║ overlay ║ ╚══════════════════╝ An example of what this algorithm does: █▀▀█ █ █ █▀▀▀▀▀▀▀▀▀▀█ ↦ █▀▀▀█ █▀▀▀█ █▄▄▄▄▄▄▄▄▄▄█ █▄▄▄█ █▄▄▄█ █ █ █▄▄█ dup is an elementary combinator which takes a value and returns a pair of the duplicated value. overlay is a predefined combinator which takes a pair of diagrams and returns a diagram which is made by overlaying the second diagram on the first one. == Wires == A better visualisation of dup and id is to draw wires in their boxes: ╔════════╤═════════╗ ║ ╭─────┴──╮ dup ║ ╠══╪═╦══════╧══════╣ ║id│ ║ rotateRight ║ ╠══╧═╩═════════════╣ ║ overlay ║ ╚══════════════════╝ A clearer presentation of the same algorithm: ╷ ╭─────┴──╮ │ ╔══════╧══════╗ │ ║ rotateRight ║ ╔══╧═╩═════════════╣ ║ overlay ║ ╚══════════════════╝ Boxes can completely be separated by wires: ╷ ╷ ╷ ╭─────┴──╮ ╭─────┴──╮ ╭─────┴──╮ │ ╔══════╧══════╗ │ ╔══════╧══════╗ │ ╔══════╧══════╗ │ ║ rotateRight ║ │ ║ rotateRight ║ │ ║ rotateRight ║ = │ ╠═════════════╣ = │ ╚══════╤══════╝ ╔══╧═╩═════════════╣ │ ║ id ║ │ │ ║ overlay ║ ╔══╧═╩═════════════╣ ╔══╧════════╧══════╗ ╚══════════════════╝ ║ overlay ║ ║ overlay ║ ╚══════════════════╝ ╚══════════════════╝ We may draw wires instead of the following elementary combinators (the detailed discussion is omitted for brevity): name example how the wire looks like typically --------- ----------------------------- ----------------------------------- id 3 ↦ 3 vertical bar assoc ((12, 5), 7) ↦ (12, (5, 7)) diagonal bars swap (3, 4) ↦ (4, 3) crossing diagonal bars first _ first (*2): (4, 3) ↦ (8, 3) wires by-passing blocks dup 8 ↦ (8, 8) fork fst (6, 2) ↦ 6 dead end There are algorithms to convert freely drawn wires to these combinators. Similar wires will result in identical algorithms which is ensured by the associativity of composition and several laws for id, assoc, swap, first, dup and fst. == Variables == Although ‘variable’ is not a basic concept for Categorical combinators, it can be introduced to simplify complex wires. Wires can be named: ╷ ╭─────a──╮ │ ╔══════╧══════╗ │ ║ rotateRight ║ ╔══╧═╩═════════════╣ ║ overlay ║ ╚══════════════════╝ Named wires can be hidden: a ╔══════a══════╗ ║ rotateRight ║ ╔══a═╩═════════════╣ ║ overlay ║ ╚══════════════════╝ A good visualization tool can mix combinators, wires and variables. == Textual representation == One can use also a textual representation of combinators. First name anonymous horizontal sides: ╔══════a══════╗ ║ rotateRight ║ ╔══a═╩══════b══════╣ ║ overlay ║ ╚════════c═════════╝ Then convert boxes to rows: b <- rotateRight -< a c <- overlay -< (a, b) This syntax is the arrow syntax in Haskell. (Unfortunately I could not use the Haskell arrow syntax in the editor implementation because the Haskell arrow notation is desugared to pure functions boxed into combinators instead of the elementary combinators id, assoc, swap, dup etc.) == Other elementary combinators == The remaining elementary combinators not discussed here are related with CONDITIONAL EXECUTION and HIGHER-ORDER ALGORITHMS (where algorithms may travel in wires). It’s cool that these features can be turned on and off by allowing or disallowing the corresponding elementary combinators. One can also reduce the power of these features by wrapping the corresponding elementary combinators into less general combinators. EFFECTFUL COMBINATORS Although Categorical combinators are computationally universal, we can add effectful combinators to Categorical combinators. The effectful combinators may simplify the implementation of a whole class of algorithms. == Local state with delay == delay is an elementary combinator which simplifies the implementation of algorithms with local state. delay has a local state. When delay is given a value, it gives back its local state and replaces its local state with the given value. For example, suppose that the initial local state of delay is 0: ╔═══════╗ ║ delay ║0 ╚═══════╝ Examples of sending values through this combinator one after each-other: ---- --- ---- 5 ↦ 0 3 ↦ 5 42 ↦ 3 3 ↦ 42 ---- --- ---- For purists it may be disturbing that the result for input 3 is not always the same. Can we call delay a function? No, we can’t. delay is not a function, it is AN ALGORITHM WITH LOCAL STATE. == Side-note about purity == Algorithms with local state are impure in the sense that they may not give the same output given the same input. The pure-impure distinction is very important but the world of algorithms is not that black-and-white. There are even more impure algorithms whose effects cannot be reversed, and there are algorithms which have better properties than just being pure: bidirectional, linear, first-order. One should be aware about these distinctions when making general statements about algorithms. Categorical combinators makes the classification easy by enumerating the combinators used in an algorithm. Type systems – for example, type classes in Haskell – can track the presence of different combinators for us. This is similar to tracking side effects with monads but simpler than that. == Examples == Example for composing delay with other combinators: ╔═══════╤═════════╗ ║ ╭────╯ ╭────╮ ║ ║ │ ╔═════╧═╗ │ ║ ║ │ ║ delay ║0 │ ║ ║╔═╧═╩═══════╣ │ ║ ║║ + ║ │ ║ ║╚══════╤════╝ │ ║ ║ ├───────╯ ║ ║ │ sum║ ╚═══════╧═════════╝ ---- --- ---- 5 ↦ 5 3 ↦ 8 42 ↦ 50 3 ↦ 53 ---- --- ---- Here (+) is a predefined combinator which adds its two inputs together. For replacing the wires with combinators in sum we need the so called FEEDBACK COMBINATOR too: ╔═══════╤════════╗ ║ ╭──╯ ╭────╮ ║ ║╔═══╧════╧═══╗│ ║ ║║ ⟨hole⟩ ║│ ║ ║╚═══╤════╤═══╝│ ║ ║ ╰──╮ ╰────╯ ║ ║ │feedback║ ╚═══════╧════════╝ == Halting the execution with halt == halt is an elementary combinator which halts the execution of an algorithm: ╔══════╗ ║ halt ║ ╚══════╝ In this blog post halt is hidden inside predefined combinators like (/) which divides two numbers. (/) halts the execution if the second number is zero: ╔═══════╗ ║ / ║ ╚═══════╝ -------- --- -------- (4, 5) ↦ 0.8 (2, 0) ↦ ⟨halt⟩ (2, 1) ↦ 2 -------- --- -------- The behaviour of algorithms containing both halt and delay is determined by the behaviour of the elementary combinators, but the semantics of elementary combinators should take both effects into account. halt is useful if we want to allow a user input (like hitting the delete key at the end of a text) but we want no response to it. == Other effectful combinators == With other effectful combinators not discussed here one can: - resurrect a halted execution - generate a random number - log events DIFFERENT TYPE OF BIDIRECTIONAL COMBINATORS Bidirectional combinators can be visualised as follows: ▴ ▾ ▾ ▴ ╔══╧══╗ ╔═╧══╧═╗ ║ ║ or ║ ║ ╚══╤══╝ ╚═╤══╤═╝ ▴ ▾ ▴ ▾ As effectful combinators, bidirectional combinators may simplify the implementation of a whole class of algorithms. In case of simple bidirectional combinators, each input results an output on the other side. Examples: 10 28 ▾ ▴ ╔══x══╗ ╔══x══╗ ╔══x══╗ ╔══x══╗ ║y=x+2║ ↝ ║y=x+2║ ║y=x+2║ ↝ ║y=x+2║ ╚══y══╝ ╚══y══╝ ╚══y══╝ ╚══y══╝ ▾ ▴ 12 30 In case of CONCURRENTLY BIDIRECIONAL combinators, each input results in OUTPUTS ON BOTH SIDES. An example is the following stateful perturbation transforming combinator which compensates too big perturbations by sending back corrections: (-10) (+4) ▾ ▴ ╔══x══╗x=6 ╔══x══╗x=0 ║0<y<x║y=2 ↝ ║0<y<x║y=0 ╚══y══╝ ╚══y══╝ ▾ (-2) Algorithms using bidirectional connections are well-defined if the elementary combinators are well-defined. Here we discuss the semantics of composition only. In case of simple bidirectional combinators, the semantics of composition is rather simple. Each input goes sequentially through the two holes to the other side, in the right order: ▾ ▴ ╔══╪═══╪══╗ ║╔═╧═══╧═╗║ ║║ ║║ ║╚═╤═══╤═╝║ ║ │ ▴ ║ ║ ▾ │ ║ ║╔═╧═══╧═╗║ ║║ ║║ ║╚═╤═══╤═╝║ ╚══╪═══╪══╝ ▾ ▴ In case of concurrently bidirectional combinators, the semantics of composition is more sophisticated: ▾ ▴ ╔══╪═════════╪══╗ ║ │ ╭▸──────┤ ║ ║ │ │ ... │ ║ ║╔═╧═╧═══════╧═╗║ ║║ ║║ ║╚═╤═╤═════╤═╤═╝║ ║ │ ▴ │ ▴ ║ ║ │ │ ... │ │ ║ ║ ▾ │ ▾ │ ║ ║╔═╧═╧═════╧═╧═╗║ ║║ ║║ ║╚═╤═══════╤═╤═╝║ ║ │ ... │ │ ║ ║ ├──────◂╯ │ ║ ╚══╪═════════╪══╝ ▾ ▴ - The values between the holes are ping-ponged until one hole gives it up. - Holes can give up ping-ponging by sending an empty value to the other hole. - The values emitted on the other sides during ping-ponging are collected and concatenated. These will be the two outputs. The values on the wires should have a monoid structure which means that they need to have a composition operation and an empty/identity value. Typical monoids for wires: - Lists with list concatenation and the empty list. - Perturbations with perturbation composition and the identity perturbation. FURTHER READING - Chris Penner: Deconstructing Lambdas: an awkward guide to programming without functions (youtube link; hackage library) - Conal Elliott: Compiling to categories - There and Back Again – Arrows for Invertible Programming (pdf paper; hackage library) CONCLUSION - Algorithms can be built up from categorical combinators. Typical categorical combinators are horizontal and vertical composition. - One can draw wires instead of fairly complex compositions of combinators. One can write text instead of drawing wires. - Effectful combinators and bidirectional combinators may simplify the implementation of a whole class of algorithms. /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \ REDUCE CODE COMPLEXITY WITH RESTRUCTURING (CASE STUDY) ====================================================== As a case study, I reduce the code complexity of the one-line text editor with categorical combinators. MOTIVATION Suppose that we begin to use a new, user-friendly application, and we get familiar with it under a few days. Suppose moreover, that someone explains us the application logic under a few weeks. More or less this means that the ‘what’ and ‘how’ of the application has a few days and a few weeks of PERCEIVED COMPLEXITY, respectively. We still don’t know the perceived complexity of ‘how to do efficiently’ because we have no clue how the application works on the actual hardware: perceived complexity of the application ┌─┬─────┬──────────────────────── ─── ─── ─── │d│weeks│ ? │a│ │ │y│ │ │s│ │ │ │ │ │W│ HOW │ how to do efficiently │H│ │ │A│ │ │T│ │ └─┴─────┴──────────────────────── ─── ─── ─── In my experience more or less the CODE COMPLEXITY of the same application looks like the following: code complexity of the application ┌─── ─── ─── ─── ─── ─── ─── ─── ─── ─── ─── ─── ───┬─── ─── ─── ─── ───┐ │months or years │ │ │ │ │ │ │ efficient │ │ │ │ │ user interface program logic │ data structures │ │ │ & │ │ │ algorithms │ │ │ │ │ │ │ └─── ─── ─── ─── ─── ─── ─── ─── ─── ─── ─── ──────┴─── ─── ─── ─── ───┘ There is a huge gap between learning the ‘what’ and ‘how’ in weeks vs. understanding the application’s user interface and program logic code in months or years. I see the following possible causes: 1. The code is NOT DOCUMENTED. This can be mitigated somewhat by relying on the active developers to explain the code for us. 2. The code is NOT PROPERLY STRUCTURED. 3. We learn the application faster because we already know other applications, and we have to learn just once what is common in applications. Code reuse has similar effect on code complexity, but the PROGRAM LOGIC IS COUPLED WITH OVERWHELMING EFFICIENCY COMPLEXITY which cannot be eliminated from there by code reuse. On the other hand, the code complexity of efficient data structures has been reduced somewhat by programming libraries and compilers. I try to narrow the gap between the perceived complexity and code complexity of applications. In this blog post I present a case study about CAUSE 2. I plan to discuss cause 3. at another time. THE ONE-LINE TEXT EDITOR The text editor is probably the most iconic interactive application. The one-line editor can edit a single line of text: editor view action done ------------- ------------------ | Hello Worl | Hello Worl cursor movement |t Hello Worl . |i Hello Worl . |m Hello Worl . |e Hello Worl . | Hello Worl . v Hello Worl . Hello Worl . Hello Worl . ello World . llo World! . lo World! . lo World deletion lo Worl . lo Wor . lo Wo . lo W . lo . lo . lo! insertion llo! visible area shift ello! . Hello! . Hello! window resize Hello! . Hello! . Hello! . Hello . Hello cursor movement Hello . Hello . Hello . As a case study, I reimplement the one-line text editor. My goal is to minimise its code complexity such that I don’t count the complexity of independent, reusable parts. == Editor features == The USER INPUT is one of the following events: ------------------------------------------------------------------------------ event function details -------------------------------- -------------------- ------------------------ Del | Backspace | Left | Right control key | ShiftLeft | ShiftRight Char p printable character p: 'a' | 'b' | 'c' | … Resize w window resize w: width (in characters) ------------------------------------------------------------------------------ I have selected the following editor features for the case study: - the cursor is shown by color inversion: Hello world! - the visible area after the editable text is reddish: Hello world! - character insertion: Hello world! & Char 'y' = Heyllo world! - character deletion - Heyllo world! & Backspace = Hello world! - Heyllo world! & Del = Hello world! - cursor movement - Hello world! & Right = Hello world! - Hello world! & Left = Hello world! - visible area shift - Hello world! & ShiftRight = Hello world! - Hello world! & ShiftLeft = Hello world! - visible area resize: Hello world! & Resize 5 = Hello world! == Corner cases == The set of corner cases is more vague than the set of features. A corner case for someone may be a feature or a common case for someone else. For me the editor has the following corner cases: - rendering the cursor at the end of the edited text (“reddish white”): Hello world! - inputs for which nothing should happen (no re-rendering) - Hello world! & Backspace - Hello world! & Left - Hello world! & ShiftLeft - Hello world! & Del - Hello world! & Right - Hello world! & ShiftRight - Hello world! & Resize 10 - inputs for which the visible area should be shifted too - Hello world! & Left = Hello world! - Hello world! & Backspace = Hello orld! - Hello world! & Right = Hello world! - Hello world! & Char 'o' = Hello worold! - inputs for which the cursor should be moved too - Hello world! & Resize 2 = Hello world! - Hello world! & ShiftRight = Hello world! - Hello world! & ShiftLeft = Hello world! == Perceived complexity of corner cases == Users predict the behaviour of the application in the corner cases and they note the surprising cases only. I conclude that the perceived complexity of corner cases correlates with the number of surprising corner cases – which should be minimal – plus the complexity of the INFERENCE PROCESS by which users predict the behaviour of the application. There is an asymptotic (huge) difference between the number of corner cases and the perceived complexity of corner cases. The number of corner cases grows probably exponentially with the number of features because corner cases may arise as interactions between different features. On the other hand, in my experience the perceived complexity of corner cases grows not much faster than the number of features. I want the code complexity to correlate with the pereceived complexity of the corner cases. For this I want to REFLECT AND DISTILL THE INFERENCE PROCESS by which users predict the behaviour in corner cases. As a side-effect the number of surprising corner cases will be minimized too. == Editor state == For further analysis, let’s introduce the following definitions about the state of the editor: --- -------------------------------------------------- t the editable text c cursor position inside t (beginning with 0) b start position of the visible area (in characters, counted from the beginning of t) e end position of the visible area (in characters, counted from the beginning of t) w width of the visible area (in characters) --- -------------------------------------------------- The extended screenshot is a compact visualisation of these values. For example, Hello world! is a visualisation of {t = "Hello world!", c = 7, b = 5, e = 15, w = 10} User input can be mapped to EDITOR STATE PERTURBATIONS. Some examples: user input perturbation meaning ------------ ------------- --------------- Left ∆c = (-1) decrement c Right ∆c = (+1) increment c ShiftLeft ∆b = (-1) decrement b ShiftRight ∆b = (+1) increment b == Constraints on state are related to corner cases == The editor state should always fulfil these so-called INVARIANT PROPERTIES: invariant explanation/feature ------------- ----------------------------------------------------------- b ≤ c ≤ e the cursor is inside the visible area 0 ≤ b the visible area cannot be shifted before the editable text c ≤ length t the cursor is inside the editable text e = w + b the meaning of ‘width’ These constraints are inherent parts of the editor state. Hello world! can be also seen as a visualisation of {t = "Hello world!", c = 7, b = 5, e = 15, w = 10 | 0 ≤ b ≤ c ≤ e, c ≤ length t, e = w + b} == Side-note about the notation == The part after the vertical bar is static information which can be expressed by refinement types or dependent types. Expressing it by refinement types would look like this: {t = "Hello world!", c = 7, b = 5, e = 15, w = 10} : {t ∊ String; c, b, e, w ∊ ℤ | 0 ≤ b ≤ c ≤ e, c ≤ length t, e = w + b} I use a bit more compact notation in the examples. The editor’s corner cases are closely connected to the constraints. Consider the corner case when the cursor is at the right end of the visible area and the user hits Right: Hello world! & Right This stands for {c = 9, e = 10, … | c ≤ e, …} & (∆c = (+1)) Here the application of the perturbation would invalidate c ≤ e which is a signal for a corner case. == Handle corner cases by adjusting the perturbed state == The common approach to handle the editor corner cases is to perturb the state and adjust it afterwards by a dedicated program logic which is called adjustVisibleArea in the following example: Hello world! = {c = 9, b = 0, e = 10, … | c ≤ e, e = w + b, …} & (∆c = (+1)) = adjustVisibleArea {c = 10, b = 0, e = 10, … | ~~c ≤ e~~, e = w + b, …} = {c = 10, b = 1, e = 11, … | c ≤ e, e = w + b, …} = Hello world! This approach has the following shortcomings: - The c ≤ e constraint is temporarily invalidated which disturbs code verification. - The program logic is not tightly connected to the constraints. The adjusting code is invented on-the-fly and verified later. - Different adjusting logic is needed for different user actions. For example, if the user moves the cursor, the visible area should be adjusted but if the user shifts the visible area, the cursor should be adjusted. To trust the code we have to check that it respects the user’s intention. I suspect that this doesn’t scale well for more complex applications. == Handle corner cases by perturbation propagation == Perturbation propagation is also known as constraint propagation. Maybe it is easier to understand perturbation propagation if we split it into two distinct phases first. In the first phase the perturbations are propagated in all possible ways: Hello world! & Right = {c = 9, b = 0, e = 10, w = 10, … | c ≤ e, e = w + b, …} & (∆c = (+1)) - = {c = 9, b = 0, e = 10, w = 10, … | c ≤ e, e = w + b, …} = Hello world! (the user input is rejected) - = {c = 10, b = 0, e = 10, w = 10, … | ~~c ≤ e~~, e = w + b, …} & (∆e = (+1)) - = {c = 10, b = 0, e = 11, w = 10, … | c ≤ e, ~~e = w + b~~, …} & (∆b = (+1)) = {c = 10, b = 1, e = 11, w = 10, … | c ≤ e, e = w + b, …} = Hello world! (the cursor moved and visible are is shifted) - = {c = 10, b = 0, e = 11, w = 10, … | c ≤ e, ~~e = w + b~~, …} & (∆w = (+1)) = {c = 10, b = 0, e = 11, w = 11, … | c ≤ e, e = w + b, …} = Hello world! (the cursor moved and the width of the visible area is increased) After the first phase we get several possible results. In the second phase the results are filtered and the first good result is chosen. This two-phase approach is tightly connected with the constraints and avoids the ad-hoc adjusting logic but it has at least two drawbacks: - an ad-hoc filtering is needed - the constraints are still temporarily invalidated == One-phase perturbation propagation == In the editor application we know in advance (= statically) the constraints and the valid propagation of different perturbations. Examples of such static knowledge: - In the constraint e = w + b the perturbation of b induce the perturbation of e and the other way around but not the perturbation of w. This knowledge comes from the expectation that the editor should not change its width if the user doesn’t want to do so. Let’s AUGMENT THE CONSTRAINT with this propagation knowledge by adding a prime to the plus sign: e = w +’ b. - e is present in only two constraints and it is not directly perturbed by user input. If e is perturbed by c ≤ e then the e = w + b constraint should propagate the perturbation further and the other way around. No other constraints should be involved in between. With the static knowledge perturbation propagation can done in one phase. The running example looks like now this: Hello world! & Right = {c = 9, b = 0, e = 10, w = 10, … | c ≤ e, e = w +’ b, …} & (∆c = (+1)) = {c = 10, b = 0, e = 10, w = 10, … | ~~c ≤ e~~, e = w +’ b, …} & (∆e = (+1)) = {c = 10, b = 0, e = 11, w = 10, … | c ≤ e, ~~e = w +’ b~~, …} & (∆b = (+1)) = {c = 10, b = 1, e = 11, w = 10, … | c ≤ e, e = w +’ b, …} = Hello world! Either compilers may generate efficient code from the static knowledge, or better, we can structure the editor’s code such that it directly reflects the static knowledge. Let’s see how. == Avoid temporary invalidation of constraints == First I show how to avoid temporary invalidation of constraints. The main idea is to compose complex constraints from basic ones. For this, constraints are represented as BIDIRECTIONAL STATEFUL ALGORITHMS (see later). Each constraint has its own local state on which THE CONSTRAINT ALWAYS HOLDS. During the propagation of perturbations, the perturbations change the local state of the constraints as they are propagated by them. Here are three steps of an example propagation: 1. │c ∆c = (+1) ╔══════╧══════╗ ║ c ≤ e ║ c = 9, e = 10 ╚══════╤══════╝ │e ╔══════╧══════╗ ║ e = w +' b ║ e = 10, w = 10, b = 0 ╚═══╤═════╤═══╝ │w │b The initial perturbation is ∆c = (+1). There are two basic constraints composed together. The local states on the right of the boxes are in sync and the constraints hold on them. 2. │c ╔══════╧══════╗ ║ c ≤ e ║ c = 10, e = 11 ╚══════╤══════╝ │e ∆e = (+1) ╔══════╧══════╗ ║ e = w +' b ║ e = 10, w = 10, b = 0 ╚═══╤═════╤═══╝ │w │b ∆c = (+1) was propagated by the c ≤ e constraint whose local state was changed. The new perturbation to be propagated is ∆e = (+1). At this point the values of e are different in the two local states, but the constraints still hold on the local states. 3. │c ╔══════╧══════╗ ║ c ≤ e ║ c = 10, e = 11 ╚══════╤══════╝ │e ╔══════╧══════╗ ║ e = w +' b ║ e = 11, w = 10, b = 1 ╚═══╤═════╤═══╝ │w │b ∆b = (+1) At the end of the propagation the local states are in sync again. == The final editor structure == At this point I am ready to show you the final editor structure which looks like this: ┌─user input─┐ ╭──────────────┬───◂ const w ↤ Resize w ╎ │ ╰──▸ screen ╎ ╎ │ ╭───▸ screen ╎ ╎ w│ ╭──────┬──┴──┬────◂ (-1) ↤ ShiftLeft ╎ ╔═╧═══╧═╗ │b ╰────◂ (+1) ↤ ShiftRight ╎ ║ +' ║ │ ╎ ╎ ╚═══╤═══╝ ╔══╧══╗ ╎ ╎ │e ║ ≤ ║ ╎ ╎ ╔══╧══╗ ╚══╤══╝ ╎ ╎ ║ > ║ │ ╎ ╎ ╚══╤══╝ │c ╭────◂ (-1) ↤ Left ╎ ├────────┴─────┴────◂ (+1) ↤ Right ╎ c│ ╭──────◂▸ co-editing ╎ ╎ ╔═╧═══╧═╗ t ╎ ╎ ║splitAt║ ╎ ╎ ╚═╤═══╤═╝ t₂ ╎ ╎ t₁│ ╰──────┬──◂ deleteAt 0 ↤ Del ╎ ├───────╮ ╰────▸ screen ╎ ╎ ╔═══╧═══╗ ╰───────▸ screen ╎ ╎ ║reverse║ ╎ ╎ ╚═══╤═══╝ t₁'╭─◂ insertAt 0 c ↤ Char c ╎ ╰─────────┴───◂ deleteAt 0 ↤ Backspace ╎ └────────────┘ Explanation: - User input is mapped to perturbations which are fed into the constraint network. - Output perturbations are used to render the editor on the screen (see later). - Support for COOPERATIVE-EDITING is a bonus feature with this architecture. Cooperative editing means that several users edit the same text such that each user runs its own editor instance. These editor instances can be synchronized by feeding their perturbations of t into each-other. - t₁ and t₂ are the text before and after the cursor, respectively. - (t₁, t₂) = splitAt (c, t) is a constraint which holds if t is the concatenation of t₁ and t₂, and length t₁ = c. From this follows that the property c ≤ length t always holds. - The following perturbations of texts are used: - insertAt i c – insert the character c at position i - deleteAt i – delete the character at position i - t₁′ = reverse t₁ is a constraint which holds if t₁′ is the reverse of t₁. The characters at the beginning of t₁′ are the characters right before the cursor, in reversed order. Backspace is mapped to deleteAt 0 which deletes the character before the cursor. Char c is mapped to insertAt 0 c which inserts c right before the cursor. Wires are translated to CONSTRAINT COMBINATORS. The translation process is automatic and it can be done by the compiler. The translation process is stable if certain conditions hold. You can read more about this in the Appendix. The circle in the wiring could have many interpretations. The interpretation of circles is connected to the SCHEDULING OF PROPAGATION. I allow only SCHEDULING-INDEPENDENT networks, for which any scheduling gives the same result. Scheduling-dependent networks can be ruled out either by the programmer or by strong static typing which I don’t discuss here. The actual scheduling is determined by the translation process of networks. This architecture handles all corner cases correctly. Let’s see the running example first: Hello world! & Right The relevant part of the network looks like this after perturbation propagation is finished: w = 10 ╭──────────────▸ - │ ╭──────┬───▸ (+1) ╔═╧═══╧═╗ │b = 0 & (+1) ║2. +' ║ │ ╚═══╤═══╝ ╔══╧══╗ e=10│&(+1)║3. ≤ ║ ╔══╧══╗ ╚══╤══╝ ║1. > ║ │ ╚══╤══╝ │c = 9 & (+1) ├────────┴──────────────────◂ (+1) ↤ Right │ ╭────────▸ - ╔══╧═══╧══╗ t = "Hello world!" ║4.splitAt║ ╚══╤═══╤══╝ t₂ = "ld!" & deleteAt 0 │ ╰────────▸ deleteAt 0 ╰────────────▸ insertAt 9 'l' t₁ = "Hello wor" & insertAt 9 'l' Remarks: - The scheduling of propagation does not matter, but the actual order is given by 1–4. It is possible to automatically visualize the propagation without touching the editor’s code (visualization can be added as a feature of constraint combinators). - The beginning of the visible area is incremented (∆b = (+1)) as expected. - The cursor position is also incremented (∆c = (+1)) but this information is not directly used in the screen rendering. The screen will be updated because t₁ and t₂ (the texts before and after the cursor) are perturbed. - The editable text is not perturbed which is right. In the second example the user tries to delete the character after the end of the text: Hello world! & Del The relevant part in this case is just the splitAt constraint: c=│12 ╭──────▸ - ╔═╧═══╧═╗ t = "Hello world!" ║splitAt║ ╚═╤═══╤═╝ t₂ = "" t₁│ ╰──────◂ deleteAt 0 ↤ Del Here the splitAt halts the propagation process because it is not possible to propagate the deletion of the first character of the empty text. Because the propagation is halted, nothing will happen, which is the right behaviour. Halting the propagation is an optional feature of constraint combinators. You can read more about halting in the Appendix. == Rendering the editor on the screen == The editor can be rendered on the screen from w (the editor width), b (the begin position of the visible area), t₁ (the text before the cursor) and t₂ (the text after the cursor). Just for illustration, here is the Haskell code for rendering the output: render w b t₁ t₂ = take w ( -- drop invisible glyps at the end drop b ( -- drop invisible glyps at the beginning map normalColor t₁ -- colour the characters before the cursor ++ mapHead invertColors ( -- invert the colours of the character -- right after the cursor map normalColor t₂ -- colour the characters after the cursor ++ repeat (reddishColor ' ') -- unlimited reddish space behind ) ) ) The functions normalColor and reddishColor map characters to glyphs (colored characters). invertColors maps a glyph to a glyph by exchanging it’s foreground and background colors. mapHead applies a function to the first element of a list. == Incremental rendering == We don’t want waste computation power by re-rendering the whole screen for each user input. This is even more important for GUI programs. Incremental rendering is important for co-editing too: if another user edits part of the text which is not in the visible area of the user, then the user’s screen should not be touched at all. Fortunately, the render function can be converted to a ∆render function which maps the perturbations from the editor core into perturbation of the screen, which is what incremental rendering means. ∆render can also be constructed from combinators. For this we need simpler combinators than in perturbation propagation because ∆render contains one-way wires only. Let’s see the running example: Hello world! & Right The relevant output of the editor core is: ∆b = (+1), ∆t₂ = deleteAt 0, ∆t₁ = insertAt 9 'l' Without going into further details, ∆render will produce the following output: insertAt 8 (normalColor 'l') . insertAt 8 (invertColors (normalColor 'd')) . deleteAt 8 . deleteAt 0 Here the dot is the (reversed) composition of perturbations. If we apply the individual perturbations one by one we get to the final rendering from the previous rendering: Hello worl ello worl – deleteAt 0 ello wor – deleteAt 8 ello word – insertAt 8 (invertColors (normalColor 'd')) ello world – insertAt 8 (normalColor 'l') IMPLEMENTATION You have to go through the Appendix if you want to understand the actual implementation. I encourage you to read it also if you have not heard about categorical combinators yet. You can find the source code of the implementation here. Note that the implementation is not in sync with this blog post and incremental rendering is not implemented which should be fixed soon. WHAT’S NEXT? I am going to implement a multi-line text editor and a basic TUI (textual user interface) email client and browser with as small code complexity as I can. FURTHER READING - Related Haskell Reddit conversation CONCLUSION - There is huge gap between the perceived complexity of applications and their code complexitiy. One cause is that application code is not structured properly. - As a case study I structured the code of the one-line text editor properly. - The editor handles ~15 corner cases and it is built up from 5 independent, reusable pieces such that the corner cases are handled by the composition of these pieces. - As a bonus, the implementation supports cooperative editing by default. /\ /\ /\ /\/\ /\ /\ /\/\ /\ /\ /\/\ /\ /\ /\/\ /\ /\ /\ \/ \/\/ \/ \/ \/\/ \/ \/ \/\/ \/ \/ \/\/ \/ \/ \/\/ \/ MONTHLY RECORD ============== GOING BACK 30 YEARS IN TIME (SEPTEMBER, 2021) Time traveling is possible. I already did it. I put aside my smartphone. I started to use nano, a text editor similar to Pico from 1989. I switched to alpine, an email client similar to Pine from 1992. The hardest step was to switch to elinks, a web browser similar to Lynx from 1992. I could spend most of the time using just these programs on my computer. They were refreshingly simple to use, and I was surprisingly effective with them. It was certainly fun, but why I did this? I want to make programming common knowledge and for this I have to test my ideas on operating system design. It is a lot easier to write a prototype but still usable operating system if I lower my needs temporarily. USING MY OWN SYSTEM (OCTOBER, 2021) The programs nano, alpine and elinks were simple enough for me to rewrite, especially because I used only a fraction of their features. Instead of replicating their look-and-feel, I replaced alpine and elinks with my own solution, a Haskell source file containing 500 lines of code. (I reused programming libraries to do the lower level steps of receiving and sending emails and getting web pages.) 500 lines of code is so small that I can have full control over my email client and my web browser. I can change the code whenever I want. I can try out new ideas tailored for my workflows, which is a very good feeling. I could replace nano too, but I decided to do that later, because I arrived to the point where I can reimagine what an operating system is, which is a lot more interesting! But before that I had to stop for starting my Patreon project. PATREON PROJECT START (NOVEMBER, 2021) We don’t have universal basic income, so I looked for an alternative. I chose Patreon because it gives enough independence and freedom for me, and it has very little bureaucracy. Donate me if you are interested in the outcome of this project. I can work 40 hours per week on this project if I reach €1500 per month. I log your questions and my answers to them on the questions and answers section. I will monthly report my progress. From the first report, my work will be open sourced with documentation such that partial results can be reused in independent projects. REPHRASING THE GOAL (DECEMBER, 2021) Although my ultimate goal did not change, I have to rephrase it because almost nobody understood it, according to the feedback I have got. To be transparent, I put the source code of my homepage on GitHub where you can follow how it changed in the past if you are interested. [Update on 8 July, 2022: I removed the GitHub repository] In the meantime I was working on my prototype operating system too. The first official version will be released next month. Stay tuned! ONE-LINE TEXT EDITOR (JANUARY, 2022) In December and January I prepared the prototype code for the first public release. I was not satisfied with the description of the email client and I started an experiment to reduce its code complexity. The experiment resulted in a case study about a one-line text editor. CASE STUDY DOCUMENTATION (FEBRUARY, 2022) I finished the documentation of the case study and I finally released the operating system code on GitHub. [Update on 8 July, 2022: The source code is available here, not on GitHub.] The released source code contains: - the Haskell code of a high level virtual machine which can currently read and send emails, read keyboard input and write characters on the terminal screen - the Haskell code of the operating system running on the virtual machine; currently the operating system consists of a very simple email client - the source code of the editor case study Next I want apply the principles learned during the case study on the operating system code. SWITCHING TO HALF-TIME EMPLOYMENT (MARCH, 2022) I didn’t get close to my Patreon goal so from April I will be half-time employed by a commercial company. I continue to work on this project in 80 hours per month. I decided to shut down my Patreon page, to reduce administration. Thank you very much for your support! X64 CPU SEMANTICS IN IDRIS (MAY - JULY, 2022) I took a break in May. At ZuriHac in June I wrote down (part of the) semantics of the X64 CPU. The goal is to use the CPU in a reliable way. Here is the result: X64CPU.idr I minimised my homepage in July. PAGE EDITOR (AUGUST, 2022) I switched from nano to my own text editor. It supports basic editing and text search in ~140 LOC in Haskell. (Not yet released.) PAGE EDITOR OS (SEPTEMBER - OCTOBER, 2022) I integrated a basic shell into the page editor. I can execute selected texts as shell commands with a key sequence. The output of the command is inserted back into the edited text file. Similarly I integrated an interpreter (ghci) into the page editor. I use just one big text file and put everything in it. I call it "source file". The source file is always opened with the page editor. This is my "page editor operating system". I can quickly go into marked places in the source file by searching strings. The page editor's source code is included in the source file. The page editor recompiles itself by hitting a key sequence. I integrated basic browser into the page editor. I can open a selected url with a key sequence. The downloaded page is converted into plain text and inserted into the source file. I integrated a basic email client into the page editor. INDEPENDENCE FROM LINUX (NOVEMBER, 2022) I implemented a basic boot loader in 16bit x86 assembly language. I implemented a limited editor in assembly which is loaded by boot loader. The editor does input/output with BIOS calls. The editor saves the edited text on the disk after its code. The saved text is automatically loaded on start. The cursor position is also saved. On my netbook, I see the exactly the same thing on the screen after 0.1 sec if I hit Ctrl+Alt+Del, so this is the total time booting the OS, starting the editor and loading the saved text :) INDEPENDENCE FROM NASM ASSEMBLER (DECEMBER, 2022) I implemented my own 16 bit code generator in Haskell. It is able to generate code for the boot loader and for the limited editor. TYPED ASSEMBLY (JANUARY - MARCH, 2023) I implement a type checker for safe machine code generation. /\/\ /\/\ /\/\ /\/\ /\/\ /\/\ /\/\ /\/\ /\/\ /\/\ \/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/ QUESTIONS AND ANSWERS ===================== I collect here the questions asked by others and my answers to them. GENERAL QUESTIONS == How long is your project? == My workplan is for 30 years according to my brother who is a senior game developer. Later he was surprised how fast I could replace the email client and the web browser with my own solution though. I think that the key to finish my project in a few years is to find the right path to follow. The path should take incremental steps. Each step should be small and interesting enough to keep my motivation. For this I have to find the essence of the problems and skip most of the details. I have to find minimalist solutions, founded on pure Mathematics to stay below the complexity level that I can tackle. I can do rapid prototyping, switch between tools and reschedule the plan to avoid blocking, to make advantage of the fact that this is a single-person project. Testing is partially done by using my own system during its development (which is called dogfooding). == Who is your target audience? == Burned-out programmers. :) To be serious, if the question is who should donate me, I would say that anyone who thinks that software systems around us are way too complicated and that they should be simplified to human scale. == Why don’t you apply for a scientific grant? == This is a high-risk, high-benefits project, and it would add additional risk to prepare for a grant. In this competition there are so many good players and only a few will win. Doing my plan as a Patreon project has also a smaller budget so it has a better benefit per cost ratio. QUESTIONS ABOUT CODE GENERATION (I presented still unpublished ideas about code generation.) == Do you need a separate language? == I am not sure. I will begin the project in three directions: an EDSL in Idris, an EDLS in Agda and a DSL with a compiler written in Haskell. After the first or second iteration I will decide which is the best. == What does (b : Bool IP) mean exactly? == This means that b is determined by the value of the Instruction Pointer. So b need not be stored in a general-purpose register or in memory. Note that IP is not determined by b, because the same Boolean value may belong to more IP values. == How is your project related to Coq: The world’s best macro assembler? == This paper is totally related! Differences: - The paper models the Intel 32 bit architecture, I model the 64 bit architecture. - The paper describes a Coq EDSL; I develop an Agda/Idris EDSL or a DSL. - In the paper, the single-step transition _function_ is defined; it is a partial function on machine state. Instead of this, I define the transition _relation_ between two machine states. - The paper has instruction decoding also; I don’t need instruction decoding because I define the state transition as a relation. My machine specification is simpler because of this. - The paper uses a monadic framework for code generation; I use unification for code generation, which is simpler. QUESTIONS ABOUT THE GAME == Do you focus on Hungary only? == The game would be international. I plan to use simplified English in the game, and I try to replace words by graphics, at least in the beginning. (For example, I would use the colour green instead of the word ‘green’. Of course, there are lots of cultural differences even if I use pictures instead of words. When I have to make a choice, I would prefer my cultural heritage.) /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \