вторник, августа 24, 2010

Душа?

Я, кажется, понял, что такое душа :) По крайней мере, с точки зрения кибернетики.

Понятно, что человек — достаточно сложное устройство. Так что будем рассматривать устройство попроще, а именно: чёрный ящик с десятью кнопочками и десятью лампочками. В зависимости от нажатия кнопочек загораются какие-то лампочки. Можно выделить два типа поведения таких ящиков:

  1. Какие лампочки сейчас горят, зависит только от того, какие кнопочки сейчас нажаты, и ни от чего больше.

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

Пусть мы хотим моделировать такие ящики на Haskell. Пусть мы ввели тип X для обозначения множества нажатых в данный момент кнопок, и тип Y — для множества горящих лампочек. Например, это можно сделать так:

import qualified Data.Set as S
type Button = Int
type Lamp = Int
type X = S.Set Button
type Y = S.Set Lamp

Тогда ящик из пункта 1) можно полностью описать функцией с типом

f1 ∷ X -> Y

Это так называемая чистая функция. Заметим, что такая функция не может создавать слишком сложного поведения ящика. Действительно, если f1 очень замысловатая, то, тыкая в кнопки на ящике, мы не сможем разгадать устройства функции f1. Но мы сможем составить табличку из двух колонок: «нажатые кнопочки», «горящие лампочки». Формально говоря, эта таблица — график функции f1. Строк в этой таблице должно быть всего-то навсего 2^10, т.е. 1024. Пользуясь этой таблицей, мы легко сможем предсказывать поведение ящика, сколь бы сложной ни была функция f1.

Ящик же из пункта 2) можно описать функцией с более сложным типом:

import Control.Monad.State
f2 ∷ X -> State St Y

где St — какой-нибудь более или менее замысловатый тип данных. Гипотеза: чем сложнее тип St, тем сложнее может быть поведение функции f2. Возьмём сначала очень простой тип: type St = Bool. Тогда f2 представляет собой конечный автомат с двумя состояниями. Ничего принципиально более сложного, чем двухтактный счётчик, из такого автомата не сделать. Возможно, например, такое поведение: при чётных нажатиях на первую кнопку загорается пятая лампочка, а при нечётных - десятая. Этот алгоритм легко разгадать наблюдениями, никакой загадочности в нём нет. Если type St = Int, то можно придумать уже гораздо более сложное поведение. А уж если, скажем,

data Tree a = Node a | Branch [Tree a]
type St = Tree [Maybe Int]

или что-нибудь ещё такое понавороченнее, то поведение f2 может быть очень сложным и даже загадочным. В процессе нажимания на кнопочки на таком ящике и наблюдения за лампочками нас вполне может посетить мысль, что в ящике сидит какой-то инопланетянин, а кнопочки и лампочки — это у него такой способ общения. Ну, я думаю, вы уже поняли мою гипотезу: душа — это и есть вот это состояние в смысле монады State!

Отсюда следуют некоторые интересные мысли. Например, мы часто говорим о человеке что-нибудь вроде «у него сложный характер» или там «у него настоящая загадочная русская душа»… Оказывается, в указанном выше смысле, понятию сложности души можно придать вполне конкретный смысл — это просто сложность типа данных! :)

Или рассмотрим какую-нибудь очень сложную программу, например банковскую опердень или ОС Windows. Такие программы обладают одновременно двумя свойствами:

  • Их поведение во многих случаях загадочно, далёкие от ИТ пользователи даже часто склонны их одушевлять;

  • Они написаны так, что содержат изменяемое состояние, причём это состояние само по себе очень сложное (ну, например, состояние базы данных).

В свете рассуждений выше мы видим, что одновременность появления этих свойств отнюдь не случайна. «Душа» таких программ по сложности сопоставима с душой человека, что ж удивляться, что она загадочна? Кроме того, оказывается, те далёкие от ИТ пользователи правы в вышеприведённом смысле.

понедельник, августа 02, 2010

Небольшая иллюстрация к предыдущему

Нашёл у Гейтинга [1] иллюстрацию к изоморфизму Карри-Ховарда. Что интересно: насколько я понял, эта иллюстрация была сформулирована до самого изоморфизма.

«Пусть A обозначает свойство натурального числа быть кратным 8, B — быть кратным 4, C — кратным 2. 8a мы можем записать как 4∙2a; благодаря этому математическому построению (P) мы видим, что свойство A влечёт свойство B, или A → B. Подобное построение (Q) показывает, что B → C. Употребляя сначала P, потом Q (суперпозиция P и Q), мы получаем 8a = 2∙(2∙2a), что доказывает A → C. Этот процесс остаётся пригодным, если вместо A, B, C мы подставим произвольные свойства. А именно, если построение P доказывает, что A → B, и построение Q доказывает, что B → C, то суперпозиция P и Q доказывает, что A → C».

Если считать «построения» функциями, то из этого рассуждения увидим, что существование операции суперпозиции двух функций (P и Q) доказывает транзитивность импликации:

(.) :: (b -> c) -> (a -> b) -> a -> c

[1] А. Гейтинг. Введение в интуиционизм. М.: Мир, 1965.