О функциональности Go

в 9:54, , рубрики: Go, Программирование, функциональное программирование

Насколько объектно Go ориентирован многократно и эмоционально обсуждалось. Попробуем теперь оценить насколько он функционален. Заметим сразу, оптимизацию хвостовой рекурсии компилятор не делает. Почему бы? «Это не нужно в языке с циклами. Когда программист пишет рекурсивный код, он хочет представлять стек вызовов или он пишет цикл.» — замечает в переписке Russ Cox. В языке зато есть полноценные lambda, closure, рекурсивные типы и ряд особенностей. Попробуем их применить функциональным манером. Примеры покажутся синтетическими оттого, что во первых написаны немедленно исполняемыми в песочнице и написаны на процедурном все же языке во вторых. Предполагается знакомство как с Go так и с функциональным программированием, разъяснений мало но код комментирован.

Closure, замыкание реализовано в языке в классической и полной мере.
Например ленивую рекурсивную последовательность можно получить так

func produce(source int, permutation func(int) int) func() int {
	return func() int {				//первоклассная lambda
		source = permutation(source)	//замыкание source
		return source
	}
}

Простой вариатор для псевдослучайных чисел

func mutate(j int) int {
	return (1664525*j + 1013904223) % 2147483647
}

И вот наш генератор случайных чисел

next := produce(1, mutate)
next()

Работающий пример

package main

import (
	"fmt"
)

func produce(source int, permutation func(int) int) func() int {
	return func() int { //первоклассная lambda
		source = permutation(source) //замыкание source
		return source
	}
}

//простой вариатор для псевдослучайных чисел
func mutate(j int) int {
	return (1664525*j + 1013904223) % 2147483647
}
func main() {

	next := produce(1, mutate) //и вот наш генератор случайных чисел

	fmt.Println(next())
	fmt.Println(next())
	fmt.Println(next())
	fmt.Println(next())
	fmt.Println(next())

}

Попробовать в песочнице
Currying. каррирование, применение функции к одному из аргументов в общем случае не реализовано. Частные задачи однако решаются. Например функция отложенного вызова стандартной библиотеки time имеет сигнатуру func AfterFunc(d Duration, f func()) *Timer принимает аргументом func(), а мы бы хотели передать нечто более параметризованное func(arg MyType). И мы можем это сделать так

type MyType string			//объявление типа
func (arg MyType) JustPrint(){      //объявление метода
	fmt.Println(arg)
}

метод в Go это функция принимающая первым аргументом своего бенефициара
Выражение MyType.JustPrint даст нам эту функцию с сигнатурой func(arg MyType), которую мы можем применить к аргументу MyType.JustPrint(«Съешь меня»)
Напротив выражение arg.JustPrint даст нам функцию JustPrint примененную к arg c сигнатурой func() которую мы и можем передать нашему будильнику

timer := time.AfterFunc(50 * time.Millisecond, arg.JustPrint)

Работающий пример

package main

import (
	"fmt"
	"time"
)

type MyType string              //объявление типа
func (arg MyType) JustPrint() { //объявление метода
	fmt.Println(arg)
}

func main() {
	arg := MyType("Hello") //экземпляр типа
	time.AfterFunc(50*time.Millisecond, arg.JustPrint)
	arg = "By"
	time.AfterFunc(75*time.Millisecond, arg.JustPrint)
	time.Sleep(100 * time.Millisecond)

}

Попробовать в песочнице.
Continuation, продолжение как первоклассный объект не реализован с той элегантностью что в scneme. Есть между тем встроенная функция panic() ¸ приблизительный аналог long_jump способная прервать вычисления и вернуть при этом достигнутый результат(например ошибку) в место откуда был сделан вызов. Конструкцию panic(), defer recover() кроме обработки исключений можно применить например для сквозного выхода из зашедшей слишком глубоко рекурсии(что заметим и делается в пакете encoding.json). В этом смысле конструкция первоклассна, а не исключительна. Выход из ненужной рекурсии, стоит подчеркнуть, это классическое применение continuation.
Вот прямолинейная, не оптимизированная(не применять в production!!) рекурсивная функция отдающая n-ное число Фибоначчи как сумму предыдущих

func Fib(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	first := Fib(n - 1)
	second := Fib(n - 2)
	if first > max {	//Если числа стали излишне велики
		panic(second)	//то здесь вычисления прерываются со сбором урожая
	}
	return first + second
}

Так мы ее вызовем с продолжением(call/cc) желая получить n-ное число Фибоначчи, если только оно не больше max

var max int = 200
func CallFib(n int) (res int) {
	defer func() {
		if r := recover(); r != nil {	//восстановление продолжения
			res = r.(int)		//плоды трудов
		}
	}()
	res = Fib(n)
	return
}

Работающий пример.

package main

import "fmt"

var max int = 1000

func Fib(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	first := Fib(n - 1)
	second := Fib(n - 2)
	if first > max { //Если числа стали излишне велики
		panic(second) //то здесь вычисления прерываются со сбором урожая
	}
	return first + second
}
func CallFib(n int) (res int) {
	defer func() {
		if r := recover(); r != nil { //восстановление продолжения
			res = r.(int) //плоды трудов
		}
	}()
	res = Fib(n)
	return
}
func main() {
	fmt.Println(CallFib(10))     //тривиальный вызов
	fmt.Println(CallFib(100000)) //Излишества
	fmt.Println("Паника подавлена")
}

Попробовать в песочнице.
Монады в понимании Haskell процедурному языку просто не нужны. В Go между тем вполне разрешены рекурсивные объявления типов, а многие как раз и полагают монады видом структурной рекурсии. Rob Pike предложил следующее определение state machine, конечного автомата

type stateFn func(Machine) stateFn

где состояние это функция машины производящая действия и возвращающая новое состояние.
Работа такой машины проста

func run(m Machine) {
	for state := start; state != nil; {
		state = state(m)
	}
}

Разве не напоминает Haskell State Monad.
Напишем минимальный парсер, а для чего же еще нужны state machine, выбирающий числа из входящего потока.

type stateFn func(*lexer) stateFn
type lexer struct {
	*bufio.Reader //машине нужна лента
}

Нам достаточно всего двух состояний

func lexText(l *lexer) stateFn {
	for r, _, err := l.ReadRune(); err != io.EOF; r, _, err = l.ReadRune() {
		if '0' <= r && r <= '9' { //если попалась цифра
			l.UnreadRune()
			return lexNumber //переход состояния
		}
	}
	return nil // Стоп машина.
}
func lexNumber(l *lexer) stateFn {
	var s string
	for r, _, err := l.ReadRune(); err != io.EOF; r, _, err = l.ReadRune() {
		if '0' > r || r > '9' { //если не цифра
			num, _ := strconv.Atoi(s)
			return lexText //переход состояния
		}
		s += string(r)
	}
	num, _ := strconv.Atoi(s)
	return nil // Стоп машина.
}

Работающий пример.

package main

import (
	"bufio"
	"fmt"
	"io"
	"strconv"
	"strings"
)

type stateFn func(*lexer) stateFn

func run(l *lexer) {
	for state := lexText; state != nil; {
		state = state(l)
	}
}

type lexer struct {
	*bufio.Reader //машине нужна лента, поток ввода
}

var output = make(chan int) //выходной поток

func lexText(l *lexer) stateFn {
	for r, _, err := l.ReadRune(); err != io.EOF; r, _, err = l.ReadRune() {
		if '0' <= r && r <= '9' { //если попалась цифра
			l.UnreadRune()
			return lexNumber //переход состояния
		}
	}
	close(output)
	return nil // Стоп машина.
}
func lexNumber(l *lexer) stateFn {
	var s string
	for r, _, err := l.ReadRune(); err != io.EOF; r, _, err = l.ReadRune() {
		if '0' > r || r > '9' {
			num, _ := strconv.Atoi(s)
			output <- num  //передаем для утилизации
			return lexText //переход состояния
		}
		s += string(r)
	}
	num, _ := strconv.Atoi(s)
	output <- num
	close(output)
	return nil // Стоп машина.
}
func main() {
	var sum int
	a := "hell 3456 fgh 25 fghj 2128506 fgh 77" //пример ввода, для песочницы просто строка
	fmt.Println("Числа из строки: ", a)
	rr := strings.NewReader(a) //сделаем поток из строки
	lexy := lexer{bufio.NewReader(rr)}
	go run(&lexy) //запускаем лексер отдельным потоком
	for nums := range output {
		fmt.Println(nums)
		sum += nums
	}
	fmt.Println("В сумме дают: ", sum)
}

Попробовать в песочнице.
Реактивное программирование сложно формально описать. Это что то о потоках и сигналах. В Go есть то и другое. Стандартная библиотека io предлагает интерфейсы io.Reader и io.Writer имеющие методы Read() и Write() соответственно и достаточно стройно отражающие идею потоков. Файл и сетевое соединение к примеру реализуют оба интерфейса. Использовать интерфейсы можно безотносительно к источнику данных, скажем

Decoder = NewDecoder(r io.Reader)
err = Decoder.Decode(Message)

будет единообразно кодировать файл или например сетевое соединение.
Идея сигналов воплощена в синтаксисе языка. Тип chan (channel) оснащен оператором < — передачи сообщений, а уникальная конструкция select{ case < — chan} позволяет выбрать готовый к передаче канал из нескольких.
Напишем совсем простой миксер потоков.
В качестве входных потоком возьмем просто строки.(Мы условились делать примеры немедленно исполняемыми в песочнице, что ограничивает в выборе. Читать из сетевого соединения было бы интересней. И код может практически без изменений.)

reader1 := strings.NewReader("ла ла ла ла ла ла ла")
reader2 := strings.NewReader("фа фа фа фа фа фа фа")

Выходным примем стандартный поток вывода

writer := os.Stdout

В качестве управляющих сигналов используем канал таймера.

stop := time.After(10000 * time.Millisecond)
tick := time.Tick(150 * time.Millisecond)
tack := time.Tick(200 * time.Millisecond)

И весь наш миксер

select {
case <-tick:
	io.CopyN(writer, reader1, 5)
case <-tack:
	io.CopyN(writer, reader2, 5)
case <-stop:
	return
}

Работающий пример.

package main

import (
	"io"
	"os"
	"strings"
	"time"
)

func main() {
	stop := time.After(10000 * time.Millisecond)
	tick := time.Tick(150 * time.Millisecond)
	tack := time.Tick(200 * time.Millisecond)

	reader1 := strings.NewReader("ла ла ла ла ла ла ла")
	reader2 := strings.NewReader("фа фа фа фа фа фа фа")
	writer := os.Stdout
	for {
		select {
		case <-tick:
			io.CopyN(writer, reader1, 5)
		case <-tack:
			io.CopyN(writer, reader2, 5)
		case <-stop:
			return
		}

	}
}

Попробовать в песочнице.

Автор: uvelichitel

Источник

Поделиться новостью

* - обязательные к заполнению поля