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

в 8:31, , рубрики: C, c++, javascript, Алгоритмы, вывод типов, Программирование, метки:

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

Надуманный пример на C++:

#include <iostream>
#include <string.h>
using namespace std;

void a(int x)
{
    cout<<"numbern";
}

void a(float x)
{
    cout<<"numbern";
}

void a(const char *x)
{
    cout<<"stringn";
}

template <typename T>
void f(void(*g)(T x), T x)
{
    g(x);
}

int main()
{
    f(a, 1);
    f(a, 1.0f);
    f(a, "Alexey");

    return 0;
}

Тот же код на Javascript:

function f(g, x)
{
    g(x)
}

function a(x)
{
    alert(typeof x)
}

f(a, 1)
f(a, 1.0)
f(a, 'Alexey')

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

Динамический подход

В javascript у каждой переменной есть свойство «тип», который возвращается при действии оператора typeof на переменную. Это свойство хранится во время выполнения программы, всегда, когда существует переменная. И когда к переменной применяется какой-то оператор, функция, реализующая этот оператор, проверяет тип переменной. В соответствии с типом выполняются какие-то действия. Например 2+2 вернёт 4, 2+'Alexey' вернёт '2Alexey'. Т.е. операторы языка обязаны почти всегда проверять типы переменных, к которым они применяются. Назовём данный подход «динамической типизацией».

Минусы этого подхода достаточно очевидны, точнее один минус-необходимо делать дополнительные вычисления во время выполнения программы.

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

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

Статический подход

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

Полиморфизм функций позволяет назвать 2 функции, делающие одно и то же но с разными типами данных, одинаковыми именами.

Шаблоны вводят новый тип-общий для всех типов. Хороши эти механизмы тем, что с их помощью, без участия программиста, производится подстановка функций с нужными типами. Т.е. если шаблон одной функции задействует 2 разных типа, то во время компиляции будут созданы 2 разные функции. При вызове исходной функции в коде будет подставляться в скомпилированный файл вызов скопированной функции нужного типа.

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

Вывод типов

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

Например, код быстрой сортировки:

#include <iostream>
#include <string.h>
using namespace std;

template<class T>
void qsort(T** array, int length, int compare(T *a, T *b))
{
    int  left  = 0;
    int  right = length-1;
    T   *middle_element;

    middle_element=array[length/2];

    do
    {
        while( compare(array[left], middle_element)<0 )
            left++;

        while( compare(array[right], middle_element)>0 )
            right--;

        if(left<=right)
        {
            swap(array[left], array[right]);

            left++;
            right--;
        }
    }
    while(left<=right);

    if(right>0)
        qsort(array, right, compare);

    if(left<length)
        qsort(array+left, length-left, compare);
}

int cmp(char *a, char *b)
{
    return strcmp(a, b);
}

int main()
{
    char *strings[]={"Alexey", "Borisenko"};

    qsort(strings, 2, cmp);

    return 0;
}

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

#include <iostream>
#include <string.h>
using namespace std;


qsort(array, length, compare)
{
    left           = 0;
    right          = length-1;
    middle_element = array[length/2];

    do
    {
        while( compare(array[left], middle_element)<0 )
            left++;

        while( compare(array[right], middle_element)>0 )
            right--;

        if(left<=right)
        {
            swap(array[left], array[right]);

            left++;
            right--;
        }
    }
    while(left<=right);

    if(right>0)
        qsort(array, right, compare);

    if(left<length)
        qsort(array+left, length-left, compare);
}

cmp(a, b)
{
    return strcmp(a, b);
}

main()
{
    strings={"Alexey", "Borisenko"};
    qsort(strings, 2, cmp);

    return 0;
}

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

Выделим 3 основных типа:

1) Простой
2) Составной
3) Функция

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

Итак, вывод типа производится при следующих операциях:

1) Присваивание
2) Вызов функции

При выводе типа переменная не может поменять тип. Доказательтво от противного:

f(a)
{
    x=1

    if(a<2)
    	x='Alexey'

    return x
}

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

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

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

Таким образом при присваивании значения переменной проверяется совпадение типа переменной с выведенным типом выражения. Это уже позволяет выводить типы для кода, у которого нет вызова функции, принимающей на вход другую функцию. Если есть такой вызов, то придётся выяснять, какую функцию подставлять в качестве аргумента.

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

Простой, очевидно, включается в остальные. Составной выводится присваиванием:

x={name:"Alexey"}

А также через описание типа в аргументах функции с указанием всех используемых в этом типе переменных:

f(user {name})
{
}

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

Концовка

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

Автор: Lex20

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js