Удаление элемента списка в Scheme

Доброго времени суток, случайные и неслучайные читатели этого блога.

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

Если вы сталкивались с Lisp'ом в жизни (например, настраивая GNU Emacs), то должны знать, что список является едва ли не основным представлением как данных, так и собственно программы, их обрабатывающей. Даже название языка -- Lisp -- произошло от "List Processing", т.е. "обработка списков". Scheme, как диалект Lisp, не представляет исключение в этом плане. И работая с Scheme, вы постоянно работаете со списками.

Так вот, в LazyCat список управляемых хостов хранится, как Lisp-список. Пример:

 
'((#f host1 host2) ("ssh-hosts" host2 host4))

В данном примере есть две группы:

• группа #f, в которую помещяются "бездомные" хосты, которые не являются членами какой-либо группы (уж так повелось);
• и группа "ssh-hosts".

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

(car '("ssh-hosts" host2 host4)) => "ssh-hosts"

Оставшаяся часть списка -- получаемая через cdr -- это члены группы.

(cdr '("ssh-hosts" host2 host4)) => '(host2 host4)

При работе с этим списком требуется добавлять и удалять его элементы. С добавлением нового элемента в список проблем нет, а вот удаление элемента из списка представляет собой не вполне тривиальную задачу. По крайней мере, я не нашёл простого спосба сделать это. Что и привело к созданию собственного "велосипеда" для выполнения этой операции.

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

1. Нужно взять часть списка, чей car -- элемент, который необходимо удалить. Эту часть можно найти путём простого перебора элементов.
2. После этого нужно получить cdr списка.
3. Склеить с помощью операции append две части списка -- часть списка до текущего car и часть списка, получаемая по cdr относительно текущей части с удаляемым элементом в car.

На практике же это превратилось в довольно громоздкую конструкцию:

 

(let ((new-cdr '())) 
  (let f ((group-members (cdr group)))

    ;; Are there elements in the given list?
    (if (not (null? group-members))

        (if (eq? (car group-members) host)

             ;; We found the host which should be removed from the list.
             ;; Cut out the car of the list and concatenate two lists
             (set-cdr! group (append new-cdr (cdr group-members)))

             ;; Host is not found. Check the next group member.
             (begin 
               ;; Add the current car to the new cdr of the group
               (new-cdr (append new-cdr (car group-members))) 
               ;; Try the next group member 
               (f (cdr group-members)))))))

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

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

Благодаря использованию модуля (ice-9 common-list) вышеприведённый кусок кода был заменён на следующую строчку:

 

(set-cdr! group (remove-if (lambda (element) (eq? element host)) 
                           (cdr group)))

Функция remove-if применяет предикат (фукнцию, возвращающую #t (true) или #f (false)) переданный, как первый параметр, ко всем элементам списка (второй параметр функции). Если предикат возвращает #t -- то элемент удаляется из списка. По завершению remove-if возвращает список, из которого удалены требуемые элементы.

В представленном выше примере remove-if сравнивает два объекта -- элемент списка и хост. Если элемент списка и хост -- один и тот же объект, то он удаляется из списка. После этого происходит замена cdr группы новым списком хостов.

Пример использования remove-if взят из файла host-list.scm, являющегося частью LazyCat.

- Артём

Получение информации о MBR и таблице разделов с помощью file(1)

Только что узнал о таком интересном умении Unix-утилиты file(1), как вывод информации из главной загрузочной записи (англ. Master Boot Record, или, по-простому, MBR).

Для примера сохраним MBR с устройства /dev/sda в файл. Для этого нам нужно скопировать первые 512 байт с жёсткого диска, то есть, один блок по 512 байт. Хочу предупредить, что утилита dd(1) славится своей способностью портить жёсткие диски при неумелом обращении. Поэтому всегда проверяйте, правильно ли вы указали источник if и место сохранения of данных. Просто нужно немного внимательности. Итак, сохраняем MBR:

$ dd if=/dev/sda of=/mnt/backup/boot.mbr bs=512 count=1



Затем получим информацию о файле:

$ file /mnt/backup/boot.mbr
/mnt/backup/boot.mbr: x86 boot sector; GRand Unified Bootloader, stage1 version 0x3, stage2 address 0x2000, stage2 segment 0x200; partition 1: ID=0x83, active, starthead 1, startsector 63, 29302497 sectors; partition 2: ID=0x83, starthead 254, startsector 29302560, 8000370 sectors; partition 3: ID=0x82, starthead 254, startsector 37302930, 2554335 sectors, code offset 0x4

В выводе команды можно увидеть тип загрузчика (GRand Unified Bootloader - GRUB) и информацию из таблицы разделов. Каждая запись отделена точкой с запятой. Например, запись

partition 1: ID=0x83, active, starthead 1, startsector 63, 29302497 sectors;

говорит, что на первом разделе (/dev/sda1) находится файловая система ext (в данном случае, ext2), так как её шестнадцатиричный код - 0x83. Так же видно, что первый раздел является активным (active) - то есть, с него осуществляется загрузка. Далее идёт размер раздела в секторах.

Вот более подробная статья на эту тему (на английском):
http://www.miljan.org/main/2007/09/05/easy-way-to-read-mbr/

Нестандартное применение функции getopt(3)

Доброго времени суток, случайные и неслучайные читатели этого блога. Сегодня я хочу рассказать об одном любопытном способе применения функции getopt(3).

Как вы наверняка знаете, getopt(3) позволяет легко разбирать (или "парсить", да простит меня русский язык) опции командной строки, переданные программе.

Вместо термина "опция" так же используются термины "флаг" или "ключ".

Вот простой пример, демонстрирующий работу getopt(3):

#include <stdio.h>
#include <unistd.h>

int
main(int argc, char* argv[])
{
  int opt;

  while ((opt = getopt(argc, argv, "ab:")) > 0)
    {
      switch (opt)
      {
      case 'a':
          puts("'a' option was found.");
          break;

      case 'b':
          printf("'b' option was found. number = %d\n", atoi(optarg));
          break;
      }
    }

  return 0;
}

Работа с программой может выглядить следующим образом:

$ ./a.out -a -b 10
'a' option was found.
'b' option was found. number = 10


В данном примере используются только короткие опции - то есть, которые начинаются с "-", например, "-h", "-n 9". Родственная функция getopt_long(3) позволяет парсить так же и длинные опции, начинающиеся с "--" (например, "--verbose" или "--option=value").

Использование getopt(3) позволяет избежать создания собственного "велосипеда" для разбора опций командной строки. А теперь представим, что нам нужно разобрать подобным образом массив строк, передаваемый в качестве параметра нашей собственной функции. Почему бы не использовать для этого столь удобный инструмент, как getopt(3)? Тем более, что функция main() очень похожа на другие функции (точнее, другие функции очень похожи неё). Разве что main() является стандартной точкой входа в программу, с которой начинается её выполнение. Но для нашего эксперимента это не столь важно. Попробуем "подделать" обычную функцию под main(), чтобы getopt(3) не обнаружила подмены. Для этого посмотрим внимательно на main().

Итак, main() принимает в качестве параметров количество аргументов командной строки argc и собственно сам список аргументов argv, который представляет собой массив указателей на строки (массивы символов). Чтобы getopt(3) работала корректно, нужно создать функцию с подобным набором параметров. Внутри функции организуем разбор "командной строки":

void
fun1(int argc, char* argv[])
{
  int opt;
  
  while ((opt = getopt(argc, argv, "ab:c:")) > 0)
    {
      switch (opt)
 {
 case 'a':
   puts("'a' was found.");
   break;

 case 'b':
   printf("'b' was found. optarg = %d\n", atoi(optarg));
   break;

 case 'c':
   printf("'c' was found. optarg = %d\n", atoi(optarg));
   break;
 }
    }
}  

Теперь возьмёмся за main():

#include <stdio.h>
#include <unistd.h>

void fun1(int argc, char* argv[]);

int
main(void)
{
  int   argc = 3;
  char* test_array[] = { "-a", "-b 10", "-c 20" };

  fun1(argc, test_array);

  return 0;
}

Скомпилируем и запустим программу:

$ gcc -o getopt-test getopt-test.c
$ ./getopt-test
'b' was found. optarg = 10
'c' was found. optarg = 20


Как можно заметить, куда-то подевался нулевой элемент массива argv - словно getopt(3) начала просмотр массива с первого элемента. Разберёмся, почему. Вспомним, что при запуске программы нулевой элемент массива argv, передаваемый в main(), содержит имя исполняемого файла программы. Поэтому функция getopt(3) попросту пропускает его, так как он не содержит опций командной строки.

Решение проблемы выглядит следующим образом:

int
main(void)
{
  int   argc = 4; /* 3 аргумента командной строки + имя программы */
  char* test_array[] = { "fun1", "-a", "-b 10", "-c 20" };

  fun1(argc, test_array);

  return 0;
}

Скомпилируем и проверим исправленную версию программы:

$ gcc -o getopt-test getopt-test.c
$ ./getopt-test
'a' was found.
'b' was found. optarg = 10
'c' was found. optarg = 20


По результатам работы программы видно, что теперь getopt(3) находит опцию "-a".

Конвейерная обработка данных в Unix

Доброго времени суток, случайные и не случайные читатели этого блога.

Сегодня я хотел бы рассмотреть пример программы, которая может работать в режиме "конвейера" (pipeline), что является обыденным делом для утилит Unix-подобных систем.

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

Наша программа будет принимать на вход вывод некой другой программы, обрабатывать эти данные неким образом и передавать на стандартный вывод.

Просто? Просто.

Исходный текст программы тоже очень простой:

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

int
main(void)
{
  char ch;

  while (fread(&ch, sizeof(char), 1, stdin))
    putchar(toupper(ch));
  
  exit(EXIT_SUCCESS);
}

Теперь немного технических деталей. Когда вы пишете что-то вроде

$ cat my-file.txt | sort

командная оболочка (shell) связывает стандартный поток вывода stdout команды cat(1) со стандартным потоком ввода stdin команды sort(1). Таким образом, эти команды связываются в конвейер, проходя через который данные преобразуются определённым образом. В данном примере, мы выводим (считываем) содержимое файла my-file.txt на stdout, команда sort(1) принимает эти данные на stdin, сортирует их и выводит на stdout. На этом конвейер заканчивается и обработанные данные выводятся на терминал.

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

Важно заметить, что программы, составляющие конвейер, выполняются параллельно. Если рассматривать приведённый ранее пример, то команда cat(1) и sort(1) работают одновременно. Как только cat(1) выводит данные на stdout, они сразу же могут быть считаны командой sort(1) из stdin.

Сравните с последовательностью команд, разделённых точкой с запятой, которые выполняются одна за другой:

$ cat my-file.txt; sort

Сначала будет выполнена команда cat(1), которая выведет содержимое файла my-file.txt на экран, а потом будет выполнена команда sort(1), которая будет ждать ввода данных с stdin.

Скомпилируем наконец нашу программу и посмотрим, что полезного она может сделать.

$ gcc tu.c -o tu

Протестируем работу программы. Свяжем в конвейер команду awk(1) и нашу програму:

$ awk --copyleft | ./tu

Команда awk(1) с параметром --copyleft выводит краткий вариант лицензии GPL на stdout. Далее наша программа считывает в цикле по одному символу с stdin, преобразует считанный символ в прописной и выводит этот символ на stdout.

Вывод нашей программы можно так же отправить дальше по конвейеру.

$ awk --copyleft | ./tu |\
   sed s/'1989, 1991-2010 FREE SOFTWARE FOUNDATION'/'2012 Artyom Poptsov'/

Неплохой обзор конвейерной обработки данных в Unix дан в следующих статьях:

• Использование UNIX: Что внутри конвейера?
• http://en.wikipedia.org/wiki/Pipeline_(Unix) (en)

Новогодняя ёлка на Emacs Lisp

Доброго времени суток, случайные и не случайные читатели.

Пользуясь случаем, поздравляю вас с уже наступившим Новым Годом. Дабы немного поднять вам (и себе) новогоднее настроение, публикую исходный код программы на Emacs Lisp, которая рисует замечательную новогоднюю ACSII-ёлку.

;;;
;;; Copyright (C) 2011 Artyom Poptsov
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as published by
;;; the Free Software Foundation; either version 3 of the License, or
;;; (at your option) any later version.
;;;
;;; For more information, see http://www.gnu.org/licenses/
;;;

;; Result of running this program sends to other buffer
(with-output-to-temp-buffer "*tree*"

  ;; Get height of the tree from stdin
  (setf HIGHT (read))

  ;; There are symbols that I will use for drawing the tree
  (setq C_BG    ":")
  (setq C_TREE  "^")
  (setq C_TRUNK "#")

  ;; A few variables
  (setq PADDING 2) ; Padding from edges of the "canvas".
  (setf TRUNK_H (/ HIGHT 4))                              

  ;; I'm using this funtions for printing empty strings filled with BG
  (defun print-bg-for-picture ()
    "This function prints out a few strings filled with background"
    (loop for i from 1 to PADDING do
   (loop for j from 0 to (+ (* HIGHT 2) (* PADDING 3)) do
  (princ C_BG))
   (princ "\n")))

  (print-bg-for-picture)

  ;; Main loop
  (loop for i from 0 to (+ HIGHT TRUNK_H (* PADDING 2)) do
 (loop for j from 0 to PADDING do
       (princ C_BG))
 (if (< i HIGHT)
     ;; Top of the tree
     (loop for j from 0 to (* HIGHT 2) do
    (if (or (< j (- HIGHT i))
     (> j (+ HIGHT i)))
        (princ C_BG)
      (princ C_TREE)))
   ;; Trunk of the tree
   (loop for j from 0 to (* HIGHT 2) do
  (if (or (< j (- HIGHT (/ HIGHT 10)))
   (> j (+ HIGHT (/ HIGHT 10))))
      (princ C_BG)
    (princ C_TRUNK))))
 (loop for j from 0 to PADDING do
       (princ C_BG))
 
 (princ "\n"))
  (print-bg-for-picture))

Вы можете вычислить (выполнить) эту программу следующим образом: запустите текстовый редактор Emacs (предположим, что он у вас уже установлен), скопируйте исходный код в буфер *scratch*, поместите точку (курсор) после последней скобки в конце программы и нажмите C-x C-e (Ctrl+x Ctrl+e). Далее вы можете ввести размер ёлки.

В результате, если вы всё сделали правильно, у вас откроется новое окно, в котором отобразится результат работы программы:

::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::^::::::::::::::::::::::: ::::::::::::::::::::::^^^:::::::::::::::::::::: :::::::::::::::::::::^^^^^::::::::::::::::::::: ::::::::::::::::::::^^^^^^^:::::::::::::::::::: :::::::::::::::::::^^^^^^^^^::::::::::::::::::: ::::::::::::::::::^^^^^^^^^^^:::::::::::::::::: :::::::::::::::::^^^^^^^^^^^^^::::::::::::::::: ::::::::::::::::^^^^^^^^^^^^^^^:::::::::::::::: :::::::::::::::^^^^^^^^^^^^^^^^^::::::::::::::: ::::::::::::::^^^^^^^^^^^^^^^^^^^:::::::::::::: :::::::::::::^^^^^^^^^^^^^^^^^^^^^::::::::::::: ::::::::::::^^^^^^^^^^^^^^^^^^^^^^^:::::::::::: :::::::::::^^^^^^^^^^^^^^^^^^^^^^^^^::::::::::: ::::::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^:::::::::: :::::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^::::::::: ::::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^:::::::: :::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^::::::: ::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^:::::: :::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^::::: ::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^:::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::::::::::::::

Happy New Year and happy coding!

Цена невнимательности, или как я подложил себе интересные грабли при настройке SSH

Доброго времени суток, случайные и неслучайные читатели.

Не так давно, а именно около месяца назад, появилась у меня идея - настроить аутентификацию по публичному ключу на домашний компьютер через SSH. Это более безопастно и более удобно, чем авторизация по паролям. Я не буду здесь объяснять, как настроить аутентификацию по публичным ключам, так как в интернете есть тьма-тьмущая всяких how-to по этой теме - от самых простых, до подробнейших руководств. К примеру, есть цикл статей от Дэниела Роббинса (создателя Gentoo Linux) на IBM DeveloperWorks:

• Part 1: http://www.ibm.com/developerworks/library/l-keyc/index.html
• Part 2: http://www.ibm.com/developerworks/library/l-keyc2/
• Part 3: http://www.ibm.com/developerworks/library/l-keyc3/

А сейчас я лишь хочу упомянуть про одни грабли, на которые я наступил при настройке SSHD. Причём грабли я подложил сам себе и набил немало шишек, пытаясь найти причину, почему через локальную сеть с ПК на ноутбук аутентификация по ключам работает, а наоборот - нет. Будто бы для настройки SSH на моём ПК под Gentoo Linux требовалось какое-то сакральное знание, которым я не обладал.

Пару дней длился поиск проблемы, были испробованы разные комбинации настроек, двадцать раз проверены права на каталог ~/.ssh и файл authorized_keys (как известно, ssh трепетно относится к выставленным правам на его файлы), в общем - была потрачена уйма времени (я занимался этим в выходные :)). Ничего не помогало - источник проблемы ускальзал от меня с удивительной ловкостью. В конце-концов я принял волевое решение оставить решение этой проблемы до лучших времён.

И вот, сегодня я решил опять попробовать найти источник проблемы. Часто так бывает, что по прошествии некоторого времени проблема решается "за пять минут". Взял свой коммуникатор под управлением Android и установленным ConnectBot, проверил, занесён ли ключ, сгенерированный на коммуникаторе, в файл ~/.ssh/authorized_keys. Всё настроено, пытаюсь подключится - ничего.

$ tail -f /var/log/messages

тоже молчит.

Ну, это мы уже проходили. Неплохо бы получить больше информации в лог. Открываю конфигурационный файл /etc/ssh/sshd_config, нахожу переменную LogLevel - установлена в INFO. Открываю man-страницу на конфиг sshd_config, нахожу описание переменной LogLevel. Значение DEBUG2 включает режим подробного вывода в лог сообщений SSHD. Выставляю LogLevel DEBUG2, перезапускаю SSHD:

$ rc-config restart sshd

Пробую подключиться на ПК с телефона. Ага, вот и подсказка: файл /home/avp/.ssh/autorized_keys не найден. Стоп, мне кажется, или в имени файла ошибка? Пропущена буква "h" в слове "authorized". Переименовываю файл:

$ cd ~/.ssh/
$ mv autorized_keys authorized_keys

Пробую подключиться - работает!..

Вот так, казалось бы, такая мелочь, как одна пропущенная буква, приводит к серьёзным последствиям. Прямо как в стихотворении Самуила Маршака:

Не было гвоздя -
Подкова
Пропала.

Не было подковы -
Лошадь
Захромала.

Лошадь захромала -
Командир
Убит.

Конница разбита -
Армия
Бежит.

Враг вступает в город,
Пленных не щадя,
Оттого, что в кузнице
Не было гвоздя.

scroller.el - простое дополнение для GNU Emacs

Решил добавить в Emacs функцию, которую не нашёл во всём многообразии keybinding'ов (может, я просто плохо искал?)

Итак, это две очень простые функции, прокручивающие текущий буфер на одну строку (вверх или вниз, соответственно), без изменение позиции курсора. Это иногда бывает очень полезно.

;;; These simple functions allows scrolling with keeping
;;; position of cursor

(defun scroll-down-keeping-cursor (&optional arg)
  "Scrolling down one line while keep cursor position."
  (interactive "p")
  (if (interactive-p)
      (progn
        (scroll-down arg)
        (scroll-down 1))))

(defun scroll-up-keeping-cursor (&optional arg)
  "Scrolling up one line while keep cursor position."
  (interactive "p")
  (if (interactive-p)
      (progn
        (scroll-up arg)
        (scroll-up 1))))

Теперь неплохо бы привязать эти функции к клавишам:

(global-set-key (kbd "M-p") 'scroll-down-keeping-cursor)
(global-set-key (kbd "M-n") 'scroll-up-keeping-cursor)

Как и при использовании обычных комбинаций C-n и C-p, эти функции можно вызывать в интерактивном режиме, передавая количество строк, на которое следует прокрутить буфер:

C-u 10 M-n

Конечно, если прописать все функции, настройки и keybinding'и в custom.el, они загрузятся. Но IMHO пользовательские файлы для Emacs выглядят гораздо опрятнее, если их разложить по отдельным файлам/каталогам.

Например, пусть это дополнение будет в отдельном файле scroller.el и положим мы его в ~/.emacs.d/. Тогда в ~/.emacs.d/custom.el останется только загрузить этот файл:


(load-file "~/.emacs.d/scroller.el")


Или так:

(setq emacs-dotdir
      (expand-file-name ".emacs.d" "~"))
(load-file (expand-file-name "scroller.el" emacs-dotdir))