Очень интересная книга Абельсона под названием SICP. Широко известна в узких кругах некоторого подмножества программистов. В очередной раз пересматривая некоторые примеры сформулировал, наконец, чем же она мне не нравится(кроме тех моментов, где она мне нравится).

Собственно, если в кратце, (что бы отпугнуть оголтелых функционалистов), не нравится
1 примеры на Лиспе. Схемы там или еще какой диалект, собственно не сильно важно.
2 изложение с забеганием вперёд — авторы увлеклись рекурсией, что изложили материал рекурсивно
3 отказ от рассмотрения вычислений в самом железе. Потому собтсвенно и приходится прибегать к фокусам навроде 'а просто есть хвостовая рекурсия' и вводить концепции 'линейная рекурсия', 'рекурсивная итерация'.
4. путаница между рекурсиями — масло масляное.

Книга, с одной стороны, подает очень важный материал. С другой стороны там очень интересные рассуждение в стиле Журавля — размахивание руками, ногами и разными другими частями тела. В первой главе вводятся два типа процессов вычислений — рекурсия и рекурсивная итерация. Здесь автор прибегает к диаграмам последовательностей, деревьям и причим фокусам. В самом конце, как бы признавая тупиковость ситуации, он объясняет 'просто там хвостовая рекурсия'.

На самом деле если взглянуть с т.з. процессора у нас есть следующие фокусы — обычный цикл с простой логикой или же обычный цикл с логикой на изменяемом состоянии. То есть, вся разница между рекурсией и рекурсивной итерацией примерно такая — рекурсивная итерация сводится к конечному автомату, рекурсия же сводится к конечному автомату с магазинной памятью. В терминах императивных языков у нас получается или простой цикл навроде while, или более сложный с операциями на списке-массиве-очереди-стеке. В терминах всяких разных грамматик у нас выходит или регулярная грамматика или контекстно-свободная.

Что касается рекурсии, то, как мы знаем, процессор про рекурсию ничего не знает. Фактически все чем занят процессор, это выполнение код вида

var state = ...;

while(true) {
  state = f(state);
}

где f простая однозначная нерекурсивная функция. На примере факториала, из Абельсона, или фибоначчи, там же, не сильно интересно. А вот на примере ханойских башен очень даже интересно. Контраст очень сильный:

//простейшая рекурсивная реализация - рекурсивный процесс в терминологии Абельсона
function hanoi(a,z,depth, intermediate) { 
                                 /* 0 */
    if(depth == 1) { 
        z.push(a.pop()); 
        return; 
    } 

    hanoi(a,intermediate,length-1, z); 
        hanoi(a, z, 1, intermediate);      /* 1 */
    hanoi(intermediate,z,length-1, a); /* 2 */
        return;                            /* 3 */ 
}

Вроде всё просто. Но фокус в том, что если переделать этот вариант в итерационный, все будет гораздо интереснее:

//итерационная реализация (есть реализация в виде рекурсивной итерации, но я решил не углубляться в это кунгфу)
function hanoi(A,Z,T) {
    var stack = [];

    stack.push({a:A, z:Z, t:T, height:A.length, code:0});

    while(stack.length > 0) {
        var state = stack.slice(-1)[0]; // top or peek

        switch(state.code){
            case 0: {
                if(state.height == 1) {
                    state.z.push(state.a.pop());
                    state.code = 3;
                    continue;
                }
                stack.push({a:state.a, z:state.t, t:state.z, height:state.height - 1, code:0});
                state.code++;
                continue;
            }
            case 1: {
                stack.push({a:state.a, z:state.z, t:state.t, height:1, code:0});
                state.code++;
                continue;
            }
            case 2: {
                stack.push({a:state.t, z:state.z, t:state.a, height:state.height - 1, code:0});
                state.code++;
                continue;
            }
            case 3: {
                stack.pop();
                continue;
            }
        }
        console.assert(false);
    }
}

Собственно именно так и работает процессор. В Абельсоне эта часть изложена в стиле Журавля. Не вижу сильной проблемы, почему товарищи не показали эту разницу, вроде как сам Лисп именно в таких вариантах не мешает.

Где именно мешает сам лисп — структуры навроде массива, хеш-таблицы и тд. Все эти приседания реализуются в лиспе через 'голова-хвост', 'голова-тело-хвост' и разные сорта списко-деревьев. Разумеется, есть диалекты лиспа, где полно всяких интринсиков навроде массивов и прочих интересных вещей. Сути это не меняет, только стиль меняется.
Самая главная проблема с лиспом — он 'не нужен' и джуниор не имеет возможности учиться на интересных и полезных вещах навроде 'двигать квадраты по экрану' или 'рисовать хвост у мыши'.

Собтсвенно, востребован именно SICP, но на JavaScript или Python, с некоторых освещением, как и почему работает процессор.

P.S. Любителям монад — во втором варианте почти что монада State. Есть вариант 1 к 1 перепилить на рекурсивную итерацию, используя иммутабельные структуры данных, получится именно она — монада State

Очень интересная книга Абельсона под названием SICP. Широко известна в узких кругах некоторого подмножества программистов. В очередной раз пересматривая некоторые примеры сформулировал, наконец, чем же она мне не нравится(кроме тех моментов, где она мне нравится).

Собственно, если в кратце, (что бы отпугнуть оголтелых функционалистов), не нравится
1 примеры на Лиспе. Схемы там или еще какой диалект, собственно не сильно важно.
2 изложение с забеганием вперёд — авторы увлеклись рекурсией, что изложили материал рекурсивно
3 отказ от рассмотрения вычислений в самом железе. Потому собтсвенно и приходится прибегать к фокусам навроде 'а просто есть хвостовая рекурсия' и вводить концепции 'линейная рекурсия', 'рекурсивная итерация'.
4. путаница между рекурсиями — масло масляное.

Книга, с одной стороны, подает очень важный материал. С другой стороны там очень интересные рассуждение в стиле Журавля — размахивание руками, ногами и разными другими частями тела. В первой главе вводятся два типа процессов вычислений — рекурсия и рекурсивная итерация. Здесь автор прибегает к диаграмам последовательностей, деревьям и причим фокусам. В самом конце, как бы признавая тупиковость ситуации, он объясняет 'просто там хвостовая рекурсия'.

На самом деле если взглянуть с т.з. процессора у нас есть следующие фокусы — обычный цикл с простой логикой или же обычный цикл с логикой на изменяемом состоянии. То есть, вся разница между рекурсией и рекурсивной итерацией примерно такая — рекурсивная итерация сводится к конечному автомату, рекурсия же сводится к конечному автомату с магазинной памятью. В терминах императивных языков у нас получается или простой цикл навроде while, или более сложный с операциями на списке-массиве-очереди-стеке. В терминах всяких разных грамматик у нас выходит или регулярная грамматика или контекстно-свободная.

Что касается рекурсии, то, как мы знаем, процессор про рекурсию ничего не знает. Фактически все чем занят процессор, это выполнение код вида

var state = ...;

while(true) {
  state = f(state);
}

где f простая однозначная нерекурсивная функция. На примере факториала, из Абельсона, или фибоначчи, там же, не сильно интересно. А вот на примере ханойских башен очень даже интересно. Контраст очень сильный:

//простейшая рекурсивная реализация - рекурсивный процесс в терминологии Абельсона
function hanoi(a,z, height, t) { 
                            /* 0 */
    if(height == 1) { 
        z.push(a.pop()); 
        return; 
    } 

    hanoi(a,t,height-1, z); /* 0 */
    hanoi(a, z, 1, t)  /* 1 */
    hanoi(t,z,height-1, a); /* 2 */
               /* 3 */
}

Вроде всё просто. Но фокус в том, что если переделать этот вариант в итерационный, все будет гораздо интереснее:

//итерационная реализация (есть реализация в виде рекурсивной итерации, но я решил не углубляться в это кунгфу)
function hanoi(A,Z,T) {
    var stack = [];

    stack.push({a:A, z:Z, t:T, height:A.length, code:0});

    while(stack.length > 0) {
        var state = stack.slice(-1)[0]; // top or peek

        switch(state.code){
            case 0: {
                if(state.height == 1) {
                    state.z.push(state.a.pop());
                    state.code = 3;
                    continue;
                }
                stack.push({a:state.a, z:state.t, t:state.z, height:state.height - 1, code:0});
                state.code++;
                continue;
            }
            case 1: {
                stack.push({a:state.a, z:state.z, t:state.t, height:1, code:0});
                state.code++;
                continue;
            }
            case 2: {
                stack.push({a:state.t, z:state.z, t:state.a, height:state.height - 1, code:0});
                state.code++;
                continue;
            }
            case 3: {
                stack.pop();
                continue;
            }
        }
        console.assert(false);
    }
}

Собственно именно так и работает процессор. В Абельсоне эта часть изложена в стиле Журавля. Не вижу сильной проблемы, почему товарищи не показали эту разницу, вроде как сам Лисп именно в таких вариантах не мешает.

Где именно мешает сам лисп — структуры навроде массива, хеш-таблицы и тд. Все эти приседания реализуются в лиспе через 'голова-хвост', 'голова-тело-хвост' и разные сорта списко-деревьев. Разумеется, есть диалекты лиспа, где полно всяких интринсиков навроде массивов и прочих интересных вещей. Сути это не меняет, только стиль меняется.
Самая главная проблема с лиспом — он 'не нужен' и джуниор не имеет возможности учиться на интересных и полезных вещах навроде 'двигать квадраты по экрану' или 'рисовать хвост у мыши'.

Собтсвенно, востребован именно SICP, но на JavaScript или Python, с некоторых освещением, как и почему работает процессор.

P.S. Любителям монад — во втором варианте почти что монада State. Есть вариант 1 к 1 перепилить на рекурсивную итерацию, используя иммутабельные структуры данных, получится именно она — монада State