Ще один Brainfuck інтерпретатор

Brainfuck — мова програмування, створена з однією метою: написати для нього інтерпретатор. Їх було написано так багато, що навіть не буду давати на них посилання. У цій статті на пальцях пояснюється простий, але ефективний спосіб його оптимізації.
quine

Читати далі →

Власна платформа. Частина 0.2 Теорія. Інтерпретатор CHIP8

Введення
Здрастуй, світ! Сьогодні у нас переклад специфікації мови CHIP8. Це стаття містить тільки теоретичну частину.
*COSMAC ELF у всій красі*COSMAC ELF
Що таке CHIP8?
CHIP8 це інтерпретується в microsoft мова програмування, який був розроблений Джозефом Вейзбекером (прим. переклад Joseph Weisbecker) в сімдесятих для використання в RCA COSMAC VIP. В подальшому був використаний COSMAC ELF, Telmac 1800, ETI 660, DREAM 6800. Тридцять одна (35?) інструкція давали можливості для виведення простого звуку, монохромного графіки в дозволі на 64 32 пікселя, а також дозволяло використовувати 16 кнопок. Сьогодні CHIP-8 часто використовується для навчання базовим навиком емуляції (не інтерпретації). Інтерпретатори CHIP-8 часто помилково називають емуляторами. Це пов'язано з фактом великої схожості CHIP-8 з комп'ютером.

Читати далі →

Генерація коду під час виконання чи «Пишемо свій JIT-компілятор»


Сучасні компілятори дуже добре вміють оптимізувати код. Вони видаляють ніколи не виконуються умовні переходи, обчислюють константные вирази, відмовляючись від безглуздих арифметичних дій (множення на 1, складання з 0). Вони оперують даними, відомими на момент компіляції.
У момент виконання інформації про оброблюваних даних набагато більше. На її підставі можна виконати додаткові оптимізації і прискорити роботу програми.
Оптимізований для приватного випадку алгоритм завжди працює швидше універсального (принаймні, не повільніше).
Якщо для кожного набору вхідних даних генерувати оптимальний для обробки цих даних алгоритм?
Очевидно, частина часу виконання піде на оптимізацію, але якщо оптимізований код виконується часто, витрати окупляться з лишком.
Як технічно це зробити? Досить просто — у програму включається міні-компілятор, що генерує необхідний код. Ідея не нова, технологія називається «компіляція часу виконання» або JIT-компіляція. Ключову роль JIT-компіляції грає у віртуальних машинах і інтерпретаторів мов програмування. Часто використовувані ділянки коду (або байт-коду) перетворюються в машинні команди, що дозволяє значно підвищити продуктивність.
Java, Python, C#, JavaScript, Flash ActionScript — неповний (зовсім неповний) список мов, у яких це використовується. Я пропоную вирішити конкретну задачу з використанням цієї технології і подивитися, що вийде.

Читати далі →

Анонс нових можливостей Typescript 1.4

Випустивши версію Typescript 1.3, ми сфокусувалися на удосконаленні системи типів і додавання функціоналу ECMAScript 6 в TypeScript. Давайте розглянемо деякі нові можливості, якими ви зможете користуватися в новій версії.

Всі описані в статті речі вже реалізовані у майстер-гілці нашого репозиторію на Github — ви можете викачати її і спробувати їх вже зараз.



Нові можливості дозволяють більш акуратно і легко працювати зі змінними, які мають різний тип під час виконання. Вони скорочують кількість місць, де потрібно явно вказувати тип, перевіряти його або використовувати тип
any
. Автори типізованих файлів (
.d.ts
) можуть також використовувати ці можливості для опису зовнішніх бібліотек. Ті, хто стежать за розвитком компілятора, могли помітити, що ми самі теж ними користуємося.
Читати далі →

Виразний JavaScript: Проект: мова програмування

Зміст



То, що перевіряє і визначає сенс виразів мовою програмування, що є в свою чергу просто програмою.

Хел Абельсон і Жеральд Сасман, «Структура та інтерпретація комп'ютерних програм».

Коли вчення запитав учителя про природу циклу Даних і Контролю, Юань-Ма відповів: «Подумай про компіляторі, компилирующем самого себе».

Майстер Юань-Ма, «Книга програмування»


Створити свій мова програмування дивно легко (поки ви не ставите позамежних цілей) і досить повчально.

Головне, що я хочу продемонструвати в цій главі — у побудові мови немає ніякої магії. Мені часто здавалося, що деякі людські винаходи настільки складні і заумны, що мені їх ніколи не зрозуміти. Однак після невеликого самоосвіти і колупання такі штуки часто виявляються досить буденними.

Ми побудуємо мова програмування Egg (Яйце). Він буде невеликим, простим, але досить потужним для вираження будь-яких розрахунків. Він також буде здійснювати прості абстракції, засновані на функціях.

Читати далі →

Пишемо простий інтерпретатор на C + + за допомогою TDD, частина 3

    У першої частини був написаний Лексер , а під другій частині — парсер . Далі буде розглянута розробка обчислювача і фасаду для всього інтерпретатора, а також рефакторінг коду для усунення дублювання.
 
 

Обчислювач

Приступимо до найцікавішого. Обчислення виразу в постфіксной записи можна здійснити двома способами: через рекурсію, неявно використовуючи стек процесу, або використовуючи явний стек. Реалізуємо другий варіант. Алгоритм з використанням явного стека такий:
 
 
     
  • Якщо на вхід поданий операнд, він поміщається на вершину стека.
  •  
  • Якщо на вхід поданий знак операції, то відповідна операція виконується над необхідною кількістю значень, витягнутих з стека, взятих в порядку додавання. Результат виконаної операції кладеться на вершину стека.
  •  
  • Після повної обробки вхідного набору символів результат обчислення виразу лежить на вершині стека.
  •  
У даній статті я не буду реалізовувати контекст виконання і обчислення кількох виразів. Тому початковий список тестів буде коротким:
 
 
     
  • Якщо на вході порожній список, повертаємо 0.
  •  
  • Якщо на вході список з одним числом, повертаємо це число.
  •  
  • Якщо на вході? [1 2 +], повертаємо 3.
  •  
Створимо новий тестовий клас і додамо перший тест.
 
 
TEST_CLASS(EvaluatorTests) {
public:
    TEST_METHOD(Should_return_zero_when_evaluate_empty_list) {
        double result = Evaluator::Evaluate({});
        Assert::AreEqual(0.0, result);
    }
};

 
Читати далі →

Пишемо простий інтерпретатор на C + + за допомогою TDD, частина 2

    У першої частини був написаний Лексер . Далі буде розглянута розробка парсера.
 
 

Парсер

Парсер буде реалізований за алгоритмом сортувальної станції, так як він досить простий і не потребує рекурсії. Сам алгоритм такий:
 
На початку даються порожній вихідний потік і порожній стек. Почнемо читати токени з вхідного потоку по черзі.
 
 
     
  • Якщо це число, то передати його у вихідний потік.
  •  
  • Якщо це ліво асоціативний оператор, то виштовхуємо токени з стека у вихідний потік до тих пір, поки він не спорожніє, або не його вершині не стрінеться дужка, або оператор з більш низьким пріоритетом.
  •  
  • Якщо це відкриває дужка, то покласти її в стек.
  •  
  • Якщо це закриває дужка, то виштовхуємо токени з стека у вихідний потік до виявлення відкриває дужки. Виштовхнути відкриває дужку з стека, але не передавати її у вихідний потік. Якщо стек спорожнів, і дужка не знайдено, то генеруємо помилку.
  •  
Після досягнення кінця вхідного потоку, виштовхнути все залишилися в стеку оператори у вихідний потік. Якщо в ньому знайдено небудь окрім операторів, то генеруємо помилку.
 
Прикинемо, які тести можуть знадобитися для початку.
 
 
     
  • При отриманні порожнього списку, повертається порожній список.
  •  
  • При отриманні списку з одним числом, повертається список з цим числом.
  •  
  • При отриманні [1 + 2], повертається [1 2 +].
  •  
  • При отриманні [1 + 2 + 3], повертається [1 2 + 3 +], так як оператор + є ліво асоціативним.
  •  
  • При отриманні [1 * 2 + 3], повертається [1 2 * 3 +].
  •  
  • При отриманні [1 + 2 * 3], повертається [1 2 3 * +], так як оператор * має більший пріоритет.
  •  
З дужками і помилками розберемося пізніше. Отже, напишемо перший тест зі списку.
 
 
TEST_CLASS(ParserTests) {
public:
    TEST_METHOD(Should_return_empty_list_when_put_empty_list) {
        Tokens tokens = Parser::Parse({});
        Assert::IsTrue(tokens.empty());
    }
};

 
Читати далі →

Пишемо простий інтерпретатор на C + + за допомогою TDD, частина 1

    

Введення

 
Багато C + + програмісти чули про розробку через тестування. Але майже всі матеріали з даної теми стосуються більш високорівневих мов і зосереджені більше на загальній теорії, ніж на практиці. Отже, в даній статті я спробую навести приклад покрокової розробки через тестування невеликого проекту на C + +. А саме, як можна припустити з назви, простого інтерпретатора математичних виразів. Такий проект також є непоганий code kata, так як на його виконання витрачається не більше години (якщо не писати паралельно статтю про це).
 
 

Архітектура

Незважаючи на те, що при використанні TDD архітектура додатку поступово проявляється сама собою, початкова її опрацювання все ж необхідна. Завдяки цьому може значно знизитися загальний час, витрачений на реалізацію. Це особливо ефективно в тих випадках, коли існують готові приклади подібних систем, які можна взяти за зразок. В даному випадку, існує цілком усталена думка про те, як повинні бути влаштовані компілятори та інтерпретатори , чим і можна скористатися.
 
Для початку, складемо список того, що повинен вміти наш простий інтерпретатор, в порядку зменшення пріоритету:
 
 
     
  • Обчислювати значення математичного виразу, що складається з чисел з плаваючою точкою і математичних операторів (- + / *).
  •  
  • Облік пріоритету операторів.
  •  
  • Облік дужок.
  •  
  • Унарні плюс і мінус.
  •  
  • Обчислення кількох виразів, розділених крапкою з комою (;).
  •  
  • Вбудовані константи (pi, e).
  •  
  • Створення власних констант за допомогою оператора присвоєння (=).
  •  
  • Вбудовані функції зі змінним числом аргументів.
  •  
  • Завдання нових функцій.
  •  
У даній статті буде реалізація тільки перших трьох пунктів. Сам проект концептуально складатиметься з чотирьох частин:
 
 
     
  • Лексичний аналізатор. Перетворює вхідну рядок в послідовність токенов.
  •  
  • Синтаксичний аналізатор. Будує з токенов синтаксичне представлення у вигляді постфіксной нотації . Робити це будемо без рекурсії і таблиць, за допомогою алгоритму сортувальної станції .
  •  
  • Обчислювач. Обчислює результат виразу на стековой машині.
  •  
  • Власне, інтерпретатор. Служить фасадом для перерахованих вище частин.
  •  
 

Інструментарій

Програма буде писатися в Visual Studio 2013 з встановленим Visual C + + Compiler Nov 2013 CTP . Тести будуть на основі вбудованого в студію тестового фреймворка для C + + проектів CppUnitTestFramework . Він надає мінімальну підтримку для написання модульних тестів (порівняно з Boost.Test, або CppUTest), але, з іншого боку, добре інтегрований в середу розробки.
 
Отже, створимо новий проект типу «Native Unit Test Project» і переконався, що всі компілюється.
 
Читати далі →

автовходу з паролем і керування по ssh «в гостях» за допомогою expect

    В черговий раз використовуючи цей скрипт в одному з навчальних класів, я пошукав матеріали і виявив, що тут давно не згадували про expect. Це чудовий альтернативний інтерпретатор для командного рядка Linux, який може спілкуватися з нею замість живої людини, і я додам сюди лише ще один приклад його застосування.
 
 
 
Картинок на цю тему особливо немає, а в статті і взагалі не буде, тому залучимо вашу увагу обкладинкою чудової книги
 
 
Читати далі →