Войти
L languageСтатьи

История разработки L. Часть 1, "Спецификация"

Автор:

Весь язык, по сути, разделен на две части - Top Level, в которой даются определения и указания компилятору, и Value Level, которая описывает правила задания констант.


Язык описания Top Level


Axiom ИмяАксиомы : Тип - "договаривается" с компилятором, что в рантайме будет присутстовать объект типа Тип с именем ИмяАксиомы.
Section ИмяСекции / End - задает неймспейс, снаружи него можно обращаться к элементам через "ИмяСекции."
Import Путь.До.Модуля - подключает модуль в компиляцию (что в моей версии реализовано не было)
Open ИмяНеймспейса - аналог using namespace ИмяНеймспейса из С++
Define - последняя и самая синтаксически сложная конструкция. Задает аналог "класса" в понятии ООП.

Define Имя [parametrized by a b c] having [cases ...конструкторы...] [variables ...мутабельные поля...] [constants ...иммутабельные поля...]
По порядку:
parametrized by позволяет создать generic-определение, в котором можно подставлять a, b, c везде, где ожидается имя типа.

cases - перечисление конструкторов, которыми можно создать экземпляр "класса". Например, если для типа MyType задать конструкторы Left(String) Right(Int), то в С++ коде это выглядело бы примерно так:

MyType MyType::Left(String param0){
  MyType object;
  object.tag = "Left";
  object.param0 = (void*)param0;
  return object;
}

MyType MyType::Right(Int param0){
  MyType object;
  object.tag = "Right";
  object.param0 = (void*)param0;
  return object;
}

То есть у нас всегда есть возможность узнать, каким конструктором и с какими параметрами был создан данный объект.
variables - просто список "переменная:Тип", каждый объект будет владеть своим экземпляром каждой переменной (для создания компилятора не понадобилось, поэтому реализовано не было)
constants - список "константа = выражение", где "выражение" задано в Value Level, вычисляется на этапе запуска программы и не изменяется все время ее работы.


Язык описания Value Level

Синтаксис весьма похож на ML, за исключением формы записи вызова функций (f(x,y) вместо f x y)

Все нижеперечисленное является выражением.

  • имя константы, имя переменной.
  • специальное значение undefined, которое немедленно бросает исключение, если было вычислено
  • вызов функции (было принято очень плохое решение, что в синтаксисе он выглядит в императивном стиле, т.е. со скобочками)
  • функция, записанная как "fun аргументы => выражение"
  • let-выражение
  • let
      константа1 = выражение1
      константа2 = выражение2
      ...
    in 
      выражение

    Сначала вычисляется выражение1, в области видимости появляется константа1 с его значением. Процедура повторяется для всех выражений. В конце вычисляется выражение после in и его результат становится результатом всего let-in. Есть одна тонкость - если выражение1 является функцией, то внутри нее можно рекурсивно ссылаться на константу1.

  • вызов конструктора (ничем не отличается от вызова любой другой функции, например, MyType можно создать так: Left("Hello") или так Right(42) 
  • pattern-matching в виде
  •   match выражение with
        конструктор1 => выражение1
        конструктор2 => выражение2
        ...
      end

    Для незнакомых с тем, что это: допустим, выражение возвращает некий объект. Он был создан с помощью какого-то конструктора. При помощи match можно узнать, какой конструктор использовался для его создания и с какими аргументами. Самый близкий императивный аналог - switch по тегу (возвращаясь к примеру с MyType):
    Предположим, что f возвращает MyType.

    match f() with
      Left(str) => print(str)
      Right(value) => sum += value
    end
    эквивалентно:
    MyType object = f()
    switch ( f.tag ){
    case "Left":
      String str = (String)f.param0;
      print(str);
    break;
    case "Right":
      Int value = (Int)f.param0;
      sum += value;
    break;
    }

    Для удобства было добавлено немножко сахара:
    Строковые и числовые литералы
    [a0, a1, a2 ... an] - литерал для списка
    value1 `function` value2 - инфиксная форма записи для function(value1, value2), в отсутствие операторов можно писать хотя бы 19 `plus` 21 вместо plus(19, 21)

    И в конце немножко размышлений на тему мощности представленного языка.
    В начале разбора исходника наше пространство имен абсолютно чисто и невинно. #include <stdio.h> сделать тоже проблематично, ввиду отсутствия последнего. Но даже в таких условиях можно сделать кое-что полезное.
    Напишем немножко математики, не прибегая к аксиомам. Число определим через "ноль" и "следующее число":

    Define Number having 
      cases 
        Zero //число - либо ноль
        Succ(Number) //либо следующее за указанным
      constants 
      //Определим операцию сложения:
        add = fun x y =>
          match x with
            Zero => y //0 + y = y
            Succ(x1) => Succ(add(x1, y)) //Succ(x) + y = Succ(x + y)
          end
      //Умножение:
        mult = fun x y =>
          match x with
            Zero => Zero // 0 * y = 0
            Succ(x1) => add(y, mult(x1, y)) // Succ(x) * y = y + x * y
          end

    Отлично, но умножение за O(N^2) - это не хорошо. А теперь - забавный фокус. Мы можем научить компилятор, как обращаться с типом Number. Заставим компилировать Number в int, Number.add(x, y) в x + y, Number.mult(x, y) в x * y. Отлично? Не отлично. Кто-то может по прежнему сделать match на нашем Number. Придется также показать, как компилировать:

    match x with 
      Succ(n) => e1 
      Zero => e2
    end
    ( для самостоятельной работы :) )
    Заметьте, что внутри языка мы не прибегали к каким-то вещам, привнесенным извне. У нас есть совершенно честный, полностью определенный Number. Все операции над ним прозрачны. Даже если компилятор будет достаточно наивным, чтобы интерпретировать его "как написано", все будет работать безупречно! Что до прозрачности операций, это огромнейший плюс. Зачем это надо - поговорим в следующих частях.
    Да, в компиляторе L тип Int задан через аксиомы, мне хотелось быстрее получить результат, и я просто прокинул int'овые +, -, /, *, ==, < в L. В стандартной библиотеке, я, безусловно, собирался исправить это допущение.

    + Показать

    22 апреля 2012