# Models of computation and programming languages: principles and paradigms

# Requisites

# Resources

#### Foundations

# 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.

#### Real code vs pseudocode

Name | Tags |
---|---|

Real code | Issues of data abstractionProgramming languageSoftware engineeringerror handlingmodularity |

Pseudocode | English languageNo software engineeringProgramming languageessence of the algorithm |

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.

- Lambda Calculus

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

- Category theory

- Lisp
- Racket.

- Schema.

- Haskell.

- Scala.

- Elm.

- Erlang.
- Ruby.

- Elixir.

- Fenix.

- Clojure.

- Curry.

- Servidor en linea.

## Notes

## Worked examples

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

- 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

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.