SICP - блеск и нищета LISP, монады...

Ikemefula Ikemefula
Очень интересная книга Абельсона под названием 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
Basil B
Basil B
10.01.2016 09:17
Ну, это в стиле "почитал я вашего Достоевского, вот что мне не нравится...". Достоевский от такой критики ничего не теряет, а сам критик выглядит дураком.
Ikemefula
Ikemefula
11.01.2016 08:09
Здравствуйте, Basil B, Вы писали:

BB>Ну, это в стиле "почитал я вашего Достоевского, вот что мне не нравится...". Достоевский от такой критики ничего не теряет, а сам критик выглядит дураком.


Сочувствую
woah
woah
16.01.2016 10:49
Здравствуйте, Ikemefula, Вы писали:

I>Собственно, если в кратце, (что бы отпугнуть оголтелых функционалистов), не нравится

I>1 примеры на Лиспе. Схемы там или еще какой диалект, собственно не сильно важно.

Собственно поэтому курс в MIT и Беркли уже лет 5 как читают на питоне.
https://news.ycombinator.com/item?id=3491142

Переработаная версия книги от Беркли доступна тут http://composingprograms.com/
От МИТа тут https://mitpress.mit.edu/index.php?q=books/introduction-computation-and-programming-using-python-0
dsorokin
dsorokin
17.01.2016 10:44
Здравствуйте, woah, Вы писали:

W>Собственно поэтому курс в MIT и Беркли уже лет 5 как читают на питоне.

W>https://news.ycombinator.com/item?id=3491142

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

Касательно блога, про рекурсию не понял ничего из написанного. Бред какой-то. Впрочем, учитывая как много программистов путаются, когда речь заходит о рекурсии, а тем более, о хвостовой рекурсии и хвостовых вызовах, то это абсолютно нормально.
elmal
elmal
17.01.2016 10:06
Здравствуйте, Ikemefula, Вы писали:

I>1 примеры на Лиспе. Схемы там или еще какой диалект, собственно не сильно важно.

Прелесть примеров на Лиспе — это то, что сам по себе этот язык ни черта не умеет. Там нет структур данных, там нет синтаксиса стандартного для ООП и т.д. И в результате показано, как из ничего можно сделать практически что угодно на весьма простом языке. Как, имея только функции, реализовывать ООП парадигму, классы, объекты, методы, наследования. И как имея ООП реализовывать функции.

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

А книга то не о лиспе. И не о функциональном программировании. Она как раз и описывает то, как различные концепции программирования связаны друг с другом, как одни выражаются через другие, и что возможно реализовать практически что угодно на любом языке. То есть книга программированию учит по большому счету. Ну и как интерпретаторы работают частично затрагивает.
Ikemefula
Ikemefula
17.01.2016 03:07
Здравствуйте, elmal, Вы писали:

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


Собственно, при переходе от Лиспа в любой реальный язык возникают ровно те же проблемы. Лисп с одной стороны предлагает самый минимум, с другой стороны Лисп слишком сильно отличается от всех остальных языков вместе взятых. Именно как язык. Это одна из сторон проблемы.

E>А книга то не о лиспе. И не о функциональном программировании. Она как раз и описывает то, как различные концепции программирования связаны друг с другом, как одни выражаются через другие, и что возможно реализовать практически что угодно на любом языке. То есть книга программированию учит по большому счету. Ну и как интерпретаторы работают частично затрагивает.


Это как бы понятно. Просто Лисп сам по себе накладывает очень жесткие ограничения, а через это очень непросто понять, как же вычисления ложатся на реальный вычислитель. А это еще сторона проблемы.