Funktionell programmering/Paradigm Flashcards
Vad är imperativ programmering?
Imperativ programmering:
Programmet har ett tillstånd (state), och programmet
har instruktioner för hur tillståndet ska manipuleras
steg för steg för att nå slutresultatet. Ex Java, Go, Assembler, C o.s.v.
En sekvens av satser som beskriver hur datorn ska bygga upp ett state (tillstånd).
Subprogram (kallas subrutiner i assembler) anropas med hopp (jump och branch, exempel jsr, beq, bne i assembler, goto i C och BASIC) och utan parametrar. Först modifieras programmets state för att hantera anropet, resultatet av beräkningarna levereras genom bieffekter på globala variabler.
Vad är funktionell programmering?
En typ av deklarativ programmering där resultatet av beräkningar beskrivs som värdet av (matematiska) funktioner.
- Vi har immutability, rena funktioner, funktioner som första klassens medlemmar. Referenstransparens följer av (se punkt 2).
- Vi har inte destruktiv tilldelning eller bieffekter av funktionsanrop.
- Bakomliggande antaganden: Vi vill arbeta med uttryck och symboler, inte detaljer om hur datorn fungerar.
De funktionella språken heter Lisp, Erlang, Haskell och Clojure. Ett språk som är fullt ut funktionellt men också tillåter flera imperativa paradigm är Scala. Funktionellt inspirerad syntax och språkkonstruktioner finns i C++, C#, Java, Javascript, Python med flera.
Vad är logikprogrammering?
Villkorsprogrammering (Constraint Programming) går ut på att speca villkoren för en beräkning och sedan låta språket räkna ut svaret själv.
Logisk programmering är ett deklarativt paradigm.
Främsta (och enda exemplet i kursen) är Prolog
Vad är deklarativ programmering?
Deklarativ programmering (motsatsen till Imperativ programmering): Koden definierar vad slutresultatet ska vara, inte hur det ska uppnås och är samlingsnamnet för funktionell programmering och logikprogrammering.
I programmeringsstil anger programmeraren vad som ska göras, inte hur beräkningen ska gå till. Man beskriver inget exekveringsflöde. I princip kan instruktionerna anges i vilken ordning som helst. Man strävar också efter att undvika sidoeffekter.
I deklarativ programmering defnierar man vad
saker är och de kan inte ändra värde.
Instruktionerna har inga sido-effekter .
——————————————————————————
Programmen beskriver vad som ska beräknas, inte hur det ska beräknas.
Om något definitivt inte är imperativt så är det deklarativt.
Deklarativ programmering undviker bieffekter.
Referenstransparens innebär att varje uttryck kan ersättas med sitt värde utan att förändra resultatet!
Deklarativa paradigmer: Funktionella, logiska,
Exempel på deklarativt språk: SQL (databasförfrågningar)
Vad innebär referenstransparens/referential transparency?
- ## Full referential transparaency i en fil eller ett metodanrop betyder att ett namn alltid är samma sak. (Funktionell programmering)An expression is called referentially transparent if it can be replaced with its corresponding value without changing the program’s behavior.[1] This requires that the expression is pure, that is to say the expression value must be the same for the same inputs and its evaluation must have no side effects. An expression that is not referentially transparent is called referentially opaque.
Vad är lat evaluering?
- Lazy evaluation is a method to evaluate a Haskell program. It means that expressions are not evaluated when they are bound to variables, but their evaluation is deferred until their results are needed by other computations. (Haskell wiki)
- In programming language theory, lazy evaluation is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing). (Wikipedia)
Lat evaluering i Haskell:
•”Beräkna bara det som behövs”
• Varje uttryck lagras som ett löfte om evaluering — vid behov. Räknas högst en gång.
Vad innebär det med “inga sidoeffekter”?
När en funktion som anropas med samma värde två gånger ger det alltid samma resultat.
Vad innebär Svansrekursion?
Rekrusion
- Man har ett basfall och låter en funktion anropa sig själv så att den steg för steg går mot basfallet och bygger upp svaret.
Det är en Svansrekursion om det rekursiva anropet returnerar direkt utan några kvarhängade operationer från tidigare anrop.
- Svansrekursion är inom datavetenskap en speciell sorts rekursion då sista operationen i en funktion är ett rekursivt anrop. (Wikipedia)
- In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of (return (recursive-function params)). Basically, the return value of any given recursive step is the same as the return value of the next recursive call. (Stack overflow)
Vad innebär det med polymorfism/polymorphism?
Det finns flera typer av polymorphism tre av de är:
• Ad hoc polymorphism -
Också känd som “method overloading” och “operator overloading”. Vilket är när man kan använda samma metod namn eller operator för olika typer. Beroende på vilken typ av input man hade så får man olik output.
“ad-hoc polymorphism is bound to a type. Depending on the type, different implementations of the method are invoked.”
“Ad-hoc polymorphismusually refers to code that appears to be polymorphic to the programmer, but the actual implementation is not. A typical example is overloading: using the same function name for functions with different kinds of parameters. Although it looks like a polymorphic function to the code that uses it, there are actually multiple function implementations (none being polymorphic) and the compiler invokes the appropriate one.”
• parametric polymorphism -
“Parametric polymorphism allows the use of a single abstraction across many types. For example, a List abstraction, representing a list of homogeneous objects, could be provided as a generic module. You would reuse the abstraction by specifying the types of objects contained in the list.”
“Parametric polymorphism refers to code that is written without knowledge of the actual type of the arguments; the code is parametric in the type of the parameters. Example generics in Java 5”
“Parametric polymorphism refers to when the type of a value contains one or more (unconstrained) type variables, so that the value may adopt any type that results from substituting those variables with concrete types.
In Haskell, this means any type in which a type variable, denoted by a name in a type beginning with a lowercase letter, appears without constraints (i.e. does not appear to the left of a =>). In Java and some similar languages, generics (roughly speaking) fill this role.
For example, the function id :: a -> a contains an unconstrained type variable a in its type, and so can be used in a context requiring Char -> Char or Integer -> Integer or (Bool -> Maybe Bool) -> (Bool -> Maybe Bool) “
• subtyping polymorphism -
“Subtype polymorphism gives a single term many types using the subsumption rule. For example, a function with argument τ can operate on any value with a type that is a subtype of τ”
“Object-oriented programming languages offer subtype polymorphism using subclassing (also known as inheritance).”
"Subtype Polymorphism – is that we have because of inheritance (When we inherit from some class, in the method signature it is possible to write superclass and put there any subclass)." --------------------------------------------------------------------------------------- In programming languages and type theory, polymorphism is the provision of a single interface to entities of different types or the use of a single symbol to represent multiple different types.
The most commonly recognised major classes of polymorphism are:
- Ad hoc polymorphism: defines a common interface for an arbitrary set of individually specified types.
- Parametric polymorphism: when one or more types are not specified by name but by abstract symbols that can represent any type.
- ## Subtyping: when a name denotes instances of many different classes related by some common superclass(polymorphism) – i programmering: det att en och samma instruktion i ett programspråk kan utföras på olika sätt. Vilket sätt som väljs avgörs av sammanhanget.
– Termen används främst inom objektorienterad programmering, och innebär där att en och samma metod utförs på olika sätt i olika klasser av objekt. Detta är möjligt i objektorienterade program därför att koden som beskriver hur ett anrop ska utföras ingår i objektet, inte i anropet. Anropet anger bara namnet på metoden och vilka argument som ingår
Polymorf funktion?
Kan tillämpas på flera typer.
Polymorf typ?
”Kan anta flera former” .
Haskells olika typklasser?
- Num – Alla numeriska typer
- Ord – Alla ordnade typer (<=)
- Eq – Alla jämförbara typer (==)
- Show – Typer med skrivbara element
- Read – Typer med läsbara element
- Integral – Heltalstyper: Int, Integer
- Fractional – ex. Float, de som stödjer division.
Vad är överlagring (overloading)?
• Samma funktion definierad på olika argument
T.ex.: Addition (+) på Int är inte samma som addition på Float.
Metod överlagrind/ Function overloading:
In some programming languages, function overloading or method overloading is the ability to create multiple functions of the same name with different implementations. Calls to an overloaded function will run a specific implementation of that function appropriate to the context of the call, allowing one function call to perform different tasks depending on context.
For example, doTask() and doTask(object O) are overloaded functions. To call the latter, an object must be passed as a parameter, whereas the former does not require a parameter, and is called with an empty parameter field. A common error would be to assign a default value to the object in the second function, which would result in an ambiguous call error, as the compiler wouldn’t know which of the two methods to use.
- The same function name is used for more than one function definition
- The functions must differ either by the arity or types of their parameters
It is a classification of static polymorphism in which a function call is resolved using some “best match” algorithm, where the particular function to call is resolved by finding the best match of the formal parameter types with the actual parameter types. The details of this algorithm vary from language to language.
———————————————————————————–
Operator overloading:
In programming, operator overloading, sometimes termed operator ad hoc polymorphism, is a specific case of polymorphism, where different operators have different implementations depending on their arguments. Operator overloading is generally defined by a programming language, a programmer, or both.
Överlagring i Haskell?
- Explicit överlagring
- Skapa en klass som beskriver gemensamma egenskaper
- Visa hur överlagringen hanteras för olika typer
T.ex: •Från Prelude.hs: class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool
•Också från Prelude.hs:
instance Eq Integer where
x == y = integerEq x y
•Tala om att din klass tillhör Eq:
instance Eq MinKlass where
x == y = minEq x y
Arv hos typklasser (Haskell)?
•Definiera ordnade typer:
class Eq a => Ord a where
( a -> Bool
(>=), (>) :: a -> a -> Bool
•”Alla Ord-typer måste vara Eq-typer också.”
Funktionell programmering (typer/klasser) jämfört med objektorienterad programmering?
Likheter
• Klasser och arv
• Klasser samlar funktioner
• Standardmetoder
Skillnad
• Inga objekt, inga attribut
• Två sorts polymorfism: Parametrisk och ad hoc
• Alla metoder är statiskt bestämda, ingen klassinformation i data
• Åtkomstkontroll (public, private) indirekt via modulsystem
Haksell och typkonvertering?
I många språk blir det automatiskt typkonvertering, men i haskell har man explicit typkonvertering.
Man måste alltså ange , t.ex:
fromIntegral(length(lista))/ 10 för om man skippar att ta “fromIntegral” får man en typfel error.
Definiera egna datastrukturer?
Java, C++, etc: Klasser
Haskell: data
Exempel:
data Bool = True | False
data Address = None | Addr String
Vad är algebraiska datatyper?
•En typ ”komponerad” av andra typer, var och en med en konstruktor, kallas algebraisk.
•Obs: En produkttyp har endast en konstruktor.
Ex: data Color = RGB Int Int Int
•Obs: En enumererad typ listar konstruktorer utan argument.
Ex: data Bool = True | False
Typer i olika språk?
Statisk typning - Typen begränsar variabeln:
int i := 17 —- Används i Java, Haskell, etc.
Dynamisk typning -Beskriver värdet:
Tänk: i := 17 —- Används i Lisp, MatLab, Perl, etc
Typkonvertering (implicit och explicit)?
Implicit konvertering:
float x = 3.5;
int i = x;
Explicit konvertering:
float x = 3.5;
int i = (int) x;
Stark och svag typning?
- Oklara begrepp. Avser hur starkt språketbegränsar tolkningen av värden.
- Sebesta: ”strongly typed if all type errors are always detected.”
- ”Ada, Java, and C# are nearly strongly typed”
Exempel:
•Tc l: Alla variabler kan tolkas som strängar.
- Perl: Listvariabel kan tolkas som listlängd, beroende på sammanhang. En lista kan tolkas som en associativ array (hashtabell).
- C: Automatisk typkonvertering (casting) mellan flera inbyggda typer. Union kan ej typkontrolleras.
- C++: Skriv dina egna automatiska konverteringsregler.
- Haskell: Ingen automatisk typkonvertering.
Säkra typsystem?
- Def: Ett typsystem är säkert om det garanterar att inga uttryck kan anta värden som inte är definierade av typen.
- Osäkert språk: C
- Säkra språk: Haskell, Ada(?)
Högre ordningens funktion?
En funktion är en högre ordningens funktion om:
- den tar en eller flera funktioner som argument
eller
- returnerar en funktion
eller
- båda ovanstående
