Requisites

Resources

Introduction

What is a model of computation?

Algorithm. The sequence of computational steps that transform the input into the output.

input <-> a instance of a problem
...computional steps <-> a computer algorithm <-> transform input to output <-> a program solves a specific problem <-> a task solves an instance of a problem
output

About Software

$computer \text{ } algorithm = program =abstract\text{ } code$ and $program \sube software$

Abstracts are important, they define the granularity of the algorithm and the elements that achieve it. For example, an algorithm with English code is not equal to a hardware design. However, the specific precise steps of the elements are given.

The software can be hardware, and inversely.

Church–Turing thesis.

Another difference between pseudocode and real code
is that pseudocode is not typically concerned with issues of software engineering.

Issues of data abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more concisely.

Why do models of computation matter to you?

Research

Ecosystem

Standards, jobs, industry, roles, …

Story

FAQ

Worked examples

Notation

Prefix

Suffix

Infix

Underlying Language Processor

Harvard architecture, von Neumann architecture

Interpreter.

Compiler.

REPL.

Notebook.

Stack Machine

Java Virtual Machine,

Register machine

Counter machine

Pointer machine

Random-access machine

Random-access stored-program machine

References

Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertl, M. Anton (2005-06-11). "Virtual Machine Showdown: Stack Versus Registers" (PDF). Retrieved 2009-12-22.

Category theory

Calculus

SKI combinator calculus

Lambda calculus

Horn clauses.

Imperative

OOP

Simula vs Smalltalk

Streaming

AWK and PERL

Functional programming

Lambda calculus

El problema del desplazamiento del paradigma.

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

https://alexott.net/en/fp/books/

https://purelyfunctional.tv/functional-programming-languages/

https://betterprogramming.pub/modern-languages-suck-ad21cbc8a57c

https://www.youtube.com/watch?v=-J_xL4IGhJA

https://www.expressionsofchange.org/dont-say-homoiconic/

Foundations.

1. Lambda Calculus
   1. https://plato.stanford.edu/entries/lambda-calculus/

2. What is an Efficient Implementation of the $\lambda$- calculus? https://www.cs.cmu.edu/~rwh/papers/nsf-pfl/excerpt.pdf

3. Category theory
   1. https://plato.stanford.edu/entries/category-theory/

4. Lisp
   1. Racket.
   2. Schema.

5. Haskell.

6. Scala.

7. Elm.

8. Erlang.
   1. Ruby.
   2. Elixir.
   3. Fenix.

   https://www.youtube.com/watch?v=idUgQ87-7kA

   1. https://www.wired.com/2015/09/whatsapp-serves-900-million-users-50-engineers/.

   https://news.ycombinator.com/item?id=21111662

9. Clojure.

10. Curry.

11. Servidor en linea.

Notes

Worked examples

1. Mathematics or Code. Automatic Verification such as Testing or Lean Proven?

2. Languages in Anki.

FAQ

Further resources

John Backus. 1978. Can programming be liberated from the von Neumann style? a functional style and its algebra of programs. Commun. ACM 21, 8 (Aug. 1978), 613–641. https://doi.org/10.1145/359576.359579

https://zsmith.co/OOA.php

Alonso, J. A. (2022, June 06). José A. Alonso Jiménez. Retrieved from https://www.cs.us.es/~jalonso

Alonso, J. A. (2022, March 02). Miscelánea de apuntes. Retrieved from https://www.cs.us.es/~jalonso/apuntes

Logic programming and Reasoning Systems

Why?

Context

Horn clauses are a subset of first-order predicate logic, which are Turing-complete.

Prolog

SAT

ProbLog

DataLog

You can embed Logic programming into your favorite language.

Resources

https://github.com/reddit-archive/reddit1.0/tree/master

https://dstrohmaier.com/why-learn-prolog-in-2021/

The Art of Prolog, by Ehud Shapiro.

Prolog Tutorial -- Contents. (2016, October 03). Retrieved from https://www.cpp.edu/~jrfisher/www/prolog_tutorial/contents.html

Fifty Years of Prolog and Beyond by Philipp Körner, Michael Leuschel, João Barbosa, Vítor Santos Costa, Verónica Dahl, Manuel V. Hermenegildo, Jose F. Morales, Jan Wielemaker, Daniel Diaz, Salvador Abreu, Giovanni Ciatto

The Power of Prolog. (2022, October 30). Retrieved from https://www.metalevel.at/prolog

Tau Prolog

"PLP Tutorial." 10 Aug. 2018, mcs.unife.it/~friguzzi/plptutorial/#tutorial.

Supplements for "Concepts, Techniques, and Models of Computer Programming". (2020, October 23). Retrieved from https://www.info.ucl.ac.be/~pvr/ds/mitbook.html

Tammet, T. (2019). GKC: A Reasoning System for Large Knowledge Bases. In: Fontaine, P. (eds) Automated Deduction – CADE 27. CADE 2019. Lecture Notes in Computer Science(), vol 11716. Springer, Cham. https://doi.org/10.1007/978-3-030-29436-6_32

FAQ

Applications

https://news.ycombinator.com/item?id=31210466

Why prolog is not popular?

https://news.ycombinator.com/item?id=14439137

TODO

https://en.wikipedia.org/wiki/Programming_paradigm

Streaming models, Timed and Hybrid Models

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

Semantics and reasoning

Logic

Of Prolog, T. P. (2022, April 03). A Tour of Prolog. Youtube. Retrieved from https://www.youtube.com/watch?v=8XUutFBbUrg&ab_channel=ThePowerofProlog

Next steps

References

Basic Category Theory for Computer Scientists, ISBN 0-262-66071-7

Types and Programming Languages Benjamin C. Pierce

Software Foundations. (2021, May 24). Retrieved from https://softwarefoundations.cis.upenn.edu

Dictionary

Algorithm.

Algorithms are a precise and unambiguous sequence of steps.

Algorithms can have side effects but you have to be able to analyze their postconditions.

You could describe Algorithms in different paradigms such as functional, logic, or imperative. In literature, most authors write algorithms as an imperative paradigm and pseudocode or natural language.

Algorithms are not systems.

Algorithms are immutable.

Algorithms have to finish.

Algorithms must be carried out mechanically.

An algorithm is the description of a machine. Every algorithm is a Turing Machine, but not every Turing Machine is an algorithm.

If exists some interpreter or compiler that can execute the algorithm, the algorithm is the code of a program too.

Running time and space measures the “quality” of the algorithms.

Procedure.

Similar to an algorithm, but unlike this, a procedure can finish or not.

Circuit.

A representation of a procedure.

Software.

Programs.

System.

Software system.

Program over time.

Application software.

Basic system.

Platform.

Hardware.

Machine.

Software = Hardware.

Function.

Process.

Code.

Language.

Routine.

Coroutine.

Parameters.

Arguments.

Input.

Pseudocode.

Testing.

Program. Programming vs coding.

Solution.

Domain.

Routine.

Subroutine.

Calculator.

Computer.

Computing.

Calculating.

Applications.

Apps.

recipe, process, method, technique, procedure, routine, rigmarole

Interface.

Script.

Hardware.

Platform.

Systems, computer systems, and business processes.

Systems, Applications, and Products in Data Processing (SAP).

Complex vs hard

Programming complexity

Concepts, Techniques, and Models of Computer Programming MIT Press, hardcover, 900pp+xxix, ISBN 0-262-22069-5, March 2004

Computation vs Computing

Parameters or Arguments?

From a function's perspective:

A parameter is the variable listed inside the parentheses in the function definition.

An argument is a value that is sent to the function when it is called.

https://www.w3schools.com/python/gloss_python_function_arguments.asp#:~:text=Parameters or Arguments%3F,are passed into a function.&text=A parameter is the variable,function when it is called