Pull to refresh

Лучшая подарочная книга для начитанных фанатов JavaScript

Reading time 11 min
Views 27K
Original author: Angus Croll
Здравствуйте, уважаемые хаброжители!

Мы вынашиваем амбициозные планы по изданию вот такой книги:



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

Приятного чтения, и поучаствуйте пожалуйста в опросе!


Я написал книгу If Hemingway Wrote JavaScript. В ней я фантазирую, как 25 знаменитых прозаиков, поэтов и драматургов могли бы решать простые задачи на JavaScript. Это дань уважения моим любимым писателям и признание в любви языку JavaScript – ведь я не знаю, какой еще язык наделял бы программиста такой свободой, позволял раскрыть творческий потенциал, а также был бы настолько своеобразен, чтобы привлечь внимание великих литераторов.

В этом посте – оригинальный материал, которого нет в книге (считайте его «бонусом»). Это первый глубокий технический разбор решений, приписываемых каждому автору. Некоторые решения требуют более подробных объяснений, нежели другие.
Приятного чтения!

Часть 1: Простые числа

Задание: напишите функцию, возвращающую все простые числа вплоть до значения заданного аргумента.

1. Хорхе Луис Борхес

https://github.com/angus-c/literary.js/tree/master/book/borges/prime.js

// Они повествуют (я знаю) о пинаклях, флеронах и балюстрадах,
// о потаенных интервольтах и чудищах, вечно идущих вверх размашистым шагом 
 
var monstersAscendingAStaircase = function(numberOfSteps) {
  var stairs = []; stepsUntrodden = [];
  var largestGait = Math.sqrt(numberOfSteps);
 
  // Череда тварей карабкается по ступенькам;
  // шаг каждой следующей химеры шире, чем у предыдущей 
  for (var i = 2; i <= largestGait; i++) {
    if (!stairs[i]) {
      for (var j = i * i; j <= numberOfSteps; j += i) {
        stairs[j] = "stomp";
      }
    }
  
// Длиннолапые чудища не попадают по ступенькам, номера которых – простые числа 
  for (var i = 2; i <= numberOfSteps; i++) {
    if(!stairs[i]) {
      stepsUntrodden.push(i);
    }
  }
 
  // Вот и наш ответ
  return stepsUntrodden;
};


Решение Борхеса – вариант алгоритма «Решето Эратосфена», в котором кратные каждого известного простого числа помечаются как составные (непростые) числа. В таком случае, у Борхеса длиннолапые чудовища занимают места делителей. Каждое чудище делает шаг на одну ступеньку шире, чем шедшее за ним: 2, 3, 4, 5… вплоть до квадратного корня из числа, соответствующего наивысшей ступеньке. (почему-то Борхес позволяет карабкаться по лестнице и чудищам с неровным шагом). Те ступеньки, на которые никто не встанет – и есть простые числа.



Обратите внимание на строку 12: каждый монстр начинает восхождение с квадрата своего множителя:

for (var j = i * i; j <= numberOfSteps; j += i) {


Дело в том, что составные числа между n и n² уже будут пройдены чудищами с более мелким шагом.

2. Льюис Кэрролл

https://github.com/angus-c/literary.js/tree/master/book/carroll/prime.js

function downTheRabbitHole(growThisBig) {
  var theFullDeck = Array(growThisBig);
  var theHatter = Function('return this/4').call(2*2);
  var theMarchHare = Boolean('The frumious Bandersnatch!');
 
  var theVerdict = 'the white rabbit'.split(/the march hare/).slice(theHatter);
 
  // в море слез…
  eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {\
      theMarchHare = 1;\
      theVerdict.push(theHatter);\
      ' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
  );
 
  return theVerdict;
}


Как и творчество Кэрролла, его код — смесь загадки и нонсенса. Давайте построчно в нем разберемся, начиная с объявления переменных.
В принципе, строка 2 вполне традиционна (если закрыть глаза на использование конструктора Array). Кэрролл создает пустой массив, длина которого совпадает с сообщенным аргументом. Он называется theFullDeck
, поскольку в решении воображается колода карт, причем в итоге рубашкой вниз будут лежать лишь те из них, что соответствуют простым числам.

В строке 3 создается функция (с применением малоиспользуемого конструктора Function), а затем эта функция вызывается при помощи call, при этом 2 * 2 (т.е. 4) передается как аргумент this. Следовательно, theHatter инициализируется со значением 1.

В строке 4 theMarchHare
устанавливается в true
. Когда конструктор Boolean вызывается как функция, его аргумент преобразуется в true
или false
. В таком случае непустая строка ‘The frumious Bandersnatch!’ преобразуется в true
. (Кстати, такое присваивание не очень-то здесь нужно, поскольку в строке 10 theMarchHare
присваивается новое значение).

Наконец – вероятно, это верх абсурда – в строке 6 Кэрролл присваивает theVerdict
пустой массив, и делает это максимально иносказательно:


var theVerdict = 'the white rabbit'.split(/the march hare/).slice(theHatter);


Здесь не так много бросается в глаза. Аргумент для split
– это регулярное выражение, не совпадающее с ‘the white rabbit’, поэтому при вызове split
получаем массив, в котором содержится лишь ‘the white rabbit’. Последующая операция slice
заносит в копию массива все элементы исходного массива, начиная с заданного индекса. Поскольку в нашем одноэлементном массиве нет индекса 1 (таково значение theHatter
), никакие члены из него не копируются, и у нас получается пустой массив.

Проще говоря, можно переписать объявления переменных вот так:

function downTheRabbitHole(growThisBig) {
  var theFullDeck = Array(growThisBig);
  var theHatter = 1;
  var theMarchHare = true;
  var theVerdict = [];


А теперь полный угар:

// в море слез…
eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {\
    theMarchHare = 1;\
    theVerdict.push(theHatter);\
    ' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
);


Прежде, чем перейти к пресловутой функции eval
, давайте поговорим о вложенных инструкциях join
. Функция join превращает массив в строку, при этом ее аргумент служит клеем между элементами массива. Если вызвать join
применительно к пустому массиву, получится строка, состоящая из сплошного клея (повторенная n – 1 раз, где n – длина массива):

Array(4).join('hi'); //'hihihi'


Если вложить друг в друга два join, то вкладывается и соответствующий клей:

Array(4).join('A' + Array(4).join('a')); //'AaaaAaaaAaaa'


Когда же мы включаем в клей переменные, начинаем понимать, что к чему:

var arr = [], count = 0;

Array(4).join('arr.push(' + Array(4).join('count++,') + '-1);');
//"arr.push(count++,count++,count++,-1);arr.push(count++,count++,count++,-1);arr.push(count++,count++,count++,-1)"


Теперь, растолковав JavaScript, как генерировать JavaScript, остается только придумать, как все это запустить. Заходим в гнусную eval


var arr = [], count = 0;
eval(Array(4).join('arr.push(' + Array(4).join('count++,') + '-1);'));
arr; //[0, 1, 2, -1, 3, 4, 5, -1, 6, 7, 8, -1]
…так вот каким образом Кэрролл автоматически генерирует программу для работы с простыми числами. Давайте еще раз взглянем на этот код:
	// в море слез...
eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {\
    theMarchHare = 1;\
    theVerdict.push(theHatter);\
    ' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
);
Аргумент к eval (после форматирования) принимает вид:
	if (!theFullDeck[++theHatter]) {
  theMarchHare = 1;
  theVerdict.push(theHatter);
  theFullDeck[++theMarchHare * theHatter] = true;
  theFullDeck[++theMarchHare * theHatter] = true;
  theFullDeck[++theMarchHare * theHatter] = true;
}
if (!theFullDeck[++theHatter]) {
  theMarchHare = 1;
  theVerdict.push(theHatter);
  theFullDeck[++theMarchHare * theHatter] = true;
  theFullDeck[++theMarchHare * theHatter] = true;
  theFullDeck[++theMarchHare * theHatter] = true;
}
if (!theFullDeck[++theHatter]) {
  theMarchHare = 1;
  theVerdict.push(theHatter);
  theFullDeck[++theMarchHare * theHatter] = true;
  theFullDeck[++theMarchHare * theHatter] = true;
  theFullDeck[++theMarchHare * theHatter] = true;
}
// etc...


…и т.д. (Сгенерированный таким образом код может получиться очень длинным. Запросив все простые числа вплоть до 100, получим более 10 000 строк кода – можете себе представить, как это скажется на производительности – но для Страны Чудес, полагаю, сойдет)

Итак, постепенно все проясняется. Оказывается, Кэрролл использовал вариант того самого решета Эратосфена, которое мы видели у Борхеса. theFullDeck
– это массив со всеми числами, которые необходимо проверить, theHatter
и theMarchHare
– вложенные счетчики, умножаемые при каждом инкременте, чтобы сгенерировать все возможные составные числа. Все карты, чьи индексы – составные числа, переворачиваются (поскольку theFullDeck
с таким индексом равен true
). Открытыми остаются лишь те карты, которым соответствуют простые числа.



3. Дуглас Адамс

https://github.com/angus-c/literary.js/tree/master/book/adams/prime.js

// Вот я, мозг размером с планету, и они просят меня написать на JavaScript...
function kevinTheNumberMentioner(_){
  l=[]
  /* почти безвредно --> */ with(l) {
 
    // извините за все это, у моей вавилонской рыбки сегодня мигрень...
    for (ll=!+[]+!![];ll<_+(+!![]);ll++) {
      lll=+!![];
      while(ll%++lll);
      // У меня в правом полушарии все болит от этих чертовых точек с запятой
      (ll==lll)&&push(ll);
    }
    forEach(alert);
  }
 
  // ну так вы же точно делать не будете...
  return [!+[]+!+[]+!+[]+!+[]]+[!+[]+!+[]];
}


Читать код Адамса в целом сложно, так как он многое заимствует из jsfuck – хитроумного, но убийственно лаконичного языка, в котором используется всего 6 символов. Тем не менее, это настоящий JavaScript — если вы запустите его в консоли, все сработает. Давайте переведем простой фрагмент:

for (ll=!+[]+!![];ll<_+(+!![]);ll++) {


Здесь видим цикл for
, а ll и _ — имена переменных. Все остальное – литерал и форменный вынос мозга.
В первом условии этой инструкции ll получает значение !+[]+!![]
. Разобрав это выражение, видим в нем два пустых литерала массива. Перед первым стоит +, из-за которого массив принудительно приводится к числу 0. Прямо перед ним стоит!, принудительно приводящий 0 к его булевской противоположности, то есть, к true
. Итак, !+[]
результирует в true
.

Теперь рассмотрим второй литерал массива. Ему предшествуют два !!
, что попросту принудительно приведет его к булеану. Поскольку массивы – всегда объекты, булеан массива всегда равен true
. Итак, !![]
всегда дает true
.

Сложив два этих выражения, !+[]+!![]
, фактически, имеем true + true
. Здесь + принудительно приводит оба операнда к числу 1, поэтому окончательный результат всего выражения равен 2.
Два остальных условия цикла for
теперь понятны без труда. Опять же, имеем !![]
, на сей раз перед ним идет +, принудительно приводящий true
к 1. Итак, ll<_+(+!![])
дает ll < _ + 1
.
Последнее условие – это обычный постфикс JavaScript, поэтому весь цикл for
дает:

for (ll = 2; ll < _ + 1; ll++) {

А вот все решение, переведенное на обычный мирской JavaScript (переменным я также дал более осмысленные имена)

// Вот я, мозг размером с планету, и они просят меня написать на JavaScript…
function kevinTheNumberMentioner(max){
  var result = [];
  /* почти безвредно --> */ with(result) {
 
    // извините за все это, у моей вавилонской рыбки сегодня мигрень...
    for (candidate = 2; candidate < max + 1; candidate++) {
      var factor = 1;
      while (candidate % ++factor);
      // У меня в правом полушарии все болит от этих чертовых точек с запятой
      (candidate == factor) && push(candidate);
    }
    forEach(alert);
  }
 
  // ну так вы же точно делать не будете...
  return '42';
}


Славно, теперь перед нами, по крайней мере, узнаваемый JavaScript, но в нем по-прежнему таятся кое-какие странности.
Инструкция with
относится к наиболее предосудительным с точки зрения «блюстителей чистоты JavaScript», но все-таки в строке 3 – именно она. JavaScript попытается заключить все свойства, на которые не указывают ссылки, в блоке with
заданного объекта. Следовательно, неприкаянные методы массива push
and forEach
окажутся в области видимости result
.

Еще одна любопытная инструкция — цикл while
в девятой строке. У этого цикла нет тела, поэтому factor
просто продолжает увеличиваться на единицу, пока не станет нацело делиться, давая candidate
в качестве частного. В следующей строке проверяется, равны ли теперь значения candidate
и factor
. В таком случае, у числа нет меньших делителей, следовательно, оно простое и добавляется к result
.
В строке 13 перебираем результаты и во всеуслышание объявляем каждое простое число в виде alert
. Наконец, программа возвращает 42.



4. Чарльз Диккенс

https://github.com/angus-c/literary.js/tree/master/book/dickens/prime.js

function MrsPrimmerwicksProgeny(MaxwellNumberby) {
  Number.prototype.isAPrimmerwick = function() {
    for (var AddableChopper = 2; AddableChopper <= this; AddableChopper++) {
      var BittyRemnant = this % AddableChopper;
      if (BittyRemnant == 0 && this != AddableChopper) {
        return console.log(
          'It is a composite. The dear, gentle, patient, noble', +this, 'is a composite'),
          false;
      }
    }
    return console.log(
      'Oh', +this, +this, +this, 'what a happy day this is for you and me!'),
      true;
  }
 
  var VenerableHeap = [];
  for (var AveryNumberby = 2; AveryNumberby <= MaxwellNumberby; AveryNumberby++) {
    if (AveryNumberby.isAPrimmerwick()) {
      VenerableHeap.push(AveryNumberby);
    }
  }
  return VenerableHeap;
}


Что, если бы вы могли спросить у числа, простое ли оно:

6..isPrime(); // ложь
7..isPrime(); // истина


Что бы сделал Чарльз Диккенс? Расширил бы Number.prototype
. Его собственное расширение называется isAPrimmerwick
(на самом деле, у всех объектов здесь причудливые диккенсовские имена) и определяется в строках 2-14. В строках 17-21 мы просто спрашиваем каждое число, простое ли оно, и добавляем простые числа в массив с результатами, который называется VenerableHeap
.
Логика метода isAPrimmerwick
в основном проста. Делим имеющееся число на все возможные делители. Если то или иное число делится без остатка, то является составным, в противном случае — простым.

В каждой инструкции возврата (строки 6 и 11) есть пара любопытных моментов. Во-первых, поскольку число вызывает метод в его же прототипе, на него можно сослаться при помощи this
(но с префиксом +, чтобы принудительно привести его от числового объекта к примитиву). Во-вторых, Диккенс использует оператор-запятую, чтобы одновременно вызвать console.log
и вернуть булевское значение.



5. Дэвид Фостер Уоллес

https://github.com/angus-c/literary.js/tree/master/book/wallace/prime.js

var yearOfTheLighteningQuickAtkinSieve = function(tops) {
  //B.P. #40 07-14
  //ELEPHANT BUTTE, NM
  var NSRS/*[1]*/ = [0,0,2,3];
  /* два конкурентных цикла мобилизуются так, что переменные i и j (каждая с
  исходным значением 1) увеличиваются на 1 при каждом инкременте 
 (правда, во вложенном виде). */
  for(var i = 1; i < Math.sqrt(tops); i++){
    for(var j = 1; j < Math.sqrt(tops); j++){
      if (i*i + j*j >= tops) {
        break;
      }
      /* Две переменные (т.e. i и j) подставляются в первую квадратичную функцию quadratic,
     и результат ее присваивается дополнительной переменной (n). */
      var n = 4*i*i + j*j;
      /* Если дополнительная переменная (т.e. n) деленная на 12, даст в остатке
      1 или 5, то у значения с этим индексом (т.e. у n) меняется знак [2]. */
      if(n <= tops && (n%12 == 1 || n%12 == 5)){
        NSRS[n] = NSRS[n] ? 0 : n;
      }
      /* Теперь мы (т.e. JavaScript) подходим ко второй квадратичной функции, and again the result
     и результат вновь присваивается (существующей) переменной n. */
      n = 3*i*i + j*j;
      /* Хотя переменная (т.e. n) вновь делится на 12, на сей раз остаток
      сравнивается с 7 для определения того, должен ли у значения с данным 
  индексом(т.e. у n) 
      меняться знак */
      if(n <= tops && (n % 12 == 7)){
        NSRS[n] = NSRS[n] ? 0 : n;
      }
      /* Теперь вы (т.e. читатель), испытываете чувство нерешительности и раскаяния,
 тем не менее, мы (т.e. JavaScript) еще не закончили. Как и следовало ожидать, теперь в ход
      идет третья квадратичная функция и(не менее предсказуемо) ее значение присваивается (уже
      уже поистрепавшейся) переменной n. */
      n = 3*i*i - j*j;
      /* Единственный интересный момент в третьей операции деления (однако и самый 
      удручающий) заключается в том, что она происходит лишь тогда, когда первая переменная
 в цикле (i) оказывается больше
      т.e. не меньше (или равна) второй переменной цикла (j) [3]. */
      if (i>j) {
        if((n <= tops) && (n % 12 == 11)){
          NSRS[n] = NSRS[n] ? 0 : n;
        }
      }
    }
  }
  /* В полуобморочном состоянии (но не доверяя фильтру кольцевой факторизации) мы
  (т.e. JavaScript) теперь предварительно определяем как составные
 все без исключения простые множители, без учета их актуального статуса: простые ли они
(т.е не составные) или составные (т.е. не простые)
*/
  for(i = 5; i < Math.sqrt(tops); i++){
    if(NSRS[i] == 1){
      for(j = i*i; j < tops; j += i*i){
        NSRS[j] = 0;
      }
    }
  }
  return NSRS.filter(Number); // [4]
}
/*
[1] Числовая система хранения и поиска информации.
[2] То есть значения, соответствующие текущему индексу [a] устанавливаются в 0, а значения 0 устанавливаются в текущие индексы.
[3] В противном случае каждый релевантный индекс [a] менял бы знак дважды.
[4] `Array.prototype.filter` будучи функцией высшего порядка, определяется в стандарте EcmaScript-262 (5-я
версия) [b]. Поскольку `Number` - это встроенная в язык функция, преобразующая любое значение в число. а Array.prototype.filter
отклоняет ложные (т.e. неистинные) значения, значения 0, будучи ложными (т.e. неистинными) не
будут включаться в массив, возвращаемый `Array.prototype.filter`.
 
[a] т.e. индекс, на котором рассматриваемая квадратичная функция результирует в true.
[b] http://es5.github.io/#x15.4.4.20
*/


Благодаря пространным комментариям, которыми так известен Уоллес, рассказывать особенно нечего — надо только отметить, что в основе его решения лежит сильно оптимизированное (и слишком сложное, чтобы вдаваться здесь в объяснения) решето Эткина.

Код особенно интересен изысканной логикой и уоллесовским точным, но непринужденным стилем. Однако в строке 54 есть и интересный оборот JavaScript:

return NSRS.filter(Number); // [4]


Результат — NSRS
. Здесь это разрежённый массив, содержащий все простые числа, которые, однако, перемежаются с неопределенными значениями (спереди он заполнен нулями):

[0, 0, 2, 3, undefined, 5, undefined, 7/*, etc.. */]


Функция Array.prototype.filter
создает новый массив, в котором содержатся лишь те элементы исходного массива, для которых заданная функция возвращает значение true
. Здесь речь идет о Number
, встроенной в язык функции, которая пытается принудительно привести свой аргумент к числу. Number
принудительно приводит undefined
к NaN
, оставляя все настоящие числа нетронутыми. Поскольку оба значения: NaN
и 0 означают «ложь», вновом массиве будут содержаться только простые числа:

[0, 0, 2, 3, undefined, 5, undefined, 7].filter(Number); //[2, 3, 5, 7]


Заключение

Вот и все. Надеюсь, вам понравилось.
Only registered users can participate in poll. Log in, please.
Vox populi
39.08% Переводите, куплю дорого, прочитаю с удовольствием 111
24.3% Такие вещи лучше читать в оригинале 69
33.45% Не зацепило 95
3.17% Я девушка, подарю возлюбленному программеру 9
284 users voted. 150 users abstained.
Tags:
Hubs:
+18
Comments 11
Comments Comments 11

Articles

Information

Website
piter.com
Registered
Founded
Employees
201–500 employees
Location
Россия