Lex20 2 сен 2016 в 11:31

Вывод типов в программировании

5 мин

12K

C*C++*JavaScript*Алгоритмы*Программирование*

Из песочницы

-6

Комментарии 69

DrPass 2 сен 2016 в 11:35

> Шаблоны вводят новый тип-общий для всех типов
Вообще-то шаблоны — это именно шаблоны. А общий тип вводят дженерики, которые есть в Java, C#, Delphi, и напрочь отсутствуют в С++. И да, синтаксически выглядят подобно шаблонам. И вот как раз «общий тип», сиречь, дженерик, не генерирует несколько разных экземпляров кода под разные типы, а оперирует приведением типов.

lair 2 сен 2016 в 11:39

И вот как раз «общий тип», сиречь, дженерик, не генерирует несколько разных экземпляров кода под разные типы, а оперирует приведением типов.

В C# именно что генерирует разные экземпляры. Типичный пример:

class Smth<T>
{
    static readonly Serializer S = new Serializer(typeof(T));
}

Shannon 2 сен 2016 в 13:50

Чтобы нагляднее было, например swift:

func f<T>(fn: T -> Void, _ item: T) {
    fn(item)
}

func a<T>(item: T) {
    print(item.dynamicType)
}

f(a, 1) // Int
f(a, 1.0) // Double
f(a, "Alexey") // String

roman_kashitsyn 2 сен 2016 в 14:51

Чтобы нагляднее было

А что именно стало наглядней?

Shannon 2 сен 2016 в 19:16

Чтобы автору статьи стало нагляднее, что дженерики решают всё то, что написано в статье

roman_kashitsyn 4 сен 2016 в 00:26

Чтобы автору статьи стало нагляднее, что дженерики решают всё то, что написано в статье

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

Shannon 4 сен 2016 в 01:40

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

Вероятно он хочет решать не эту проблему, потому что эта проблема уже решена в js

Самое начало статьи:

При написании алгоритмов зачастую возникает ситуация, когда какая-то функция нуждается в вызове с тем же количеством аргументов, но с не совпадающими типами. Решаем.

И приводится решение этой задачи 2-мя примерами на C++ и JS, после чего промежуточный вывод «Очевидно, что код на javascript является более удачным.»

Дальше идет, собственно, и сама суть:

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

Соответственно вместо написания своего языка, обозначенную проблему (писать максимально производительный код без потери читаемости и без необходимости писать тип на «каждый чих») можно решать другим путем, и я лишь дополнил наглядным примером, что получившийся код, например, на swift не сильно сложнее варианта на js

Но раз речь зашла про не указывать типы явно, то например, в swift тоже не обязательно описать типы явно, они выводятся из контекста, а для функций можно использовать дженерики, таким образом получится гибрит, когда ни один тип явно не задан и код не теряет в читаемости (тут http://www.runswiftlang.com/ можно поэкспериментировать онлайн)

func f<T>(fn: T -> Void, _ item: T) {
    fn(item)
}

func a<T>(item: T) {
    print("item type: \(item.dynamicType)") // аналог typeof item
}

let a1 = 1
let a2 = 1.0
let a3 = "Alexey"

f(a, a1) // item type: Int
f(a, a2) // item type: Double
f(a, a3) // item type: String

let z = "zzz"
let zz = ["key1": z]
f(a, zz) // item type: Dictionary

var b1 = 1
var b2 = "str"
b1 = b2 // error: cannot assign value of type 'String' to type 'Int'

lair 4 сен 2016 в 01:54

когда ни один тип явно не задан

Ну, это неправда. Типы параметров функций задаются явно (то, что они при этом дженеричны — это второй вопрос).

let f fn item = fn item
let a item = fn.GetType() |> printfn "%A"

Вот тут типов параметров функций и правда нет (при этом все статически типизированное).

Shannon 4 сен 2016 в 02:14

Да, не правда, поэтому и назвал это «гибридом», чтобы просто идею продемонстрировать

qadmium 2 сен 2016 в 22:22

А общий тип вводят дженерики, которые есть в Java, C#, Delphi, и напрочь отсутствуют в С++.

C#?

 class Program
    {
        static void Main(string[] args)
        {
            Generic(1);
            Generic("1");
        }

        static string Generic<T>(T value)
        {
            return value.ToString();
        }
    }

int:

--- C:\Users\sow\Documents\Visual Studio 2015\Projects\testawait\testawait\Program.cs 
    24:             return value.ToString();
029C2DE8  push        ebp  
029C2DE9  mov         ebp,esp  
029C2DEB  sub         esp,8  
029C2DEE  xor         eax,eax  
029C2DF0  mov         dword ptr [ebp-8],eax  
029C2DF3  mov         dword ptr [ebp-4],ecx  
029C2DF6  cmp         dword ptr ds:[0FBC7D4h],0  
029C2DFD  je          029C2E04  
029C2DFF  call        72BE6150  
029C2E04  lea         ecx,[ebp-4]  
029C2E07  call        717B6220  
029C2E0C  mov         dword ptr [ebp-8],eax  
029C2E0F  mov         eax,dword ptr [ebp-8]  
029C2E12  mov         esp,ebp  
029C2E14  pop         ebp  
029C2E15  ret

string:

--- C:\Users\sow\Documents\Visual Studio 2015\Projects\testawait\testawait\Program.cs 
    24:             return value.ToString();
029C2E2C  in          al,dx  
029C2E2D  or          al,33h  
029C2E2F  ror         byte ptr [ecx+4D89F445h],0FCh  
029C2E36  mov         dword ptr [ebp-8],edx  
029C2E39  cmp         dword ptr ds:[0FBC7D4h],0  
029C2E40  je          029C2E47  
029C2E42  call        72BE6150  
029C2E47  mov         ecx,dword ptr [ebp-4]  
029C2E4A  mov         eax,dword ptr [ecx]  
029C2E4C  mov         eax,dword ptr [eax+28h]  
029C2E4F  call        dword ptr [eax]  
029C2E51  mov         dword ptr [ebp-0Ch],eax  
029C2E54  mov         eax,dword ptr [ebp-0Ch]  
029C2E57  mov         esp,ebp  
029C2E59  pop         ebp  
029C2E5A  ret

Halt 2 сен 2016 в 11:42

Советую вам обратить внимание на литературу по этой теме, дабы не изобретать велосипед. А если и изобретать, то делать это осознанно.
То что вы описали, реализуется на полиморфном типированном лямбда-исчислении алгоритмом Хиндли-Милнера.

Буквально неделю назад, я читал доклады на эту тему на конференции C++ Siberia. Видео еще нет, а слайды можно посмотреть.

Первая часть — вывод типов на примере Smalltalk
Вторая часть — основы лямбда-исчисления и подход к проблеме типизации

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

НЛО прилетело и опубликовало эту надпись здесь

Veliant 2 сен 2016 в 11:42

Язык C требует указывать тип переменной и запрещает его менять. В результате во время выполнения программы нет никаких проверок типов, операторы применяются к переменным однозначно. Но при этом нет красивых механизмов обобщения. Что есть: универсальный указатель void*, возможность передать функции указатель на другую функцию. В языке C++, который в некотором роде является расширением языка C, появились такие механизмы как полиморфизм функций(перегрузка) и шаблоны.

Читайте стандарт C11. Там есть следующие конструкции:

#define cbrt(X) _Generic((X), long double: cbrtl, \
                              default: cbrt, \
                              float: cbrtf)(X)

При вызове cbrt с аргументом long double типа будет вызвана cbrtl, с аргументом float — cbrtf

Lex20 2 сен 2016 в 17:33

Имел ввиду ANSI С

lair 2 сен 2016 в 11:44

К простому типу отнесём все типы, в которые не вложены другие(строковый, числовой, массив ...).

И почему же в массив не вложены другие типы?

Вывод типа из выражения делается вполне однозначно, так как операторы, как унарные, так и бинарные, действуют во множество определённого типа. Так, оператор "+" при сложении двух типов int даёт в результате int.

Это только ваше допущение, оно не обязательно всегда верно.

И да, как вы, собственно, собираетесь выводить тип аргументов функции?

f(user {name}) {}

Какого типа user.name?

Lex20 2 сен 2016 в 17:43

И почему же в массив не вложены другие типы?

В простом массиве все данные одного типа.
В гетерогенный вложены.

И да, как вы, собственно, собираетесь выводить тип аргументов функции?

Тип выводиться в теле функции.

lair 2 сен 2016 в 17:47

В простом массиве все данные одного типа.

… и этот тип не "вложен" в массив разве? Собственно, массив — это первый и канонический пример обобщенного типа, вообще-то.

Тип выводиться в теле функции.

fun f(a) -> a.x

Какого типа a? Какого типа возвращаемое значение?

roman_kashitsyn 2 сен 2016 в 18:07

Какого типа a? Какого типа возвращаемое значение?

В OCaml, к примеру, функция f имеет вполне определённый тип, тип аргумента определяется его структурной, тип возвращаемого значения — полиморфный:

let f a = a#x;;

  val f : < x : 'a; .. > -> 'a = <fun>

lair 2 сен 2016 в 18:10

Я, в принципе, в общем случае представляю себе, как это делается, но есть, так сказать, нюансы. Ну и мне интересно, что именно автор по этому поводу думает.

(кстати, а OCaml в таком случае требует, чтобы у a было как минимум x, или только x?)

roman_kashitsyn 2 сен 2016 в 18:19

как минимум x, или только x?

Как минимум x. За это отвечают две точки после точки с запятой: ; .. >. Если бы этих точек не было, тип бы означал "только x".

Lex20 3 сен 2016 в 14:21

Аргументы выводятся при каждом вызове функции. Тип возвращаемого значения выводится в теле самой функции. Если возвращаемых значений 2 и более — ошибка компиляции.

lair 3 сен 2016 в 14:25

Я там выше привел пример. Какого типа параметр функции и возвращаемое ей значение?

Ну или вот вам другой пример.

fun f (a, b) = a > b

Какого типа a и b?

Или вот еще:

fun f (a, b) = if a > b then a.x else b.y

Lex20 3 сен 2016 в 14:40

fun f (a, b) = a > b

При таком вызове функции:

f(1, 'string')

a-числовой, b-строковый тип. Если для таких a и b определён оператор >, то возвращаемое значение функции a будет того же типа, что и возвращаемое значение оператора >.

fun f (a, b) = if a > b then a.x else b.y

Здесь ошибка, поскольку в аргументах не обозначено, что переменная a включает в себя переменную x, b, соответственно, y.
Если было бы обозначено, и функция возвращала значения разных типов(типы переменных x и y), то была бы ошибка компиляции.

lair 3 сен 2016 в 14:48

При таком вызове функции f(1, 'string') a-числовой, b-строковый тип.

Ну то есть вы не выводите тип параметра, на самом деле (а, значит, и тип функции). Вы, наоборот, подставляете ранее выведенный тип в параметр, и от этого пытаетесь посчитать, возможна ли функция. А что делать, если вызовов нет?

Здесь ошибка, поскольку в аргументах не обозначено, что переменная a включает в себя переменную x

И опять, это означает, что вы не выводите тип параметра по употреблению (хотя это возможно), а на этот раз требуете этой аннотации от программиста (и чем это отличается от явной типизации?).

Если было бы обозначено, и функция возвращала значения разных типов(типы переменных x и y),

… а как вы определяете, каких типов x и y? Опять подстановкой при вызове?

Честное слово, модель Хиндли-Милнера, с выводом ограничений, выглядит продуктивнее.

Lex20 3 сен 2016 в 15:05

А что делать, если вызовов нет?

В этом случае функция не нужна.

И опять, это означает, что вы не выводите тип параметра по употреблению (хотя это возможно), а на этот раз требуете этой аннотации от программиста (и чем это отличается от явной типизации?).

Предполагалось задавать порядок следования элементов в структуре, хотя может вы и правы.

… а как вы определяете, каких типов x и y? Опять подстановкой при вызове?

Их типы задаются при первой инициализации структуры.

lair 3 сен 2016 в 16:18

В этом случае функция не нужна.

Ну то есть никаких компонентов для повторного использования. Вы это серьезно?

Предполагалось задавать порядок следования элементов в структуре

Кого он вообще волнует в рамках системы типов?

Их типы задаются при первой инициализации структуры.

… а структура инициализируется снаружи, что опять означает подстановку.

humbug 3 сен 2016 в 19:16

Функция main нигде в программе не вызывается, значит её можно удалить. Затем можно удалить все остальные функции, которые вызывались только из main, затем и взаимно рекурсивные функции, которые не вызываются снаружи. То есть совершенно всё.

lair 3 сен 2016 в 19:18

Кстати, да, как же делать "вывод" типов по использованию для входящих данных?

Lex20 4 сен 2016 в 10:19

Их не нужно выводить, они уже известны.

lair 4 сен 2016 в 10:21

Это откуда же?

Lex20 4 сен 2016 в 10:18

С main начинается вывод типов, дальше рекурсия по вызовам.

lair 4 сен 2016 в 10:31

А если в прикладном коде нет main? (любой код под внешним фреймворком, будь то тесты, веб-приложение, сервис (который на запросы отвечает) и так далее)

lair 3 сен 2016 в 14:53

Если для таких a и b определён оператор >

Эээ, стоп. Что значит "для x определен оператор y"?

Lex20 3 сен 2016 в 15:06

Предусмотрено сравнение числа и строки.

lair 3 сен 2016 в 16:16

"Предусмотрено" кем?

Смотрите, концептуально нет никакой разницы между оператором и функцией; оператор — это частный случай функции. В функциях вы типы входящих значений не знаете, а просто подставляете то, что пришло снаружи, и проверяте, сходится ли. Но ваша сходимость, в итоге, основана на тех же функциях, просто на уровень ниже. Как вы будете решать эту рекурсивную проблему?

Lex20 3 сен 2016 в 17:38

Задам операторы для стандартных типов.

lair 3 сен 2016 в 17:49

Указав типы, не так ли?

Lex20 3 сен 2016 в 18:59

Не вижу проблемы.

lair 3 сен 2016 в 19:17

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

НЛО прилетело и опубликовало эту надпись здесь

lair 4 сен 2016 в 13:59

Мне он доказывал прямо противоположное.

Оу, правда? И где же?

impwx 2 сен 2016 в 11:50

Из этих соображений был сделан вывод, что отказаться от типов-хорошая идея.

А как теперь быть с перегруженными функциями, которые по-разному обрабатывают аргументы разных типов?

При полном удалении типов только выигрывает в читаемости:

Не выигрывает. Теперь, чтобы определить, что можно передать в функцию, придется попотеть. Из вашего же примера, что именно принимает qsort в качестве значения для аргумента compare? Какой объем кода придется проанализировать человеку \ среде разработки, чтобы это определить?

claygod 2 сен 2016 в 12:24

На основании всего написанного я, автор статьи, пишу язык программирования

Сейчас уже столько языков существует… может Вам присоединиться к какому-нибудь
сообществу языка программирования, наиболее близкого по духу?

NeoCode 2 сен 2016 в 18:01

Как бы то ни было, но я всегда уважаю разработчиков собственных языков программирования. Можно конечно и присоединиться, но и своя собственная разработка это очень хорошо. Может потом наоборот к автору присоединятся:)

NeoCode 2 сен 2016 в 12:24

Мне не нравится динамическая типизация и идея отказаться от типов. Вот в динамической типизации обычно можно написать такое

x = 10;
if(condition)
  x = "Alexey";

Но скажите — кому может понадобиться на ходу менять тип переменной с числа на строку? Если х — число, то оно скорее всего используется в математике, возможно как счетчик цикла или индекс. Если х — строка, то это работа с текстом, строковые алгоритмы, может быть имена файлов и т.д.
И это только простые типы. А если х — навороченная структура?
Поэтому когда я в коде вижу

foo(x,y,z) { }

то что я должен ожидать от x, y и z? Какие действия я имею право с ними совершать?
А если написано

foo(int x, string y, File z) { }

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

Lex20 2 сен 2016 в 17:36

Если функция foo работает только с такими аргументами, то

foo(int_x, string_y, file_z) { }

NeoCode 2 сен 2016 в 18:00

А это костыль вместо естественного механизма типов (как и всякие специальные комментарии для php). В сложном коде ничто не помешает программисту случайно сохранить где-нибудь значение не того типа, которое в конечном итоге будет передано в эту функцию, и все сломает.
Прелесть статической типизации именно в ее декларативности, в том что ошибки выявляются не во время выполнения (если ветвь кода редко выполняется, то ошибка может не проявляться годами), а во время компиляции, где программа — просто дерево, и компилятор гарантированно пройдет по каждой ветке этого дерева.

НЛО прилетело и опубликовало эту надпись здесь

lair 3 сен 2016 в 16:21

Как ни странно, если у вас заранее неизвестен ответ, вы не можете утверждать, что он будет типа int, long или double long или ещё длиннее, то языки типа С++ вам не подойдут, придётся использовать язык с динамической компоновкой.

Зачем? Достаточно иметь числовой тип данных с произвольной точностью.

Слово в словаре может иметь какую максимальную длину?

Определенную требованиями, очевидно.

Большинство обычных задач с базами данных требует вычислений типов, и динамических языков.

Зачем для работы с БД динамически типизованный язык? Я вот прекрасно работаю с БД из статически типизованных языков (да и пишут БД регулярно на статически типизованных языках).

НЛО прилетело и опубликовало эту надпись здесь

lair 3 сен 2016 в 18:09

сколько характеристик товара в базе

Столько, сколько указано в требованиях. Если требования говорят, что атрибуты должны меняться без модификации таблиц, то строим EAV или аналоги.

есть в базе ли картинки и какого они размера?

Если по требованиям нужны, то есть. Размер тоже определен требованиями.

НЛО прилетело и опубликовало эту надпись здесь

lair 3 сен 2016 в 20:31

Для носков характеристики имеют другой тип, чем для характеристик смартфонов

Правда? Я думаю, что все характеристики носков сводимы к четыре типам — строке, перечислению, числу и ссылке. У смартфонов приблизительно то же самое. Добавите структурные типы — вообще все покроется.

Ну если у вас есть терабайт ОЗУ.

Зачем же?

И кстати, как вы запишите число ПИ в числовом типе данных с произвольной точностью?

Так, как нужно для решения задачи.

НЛО прилетело и опубликовало эту надпись здесь

lair 3 сен 2016 в 22:47

ага, значит таки типы разные у характеристик носков и смартфонов.

Разные, конечно. Вообще, в статически типизированных языках типы разные (иначе нет смысла в статической типизации). И что?

будет заполнен в основном нулями, при использовании реляционных баз с полями постоянной длины.

Оу, а откуда взялись поля постоянной длины?

А иначе у вас будет быстродействие низкое, заказчик будет недоволен.

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

Что характерно, ни один из ваших вопросов не содержит ответа на мое "зачем для работы с БД динамически типизованный язык?". Более того, все описанные ответы равноприменимы для статически и динамически типизированных языков.

НЛО прилетело и опубликовало эту надпись здесь

lair 4 сен 2016 в 10:09

Ну да, в обиженную позу-то легче встать, чем свои слова обосновывать.

playermet 3 сен 2016 в 17:17

> А если написано
Неправильный пример. Ответом на
«foo(x,y,z) {}»
является
«foo(type1 x, type2 y, type3 z) {}»
И как видно это не очень помогло, нам все равно нужно совершать дополнительные действия. Если бы у переменных были нормальные имена, было бы намного проще.

NeoCode 3 сен 2016 в 20:33

Пусть даже такой пример. Но если я в теле функции напишу

x = y + z

а это невозможно, потому что не существует понятия сложения для типов type2 и type3, ошибка возникнет сразу же, на этапе компиляции, а не неизвестно когда на этапе выполнения в продакшене.

playermet 3 сен 2016 в 22:07

Пример о котором мы сейчас говорим, это не столько динамическая/статическая, сколько явная/неявная типизация. На самом деле, ничто не мешает создать инструмент, выводящий и проверяющий типы статически, до выполнения. Проблемы возникнут только в случаях, где переменная получает значение из «черного ящика».

NeoCode 4 сен 2016 в 10:00

Ну так вот, все такие случаи когда переменная получает значение из «черного ящика», лучше бы обозначить в коде явно, с помощью специального динамического типа any (в чем-то по аналогии с ключевым словом unsafe, существующим в некоторых языках для ограждения небезопасного кода).
Против неявной типизации и вывода типов я ничего не имею — поскольку тип выводится на этапе компиляции, потенциальные ошибки также выведутся на этапе компиляции.
PS. интересно, если в языке есть и тип «any», и вывод типов, который в сложных случаях вполне может вывести «any» и ничего не сказать программисту… но это уже тонкости реализации компилятора. Как минимум warning я бы на такой случай давал.

playermet 12 сен 2016 в 14:41

> лучше бы обозначить в коде явно, с помощью специального динамического типа any
Если бы я делал язык, я бы обошел это по другому. Что-то вроде конструкции похожей на switch, но для типов, с обязательной other/default секцией. Пока тип переменной неизвестен, она не может участвовать нигде кроме как в этой конструкции, а дальше на все предусмотренные варианты есть гарантированная логика с наверняка известными типами.

P.S. Все хочу запилить статический анализатор типов для Lua, но никак не соберусь.

Eivind 2 сен 2016 в 14:06

Минусы: больший объём памяти, необходимый для выполнения.

А теперь я предлагаю вам подтвердить своё утверждение результатами тестов, где ваш сравниваемый код на javascript требует для выполнения меньше памяти.

Dark_Daiver 2 сен 2016 в 18:26

А что мешает просто воткнуть auto в С++ коде везде где это возможно? И не нужно писать велосипеды.

Lex20 2 сен 2016 в 20:21

auto можно вообще не писать, об этом статья.

Antervis 5 сен 2016 в 06:17

нет. Синтаксис объявления переменной отличается от синтаксиса её использования. Вдруг я хотел не объявить локальную переменную, а воспользоваться экспортированной из либы?

НЛО прилетело и опубликовало эту надпись здесь

Antervis 5 сен 2016 в 06:22

статическая типизиация позволяет сэкономить примерно вдвое, т.к. не надо проверять тип на каждом шаге использования переменной. Ничто в принципе не мешает написать оболочку над variant/any и пользоваться той же самой динамической типизацией. Просто от введения её туда, где не надо, проиграет только код.

fynivx 5 сен 2016 в 14:39

Мне кажется, прежде чем пытаясь заимплементить вывод типов, нужно познакомиться с каким нибудь функциональным языком. В C++, C# и иже с ними, даже в современном виде, вывод типов очень скуден. Я бы посоветовал посмотреть на Haskell. По сравнению с указанными выше языками он просто чудеса творит в смысле вывода типов.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий