Группа широко известных в узких кругах отечественных разработчиков компьютерных игрушек (и не только) с недавних пор ведет коллективный блог по адресу http://blog.gamedeff.com
Получается довольно интересно, даже для тех кто с игроделательной промышленностью не связан (вроде меня). Вообще, маловато нынче блогов посвященным всяким нетривиальным практическим программистским вещам, а этот — приятное исключение.
Всячески рекомендую, в общем.
... чей рантайм установлен практически на каждом компьютере — это XSLT, язык для трансформации XML документов.
Если кто не в курсе, в списке возможностей — абсолютное отсутствие побочных эффектов, то есть язык чисто функциональный, и поддержка функций высшего порядка.
Все это в изобилии можно наблюдать в замечательной XSLT-библиотеке FXSL, разработанной Димитром Новачевым. Реализации большинства функциональных идиом, таких как композиция функций, операций со списками по мотивам хаскелевской стандартной библиотеки — map/filter/foldl/zipWith и т.п. Более того, в cvs-версии библиотеки можно найти даже реализацию небольшого LR-парсера на чистом XSLT 2.0
Конечно, выглядит не очень прозрачно, вот например использование foldl для вычисления произведения элементов списка:
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:foldl-func="foldl-func" xmlns:f="http://fxsl.sf.net/" exclude-result-prefixes="f foldl-func" > <xsl:import href="../f/func-foldl.xsl"/> <!-- This transformation must be applied to: ../data/numList.xml Expected result: 3628800 or 3.6288E6 --> <foldl-func:foldl-func/> <xsl:variable name="vFoldlFun" select="document('')/*/foldl-func:*[1]"/> <xsl:output encoding="UTF-8" omit-xml-declaration="yes"/> <xsl:template match="/"> <xsl:value-of select="f:foldl($vFoldlFun, 1, 1 to 10 )"/> </xsl:template> <xsl:template match="*[namespace-uri() = 'foldl-func']" mode="f:FXSL"> <xsl:param name="arg1" select="0"/> <xsl:param name="arg2" select="0"/> <xsl:value-of select="$arg1 * $arg2"/> </xsl:template> </xsl:stylesheet> Created with colorer-take5 library. Type 'xslt2'
В качестве примеров более серьезных программ на XSLT — решалка головоломки Sudoku и CSV2XML конвертер,написанные товарищем по имени Andrew Welch, у которого есть еще очень интересный блог по XSLT.
Если захочется поиграться, берите saxon в качестве XSLT процессора — поддержка XSLT 2.0 в MSXML только планируется (а в Orcas ее точно еще не будет)
Ссылки:
Когда в 2001 году компания Adobe начала строить в Сан-Хосе третью башню своего головного офиса, было решено украсить здание каким-нибудь образцом крайне современного исскуства.
Провели конкурс, и выиграл проект художника Бена Рубина: на последнем этаже здания с помощью мощных светодиодов (количеством >23000 шт) выводится четыре ярких световых пятна, поворачивающихся на разные углы каждые 7.2 секунды. Одновременно с этим вблизи здания на волне 1680 кГц можно услышать саундтрек, состоящий из не менее странного набора звуков. Все это еще реагирует на пролетающие самолеты (рядом аэропорт).
Называется это "Семафор Сан-Хосе", на сайте можно найти и видео того, как вся композиция выглядит:
Плюс к этому, автор зашифровал в последовательности этих вращений и звуков некий набор осмысленных данных, и объявил в августе 2006 года вместе с Adobe конкурс на расшифровку этого сообщения.
Уже через месяц код был расшифрован двумя местными учеными, однако по по правилам конкурса результаты были объявлены только через год — 14 августа 2007.
Вот тут можно почитать довольно увлекательный отчет о том как они пытались сломать этот код, а тут — описание собственно алгоритма.
Ничего сверхъестественного внутри не оказалось — каждому символу ASCII соответствовало определенное сочетание положений дисков / звуков, а данные состояли из заголовка и зашифрованного (вариантом шифра Вижинера) текста.
27723148.0f886b0078628df55b2305efb1cb3729.1188550416.ad19e9ea28e0c0f82d80c4e264544d86
Пожалуй, первая серия постов про типы на этом заканчивается. Продолжение будет.
В этом посте я собрал немножко разных ссылок по теме, часть из них я уже приводил — пускай будут в одном месте:
Вообще:
Про подтипы:
Про наследование:
На русском языке, из интересного, рекомендую почитать в блоге Льва Курца откуда типы вообще возникли — с "более математической" точки зрения.
Еще есть глава про типы в книжке И. Дехтяренко "Декларативное программирование" — сам я, правда, ее подробно еще не смотрел.
Для полноты картины нужно упомянуть еще два специальных крайних случая — типы Top и Bottom.
Тип Top (записывается как 
) — это специальный тип, являющийся супертипом для всех остальных. Если быть ближе к математике — для любого t: t <: T.
В Java и C#, например, ему соответствует тип Object (правда, он не является супертипом для простых unboxed типов вроде int). Вообще в большинстве ОО языков (кроме C++) такой тип присутствует.
Другой полезный элемент системы типов — это тип Bottom 
, который является подтипом для любого типа. Как правило, нет ни одного значения этого типа — в противном случае, это значение допустимо было бы использовать и в контексте когда нужен тип функции (a → b), и, скажем, когда требуется тип сложной структуры данных.
Несмотря на это, тип bottom весьма полезен в некоторых случаях — он может обозначать тип функции, которая никогда не возвращает значений, например, входит в бесконечный цикл или кидать exception:
function div(a : float, b : float) : float =
if (a != 0)
a / b
else
error
Выражение error имеет тип bottom, технически оно выкидывает эксепшен. Благодаря этому выражение if в целом отлично проходит проверку типов1 (имеет тип float).
Однако, введение в систему типов такого специального случая ее неслабо усложняет — кроме Haskell Scala такого типа нет, вроде бы, нигде из более-менее мейнстримных языков.
1 Тут имеется ввиду выражение if, а не statement (как в C++/C#/Java). В C++/C#/Java этому соответствует тернарный оператор ?:
Наследование — это довольно сложный механизм, который с понятием подтипа очень сильно связан, но в то же время вносит довольно много путаницы и ошибок.
Поэтому некоторые неглупые люди даже считают, что наследования лучше избегать вообще.
Обычно есть несколько видов наследования. Первый — самый понятный и полезный — это наследование интерфейса. Он есть во все ОО-языках.
Нужен он, как известно, для очень полезных вещей — обеспечение слабого связывания через полиморфизм. Или, если проще, для того, чтобы некий код мог пользовать другой код через интерфейс, не зная деталей реализации.
Другими словами, конкретный класс Cow, реализующий интерфейс IAnimal, должен иметь соответствующий подтип Cow <: IAnimal. То есть везде, где используется IAnimal можно впихнуть Cow и все будет все ок. По сути, так оно и работает.
Но ситуация заметно усложняется, если наследование происходит не от абстрактного интерфейса, а от другой реализации. В C++ это public наследование, в Java — кейворд extends.
Жизнь усложняется из-за двух основных обстоятельств: Во-
первых, поскольку в классах обычно есть какое-то состояние, две эти реализации это состояние по разному дергают. А во-вторых, в большинстве языков есть такая фича: пусть функция sayMoo() в Cow вызывает Cow::open(), и если open() в наследнике переопределено, а sayMoo() — нет, то sayMoo() будет вызывать переопределенную версию open(). Это называется "открытой рекурсией" (open recursion).
Из-за этих сложностей нередко появляются неприятные баги, и, чтобы постороннему человеку понять как работает WhiteCow, нужно смотреть заодно всю иерархию доверху — таким образом, с инкапсуляцией и слабым связыванием получается нехорошо.
Чтобы избежать всяких отвратительных ошибок, был изобретен всем известный Liskov Substitution Principle — по которому подкласс должен себя вести в точности как родитель в отношении ряда заранее определенных инвариантов, чтобы его можно было считать подтипом родителя. К сожалению, соблюдение этого принципа ложится на плечи программиста, а дело это не очень тривиальное.
Чистое же наследование реализации (private inheritance в C++) страдает похожими недостатками. Только подкласс при таком наследовании уже подтипом родителя не является совсем.
Ссылки:
Такая штука как подтипы и приведение типов встречается повсюду, однако и тут есть некоторые нюансы, о которых лучше не забывать.
Подтип типа τ — это такой тип τ', значения которого можно безболезненно подставлять везде, где предполагается значение типа τ. Записывается это как
τ' <: τ
При этом τ называется супертипом для τ' .
Подтипы очень полезная в хозяйстве вещь: интуитивно понятно, например, что int <: float, то есть везде, где некая функция предполагает на входе действительное число, ей можно передать и целое. Еще очень широко подтипы используются нынче в ООП — когда тип (конкретный класс) "корова" является подтипом интерфейса "животное", другими словами, когда используется наследование интерфейса. Но тут есть уже очень много подводных камней, и к подтипам в ООП лучше вернемся попозже.
Логичное развитие идеи подтипов — это применение ее к параметризованым типам. В том числе ко всяким контейнерам.
Вопрос: если τ' <: τ, то следует ли из этого что List<τ'> будет подтипом List<τ>?
Если да, то тип List<T> называется ковариантным по параметру T, если наоборот (то есть List<τ> <: List<τ'>) — контравариантым.
Классический пример тут это параметризованный тип функции,
X → Y
то есть, она берет значение типа X в качестве аргумента, а возвращает Y. (X,Y - переменные типа, aka имена параметров шаблона/генерика).
Такой тип будет контравариантным по типу аргумента, и ковариантным по типу возвращаемого значения. И правда:
float → float <: int → float
Другими словами, мы вполне можем использовать функцию, принимающую на вход любые действительные значения в тех местах, где фактически на вход передаются целые.
int → int <: int → float
И наоборот, можем использовать функцию, возвращающую целые значения там, где предполагается, что функция возращает действительные.
Теперь вернемся к контейнерам. Возьмем некий шаблонный массив Array<T>. Пускай Cow <: Animal.
function boogaga(Array<Animal> animals)
{
foreach (i in animals)
i.go_home()
}С точки зрения этой функции, Array<Cow> похоже, вполне себе подтип Array<Animal>. И он таковым является в C#, Java и, в общем-то, C++. Однако, если наша функция захочет добавить еще один элемент в массив как animals.add(new Animal) — все сразу поломается, потому как где-то выше этот массив объявлен как Array<Cow>.
function boogaga(Arrayanimals) { animals.add(new Animal); } Array<Cow> cows; boogaga(cows); foreach(i in cows) i.sayMoo(); // у Animal нет метода sayMoo!
Зачем тогда делать массивы ковариантными — это удобно для всяких операций сортировок и поиска, и других операций, навроде первой функции boogaga. А чтобы избежать подобных ошибок, при добавлении в массив элемента не того типа (Animal вместо Cow) в Java и C# при выполнении программы вылетит специальный эксепшен.
Что касается C++, то тут, как обычно, все хуже. Из-за того что типы указателей неявно конвертятся в массивы и наоборот. Очевидно, что Cow * есть подтип Animal * — но благодаря неявным преобразованиям, Cow[] будет подтипом Animal[], и это практически всегда будет приводить к ошибкам при вычислении смещений на элементы массива. см. C++ FAQ Lite.
Да, в Хаскеле, благодаря тому, что он чисто функциональный и никаких присваиваний там нет, все параметризованые типы всегда ковариантны.
Немножко ссылок по теме:
В продолжение предыдущего поста. В основном, по мотивам этого эссе.
Для начала факты:
А теперь несколько самых распространенных заблуждений о системах статической и динамической типизации:
1. Статическая типизация подразумевает объявления типов
Дело в том, что Java, Pascal, C++ и C не просто языки со статической типизацией — это языки с явным объявлением типов. Многим не нравится тратить кучу времени на описание типов функций и переменных, и они не любят статически типизированные языки именно по этой причине. Это зря, потому как, скажем в ML и Haskell типы объявлять в большинстве случаев не нужно, при этом они являются на 100% языками с развитой системой статической проверки типов. Вот и в C# (и C++) сейчас видны подвижки в сторону включения в язык неявного вывода типов в некоторых случаях.
2. Динамическая типизация = "слабая" типизация
Это заблуждение происходит от того, что люди, привыкшие к C/C++ и программирующие на динамических языках используют их, скажем так, не в полной мере. Они боятся рантайм ошибок, помня, что такие ошибки на C могут стоить нескольких дней ковыряния в коде с отладчиком — и поэтому начинают добавлять кучу ненужных комментариев, пытаться всячески явно отслеживать информацию о типах значений, когда это совсем необязательно.
Они совершают кучу ненужных телодвижений — и конечно же, после всего этого, программирование на динамических языках им кажется сложнее. Это все равно что купить новую машину, но не ездить на ней быстрее велосипеда: по лесным тропинкам не поездишь, бензин жрет — велосипед круче в сто раз.
А все дело в том, что в динамических языках сам подход другой, главным образом это быстрое написание кода и интенсивное тестирование потом. В динамических языках есть отличные средства для быстрого и четкого отлова рантайм ошибок, с диагностикой, которая покажет вам, почему именно ошибка произошла (см. идеологию "Let it crash" в Erlang.)
3. Статическая типизация не сочетается с итеративными/agile процессами разработки, заставляет разрабатывать архитектуру целиком и полностью до кодирования, и вообще предполагает водопадную модель.
Некоторые статически типизированные языки и правда устроены так, чтобы стимулировать определенный подход к процессу разработки. Пример этого — требование объявлять все переменные заранее в Паскале, заголовочные файлы в C++ (хотя там это отчасти продиктовано практическими соображениями).
Подобные ограничения частью — пережитки прошлого, когда на стиль программирования серьезно влияли различные ограничения компилятора, частью — осознанные решения, принятые разработчиками языка, чтобы заставить программиста следовать определенной идеологии. Однако, все это не имеет отношения к статической типизации, ни в одной серьезной работе по теории типов нету ничего ни о "разделении интерфейса и реализации", ни об необходимости объявлять переменные заранее, ни о прочих оргвопросах.
4. Языки с динамической типизацией не предоставляют средств для поиска багов на этапе разработки
Распространенный аргумент против динамических языков — это то, что ошибки вылезают у пользователя, а не у разработчика. Однако, в реальности это происходит очень редко, так что аргумент хреновый — программы на динамических языках в среднем содержат не особенно больше ошибок чем на языках вроде C++ и Java. Если это вообще можно измерить.
5. Статическая типизация ведет к более объемным исходникам
Ну данное заблуждение происходит опять таки из распространенного мнения что в статических языках приходится явно объявлять все типы.
Красивый пример из Haskell: есть функция lookup, которая ищет в Map (ассоциативном массиве) значение по ключу. Тип у нее такой:
lookup :: (Monad m, Ord k) => k -> Map k a -> m a
Если кто с хаскелем не знаком — у функции два аргумента, ключ типа k и ассоциативный массив с типом ключа k и типом значений a. Возвращает функция значение типа a, завернутое в монаду m.
Вроде все просто, но что она должна делать если ключа такого нет? Возвращать специальное "пустое" значение? Прерывать вычисления и переходить к обработчику ошибок? Или вообще завершать выполнение программы? Фишка в том что функция эта может делать все вышеперечисленное, вот как это выглядит:
case (lookup bobBarker employees) of
Nothing -> hire bobBarker
Just salary -> pay bobBarker salary
Как Хаскель узнал что мы хотим именно первый вариант, получать значение Nothing в случае ошибки? Он увидел что мы сравниваем результат с Nothing, и вывел соответствующий конкретный тип для монады m. Если б мы не написали этого куска кода, обрабатывающего ошибки сразу, а воткнули бы обработчик ошибок где-нибудь несколькими уровнями выше по стеку — Хаскель тоже правильно вывел бы тип, и можно было б вызывать lookup несколько раз, не заботясь о том, что ключа может не оказаться.
Оригинал: "What To Know Before Debating Type Systems"
В основном это вольный перевод избранных мест из "What To Know Before Debating About Type Systems" и статьи L. Cardelli "Type Systems".
Итак,
Определение
Одного простого и общепринятого определения понятия "тип" или "система типов", как ни странно, нету. Основное назначение системы типов это обнаружение ошибок, которые могут возникнуть при выполнении программы. Весьма известный деятель в области computer science, лауреат премии Тьюринга Лука Карделли приводит такое несложное определение:
Тип переменной -- это множество значений которые может принимать переменная во время выполнения программы.
Определение так себе, конечно. Простое и очень обтекаемое. Не понятно какую роль типы играют для языка, как система типов работает вообще и зачем она нужна.
Если хотите чего-нибудь более философского, то можно обратиться к книжке Б. Пирса "Types and Programming Languages", где он дает более хитрое определение для системы типов:
Система типов — это способ доказать за конечное время, основываясь на синтаксисе и классификации фраз программы по видам вычисляемых ими значений, что программа не ведет себя определенным образом.
На английском это звучит тоже жутко. Ключевые момент здесь в том, что анализируя фразы, составляющие текст программы и используя правила, составляющие систему типов, мы можем исключить некоторое "ошибочное" поведение программы при ее выполнении. При этом анализ этот должен проходить за конечное время.
К тому же, можно придраться и к требованию чтобы проверка типов заканчивалась за конечное время, например в языках Qi и Cayenne это не обязательно так.
Попытка тоже неплохая, однако не очень подходит для случая динамической типизации. Впрочем, чтобы и его охватить, нужно вообще очень сильно постараться.
Строгая типизация
Пара слов о "слабой" и "строгой" типизации — дело в том, что им никто еще сколько-нибудь приличного определения не дал. Выражение "в языке X нет строгой типизации" обычно означает завуалированное "ваш язык X — ацтой", и серьезные дядьки таких слов не используют.
Статическая vs Динамическая система типов
Отсутствие статической проверки типов означает, что операции в языке могут быть применены без проверок к абсолютно любым значениям, в том числе и "неправильным" ("неправильность" может определяться по разному в разных системах). Тут-то и кроется главный нюанс.
Если такие операции приводят к каким-то непредсказуемым в общем случае последствиям, можно смело говорить что типов нету вообще. Товарищ Карделли вот называет это untyped unsafe languages, и приводит в пример ассемблер.
Если последствия таких действий предсказуемы, например, вылетает исключение или в результате получается какое-то специальное значение, то это называется системой динамических типов. Реально между статической и динамической типизацией общего не так уж и много, и в основном все заблуждения здесь как раз происходят от желания найти какой-то общий знаменатель для них. Это бесполезно, слово "тип" в них означает совершенно разные вещи.
Карделли вот вообще осознанно не использует термин "динамическая типизация" — вместо этого у него "динамические проверка [значений]", а подобные языки называет untyped safe languages. Это он не потому что считает, что динамические языки это не тру, а потому что путаница получается серьезная.
Продолжение следует
Поскольку я неожиданно узнал как делать урезанные посты в блоггере (с кнопочкой Read More), потоки моего графоманства теперь ограничивает только отсутствие свободного времени :)
В общем, я решил собрать в кучу все куски ценного знания по некоторым интересным мне темам, раскиданные у меня по мозгу и жесткому диску ноутбука, и написать что-то вроде FAQ или курса молодого бойца. В качестве пилотного выпуска вам, дорогие читатели, грозит много букв по поводу статических и динамических систем типов. Негативные отзывы, комментарии и правки приветствуются — это и мне поможет мозги в порядок привести, и, возможно, кому-то еще пригодится.
![[info]](http://stat.livejournal.com/img/userinfo.gif){kind=small}
