Андрей Власовских

Блог Андрея Власовских

Posts Tagged ‘lang

Курс по языкам программирования осенью 2009

4 комментария

В осеннем семестре 2009 я читаю лекции по языкам программирования на кафедре АиВТ в Политехе. На странице курса я буду выкладывать слайды и другие материалы по курсу. За обновлениями можно следить через блог курса.

Реклама

Written by vlan

2009-09-04 at 12:56

Опубликовано в Uncategorized

Tagged with ,

Курс по языкам программирования

10 комментариев

Закончилась зимняя сессия, время рассказать о прочитанном курсе и подвести небольшие итоги.

В осеннем семестре 2008 читал в Политехе курс лекций «Языки программирования» студентам 5-ого курса кафедры АиВТ. Идеей было дать общий подход к рассмотрению языков, познакомить с функциональным программированием, рассмотреть некоторые компромиссы при проектировании языков. Курс наполовину основан на SICP и языке Scheme, а вторая половина посвящена сравнительному обзору языков C, C++, Python и Java.

Поделюсь впечатлениями о курсе. Во-первых, наши студенты имеют весьма туманные навыки программирования, немного грустно :( Думаю, такое характерно для большинства вузов, хотя наверняка есть и исключения. Они написали к 5-ому курсу слишком мало программ (к тому же весьма простых), и не в состоянии нормально чувствовать и рассуждать о проблемах борьбы со сложностью в программировании. Во-вторых, в курсе получился большой перекос в сторону основ ФП и Scheme в противовес передаче сообщений, параллельности, малым языкам и т. д. Наконец, чтение курса помогает заострить внимание на моментах, которые иначе не были бы замечены и систематизированы.

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

Студентов поздравляю с Татьяниным днём :)

Written by vlan

2009-01-25 at 23:40

Опубликовано в Uncategorized

Tagged with , , , , ,

Генераторы и продолжения

leave a comment »

Выступил с докладом на очередной встрече SPbHUG. Я рассказал о генераторах и продолжениях на примерах Python и Scheme. Вторая часть доклада, в которой рассматриваются акторы (в т. ч. как обобщение продолжений) и их реализация на Haskell, Python и Scheme, будет позже. Слайды по обеим частям и другая инфа лежат в вики SPbHUG.

Written by vlan

2008-09-20 at 17:48

Опубликовано в Uncategorized

Tagged with , , , , , , , , ,

Простой рекурсивный парсер JSON

with one comment

Недавно наткнулся на интересный метод парсинга, который в «Книге дракона» если и описан, то только в виде упоминания. Метод называется рекурсивный спуск с использованием перебора с возвратом (recursive descent with backtracking). Встретил я пример использования этого метода в русском переводе «Введения в функциональное программирование» Джона Харрисона (John Harrison). Парсеры такого типа можно свободно писать с нуля на функциональных языках.

Upd: Выпустил в июле 2009 года библиотеку funcparserlib. Вот пост о ней. Она включает в себя как пример довольно хороший парсер JSON. Материал ниже можно считать устаревшим.

Если есть BNF-подобное описание грамматики без левой рекурсии, то по её нетерминалам легко пишутся функции их разбора. Каждая такая функция является парсером и имеет тип (здесь и далее используется язык Python) Sequence(a) -> (b, Sequence(a)), где a — тип токенов (например, банальных str), b — тип результата разбора (в общем случае object), а Sequence — тип любой последовательности (вот один из вариантов того, что можно считать последовательностью). Для таких функций-парсеров можно ввести очень удобные комбинаторы типа альтернативы, следования, множественного применения. Вообще, это очень показательный пример преимуществ функционального программирования.

Используя этот метод, я написал парсер JSON на Python на основе грамматики из RFC 4627. Известны проблемы парсеров JSON на Python, но я строго следовал грамматике RFC, так что в лексике и синтаксисе ошибок быть не должно. Приведу исходный код. Вначале часть, которую можно было бы сделать библиотекой: несколько удобных комбинаторов, взятых из книги Харрисона, а также объектная обёртка комбинаторов для перегрузки операторов Python ради красоты:

Читать далее…

Written by vlan

2008-07-24 at 05:28

Опубликовано в Uncategorized

Tagged with , , , , , ,

Литературный Python

5 комментариев

Под впечатлением Literate Haskell, я решил сделать что-то подобное для Python, чтобы было проще писать заметки в блоге. Пишу я редко, поэтому это было стимулом повозиться с блогом и написать что-нибудь.

Literate programming, литературное программирование — идея, придуманная и реализованная Дональном Кнутом в 1980-x для C и TEX:

Главная идея — рассматривать программу как средство взаимодействия между людьми, а не набор инструкций для компьютера.

Идею Кнута реализовали и в Haskell. Там поддерживается два стиля разделения кода и текста: добавление к строкам кода > (птичий стиль) или окружение кода парами \begin{code} и \end{code} (стиль LATEX). К тому же для Haskell часто применяют преобразователи кода из ASCII в расширенный математический набор символов, из-за чего код выглядит неприлично красивым :)

Для меня целью было получить хотя бы некоторые преимущества литературного программирования для Python. Я хотел иметь возможность запускать код, который я пишу в заметках для блогов. Раньше приходилось писать его в отдельном исходнике, затем перенося в заметку, либо полагаться на то, что код написан правильно и запускать его не нужно.

Когда я пишу заметки в блог, я размечаю текст при помощи XHTML или (намного чаще) Markdown. В последнем случае при помощи утилиты markdown я перевожу разметку в XHTML. Для автоматизации я использую GNU make: здесь нужен совсем простой makefile. Для себя я придумал довольно простой способ написания текста в Literate Python. Для разделения кода я использовал птичий стиль Haskell. Исходный файл *.lpy автоматически преобразуется при помощи make в два файла: обычный исходник *.py и файл *.xhtml.

Читать далее…

Written by vlan

2008-05-18 at 22:17

Опубликовано в Uncategorized

Tagged with , , , , , , ,

Презентация о языке Jython

leave a comment »

Сегодня выступил с презентацией о Jython на встрече Sun Users Group в Политехе:

Рассказываю о Jython

Об этом же событии можно почитать в блоге Игоря Стручкова. Выкладываю здесь материалы презентации:

Первый слайд презентации о Jython

А так выглядит программка, написанная для демонстрации возможностей Jython:

Скриншот filetree

Также привожу список ссылок:

Written by vlan

2008-02-01 at 19:54

Опубликовано в Uncategorized

Tagged with , , , , , , ,

Выделение изменений в коде

4 комментария

Часто код бывает не очень читаемым. Особенно неприятно, когда простой по своей сути код выглядит как огромное количество проверок, специальных случаев и т. д. Эффект, конечно, начинает действовать, когда такого кода не одна процедура, а целые классы и модули. Тогда оказывается, что, например, вместо 500 строк кода модуль занимает 2000. Из этих 2000 строк только небольшое количество присутствовало в первых версиях модуля. Вначале код лишь кратко описывал суть алгоритмов. Потом же в него добавлялись новые возможности, параметры, исправления багов и т. д. Это, наверное, одна из главных причин обилия специальных случаев в коде.

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

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

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

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

Для пояснения способа возьмём пример. В этом примере для улучшения читаемости используем 3 средства:

  • Замена императивных циклов и проверок на списковые операции и определения списков (list comprehensions или аналогичные конструкции)
  • Выделение второстепенного кода во вложенные процедуры
  • Явное выделение пред- и пост-условий

Примером послужит такой императивный метод Logger.callHandlers из модуля logging из стандартной библиотеки языка Python:

def callHandlers(self, record):
    c = self
    found = 0
    while c:
        for hdlr in c.handlers:
            found = found + 1
            if record.levelno >= hdlr.level:
                hdlr.handle(record)
        if not c.propagate:
            c = None    #break out
        else:
            c = c.parent
    if (found == 0) and raiseExceptions and not self.manager.emittedNoHandlerWarning:
        sys.stderr.write("No handlers could be found for logger"
                         " \"%s\"\n" % self.name)
        self.manager.emittedNoHandlerWarning = 1

Вначале он, наверное, выглядел примерно так:

def callHandlers(self, record):
    c = self
    while c:
        for hdlr in c.handlers:
            if record.levelno >= hdlr.level:
                hdlr.handle(record)
        c = c.parent

Довольно прозрачно, не правда ли? Но потом он оброс различными проверками, условиями и т. д. Посмотрим на него и попробуем сделать метод более читаемым при помощи некоторых приёмов из области функционального программирования.

Императивные конструкции здесь используются как для вызова Handler.handle, наверняка обладающих побочными эффектами, так и для итерации по предкам логгера, что не особо обосновано. Например, при таком подходе приходится помнить, что нужно присвоить c новый логгер, и сделать это нужно именно в конце цикла.

Тот же код, в котором предки получаются функционально:

def callHandlers(self, record):
    def affectedBy(log):
        if log is None:
            return []
        else:
            return [log] + affectedBy(log.parent)
    for log in affectedBy(self):
        for hdlr in log.handlers:
            if record.levelno >= hdlr.level:
                hdlr.handle(record)

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

def affectedBy(log):
    if log is None:
        return []
    elif not log.propagate:
        return [log]
    else:
        return [log] + affectedBy(log.parent)

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

def callHandlers(self, record):
    def affectedBy(log): ...
    handlers = sum(log.handlers for log in affectedBy(self), [])
    found = len(handlers) > 0
    for hdlr in handlers:
        if record.levelno >= hdlr.level:
            hdlr.handle(record)
    if not found and raiseExceptions and not self.manager.emittedNoHandlerWarning:
        sys.stderr.write("No handlers could be found for logger"
                         " \"%s\"\n" % self.name)
        self.manager.emittedNoHandlerWarning = 1

Ну и наконец, хвост метода про выдачу предупреждения явно мешает чтению и отвлекает от основной сути. Обернём его в процедуру, вызвав его как своего рода пост-условие для метода Logger.callHandlers. Полный улучшенный аналог первоначального кода выглядит так:

def callHandlers(self, record):
    def affectedBy(log):
        if log is None:
            return []
        elif not log.propagate:
            return [log]
        else:
            return [log] + affectedBy(log.parent)
    def checkEmittedNoHandlerWarning(found):
        if not found and raiseExceptions and not self.manager.emittedNoHandlerWarning:
            sys.stderr.write("No handlers could be found for logger"
                             " \"%s\"\n" % self.name)
            self.manager.emittedNoHandlerWarning = 1
    handlers = sum(log.handlers for log in affectedBy(self), [])
    for hdlr in handlers:
        if record.levelno >= hdlr.level:
            hdlr.handle(record)
    checkEmittedNoHandlerWarning(len(handlers) > 0)

Если скрыть тела вложенных в блок метода функций, он выглядит так:

def callHandlers(self, record):
    def affectedBy(log): ...
    def checkEmittedNoHandlerWarning(found): ...
    handlers = sum(log.handlers for log in affectedBy(self), [])
    for hdlr in handlers:
        if record.levelno >= hdlr.level:
            hdlr.handle(record)
    checkEmittedNoHandlerWarning(len(handlers) > 0)

Заметим, что метод по-прежнему императивный, т. к. его назначение — вызвать другие императивные методы Handler.handle. И к тому же проверка выдачи предупреждения использует состояние самого объекта Logger для хранения флага. Но с помощью нескольких приёмов FP код метода Logger.callHandlers стал немного чище. Здесь слово чище использовано в двух значениях:

  • Стало меньше изменяемого состояния и присваиваний (чище в смысле FP)
  • Код стал более читаемым, вторичные аспекты меньше заслоняют первичные

Written by vlan

2008-01-14 at 10:10

Опубликовано в Uncategorized

Tagged with , , ,