Опыт шести клавиатур

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

Clojure, emacs, slime

Очень часто наблюдаю в своём окружение определённые проблемы с тем, как заставить работать совместно clojure и emacs. Собственно, оно и не мудрено, так как большая часть tutorial-ов на эту тему обязательным образом используют систему пакетов elpa (где все пакеты устарели уже очень давно), и рекомендуют использовать clojure-swank для запуска clojure (которая не хочет очевидным способом решать эту задачу, и заставляет плясать с бубном).

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

Перед началом работы вы имеете какой-нибудь линукс, с установленным emacs-ом и openjdk. Они устанавливаются для fedora:

sudo yum install emacs java

если у вас ubuntu, то запустите synaptics и просто найдите эти пакеты в списке (на сколько я помню пакеты имеют другие имена).

Установка leiningen

1. Загружаете установочный скрипт по этой ссылке: https://raw.github.com/technomancy/leiningen/stable/bin/lein
2. Далее вам необходимо открыть терминал и скопировать скачанный файл в одну из директорий, предназначенных для запуска приложений.
   

   sudo cp <загруженный файл> /usr/bin/
   

3. Затем необходимо дать эту файлу права на запуск.
   

   sudo chmod +x /usr/bin/lein
   

4. Готово.

Установка slime и clojure-mode

Есть как минимум три способа установить эти расширения emacs.

• elpa (очень всё устаревшее)
• руками (очень не удобно обновлять и переносить)
• el-get

Последний вариант представляет из себя инструмент, который содержит множество рецептов, позволяющих загружать исходные коды расширений автоматически. Это позволяет не только легко обновляться, но и иметь свой конфиг чистым, от огромного количества чужих кодов. Так как большинство расширений лежат просто в репозиториях, то вам нужно установить git (часто нужный вам пакет называется git-core). Так же для сборки slime необходимо, что бы был установлен пакет texlive.

Для установки el-get сделайте следующее:

1. Запустите emacs и откройте ваш .emacs файл (находится в домашней директории, открыть файл: C-x C-f).
2. Вставте в него следующий код:
   

   (add-to-list 'load-path "~/.emacs.d/el-get/el-get")
   (unless (require 'el-get nil t)
     (url-retrieve
      "https://github.com/dimitri/el-get/raw/master/el-get-install.el"
      (lambda (s)
        (end-of-buffer)
        (eval-print-last-sexp))))
   (setq el-get-verbose)
   (el-get 'sync '(slime clojure-mode))

   (require 'slime)
   (require 'clojure-mode)
   

3. Перезапустите emacs два раза, в первый запуск будет установлен el-get и будет написано об ошибках. Во второй остальные пакеты.

Первый проект

1. Создайте пустой проект.
   

   lein new
   

2. Добавьте в файл проекта зависимость от clojure-swank. Для этого приведите содержимое файла project.clj в созданном проекте к следующему виду:
   

   (defproject test "1.0.0-SNAPSHOT"
     :description "FIXME: write description"
     :dependencies [[org.clojure/clojure "1.2.1"]]
     :dev-dependencies [[swank-clojure "1.2.1"]])
   

3. Установите зависимости.
   

   lein deps
   

4. Запустите сервер с вашим проектом.
   

   lein swank

Подключение из emacs-а

1. Запустите emacs.
2. Выполните команду slime-connect (для этого надо нажать M-x (альт + x) и ввести команду).
3. Согласитесь со стандартным адресом и портом. Если вас предупредят о несовпадение версий, всё в порядке.
4. Откройте любой исходник на clojure и используйте.

Переход на Dvorak, фикс русской раскладки в OS X

Не верьте никому, кто говорит: "Программисты руками не работают".

Предпосылка

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

Что же делать, и как можно лишить себя этого пагубного, но хорошего навыка? Как себя сломать, и надо ли себе превозмочь? Нет. Можно просто научиться заново печатать с новой раскладкой. Так же за счёт более вменяемого расположения кнопок, есть шанс понизить нагрузку на руки.

Почему Dvorak, а не Colemak?

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

• более похожа на qwerty, а значит проще учиться;
• большинство shortcut-ов не изменяются;
• большая скорость набора (нигде кроме офф. сайта этого довода не видел);
• что-то ещё, что забыл, так как писал по памяти.

Собственно учитываю описанную выше предпосылку, первое преимущество быстро стало недостатком. Учитывая тот нюанс, что основная проблема у меня с левой рукой, главным образом из-за shortcut-ов (привет и тебе, emacs), то и второе преимущество становится недостатком. Таким образом среди бывших преимуществ остаётся лишь одно, и то, не проверяемо и сомнительно.

Переход

Процедура перехода на английский Dvorak много где описана,  например тут и она работает прекрасно. В случае же с русской раскладкой (а она тут при чём казалось бы?) возникает проблема: shortcut-ы в русской (и только русской) раскладке остались старыми. Работать с этим не возможно.

Решить эту проблему можно при помощи программы Ukelele, которая позволяет создать раскладку, которая будет работать так, как ожидается. У меня получилась такая раскладка: Russian - Dvorak Shortcut.bundle.zip. Для её установки надо распаковать архив и положить файл в /Library/Keyboard Layouts или ~/Library/Keyboard Layouts, после чего перелогиниться в систему и выбрать новую русскую раскладку.

Отзывы по прошествию нескольких недель

• Эта раскладка намного более удобна чем qwerty, очень хорошо заметно по тому, как редко ты тянешься до неудобных кнопок (y, b в раскладке qwerty, к примеру). А значит задача понизить нагрузку на руки выполнена.
• Это действительно помогает разучиться печатать. А значит задача переучиться выполнена.
• Shortcut-ы по первости просто убийственны, особенно то, что вставить и закрыть окно рядом.
• Компьютер стал значительно более персональным (никто не может на нём ничего сделать).
• Переход между двумя английскими раскладками быстр и прост.

Хвостовая "рекурсия" и взаимная хвостовая "рекурсия" на C

Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией.^[1] Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию, что реализовано во многих оптимизирующих компиляторах.

Википедия

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

typedef struct ReturnValue (* RecurFunction) (void *);

struct ReturnValue {
  RecurFunction function;
  void * value;
};

void * recur(RecurFunction function, void * input) {
  struct ReturnValue tmp;
  tmp.value = input;
  tmp.function = function;
  do {
    tmp = tmp.function(tmp.value);
  } while (tmp.function != NULL);
  return tmp.value;
}

Основная идея этого решения следующая: функция во время своего вычисления, формирует структуру данных типа ReturnValue, в которой определяется в поле value результат вычисления или задаётся функция, которая должна быть вычислена в следующую "итерацию" и её аргументы. Ограничения и неудобства решения видны сразу, рекурсивная функция должна быть типа RecurFunction, на вход получать void* (а значит и преобразовывать типы), и её результат должен быть представлен типом ReturnValue. Это делает код довольно страшным...
Посмотрим на классический пример, а именно на вычисление факториала:

// Тип входных данных.
struct RecurFactorial {
  int n, acc;
};
struct ReturnValue factorial(void * input) {
  struct RecurFactorial * args = input; // Приведение типа данных.
  struct ReturnValue result;
  result.value = input; // Входные и результируещие данный одни и теже.
  if (args->n == 1) {
    // Функция на следующий запуск не устанавливается для завершения вычислений.
    result.function = NULL;
  } else {
    // Формируем результаты итерации.
    args->acc *= args->n;
    args->n -= 1;
    // Устанвливаем функцию на следующий запуск.
    result.function = factorial;
  }
  return result;
}

Теперь рассмотрим пример поинтереснее, с двумя взаимно-рекурсивными функциями. Реализуется алгоритм с примерно тем же поведением (и с ошибкой на списке нулевой длинны), что у кода на Haskell в этом посте про алгоритм определения конца списка.

struct RecurLoopInList {
  struct List * fastMarker, * slowMarker;
};

struct ReturnValue slowMarker(void * input);
struct ReturnValue fastMarker(void * input);

bool loopInList(struct List *head) {
  struct RecurLoopInList args;
  args.fastMarker = head->next;
  args.slowMarker = head;
  bool * resultP = recur(fastMarker, (void*)&args);
  bool result = *resultP;
  free(resultP);
  return result;
}

struct ReturnValue slowMarker(void * input) {
  struct RecurLoopInList * args = input;
  struct ReturnValue result;
  result.value = input;
  args->slowMarker = args->slowMarker->next;
  result.function = fastMarker;
  return result;
}

struct ReturnValue fastMarker(void * input) {
  struct RecurLoopInList * args = input;
  struct ReturnValue result;
  if (args->fastMarker->next == NULL ||
      args->fastMarker->next->next == NULL) {
    bool * ans = malloc(sizeof(bool));
    *ans = false;
    result.value = (void*)ans;
    result.function = NULL;
  } else if (args->fastMarker->next == args->slowMarker ||
             args->fastMarker->next->next == args->slowMarker) {
    bool * ans = malloc(sizeof(bool));
    *ans = true;
    result.value = (void*)ans;
    result.function = NULL;
  } else {
    args->fastMarker = args->fastMarker->next->next;
    result.value = (void*)input;
    result.function = slowMarker;
  }
  return result;
}

Целиком весь код можно увидеть тут: https://gist.github.com/1003337

PS. есть ли другой подход, что бы сделать взаимно-рекурсивные функции на C без стека и платформо-независимо?

Один хороший человек с ником Powerfox предложил решение через контексты.

Проверка списка на наличие цикла в O(1) по памяти

Есть произвольный односвязный список, в котором может быть петля, необходимо предложить алгоритм который бы позволил определить, есть ли цикл в O(1) по памяти.

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

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

Реализация на С:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct List {
  struct List *next;
  int value;
};

struct List* makeList(int all, int inLoop) {
  struct List *head = malloc(sizeof(struct List));
  struct List *current = head;
  int marker = 1;
  for (int i = 0; i < all - inLoop; ++i) {
    current = current->next = malloc(sizeof(struct List));
    current->value = marker++;
  }
  if (inLoop > 0) {
    struct List *loopStart = current;
    for (int i = 0; i < inLoop; ++i) {
      current = current->next = malloc(sizeof(struct List));
      current->value = marker++;
    }
    current->next = loopStart->next;
  }
  return head;
}

bool loopInList(struct List *head) {
  struct List *fastMarker, *slowMarker;
  fastMarker = slowMarker = head;
  if (fastMarker->next == NULL) return true;
  else fastMarker = fastMarker->next;

  while (true) {
    if (fastMarker->next == NULL ||
        fastMarker->next->next == NULL)
      return false;
    if (fastMarker->next == slowMarker ||
        fastMarker->next->next == slowMarker)
      return true;
    fastMarker = fastMarker->next->next;
    slowMarker = slowMarker->next;
  }
}

int main(int argc, char** argv) {
  struct List * head = makeList(10, 0);
  printf("%s", loopInList(head) ? "true" : "false");
  return 0;
}

Реализация на Haskell. Собственно как и практически всегда у меня этим языком - первая мысль: "А как это вообще сделать?", вторая: "Так очевидно же как...".

makeList all inLoop = [1 .. (all - inLoop)] ++ loopListPart
    where loopListPart | inLoop > 0 = [(all - inLoop + 1) .. all] ++ loopListPart
                       | otherwise = []

list = makeList 5000000 500000

loopInList list@(x:xs) = fastMarker list xs
    where slowMarker (_:slows) fast = fastMarker slows fast
          fastMarker _ [] = False
          fastMarker _ (_:[]) = False
          fastMarker allSlow@(slow:_) (fast1:fast2:fasts)
              | fast1 == slow || fast2 == slow = True
              | otherwise = slowMarker allSlow fasts

main = putStrLn $ show $ loopInList list

Подход не правильный, но работающий.
Этот подход основывается на предпосылки - данные можно изменять. Идея следующая, проходим список вперёд разворачивая его. Если конец списка совпадёт с головой - значит была петля. Повторная проходка позволит восстановить исходную структуру данных. Реализация на C (только функция проверки):

bool loopInList(struct List *head) {
  struct List *current = head, *last = head, *next;
  current = last = head;
  if (current->next == NULL) return true;
  else {
    current = current->next;
    last->next = NULL;
  }
  while (current->next != NULL) {
    printf("%d ", current->value);
    next = current->next;
    current->next = last;
    last = current;
    current = next;
  }
  if (current == head) return true;
  else return false;
}

О начале массивов и списков...

Как-то раз, около полу года назад, имел я беседу с одним интересным человеком с ником powerfox, на предмет того, что идея нумеровать массивы с нулевого элемента довольно таки дурацкая. Думаю, никого не удивит, что данный тезис защищал именно я. Аргументация довольно простая, и не вдавая в детали может быть сформулирована так: считать с единицы более естественно, нежели чем с нуля. Счёт с нуля в массивах является историческим бременем низкоуровнего программирования, когда индекс массива являлся приращением базового указателя.

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


my $day_epoch = timelocal(0, 0, 0, 31, 3, 2011);
Day '31' out of range 1..30 at - line 2


The value for the day of the month is the actual day (ie 1..31), while the month is the number of months since January (0..11). This is consistent with the values returned from "localtime()" and "gmtime()".


$mday is the day of the month, and $mon is the month itself, in the range 0..11 with 0 indicating January and 11 indicating December.  This makes it easy to get a month name from a list:


Как видно, на первый взгляд, совершенно дурное решение нумеровать дни от 1 до 31, а месяцы с 0 до 11, становится вполне логичным и оправданным в контексте нумерации массивов с 0. Напрашиваются странные выводы...

P. S. Что все уже привыкли, и ничего не поделаешь - понятно. Но тут дело дурацкого принципа об этом сказать.

Кремниевая компиляция.

Какое прекрасное и интригующее словосочетание - кремниевая компиляция. Вот вы написали программу, скажем, на СИ (или, что более интересно, на Prolog или Smalltalk), и она работает, прямо скажем, хорошо, но немного медленно. Тут запускаете кремниевый компилятор и из печки рядом неспешно вылезает полностью аппаратная реализация, как слоёная булочка. Работает она на порядки быстрее. Энергии потребляет меньше. К сожалению, суровая реальность немного иная, и основная проблема не в том, как можно так быстро, просто и дёшево сделать железку (всё таки есть ПЛИС-ы), а в самой трансляции.

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

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

Модель вычислений - общее, крайне абстрактное описание того, что может наш вычислитель. Грубого говоря, для фон-Неймановского процессора это сводится к работе пересылке данных между памятью, регистрами и портами ввода/вывода, обработкой данный в АЛУ (и тут не важно какие команды), видами адресации и последовательным принципом выполнения команд с jmp. Другими слова МВ - набор базовых правил, по которым работает система.

Вычислитель - коробка (или программа), которая реализует МВ и позволяет выполнять на себе программу.

Семантический разрыв - разница между моделями вычислений. В чём её мерить сказать крайне трудно, но интуитивно это довольно понятно. К примеру, программа на СИ легко транслируется в машинный код, в то время как программу на Java значительно сложнее (я бы даже осказал что не транслируется совсем. Да, я знаю про jit и ниже упомяну почему занимаю такую позицию). Пример из другой области: семантическая разница между градусами Кельвина и Цельсия меньше, чем между градусами Кельвина и Фаренгейта (в первом случае зависимость линейна, во втором нет). Таким образом, интуитивное понимание понятия семантического разрыва сводится к тому, что чем сложнее нам перевести что-либо из одного представления в другое, тем больше семантический разрыв между этими представлениями.

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

1. Расширение МВ вычислителя. Идея очень проста и полностью аналогична идеи Магомета подойти к горе. Если мы не можем преобразовать код под конкретный вычислитель, можно преобразовать вычислитель под конкретный код. Этого можно добиться путём реализации расширения для вычислителя, наиболее яркими примерами которых являются виртуальные машины (на пример Java, которая всегда имеет свой run-time, и как следствие, никогда полностью не транслируется). Возможны и аппаратные расширения
2. Абстрактная МВ. Основной идеей данного подхода является то, что бы ввести в инструментальную цепочку промежуточный язык, который построен таким образом, что бы не завязывать систему на конкретную платформу для реализации и при этом покрывать все возможные решения. К сожалению, этот подход довольно проблематичен, так как подобную МВ крайне сложно определить таким образом, что бы она оказывала минимальное влияние на программу, то есть: не добавляла в код новых ограничений, не добавляла ему новых свойств, не затачивала под конкретный вычислитель (класс вычислителей) или язык разработки. В качестве одного из наиболее удачных примеров использования этого подхода можно назвать LLVM (на сколько мне известно, есть попытки прикрутить к нему синтез HDL).
3. Выскоуровневое проектирование. Идея подхода заключается в том, что бы сделать некоторое гетерогенное (разнородное), иерархическое описание вычислительной системы, где на разных уровнях используются различные МВ, что позволяет с одной стороны решать проблемы наиболее оптимальным образом и с другой стороны, при использование "базовых" МВ, относительно легко реализовывать трансляторы кода как в программный код, так и в аппаратуру. Подробнее об этих идеях можно почитать в документациях к проекту ptolemy или в моей бакалаврской.

Возвращаясь к вопросу о кремневой компиляции, зачем нам это надо? Основных причин две:

1. Портировать существующий код в аппаратуру.
2. Работать с более высокоуровневым кодом, нежели позволяют HDL языки, и тем самым понизить стоимость разработки.

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

Разрешение же второй причины вполне себе реально, в случае если использовать идею высокоуровневого проектирования, но отказавшись от её самой сложной составляющей - иерархичности и гетерогенности на столько, на сколько это возможно. Другими словами, взять некоторую МВ с интересующими нас свойствами (а тут это главным образом предсказания времени работы и параллелизм, по крайней мере для тех задач, которыми интересуюсь я), и прикрутить к ней возможность в качестве примитивных операций использовать пользовательские аппаратные блоки с интерфейсами, отвечающими на заданные требования.

Таким образом вырисовывается довольно приятная картина: у пользователя будет высокоуровневый язык, на котором он легко опишет поведение своей системы, попутно создав или взяв из библиотеки некоторое множество примитивных операций (само собой он сможет их прототипировать на обычном языке высокого уровня). Затем он нажимает кнопочку "скомпилировать", и на выходе получает программно управляемый процессор (с кодом для него) с заточенным набором базовых команд и оптимизированной архитектурой под конкретный код. Как следствие, происходят следующие приятные вещи:

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

Правда, тут есть и целый ряд ложек дёгтя:

• МВ довольно необычна, и к ней придётся довольно долго привыкать.
• МВ не является моделью вычислений общего назначения (такая как в СИ), а значит, некоторые вещи прийдётся решать на ней не типичным способом или опускать на уровень аппаратуры.

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

PS Проект в текущий момент является закрытым, но постепенно, с появлением в нём завёршённых этапов, он будет открываться.