«Жизнь» Конвея на «R»

«Жизнь» (18.72КиБ)
Одно поколение в игре «Жизнь», запущенной в терминале

Игра «Жизнь» знакома, наверное, каждому программисту. Интересна она тем, что этот незатейливый алгоритм оказал существенное влияние на целый ряд научных дисциплин.

Не помню, чтобы я её когда-то либо программировал в чистом виде, но совершенно точно должен был ею вдохновляться, когда в детстве, ещё на Турбо Паскале реализовывал какую-то собственную её версию с генетическим обменом между соседями.

Сегодня ночью постарался написать классическую версию игры «Жизнь» на языке «Эр». Мне показалось это интересной задачей, так как «Эр» очень удобным образом позволяет работать со множествами так, как будто это скалярные значения.

Это можно увидеть почти сразу, в строке, где создаётся матрица случайных значений:
life <<- matrix(as.integer(runif(rows * cols) < ratio), rows, cols)
Сравнение с переменной ratio и вызов as.integer тут применяется к каждому значению из множества, генерируемого функцией runif (Random Uniform Distribution, генерирует случайные значения с нормальным распределением). Так матрица игры заполняется случайными нулями и единицами.

Ниже по коду довольно много манипуляций с этой матрицей и выполнение правил алгоритма за счёт конструкций языка занимает всего несколько строк.

Суть такова: матрица двигается во все восемь направлений (с шагом 45°), все получившиеся матрицы складываются, это позволяет оценить количество соседей любой клетки в каждом из направлений. Далее в две строки выполняются основные условия:
# Any dead cell with exactly three live neighbours becomes a live cell
life.new[life == 0 & life.neighbors == 3] <- 1
# Any live cell with fewer than two or more than three live neighbours dies
life.new[life == 1 & (life.neighbors < 2 | life.neighbors > 3)] <- 0
Тут участвуют три матрицы: life — поле игры на предыдущем шаге, life.new — поле игры на текущем шаге и life.neighbors — матрица соседей (точка в «Эре» не имеет специального значения). Как видите матрица сравнивается с числом, как будто она скаляр, результат этой операции тоже матрица, но из булевых значений, в каждой клетке — результат операции. Такую матрицу можно использовать как индекс, в результате чего вернутся только те ячейки, по адресам которых в булевой матрице было TRUE.

Дальше просто, поскольку ячейки возвращаются по ссылке, им скопом присваивается требуемое значение.
Комментировать
2 августа 2017 10:00

«Песня о пиве»: R

Как многие наверное помнят, в качестве хобби я время от времени пишу на разных языках программирования американскую «Песню о пиве»

Это довольно известное развлечение — реализовывать на куче языков что-то простое, обычно выбирают числа Фибоначчи, «Песню» или ещё что-то незатейливое.

Я выбрал именно «Песню о пиве», так как не всем языкам из моего списка, под силу что-то большее. До сегодняшнего дня в списке было 57 языков, сегодня, 58-м пунктом, к ним вполне ожидаемо присоединится язык «Эр», о нём я уже немного писал, собираюсь писать и дальше как время образуется.
# Written by Evgeny Stepanischev, 2017

bottles <- function(beer) {
	ifelse(beer == 0, "no bottles",
		ifelse(beer > 1, paste(beer, "bottles"),  "1 bottle")
	)
}

for (i in 99:1) {
	paste(bottles(i), "of beer") -> b

	cat(b, " on the wall, ", b, ".\n", sep = "")
	cat("Take one down and pass it around,", bottles(i - 1), "of beer on the wall.\n\n")
}

cat("No more bottles of beer on the wall, no more bottles of beer.\n")
cat("Go to the store and buy some more, 99 bottles of beer on the wall.\n")
1 комментарий
21 июля 2017 20:37

Вызов C из R

Заинтересовался темой вызова функций Си из языка «Эр». Обнаружилось целых два интерфейса: простоватый вызов «.C» и более сложный «.Call», к сожалению ни один из них не предназначен для вызова произвольного кода — со стороны Си в каждом из случаев следует соблюдать некоторые соглашения.

Я решил попробовать подёргать функции библиотеки libmagic, поскольку когда-то делал то же на «Пайтоне». Интерфейс .Call для этой задачи — пушка по воробьям, его имеет смысл использовать, если языки должны обмениваться специфичными для «Эра» структурами, а у меня из типов только строки и числа.

Так как .C не умеет работать с возвращаемыми из функции значениями (возможен возврат только через параметр), да и передаётся всё как указатели, пришлось даже для этой простой задачи написать обёртку. Скомпилировать её можно командой make, либо запустить руками строчку компиляции из файла сборщика.

Программа на «Эре» небольшая, бо́льшую часть занимает определение констант. Внутри захардкожен пример использования, так как библиотеку я делать не намерен, он там так и останется.

Примечание: я знаю, что функция strdup не является переносимой, но мне, если честно, всё равно, не хочется ради исследования принципа тащить в код её реализацию.
Комментировать
1 июля 2017 21:21

Применил «R» на практике

Квантили (11.16КиБ)
Вычисление на языке «Эр» разных квантилей делается одной командой

Каждый год я стараюсь, если не выучить, то познакомиться с одним или несколькими языками программирования. В основном, чтобы прочувствовать какие-то новые концепции.

Научившись их применять в языке, растёшь как профессионал, приобретаешь новые навыки и новые способы мышления. Стараюсь выбирать языки именно с таким прицелом, и если этого не происходит, испытываю сожаление от потраченного времени.

Тем не менее, не чураюсь применения языков на практике, в работе. Так в «Яндексе» я внезапно несколько лет попрограммировал на «Пайтоне», который выучил по забытой соседом на общей кухне книжке, а на текущем месте работы написал специализированную СУБД на «Гоу».

А вчера случилось написать по работе строчку на языке «Эр» (который я сейчас изучаю), всего одну, но полезную — нужно было посчитать различные квантили по количеству страниц на документ, программа с результатом на скриншоте — там загружается файл, где разделитель полей — точка с запятой, из загруженных данных выбирается второй столбец и считаются указанные квантили.
Комментировать
24 июня 2017 20:06

Интерпретатор Brainfuck на языке R

В качестве упражнения написал тривиальный интерпретатор «Брейнфака» на языке «Эр», никаких оптимизаций, кроме преподсчёта переходов. Даже на версию без поддержки вложенных циклов ушло прилично времени — некоторые вещи у меня пока со скрипом идут. Зато воспользовался разными структурами данных и сделал класс на RC (в языке «Эр» три встроенных способа работы с классами).
Комментировать
15 июня 2017 21:27

Аналог defer в языке R

В Гоу есть интересная конструкция (defer) — её содержимое выполняется, когда заканчивает работу функция, в которой эта конструкция объявлена, очень удобно память освобождать или другие ресурсы. Я накидал небольшой пример, чтобы было понятно:
package main

import (
	"bufio"
	"fmt"
	"os"
)

func readFile(filename string) (out []string) {
	file, _ := os.Open(filename)
	defer file.Close()

	b := bufio.NewReader(file)

	for {
		if str, err := b.ReadString('\n'); err != nil {
			break
		} else {
			out = append(out, str)
		}
	}

	return out
}

func main() {
	var lines []string

	for _, line := range readFile("/etc/passwd") {
		if line[0] != '#' {
			lines = append(lines, line)
		}
	}

	fmt.Println(lines)
}
В примере одна функция построчно читает файл и возвращает массив строк. Её использует основная функция (main), чтобы прочитать файл с информацией о пользователях в системе, удалив оттуда комментарии — строки, начинающиеся с «#». Обработку ошибок я не стал делать — и без этого длинновато вышло.

В фунции чтения файла блок defer вызовется как только мы покинем функцию и закроет используемый файл. Такой способ лучше, чем отсутствующий «Гоу» блок try…finally, так как позволяет указать способ освобождения ресурса очень близко к началу его использования.

Есть языки, которые, на мой взгляд, решают эту задачу ещё лучше (например, Пайтон со своим with), но у Гоу своя атмосфера и выбранное решение отвечает духу языка.

«Эр» на «Гоу» совсем не похож, у языков совершенно разные идеологии, поэтому я очень удивился, обнаружив в «Эр» тот же подход, что выбран в «Гоу».Тот же пример на «Эре»:
readFile <- function(filename) {
	f <- file(filename, 'r')
	on.exit({
		close(f)
	})

	return(readLines(f))
}

lines <- readFile('/etc/passwd')
print(lines[!grepl('^#', lines)])
Конструкция on.exit делает тут ровно то же, что defer в «Гоу». Нельзя не заметить, что программа стала гораздо компактнее, но в многословности Гоу обвинить нельзя — всё-таки он более низкоуровневый, плюс статически типизированный, отсюда и более подробный код.
2 комментария
12 июня 2017 20:04

ООП в R

Я думал, нет, даже надеялся, что присваивания в «Эр» единственная запутанная вещь. Не тут-то было — с ООП всё гораздо хитрее. Я и раньше видел языки, где несколько систем типов (Пайтон, Джаваскрипт), но в «Эр» есть три встроенные системы (S3, S4, RC (она же R5)) и несколько реализумых через внешние модули — например R6 и R.oo.

Я надеялся, что это отражение некой эволюции, но нет, некоторые апологеты языка рекомендуют использовать разные реализации в разных случаях, говорят, что каждая из систем несёт в себе определённые удобства.

Удобства я пока не ощутил, каждая из система плоха, на мой вкус, зато изучая здешние объектные модели, наткнулся на интересное.

Каждая функция создаёт, как обычно, свою зону видимости, насколько я понял, тут она зовётся «окружением», причём из вложенной функции можно обращаться в окружения выше, если я правильно понимаю, сколь угодно далеко, пока не упрёшься в глобальное окружение — верхний уровень программы.

Самое интересное, что окружениями можно манипулировать — это обычные объекты, которые содержат в себе текущие переменные. В итоге сэмулировать собственный класс без затей и претензий можно вот так:
NewCat <- function() {
	phrase <- 'Meow'

	say <- function() {
		print(phrase)
	}

	environment()
}

cat = NewCat()
cat$phrase # Meow
cat$say() # Meow
В «Эр» функции возвращают последнее значение, тут последним создаётся объект окружения, который возвращает в себе свою зону видимости и с которым можно работать как со списком (доллар — такой синтаксический сахар обращения к элементу списка).

При желании достаточно многое можно сделать с таким подходом (наследование, например), но я всё же буду изучать более естественные способы создания объектов.
Комментировать
1 июня 2017 15:55

Присваивания в R

Когда-то я изучал в год по языку, но в последнее время это моё установление сошло на нет, а жаль. В этом году нестерпимо захотелось посмотреть что-нибудь новенькое и уж не знаю как мой выбор пал на язык «Эр», предназначенный для статистической обработки данных. Наверное следовало бы его называть «Ар», но никто из русскоязычного сообщества его так не называет.

В языке много необычного, но почти сразу бросается в глаза наличие целой кучи операций присваивания, большинство из которых, правда, являются альтернативными способами записать одно и то же. Значительная часть операций несут в себе очень чёткую логику, а в двух из них такая восхитительная путаница, что даже опытные программисты на «Эре» иногда не знают как это всё работает. О них и хочу рассказать.

Сначала небольшой исторический очерк.

В далёком 1964 году на свет появился язык программирования APL — функциональный язык программирования, предтеча разных там «Матлабов» и иже с ними. Язык вводил для своих нужд целую кучу специальных значков в качестве операторов, так что программисты даже использовали специальные накладки на клавиатуры, либо рисовали спецсимволы фломастерами.

Вот так, например, выглядит на «АПЛе» гиковская игра «Жизнь»:
life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
Стрелка слева от слова «life» — операция присваивания, примерно в таком виде она по наследству перешла во многие математические языки, в том числе и в «Эр». Обычное «равно» же в «Эре» использовалось для другой цели — присвоения значений именованным параметрам:
op <- function (..., func) print(get(func)(...))
op(1, 2, 3, 4, 5, func = "sum") # =15
op(4, 2, func = "/") # =2
Пример выше иллюстрирует использование обоих операторов — стрелкой мы присваиваем переменной тело анонимной функции, которая принимает неограниченное количество параметров и один именованный параметр, а ниже указываем значение именованного параметра через «равно».

Как видите, символ деления вполне подходит в качестве имени функции, но об этом как-нибудь в другой раз.

Присваивание стрелкой и наличие в языке «равно», которым нельзя присваивать значения переменным, приводило новичков в замешательство, так что под влиянием более современных языков («Си», «Джавы» и так далее) случилось непоправимое — «равно» стало использоваться и для присваивания тоже, что только усугубило путаницу:
# Присваивание переменной «x» значения «1»
x = 1
f <- function(x) print(x)
# Вызов функции «f» со значением «5» аргумента «x»
f(x = 5)
# Вызов функции «f» с присваиванием переменной «x» значения «5»
# и передачей этого же значения в качестве первого аргумента
f((x = 5))
Казалось бы все операции выше выглядят вполне логично и «равно» тут исправно выполняет новую роль. Но увы. Дело в том, что «Эр» — язык «ленивых» вычислений, выражения в аргументах передаются в функцию не значениями, а промисами, которые будут вычислены в момент использования.

Это означает, в частности, что если аргумент не использовался в функции (выполнение пошло по какой-то ветке, где он не используется, например), то вычислен он не будет. Вот предельно упрощённый случай для иллюстрации:
x = 1
f <- function(x) TRUE
f((x = 5))
print(x) # выведется единица
Так как первый аргумент в функции использован не был, то переданное выражение вычислено не было, а значит и переменная «x» своего значения не изменила. Возможно новичкам и стало проще, но наравне с этим на поле языка рассыпалось несколько новых интересных грабель.

Есть и ещё проблемы. Операции «стрелка» и «равно» имеют разный приоритет и их лучше не использовать в цепочках присваиваний вместе:
# работает, вычисляется справа налево, трактуется как a = (b = 5)
a = b = 5
# работает, вычисляется справа налево, трактуется как a <- (b <- 5)
a <- b <- 5
# выдаст ошибку, так как «стрелка» имеет приоритет выше: (a <- b) = 5
a <- b = 5
# работает, так как «стрелка» имеет приоритет выше: a = (b <- 5)
a = b <- 5
Вообще, конечно, не всё так страшно — можно это всё либо понять (что почти никто не делает), либо запомнить несколько нехитрых правил (прочитав пару хороших книг по языку), либо набить шишки на практике (что чаще всего и происходит).
2 комментария
23 мая 2017 22:08

Счастливые билеты

Мы тут недавно с одним товарищем разговорились про точное количество «счастливых» билетов. В ответ я вспомнил, что как-то очень давно считал их количество на Перле — тогда короткие программы я предпочитал писать на нём. В алгоритмом я не заморачивался — там простой перебор, в комментариях есть указание, что выполняется он за три секунды.

На что товарищ прислал мне ссылку на выписку из статьей о счастливых билетах журнала «Квант». Там, помимо перебора, предлагается несколько методов вычисления, в частности есть даже интеграл: Вычисление через интеграл (12.78КиБ)
Вычисление количества шестизначных счастливых билетов через интеграл

Вообще статьи интересные, умели же раньше писать! Кстати, стало интересно насколько сейчас плох старый-добрый перебор на современных мощностях и интерпретаторах. Взял код из своей заметки в блоге, на пятом Перле и ПХП7 — 0,9 и 0,5 секунды соответственно, вместе с запуском интерпретатора.

Вариант на R, который я наскорую написал по мотивам второй статьи из подборки выглядит вот так:
N <- function (n, k) {
	if (n == 1)
		ifelse(k >= 0 & k <= 9, 1, 0)
	else
		sum(sapply(0:9, function (l) N(n-1, k-l)))
}

lucky <- function (n) {
	0 -> s
	for (k in 0:999) {
		N(3, k) -> v

		if (v == 0) {
			break
		}

		s + v * v -> s
	}

	s
}

print (lucky(3))
Выполняется вместе с запуском интерпретатора за треть секунды, если кому-то интересно, чуть медленнее интеграла. Можно было бы переписать его аккуратнее — накапливать значение N, а не вычислять заново каждый раз.
2 комментария
19 мая 2017 13:16