Introduction to Computational Thinking | Lecture 2

Who is Haskell B. Curry and what is he known for?

Haskell B. Curry (1900-1981) was an American mathematician, logician, and computer scientist.

He is known for his development of combinatory logic which was first presented by Moses Schonfinkel in a 1924 paper.

He is also known for the Curry Paradox, the Curry-Howard correspondence, and the method of Currying a function.

The Haskell programming language is named after Curry.

What do computers do?

Store and manipulate information.

What determines the behavior of a computer?

A sequence of statements called a program.

Why are computers so useful?

1. Hardware enables massive amounts of data to be stored and manipulated with great speed and accuracy.

2. Software provides the means to control the behavior of the hardware with extraordinary power and flexibility.

What is a programming language?

A programming language is a formal language for writing programs.

What is the difference between imperative and declarative statements?

An imperative statement expresses an action to be performed, while a declarative statement expresses a property to be employed.

What is an imperative program?

An imperative program is a sequence of imperative statements that expresses how the program will work.

What is a declarative program?

A declarative program is a sequence of declarative statements that expresses what the program will achieve.

What is a programming paradigm?

A programming paradigm is a well-developed style of programming.

How many programming paradigms can a language support?

One or more.

What are major programming paradigms?

Procedural, Object Oriented, Functional, and Logical

What is the procedural programming paradigm?

Programs are imperative; a program is a collection of procedures possibly having side effects.

Examples: Fortran, COBOL, C, BASIC, Pascal, Ada.

What is the object oriented programming paradigm?

Programs are imperative; a program behaves as a collection of interacting objects.

Examples: Smalltalk, C++, Java, C#, Python.

What is the functional programming paradigm?

Programs are mostly declarative; a program is a collection of side-effect free function definitions.

Examples: Lisp family, ML family, Elm, Haskell

What is the logical programming paradigm?

Programs are mostly declarative; a program is a collection of logical statements.

Example: Prolog.

What are the modes of program execution and what do they mean?

1. Interpretation: A program is interpreted and executed one line at a time. It supports interactive development and debugging of code however its generally slower than executing compiled code.

2. Compiled: A program that is compiled into native machine code. The machine code is optimized to run fast however the code development is more difficult.

Is Haskell compiled or interpreted?

It can be executed by both models. Haskell can be compiled into byte code for a virtual machine that is either interpreted or compiled. This makes programs more portable however byte code is slower than native code.

What are values and what are some examples?

Values are the information (called data) stored and manipulated by computer programs.

Examples:

1. Booleans: Represents true or false values.

2. Machine integers: Represents small integers

3. Floating point numbers: Represents rational numbers in scientific notation

4. Strings: Represent sequences of characters.

5. Tuples: Represents sequences of values of different kinds.

6. Lists: Represents sequences of values of the same kind.

7. Functions: Represent mathematical functions.

What is an expression and what types of expressions exist?

An expression is a syntactic entity that denotes a value.

Examples in Haskell:

1. (x * 2) + 7

2. “abc”

3. True && y

An atomic expression is an identifier (e.g., x or rotateHorse) or a literal (e.g., 2.3, “cat”, or True)

A compound expression is formed by applying a function or operator to other expressions (e.g., abs 10 or 1 + 2)

The value of an expression is obtained by evaluating the expression.

What is a data type and what data types exist?

A data type (or type for short) is a syntactic entity that denotes a collection of values of similar form.

Examples in Haskell:

1. Bool denotes the values True and False.

2. Int denotes the set of machine integers.

3. Float denotes the set of floating point numbers.

4. Integer → Integer denotes the set of functions from Integer to Integer

When does a type error happen?

A type error happens when a value of one type is used where a value of another type is expected.

An expression is type checked in Haskell (before it is evaluated) to determine if it contains any type errors.

What are unary functions?

A unary function is a function that takes in exactly one input parameter.

What is a function?

Definition 1: A function is a rule f : I → O that associates members of I (inputs) with members of O (outputs)

• Every input is associated with at most one output.

• Some inputs may not be associated with an output. (For instance the function 1/x)

  
  

Definition 2: A function just is the set of all its input-output pairs.

Each function f has a domain and a range corresponding to the functions input set and output set

What are the important properties of functions?

Total: A total function is a function that returns a predictable defined value for every input within its specified domain.

Surjective: A function is surjective if every output maps to at least one input.

Injective: A function is injective (one to one) when different inputs always produce different outputs.

Bijective: A function is bijective (Injective & Surjective) when every output value has exactly one input value pointing to it.

What is an n-Ary Function?

n-Ary means a function that takes in n inputs.

Definition 1: A function is a rule f : I₁,...,Iₙ → O that associated every list of inputs with at most one output and some lists of inputs may not be associated with an output.

Definition 2: A function is a value — the set of all (n+1)-tuples (x₁,...,xₙ,y), where tuples agreeing on all n inputs must agree on y.

How do you represent an n-Ary Function as a Unary Function?

There are two ways of representing an n-Ary function as a unary function:

1. Converting the list of inputs to a tuple and passing it as one argument

2. Or as a Curryed function where for each parameter a new function is returned and called: F(x,y,z) = F(x)(y)(z)

What form are functions in Haskell usually defined?

Functions in Haskell are usually defined in Curryed form but can also be defined on tuples.

What is functional programming?

In functional programming, programs are declarative meaning a program is a sequence of side-effect free function definitions.

Results are produced by evaluating expressions built from functions.

Functions are defined as first-class values and used as rules.

Recursion plays a crucial role.

State change and data mutation are avoided as much as possible.

What are the advantages of functional programming?

1. The meaning of a program is simpler and more explicit.

2. Testing and reasoning about programs is much simpler.

3. Expressions can be safely moved around in the code.

4. Code is more compact.

5. Evaluation can be performed in parallel.

What are the leading functional programming languages?

Lisp family (e.g., Scheme, Common Lisp, Clojure):

• Lisp is the second oldest programming language (1958)

• Procedural + functional programming

• Weak type system with dynamic type-checking

ML Family (e.g., Standard ML, OCaml, F#):

• Procedural + functional programming

• Strong type system with static type-checking.

OO + FP languages:

• Python

• Ruby

• Scala

Pure FP languages:

• Elm

• Erlang

• Haskell