Computer Science Quick Reference

    The IT field is growing, and it is easy to get lost in the zoo of approaches, frameworks and technologies that loudly declare their “novelty” and “effectiveness”. But the wrapper usually hides the good old ideas, newly "invented" in a different context. As a result, it is not the simplest and most effective that is distributed, but the most advertised implementation. Developers do not have time to carefully make a choice due to a constant lack of time, and managers choose the most common to reduce the risks when searching for developers.


    For myself, I try to reduce the term or technology used in the industry to a simple definition or illustrative example. I offer a guide that is very concise, and therefore incomplete and not intended to be accurate.


    Type is what the computer can talk about. To reason in the sense of habitual human or formal logic, that is, according to the rules to build some conclusions from the initial premises. The good news is that the computer does this automatically. There are different type systems: some eliminate a certain type of error, such as type mismatch, resource leak (Rust Borrow Checking); others automatically generate an implementation (Haskell Type Class, Scala & Rust Trait). When types are easily perceived by humans, they serve as documentation. Strong type systems can do more work for you than weak ones. And static type processing will do this work earlier, at compilation, and not later, at execution, as dynamic.


    A class in OOP is one of the type systems that allows you to talk about the internal structure, which fields and methods are inside. Analogs: record, tuple, type-product.


    OOP inheritance mixes at least 4 ideas that should be implemented in separate ways:


    1. Data inheritance, pretty useless after they are wrapped in getter / setter and turned into methods with inheritance of implementation. An example of transparent wrapping is Elm Records and Haskell Records.
    2. Inheritance of implementation for reuse, it is recommended to replace with delegation.
    3. Interface inheritance (Ad hoc polymorphism) overloads the method, that is, it allows one name to get a different implementation for each type. Analogs: Java Interface, Scala & Rust Trait, Haskell Type Class; algebra as a data type and a set of operations on this type.
    4. Type aggregation is similar to Java Enum, Scala Case Class, Elm & Haskell Algebraic Data Type, type-sum.

    Pattern Matching deconstructs an algebraic type-sum or type-product, that is, it is the inverse of the constructor operation.


    An object in OOP is a closure , where free variables are fields, preferably private.


    OOP is a popular brand that has historically developed, but not a unique set of ideas without a single central core.


    Polymorphism is different .


    Type , interface - type-product, consisting mainly of functions.


    A design pattern is an informal implementation of an idea outside of a programming language, since this language does not support the necessary level of abstraction. In another, higher-level language, it is possible to implement a template using the language.


    Visitor is a design pattern that implements Pattern Matching.


    Builder is a design pattern that implements a higher-order function that takes parts and delivers a product.


    Dependency Injection is a design pattern that implements a higher-order function that accepts dependencies and produces a product. Isomorphic to the Builder pattern, adjusted for the fact that dependencies are usually functions.


    Client Web development is a demanded historically developed, but not unique set of ideas based on the exclusive position of JavaScript.


    MVC , MVP , MVVC - a pure function and an abstract machine for processing external events.


    Event Loop (Node.js, Rust tokio) is an abstract machine for processing external events.


    Programming is the engineering science of code composition.


    Category theory is a fundamental theory about the composition of anything.


    Isomorphism is the transformation or replacement of something into something else and vice versa, that is, the essence of isomorphic things is one.


    Refactoring is an isomorphism performed by humans.


    Optimization is an isomorphism performed by a computer.


    A (pure) function - the transformation of one into another is always the same.


    A functor turns one type into another (function on types), so much so that it is possible to optimize the composition of pure functions. For example, a list functor can turn a string type into a list of strings type, and a number type into a list of numbers type. We apply the function " length " to each element of the list of strings and get a list of numbers. Add 1 to each element of the list of numbers and get a new list of numbers. And you can replace (manually refactor or automatically optimize) a couple of passes through lists with one composite one, which will find the length of the line and immediately add 1, but most importantly, the intermediate list will disappear.


    The monad turns one type into another, so much so that you can combine functions with a side effect. For example, the “ wait ”monad( Future , Promice ) has the side effect of waiting for the completion of a long operation and converts the type “ byte array ” to the type “ wait for byte array ” and the type “ confirmation ” to the type “ wait for confirmation ”. We pass the file name to the read function and wait for an array of bytes from the disk. Then we pass the received byte array to the send function over the network and wait for the client to confirm receipt. And you can replace a couple of expectations with one compound (combinator (>> =) , bind ,), which will first wait for an array of bytes from the disk, and then wait for confirmation from the client over the network, but most importantly, the explicit intermediate wait will disappear, allowing the runtime to do other useful things at this time.


    Duality - turned inside out also works. For example, since the type-sum is dual to the type-product, it follows that a function that accepts apples or pears (type-sum) can be replaced by a pair (type-product) of functions: one says what to do with apples, and the other - what's with the pears.


    Variation says that turned inside out works directly (covariance) or inverted (contravariance). For example, the function that eats the type of apples or pears can be fed apples, but it is impossible to type apples or pears or peaches because it chokes on peaches. A more omnivorous function is more difficult to create and fewer. A larger argument - fewer functions with such an argument - this is the "works in an inverted way", that is, the function is contravariant with respect to the argument. But according to the result, the function is covariant.


    Calculations can be made even on pebbles .



    Quantum computing does not work with bits, but with qubits. For example, instead of balls in the Marble adding machine, you can throw the Schrödinger Cats. For example, a pair of cats will give 4 options: both alive, the first alive, the second alive, no survivors. As a result, for one start of the machine we get the sum of all possible numbers. The only problem is how to turn the Schrodinger Cats at the bottom of the car into ordinary cats, useful in the household.


    Dependent types - work with types and code optimizations in the same way (Pattern Matching and calculations) as with values. Dependent types allow you to transfer work with computable templates and even mathematics to the computer. For example, you can specify that the type is “set of elements”, when there are no more than 64 elements, you can replace it with the u64 type, which will fit in the register. Or the compiler can make sure that the sizes of the added vectors are the same.


    Additions and corrections are accepted.


    Also popular now: