Процессор J1 — куда уж проще

Осторожно — эта статья не содержит и теоретической, ни практической пользы, и была написана просто, как подведение черты под одним из увлечений.

Я давний фанат этого процессора. Я писал о нем на хабре, дважды, и хочется написать еще.

Для тех, кто не слышал никогда о J1 — это простенький процессор,
ориентированный на язык Форт. Для любителей подробностей — официальный сайт J1 CPU.

Так вот, я с гордостью могу сказать, что я маялся бездельем и тем временем написал эмулятор + компилятор почти-Форта для J1. Здесь я расскажу что это и зачем. Читать далее

Реклама

tip-топ. Или не тип-топ?

Недавно узнал, что у сайта http://golang.org есть особенная версия — http://tip.golang.org

Там находится всякая документация относительно последней версии (tip, по-старинке — head: последний коммит) языка из репозитория.

Вот, например, когда я последний раз его обновлял, я удивился, что там больше нет Makefile (помните — еще недавно мы их учились писать). Теперь все возложили на утилиту go. И сборку, и установку, и тестирование, и форматирование кода. Читать далее

Go 1

Слышали, да? Это стучат клавиатуры и щелкают мыши. Там пишут Go 1.

Это будет первая стабильная база языка Go. API зачерствеет и не будет меняться каждый месяц. Язык станет совсем взрослым и серьезным.

Появятся нумерация версий языка — напр., в Go 1.x будут включаться багфиксы для Go 1.

Итак, что же нового принесет язык? Читать далее

codesearch is dead, long live the codesearch!

Это произошло. codesearch.google.com или google.com/codesearch больше нет.
Я пользовался этим сервисом часто, и теперь я даже не знаю что делать.
Но, спасибо Робу Пайку и Россу Коксу, которые тоже тяжело переживают эту утрату.
Они начали новый проект — codesearch.

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

Для неленивых

Проект написан на Go. Поэтому все кто собирать его вручную — сначала установите Go.

Затем:

cd $GOROOT/src/pkg
# Возможно go install может установить все автоматически прямо с сайта,
# но у меня не получилось.
mkdir -p code.google.com/p/codesearch
hg clone https://code.google.com/p/codesearch code.google.com/p/codesearch
cd code.google.com/p/codesearch/lib
# buildall перебирает все архитектуры и собирает под все что можно, 
# изучите его, закомментируйте то что вам не надо (напр. упаковку результатов
# сборки в *.zip), и тогда запускайте.
./buildall

После этого у вас в $GOBIN появятся три утилиты: cindex, csearch, cgrep.

Для ленивых

Качаем утилиты с сайта проекта и распаковываем куда удобно.

Начало работы

Проиндексируем какую-нибудь папку, напр. наш /usr/include:

$ cindex /usr/include

В результате получим «базу» для поиска в файле ~/.csearchindex

UPD: Описанный ниже баг уже оперативно исправили.
У меня в 64-битной Gentoo произошла ошибка, cindex не смог смержить пустую базу в .csearchindex и временную базу по /usr/include (.csearchindex~ — с тильдой в конце). Проблема была в том, что делали mmap для размера в 0 байт (файл-то пустой), получали ошибку, и завершали программу. Не знаю, это баг Go или codesearch, но уже сообщил о нем. Временный фикс:
$ cp ~/.csearchindex\~ ~/.csearchindex
Так ведь у нас мержат пустой файл с непустым? 🙂
Это надо делать только для 1-го запуска cindex. Дальше все как по маслу.

Войдя в азарт я проиндексировал /usr/src/linux и еще пару мелких проектов.
Размер ~/.csearchindex составил около 50 Мб, что в целом неплохо для всех include и ядра линукса.

Поиск

Для поиска я использовал csearch. В результатах отображается файл и (опционально) номер строки. Конечно, не так красиво как было у codesearch, но пользоваться можно. Глядишь — web-интерфейс сделают когда-нибудь.

$ csearch hcd_bus_
/usr/src/linux/drivers/usb/core/generic.c:		rc = hcd_bus_suspend(udev, msg);
/usr/src/linux/drivers/usb/core/generic.c:		rc = hcd_bus_resume(udev, msg);
/usr/src/linux/drivers/usb/core/hcd.c:int hcd_bus_suspend(struct usb_device *rhdev, pm_message_t msg)
/usr/src/linux/drivers/usb/core/hcd.c:int hcd_bus_resume(struct usb_device *rhdev, pm_message_t msg)
/usr/src/linux/include/linux/usb/hcd.h:extern int hcd_bus_suspend(struct usb_device *rhdev, pm_message_t msg);
/usr/src/linux/include/linux/usb/hcd.h:extern int hcd_bus_resume(struct usb_device *rhdev, pm_message_t msg);

time вернул: csearch hcd_bus_ 0.02s user 0.01s system 74% cpu 0.031 total. Неплохой показатель, и глазом не моргнул. Старикашка grep тут бы трудился около минуты.

# Смотрим где объявлены функции для работы с интерфейсами в libusb (поиск по regex)
$ csearch -n "libusb_.+_interface"
2012/01/19 22:46:58 56591902 56594432
/usr/include/libusb-1.0/libusb.h:803:int libusb_claim_interface(libusb_device_handle *dev, int iface);
/usr/include/libusb-1.0/libusb.h:804:int libusb_release_interface(libusb_device_handle *dev, int iface);
/usr/include/libusb-1.0/libusb.h:809:int libusb_set_interface_alt_setting(libusb_device_handle *dev,

А вот бы еще…

Проект свою функцию выполняет — ищет, и ищет очень быстро. Но аппетит разыгрался. Хочу инверсный поиск (все что не regex), хочу текст до и после совпадающей строки, хочу цепочки фильтров, хочу упрощенный синтаксис наряду с regex, хочу красивый интерфейс (ох как непривычно от самого себя такое слышать). Другие пожелания думаю тоже можно в Issue ребятам писать, так что не скромничайте.

А может взять да и форкнуть? И сделать круто? Робу Пайку думаю не до интерфейсов, а вот самому сделать бы да покрасивше.. Или может взять дерево исходников, скажем, ядра или андроида, да сделать проект на Google App Engine для быстрого поиска по этому дереву прям онлайн, чтобы себе репозитории огромные не качать. Круто, да? Ау, есть желающие? У кого какие еще есть идеи?

Сборка Go-проекта

У новичка могут возникнуть проблемы со сборкой проектов, написанных на Go. Это потому, что вначале во всех учебниках говорят про 8g/8l (6g/6l), а потом вот так сразу переходят к дебрям языка, а про make и правила сборки упускают.

Так вот, не пугайтесь. В Go самые простые Makefile. Давайте разбираться.

Сборка проекта

Для сборки проекта можно использовать такой шаблон Makefile:

include $(GOROOT)/src/Make.inc

TARG=mycmd
GOFILES=mycmd.go

include $(GOROOT)/src/Make.cmd

В любом Makefile для Go вначале включают Make.inc. В этом файле лежат общие правила сборки, а именно:

  • Проверяется окружение ($GOROOT, $GOOS, …)
  • Устанавливаются компиляторы (?g, ?l, ?a)
  • Создается правило, которое показывает ваше окружение: make go-env

После включения Make.inc (который обеспечивает вам кросс-платформенность, потому что внутри сам определяет платформу и устанавливает соответствующие переменные) создаем переменную $TARG. Это — имя вашего бинарника, который должен получиться в результате сборки.

Затем указывает $GOFILES — список файлов, из которых состоит проект. Файлов может быть несколько, напр. GOFILES=main.go util.go conf.go

Последняя строчка — это включение Make.cmd, файла, в котором описаны правила сборки «команды» — обычного приложения. В нем определяются также правила для тестирования проекта с помощью gotest.

Сборка пакета

Если же вы хотите собрать не приложение, а библиотеку (пакет), то замените Make.cmd на Make.pkg.

Все. Теперь можете делать make, make clean и даже make install.

Unlambda — мозги навыворот

Давно тешил себя мыслью, что пойму функциональное программирование. Недавно выпустил эту мысль на волю.
Я несколько раз пытался писать на lisp/scheme и даже немного на clojure. Но это все не серьезно.
И вот я узнал о языке, который мне СОВЕРШЕННО НИКАК в жизни не пригодится и я СОВЕРШЕННО НИЧЕГО на нем не смогу написать.
Это самый бесполезный, непонятный, нечитабельный язык. Даже хуже brainfuck.

Итак, встречайте…

Unlambda

Это почти чистый функциональный язык. Я не владею терминами ФП, поэтому говорить о том, что он использует комбинаторную логику как вид лямбда-исчисления, я не стану. Также этот язык считается полным по Тьюрингу.

Все, с чем работает Unlambda — это функции. Каждая функция имеет ровно один аргумент. Помимо функций у языка есть еще всего один оператор: ` (обратная кавычка). Этот оператор означает «применить» («apply»). Встретив такой символ, интерпретатор должен выполнить идущую за ним функцию.

Имена функций состоят из одной буквы. Именованных функций мало. Мы рассмотрим всего три-четыре (самых основных и необходимых — язык оказывается еще каким-то странным образом развивается).

Самая простая и невписывающаяся в идеологию языка — это функция вывода символа на экран. Функция описывается точкой. Такая функция, когда её выполнят с помощью оператора-кавычки, выведет на экран идущий за ней символ, например .x напишет «x», а .* нарисует звездочку. Почему же не вписывается в идеологию? Да потому что эти самые «иксы» и «звездочки» — это не аргументы функции. Это просто хак, для того чтобы сделать для чисто функционального языка в вакууме, который что-то вычисляет, функцию вывода.

Итак, есть еще функция i. Она принимает один аргумент, и возвращает его же. Т.е. `ix в результате выполнения вернет x.
Не понимаете зачем это может понадобится? Хе-хе!

А вот еще функция k. Она принимает уже два аргумента и… Как это может быть? Да, я говорил что функции принимают по одному аргументу. В Unlambda применяют подход «карринга». Т.е. если функция K принимает в действительности один аргумент, затем возвращает функцию, которая запоминает этот аргумент, и принимает еще один. Так вот получается, что в итоге K принимает как бы два аргумента. Вызывать такую конструкцию (функций-то уже как бы две) надо так: ``kxy, т.е. вызвать k(x), и ту функцию которую он вернет (скажем kx) вызвать как kx(y). Так вот, функция ``kxy принимает два аргумента и возвращает первый (x). Тоже странно?

Ну и напоследок, функция s. У неё уже три аргумента. В итоге, функция ```sxyz применяет функцию x к z, затем y к z, и потом применяет полученные в итоге функции друг к другу. Т.е. эквивалент ```sxyz — это ``xz`xz:

# В только что придуманном мною псевдокоде функция S выглядит так
s(x,y,z):
  a = x(z);
  b = y(z);
  return a(b);

Все. Тоже непонятно? Давайте начнем с вывода звездочки на экран. А потом возьмем, да и напишем свой интерпретатор языка Unlambda.

Для вывода звездочки нужна примерно такая программа: `.*i. Буквально: выполни функцию печати звездочки с аргументом — функцией i. Функция i, конечно, не будет выполнятся (у нас же только одна кавычка, а значит и одно выполнение). Роль функции i — просто выступать в качестве необходимого аргумента для функции вывода. Заметим, что аргументы функции проверяются только во время её вызова (через кавычку). До тех пор — можно писать что угодно.

Интерпретатор

Реализация языка на самом деле простая. Но если вам не знаком язык Go, или вы не любите писать свои интерпретаторы, то можете пропустить эту главу.
Итак, есть функции, есть оператор. Давайте обобщим эти два понятия и назовем это «выражением». Т.е. выражение — это либо оператор «применить», либо функция. Для выражения «применить» надо помнить выражение, которое применяем и его аргумент (тоже выражение). Для выражения-функции надо помнить только функцию. Получаем структуру:

type Expression struct {
	f   *Expression
	x   *Expression
	fn  *Function
	exp int // тип выражения - APPLY или FUNC
}
// Создаем новое выражение "apply"
func NewApplyExp(f *Expression, x *Expression) (e *Expression) {
	e = new(Expression)
	e.f = f
	e.x = x
	e.exp = EXPRESSION_APPLY
	return
}
// Создаем новое выражение-функцию
func NewFuncExp(f *Function) (e *Expression) {
	e = new(Expression)
	e.fn = f
	e.exp = EXPRESSION_FUNC
	return
}
// Выполняем выражение. "Apply" вернет нам результат, а выражение-функция вернет саму функцию.
func (e *Expression) Eval() (f *Function) {
	switch e.exp {
	case EXPRESSION_FUNC:
		return e.fn
	case EXPRESSION_APPLY:
		return e.f.Eval().ApplyTo(e.x.Eval())
	}
	panic("Bad expression")
}

Например, конструкция `.xi будет представлена выражениями:

f1 = FUNC(.x)
f2 = FUNC(i)
e1 = APPLY(f1, f2)

Сами же функции выглядят тоже достаточно просто:

type Function struct {
	x    *Function // аргумент 1
	y    *Function // аргумент 2
	rune int       // символ который надо вывести. Только для функции-точки
	fn   int       // код функции: I/S/K/DOT
}

// Creates a new function with the given operator code
func NewFunc(code int) (f *Function) {
	f = new(Function)
	f.fn = code
	return
}

// Creates a new dot-function, that will print a given rune
func NewDotFunc(rune int) (f *Function) {
	f = new(Function)
	f.fn = FUNCTION_DOT
	f.rune = rune
	return
}

func (f *Function) ApplyTo(x *Function) (res *Function) {
        // Тут выполняется функция f с аргументом x
}

Чтобы реализовать карринг, добавим несколько вспомогательных функций. Так, функция K возвращает функцию K1, которая делает всю работу, а функция S возвращает S1, которая потом возвращает S2. Вот как это отразится на ApplyTo:

func (f *Function) ApplyTo(x *Function) (res *Function) {
	switch f.fn {

	// I-function just returns its operand
	case FUNCTION_I:
		return x

	// K-function returns its first operant, but takes two of them
	case FUNCTION_K:
		res = new(Function)
		res.x = x
		res.fn = FUNCTION_K1
		return res
	case FUNCTION_K1:
		return f.x

	// S-function takes 3 operands and applies 1st to the 3rd, and 2nd to the 3rd
	case FUNCTION_S:
		res = new(Function)
		res.x = x
		res.fn = FUNCTION_S1
		return res
	case FUNCTION_S1:
		res = new(Function)
		res.x = f.x
		res.y = x
		res.fn = FUNCTION_S2
		return res
	case FUNCTION_S2:
		return f.x.ApplyTo(x).ApplyTo(f.y.ApplyTo(x))

	// Dot-function prints a single rune
	case FUNCTION_DOT:
		print(string(f.rune))
		return x
	}
	panic("Bad function code")
}

Весь код интерпретатора (в нем не хватает еще парсера) можно найти здесь. Собираем, запускаем.

Изучаем подробнее

Теперь у нас есть на чем тестировать выражения. Пишем hello world:

`````.h.e.l.l.oi

Меня хватило только на hello. У функции .h аргументом является .e.l.l.oi. Выполнив эту функцию, на экране появляется буква h, и следом выполняется функция-хвостик. Она пишет «e», и возвращает .l.l.oi. Так длится до функции .oi, которая пишет «о», и возвращает i. Больше нет операторов выполнения (их было всего пять), программа останавливается.

Несмотря на примитивность, Unlambda — язык избыточный. В нем больше 20% функций — не нужны. А именно, функция «i». Потому что iX это то же самое, что и skkX: ```skkX = ``kX`kX = `kxkx = x

Я пока остановлюсь. Хотел рассказать, как работает программа, рисующая числа фиббоначи, но… Вообщем вот она:

```s``s``sii`ki
  `k.*``s``s`ks
 ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
  `k``s`ksk

На нашем интерпретаторе она работает, и рисует строчки из звездочек (кол-во звездочек = число). Как это происходит — я уже не понимаю.

Напоследок скажу, что с помощью S/K функций можно описывать числа как глубину рекурсии(Church Integers), булевы значения (аналогично) и делать конструкции типа if-then-else. Может быть когда нибудь я вам об этом тоже расскажу. Жаль, что я к тому времени уже утрачу рассудок, буду общаться с духами и возможно покину этот слишком материальный мир.