среда, 29 июня 2011 г.

Анархия или заблуждения обывателей

Мы должны дать самим себе отчет в нашем бытии; следовательно, мы хотим также стать подлинными кормчими этого бытия и не допустить, чтобы наше существование было равносильно бессмысленной случайности. В отношении жизни нужно допустить некоторое дерзновение и риск, тем более, что в худшем, как и в лучшем случае мы все равно ее потеряем. Для чего быть привязанным к этому клочку земли, к этому ремеслу, для чего прислушиваться к тому, что говорит сосед? Какой провинциализм — подчиняться воззрениям, которые за несколько сот миль от нас уже не обязательны! Восток и запад суть лишь черты, которые кто-то проводит мелом перед нашими глазами, чтобы обманно воспользоваться нашей боязливостью. Я хочу сделать попытку прийти к свободе, — говорит юная душа; и неужели этому должно помешать, что случайно две нации ненавидят одна другую и воюют между собой, или что между двумя частями света лежит море, или что всюду вокруг проповедуется религия, которая еще несколько тысячелетий тому назад совсем не существовала? Все это — не ты сам, — говорит себе юная душа. Никто не может построить тебе мост, по которому именно ты можешь перейти через жизненный поток, — никто, кроме тебя самого. Правда, есть бесчисленные тропинки и мосты, есть полубоги, которые хотят перенести тебя через поток; но только ценой тебя самого: ты должен был бы отдать себя в залог, потерять самого себя. В мире есть единственный путь, по которому никто не может идти, кроме тебя; куда ведет он? не спрашивай — иди по нему!
Фридрих Ницше.
«Шопенгауэр как воспитатель»

пятница, 24 июня 2011 г.

Inside Go language

Появилось желание поковыряться в бинарниках, которые генерирует компилятор Go)
Хотелось посмотреть своими глазами, чем он отличается и увидеть, как реализован garbage collector (последнее пока не удалось).
Тактика была следующей - я написал несколько самых простых приложений на Go и, дабы иметь возможность сравнить, на С. Затем стал копаться в них с помощью различных отладчиков и hex-editor'ов. В качестве инструментов я выбрал gdb, DDD (front-end для gdb) и EDB + GHex. EDB сразу пришлось отмести, т.к. он хоть и выглядел как всеми любимая OllyDbg, но был как-то дико неудобен в использовании)
Для начала продемонстрирую листинги:

package main

import "fmt"

func print(input string) {
fmt.Printf("%s\n",input)
}

func main(){
test:="aaaa"
print(test)
}

Все чрезвычайно просто) Теперь посмотрим, какой бинарник получился после компиляции (упомяну, что собирать надо с отладочной информацией - т.е. не забыть про ключ -g)


0x08048c8b <+0>: mov    %gs:0x0,%ecx
0x08048c92 <+7>: mov    -0x8(%ecx),%ecx
0x08048c95 <+10>: cmp    (%ecx),%esp
0x08048c97 <+12>: ja     0x8048ca2 <main.main+23>
0x08048c99 <+14>: xor    %edx,%edx
0x08048c9b <+16>: xor    %eax,%eax
0x08048c9d <+18>: call   0x804966a <runtime.morestack>


Это начало функции main. Как можно заметить, в начале происходит некоторая работа - выбирается аргумент функции, затем проверяется его расположение. Если он находится не на вершине стека, то, видимо, есть еще аргументы и для них вызывается функция увеличения стека morestack

0x08048ca2 <+23>: sub    $0x20,%esp
0x08048ca5 <+26>: lea    0x808239c,%esi
0x08048cab <+32>: lea    0x18(%esp),%edi
0x08048caf <+36>: cld    
0x08048cb0 <+37>: movsl  %ds:(%esi),%es:(%edi)
0x08048cb1 <+38>: movsl  %ds:(%esi),%es:(%edi)
0x08048cb2 <+39>: lea    0x18(%esp),%esi
0x08048cb6 <+43>: lea    (%esp),%edi
0x08048cb9 <+46>: cld    
0x08048cba <+47>: movsl  %ds:(%esi),%es:(%edi)
0x08048cbb <+48>: movsl  %ds:(%esi),%es:(%edi)
0x08048cbc <+49>: call   0x8048c00 <main.print>


Далее происходит следующее - из данных выбирается необходимая строка "aaaa" и передается в нашу функцию print. Стоит заметить, что в Gо каждый поток имеет собственный стек, место для которого выделяется в куче. В функции printf также сначала проверяется количество аргументов (при необходимости вызывается morestack), затем выделяется память для копирования переданной на вход строки

0x08048c1a <+26>:    sub    $0x54,%esp
0x08048c1d <+29>:    movl   $0x8,(%esp)
0x08048c24 <+36>:    call   0x804e245 <runtime.new>


И, собственно, вызов Printf из пакета fmt

0x08048c82 <+130>:   call   0x805b367 <fmt.Printf>

Теперь, для сравнения, аналогичный код на C:

#include <stdio.h>

void print(char *input)
{
printf("%s\n",input);
}

int main()
{
char test[]="aaaa";
print(test);
}

Исследуя внутренности бинарника, который реализует этот код, мы, конечно, заметим достаточно отличий.

   0x08048427 <+0>:     push   %ebp
   0x08048428 <+1>:     mov    %esp,%ebp
   0x0804842a <+3>:     and    $0xfffffff0,%esp
   0x0804842d <+6>:     sub    $0x20,%esp
   0x08048430 <+9>:     mov    %gs:0x14,%eax
   0x08048436 <+15>:    mov    %eax,0x1c(%esp)
   0x0804843a <+19>:    xor    %eax,%eax

//строка "aaaa" явным образом помещается в стек
   0x0804843c <+21>:    movl   $0x61616161,0x17(%esp)
   
//поместить символ окончания строки
   0x08048444 <+29>:    movb   $0x0,0x1b(%esp)
   
//помещаем полученную строку в eax и вызываем print
   0x08048449 <+34>:    lea    0x17(%esp),%eax
   0x0804844d <+38>:    mov    %eax,(%esp)
   0x08048450 <+41>:    call   0x8048414 <print>
   
//проверка целостности стека   
   0x08048455 <+46>:    mov    0x1c(%esp),%edx
   0x08048459 <+50>:    xor    %gs:0x14,%edx
   0x08048460 <+57>:    je     0x8048467 <main+64>
   0x08048462 <+59>:    call   0x8048338 <__stack_chk_fail@plt>
   0x08048467 <+64>:    leave  
   0x08048468 <+65>:    ret

Судя по всему, gcc немного оптимизировал код, поместив строку "aaaa" в код. К тому же обнаружился stack protector. Конечно, на таком простом примере трудно заметить много особенностей, поэтому в качестве эксперимента я решил посмотреть другой код, где появится работа с памятью:

package main

func main(){
test := make([]int, 100)

for i:=0; i<100; i++ {
 test[i]=i;
}
}


Вновь получим бинарник и увидим - в начале также проверяется расположение аргумента. А что дальше?

//вызов make - в данном случае это обертка для функции makeslice
0x08048c41 <+65>: call   0x8051e14
0x08048c46 <+70>: lea    0x14(%esp),%ebx
0x08048c4a <+74>: mov    %ebx,%esi
0x08048c4c <+76>: lea    0x3c(%esp),%edi
0x08048c50 <+80>: cld    
0x08048c51 <+81>: movsl  %ds:(%esi),%es:(%edi)
0x08048c52 <+82>: movsl  %ds:(%esi),%es:(%edi)
0x08048c53 <+83>: movsl  %ds:(%esi),%es:(%edi)

//начало цикла
0x08048c54 <+84>: xor    %eax,%eax
0x08048c56 <+86>: cmp    $0x64,%eax
0x08048c59 <+89>: jge    0x8048c78 <main.main+120>
0x08048c5b <+91>: lea    0x3c(%esp),%ebx
0x08048c5f <+95>: mov    %eax,%ebp

//проверка попадания счетчика в диапазон индексов слайса
0x08048c61 <+97>: cmp    0x4(%ebx),%eax
0x08048c64 <+100>: jb     0x8048c6b <main.main+107>

//если счетчик вне границ - паникуем)
0x08048c66 <+102>: call   0x8050a23 <runtime.panicindex>

0x08048c6b <+107>: mov    (%ebx),%ebx
0x08048c6d <+109>: lea    (%ebx,%ebp,4),%ebx
0x08048c70 <+112>: mov    %eax,(%ebx)
0x08048c72 <+114>: inc    %eax
0x08048c73 <+115>: cmp    $0x64,%eax
0x08048c76 <+118>: jl     0x8048c5b <main.main+91>
0x08048c78 <+120>: add    $0x48,%esp
0x08048c7b <+123>: ret    

Как мы видим, вызов функции make преобразовывается в вызов makeslice. К тому же, оказалось, что Go обрабатывает неожиданную ситуацию в виде выхода за пределы слайса. Но вот признаки работа сборщика мусора так и не найдены.

Выводы, конечно, по таким небольшим примерам делать сложно, но уже вырисовывается тот факт, что Go на низком уровне обеспечивает некоторые интересные мелочи, такие как работа со стеком (напоминает стек в .net), но в то же время С-шный компилятор, конечно, генерирует более оптимизированные бинарники.



суббота, 18 июня 2011 г.

Мышление

Никто не задавался вопросом, а как мы мыслим? Вот перед нами есть задача, вот мы начинаем над ней думать - и что происходит в этот момент? Какими абстрактными категориями мы оперируем? Это далеко не праздная философия, ибо понимание этих процессов может дать способ оптимизировать процесс мышления)
Некоторое время назад меня заинтересовал этот вопрос и для начала я решил набрать немного информации на эту тему. Натолкнулся на разные "Драконы", ТРИЗ'ы, статьи по психологической кибернетике - но как-то не возникало ощущения, что все ответы получены) Хотя, вполне возможно, я потратил на это недостаточно времени.
И тем не менее возникли некоторые правдоподобные мысли...и так, процесс мышления?
Любая задача всегда имеет две точки отсчета - постановка задачи и то, что принимается в качестве верного решения(ответ). Они должны быть как можно более строго определены, т.к. от них зависит процесс решения. Такая определенность помимо всего прочего локализует задачу в определенном пространстве - например, постановка математической задачи сразу отметает гуманитарные порывы и указывает, например, что она решается в евклидовом пространстве. Будем считать, что мы обитаем в идеальных условиях - постановка и верное решение полностью детерминированы.
Ясно, что для решения задачи надо перейти от постановки к ответу:


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


Переходов уже больше) Понятно, что каждый переход имеет несколько продолжении - и не каждый из них приводит к нужному результату. Чтобы увидеть интуитивно всю цепочку сразу, необходимо обладать особыми способностями к ясновидению - хотя и такие мыслители встречаются)
Видимо, для того, чтобы точно решить такую задачу, необходимо сконцентрироваться именно на этих шагах, а не пытаться увидеть всю цепочку переходов сразу. А что они представляют из себя?


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


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

В итоге получается, что для решения любой по сложности задачи, необходимо умение выделять из входных данных какие-либо особенности, ключевые моменты, сравнивать их с имеющейся базой данных и делать из них атомарные выводы.
Данный процесс, как можно заметить, достаточно трудоемкий, но в идеале должен точно привести к решению. Чтобы уменьшить степень сложности, было бы неплохо строить схемы, подобные mind maps, так что имеются и плюсы и минусы)


воскресенье, 12 июня 2011 г.

Web Application with Go


Некоторое время назад столкнулся с очень интересным языком программирования, носящим гордое название Go)
Оказывается, он существует уже достаточно давно и количество проектов в code.google, написанных на этом языке уже не так мало (http://code.google.com/hosting/search?q=label:Go). Для справки, wikipedia сообщает, что
"На данный момент его поддержка осуществляется для операционных систем FreeBSD, Linux, Mac OS X и частично Windows" (линуксоиды, радуемся!)). 
Насколько я понял, причиной создания Go явилась Идея - попытка сделать нечто такое, что работало бы чрезвычайно быстро, но при этом радовало простотой разработки. Т.е. совместить C/C++ и python)
Т.к. язык разрабатывается компанией Google и поддерживает много интересные вещей (например, сборку мусора или обобщенного программирования), то я просто не мог обойти его своим вниманием.

Пару слов об установке на linux

  • для установки потребуются следующие пакеты:
    $ sudo apt-get install python-setuptools python-dev mercurial bison gcc libc6-dev ed make
  • добавить переменные окружения (директории, конечно, можете выбрать любые)
    export GOROOT=$HOME/go
    export GOARCH=386
    export GOOS=linux
    export GOBIN=$HOME/bin
    export PATH=$GOBIN:$PATH
  • затем добавить эти строки в .bashr и не забыть создать нужные директории
    $ mkdir ~/bin  
    $ chmod 755 ~/bin
  • далее надо клонировать репозиторий Go
    $ hg clone -r release https://go.googlecode.com/hg/ $GOROOT  
    и начать установку, выполнив скрипт .all.bash
    $ cd $GOROOT/src 
    $ ./all.bash
Для разработки можно использовать Go перспективу для eclipse (хотя она мне почему-то не впечатлила), либо взять плагин для gedit (http://go-lang.cat-v.org/text-editors/gedit/) или другого удобного редактора.

Начинаем кодить
Ну теперь стоит прикоснуться к Go и что-нибудь написать) Hello World никому не интересны, поэтому я решил поглядеть на пример написания простенького веб-приложения, которое будет отображать wiki страницу. Итак...
Для начала создадим файл wiki.go, который будет содержать код приложения, и постепенно наполним его смыслом)


package main

import (
"http"
"io/ioutil"
"os"
"regexp"
"template"
)

Конечно, package) здесь говорим, что создаем пакет main и импортируем другие необходимые для работы пакеты. 
  • regexp - для работы с регулярными выражениями
  • template - для работы с шаблонами (далее скажу подробнее)
  • os - для работы со стандартными потоками Stdin,Stdout и ошибками
type Page struct {
  Title string
  Body  []byte 
}
Создаем структуру данных, которая будет описывать веб страницу. Скажу сразу, в Go редко используются точки с запятой, поэтому нужно отбросить внезапно появившееся желание перевести строку следующим образом
func someFunc()
  {
  }
ибо это вызвет негодования компилятора. Как точку с запятой Go трактует конец не пустой строки (при определенных условиях).
 Ну и скорее всего такой способ объявления не порадует C-программистов - создатели Go решили сделать объявление переменных более приближенным к человеческому языку, и теперь это выглядит так: "var A int", т.е. переменная такая-то такого-то типа. Но можно и не заморачитаться с объявлением, написав нечто подобное "p, err := loadPage(title)". Здесь loadPage возвращает два значения, которые принимают переменные p и err.

func (p *Page) save() os.Error {
 filename := p.Title + ".txt"
 return ioutil.WriteFile(filename, p.Body, 0600)
}

func loadPage(title string) (*Page, os.Error) {
 filename := title + ".txt"
 body, err := ioutil.ReadFile(filename)
 if err != nil {
  return nil, err
 }
 return &Page{Title: title, Body: body}, nil
}
Что можно сделать со страницей? Правильно, сохранить в виде файла либо загрузить) Причем сохранение мы описываем прямо на типе Page, указывая перед функцией receiver - (p *Page). Ключевое слово class в Go отсутствует, вместо этого для любого именнованого типа (включая структуры и базовые типы вроде int) можно определить методы работы с ним. Это, конечно, может показаться неожиданным - да что там, это чертовски непривычно и любопытно) Именно поэтому в слайдах документации перед описанием объектно-ориентированности в Go появляется призыв отбросить предубеждения) Для полноты описания, скажу что loadPage возвращает два значения - os.Error отвечает за ошибки, которые могли произойти в процессе загрузки файла. Дальше начинается самое интересное - обработка запросов, приходящих от клиента. Все обработчики будут строиться по определенному принципу
 func someHandler(w http.ResponseWriter, r *http.Request, title string) {
  p, err := loadPage(title)
  if err != nil {
   //some error handler
   return
  }
  renderTemplate(w, "someTemplate", p)
 }
На вход, естесственно, принимается writer для ответа, сам http запрос и название запрошенной страницы. Затем нужная страница загружается по названию и происходит проверка выполнения загрузки. Отображением занимается функция renderTemplate, которая отображает шаблон страницы, заполненный нужными данными.
 func viewHandler(w http.ResponseWriter, r *http.Request, title string) {
 p, err := loadPage(title)
 if err != nil {
  http.Redirect(w, r, "/edit/"+title, http.StatusFound)
  return
 }
 renderTemplate(w, "view", p)
 }

 func editHandler(w http.ResponseWriter, r *http.Request, title string) {
  p, err := loadPage(title)
  if err != nil {
   p = &Page{Title: title}
  }
  renderTemplate(w, "edit", p)
 }

 func saveHandler(w http.ResponseWriter, r *http.Request, title string) {
  body := r.FormValue("body")
  p := &Page{Title: title, Body: []byte(body)}
  err := p.save()
  if err != nil {
   http.Error(w, err.String(), http.StatusInternalServerError)
   return
  }
  http.Redirect(w, r, "/view/"+title, http.StatusFound)
 }
Т.к. это все-таки wiki, страницу можно просмотреть, отредактировать и сохранить измененный вариант. Здесь также присутствуют вызовы методов из пакета http - http.Error (отправляет клиенту сообщение об ошибке) и http.Redirect, которая запрашивает сохраненную страницу на просмотр и приводит к выполнению обработчика viewHandler. Теперь настало время renderTemplate)
 //создаем список, содержащий *Template, ассоциируемый с ключами типа string
 //make - аналог new в cpp, но совершающий еще некоторые действия, помимо выделения памяти
 var templates = make(map[string]*template.Template) 
               
 func init() { //инициализируем список двумя значениями
  for _, tmpl := range []string{"edit", "view"} {
   templates[tmpl] = template.MustParseFile(tmpl+".html", nil)
  }
 }

 
 func renderTemplate(w http.ResponseWriter, tmpl string, p *Page) {
  //шаблон заполняется нужными значениями из p и передается в ResponseWriter  
  err := templates[tmpl].Execute(w, p)
  if err != nil {
   http.Error(w, err.String(), http.StatusInternalServerError)
  }
 }
а шаблон выглядит примерно так:
 <h1>Editing {Title}</h1>

 <form action="/save/{Title}" method="POST">
 <div><textarea name="body" rows="20" cols="80">{Body|html}</textarea></div>
 <div><input type="submit" value="Save"></div>
 </form>
Т.е. просто туда, где надо, подставляем значения, которые будут получены из объекта Page в будущем. Теперь немного валидации. Все, что передал пользовател, надо проверять - это аксиома)
 const lenPath = len("/view/")

 var titleValidator = regexp.MustCompile("^[a-zA-Z0-9]+$")

 func makeHandler(fn func(http.ResponseWriter, *http.Request, string)) http.HandlerFunc {
  return func(w http.ResponseWriter, r *http.Request) {
   title := r.URL.Path[lenPath:]
   if !titleValidator.MatchString(title) {
    http.NotFound(w, r)
    return
   }
   fn(w, r, title)
  }
 }
На счет регулярок здесь все просто, а вот функция makeHandler требует пристального внимания. Она будет использоваться для создания обработчиков (возвращает http.HandlerFunc) и принимает на вход переменную типа функции с нужными параметрами. По сути, это обертка для наших обработчиков, которая помимо основных действий (представленных вызовом fn(w,r,title)) еще и выполняет проверку запрошенного пользователем заголовка. Ну и, наконец, добрались до финала
 func main() {
  http.HandleFunc("/view/", makeHandler(viewHandler))
  http.HandleFunc("/edit/", makeHandler(editHandler))
  http.HandleFunc("/save/", makeHandler(saveHandler))
  http.ListenAndServe(":8080", nil)
 }
Здесь мы просто указываем, какой обработчик будет отвечать за ту или иную страницу. Затем начинаем слушать 8080 порт на localhost'е. Теперь надо все это безобразие собрать и запустить
 $ 8g wiki.go
 $ 8l -o wiki wiki.8
 $ ./wiki
Отмечу, что компилятор 8g (для архитектуры 386) в использовании во многом напоминает обычный gcc. Ну вот и все, мой рассказ окончен. Боюсь, что получилось несколько сумбурно, но я старался заинтересовать) Вот несколько полезных ссылок:

      среда, 8 июня 2011 г.

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