Foundations of Computing

Preface

🗣️

Computer science is no more about computers than astronomy is about telescopes.
—
Edsger Dijkstra

Today computing is really important and whatever reason you want to learn it Welcome!

Learning ethics

Introduction

What is Computing?

Our approach is to define things and then build a castle. We define Computing as the creation, and use of computers [4]. Informally, we define a computer as a programmable machine usually electronic that can give outputs, retrieve, and process data —insights and information. In the theory of computation, you might learn a formal definition.

But, how can you build a computer? how can you connect with other computers and other humans? what can do computers and what can they not? are they secure? how can you build Artificial Intelligence to be better than humans? They are some questions that different study areas answer, and we encourage you to answer all of them at least in a superficial way.

Those disciplines are Computer Engineering, Computer Science, Cybersecurity, Information Systems, Information Technology, and Software Engineering, Data Science. They are the current Computing areas, but they are not all of them —the future is exciting. They are other fields that use computing, we call those fields Computing+X e.g. BioComputing.

The discipline of Computer science is the systematic study of processes (how-to knowledge) and their derived systems —software— that describe and transform a domain of discourse -information and data-: their theory, analysis, design, delivery, efficiency, implementation, and application. Sometimes wrongly Computer science is equally equated with all Computing, but the former is more theoretical focus than other computing disciplines —Software engineering, Computer engineering, or Cybersecurity, …

A 1995 U.S. government “blue book” defines “Computer science” like this: “The systematic study of computing systems and computation. The body of knowledge resulting from this discipline contains theories for understanding computing systems and methods; design methodology, algorithms, and tools; methods for the testing of concepts; methods of analysis and verification; and knowledge representation and implementation.” So, Computer science has two approaches Mathematics —logic— and Engineering. Interesting noting that Mathematics changes of course, but engineering changes a lot more.

TODO: Computational thinking by Stephen Wolfram (2016).

Why does Computing matter to you?

Money —Maybe you want to learn how to build a Killer app or work in Big Tech Companies.

Funny —when you understand what happened.

Power —IA is coming up and Cybersecurity is really important.

Motives For Writing Free Software - GNU Project - Free Software Foundation. (2022, December 27). Retrieved from https://www.gnu.org/philosophy/fs-motives.html

Research

If you want to learn State-of-art, you have to learn from the best people, ACM and IEEE are the institutions you must read.

Ecosystem

Oh maybe you don’t know but Computing has a lot of work in different fields, industries, and roles.

Learning path

Story

If you want to know more about Computing story, then visit

🪕Computing social context

Milestones in computer architecture

The history of hardware can be divided into:

the period of mechanical machines (before 1930)
- Pascaline simulator

the period of electronic computers (1930–1950)

and the period that includes the five modern computer generations.

Desktop Computer.

Smartphones.

Cloud (1960-)

Quantum computer (1980-)

Desktop Quantum Computer (?)

FAQ

What is the difference between a calculator and a computer?

Exercises

An easy homework is to search for whatever field you like, and see if Computing is there.

Recurrent concepts

When you advance in your career, some concepts appear again and again, sometimes with different names and more rigorously —depending on your interests, but they are transversal to all computing —Knowledge, Science, and Human Life too!

Formal and conceptual models

💡

A model is an experimental tool that provides insights, helps us predict future outcomes, or guides us in designing systems.

Natural language is almost always ambiguous, you need a somehow unambiguous; that somehow is the formal languages and conceptual models. They unambiguously formalize, characterize, visualize, and think about a domain, idea, or problem.

But, you should not abuse formalization with you are talking with others. You speak to humans!

Indeed, conversion between natural language and formal languages is an open problem in Artificial Intelligence. The science is to find exciting Patterns —formal languages and models. Models can be:

Explanatory. These models help in explaining the underlying reasons or processes within a system.

Predictive. These models forecast future states or outcomes based on a set of input variables.

Prescriptive. These models recommend actions to achieve desired outcomes.

Simulation. These models mimic the behavior of a system to understand its functioning, behavior, or to make predictions.

Conceptual. These are representations of abstract ideas or systems, designed to understand and explain certain phenomena.

Can you tell me formal language and conceptual model examples? Some of those are optimization, statistical, and simulation.

Not everything is a problem, sometimes we should think to model with substantives and verbs. Roughly speaking, modeling a domain is harder than applying a procedure.

We have the following problem

A father is 27 years older than his son. Ten years ago he was twice as old
as his son. How old is the father?

What is the best model? It is an algebraic problem, so you must find an algebraic model where we have an associated procedure such that given a model it find the values of variables.

Model.

father: father’s age in natural numbers.

son: son’s age in natural numbers.

father=27+son\\ father-10=2(son-10)

Procedure.

It is a Linear Algebra problem, so you transform the problem into the standard form $Ax=b$ and you apply some solver in order to find $x$ and we’ve done.

Some people could think this is an easy problem, however, it illustrates the idea that applying a procedure is easy, especially since we have computers, but a find good model is harder. “What is a good model?” and “How can you find them?” are open questions, but when you study somehow you are learning how to do it since you’re learning patterns.

You should know that not everything is a problem, but a domain since there are things and transformations of things.

We have the following domain extracted from [14]

“marriage, a legally and socially sanctioned union, usually between a man and a woman, that is regulated by laws, rules, customs, beliefs, and attitudes that prescribe the rights and duties of the partners and accords status to their offspring (if any).”

What is the best model? Suppose you must express the relations and types of marriage to remove ambiguity for humans. This is not a mathematical problem, but somehow we have to represent our ideas. For this kind of problem, people invent diagrams —ER diagrams, UML, graphs, and so on.

Model. Draw a mindmap that expresses marriage but using a language https://plantuml.com/mindmap-diagram.

We recommend the essay [8].

Concept drift

Abstraction

Abstraction is the process of extracting the essential features of objects, ignoring the superfluous details [Booch]. We extract the features from a specification, problem, or domain. Sometimes, abstraction is a process where you transform informal ideas into more formal ones. TODO: Generalization.

It is a recursive definition. Since we can abstract objects over another abstract object. Indeed, some people (eg. Plato) have thought the real world is the world of ideas because they are immutable, universal, and more general, they think of statements like “the more abstract, the better”. You can read more by searching Theory of forms.

graph TD
  AbstractObject1 --> Object1
  AbstractObject1 --> Object2
  AbstractObject1 --> Object3
  AbstractObject2 --> Object4
  AbstractObject2 --> Object5
  AbstractObject2 --> Object6
  AbstractObject3 --> AbstractObject1
  AbstractObject3 --> AbstractObject2
  AbstractObject3 --> AbstractObject4[...]
  AbstractObject5[...] --> AbstractObject3
  AbstractObject4 --> ...
  AbstractObject5[...] --> AbstractObject6[...]
  AbstractObjectN[?] --> AbstractObject5

What is essential and what is not? It depends on what model you want. You have to consider what layer you’re building, who are your users, and what people, technology, and knowledge available you depend on.

TODO: metaphors.

Since a box is a useful model to understand models, we explain abstraction layers with boxes.

You can build boxes but you depend on other black boxes and you serve another box, you only know boxes that you benefit from them by their interfaces. We work in different abstraction layers. We are not talking about Graphical User interfaces, we are talking about protocols and how can you can benefit from interfaces, and build good interfaces and protocols.

What the heck these guys are talking about?

Think about a university: what services do they offer you? and sincerely, do you want to know every internal aspect of how they work? Of course, no. Some systems and parts of the system are interesting and others no.

Indeed, understanding each black box and these sub-boxes takes a lot of time since when you’re studying or researching takes time —you are transforming Black boxes into White boxes.

Ok, but why do we have to use abstraction and abstraction layers? There are two answers. In the economy, humans divide their work, we specialize in layers since understanding and working with each one is hard. And latter reason is that we manage better general system complexity with layers —the knowledge.

If some people say something ambiguous, look up computer science papers about it. They have to formalize it.

Choosing the right abstraction or representation —Encoding and Decoding.

The most exciting activity upon abstraction is not working black box interfaces, it is writing or drawing your own model in somehow representation. Every problem you have had or you will have, you can dissolve easily when you chose the right model —when your abstraction works and excels.

Learning Computing (or other sciences) is understanding useful models, and how to adapt to your domain. Why?

We say some strings such as “10”, “A” or “1010”, they are in some representation with proper rules. We can apply some encoding in order to change their representation.

encode(string)=new encoding string.

decode(new encoding string)=string.

Now, encode(”39”)=”100111” where “39” follows the decimal representation and “100111” follows the binary representation. Mathematicians write like $39_{10}=100111_2$ .

If you build a digital computer and choose the decimal representation, you’re going to have a lot of issues with electricity and other aspects. For that reason, Claude Shannon and others choose binary in digital circuits because it is better than decimal representation.

We are warning you, some “encode” and “decode” functions check that property $f(g(x))=x$ , but others no since they have noise or remove superfluous relevance.

You’ve read representations, but which is the most abstract thing upon thinking of natural numbers? Are they isomorphic relations?

Types and relations

TODO: Category theory

Type theory.

Types. The type of a type is a type. An object is synonymous with objects.

Objects.

Classes.

The relation is the process to connect terms —objects or things.

You can find relations such as Association, Use, Composition, and Inherit.

“Association” is a relationship in which two terms collaborate publicly on a lasting basis. Indeed, humans have associative memories, our mind works as a web, and yes as in the WWW, no happened by causality.

“Use” is a relationship in which two terms collaborate, either publicly or privately, on a temporary basis.

“Composition” is a relationship in which two terms collaborate privately on a lasting basis.

“Inherit” is a relationship in which a term transmits its properties into another term.

But the law of leaky abstractions appears

The Law of Leaky Abstractions. (2018, October 05). Retrieved from https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-abstractions

Reuse, reduction, and protocols

“Reusing” means the capacity of a box to respond in different contexts. Sometimes you want the most general solution ever seen, sometimes you don’t. Not every reuse is a reduction, but every reduction is a reuse.

Working black box interfaces is useful when you have to reuse some boxes since they have some representation, you have to adapt your representation to their proper following their protocol. Other times, we choose a representation since it solves faster the problem or it is a more general solution. You are reducing your problem to another one and reusing black boxes.

Don’t reinvent the wheel (black boxes) unless you have good reasons. Good reasons are learning, security, and efficiency. Follow Standards is essential.

Configuration is another way to reduce your problem. eg. you are deploying a web application, are you going to write another web server such as Apache? No, you are going to configure Apache or something like that.

Suppose you have a problem the sort a list of strings and you know have to sort numbers with a function $sort(numbers)$ , how can you reduce your problem into sorting numbers?

When you build boxes, you must consider boxes and how general your problem is.

Effectiveness

Measurement resources and optimizing them. Resources are time, money, cost, people, space, and computational power, in order to achieve goals, and habits.

But we have to consider their consequences and tradeoffs.

Effectiveness, Efficacy, Efficiency

Management and Economy

Every Agent Action must deal with managing resources.

Space

In computing, space is about locality, measurement, and proximity.

Time

In computing, time is on order events, measurement of them, and, of course, optimizing the time.

Consequences and tradeoffs

We live in an optimization world with functions multi objectives —this fact is especially relevant in Artificial Intelligence. Informally, it means functions have trade-offs between two or more conflicting objectives, and when it is not clear what to choose after optimization, you use some apriori criteria assuming the consequences —heuristics.

Another way to think about that statement is to think that you are optimizing your life, but sometimes two or more objectives are in conflict —human abilities and human limitations, technology capabilities, algorithmic, task, social, aesthetic, economic, legal, and evolution constraints.

Arrow’s theorem

Franssen, Maarten, et al. "Philosophy of Technology." 20 Feb. 2009, plato.stanford.edu/entries/technology.

Evolution

A fact is that Human Systems change constantly. We consider this when you build systems such that your system can support changes with good models (design).

Complexity and simplicity

Complexity is the quality of being complicated, difficult, or intricate [6].

It sounds a little informal. but you might explore some rigorous definitions depending on your interest area.

Simplicity is contrary to complexity, so we can understand complexity as a relation.

What minimum model, system, or algorithm describes the domain? When the description is minimal is “the inherent complexity” (the optimal), when it is simpler an incorrect one (or informally a dump one), and when it is more complex “the invented complexity”, “baroque description” or “rococo description”. You must search for the simplest models, systems, writings, ideas, and algorithms although it is harder. When we have more resources, we tend to do complex things.

Why do you search the simplicity? TODO: Simplicity.

Areas that teach about Complexity and deal thereof are

Complicated Cognitive model. A complicated cognitive model is one whose complexity exceeds your current intellectual capacity. TODO: Communication.

Complicated models (software complexity). A complicated model or complicated software is one whose complexity exceeds human intellectual capacity [Booch]. When the author refers to “the human intellectual capacity” he says “no average experimented trained human can understand the model”—software complexity.

Philosophical and Science Complexity. This is on Occam's razor or principle of parsimony, but not about cognitive understanding. Indeed, a theory can be hard to understand but not simple, and inversely, a theory can be simple but hard to understand. Kolmogorov Complexity is an objective way to measure complexity or simplicity.

Computational Complexity. It refers to the resources required to run an algorithm. They are resources in execution time.

Kolmogorov Complexity. Informally, it is the description’s length in precise language or information content in a precise language. So, we apply an ideal data compressor to a description, we get the simplest description.

Complex system. It is one whose components interact in multiple ways, and follow rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergency [7]. What is a system? What do those words mean? Systems.

Coherence and integrity

Models must be correct, robust, and reliable.

Security and safety

Models must respond appropriately to and defend against inappropriate and unexpected requests. Since security is a wide topic when you are ready you can read about Intelligence.

There are four key threats to consider.

Spam.

Bugs o the more modern concept defect.

Denials of service.

Malicious software or malware. This includes viruses, worms, Trojan horses, and spyware.

User experience and communication

We do things for ourselves or others. Receivers, clients, or users expect ideas, software, and products that won’t be a pain of the ass to understand. It applies to how we write mathematics well, how we write code, how we write, and how we express ourselves to others.

Good taste is something that you learn by reading people better than you, understanding the underlying patterns, and doing mistakes.

Data model

data query language (DQL), a data definition language (DDL), a data control language (DCL), and a data manipulation language

Entity–relationship model

RFD

Object–role modeling

Object-oriented programming

Exercises

If Uber is encoded as VAFQ, how would COMMOPS be encoded?

U (21) -> V (22) : +1

b (2) -> A (1) : -1

e (5) -> F (6) : +1

r (18) -> Q (17) : -1

Summary

We explain before what is an abstraction, but how do we abstract abstraction? We present a model of abstraction based on type theory and UML.

Notes.

“Mathematical abstraction” is another for “Type”.

“Data model” is another word for “Abstract Data Type”.

FAQ

How can I be better in X efficiently?

TODO: Demming cycle?

start from X foundations
while you want or have
    read or listen knowledge
    ponder
    practice

Correctness proof. TODO.

Patterns

💡

The key to understanding complicated things is knowing what not to look at, what not to compute, and what not to think [9].

A pattern is a regularity in data. Somehow we use Mathematics (Abstraction and proof), Units, and Algorithms to find out patterns that lives in a specific domain.

In mathematics and logic, the domain of discourse or domain is a set of terms over which certain variables of interest in some treatment may range. But, you can find similar definitions in sociolinguistics, so informally the domain is the set of features or conventions of language use that are specific to the context in which communication occurs [10]. Some elements of the domain are theoretical framework, organizational idiosyncrasy, personal idiosyncrasy, culture (common knowledge) and different process instances. Other names are cognitive discourse domain, discourse world, knowledge map, and knowledge base.

Databases, datasets and software are reduced domains, they take an aspect of reality. Some people expect rev

Special patterns for computing

Model of computation. Algorithms. Process. Programs. algorithmic thinking?

Algorithms are knowledge form, indeed how-to knowledge but other areas of mathematics are declarative. Since we are given useful definitions, we present you with an informal definition of an algorithm and related terms.

“Algorithm” is a term with well-defined rules or instructions in a finite number of steps. We know from our model terms have different representations as in the Algorithm case.

Algorithms are something unuseful if you can not execute them in real-time since each algorithm that you can write should be executable in a computer, we need another concept, we need programs.

A computer program is an algorithm in a particular language, so it can be executed by a computer. When your program is executed, your program becomes a process.

But, algorithms are not systems; not every software solves a problem but models a domain.

Formal definitions are given in Dictionary.

Iterative

Iterative is a pattern where iterations happen one other another. After day follows the night after night follows the day. If your language support Tail recursion optimization, loops are not needed.

graph LR
  Day --> Night
  Night --> Day

Recurrence

Recurrence is a pattern that probably and eventually repeats. Sometimes rains and sometimes doesn't, it is a recurrent event as errors in systems sometimes happen and sometimes don’t.

Recursivity

Recursivity is a term or type that is definite by itself. Note that recursivity is a special case of a definition. Even though we don’t define recursivity with base cases, it must have base cases in order to keep away infinite recursivity.

Examples

GNU is “GNU is Not Unix”,

PHP is “PHP: Hypertext Preprocessor”,

self-reference (I am Charlie),

self-modification,

$S\to (S)|\epsilon$ ,

fractals,

architecture,

the never-ending story,

directories,

memory,

autoregressive (AR) model,

ouroboros,

recurrence relations,

$Fib(n)=Fib(n-1)+Fib(n-2),Fib(0)=0,Fib(1)=1$ ,

Gamma function (Yes, recursivity can be continuous),

Mise en abyme,

mathematical induction (?),

infinite zoom art (?)

TODO: Michael C. Corballis The Recursive Mind: The Origins of Human Language Thought and Civilization. 2007

…

Simple patterns

Line

2 points

Forms, timeline, waterfall, sequence, sequential sentences, lineal recursivity

Triangle

3 points

Tree, table, alternative sentences, multiple recursivities

Circle

A point and a radius

Cells, maps, loops, cycles, graphs, iterative sequences, mutual recursion

Knowledge

We use knowledge in order to solve human needs, indeed learning is somehow a human need.

Deming cycle.

Information.

Data.

Information Ethics. Flourishing Ethics.

Logic

🗣️Logic

Science

👩🏾‍🔬Research, research methodology, science

Standards, documentation, and specification

A principle in every communication is following the standards, protocols, community, and specifications. Otherwise, the communication fails. However, if you have good reasons, should not do it.

TODO: Compatibility.

If you don’t follow the programming language syntax, your program doesn’t work. If you speak English in a Spanish country, your listener could not understand you. If you write your internet protocol, probably nobody uses it. So, follow the standards and read the documentation.

TODO: Diseñas y publicas una API es que esta es un contrato. Una responsabilidad y un acuerdo tácito con los desarrolladores que invertirán tiempo y dinero en crear software que la
use, la confianza de su ecosistema, socios y clientes.

Computing as human need

insights, communication, agents, games

TODO: DIKW Pyramid. Economy.

Systems

A system is a component set interacting with each other.

When people speak about Software, they are talking about building systems based on computers, and programming over time. We build systems in order to interact or speak with users, therefore you’re building a language.

Computing is hardware and software where systems are mirrors of a domain but sometimes more like inspiration.

Hardware and software are equivalent —you’re transforming software into hardware every time, but the software is more flexible thereby you get feedback faster in order to learn how to build stuff. So, we’re going to learn computing from a software point-of-view, more concretely from a programming point-of-view.

What is software? how can we build good systems? Learn Software Engineering after.

Simplicity

Any model should be as simple as possible and as complex as needed to answer the expected questions.

Haimes, Y. Y. (2009). On the Complex Definition of Risk: A Systems-Based Approach. Risk Analysis, 29(12), 1647–1654. doi:10.1111/j.1539-6924.200

Cognitive limitations. Miller Number.

Your model has to be correct, but simple too. Bad systems are ones where the invented complexity exists where every change is harder than the previous one, in other words, the marginal utility decreases exponentially. However, you have to consider tradeoffs.

Managing Complexity

Modularity

Although we can build universal functions —universal machines, it doesn’t imply we should. Since our human mind is limited, we prefer modularizing our descriptions since building complicated or messy systems causes big problems. TODO: Telecommunication layers.

Primitive expressions.

Means of combinations.

Means of abstraction.

Encapsulation.

Combination and Interfaces.

Composition and classification.

Abstraction

💡

“The limits of my language mean the limits of my world.” — Ludwig Wittgenstein in Tractatus Logico-Philosophicus.

Computing is a science of abstraction —writing down the right model for thinking about a domain and ignoring superfluous details; thereby, it becomes your good friend since it helps you to understand the world, think about real-world problems, and control things when you have good language for talking about —horses for courses.

You may have the intuition that abstract things are hard to understand, but abstraction doesn’t imply fear and complex things, abstraction implies simplification, deals with the essence of the domain, and ignore details whose effect is minimal or nonexistent.

But, we live in a world with constraints, consequences, and tradeoffs —computer capabilities, time, and other means; therefore finding a good abstraction can be quite difficult. Learning computing is learning a framework to find good abstractions and good languages. Nevertheless, building a computer or program that thinks for us or models the real world thereof remains a challenge.

What is the framework to find good abstractions and good languages?

Informally, you can think of the framework as a set of “tricks”. However, the framework is Mathematics focuses on computation, automation, and information. Indeed, the best languages are like algebras and the best software is like pile languages rather than a decomposition of the problems into parts.

Perfomance. https://www.youtube.com/watch?v=B2YrMZOO9d0

Codification: choosing the right abstraction

Domain of discourse

Abstract data type

Language, Hierarchy, and problem-solving mindset

When you write a description (e.g. algorithms, systems, mathematics), instead of seeing the world from a problem-solving mindset, should see yourself as a language builder. If you have the right language, you can problems easier and think of breathtaking places —higher intellectual places.

Diophantine equations were a long time mysterious insofar as we didn’t have a precise definition of algorithms we weren’t able to give a solution using a procedure (but not by brute force) until Turing, Church, and others wrote a language to think of algorithms, information, and machines. Nowadays, we have computers, the Internet, and the famous statement $NP=P$ as their legacy or work derivative.

"Rights and privileges" of first-class.

Language and formal languages.

Regular expressions.

Conventional interfaces, allow things to glue together. Closure principle.

Break down the world.

Programming

Pieces of Advice

Don’t your code until you make sure your model would be correct and simple.

Don’t search for solutions or help until you’re tried by our own 30 minutes.

Read first the documentation, after googling it, and only then ask.

Flowcharts or activity diagrams are not the modern way to write a program —Management People invent them for industrial processes. Von Neumann and others in the 1950s used them to express programs because they don’t have high-level languages —a better representation.

What language should you use depends on your level in the abstraction hierarchy and what is your domain.

Notebooks and REPL

Memory managment

Pointers

I have a friend, Darv. Darv moves often. Often enough that many of our mutual friends do not have his current address. But I always have Darv’s current address, so that if any of our mutual
friends want to know where Darv lives, they ask me. That is, I am a pointer to Darv.

Thomas Cormen. https://www.quora.com/What-should-I-learn-to-understand-pointers-Should-I-learn-something-like-how-memory-works-or-anything-similar-Because-Im-finding-it-hard-to-understand-it-Every-tutorial-I-saw-only-mention-the-basics-of-pointers-I

Heap

https://rust-unofficial.github.io/too-many-lists/index.html

https://www.cs.brandeis.edu/~cs146a/rust/doc-02-21-2015/book/README.html

Storage managment.

How can you deal with filesystems?

IPC

Functional programming

Some key ideas in functional programming are you don’t worry about the state, you need to know Lambda calculus.

$(\lambda(x) x))$ x is a variable.

Streaming and recursion.

Substitution model.

Functional programming implies no side effects, so there are no assignments, thus you can build parallel algorithms quickly —there is no time, so you don’t have any synchronization.

We have boxes, but what is the ultimate box? Lambda is the ultimate glue.

Imperative Programming

Logical control flow

Iterative sentence.

Sequential sentence.

Conditional sentences.

Side effect

Can (a==1 && a==2 && a==3) ever evaluate to ‘true’ in JavaScript?
https://twitter.com/PR0GRAMMERHUM0R/status/1661779185117933578/photo/1
Yes, some ways are written here https://twitter.com/wiseaidev/status/1661787402669633545
```
const evalCond = () => {
  let a = {
    value: 1,
    valueOf: function () {
      return this.value++;
    }
  };
  return a == 1 && a == 2 && a == 3;
}

console.log(evalCond())
```

Identity and equality. Mutability and Immutability. Time.

Are objects their positions, their value, or their identifier?

State and Configuration.

Time is important in imperative programming since assignments change the state.

Assignments, frames, environments, and bounds. Scopes. Global.

Turing machine, Von Neumann, Random-Access Machine. We do not discuss how a real computer works here since you must understand high-level concepts, you’ll learn more thereof in Computer Organization and Architecture.

You have to think of programming mechanically.

Free variables and Bound variables.

Identity and equality.

Side-effects.

An environment is a place where we associate variables and values. Variables are bound in an environment.

A frame is a particular time of environment.

Pointer and reference. by name and by value.

Variables have a memory address, so you could declare a variable to get a memory address. A pointer is a variable that holds the memory address of another variable.

int i = 3; // int is a type and it means integer
int* pointer = &i; // int* is a type and it means pointer
// & is operator to get memory address
// So it the pointer stores the memory address of i

Reference. Informally, you are changing the variable’s name or you are making aliases.

int i = 3;
int& reference = i; // int&  is a type and it means reference
// i=3, reference=3
i++;
// i=4, reference=4
reference++;
// i=5, reference=5

There is sharing here, sometimes is exactly what we defined, but inadvertent sharing is the source of most of the bugs that occur in programs. Composite structures are the most common way to facilitate unanticipated interactions between objects. So, you must careful with that.

Ignore types for a moment, suppose we have the following code

t = [1,2,3]
y = t
y[0] = -5

Now, what is the $t$ ’s value?

When we declare primitive variables the machine by default copy the value into the new variable.

int i = 3;
int j = i;
i++;
// i=4, j=3
j = 6;
// i=4, j=6

But, things come up interesting with functions.

unsigned long x = 4;

void func1(unsigned long& val) {
     val = 5;
}
func1(x);
// x = 5

unsigned long x = 4;

void func1(unsigned long val) {
     val = 5;
}
func1(x);
// x = 4

unsigned long x = 4;

void func1(unsigned long* pointer) {
     *pointer = 5; 
    // when you apply to a pointer the operator *
    // it means 
}
func1(x);
// x = 5

comp.lang.c Frequently Asked Questions. (2008, January 07). Retrieved from https://c-faq.com

Theseus problem

When you introduce assignments, you introduce the Thesus problem, and time becomes a headache. —What do identity, reference, and equality mean?

array=[1,2,3]
array[1] = array
// ?

Identity, reference, and equality in JavaScript

// x and y are in the same memory position and have the same type.
equality(x, y) = (x,y) => x === y

// x and y have exactly the same elements
identity = (x,y) => {
      if (
            (typeof x != typeof y) ||
            (typeof x != "object" && typeof y != "object" && x !== y) ||
            (typeof x == "object" && typeof y == "object" && Object.keys(x).length !== Object.keys(y).length)
        )
            return false;
      if (typeof x != "object" && typeof y != "object" && x === y) return true;
      for(const key of Object.keys(x)) {
        if(!(key in y)  || !identity(x[key], y[key])) 
             return false;
      }
      return true;
}

Example with Ship of Theseus. ? proposition returns the proposition value.

// myShip says Thesus
const myShip = {'location': 'greek', 'owner': 'Thesus', 'parts': ['mast', 'foremast']};
// bossShip says the tribulation
const bossShip = myShip;
// thesusShip says Plato
const thesusShip = myShip;

// They have the same memory position but with different identifier, 
// so we associate different names to values.

// CASE f(T, T)=T
// Thesus changes all parts of his ship
myShip.parts = ['new mast', 'new foremast']

// Plato asks "Theseus's Ship is identical that Theseus's ship with new parts".
? identity(myShip, thesusShip)
// true

// Plato asks "Theseus's Ship is equal that Theseus's ship with new parts".
? myShip === thesusShip
// true


// CASE f(F, F)=T
// Ship with old parts.
const oldThesusShip = {'location': 'greek', 'owner': 'Thesus', 'parts': ['mast', 'foremast']};;
? identity(oldThesusShip, thesusShip)
// false

? myShip === oldThesusShip
// false

// CASE f(T, F)=T
const newThesusShip = {'location': 'greek', 'owner': 'Thesus', 'parts': ['new mast', 'new foremast']};
? identity(newThesusShip, thesusShip)
// true

? myShip === newThesusShip
// false

// CASE f(F, T)=F
// This case cannot be exist.

// Maybe you are thinking something as
let x = 5;
let y = x;
y++

// But it doesn't work. Numbers are immutables.

? identity(x, y)
// false

? x === y
// false

Structured Programming

Structured programming is a language

Defensive programming

Composition vs piping (streaming)

Composition is the usual function notion in mathematics $f .g$

Pipes (or streams) are a continuous flow of data $g|f$ . Roughly a flow is a list.

Exceptions

Process Programming

Objects and classes

Hierarchy

Composition and inherently

Modules

Concurrecy

Memory managment and memory safety risks

https://media.defense.gov/2022/Nov/10/2003112742/-1/-1/0/CSI_SOFTWARE_MEMORY_SAFETY.PDF

Traversal software features

Communication between processes

We won’t see the whole power of the combined processes since we have different choices —you can explore more in Operating Systems. Instead of combining your functions, you can think combining processes as sharing information from different machines, different languages, and different teams. In Unix, we have Bash which supports pipelines. Suppose you want to search all files that match X*X and remove it, then you

time touch X{1..5}X | ls | grep -E "X*X" | xargs rm
# touch X{1..5}X  0.00s user 0.00s system 74% cpu 0.002 total
# ls  0.00s user 0.00s system 89% cpu 0.002 total
# grep -E "X*X"  0.00s user 0.00s system 91% cpu 0.004 total
# xargs rm  0.00s user 0.00s system 46% cpu 0.005 total

Pipelines work Parallel.

sleep 5 | echo "Hello World"
# "Hello World"
# ...

"Bash Reference Manual." 24 Jan. 2023, www.gnu.org/software/bash/manual/bash.html#Pipelines.

"What is a simple explanation for how pipes work in Bash?" Stack Overflow, 24 Jan. 2023, stackoverflow.com/questions/9834086/what-is-a-simple-explanation-for-how-pipes-work-in-bash.

IO principle

In the context of memory hierarchy in computer systems, "I/O" (Input/Output) refers to all operations and devices that are not directly part of the main memory (RAM) or higher levels in the hierarchy, such as cache memory. This includes:

Secondary Storage Devices: Such as hard disk drives (HDD), solid-state drives (SSD), optical drives (CD, DVD), and removable storage devices (USB drives, SD cards).

Input Peripherals: Such as keyboards, mice, scanners, and microphones.

Output Peripherals: Such as monitors, printers, and speakers.

Network Devices: Network cards, modems, routers, etc.

Other External Devices: Any other device that connects to the system and requires an I/O interface to operate.

Principle. Separate your IO calls and your model into two different pieces.

Why? TODO.

Examples are https://hydra.cc/

Coroutine

Threads

https://lerner.co.il/2020/05/08/making-sense-of-generators-coroutines-and-yield-from-in-python/

https://peps.python.org/pep-0525/

Errors

def f(i=4):
    try:
        if i >= 3:
           raise Exception("Some useful message")
        return i
    except:
        return f(i-1)
    
f() # 2

Generator

while True
   yield X

while True
   yield timeout(500)

Check data and get data

XML

Buffering and flushing

https://stackoverflow.com/questions/47735850/what-exactly-is-flushing

Selection and decomposition

We perform different actions depending on a value and retrieve components of a value (transformation).

Switch and if sentences

if (predicate)
   ... // action
if (another predicate)
   ... // another action

Fibonacci example

fib(n):
  if (n  <= 1)
    return n
  return fib(n-1)+fib(n-2)

Visitor pattern

Fibonacci example

Pattern matching

Pattern matching is a technique to match values against terms and bind variables.

inspect (value) {
  pattern guard : statement
}

Fibonacci example

fib n<=1 : n
fib n : fib(n-1)+fib(n-2)

Code as data

There’s no difference between data and code. Your code is data, so you can make dynamic functions. Lambda.

Closure property

Operations are closed

Curry and closures

function counter(init) {
   count = init;
   return () => count++; // A closure function that is curryfing. 
}

Why works? Functions are first citizenships, you are making function dynamic functions with local data.

Batch processing

Async

Big data

No user interaction rather than submit the jobs

Streaming processing

https://stackblitz.com/edit/kuxljq-txprxk

Composition functions.

(filter procedure (map procedure (enumerate data-structure)))

Time

Lazy streaming or on-demand streaming

Delay and force.

Queen problem with streamings

Backtracking search with streamings

Lazy evaluation vs eager evaluation

Normal-order evaluation

Libraries

The imperative way to manipulate streams is "ReactiveX", functional languages such as Haskell can manipulate them but no libraries. [15] 3.5.1 Streams Are Delayed Lists presents streams to find the second prime between 1000 and 10000000000 inclusive in order to computer as faster as traditional computing. We present you the same exercise using ReactiveX —RxJS ≥ 7. The current RxJS version does the operations as delayed, so it doesn’t build the whole range thereby you get a clean, maintainable, and fast procedure.

import { range, skip, filter, take } from 'rxjs';
/* Display the second prime */
range(10000, 10000000000)
  .pipe(filter(is_prime), skip(1), take(1))
  .subscribe(console.log);

/* Display the Sieve Of Eratosthenes */
interval(500).pipe(filter(is_prime)).subscribe(display);

You can memorize as

import { interval, take, map, shareReplay } from 'rxjs';
function memo(stream$) {
  let memo$ = null;
  return () => (memo$ === null ? (memo$ = stream$.pipe(shareReplay())) : memo$);
}

const memo$ = memo(
  interval(2000).pipe(
    map((i) => [i, Math.random()]),
    take(6)
  )
);
memo$().subscribe((x) => console.log('sub A: ', x));
memo$().subscribe((y) => console.log('sub B: ', y));
setTimeout(() => {
  memo$().subscribe((y) => console.log('sub C: ', y));
}, 11000);

Write Fib as Stream

import {generate, take} from "rxjs";

generate({
		initialState: [0,1],
		iterate: state => [state[1], state[0]+state[1]]
	}).pipe(take(5)).subscribe(console.log);

import { interval, scan, map, startWith } from 'rxjs';
 
interval(1000)
	.pipe(scan(([a,b]) => [b,a+b], [0,1]), startWith([0,1]))
	.subscribe(console.log);

Write $S_n=\sqrt{3+\sqrt{S_{n-1}}},S_0=\sqrt{3}$ as stream until $S_k-S_{k-1}<\epsilon$ .
```
import {generate} from "rxjs";

generate({
	initialState: [Infinity,Math.sqrt(3)],
	condition: state => Math.abs(state[1]-state[0]) > Number.EPSILON,
	iterate: state => [state[1], Math.sqrt(3+Math.sqrt(state[1]))]
}).subscribe(console.log);
```

Write Netwon-Rapshon as Stream.

import {generate} from "rxjs";

const netwon_rapshon_recurrence = (fn,dfn) => state => state[1]-fn(state[1])/dfn(state[1]);
const find_root = recurrence => x => generate({
	initialState: [Infinity,x],
	condition: state => Math.abs(state[1]-state[0]) > Number.EPSILON,
	iterate: state => [state[1], recurrence(state)]
});
// Which is the x such that x^2=16?
// We reduce the problem into root finding x^2-16=0,
// then we apply our favorite method.
find_root(netwon_rapshon_recurrence(x => x**2-16, x => 2*x))(16).subscribe(console.log);

User interfaces and deployment

Desktop

GTK

Web

How-to?

W3Schools How TO - Code snippets for HTML, CSS and JavaScript. (2023, January 01). Retrieved from https://www.w3schools.com/howto/default.asp

CSS

https://flukeout.github.io/

Design path

Selectors

https://sipb.mit.edu/iap/webdesign/course_materials/

https://ocw.mit.edu/courses/1-264j-database-internet-and-systems-integration-technologies-fall-2013/pages/lecture-notes-exercises/

Worked examples

Search

[1]

Recursion problems

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if a valid path exists from the vertex source to the vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Formally,

isAValidPath(
    n: NaturalNumber, 
    edges: [[NaturalNumber, NaturalNumber]], 
    source: NaturalNumber, 
    destination: NaturalNumber
): boolean

Examples:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

Find if Path Exists in Graph - LeetCode. (2022, December 19). Retrieved from https://leetcode.com/problems/find-if-path-exists-in-graph

Bad Solution

class Solution {
private:
    bool set[200000];
public:
    bool has(int element) {
        return set[element];
    }
    void insert(int element) {
        set[element] = true;
    }
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        if (source == destination)
            return true;
        if (has(source))
            return false;
        insert(source);
        for(int i=0; i < edges.size(); i++)
            if (
                   edges[i][0] == source && validPath(n, edges, edges[i][1], destination) ||
                   edges[i][1] == source && validPath(n, edges, edges[i][0], destination)
                )
                return true;
        return false;
    }
};

Why is it a bad solution? As edges have a bad representation, so you should transform vectors to another representation that does more sense —such as DFS, BFS, or Disjoint Set Union (DSU). But, we are not doing it, we are using representation such as they are coming.

Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
      if (list1 == nullptr)
            return list2;
      if (list2 == nullptr)
            return list1;
      if (list1->val >= list2->val) {
          list2->next = mergeTwoLists(list1, list2->next);
          return list2;
      }
      return mergeTwoLists(list2, list1);
    }
};

A brief introduction of how computers do the job

Von Neumann Simulator

Metaprogramming

Metaprogramming is a programming technique in which you treat programs as data. In other words, your code is data, so you can reflect on that, modify it, and code that generates code.

Metaprogramming. (2023, January 02). Retrieved from https://cs.lmu.edu/~ray/notes/metaprogramming

Generation

Genetics programming

Compilers

Reflection

Self-modification

Ecosystem

Resources

Git

Libraries, framework, standards. Community.

Emulating machines

Virtual machines

Ventoy

Docker

GitHub Cloud

Editors

Java

Gradle

Maven

Apache Ant

Security

Kill Switch

Build systems or build automation

Fundamental

Name	Tags
Managing Project with Make. O’Reilly
Untitled
Untitled

Linux environment

Make

Cmake

Ninja

https://bazel.build/start/bazel-intro

https://makefiletutorial.com/

https://www.cs.columbia.edu/~jae/3157/

Sed & AWK

Practical VIM

References

https://wiki.nikiv.dev/computer-science/#notes

https://missing.csail.mit.edu/

En espanol:

https://missing-semester-esp.github.io/

Future of computing

https://www.youtube.com/watch?v=EOuGmRXsb4g&ab_channel=MaartenvanSteen

Glossary

Institutes and corporations

⚠️

Use ACM citations about other styles (IEEE, APA, ...)

IEEE

ACM

MIT

Stanford

Cambridge

Berkley

O'Reilly

ANSI

Dr. Dobb's Journal

Oxford

Bell Labs

Springer Science+Business Media

Undergraduate Topics in Computer Science

Addison-Wesley

RAND corporation

FANG

Y-Combinator

Xerox PARC

IBM

Tech Model Railroad Club

Top Secret Rosies

https://sites.google.com/view/amexcompmujeres/recursos?authuser=0

AMEXCOMP

https://www.quora.com/How-does-the-CS-student-culture-differ-between-the-top-4-MIT-Stanford-Berkeley-and-CMU

Fields

https://en.wikipedia.org/wiki/Computer_science#Fields

https://www.youtube.com/watch?v=SzJ46YA_RaA

Computing

https://www.acm.org/binaries/content/assets/education/curricula-recommendations/cc2020.pdf

https://dl.acm.org/ccs

Translations

Name	Computing	Computer science	Computer engineering	Information management	PROGRAMMING	Cybernetics	Software engineering
Spanish	Computacion	Ciencias computacionales	Ingenieria de la computacion	Informatica. Relacionado con humanidades. Admnistracion de la informacion.	Programacion.	Cibernetica	Ingenieria del software
German
Chinese
French
English

Data Processing Industry.

Programming vs Coding?

electronic engineering

Practical Epistemology

Data. Transmittable and storable information by which computer operations are performed

https://www.etymonline.com/word/data

Data is not exactly a plural on Datum.

https://es.wikipedia.org/wiki/Cibernética

Terms for the practitioners of computer science.

computer scientist,

turingineer,

turologist,

flow-charts-man,

applied meta-mathematician,

datology or data science?

and applied epistemologist

Tools

Difference between developing and automatizing

https://www.devtoolsdaily.com/graphql/playground/

References

We order cites from foundational to advance.

freeCodeCamp.org. (2022, December 12). Retrieved from https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/#intermediate-algorithm-scripting

6.001 Athena Locker. (2022, January 06). Retrieved from https://web.mit.edu/6.001

6.100A/B. (2022, December 13). Retrieved from https://sicp-s1.mit.edu/fall22

Curricula Recommendations. (2022, December 19). Retrieved from https://www.acm.org/education/curricula-recommendations

Andrew Butterfield, Gerard Ekembe Ngondi, and Anne Kerr. 2016. A Dictionary of Computer Science (7th. ed.). Oxford University Press, Inc., USA.

Definition of complex. (2022, December 18). Retrieved from https://www.merriam-webster.com/dictionary/complex

What is complex systems science? | Santa Fe Institute. (2022, December 23). Retrieved from https://web.archive.org/web/20220414202627/https://santafe.edu/what-is-complex-systems-science

Analogical Reasoning, Analog Computation and the Computational Hypothesis of Cognitive Science R. I. Damper, Image, Speech and Intelligent Systems Research Group.

Opencourseware, M. (2019, August 22). Lecture 1B: Procedures and Processes; Substitution Model. Youtube. Retrieved from https://www.youtube.com/watch?v=V_7mmwpgJHU&list=PLE18841CABEA24090&index=2&ab_channel=MITOpenCourseWare

What Is a Discourse Domain? (2019, April 14). Retrieved from https://www.thoughtco.com/discourse-domain-language-1690398

Malhotra, V. (2022, December 29). Home. Vedansh Malhotra. Retrieved from https://cs10.org/fa22

John DeNero, J. Y. (2023, January 02). CS 61A Fall 2022. Retrieved from https://cs61a.org

Departmental, C. 6. (2020, June 23). CS61A Su20: HW01 Hailstone (hints video). Youtube. Retrieved from https://www.youtube.com/@cs61adepartmental39/featured

Of Encyclopaedia Britannica, T. E. (2022). Marriage | Definition, History, Types, Customs, Laws, & Facts. Encyclopedia Britannica. Retrieved from https://www.britannica.com/topic/marriage

Structure and Interpretation of Computer Programs, Comparison Edition. (2022, December 28). Retrieved from https://sicp.sourceacademy.org

CS50x 2023. (2023, January 12). Retrieved from https://cs50.harvard.edu/x/2023

Dive Into Python 3. (2023, January 16). Retrieved from https://diveintopython3.net

Wayne, Robert Sedgewick and Kevin. "Introduction to Programming in Java · Computer Science." 8 Mar. 2023, introcs.cs.princeton.edu/java/home.

Association for Computing Machinery (ACM). (2021, August 31). Turing Lecture 2021: Abstractions, Their Algorithms, and Their Compilers. Youtube. Retrieved from https://www.youtube.com/watch?v=ixIlknu7svM&ab_channel=AssociationforComputingMachinery(ACM)

Foundations of Computer Science by Behrouz A. Forouzan

The practice of Programming

The pragmatic programmer

Getting Started Step-By-Step. (2022, November 28). Retrieved from https://json-schema.org/learn/getting-started-step-by-step.html

The career programmer: Guerrilla tactics for an imperfect World

Logic == computation? https://philosophy.stackexchange.com/questions/42352/logic-and-computation-a-philosophical-viewpoint-on-curry-howard-isomorphism

??cs101??

GNU C Language Intro and Reference Manual. https://forums.linuxmint.com/viewtopic.php?t=381284 https://www.docdroid.net/73uNJco/c-pdf

google. (2022, September 28). latexify_py. Retrieved from https://github.com/google/latexify_py

Programming Pearls. Jon Bentley.?

Structure and Interpretation of Computer Programs. Harold Abelson, Gerald Jay Sussman y Julie Sussman.

Algorithms + Data Structures = Programs

C language. K&R.

C++ Stroustrup.

Which book should I choose to get into the Lisp World? (2022, September 25). Retrieved from https://cseducators.stackexchange.com/questions/7478/which-book-should-i-choose-to-get-into-the-lisp-world/7481#7481

norvig. (2022, September 27). pytudes. Retrieved from https://github.com/norvig/pytudes

https://www.youtube.com/playlist?list=PLH2l6uzC4UEW0s7-KewFLBC1D0l6XRfye

https://dl.acm.org/doi/10.1145/1272516.1272529

https://www.informatics-europe.org/images/ECSS/ECSS2015/slides/ECSS2015-Tedre.pdf

https://textbooks.cs.ksu.edu/

CHRISTOPHER STRACHEY of Oxford University, entitled "Is Computing Science?" (1970).

Denning, P. J. (2005). Is computer science science? Communications of the ACM, 48(4), 27. doi:10.1145/1053291.1053309

https://denninginstitute.com/pjd/GP/GP-site/welcome.html

https://fgbueno.es/act/img/sdc2018m.pdf

Encyclopedia of Computer Science, 4th Edition. ISBN: 978-0-470-86412-8

https://plato.stanford.edu/entries/computer-science/

Weiss, E. A., & Corley, H. P. T. (1958). Letters to the editor. Communications of the ACM, 1(4), 5. doi:10.1145/368796.368802

https://www.guillermodeladehesa.com/files/capital_humano_y_crecimiento_economico.pdf

https://guillermodeladehesa.com/files/0006.1450263067.KAIQ5962GFQD5022PIAE8796KYES7779.pdf

https://cpu.land/the-basics

Next steps

Counting repeated characters in a string

https://colab.research.google.com/drive/1u3VIr2VS3hpQjeLO66XbwVJeoqvCoEsZ?usp=sharing

# Python 3+
import collections
collections.Counter(input_string)

# Python 2 or custom results.
{key: string.count(key) for key in set(string)}