Zaawansowane elementy programowania funkcyjnego¶

Prezentacja: http://www.cs.put.poznan.pl/ksiek/fp/meddley/

Currying i częściowe wykonanie funkcji¶

Currying (Schönfinkelisation) rozbicie wykonania funkcji n argumentowej na n wykonań funkcji jednoargumentowych wyższego rzędu.

\(f: (T_1 \times T_2 \times T_3) \rightarrow T_r\)

\(f^c: T_1 \rightarrow T_2 \rightarrow T_3 \rightarrow T_r = g^c\)

\(g^c: T_2 \rightarrow T_3 \rightarrow T_r = h^c\)

\(h^c: T_3 \rightarrow T_r\)

\(f(x,y,z) \Rightarrow f^c(x)(y)(z)\)

Odwrotność: uncurrying.

\(f^c(x)(y)(z) \Rightarrow f(x,y,z)\)

Wykonanie częściowe (częściowa aplikacja): wykonanie funkcji wieloargumentowych z użyciem tylko części argumentów.

\(f: (x,y,z) \Rightarrow f (x)(y,z)\)

W praktyce terminy używane zamiennie.

Częściowe wykonanie funkcji:

val f(x: Int, y: Int) = x + y
val g = f(13, _:Int)

val debug = (level: String, string: String) => "[" + level + "]: " + string

val warning = debug("Warning", _: String)
val error = debug("Error", _: String)

Częściowe wykonanie metody:

def method(x: Int, y: Int)(z: Int, v: Int) = x * y + z * v

def f(x: Int, y: Int) = x + y
val g = f(13, _:Int)

Domknięcia¶

Funkcja której wolne zmienne zostały zamknięte (bound).

val y = 5
val f = (x: Int) => x + y

f(14228, 5)

Wolne zmienne w funkcjach wyższego rzędu. Funkcja przenosi swój kontekst.

val outer = (z: Int) => {
    val y = 5 + z
    val f = (x: Int) => x + y
    f
}

val g = outer(5)
g(3)

Modyfikacja pamięci.

var x = 1
f = () => x
x = 2
f()

var f: () => Int = _
var l: List[() => Int] = List()
var i = 0
while (i <= 9) {
    f = () => i
    l = f :: l
    i = i + 1
}

l(5)()

var f: () => Int = _
var l: List[() => Int] = List()
for (i <- 0 to 9) {
    f = () => i
    l = f :: l
}

l(5)()

Funkcje częściowe¶

val pf: Int => Int = {case x => x + 1}

Pattern matching:

val pf: Int => Int = {
    case x if x > 0 => x + 1
    case 0 => 0
    case x => -x + 1
}

pf(1)
1 match pf

Podzbiór domeny

val pf: Int => Int = {case x if x > 0 => x + 1}

pf(1)
pf(-1) #scala.MatchError: -1 (of class java.lang.Integer)

Dekompozycja argumentów

val pf: ((Int, Int)) => Int = {case (x, y) => x + y}

val p = (2,2)
pf(p)

List(2->2, 1->1, 3->3) map pf

List(2->2, 1->1, 3->3) map {case (x, y) => x + y}

Leniwa strategia ewaluacji¶

Leniwa ewaluacja (lazy evaluation): obliczanie wyrażeń w najpóźniejszym możliwym momencie. Przeciwieństwo: eager evaluation, obliczanie wyrażeń w momencie deklaracji.

Leniwe wartości:

val x = { println("initializing x!"); 5 }
x

lazy val x = { println("initializing x!"); 5 }
x

Przekazywanie argumentów przez wartość (call by value) vs przekazywanie wartości przez referencję (call by name):

def callByValue(x: Int) = { println("returning x!"); x; x }
def callByName(x: => Int) = { println("returning x!"); x; x }

callByValue({ println("initializing x!"); 5 })
callByName({ println("initializing x!"); 5 })

Motywacja: wygoda, efektywność (zapobieganie wywołań), nieskończone listy.

lazy val now = new Date

val start = System.currentTimeMillis
lazy val end = System.currentTimeMillis
// ...
val total = end - start

var currentLevel = 2
def debug(level: Int, msg: => String) = if (currentLevel <= level) println(msg)

debug(1, "Potentially bad things happening in thread " + Thread.currentThread)
debug(2, "Potentially bad things happening in thread " + Thread.currentThread)

Leniwe strumienie to listy zaimplementowane za pomocą leniwej strategii ewaluacji, pozwalające na pracę na nieskończonych ciągach.

val s: (Int => List[Int])   = k => k :: s(k + 1)
val s: (Int => Stream[Int]) = k => Stream.cons(k, s(k + 1))

val naturals = s(1)

naturals(100)
naturals(101)

val even = naturals.filter((k: Int) => k % 2 == 0)

even(100)
even(101)

Ankieta

Ćwiczenia¶

Problem: Memoizacja to technika optymalizacyjna polegająca na przechowywaniu wyników funkcji dla najczęściej powtarzanych wektorów argumentów i zwracaniu wyniku z cache-a zamiast wykonywania funkcji. Zaimplementuj memoizację używając mechanizmów funkcyjnych.
Problem: Zaimplementuj ciąg Fibonacciego za pomocą leniwych strumieni.
Problem: Zaimplementuj sito Eratostenesa za pomocą leniwych strumieni.
Problem: W języku niefunkcyjnym (e.g. Python) zdefiniuj konstrukcje pozwalającą uzyskać efekt:
- leniwej ewaluację wyrażenia,
- currying, uncurrying,
- przekazania argumentu call by name,
- nieskończone listy.

Zadanie [Scala3]¶

Zaimplementuj w Scali następujący generator code highlighterów (jakkolwiek to się nazywa po polsku).

Code highlighter to parser jakiegoś języka L działający wg jakiejś konfiguracji C. Ten parser dostaje na wejście kod źródłowy P jakiegoś programu napisanego w L i zwraca “pokolorowany” kod źródłowy P’.

Kod pokolorowany to taki, do którego dodane zostały znaczniki określające sposób prezentacji poszczególnych fragmentów tego kodu (np. à la HTML/CSS, e[31m...e[0m, itp.).

Sposób w jaki kod ma być pokolorowany jest określone przez C (np. słowa kluczowe na czerwono, boldface, operatory na niebiesko).

Czyli highlighter to funkcja P -> P’ której semantykę określają L i C.

Generator code highlighterów dostaje na wejście specyfikację L i C i na wyjściu zwraca odpowiedni code highlighter.

Na potrzeby zadania wystarczą proste parser które rozróżniają tylko słowa kluczowe, operatory, typy, literały i “wszystko inne” danego języka.

Przykładowa specyfikacja mojego wymyślonego na szybko języka:

keywords={let, in, if, then, else, function}
types={bool}
literals={true, false, _}
operators={∧, ∨, ¬, =}

/*wszystko oddzielone spacjami od siebie w programie*/

Przykładowa konfiguracja:

keywords=black
types=italic, blue
literals=red
operators=black
other=gray

Przykładowy program:

let x = true in
    if ¬ x ∨ false
        then true
        else false

Zadanie [Scala3 deprecated]¶

Zaimplementuj w Scali bibliotekę dla nieskończonych ciągów liczbowych zawierającą (ad minimum):

konstruktor z wzoru ogólnego (e.g., faksymile \(s_n = 2n + 6\)),

wartość k-tego elementu,

suma k elementów,

tworzenie skończonego podciągu,

tworzenie sufiksów od k-tego elementu,

monotoniczność i słaba monotoniczność w przedzialne ciągu.

Konrad Siek