Литуратурная аппаратура на VHDL

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

Сперва о инструментарии, который мною использовался. Это была реализация системы литературного программирования noweb, которая не привязана ни к какому языку программирования (что оказалось крайне приятным, так как VHDL специально никто ничего подобного не делал). В качестве редактора использовался emacs + noweb.el. Текстовая часть кода оформлялась в LaTeX (тут была альтернатива в качестве html). В принципе, эти инструменты позволили с комфортом работать над задачей, после некоторой привычки. К сожалению, noweb.el является достаточно кривой реализацией, с некоторым количеством неприятных моментов (часто слетает подсветка синтаксиса).

Русская вики даёт следующее определение для литературного программирования:

Литературное (английский термин намеренно двусмысленный), или грамотное программирование (англ. Literate Programming) — концепция, методология программирования и документирования. Термин и саму концепцию разработал Дональд Кнут в 1981 году при разработке системы компьютерной вёрстки TeX.

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

Не знаю как все, но лично я, как правило, перед тем как решать какую-то задачу, в случае если она не совсем тривиальна, или по тем или иным причинам для меня не обычна, я сперва беру блокнот с ручкой, и пишу свои рассуждения о ней на бумаге. А затем, поглядывая в записи, пишу код. Само собой, никакого желания ни документировать, ни писать комментарии после этого как правила нет. В случае же использования литературного программирования, этот текст пишется в текстовом редакторе. Причём, не имеет никакого значения, как именно должен быть записан код, текст пишется именно так, как он думается, как он придумывается. Вот формулируется мысль о каком-то конкретном аспекте поведения, и прямо тут же, вы пишете:

<<фича такая-то>>=

Код этой фичи, абсолютно выдранный из контекста.

@

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

<<имя_файла>>=

Заголовок такой-то
<<контескт такой-то фичи>>

<<фича такая-то>>

<<фича такая-то>>

<<фича такая-то>>

Ещё какой-то код, необходимый тут.

@

Теперь, мы можем двумя простыми командами получить как статью, в которой довольно неплохо описано, что делает программа (noweave -delay programm.nw > text.tex) и собственно сам код программы (notangle -Rимя_файла programm.nwп > имя_файла). Так как вы нормальный человек, а следовательно не достаточно внимательны, команда для кода скорее всего любезно скажет вам, какие аспекты программы вы забыли, и вы будете вынуждены, добавить пару абзацев текста.

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

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

Преимущества:

- Вы пишите код к той форме и в том порядке, в котором вы думаете. Соответственно он намного проще проверяется, намного проще восстанавливается в голове, так как в нём все его детали всегда явно присутствуют и вводятся последовательно.

- Наличие такой детальной документации в коде, позволяет в нём разобраться любому человеку, и для этого не обязательно знать язык разработки.

Недостатки:

- Не понятно как это можно применять для динамических языков, таких как Smalltalk и Lisp.

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

- Не совсем понятно, как такой стиль может применяться в коллективе, так как все думают по разному.

- (самый существенный, также его отмечает Кнут) Мало уметь программировать, надо уметь и писать. 

Непонятные моменты:
- Время написания программы значительно выше, нежели в случае традиционного подхода, но в тоже время количество ошибок меньше. Сложные ошибки исправлять проше, а простые труднее.

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

http://dl.dropbox.com/u/1619524/src/literate_lab1.zip.

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

5 + 1 главных особенностей, которые необходимо знать о конструкторах в Scala

Вольный перевод данного поста: Top 5 Things to Know About Constructors in Scala и плюс ещё одна особенность, на которую волей случая наткнулся.

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

1. Как сделать конструктор с параметром?

public class Foo() { public Bar bar; public Foo(Bar bar) {  this.bar = bar;  } }

На Scala это будет выглядеть так:

class Foo(val bar:Bar)

В данном случае val создаёт неизменяемое публичное поле, используте var для создание изменяемых полей.

2. Как сделать приватные поля?

public class Foo() { private final Bar bar; public Foo(Bar bar) { this.bar = bar; } }

На Scala это будет выглядеть так:

class Foo(private val bar: Bar)

Приватные поля не так необходимы как в Java и вы можете делать все поля публичными. В случае необходимости вы можете потом определить геттер и сеттер без внесения изменений в клиенты.

3. Как использовать super()?

public class Foo() extends SuperFoo { public Foo(Bar bar) { super(bar); } }

На Scala это будет выглядеть так:

class Foo(bar:Bar) extends SuperFoo(bar)b

4. Как создать более одного конструктора?

public class Foo { public Bar bar; public Foo() { this(new Bar()); } public Foo(Bar bar) { this. bar = bar; } }

На Scala это будет выглядеть так:

class Foo(val bar:Bar) { def this() = this(new Bar) } Второй конструктор (this()) делегирует свои обязанности другому конструктору.

5. Как сделать "bean style" геттер и сеттер?

public class Foo() { private Bar bar; public Foo(Bar bar) { this.bar = bar; } public Bar getBar() { return bar; } public void setBar(Bar bar) { this.bar = bar; } } На Scala это будет выглядеть так:

class Foo(@BeanProperty var bar:Bar) Поле bar является публичным, что не представляет проблем в Scala (смотри выше).

(далее от переводчика)
6. Как сделать конструктор c несколькими выражений?
Данный пункт отмечен в примечание к посту, но я покажу его подробнее.

public class Foo() {
  private Int b; 
  private Int y; 
  public Foo(Int b) { 
    this.b = b; 
  } 
  public Foo() { 
    this.y = java.util.Random.nextInt();
    this.y += 1;
    this.b = b; 
  } 
}

На Scala это будет выглядеть так:

class Foo (val b:Int) {
  var y = 0
  def this() = {
    this(3)
    y = scala.util.Random.nextInt
    y += 1
  }
}

Язык Scala накладывает ограничение на метод this(): "- первым вызовом конструктора должен быть вызов другого конструктора, причем любого - важно только чтобы цепочка вызовов конструкторов в итоге привела к вызову первичного конструктора"

Спасибо javverwocky, за указание на ошибку и пример.

Модель простейшего процессора на Haskell

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

Описание процессора:

Сплошной линией обозначены линии данных. Пунктиром обозначены управляющие сигналы.

Основные характеристики:

Разрядность процессора: 8 бит. 

Организация памяти: гарвардская, с отдельными блоками памяти для команд и данных. 

Подсистема обработки прерываний и команды вызова подпрограмм отсутствует. 

Внешние устройства (для данной работы это светодиоды, двухпозиционные переключатели и тактовые кнопки) отображаются в адресное пространство данных. Работа с ними выполняется по опросу. 

Команды выполняются за 2 или 3 такта (в зависимости от типа команды): 1) Выборка команды 2) Выборка операндов 3) Выполнение команды. 

Регистры:

PC — счетчик команд

IR — регистр инструкций

AR — регистр адреса операнда

C — флаг переноса/заёма

Z — флаг нуля

Описание системы команд можно найти в файле Cmd.hs, функция cmd. Функциональность описана в комментариях с использование C синтаксиса. pmem и dmem - память программ и данных соответственно. arg - аргумент команды.

Модель.

Модель создавалась с учётом того, что бы в случае необходимости её можно было относительно легко перетащить в Verilog, а значит вариант с наивным case по командам отпадал вроде такого:

command 0x01 state = someFunctiom1 state

command 0x02 state = someFunctiom2 state

или в без точечном стиле (в основном будет использовать именно он):

command 0x01 = someFunctiom1

command 0x02 = someFunctiom2

Не подходит, так как в данном случае пришлось бы переписывать весь код полностью. Разбираясь с принципами работы процесса, довольно быстро становится очевидно, что наиболее простой способ описания работы команд - потактово задать функции, определяющие изменения состояния процессора после каждого из них. Функции на каждый такт можно получить при помощи композиции нескольких простейших функций, которые были бы в реальном процессоре представлены управляющими сигналами (назовём их микрокомандами, хотя ими они и не являются). К примеру, первый такт программы представляет из себя выборку команд, который может быть описан через композицию сигнала для инкриминирования регистра PC и чтения команды в регистр IR. В моделе это выглядит так:

nextCommand = incPC . pmem2IR

К сожалению, модель вычислений языка Haskell довольно сильно отличается от модели SDF, которая присутствует в Verilog (или отчасти присутствует), и мы вынуждены следить за соблюдением правильной последовательности операций при композиции функций. Использую этот подход, вся система команд может быть описана в одной таблице следующим образом:
cmd = [(0x01, Nop, NoneArg, [nop]), -- nope
       (0x00, Hlt, NoneArg, [hlt]), -- halt model
       (0x02, Ldm, DmemArg, [incPC . pmem2AR, dmem2acc]), -- acc = dmem[arg]; c = const; z = (dmem[arg] == 0)
       (0x03, Ldi, ValueArg, [incPC . pmem2acc]), -- acc = arg; c = const; z = (arg == 0)
...
В данном случае важен только первый (код команды) и последний (поведение) элемент кортежа (остальные необходимы для компилятора). Поведение команды задаётся списком функций, каждая из которых выполняется за такт. Значительная часть функций задаётся композицией микрокоманд которые имеют тип (State -> State).

Таким образом, описание микропроцессора сводится к определению: 

• типа данных State - хранит состояние процессора в текущий момент; 
• таблицы cmd, в которой описываются все команды; 
• микрокоманды, путём композиции которых получаются собственно сами команды; 

Само моделирование производится следующим небольшим кусочком кода:

step (State {on = False}) = return ()

step state = step $ executeCommand state' commandFlow

    where 

      state'@(State{ir = hexCommand}) = nextCommand state

      commandFlow = commandFlowFromInfo $ getCommandInfo hexCommand

      executeCommand state [] = state

     executeCommand state (f:fs) = executeCommand (f state) fs

В нём происходит следующее, производится выборка команды (PC инкриминируется), из таблицы cmd выбираются команды, список функций команд по очереди применяется к текущему состоянию и далее по рекурсии. 

Явные недочёты: 

• Внешние устройства "зашиты" в структуру модели. По хорошему их необходимо вынести из модели, и обрабатывать в step. (тут же использование Trace, для функциональности). 
• Использование неправильных структур данных (в частности для cmd). 
• В модуле отвечающем за моделирование захардкодено всё, что только можно. 

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

Cmd.hs - http://gist.github.com/492325

SimpleRiscModel - http://gist.github.com/492327

KDE, CapsLock как новый Control

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

Вот где искать:
General -> Personal -> Region & Language -> KeyboardLayout -> Advanced -> (отсюда как в гноме) Ctrl key position -> Make CapsLock an additional Ctrl.

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

Обход бинарного дерева с константным количеством памяти.

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

Задача:

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

Рассуждения:

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

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

• Создаём указатель на голову нашего импровизированного списка вершин в которых мы не были. 
• В случае, если мы попадаем на развилку, то добавляем в этот список ещё один элемент, в котором отмечаем текущую вершину. Память для нового элемента списка находим в правой ветке, а сами переходим в левую.
• В случае, если мы попадаем в листок, то смотрим не пуст ли наш список, если это так, то откусываем первый элемент (последняя развилка), и останавливаем нулевые указатели. Переходим конечно в правую ветку относительно последней развилки.

Вот два варианта реализации на языке salltalk и java (если кто-то может попинать меня за стиль кодирования, прошу это сделать, так как сейчас учу этот язык). Проверка корректности производится при помощи использования свёрток, в данном случае свёртка суммы.

Код на Java для узла:

public class Node<T extends Comparable<T>> {
    private T value;
    private Node<T> left, right;

    public Node(T value) {
        this.value = value;
    }

    public void add(T value) {
        if (left == null) {
            left = new Node<T>(value);
            return;
        }
        if (right == null) {
            right = new Node<T>(value);
            return;
        }
        if (left.getSize() < right.getSize()) {
            left.add(value);
        } else {
            right.add(value);
        }
    }

    public void addSort(T value) {
        if (this.value.compareTo(value) == -1) {
            if (left == null) {
                left = new Node<T>(value);
            } else {
                left.addSort(value);
            }
        } else {
            if (right == null) {
                right = new Node<T>(value);
            } else {
                right.addSort(value);
            }
        }
    }

    public int getSize() {
        return 1 + (left == null ? 0 : left.getSize())
                + (right == null ? 0 : right.getSize());
    }

    public Node<T> getNext() {
        if (!(right == null)) return right;
        if (!(left == null)) return left;
        return null;
    }

    public boolean isNormalBranch() {
        if (left == null && right != null) return true;
        if (left != null && right == null) return true;
        return false;
    }

    public boolean isLeaf(){
        return left == null && right == null;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }

    public T getValue() {
        return value;
    }

}

Код на Java для корня, в котором и реализован алгоритм:

import java.util.*;

interface Callable<T1, T2> {
        public T1 call(T1 acc, T2 e);
        }

public class Root<T extends Comparable<T>> {
    private Node<T> root;

    public Root() {
    }

    public int getSize() {
        return root.getSize();
    }

    public void add(T value) {
        if (root == null) {
            root = new Node<T>(value);
        } else {
            root.add(value);
        }
    }

    public void addSort(T value) {
        if (root == null) {
            root = new Node<T>(value);
        } else {
            root.addSort(value);
        }
    }

    public Node getRoot() {
        return root;
    }

    private Node<T> store(Node<T> branch, Node<T> edit) {
        Node<T> node = branch;
        while (!node.isLeaf()) {
            node = node.getNext();
        }
        node.setLeft(branch);
        node.setRight(edit);
        return node;
    }

    private Node<T> fetch(Node<T> node){
        Node<T> tmp = node.getRight();
        node.setLeft(null);
        node.setRight(null);
        return tmp;
    }

    public <TAcc> TAcc inject(TAcc state, Callable<TAcc, T> fun){
        if (root == null) return null;
        Node<T> current = root;
        Node<T> edit = null;
        while (!(edit == null && current.isLeaf())) {
            state = fun.call(state, current.getValue());
            if (current.isNormalBranch()) {
                current = current.getNext();
            } else {
                if (current.isLeaf()) {
                    current = edit.getLeft().getRight();
                    edit = fetch(edit);
                } else {
                    edit = store(current, edit);
                    current = current.getLeft();
                }
            }
        }
        state = fun.call(state, current.getValue());
        return state;
    }

    public static void main(String[] args) {
        Root<Integer> root = new Root<Integer>();
        Random rand = new Random();
        long state = 0;
        int tmp;
        for (int i = 0; i < 10000; i++){
            tmp = rand.nextInt(100000);
            root.add(tmp);
            root.addSort(tmp + 1);
            state += 2*tmp + 1;
        }
        System.out.println(state ==
                root.inject(0, new Callable<Integer, Integer>(){
                    public Integer call(Integer a, Integer b){
                        return a + b;
                    }
                }));
    }
}

Код на Smalltalk, реализован в Pharo, почти стандартный экспорт в файл.

Object subclass: #Node
 instanceVariableNames: 'left rigth value'
 classVariableNames: ''
 poolDictionaries: ''
 category: 'my'!

add: v
 left ifNil: [ ^ left := Node new value: v ].
 rigth ifNil: [ ^ rigth := Node new value: v ].
 ^ (left size) < (rigth size) ifTrue: [ left add: v ] ifFalse: [ rigth add: v ]

addSort: v
 ^ v < value
  ifTrue: [ left isNil ifTrue: [ left := Node new value: v ] ifFalse: [ left addSort: v ] ] 
  ifFalse: [ rigth isNil ifTrue: [ rigth := Node new value: v ] ifFalse: [ rigth addSort: v ] ] .

fetch
 | tmp |
 tmp := rigth.
 left := nil.
 rigth := nil.
 ^ tmp

isBranch
 (left isNil) & (rigth isNil not) ifTrue: [ ^ true ].
 (left isNil not) & (rigth isNil) ifTrue: [ ^ true ].
 ^ false


isLeaf
 ^ left isNil & rigth isNil

left
 ^ left

left: anObject
 left := anObject

next 
 rigth isNil not ifTrue: [ ^ rigth ].
 left isNil not ifTrue: [ ^ left ].
 ^ nil

printOn: aStream
 aStream nextPutAll: 'aNode: '.
 aStream print: value.

rigth
 ^ rigth

rigth: anObject
 rigth := anObject

size
 | lsize rsize |
 lsize := left isNil ifTrue: [ 0 ] ifFalse: [ left size ].
 rsize := rigth isNil ifTrue: [ 0 ] ifFalse: [ rigth size ].
 ^ lsize + rsize + 1

store: branch lastEdit: edit
 ^ self isLeaf 
  ifTrue: [ 
   left := branch.
   rigth := edit.
   self ]
  ifFalse: [ self next store: branch lastEdit: edit ].

value
 ^ value

value: anObject
 value := anObject


Object subclass: #Root
 instanceVariableNames: 'root'
 classVariableNames: ''
 poolDictionaries: ''
 category: 'my'!

add: value
 ^ root isNil ifTrue: [ root := Node new value: value ] ifFalse: [ root add: value ]

addSort: v
 ^ root isNil ifTrue: [ root := Node new value: v ] ifFalse: [ root addSort: v ]

inject: init into: aBlock
 | cur edit state |
 cur := root.
 state := init.
 edit := nil.

 [ edit isNil & cur isLeaf ] whileFalse: [
  state := aBlock value: state value: cur value.
  cur isBranch
   ifTrue: [ cur := cur next ]
   ifFalse: [ cur isLeaf
    ifTrue: [ 
     cur := edit left rigth. 
     edit := edit fetch ]
    ifFalse: [
     edit := cur store: cur lastEdit: edit.
     cur := cur left ] ] ].
 ^ aBlock value: state value: cur value.

root
 ^ root

size
 ^ root size

Тестовый workspace:

root := Root new.
rand := Random new.
state := 0.

1000 timesRepeat: [ | t | 
 t := rand nextInt: 1000000.
 state := state + 1 + (t * 2). 
 root addSort: t.
 root add: (t + 1) ].

(root inject: 0 into: [ :a :b | a + b ]) = state. 

Файлы с исходниками
smalltalk: http://dl.dropbox.com/u/1619524/src/binary_tree.st
java node class: http://dl.dropbox.com/u/1619524/src/Node.java
java root class: http://dl.dropbox.com/u/1619524/src/Root.java

PS Буду рад любым замечаниям.