Pull to refresh

Конспект монографии по λ-исчислению

Abnormal programming *Lisp *
Данный текст представляет собой чрезвычайно сжатый конспект классической монографии по λ-исчислению (Х. Барендрегт, «Ламбда-исчисление. Его синтаксис и семантика», перевод с английского Г. Е. Минца под редакцией А. С. Кузичева, Москва, «Мир», 1985). Он может оказаться интересен всем тем, кто планировал взяться за систематическое изучение данной темы, уже в общих чертах ознакомившись с ней, но откладывал из-за сложной структуры основной монографии, определения и основные результаты в которой довольно разрозненны. Здесь мы попытаемся сделать изложение, напротив, абсолютно линейным, и, конечно, несравнимо более коротким, избегая лишних определений и примеров, а сосредоточившись на необходимых терминологии, обозначениях и утверждениях, которые, в свою очередь, изложены близко к оригинальному тексту. Мы начнем от определения системы λβη, то есть классического бестипового экстенсионального λ-исчисления. Затем перейдем к комбинаторной логике, теореме о неподвижной точке и синтаксическому сахару. Наконец, заключительная часть конспекта — построение топологии на выражениях этой системы, призванной объяснить кажущееся противоречие: отображения множества выражений в себя содержатся в самом этом множестве при его счетности. На самом же деле, множество наделяется надлежащей топологией, в которой выражения представляют собой непрерывные отображения.
Читать дальше →
Total votes 86: ↑62 and ↓24 +38
Views 4.6K
Comments 19

Когда гаснет звезда: интервью с Джимом Вейрихом

Ruby *Programming *
Translation
От переводчика: Джим Вейрих — легендарная личность в Ruby-сообществе. К сожалению, он, как и все мы, смертен. Не так давно он покинул нас. Этот перевод — дань уважения к этому человеку, который немного изменил мир.

Я наслышан о Джиме достаточно давно: ведь он — автор утилиты rake, ставшей фактически стандартом де-факто среди рубистов. К моей большой удаче, я был в числе слушателей его выступления на GoRuCo 2012, на котором было рассказано о продвинутых возможностях rake. Помню, как меня поразила та ловкость и легкость, с которой Джим говорил на сложные темы. Позже, в том же году на конференции RubyConf я наблюдал еще одно его замечательное выступление, в котором объяснялись некоторые базовые принципы Лямбда-исчисления. Джим не только доступно объяснил эту не самую простую тему, но также не потерял своих слушателей по дороге.

Думаю, теперь вы понимаете, почему я был так рад взять у Джима это интервью, ведь это уникальная возможность узнать о нем чуточку больше и чему-то научиться. Нам также удалось побеседовать о начале его пути в мире разработке, о его первых шагах в Руби, о функциональном программировании, модели потоков в Руби и даже о его фреймворке для тестов: RSpec-Given). Так что открывайте это интервью, не поленитесь узнать об одном из самых передовых и харизматичных разработчиков!


Читать дальше →
Total votes 60: ↑59 and ↓1 +58
Views 13K
Comments 6

λ-исчисление. Часть первая: история и теория

Programming *
Tutorial
Идею, короткий план и ссылки на основные источники для этой статьи мне подал хабраюзер z6Dabrata, за что ему огромнейшее спасибо.

UPD: в текст внесены некоторые изменения с целью сделать его более понятным. Смысловая составляющая осталась прежней.

Вступление


Возможно, у этой системы найдутся приложения не только
в роли логического исчисления. (Алонзо Чёрч, 1932)


Вообще говоря, лямбда-исчисление не относится к предметам, которые «должен знать каждый уважающий себя программист». Это такая теоретическая штука, изучение которой необходимо, когда вы собираетесь заняться исследованием систем типов или хотите создать свой функциональный язык программирования. Тем не менее, если у вас есть желание разобраться в том, что лежит в основе Haskell, ML и им подобных, «сдвинуть точку сборки» на написание кода или просто расширить свой кругозор, то прошу под кат.
Читать дальше →
Total votes 64: ↑54 and ↓10 +44
Views 137K
Comments 33

λ-исчисление. Часть вторая: практика

Programming *
Tutorial
Идею, короткий план и ссылки на основные источники для этой статьи мне подал хабраюзер z6Dabrata, за что ему огромнейшее спасибо.

Первая часть дала нам теоретическое представление о том, что есть лямбда-исчисление. В этой статье мы последуем неофициальной його-заповеди «Practice-practice-practice» и увидим его в действии.
Читать дальше →
Total votes 29: ↑28 and ↓1 +27
Views 43K
Comments 1

Интерпретация во время компиляции, или Альтернативное понимание лямбд в C++11

Abnormal programming *Programming *C++ *
Yo dawg, I heard you like programming. So we put a language in you language, so you can program while you programНа Хабре недавно проскочила ещё одна статья про вычисления на шаблонах C++ от HurrTheDurr. В комментариях к ней лично я увидел вызов:

> С каждым новым релизом количество способов нетривиально вывихнуть себе мозг при помощи С++ продолжает увеличиваться)
> > Особенно, если не менять подход к реализации игрового поля и продолжать пытаться все вычисления выполнять не над константами, а над типами.


А так ли сложно будет написать универсальный вычислитель на типах, более удобный для программирования, чем клеточный автомат? Как оказалось, несложно; я в 30 раз больше времени потратил на эту статью, чем на написание и отладку собственно кода вычислителя.

Чуть раньше AveNat опубликовала введение в лямбда-исчисление в двух частях, так что вдохновение пришло мгновенно. Хотелось, чтобы можно было (образно) писать так:
#include <iostream>

#include <LC/kernel.h>
#include <LC/church_numerals.h>

int main()
{
    // Представление натуральных чисел в виде лямбда-абстракций
    typedef ChurchEncode<2> Two;    // 2 = λfx.f (f x)
    typedef ChurchEncode<3> Three;  // 3 = λfx.f (f (f x))

    // * = λab.λf.a (b f)
    typedef Lambda<'a', Lambda<'b', Lambda<'f',
                Apply<Var<'a'>, Apply<Var<'b'>, Var<'f'> > >
        > > > Multiply;

    // Вычисление (* 2 3)
    typedef Eval<Apply<Apply<Multiply, Two>, Three>> Output;

    // Переход обратно от лямбда-абстракций к натуральным числам
    typedef ChurchDecode<Output> Result;

    std::cout << Result::value;
}

А на выходе получать такое:
ilammy@ferocity ~ $ gcc cpp.cpp
ilammy@ferocity ~ $ ./a.out
6

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

Под катом находится очередное прокомментированное конструктивное доказательство Тьюринг-полноты шаблонов C++ в виде compile-time интерпретатора бестипового лямбда-исчисления (плюс печеньки в виде макросов и рекурсии).
Читать дальше →
Total votes 102: ↑98 and ↓4 +94
Views 31K
Comments 13

Лямбда-выражения в Java 8

Website development *Programming *Java *
В новой версии Java 8 наконец-то появились долгожданные лямбда-выражения. Возможно, это самая важная новая возможность последней версии; они позволяют писать быстрее и делают код более ясным, а также открывают дверь в мир функционального программирования. В этой статье я расскажу, как это работает.

Java задумывалась как объектно-ориентированный язык в 90-е годы, когда объектно-ориентированное программирование было главной парадигмой в разработке приложений. Задолго до этого было объектно-ориентированное программирование, были функциональные языки программирования, такие, как Lisp и Scheme, но их преимущества не были оценены за пределами академической среды. В последнее время функциональное программирование сильно выросло в значимости, потому что оно хорошо подходит для параллельного программирования и программирования, основанного на событиях («reactive»). Это не значит, что объектная ориентированность – плохо. Наоборот, вместо этого, выигрышная стратегия – смешивать объектно-ориентированное программирование и функциональное. Это имеет смысл, даже если вам не нужна параллельность. Например, библиотеки коллекций могут получить мощное API, если язык имеет удобный синтаксис для функциональных выражений.

Главным улучшением в Java 8 является добавление поддержки функциональных программных конструкций к его объектно-ориентированной основе.
Читать дальше →
Total votes 60: ↑51 and ↓9 +42
Views 438K
Comments 24

А-машина Тьюринга и кофе-машина Хоара пит-стоп

Programming *Algorithms *
Всякий, кто полагается на практику, не зная теории, подобен кормчему, вступающему на судно без руля и компаса, – он не знает, куда плывет.
Леонардо да Винчи
В Священных Языковых Войнах в качестве окончательного аргумента нередко приводят — поскольку языки полны по Тьюрингу, постольку они и равноценны. Под катом попытка уточнить этот тезис для тех, кто уже справился с Python и теперь планирует изучить Erlang или Haskell по спецификации. Материал обзорный, не методичный с картинками.
Читать дальше →
Total votes 25: ↑22 and ↓3 +19
Views 15K
Comments 6

Лямбда-исчисление на JavaScript

Abnormal programming *JavaScript *Functional Programming *
Привет! В этой статье я хочу в очередной раз взглянуть на лямбда-исчисление. Теоретическую сторону вопроса на хабре обсуждали уже множество раз, поэтому взглянем на то, как лямбда-исчисление может выглядеть на практике, например, на языке JavaScript (чтобы примеры можно было выполнять прямо в браузере).

Итак, основная идея: всё есть функция. Поэтому мы ограничим себя очень узким кругом возможностей языка: любое выражение будет либо анонимной функцией с одним аргументом (x => expr), либо вызовом функции (f (x)). То есть весь код будет выглядеть похожим образом:

id = x => x
double = f => x => f (f (x))

Поскольку результатом работы функций будут другие функции, нам понадобится способ интерпретировать результат. Это единственное место, в котором пригодятся нетривиальные возможности JavaScript.
Читать дальше →
Total votes 38: ↑31 and ↓7 +24
Views 48K
Comments 53

Книга Алана Тьюринга и загадочная записка — Научный детектив

Wolfram Research corporate blog Mathematics *Functional Programming *Reading room History of IT
Translation

Оригинал перевода в моём блоге

Как ко мне попала эта книга?


В мае 2017 года я получил электронное письмо от моего старого учителя средней школы по имени Джордж Раттер, в котором он писал: «У меня есть копия большой книги Дирака на немецком языке (Die Prinzipien der Quantenmechanik), которая принадлежала Алану Тьюрингу, и после того как я прочел вашу книгу Создатели идей (Idea Makers), мне показалось само собой разумеющимся, что вы именно тот человек, которому она нужна». Он объяснил мне, что получил книгу от другого (к тому времени умершего) моего школьного учителя Нормана Рутледжа, о котором я знал, что он был другом Алана Тьюринга. Джордж закончил свое письмо фразой: «Если вам нужна эта книга, я мог бы вручить ее вам в следующий раз, когда вы приедете в Англию».

Спустя пару лет в марте 2019 года я действительно прибыл в Англию, после чего договорился с Джорджем о встрече за завтраком в небольшом отеле в Оксфорде. Мы ели, болтали и ждали, пока еда уляжется. Затем настал подходящий момент для обсуждения книги. Джордж сунул руку в портфель и вытащил довольно скромно оформленный, типичный академический томик середины 1900-х годов.



Я открыл обложку, размышляя, не может ли на ней быть с обратной стороны надписи: «Собственность Алана Тьюринга» или чего-то в этом духе. Но, к сожалению, это оказалось не так. Тем не менее к ней была приложена достаточно выразительная записка на четырех листах от Нормана Рутледжа к Джорджу Раттеру, написанная в 2002 году.

Я знал Нормана Рутледжа, когда еще был учеником средней школы в Итоне в начале 1970-х годов. Он был учителем математики по прозвищу «Чокнутый Норман». Он был приятным во всех отношениях преподавателем и рассказывал бесконечные байки о математике и о всяких других занимательных вещах. Он был ответственным за то, чтобы школа получила компьютер (программируемый с помощью перфоленты шириной с парту) — это был самый первый компьютер, который я когда-либо использовал.
Читать дальше →
Total votes 32: ↑31 and ↓1 +30
Views 9.6K
Comments 4

Функциональное программирование на Python для самых маленьких — Часть 1 — Lambda Функция

Python *Functional Programming *
Sandbox
Tutorial
image

Я решил написать эту серию статей, ибо считаю, что никто не должен сталкиваться с той стеной непонимания, с которой столкнулся когда-то я.

Ведь большинство статей написаны таки образом что, для того чтобы понять что-то в Функциональном Программировании (далее ФП), тебе надо уже знать многое в ФП. Эту статью я старался написать максимально просто — настолько понятно, чтобы её суть мог уловить мой племянник, школьник, который сейчас делает свои первые шаги в Python.
Читать дальше →
Total votes 11: ↑7 and ↓4 +3
Views 47K
Comments 25

Архитектура Вселенной, часть 3: Идея

Popular science

Перед прочтением рекомендуется ознакомиться с предыдущими статьями цикла "Архитектура Вселенной":

Часть 1: Сознание
Часть 2: Относительность
Часть 3: Идея

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

Слово "материя" имеет тот же корень, что и слово "материал". В русский язык эти слова попали из латыни, где слово "materia" - это существительное, а слово "materialis" - прилагательное. Приблизительно эти слова можно перевести как "вещество" и "вещественный". Однако, если мы попытаемся дать понятию "материя" четкое определение, то натолкнемся на те же самые проблемы, что с сознанием, временем и пространством. Мы можем сказать, что материя - это то вещество, тот материал, из которого состоят все вещи. Но это определение можно выставлять в парижской палате мер и весов, как эталон тавтологии, ведь материя и есть вещество. Так что давайте обойдемся простым "материя - это то, из чего все состоит".

Читать далее
Total votes 23: ↑22 and ↓1 +21
Views 14K
Comments 72

Лямбда-исчисление в 397 байтах

Programming *Mathematics *
Translation

Лямбда-исчисление — это язык программирования с единственным ключевым словом. Это асфальтовая топь Тьюринга, обнаруженная научным руководителем Тьюринга. В этом посте я расскажу о совершенно новой 397-байтной реализации двоичного лямбда-исчисления в виде Linux ELF для x86-64. Также в нём представлены удобно портируемый код на C и собранные двоичные файлы APE для других платформ.
Читать дальше →
Total votes 70: ↑69 and ↓1 +68
Views 13K
Comments 13