Автор Тема: Делаем строку на O7  (Прочитано 21632 раз)

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Делаем строку на O7
« : Октябрь 11, 2013, 05:54:37 am »
Итак, pure Oberon-07 (без динамических массивов). Пытаемся написать модуль для работы со строками любого размера. Минимальный варинт:
- создать строку из ARRAY OF CHAR
- получить размер за O(1)
- получить CHAR по индексу (не знаю как сделать за O(1), но можно попытаться сделать меньше, чем за O(n))
Вот, что у меня получилось:
MODULE String;
CONST
    offs8 = 8;
    offs16 = 8 + 16;
    offs32 = offs16 + 32;
    offs64 = offs32 + 64;
    offs128 = offs64 + 128;
    offs256 = offs128 + 256;
    offs512 = offs256 + 512;
    offs1024 = offs512 + 1024;
    chunkSize = 4096;
TYPE
    Type* = POINTER TO RECORD
        size: INTEGER;
        data: ARRAY 8 OF CHAR;
        next: POINTER TO Data16
    END;
    Data16 = RECORD
        data: ARRAY 16 OF CHAR;
        next: POINTER TO Data32
    END;
    Data32 = RECORD
        data: ARRAY 32 OF CHAR;
        next: POINTER TO Data64
    END;
    Data64 = RECORD
        data: ARRAY 64 OF CHAR;
        next: POINTER TO Data128
    END;
    Data128 = RECORD
        data: ARRAY 128 OF CHAR;
        next: POINTER TO Data256
    END;
    Data256 = RECORD
        data: ARRAY 256 OF CHAR;
        next: POINTER TO Data512
    END;
    Data512 = RECORD
        data: ARRAY 512 OF CHAR;
        next: POINTER TO Data1024
    END;
    Data1024 = RECORD
        data: ARRAY 1024 OF CHAR;
        next: POINTER TO Chunk
    END;
    Chunk = RECORD
        data: ARRAY chunkSize OF CHAR;
        next: POINTER TO Chunk
    END;

PROCEDURE fromArray*(a: ARRAY OF CHAR): Type;
VAR
    result: Type;
   
    PROCEDURE copy(from: INTEGER; VAR dst: ARRAY OF CHAR): BOOLEAN;
    VAR
        i: INTEGER;
    BEGIN
        WHILE (i < LEN(dst)) & (i + from < LEN(a)) DO
            dst[i] := a[i + from];
            INC(i);
        END;
        RETURN i + from < LEN(a)
    END copy;

    PROCEDURE copyToChunks();
    VAR
        i: INTEGER;
        from: INTEGER;
        chunk: POINTER TO Chunk;
    BEGIN
        from := offs1024;
        NEW(chunk);
        result.next.next.next.next.next.next.next.next := chunk;
        WHILE from < LEN(a) DO
            IF i = LEN(chunk.data) THEN
                NEW(chunk.next);
                chunk := chunk.next;
                i := 0;
            END;
            chunk.data[i] := a[from];
            INC(i);
            INC(from);
        END;
    END copyToChunks;

BEGIN
    NEW(result);
    IF copy(0, result.data) THEN
        NEW(result.next);
        IF copy(offs8, result.next.data) THEN
            NEW(result.next.next);
            IF copy(offs16, result.next.next.data) THEN
                NEW(result.next.next.next);
                IF copy(offs32, result.next.next.next.data) THEN
                    NEW(result.next.next.next.next);
                    IF copy(offs64, result.next.next.next.next.data) THEN
                        NEW(result.next.next.next.next.next);
                        IF copy(offs128, result.next.next.next.next.next.data) THEN
                            NEW(result.next.next.next.next.next.next);
                            IF copy(offs256, result.next.next.next.next.next.next.data) THEN
                                NEW(result.next.next.next.next.next.next.next);
                                IF copy(offs512, result.next.next.next.next.next.next.next.data) THEN
                                    copyToChunks();
                                END;
                            END;
                        END;
                    END;
                END;
            END;
        END;
    END;

    result.size := LEN(a);
    RETURN result
END fromArray;   

PROCEDURE size*(s: Type): INTEGER;
    RETURN s.size
END size;

PROCEDURE at*(s: Type; index: INTEGER): CHAR;
VAR
    result: CHAR;

    PROCEDURE chunkAt(): CHAR;
    VAR
        i: INTEGER;
        chunk: POINTER TO Chunk;
    BEGIN
        chunk := s.next.next.next.next.next.next.next.next;
        FOR i := 0 TO ((index - offs1024) DIV chunkSize) - 1 DO
            chunk := chunk.next;
        END;
        RETURN chunk.data[(index - offs1024) MOD chunkSize]
    END chunkAt;

BEGIN
    IF index < offs8 THEN
        result := s.data[index];
    ELSIF index < offs16 THEN
        result := s.next.data[index - offs8];
    ELSIF index < offs32 THEN
        result := s.next.next.data[index - offs16];
    ELSIF index < offs64 THEN
        result := s.next.next.next.data[index - offs32];
    ELSIF index < offs128 THEN
        result := s.next.next.next.next.data[index - offs64];
    ELSIF index < offs256 THEN
        result := s.next.next.next.next.next.data[index - offs128];
    ELSIF index < offs512 THEN
        result := s.next.next.next.next.next.next.data[index - offs256];
    ELSIF index < offs1024 THEN
        result := s.next.next.next.next.next.next.next.data[index - offs512];
    ELSE
        result := chunkAt();
    END
    RETURN result
END at;

END String.

Тестируем это безобразие:
MODULE TestString;
IMPORT String;
CONST
    longStringSize = 1024 * 100 + 1;
VAR
    s: String.Type;
    testArray: ARRAY longStringSize OF CHAR;
    i: INTEGER;
BEGIN
    s := String.fromArray("abc");
    ASSERT(String.size(s) = 3);
    ASSERT(String.at(s, 0) = "a");
    ASSERT(String.at(s, 1) = "b");
    ASSERT(String.at(s, 2) = "c");

    FOR i := 0 TO LEN(testArray) - 1 DO
        testArray[i] := CHR(i);
    END;
    s := String.fromArray(testArray);
    ASSERT(String.size(s) = LEN(testArray));
    FOR i := 0 TO LEN(testArray) - 1 DO
        ASSERT(testArray[i] = String.at(s, i));
    END;

END TestString.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #1 : Октябрь 11, 2013, 06:15:33 am »
Что не нравится в этом решении (помио отсутствия динамических массивов, которые сделали бы решение тривиальным):
- Жуткий копипаст (привет джерекам).
- Огроменная лестница IF'ов (из-за единственности RETURN). Можно завести булевую переменную и проверять ее каждый раз... но зачем?
- Запись String.at(s, index) для доступа к элементу строки осилят только религиозно обработанные писатели (привет перегрузке операторов).
- Строка всегда будет в хипе (давайте представим, что транслируем не в JS). И с этим ничего нельзя сделать, если потребовать иммутабельности строки (мутабельные строки не нужны). Привет конструкторам.
- Доступ к элементу за O(n), хотя n и поделено на довольно большую константу. Более быстрый доступ требует более сложной реализации.

 

adva

  • Sr. Member
  • ****
  • Сообщений: 385
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #2 : Октябрь 11, 2013, 07:09:08 am »
Извиняюсь, что не в тему:

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

Таблица, как понимаю МАССИВ. Колоноки обеспечиваются ЗАПИСЬю

Но вот не соображу, как задать СВОЙСТВО данной ЗАПИСИ составного типа (чтобы можно было присвоить, например и ТИП1 и ТИП2)

adva

  • Sr. Member
  • ****
  • Сообщений: 385
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #3 : Октябрь 11, 2013, 07:16:38 am »
И вдогонку, в итоге нужна будет одна функция, возвращающая объекты разных типов. Это реализуется с помощью ПРОЦЕДУРНОГО типа?

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #4 : Октябрь 11, 2013, 07:43:37 am »
Таки это попытки использовать язык для встроенки на прикладном уровне, имхо.
Вирт порезал его для того, чтобы это всюду влезало, а не чтобы так строки на нём реализовывать :)

DddIzer

  • Гость
Re: Делаем строку на O7
« Ответ #5 : Октябрь 11, 2013, 07:54:55 am »
Таки это попытки использовать язык для встроенки на прикладном уровне, имхо.
Вирт порезал его для того, чтобы это всюду влезало, а не чтобы так строки на нём реализовывать :)
только сам Вирт про это ничего не говорил.. видать не влезло в 16 страниц... хотя вроде место для  general purpose language - у него нашлось.. ;)

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #6 : Октябрь 11, 2013, 08:53:53 am »
Таки это попытки использовать язык для встроенки на прикладном уровне, имхо.
Вирт порезал его для того, чтобы это всюду влезало, а не чтобы так строки на нём реализовывать :)
Стоп. А как отсутствие массивов с размером неизвестным на этапе компиляции облегчает влезабельность в микроконтроллер?

PS. а чтобы оно везде влезало нужно было отвязываться от 32 бит. А то в msp430 оно, в отличие от С++, до сих пор не влазит.
Y = λf.(λx.f (x x)) (λx.f (x x))

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #7 : Октябрь 11, 2013, 09:53:12 am »
Ну, я так понимаю рантайм упрощается - это раз;
во-вторых, чтобы любой компонент, написанный на языке X, мог быть использован в любом окружении, можно пойти как раз путём сделать невозможным программировать так, что потом конкретный компонент не влезет в конкретное системное окружение (типа, писали на КП библиотеку - внутри понаюзали дин. массивов, потом микроконтроллерщики, допустим, на том же КП захотели использовать эту библиотеку - а оп-па, этот компонент требует кучи не слабого размера и т.п. А запретим дин. массивы - так все будут осмотрительнее по использованию памяти). Возможна такая логика.
Кроме того, Вирт давно смотрел в сторону компиляции с ЯП прямо в схемную топологию, может, из-за этого тоже такие эксперименты с урезанием языка...

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #8 : Октябрь 11, 2013, 10:27:25 am »
Ну, я так понимаю рантайм упрощается - это раз;
Если подумать, то нет, не упрощается - менеджер памяти на практике остается тем же самым - размещающим блоки произвольного размера в куче.

Либо нужно сурово усложнить рантайм, сделать его сборку зависящим от сборки основного приложения - усложнить компилятор, чтобы он проводил глубокий анализ кодов приложения и на основе этого генерировал код рантайма. В этом случае да, теоретически возможно скажем уменьшить вероятность фрагментации кучи во время работы.

во-вторых, чтобы любой компонент, написанный на языке X, мог быть использован в любом окружении, можно пойти как раз путём сделать невозможным программировать так, что потом конкретный компонент не влезет в конкретное системное окружение (типа, писали на КП библиотеку - внутри понаюзали дин. массивов, потом микроконтроллерщики, допустим, на том же КП захотели использовать эту библиотеку - а оп-па, этот компонент требует кучи не слабого размера и т.п. А запретим дин. массивы - так все будут осмотрительнее по использованию памяти).
Запрет динамических массивов скорее приведет либо к написанию собственного менеджера памяти и собственных Opaque-массивов, либо к ПЕРЕРАСХОДУ памяти в куче и на стеке. Ибо брать будут с запасом, чтобы гарантированно поместилось.

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

Нужно что-то разместить в куче? Делайте через SYSTEM!

PS. А есть еще более странные изменения в Обероне-07/11 относительно Оберона изначального: http://oberspace.dyndns.org/index.php/topic,544.0.html Мы так и не смогли придумать нафига это может быть нужно.
Y = λf.(λx.f (x x)) (λx.f (x x))

Jordan

  • Sr. Member
  • ****
  • Сообщений: 282
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #9 : Октябрь 11, 2013, 10:58:43 am »
Из всего, что сказано, 07 это универсальный язык или нет? Сам Вирт, что пишет по этому поводу? Это дальнейшее развитие языка оберон или узконацеленная ветка языка, для конкретных задач?

Jordan

  • Sr. Member
  • ****
  • Сообщений: 282
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #10 : Октябрь 11, 2013, 11:02:42 am »
И такой вопрос, имеет ли смысл запрет дин массивов для программирования микроконтроллёров?
И ещё вопрос, обосновывает ли Вирт, удаление возможностей из языка? Исключил потому, что мол так и так.

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #11 : Октябрь 11, 2013, 11:04:31 am »
Из всего, что сказано, 07 это универсальный язык или нет? Сам Вирт, что пишет по этому поводу? Это дальнейшее развитие языка оберон или узконацеленная ветка языка, для конкретных задач?
Судя по репорту - это дальнейшее развитие Оберона. Там нет ни слова про "Oberon-07" - это чисто наше изобретение. Это просто Oberon, новая, уточненная и дополненная ревизия репорта.
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #12 : Октябрь 11, 2013, 11:08:25 am »
И такой вопрос, имеет ли смысл запрет дин массивов для программирования микроконтроллёров?
Для программирования микроконтроллеров (и не только) имеет смысл запрет NEW (кучи) вообще. Точнее, по хорошему, NEW вынести бы в либы (тогда был бы один набор либ для скажем микроконтроллеров, другой для десктопа). Но семантика NEW такова, что языковыми методами библиотечно NEW сделать не возможно. Видимо поэтому NEW Вирт до сих пор из языка не выпилил - чтобы NEW стала обычной процедурой пришлось бы существенно усложнить язык.

И ещё вопрос, обосновывает ли Вирт, удаление возможностей из языка? Исключил потому, что мол так и так.
По поднятым тут вопросам обоснований я не видел. Ну и Вирт на письма не отвечает, увы.
Y = λf.(λx.f (x x)) (λx.f (x x))

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #13 : Октябрь 11, 2013, 01:09:43 pm »
И вдогонку, в итоге нужна будет одна функция, возвращающая объекты разных типов. Это реализуется с помощью ПРОЦЕДУРНОГО типа?

А на каком языке? Если на обероне, то это делается с помощью наследования записей.
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Делаем строку на O7
« Ответ #14 : Октябрь 11, 2013, 02:44:25 pm »
Но вот не соображу, как задать СВОЙСТВО данной ЗАПИСИ составного типа (чтобы можно было присвоить, например и ТИП1 и ТИП2)

Классический ООП подход - завести базовый "безтиповый" тип и наследовать от него "типизированные". Везде, где нужна "безтиповость" такскать базовый, а там где нужен тип - кастить к "типизированному". На O7:
TYPE
    AnyType = RECORD END;
    Type1 = RECORD(AnyType) field: INTEGER END;
    Type2 = RECORD(AnyType) field: CHAR END;
    PAnyType: POINTER TO AnyType;

PROCEDURE getObject(): PAnyType; (* возвращает любой объект*)
« Последнее редактирование: Октябрь 11, 2013, 02:46:04 pm от vlad »