codedot | Recent Entries

Так называемые жесткие комбинаторы принадлежат более узкому классу graph relabeling systems, чем graph rewriting systems, к которым относятся сети взаимодействия в общем случае. По научным меркам, они введены буквально вчера - в нулевых. По их поводу написано полторы статьи, а наивная реализация в современных FPGA/ASIC и для жестких комбинаторов не очень многообещающая, так как агенты одновременно служат и для вычисления и для хранения данных, что слишком затратно для FPGA/ASIC, где суммарный объем памяти регистров всегда на порядок, если не на два, меньше доступной на той же доске встроенной RAM. У последнего неизбежно оказывается бутылочное горлышко.

В определенной перспективе жесткие сети взаимодействия - логичное продолжение развития процессоров. Но на данном этапе этот подход кажется слишком далеким от практики, - возможно, им потребуется еще несколько лет побыть в академических кругах. Впрочем, коммерческие компании типа ARM и сами метят в ту же сторону. К сожалению, пока это только пресс-релизы и провалившиеся проекты, тем не менее, ключевые слова правильные - "clockless computation".

С точки зрения исследований, сети взаимодействия - гораздо более зрелое направление. Первые работы в эту стороны были в конце 80-ых, а первая система взаимодействия (Lamping) решала задачу оптимальной по Levy редукции, даже не называясь собственно системой взаимодействия (Lafont формализовал и обобщил такие системы уже пост-фактум). По данной теме доступны сотни статей, учебник (см. черновой перевод на русский язык соответствующей главы), монография, а также десятки различных программных реализаций, хотя большинство из них представляет собой лишь приложения к публикациям.

В отличие от жестких комбинаторов, сети взаимодействия в чистом виде неприменимы для архитектуры процессоров из-за необходимой перезаписи графов. Однако, возможен совсем другой подход.

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

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

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

Один из вариантов того, как можно читать классическую монографию по λ-исчислению [1]:

параграф 2.1;
упр. 2.4.1 (i)-(iii), 2.4.2-2.4.13;
упр. 2.4.15 (только в оригинале [2]);
параграф 2.2;
упр. 2.4.14;

параграфы 3.1-3.3;
упр. 3.5.1 (v), 3.5.1 (i), 3.5.6 (i), 3.5.2, 3.5.3, 3.5.11;
параграфы 13.1-13.2 до приложения 13.2.3 включительно;

часть II (главы 6-10);

параграф 4.1;
упр. 4.3.2, 4.3.4;
главы 15 и 16.

В каком-то приближении именно этот материал изложен чрезвычайно кратко в [3] (по-русски).

[1] Х. Барендрегт. Ламбда-исчисление, его синтаксис и семантика. Москва, 1985.
[2] H. P. Barendregt. The Lambda Calculus, Its Syntax and Semantics. North-Holland, 1984.
[3] A. Salikhmetov. Lambda Calculus Synopsis. arXiv:1304.0558, 2013.

"PLACEBO : LOUD LIKE LOVE TV : 16.09.13 FULL SHOW - [EXPLICIT LANGUAGE]" (Watch on YouTube)

What's your status?

Issue 735 Resolved and Accepted.

Issue 736 Needs an Interpretation and Accepted as Marked by Don Cragun:

Interpretation response
------------------------
The standard is unclear on this issue, and no conformance
distinction can be made between alternative implementations
based on this.  This is being referred to the sponsor.

Rationale:
-------------
The following changes make the grammar and text reflect existing
practice.

Notes to the Editor (not part of this interpretation):
-------------------------------------------------------
On page 2350, lines 74801-74808, change

%start  complete_command
%%
complete_command : list separator
                 | list
                 ;

to:

%start program
%%
program          : linebreak complete_commands linebreak
                 | linebreak
                 ;
complete_commands: complete_commands newline_list complete_command
                 |                                complete_command
                 ;
complete_command : list separator_op
                 | list
                 ;

Cross-volume change to XRAT...

At page 3700 line 126612 section C.2.10 delete:

The start symbol of the grammar (complete_command) represents
either input from the command line or a shell script.  It is
repeatedly applied by the interpreter to its input and represents
a single "chunk" of that input as seen by the interpreter.

Issue 737 Resolved and Accepted.

http://austingroupbugs.net/view.php?id=737

Shell Grammar Rules for compound_list duplicate the definition of linebreak

linebreak        : newline_list
                 | /* empty */
                 ;

which results in four grammar rules for compound_list instead of two.

Desired Action

On page 2350, lines 74834-74838, change

compound_list    :              term
                 | newline_list term
                 |              term separator
                 | newline_list term separator
                 ;

compound_list    : linebreak term
                 | linebreak term separator
                 ;

http://austingroupbugs.net/view.php?id=736

An empty Shell program and a program consisting of two or more commands separated with NEWLINE tokens are valid Shell scripts. However, Shell Grammar Rules only accept exactly one single command which results in a syntax error against zero commands and two or more commands separated with NEWLINE tokens.

Desired Action

On page 2350, lines 74801-74808, change

%start  complete_command
%%
complete_command : list separator
                 | list
                 ;

%start script
%%
script           : commands linebreak
                 | /* empty */
                 ;
commands         : commands newline_list complete_command
                 |                       complete_command
                 ;
complete_command : list separator_op
                 | list
                 ;

http://austingroupbugs.net/view.php?id=735

When processed by yacc(1), Shell Grammar Rules result in 5 shift/reduce conflicts. These conflicts are all caused by unnecessary linebreak non-terminals in case_item_ns rule after compound_list non-terminals. The linebreak non-terminal are indeed unnecessary because compound_list rule

compound_list    :              term
                 | newline_list term
                 |              term separator
                 | newline_list term separator
                 ;

where

separator        : separator_op linebreak
                 | newline_list
                 ;

itself embeds linebreak definition

linebreak        : newline_list
                 | /* empty */
                 ;

Without the trailing linebreak non-terminals following compound_list, yacc(1) produces no shift/reduce conflicts.

Desired Action

On page 2351, lines 74863-74866, change

case_item_ns     :     pattern ')'               linebreak
                 |     pattern ')' compound_list linebreak
                 | '(' pattern ')'               linebreak
                 | '(' pattern ')' compound_list linebreak
                 ;

case_item_ns     :     pattern ')' linebreak
                 |     pattern ')' compound_list
                 | '(' pattern ')' linebreak
                 | '(' pattern ')' compound_list
                 ;

http://ivan-gandhi.livejournal.com/2404418.html?thread=32857666

Her Diary

Tonight, I thought my husband was acting weird. We had made plans to meet at a nice restaurant for dinner. I was shopping with my friends all day long, so I thought he was upset at the fact that I was a bit late, but he made no comment on it. Conversation wasn't flowing, so I suggested that we go somewhere quiet so we could talk. He agreed, but he didn't say much. I asked him what was wrong. He said, "Nothing." I asked him if it was my fault that he was upset. He said he wasn't upset, that it had nothing to do with me, and not to worry about it. On the way home, I told him that I loved him. He smiled slightly, and kept driving. I can't explain his behavior. I don't know why he didn't say, "I love you, too." When we got home, I felt as if I had lost him completely, as if he wanted nothing to do with me anymore. He just sat there quietly, and watched TV. He continued to seem distant and absent. Finally, with silence all around us, I decided to go to bed. About 15 minutes later, he came to bed. But I still felt that he was distracted, and his thoughts were somewhere else. He fell asleep - I cried. I don't know what to do. I'm almost sure that his thoughts are with someone else. My life is a disaster.

His Diary

My code is broken, can't figure out why.

$ cat >c.c
#include <stdio.h>

int main()
{
        fprintf(stdout, "stdout\n");
        fprintf(stderr, "stderr\n");
        return 0;
}
$ cc c.c
$ 3>&2 2>&1 1>&3 ./a.out | tee log
stdout
stderr
$ cat log
stderr
$

http://iospress.metapress.com/content/l5r8t7n6755286h1/

Universal Hard Interaction for Clockless Computation
Dem Glücklichen schlägt keine Stunde!
Sylvain Lippi

We give a self-contained presentation of Hard Interaction, a rewriting system on fixed graphs. We discuss the universality of natural subclasses of hard systems and highlight the main ideas that lead to a universal system with 7 rules called Hard Combinators.

Keywords: hard interaction nets, abstract machine, asynchronous computation, digital circuits, graph relabeling.

http://tinyurl.com/q9x9k4c

module smm(clk, dst, src, idx, val);
	input clk;
	input [3:0] dst;
	input [3:0] src;
	output [7:0] idx;
	output [7:0] val;

	reg [7:0] ram [0:255];

	wire [7:0] map [0:15];

	assign map[0] = 8'b0;

	genvar i;

	generate
		for (i = 1; i < 16; i = i + 1) begin: anl
			if (i % 2)
				assign map[i] = map[i / 2] + 1;
			else
				assign map[i] = ram[map[i / 2]];
		end
	endgenerate

	assign idx = map[dst];
	assign val = map[src];

	always @(posedge clk)
		ram[idx] <= val;
endmodule

`ifdef SIM
module sim;
	reg clk = 1'b0;
	reg [3:0] dst = 4'b1;
	reg [3:0] src = 4'b1;

	wire [7:0] idx, val;

	smm blk(clk, dst, src, idx, val);

	always begin
		if ($time >= 20)
			$finish;

		#1 $display(val);
		#1 clk <= ~clk;
		#1 clk <= ~clk;
		#1 src <= 4'b101;
	end
endmodule
`endif

http://tinyurl.com/q7yhgjq

$ make
iverilog -Wall -DSIM -o comb comb.v
./comb
0381353f9 0 b2e09fd28ea2916f526a8dbb3a92235f0ddb9b0b1ccd0e7d9b5786f91b62031e
0381353fa 1 00000000627d0f02061ce63584c20662272c527d21f17dfaffb20d7de340423d
0381353fb 0 c90dd726ebe7c2770808fe574e85aba7e90ba2aea8998c70bcb24781d4010955
$

Кто может скорректировать шестнадцатеричное число?

A 0 0 B

Задействуйте свои проверочные колбочки!

http://www.cims.nyu.edu/~eve2/predprey.pdf

Prime number selection of cycles in a predator-prey model
Eric Goles, Oliver Schulz, Mario Markus

The fact that some species of cicadas appear every 7, 13, or 17 years and that these periods are prime numbers has been regarded as a coincidence. We found a simple evolutionary predator-prey model that yields prime-periodic preys having cycles predominantly around the observed values. An evolutionary game on a spatial array leads to travelling waves reminiscent of those observed in excitable systems. The model marks an encounter of two seemingly unrelated disciplines: biology and number theory. A restriction to the latter, provides an evolutionary generator of arbitrarily large prime numbers.

Via

udod's post and Wikipedia.

module brain (clk, sensor, effect);
	parameter nbit = 12;
	parameter size = 2 ** nbit;
 
	input clk;
	input [7:0] sensor;
	output [7:0] effect;
 
	reg sig [0:size - 1];
	reg trace [0:size - 1];
	reg [nbit - 1:0] ram [0:size - 1];
 
	assign effect[3:0] = {sig[3], sig[2], sig[1], sig[0]};
	assign effect[7:4] = {sig[7], sig[6], sig[5], sig[4]};
 
	integer i;
 
	initial for (i = 0; i < size; i = i + 1) begin
		trace[i] = 0;
		sig[i] = 0;
		ram[i] = i;
	end
 
	always @(posedge clk) begin
		for (i = 0; i < 8; i = i + 1)
			sig[ram[i]] <= sensor[i];
 
		for (i = 0; i < size; i = i + 1) begin
			case ({trace[i], sig[ram[i]]})
			2'b00: ram[i] <= ram[i] + 1;
			2'b01: sig[i] <= 1;
			2'b10: sig[i] <= 0;
			2'b11: ram[i] <= ram[i] - 1;
			endcase
 
			trace[i] <= sig[ram[i]];
		end
	end
endmodule
 
`ifdef SIM
module sim;
	reg clk = 0;
	reg [7:0] key;
	wire [7:0] led;
 
	brain core(clk, key, led);
 
	integer c;
 
	always begin
		c = $fgetc(32'h8000_0000);
		if (-1 == c)
			$finish;
 
		key = c[7:0];
		#1 clk = ~clk;
		#1 clk = ~clk;
		$displayb(led);
	end
endmodule
`endif

`define OPZ 4'b1111
`define OPA 4'b0001
`define OPL 4'b0010
`define OPN 4'b0100
`define OPS 4'b1000

`define BIT 15
`define SIZE (2 ** `BIT)

module ram0 (clk, op, led);
	input clk;
	input [3:0] op;
	output [7:0] led;

	reg [`BIT - 1:0] ram [0:`SIZE - 1];
	reg [`BIT - 1:0] n, z;

	assign led = z[7:0];

	always @(posedge clk) begin
		case (op)
		`OPZ: z = 0;
		`OPA: z = z + 1;
		`OPL: z = ram[z];
		`OPN: n = z;
		`OPS: ram[n] = z;
		endcase
	end
endmodule

`ifdef SIM
module sim;
	reg clk = 0;
	reg [3:0] op;
	wire [7:0] led;

	ram0 core(clk, op, led);

	integer ch;

	always begin
		ch = $fgetc(32'h8000_0000);
		case (ch)
		"z", "Z": op = `OPZ;
		"a", "A": op = `OPA;
		"l", "L": op = `OPL;
		"n", "N": op = `OPN;
		"s", "S": op = `OPS;
		-1: $finish;
		default: op = 0;
		endcase

		if (op) begin
			#1 clk = ~clk;
			#1 clk = ~clk;
			$displayb(led);
		end
	end
endmodule
`endif

Килобит можно передать одним сообщением по SMS.

При этом его достаточно, чтобы адресовать любую точку пространства-времени с точностью до планковских единиц измерения на протяжении 10²⁷ лет, что в 10¹⁷ раз больше, чем уже прошло после момента Большого взрыва. Для сравнения, полкилобита адресуют около ста микросекунд. Для данной оценки использовался гиперобъем гиперконуса, который примерно равен гиперобъему гиперкуба со стороной, равной высоте этого гиперконуса.

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

Теперь предположим, что у нас есть хэш-функция F, похожая на SHA-2, но с размером хэша и размером блока ровно в один килобит (вместо обычных 256 бит и 512-битных блоков), и способ адресации, подобный .onion-доменам для анонимных сервисов в сети Tor, причем каждый сервис хранит ровно одну килобитную ячейку памяти.

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

#define A	z = F(z)
#define L	z = recvkbit(z)
#define N	n = z
#define S	sendkbit(n, z)

http://www.halla-aho.com/scripta/husbyn_herattamia_ajatuksia.html

Одна проблема, которую я неоднократно объяснял как властям Хельсинки, так и государственным чиновникам, состоит в том, что критерии и способы измерения "успешности интеграции" являются совершенно ошибочными. По мнению помощника мэра Ритвы Вильянен, отвечающей за иммиграцию, доказательством успеха мер по интеграции является то, что в городе имеется отвечающий за эти вопросы чиновник. Иначе говоря, успешность интеграции измеряется тем, сколько к ней приложено усилий и сколько на неё потрачено денег.

Второй способ измерения интеграции - это опросы самих иммигрантов, обычно из Сомали, насколько им уютно в Финляндии. Можно, таким образом, сказать, что "интеграция" отождествляется с "чувствовать себя как дома". Это проблемная характеристика, как продемонстрировала ниже жительница Мальмё Фатима.

Здесь всё так же, как в Ираке или другой арабской стране. Мне очень уютно в Мальмё.

Здесь всё так же, как в Ираке или другой арабской стране. Мне очень уютно в Мальмё.

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

Успех процесса интеграции необходимо оценивать с помощью объективных и измеряемых критериев, таких как степень зависимости от социальной поддержки, процента безработицы, и относительного уровня преступности. Если эти параметры выглядят каждый год одинаково плохо, необходимо сделать вывод, что интеграция не работает, сколько бы денег мы на это ни потратили, и как бы уютно ни было Фатиме.

Программы на языке MLC (Macro Lambda Calculus) - пример доступен на GitHub - имеют следующий вид:

N1 = M1;
...
Nm = Mm;

M0.

Выражение M0 может содержать произвольное число вхождений имен макросов N1, ... , Nm, а также свободных переменных - обозначим их x1, ... , xn. Комбинатор M, нормальную форму которого мы фактически ищем, получается из программы следующим образом:

M = x1, ... , xn: (N1, ... , Nm: M0) M1 ... Mm.

Комбинатор M, в свою очередь, представим в исчислении взаимодействия, воспользовавшись направленной версией компактной кодировки λ-выражений. Заметим, что конфигурация <x | Γ(M, x)>, как можно видеть из определения, содержит только редексы по левому разыменованию. Следовательно, чтобы инициализировать нашу систему слепой перезаписи графов, достаточно все уравнения конфигурации положить в стек, соответствующий левому разыменованию.

Полученную в результате структуру памяти можно восстановить некоторой последовательностью I инструкций Z, A, L, N и S машины RAM0. Основной цикл работы нашей системы слепой перезаписи графов, реализующей редукцию сетей взаимодействия, также может быть представлен некоторой последовательностью R инструкций Z, A, L, N и S, которая не зависит от вычисляемого выражения. Таким образом, исходный код на языке MLC может быть скомпилирован в следующую программу RAM0:

I;
loop: R;
goto loop;

Данная программа не содержит инструкцию C для условного перехода. Такие детали, как стратегия вычисления, остановка машины, обработка дна стеков и механизм "read-back" во время стягивания конфигурации, были здесь намеренно опущены, чтобы не нагромождать и без того уже объемное изложение.

Profile

Anton Salikhmetov

November 2018

S	M	T	W	T	F	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Syndicate

Page Summary

Распределенные сети взаимодействия
Как читать Барендрегта
LLLTV: Full Show by Placebo
Aardvark 735-737 Accepted (As Marked)
Aardvark 737: two of Shell Grammar Rules unnecessary
Aardvark 736: grammatically accept zero or more Shell commands
Aardvark 735: 5 shift/reduce conflicts in Shell Grammar Rules
Disaster
How to Swap stdout and stderr
Universal Hard Interaction for Clockless Computation
Schönhage's SMM 8-bit Set Operation on Verilog
Combinational Logic for SHA-256
Цветопередача с ошибками
Chromebook in Gigantti
Prime Number Natural Selection
Мой второй кот на Verilog
Мой первый кот на Verilog
Tor-подобная килобитная RAM0
Халла-Ахо об ошибках Швеции и Финляндии
Компиляция из MLC в RAM0

Style Credit

Style: Plain for Tabula Rasa

Expand Cut Tags

No cut tags

Page generated Nov. 4th, 2025 10:19 am