Почти пришла пора покинуть это место.

Немного жаль лишаться такого вида из окна зимой и летом:



Ну да ладно.

Посмотрим, как там будет дальше.
Это музыкой навеяло:

alexo@euromake:/tmp/and$ cat and.c
void *
true_(x, y)
void *x, *y;
{
        return x;
}

void *
false_(x, y)
void *x, *y;
{
        return y;
}

void *
bool_[] = {false_, true_};

void *
and(x, y)
void *(*x)(), *y;
{
        return x(y, x);
}

main(argc, argv)
char *argv[];
{
        int x = argv[1][0] - '0';
        int y = argv[2][0] - '0';

        return (true_ == and(bool_[x], bool_[y]));
}
alexo@euromake:/tmp/and$ cat Makefile
all: and
        ./and 0 0; echo $$?
        ./and 0 1; echo $$?
        ./and 1 0; echo $$?
        ./and 1 1; echo $$?

clean:
        -rm -f and
alexo@euromake:/tmp/and$ make
cc     and.c   -o and
./and 0 0; echo $?
0
./and 0 1; echo $?
0
./and 1 0; echo $?
0
./and 1 1; echo $?
1
alexo@euromake:/tmp/and$ 
Едва заметным прошел момент, когда в нашем распоряжении оказалось достаточно материала, чтобы более явно показать, что системы слепой перезаписи графов действительно обладают полнотой по Тьюрингу. Как и предполагалось ранее, достаточно элегантным способом является симуляция направленных комбинаторов взаимодействия, которые сами обладают Тьюринг-полнотой (см. статью Lafont "Interaction Combinators" 1997 года). И хотя по общим соображениям этот факт был понятен еще полгода назад (см. "Логические операции без сравнений"), на данный момент доказательство можно построить из нескольких пунктов.

Мы будем опираться на предыдущие описания наших конструкций. Напомним, что первым шагом был выбор представления направленных комбинаторов γ, γ*, δ и δ*, а также двух видов связей между агентами: между двумя главными портами и между дополнительным и главным (см. "Слепые комбинаторы взаимодействия"). Затем мы получили представление для недостающего третьего вида связей, то есть между двумя дополнительными портами (см. "Слепые двунаправленные соединения"). Наконец, мы добились того, чтобы за один цикл работы системы количество используемых ячеек оставалось постоянным (см. "Баланс освобождаемой и выделяемой памяти"). В заключение мы пояснили выбор алгоритмов работы системы (см. "Трюки в синтаксическом сахаре λ-исчисления").

Итак, во-первых, заметим, что участие ε не влияет на ход вычислений. Поэтому мы можем заменить ε и ε* на свободные порты, которые, в свою очередь, симулируем парами ξ и ξ*, не связанными с чем-либо на противоположной стороне.

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

В-третьих, по аналогии с aord построим алгоритм слепого копирования агентов, такой, что для данных α, β из набора {γ, δ} на месте β оказывается тот же тип агента, что и у агента α (пусть данная задача послужит несложным упражнением читателю). Копирование агентов γ* и δ* тривиально. Поясним, что копирование необходимо при дублировании (элемент списка D), для чего требуется преобразовать оба освобождаемых после аннигиляции агента (элемент списка A) неизвестных типов, в общем случае, в неизвестные типы.

Тогда в порядке обработки списков, диктуемом балансом освобождаемой и выделямой памяти, то есть за цикл по паре элементов из списков L и R и по одному элементу из списков A и D, машина слепой перезаписи симулирует взаимодействие направленных комбинаторов.



P. S. Как правильно заметил [livejournal.com profile] nivanych, полученная нами система имеет прямое отношение к конкатенационным языкам программирования. А именно, о списках A, D, L и R можно думать как о четырех стеках. Как мы видим, симуляция направленных комбинаторов взаимодействия с помощью слепой перезаписи графов в данном случае действительно породила стековую машину, имеющую одну кучу и четыре стека.
Только что понял, что именно мне напоминает схема вычисления с четырьмя списками L, A, D, R и алгоритмом сортировки "мусора" aord. Она во многом похожа на механизм транскрипции в биологии (процесс синтеза РНК с использованием ДНК в качестве матрицы).

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

Произведя нехитрый поиск, я немедленно натолкнулся на книгу Maribel Fernandez под названием "Models of Computation: An Introduction to Computability Theory" и теперь жду не дождусь заполучить ее в руки:



http://www.amazon.co.uk/dp/1848824335

P. S. Получил, наконец-то. Оказалось неплохим вводным учебником по CS в его современном виде.
+

1. Implement eye-tracking in Project Glass as a pointing input device.
2. Buy Dasher Project by Inference Group before someone else does.
3. Apply real-time collaborative filtering to online dictionaries if your cloud got any balls :-P
4. ???
5. PROFIT!!!
Ключевые слова "blind computation", возникшие в рамках нашей небольшой задачи, приводят к целой туче исследований по BQC, "blind quantum computation", в различных журналах и на arXiv, а также к похожим друг на друга новостным статьям, прошедшим лавиной по интернетам в начале текущего года.

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

http://www.bbc.co.uk/news/science-environment-16636580

Базворды те же: "can be carried out without a cloud computer ever knowing what the data is". Таким образом это тем более любопытно, так как одним из применений систем слепой перезаписи графов мы ранее рассматривали именно Web с точки зрения особенного устройства кэша предвычисленных в облаке результатов для дерева возможных действия пользователя на определенную глубину. И хотя подходы, вроде бы, разные: один по сути нацелен на облегчение клиента, а другой - на вычисления без дешифрования, - темы все-таки кажутся взаимосвязанными.

В связи с этим хотелось бы задать вопрос залу: кто что слышал про BQC, в каком оно примерно состоянии и насколько это действительно может иметь отношение к нашей теме? Сами мы не местные и квантовую физику не знаем.
[livejournal.com profile] polycode @ 2012-08-30 12:33:00:

Deep C

Слайды, рассказывающие о тонкостях языка C в политкорректных «комиксах» (в роли гуру C выступает женский персонаж). Просто класс, получил истинное удовольствие от чтения!

http://www.slideshare.net/olvemaudal/deep-c

[livejournal.com profile] altsoph @ 2012-08-13 09:41:00:

Мэтью Генри aka P01 сделал JS-браузерную дему MATRAKA с 3D-графикой, музыкой и текстом, которая представляет собой 1K PNG-файл, самораспаковывающийся в JavaScript-код:

А кроме того:

Что еще почитать:

И, да, все ссылки работают у меня в Хроме, на кроссбраузерность не проверял.

A two-week trip by car from Nordic to Benelux through the impossible bridge and unlimited autobahns, then back home*.



*Stupid me, to believe there's civilized world any farther. Free advice: turn around when possible.
[livejournal.com profile] khatarnak @ 2012-07-19 11:28:00:

Вот так было:



А вот так стало:



Сейчас готовая книга в формате DjVu доступна здесь.
Про ЖЖ:

— Так… Товарищи! У нас сегодня диспут! На любую тему. Столкновение разных мнений. Утверждение! Возражение! Вот вы, гражданин из первого ряда… Идите сюда! Подойдите! О чем вы хотели бы поспорить?
— Я?
— Да, вы. Именно вы! Я вчера с вами говорил. Вы были таким темпераментным, запальчивым. Вот теперь здесь, на сцене, попробуйте отстоять свое мнение. Покажите, как это делается! Итак, что вам не понравилось?
— Где?
— Вчера. Вам что-то не понравилось. Вы спросили.
— Мне все понравилось. Я еще вчера говорил, что мне все понравилось.
— Ну, это не разговор. Вот, к примеру, мне не нравится ваш галстук!
— Мне тоже! (Сорвал, выбросил.) Тряпье!
— Ну, постойте… Вы не понимаете. Это диспут. А диспут — разговор, где сталкиваются разные мнения. То есть если я «за», вы должны быть «против». У нас должен быть спор, понимаете? Я считаю, что в семье должен быть один ребенок. А вы возражайте!
— А я считаю, что и одного много.
— Нет, вы возражайте!
— Я возражаю!
— А вы возражайте.
— Я возражаю!
— Вот. (После паузы.) Вот. Почему вы возражаете?
— Я возражаю.
— Почему?
— Я возражаю.
— Нет, но почему?
— Я возражаю.
— Это хорошо. Но почему вы возражаете?
— Я возражаю.
— Нет. Вы так просто не возражайте. Вы должны говорить — два.
— Два.
— Вот. (После паузы.) А я считаю, один.
— И я считаю, один.
— Вы же говорили, два.
— Два.
— Вот. (После паузы.) А я говорю, один.
— Два.
— Вот. (После паузы.) А я говорю, один.
— Два.
— Вот видите, уже спор. А я говорю, один.
— Два.
— Вот, чудно. Так что я говорю: один.
— Два.
— Так, один.
— Два.
— Один.
— Два.
— Ну, спорьте, спорьте… Один.
— Два.
— Ну, вы спорьте, возражайте… Один.
— Два.
— Один.
— Два.
Жванецкий

I should have learnt this before.

Let us suppose you have just made a pull request with about twenty commits: something borrowed, something blue, and something from Linus. Say, few commits have typos in their commit logs, few should have been merged into a single one, some should have been removed, a couple of them are so huge that you should split them into several ones, and except, maybe, one lucky change, the rest is to be completely rewritten.

In GitHub, it is however not common practice to deal with pull requests that way. After a pull request has been reviewed, it usually happens to be appended with nearly as many commits as in the original pull request. When the pull request has finally been merged, this in turn makes the master branch contain almost nothing but garbage.

Reviewing patch series and making the developer redo all the stuff from the very beginning, probably several times, might look as inapplicable approach to deal with pull requests. Besides, it does not guarantee the master branch not to contain any garbage. Of course, it is not a silver bullet. Nevertheless, it does help avoid more than 90% of junk, keeping the master branch log much more clear. That appears to be really helpful when you deal with a bug using git-bisect(1).

There exists at least the following scheme which makes GitHub-style pull requests do the trick, quite close to reviewing patch series in LKML.

  1. Make a new pull request from bug2645 to master.
  2. Discuss the changes and how to improve it until it is clear what to do for the next iteration.
  3. Close the pull request in order to save the resulting review.
  4. Fork a backup with git branch bug2645-backup bug2645 just in case.
  5. Play with git rebase -i master (edit and squash), git reset HEAD^ (splitting commits), git add -p wtf.c (s and e), and git stash -k (test results before committing) to address the comments from the review.
  6. When you are done, type git push -f origin bug2645 and start from the very beginning.

This scheme has been tested on an artificial task simulating huge and ugly patch series. Specifically, we cleared the master branch, and pretended that its backup is the development branch far away ahead of master. Then, we agreed on the rules to write commit logs in a different manner than it was before. Namely, all commit logs should have the form of 2645: update time stamps in msync(), where 2645 is the number of an issue on GitHub which corresponds to the applied changes. This way, one can always track which exactly bug implied each particular commit.

So, give it a try!

From the Preface

Have you ever...

  • wasted a lot of time coding the wrong algorithm?
  • used a data structure that was much too complicated?
  • tested a program but missed an obvious problem?
  • spent a day looking for a bug you should have found in five minutes?
  • needed to make a program run three times faster and use less memory?
  • struggled to move a program from a workstation to a PC or vice versa?
  • tried to make a modest change in someone else's program?
  • rewritten a program because you couldn't understand it?

Was it fun?

These things happen to programmers all the time. But dealing with such problems is often harder than it should be because topics like testing, debugging, portability, performance, design alternatives, and style -- the practice of programming -- are not usually the focus of computer science or programming courses. Most programmers learn them haphazardly as their experience grows, and a few never learn them at all.

In a world of enormous and intricate interfaces, constantly changing tools and languages and systems, and relentless pressure for more of everything, one can lose sight of the basic principles -- simplicity, clarity, generality -- that form the bedrock of good software. One can also overlook the value of tools and notations that mechanize some of software creation and thus enlist the computer in its own programming.

Our approach in this book is based on these underlying, interrelated principles, which apply at all levels of computing. These include simplicity, which keeps programs short and manageable; clarity, which makes sure they are easy to understand, for people as well as machines; generality, which means they work well in a broad range of situations and adapt well as new situations arise; and automation, which lets the machine do the work for us, freeing us from mundane tasks. By looking at computer programming in a variety of languages, from algorithms and data structures through design, debugging, testing, and performance improvement, we can illustrate universal engineering concepts that are independent of language, operating system, or programming paradigm.

This book comes from many years of experience writing and maintaining a lot of software, teaching programming courses, and working with a wide variety of programmers. We want to share lessons about practical issues, to pass on insights from our experience, and to suggest ways for programmers of all levels to be more proficient and productive.

http://cm.bell-labs.com/cm/cs/tpop/preface.html

В прошлом году я довольно пристально следил за выходом Google Chromebook, прежде всего за моделью от Samsung. Довольно быстро после выхода он появился и в UK, откуда уже можно было заказать по EU без таможни. Единственная проблема с заказом из UK, на самом деле, оказалась с клавиатурой. Дело в том, что я физиологически не принимаю никакую другую клавиатуру, кроме обычной американской, на которой обе клавиши Shift и клавиша Enter широкие, а не изуродованные неведомыми силами.

Заказ же из USA в EU появился значительно позже. Это интернет-магазин TigerTirect.com. Между банковским переводом и получением посылки в UPS прошла ровно одна неделя. Еще неделю я к нему присматривался. А на прошлых выходных я, наконец, решился на эксперимент: использовать только Chromebook для работы. Для этого мне и понадобился SSH-доступ со screen(1) при входе в систему. Мне нужно еще перенаправлять порт, чтобы легче тестировать Web-приложение, так что к файлам с ключами добавился и config с соответствующими строчками.

По большому счету, я годами не использовал ничего, кроме терминала с SSH и браузера. Все остальное выпрыгивало, пугало, мешало и всячески притягивало внимание, отвлекая от работы, как тамагочи. Этому место, может быть, на телефоне, но не на рабочей машине. Конечно, MacBook Pro производительный, однако я не видел смысла таскать за собой лишний килограмм ради каких-то редких случаев локальной сборки программного обеспечения сомнительного происхождения. Пусть греется сервер, а не ноутбук.

Итак, теперь у меня обычно одно окно браузера на весь экран с тремя пин-табами: почта (с нотификациями на рабочем столе), оболочка через SSH (на iMac дома) и собственно тестируемое приложение. Остальные вкладки используются как обычно: документация, GitHub, багтрекер, Wiki, и так далее. Используется нестабильная версия системы, однако, как я понял, они недавно обновили стабильную ветку одной из бета-версий, вместе с выпуском следующей версии компьютера от Samsung, которая теперь еще больше косит под Apple.

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

А вот этого я уже в других языках программирования как-то не видал. Эдакая «лиспо-лямбда» получается:

alexo@codedot:~$ wscat -c ws://localhost:8080/

connected (press CTRL+C to quit)

< (function () {
			socket.say = function(data) {
				data = JSON.stringify(data);
				this.send(data);
			};
		})(undefined)

< (function () {
			socket.say("Hello World!");
		})(undefined)
> "Hello World!"

< (function (data) {
			window.alert(data);
		})("Hello World!")

disconnected

alexo@codedot:~$

Кстати, wscat вчера починили.

Опубликовал свой первый пакет на свалке Node.js. Теперь запустить пример с «Hello World!», который будет доступен по локальному адресу, можно следующим образом:

alexo@codedot:/tmp$ npm install uniweb
npm http GET https://registry.npmjs.org/uniweb
npm http 200 https://registry.npmjs.org/uniweb
npm http GET https://registry.npmjs.org/ws
npm http 304 https://registry.npmjs.org/ws

> ws@0.4.13 preinstall /private/tmp/node_modules/uniweb/node_modules/ws
> make

node-waf configure build
Checking for program g++ or c++          : /usr/bin/g++ 
Checking for program cpp                 : /usr/bin/cpp 
Checking for program ar                  : /usr/bin/ar 
Checking for program ranlib              : /usr/bin/ranlib 
Checking for g++                         : ok  
Checking for node path                   : ok /usr/local/lib/node_modules 
Checking for node prefix                 : ok /usr/local 
'configure' finished successfully (0.183s)
Waf: Entering directory `/private/tmp/node_modules/uniweb/node_modules/ws/build'
[1/4] cxx: src/validation.cc -> build/Release/src/validation_1.o
[2/4] cxx: src/bufferutil.cc -> build/Release/src/bufferutil_2.o
[3/4] cxx_link: build/Release/src/validation_1.o -> build/Release/validation.node
[4/4] cxx_link: build/Release/src/bufferutil_2.o -> build/Release/bufferutil.node
Waf: Leaving directory `/private/tmp/node_modules/uniweb/node_modules/ws/build'
'build' finished successfully (1.050s)
npm http GET https://registry.npmjs.org/commander
npm http GET https://registry.npmjs.org/options
npm http 304 https://registry.npmjs.org/commander
npm http 304 https://registry.npmjs.org/options
uniweb@1.1.1 ./node_modules/uniweb
└── ws@0.4.13 (options@0.0.3, commander@0.5.2)
alexo@codedot:/tmp$ npm test uniweb

> uniweb@1.1.1 test /private/tmp/node_modules/uniweb
> node hello.js

Не считая примера, код пакета занимает всего 62 строки. Ниже комбинированный HTTP/HTTPS/WebSocket-сервер на его основе, который работает под рутом, так как использует порты 80 и 443, и ожидает SSL-сертификат в файлах key.pem и cert.pem:

var start = require("uniweb");
var read = require("fs").readFileSync;

function hello(socket) {
	socket.on("message", function(msg) {
		socket.send("alert(\"" + msg + "\");");
	});
	socket.send("socket.send(\"Hello World!\");");
}

start({
	handler: hello,
	domain: "example.com",
	key: read("key.pem"),
	cert: read("cert.pem")
});

Below are index.html and server.js sources. The server expects the index.html file as well as SSL key.pem and cert.pem to be located in the current directory.

<!doctype html>
<meta charset="utf-8">
<title></title>

<script>
var socket = new WebSocket("ws://localhost/");

socket.onmessage = function(msg) {
	eval(msg.data);
};
</script>

var read = require("fs").readFileSync;

function server(socket)
{
	socket.on("message", function(msg) {
		socket.send("alert(\"" + msg + "\");");
	});
	socket.send("socket.send(\"Hello World!\");");
}

function client(ws)
{
	var html = read("index.html", "utf8");

	return function(request, response) {
		response.writeHead(200, {
			"Content-Type": "text/html"
		});
		response.end(html.replace("ws", ws));
	};
}

function uniweb(host, ws, port)
{
	(new (require("ws").Server)({
		server: host
	})).on("connection", server);
	host.on("request", client(ws));
	host.listen(port);
}

uniweb(require("http").createServer(), "ws", 80);
uniweb(require("https").createServer({
	key: read("key.pem"),
	cert: read("cert.pem")
}), "wss", 443);
<!doctype html>
<meta charset="utf-8">
<title></title>

<script>
var socket = new WebSocket("wss://127.0.0.1:8888/");

socket.onmessage = function(msg) {
	eval(msg.data);
};
</script>

The above HTML5 code successfully validated by W3C, unlike the previous one, uses the secure WebSocket protocol. One can easily create a Node.js-based secure WebSocket server for such a client as follows. We assume files named key.pem and cert.pem to contain the private key and the corresponding certificate both PEM-formatted, and that server.js contains the source code from below. If you have the ws package installed using npm install ws, running node server.js will then start the server.

var fs = require("fs");
var https = require("https");
var ws = require("ws");

var host = {
	server: https.createServer({
		key: fs.readFileSync("key.pem"),
		cert: fs.readFileSync("cert.pem")
	})
};

(new ws.Server(host)).on("connection", function(socket) {
	socket.on("message", function(msg) {
		socket.send("window.alert(\"" + msg + "\");");
	});
	socket.send("socket.send(\"Hello World!\");");
});

host.server.listen(8888);
Page generated Nov. 25th, 2025 09:03 pm
Powered by Dreamwidth Studios