День третий (an investigation)

TASK
An Investigation. R and tail recursion. Lazy evaluation in R.

SOLUTION
With a Google's help i found this message: http://finzi.psych.upenn.edu/R/Rhelp02a/archive/73651.html
> Some functional languages have a feature called tail recursion that
> can provide performance improvements if you write your recursions
> to take advantage of it:
>
> http://en.wikipedia.org/wiki/Tail_recursion
>
> but I don't think R supports it. Is this likely to become available
> in R?
No. For a start, this is usually done by compilers, which we don't got.
In addition, it would be very difficult to do tail recursion optimization and not break most of the sys.* functions, which give explicit access to all the frames that would be optimized away.
-thomas

Alas, R doesn't have tail recursion optimization. That explains last error messages about stack fault. Now, what do they mean, when they write: "R is a functional language, with lazy evaluation"?
Here is the answer:

http://tolstoy.newcastle.edu.au/R/help/03b/0731.html
"...R is a functional language, with lazy evaluation and weak dynamic typing (a variable can change type at will: a <- 1 ; a <- "a" is allowed). Semantically, everything is copy-on-modify although some optimization tricks are used in the implementation to avoid the worst inefficiencies. Parameter passing is according to the "pass-by-value illusion", i.e. what is really getting passed down to a function is a "promise", which embodies the expression used in the call. This is at the core of the lazy evaluation mechanism: The result of the expression is not computed until needed. It also allows a function to get hold of the the expression itself: This is useful for labeling plots but it also allows some variants of "pass-by-name"-like semantics via evaluation in the environment of the caller..."

But... Extra!Extra! I found more sensational materials...
"Besides lazy evaluation in R is not really lazy evaluation!" http://www.postech.ac.kr/~gla/paper/R-ism-dec-8.ppt

CONCLUSIONS
So, my first impression, when i started this blog, was: "Incredibly! Such perfect program for data analysis, visualization, uses functional language." Now i see, R is not perfect.

День второй (lazy list)

ЗАДАЧА
Реализация ленивых списков и ленивых вычислений над ними.

РЕШЕНИЕ
Первоначально я сконструировал список так:

> nums_from <-function(n)
     c(function() n, 
       function() 
          c(function() n + 1, 
            function() nums_from(n + 2)))

Сразу же выяснил, что писать функции, работающие с ним не очень удобно:

> ints <- nums_from(1) 
> ints[[1]]()
[1] 1
> ints[[2]]()[[1]]()
[1] 2
> ints[[2]]()[[2]]()[[1]]()
[1] 3

Следующий вариант стал более удачным:

> nums_from <-function(n)               
     pairlist(head = function() n,                        
              tail = function() 
                 pairlist(head = function() n + 1,
                          tail = function() nums_from(n + 2)))
> ints <- nums_from(1) # ленивый список натуральных числел
> ints$head()
[1] 1
> ints$tail()$head()
[1] 2
> ints$tail()$tail()$head()
[1] 3

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

> nums_from <-function(n) c(n, c(n+1, nums_from(n + 2))) #1
> ints <- nums_from(1) #2
Ошибка: исполнение расположено слишком глубоко: неопределенная рекурсия / options(expressions=)?
> ?options
....
expressions:    sets a limit on the number of nested expressions that 
will be  evaluated. Valid values are 25...500000 with default 5000. 
If you increase it, you  may also want to start R with a larger protection 
stack; see --max-ppsize in  Memory. Note too that you may cause a segfault 
from overflow of the C stack, and on  OSes where it is possible you may 
want to increase that
.....

Так что #1 - если вычисления аргументов и ленивые, то непонятно, почему #2 - стек сносит. Т.е. стек сносит понятно почему - вычисления всё - таки производятся, при этом хвостовая реурсия, можно предположить, не оптимизируется. Тут определённо какие - то тонкости. С ними разберусь потом.

> take <- function(count, nums) {             
     if(count == 1) nums$head()             
     else  c( nums$head(), take(count - 1, nums$tail()) )
}
> take(6, ints)
[1] 1 2 3 4 5 6
> is.even <- function(num) num %% 2 == 0
> sieve <- function(cond, nums) {      
     if (cond(nums$head())) 
        pairlist(head = nums$head,                    
                 tail = function() sieve(cond, nums$tail()))
     else              
        sieve(cond, nums$tail())
}
> take(3, sieve( is.even, ints ))
[1] 2 4 6

В последнем вызове - sieve( is.even, ints )) уже лениво фильтруются чётные числа. Далее вычисляются 7 первых простых числел:

> nums_down_from <- function(n)       
     pairlist(head = function() n,              
              tail=function() pairlist(head = function() n - 1,   
                                       tail = function()
                                          nums_down_from(n - 2)))
> has.divider <- function(nums, dvding) {     
     if (nums$head() == 1) F     
     else if (dvding %% nums$head() == 0) T         
     else has.divider(nums$tail(), dvding) 
}
> is.prime <- function(num) {     
     if (num == 1) F      
     else {            
        nums <- nums_down_from(floor(sqrt(num)))           
        !has.divider(nums, num)      
     }
 }
> take(7, sieve( is.prime, ints ))
[1] 2 3 5 7 11 13 17

ВЫВОД
Второй предок R - Scheme. Вполне понятно моё желание поиграться с ленивыми списками и вычислениями. Я это сделал. Но результаты не очень - то и радуют. Похоже, хвостовая рекурсия съедает стек, а вместе с ним и все преимущества ленивости. Да, кстати, и memoization не реализована. Сегодняшний день породил больше вопросов чем ответов.

День первый (an arithmetic)

ЗАДАЧА
При некотором натуральном n числа 4n+5 и 9n+4 - точные квадраты. Доказать, что число 5n+4 делится на 29.

РЕШЕНИЕ
В действительности - это задача на вычеты, и не важно даже - точные квадраты первые два числа или нет. И вот почему:

9n + 4 - (4n + 5) = 5n - 1, 5n + 4 = 0 mod 29 
<=> 5n - 1 = 24 mod 29

Используя R проверим:

> ns <- 1:29 # а дальше повторы 
> ns[1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
> rst1 <- (4*ns +5) %% 29 
> rst1 # где - то здесь вычет первого квадрата
[1] 9 13 17 21 25 0 4 8 12 16 20 24 28 3 7 11 15 19 23 27 2 6 10 14 18 22 26 1 5
> rst2 <- (9*ns +4) %% 29 
> rst2 # где - то здесь вычет второго квадрата
[1] 13 22 2 11 20 0 9 18 27 7 16 25 5 14 23 3 12 21 1 10 19 28 8 17 26 6 15 24 4
> (rst2 - rst1) %% 29 # а это вычеты 5n - 1, ищем 24
[1] 4 9 14 19 24 0 5 10 15 20 25 1 6 11 16 21 26 2 7 12 17 22 27 3 8 13 18 23 28
> # Ага, есть такой остаток!

ВЫВОД
В незаконченном "The R Language Definition" пишут, что R происходит от APL и Scheme. Значит по линии APL он в родственных отношениях с J, K и прочими Q. Пусть возможности R по работе с многомерными данными и не столь изощрённы, но эта задачка - была моим первым опытом после установки, и "векторизация" очень понравилась. Кажется, R можно использовать для арифметических экспериментов.

БОНУС
Задача производит впечатление чего - то вырожденного, давалась школьникам на маткружке. В самом деле, не счёт же от них требовали. Очевидно, здесь есть решение "с вывертом". Вот оно:

(4*n+5) = a^2(9*n + 4) = b^2
9*a^2 - 4*b^2 = 29
(3*a - 2*b)*(3*a + 2*b) = 29

Из простоты 29 получаем n = 5

Запись вводная

Основные темы этих лабораторных записей:

• анализ данных
• программирование на языке R (и не только)
• R, как программа

За образец взяты записки inferno программиста. Мотивы те же. Формат записей следующий:
Задача - тема лабораторной
Решение - решение, как я его вижу на текущий момент
Вывод - оставлю как отдушину для графоманства )