Этюд Unbox(Box<Box<...Box<T>...>> )
От: WolfHound  
Дата: 26.06.10 22:55
Оценка: 25 (2)
В форуме .НЕТ запостили вот такой этюд
Автор: nikov
Дата: 26.06.10
.
В рамках системы типов .НЕТ данный этюд статически типизированно не решается.
Но он по зубам С++:
template<class T>
struct Box
{
private:
    T _value;

public:
    T Get() const
    {
        return _value;
    }

    Box(T const& value)
        : _value(value)
    {}
};

template<class T>
Box<T> box(T const& value)
{
    return Box<T>(value);
}

template<class T>
struct UnwrapBoxedType
{
    typedef T type;
};

template<class T>
struct UnwrapBoxedType<Box<T> >
{
    typedef typename UnwrapBoxedType<T>::type type;
};

template<class T>
T unwrap(T const& value)
{
    return value;
}

template<class T>
typename UnwrapBoxedType<T>::type unwrap(Box<T> const& box)
{
    return unwrap(box.Get());
}

int main()
{
    std::cout << unwrap(box(box(box(box(box(box(123))))))) << std::endl;
    return 0;
}

UnwrapBoxedType это функция осуществляющая вычисления над типами. Она достает тип значения самой вложенной коробки.

Однако система типов С++ весьма не формальна и все проверки осуществляются в момент вызова unwrap.

Есть ли языки где можно провернуть такой фокус проверив типы unwrap в месте ее описания, а не в месте вызова.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Этюд Unbox(Box<Box<...Box<T>...>> )
От: gear nuke  
Дата: 27.06.10 02:39
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Однако система типов С++ весьма не формальна и все проверки осуществляются в момент вызова unwrap.

WH>Есть ли языки где можно провернуть такой фокус проверив типы unwrap в месте ее описания, а не в месте вызова.

Можно более подробно описать проблему для ммм... приплюснутых мозгов?

Проверка типа в момент вызова (инстанциации) функции происходит при использовании специализаций шаблона.

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

Немного упрощу предложенное решение, что бы это стало очевидно:
int unwrap(int const& value)
{
    return value;
}

template<class T>
typename UnwrapBoxedType<T>::type unwrap(Box<T> const& box) 
{
    return unwrap(box.Get());
}
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re: Этюд Unbox(Box<Box<...Box<T>...>> )
От: FR  
Дата: 27.06.10 05:19
Оценка:
Здравствуйте, WolfHound, Вы писали:


WH>Однако система типов С++ весьма не формальна и все проверки осуществляются в момент вызова unwrap.

WH>Есть ли языки где можно провернуть такой фокус проверив типы unwrap в месте ее описания, а не в месте вызова.

На D можно запихнуть в одну compile time функцию, но по сути будет тоже что и в C++ проверка при инициализации.
Re[2]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: WolfHound  
Дата: 27.06.10 10:58
Оценка:
Здравствуйте, gear nuke, Вы писали:

WH>>Есть ли языки где можно провернуть такой фокус проверив типы unwrap в месте ее описания, а не в месте вызова.
GN>Можно более подробно описать проблему для ммм... приплюснутых мозгов?
Честно говоря не понимаю куда подробнее.
Проблема в том что все проверки осуществляются вот в этом месте
unwrap(box(box(box(box(box(box(123)))))))
А хочется чтобы к этому моменту уже все было проверено

GN>Проверка типа в момент вызова (инстанциации) функции происходит при использовании специализаций шаблона.
GN>В данном случае специализации шаблона нет, есть 2 перегруженные функции, тип агрумента которых уже известен в момент определения.
А ты хорошо смотрел?
А это что?
typename UnwrapBoxedType<T>::type
Также не стоит забывать вот про эту волшебную строку
return unwrap(box.Get());
разрешение перегрузки опять же происходит в момент вызова функции.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: vdimas Россия  
Дата: 27.06.10 12:59
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Проблема в том что все проверки осуществляются вот в этом месте
WH>unwrap(box(box(box(box(box(box(123)))))))
WH>А хочется чтобы к этому моменту уже все было проверено

Задай в Box<> целочисленный параметр-счетчик, определяющий глубину вложения, и перепиши специализации UnwrapBoxedType<> с рекурсивным использованием счетчика, типа ручная проверка.

Только не понятно, зачем? Да, в момент компиляции конкретного места вызова ф-ии, компилятор сам рекурсивно проверит все типы для каждой итерации unwrap(), вплоть до своего ограничения на глубину вложенности шаблонов.

WH>разрешение перегрузки опять же происходит в момент вызова функции.

Хотел сказать, компиляции места вызова?

Да, проблема известная. Это из-за отсутствия частичной специализации ф-ий, вследствии чего приходится использовать пользовательские типы-хелперы, навроде твоего UnwrapBoxedType<T>. Проблема тут в том, что раз хелпер-это другой тип, не связанный с Box<>, то в момент его определения и определения шаблонной ф-ии unwrap компилятор не способен проверить соответствие типов (без того "ручного" счетчика, например). Я в похожих случаях стараюсь давать компилятору больше информации, типа:

template<typename T>
struct Box {
typedef T value_type;
typedef T most_wrapped_type;
...
};

template<typename T>
struct Box< Box<T> > {
typedef Box<T> value_type;
typedef typename Box<T>::most_wrapped_type most_wrapped_type;
...
};

А в самом хелпере UnwrapBoxedType просто перенаправить на Box<>::most_wrapped_type, чтобы уменьшить вероятность ошибки. (Рассматриваемый пример конечно примитивен и не нуждается в этом, но это я об общей практике говорю).

Правда, MS VC все-равно все нафиг игнорирует, т.е. не проверяет толком шаблоны. Дык, зато GCC с версий 4.x более внимательно их проверяет, и частенько ругается на всякие несоответствия еще до инстанциирования, т.е. в момент компиляции самих шаблонных определений, чем приятно радует.

Конечно, нужны явные constrains. До определенной степени их можно эмулировать (и в бусте полно хелперов под распространенные случаи, довольно-таки мощный там раздел type traits), но на уровне языка, т.е. с нормальным синтаксисом, а не тонной угловых скобок, было бы интересней.
Re[4]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: WolfHound  
Дата: 27.06.10 13:49
Оценка:
Здравствуйте, vdimas, Вы писали:

V>Задай в Box<> целочисленный параметр-счетчик, определяющий глубину вложения, и перепиши специализации UnwrapBoxedType<> с рекурсивным использованием счетчика, типа ручная проверка.
Box менять нельзя.

V>Только не понятно, зачем? Да, в момент компиляции конкретного места вызова ф-ии, компилятор сам рекурсивно проверит все типы для каждой итерации unwrap(), вплоть до своего ограничения на глубину вложенности шаблонов.
Проблема в том что в таком виде unwrap нельзя скомпилировать и положить в отдельный модуль.

V>Да, проблема известная. Это из-за отсутствия частичной специализации ф-ий, вследствии чего приходится использовать пользовательские типы-хелперы, навроде твоего UnwrapBoxedType<T>.
Нука покажи как это можно сделать без использования UnwrapBoxedType.

V> Проблема тут в том, что раз хелпер-это другой тип, не связанный с Box<>, то в момент его определения и определения шаблонной ф-ии unwrap компилятор не способен проверить соответствие типов (без того "ручного" счетчика, например). Я в похожих случаях стараюсь давать компилятору больше информации, типа:
Ты не понял.
Мне интересно решение конкретной задачи.
Причем не абы какое, а формальное.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Этюд Unbox(Box<Box<...Box<T>...>> )
От: deniok Россия  
Дата: 27.06.10 14:02
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Есть ли языки где можно провернуть такой фокус проверив типы unwrap в месте ее описания, а не в месте вызова.

Можно точно сформулировать требуемые ограничения на "фокус"? Такое впечатление, что все сложности связаны с полубезумными механизмами терминирования типовой рекурсии на шаблонах.

Почему бы, например, не маркировать завершение рекурсии по типам явно, поименовав конструктор небоксированных данных?
data Boxes a = Value a | Box (Boxes a)

unwrap :: Boxes t -> t
unwrap (Box b)   = unwrap b
unwrap (Value v) = v


> unwrap (Box (Box (Box (Box (Value 123)))))
123
Re[2]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: WolfHound  
Дата: 27.06.10 15:00
Оценка:
Здравствуйте, deniok, Вы писали:

D>Почему бы, например, не маркировать завершение рекурсии по типам явно, поименовав конструктор небоксированных данных?
Так не интересно.
Ибо вот эти значения имеют один тип.
(Box (Value 123))
(Box (Box (Value 123)))
В исходной задаче они имеют разные типы.

Хочется вот такое
data Box a = Box a

unwrap :: ??? -> t
???


unwrap (Box(Box(Box(Box(123)))))

Хочется посмотреть на язык в котором такое можно.
Ибо что-то мне подсказывает что если можно такое то система типов позволит еще много интересного.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[5]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: vdimas Россия  
Дата: 27.06.10 18:21
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Мне интересно решение конкретной задачи.
WH>Причем не абы какое, а формальное.

Из очевидных формальных — с положительным целочисленным счетчиком в Box и генерацией ошибки на некоем count==some_max. А не меняя Box<> решить в общем виде ИМХО в принципе невозможно, хотя бы из-за потенциальной бесконечной вложенности.

В типах дотнета красивое и строго типизированное решение вообще не представимо. У меня была абсолютно идентичная задача, так вот, без всяких динамиков она решалась примерно так:
interface IBoxedValue { object Value { get; } }
interface IBoxedValue<T> { T Value { get;} }

class Box<T> : IBoxedValue<T>, IBoxedValue { ... }

object GetRealObject(object o) {
  object tmp;
  while(null != (tmp=(o as IBoxedValue)))
    o = tmp.Value;

  return o;
}


К тому же, интерфейс IBoxedValue использовался не только в Box<>, бо прием типа ISomethingProvider удобен в массе различных вариаций.
Re[2]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: vdimas Россия  
Дата: 27.06.10 18:26
Оценка:
Здравствуйте, deniok, Вы писали:

D>Почему бы, например, не маркировать завершение рекурсии по типам явно, поименовав конструктор небоксированных данных?
D>
D>data Boxes a = Value a | Box (Boxes a)

D>unwrap :: Boxes t -> t
D>unwrap (Box b)   = unwrap b
D>unwrap (Value v) = v
D>


D>
>> unwrap (Box (Box (Box (Box (Value 123)))))
D>123
D>


Ну, введя доп. рантайм флаг (дискриминатор алг. типа) можно на любом языке аналогично сделать.
Хотелось без рантайм-костылей.
Re[5]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: Artifact  
Дата: 27.06.10 21:55
Оценка: 5 (1)
Здравствуйте, WolfHound, Вы писали:

WH>Нука покажи как это можно сделать без использования UnwrapBoxedType.

Ну в GCC 4.4 (я пользуюсь MinGW под Виндой сейчас) с опцией -std=c++0x можно заставить компилятор вывести тип

template<class T>
struct Box
{
private:
    T _value;

public:
    T Get() const
    {
        return _value;
    }

    Box(T const& value)
        : _value(value)
    {}
};

template<class T>
Box<T> box(T const& value)
{
    return Box<T>(value);
}

template<class T>
struct Unwrap
{
    T operator()(T const& value)
    {
        return value;
    }
};

template<class T>
struct Unwrap<Box<T>>
{    
    auto operator()(Box<T> const& box) -> decltype(Unwrap<T>()(box.Get()))
    {
        return Unwrap<T>()(box.Get());
    }
};

template<class T>
auto unwrap(Box<T> const& box) -> decltype(Unwrap<Box<T>>()(box.Get()))
{
    return Unwrap<Box<T>>()(box.Get());
}

int main()
{
    std::cout << unwrap(box(box(box(box(box(box(123))))))) << std::endl;
    return 0;
}


Только вот пришлось использовать структуры. С функциями decltype отправляет компилятор в аут.
__________________________________
Не ври себе.
Re[3]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: night beast СССР  
Дата: 28.06.10 06:13
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>>>Есть ли языки где можно провернуть такой фокус проверив типы unwrap в месте ее описания, а не в месте вызова.
GN>>Можно более подробно описать проблему для ммм... приплюснутых мозгов?
WH>Честно говоря не понимаю куда подробнее.
WH>Проблема в том что все проверки осуществляются вот в этом месте
WH>unwrap(box(box(box(box(box(box(123)))))))
WH>А хочется чтобы к этому моменту уже все было проверено

ок. где по твоему все уже должно быть проверенно? (в каком месте)
Re[3]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: deniok Россия  
Дата: 28.06.10 07:20
Оценка: 10 (2)
Здравствуйте, vdimas, Вы писали:

D>>
>>> unwrap (Box (Box (Box (Box (Value 123)))))
D>>123
D>>


V>Ну, введя доп. рантайм флаг (дискриминатор алг. типа) можно на любом языке аналогично сделать.
V>Хотелось без рантайм-костылей.

Ну тогда это уже не что иное как оптимизация; напишем правила, аннигилирующие unwrap'ы и явные применения конструкторов боксов:
{-# RULES
"unwrap/box"    forall b. unwrap (Box b) = unwrap b
"unwrap/value"  forall v. unwrap (Value v) = v
  #-}

откомпилируем с ключиками -o2 (оптимизация) и -ddump-simpl-stats (чтобы посмотреть, что правила отработали). Получим для 
main = do putStrLn test 
test = unwrap (Box (Box (Box (Box (Value "foo")))))

дамп статистики
==================== Grand total simplifier statistics ====================
Total ticks:     36

8 PreInlineUnconditionally
4 UnfoldingDone
7 RuleFired
    1 unpack
    1 unpack-list
    4 unwrap/box
    1 unwrap/value
2 LetFloatFromLet
15 BetaReduction
10 SimplifierDone
Re[3]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: deniok Россия  
Дата: 28.06.10 07:42
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Хочется вот такое
WH>
WH>data Box a = Box a

WH>unwrap :: ??? -> t
WH>???


WH>unwrap (Box(Box(Box(Box(123)))))
WH>

WH>Хочется посмотреть на язык в котором такое можно.

"Такое" мне непонятно. unwrap — это функция, то есть ??? — это тип. Задача — свернуть семейство возможных здесь тИповых конструкций в замкнутую форму для этого типа. Вариант ad hoc множества типов не очень элегантен (ручками писать все возможные перегрузки — задолбаешься) и, вроде, ни кем и не предлагается. Я предложил классический рекурсивный тип; можно ещё забацать индексированное натуральными числами семейство.
Re: Этюд Unbox(Box<Box<...Box<T>...>> )
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 28.06.10 08:21
Оценка: 236 (12)
Здравствуйте, WolfHound, Вы писали:

WH>Есть ли языки где можно провернуть такой фокус проверив типы unwrap в месте ее описания, а не в месте вызова.

То, чем ты занимаешься, называется "извращение". Присоединюсь, если ты не против 

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, IncoherentInstances, TypeFamilies #-}

data Box a = Box a

class Boxed b v where
    unwrap :: b -> v

instance Boxed b v => Boxed (Box b) v where
    unwrap (Box x) = unwrap x

instance (l ~ r) => Boxed l r where
    unwrap x = x

> unwrap (Box(Box(Box(Box(123)))))
123
Re[2]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: deniok Россия  
Дата: 28.06.10 08:23
Оценка:
Здравствуйте, lomeo, Вы писали:

L>
L>{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, IncoherentInstances, TypeFamilies #-}

L>instance (l ~ r) => Boxed l r where
L>    unwrap x = x

L>


Где ты научился пользоваться ~ ? Я тоже хочу!
Re[3]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 28.06.10 08:33
Оценка:
Здравствуйте, deniok, Вы писали:

D>Где ты научился пользоваться ~ ? Я тоже хочу!

Не надо, это изврат, лучше задачу переформулировать.
Re[4]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: vdimas Россия  
Дата: 28.06.10 11:46
Оценка:
Здравствуйте, deniok, Вы писали:

Интересная фича, но сдается мне, она возможна только если компилятор "видит" как формировался вложенный Box.
Re[3]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: gear nuke  
Дата: 28.06.10 20:31
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>А это что?
WH>typename UnwrapBoxedType<T>::type

Это "вытащенный из коробки" тип T. Он уже известен в момент определения функции.

WH>Также не стоит забывать вот про эту волшебную строку
WH>return unwrap(box.Get());
WH>разрешение перегрузки опять же происходит в момент вызова функции.

Оно происходит когда компилятор смотрит тело функиции, то есть в момент определения.

Можно добавить явное инстанциирование (и проверки) перед вызовом:
auto p = &unwrap<Box<Box<Box<Box<Box<int>>>>>>;


Это можно скомпилировать и положить в отдельный модуль. Однако есть проблема с неограниченной вложенностью.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re[2]: Этюд Unbox(Box<Box<...Box<T>...>> )
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 29.06.10 08:00
Оценка:
lomeo,

Это чего такое, можешь объяснить?
L>instance (l ~ r) => Boxed l r where
L>    unwrap x = x

Ибо такую синтаксическую конструкцыю я встречаю впервые.
... << RSDN@Home 1.2.0 alpha 4 rev. 1423>>
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.