Как строятся типы в Си

[vak]

Простой ли язык Си? Я покажу вам как в нём строятся типы, и вы сами решите. (Подсказка: непростой.)

Я задумал некий сложный тип. Будем строить его по шагам. Что он по большому счёту представляет? Указатель. Ставим звёздочку.

*

На что указывает наш указатель? На массив. Ставим круглые скобки вокруг звёздочки и дописываем квадратные скобки справа.

(*)[]

Сколько элементов в массиве? Пять. Ставим пятёрку внутри квадратных скобок.

(*)[5]

Что находится в каждом элементе массива? Указатель. Добавляем звёздочку слева.

*(*)[5]

На что указывает этот указатель? На функцию. Какие аргументы принимает функция? Один аргумент типа char. Заворачиваем нашу конструкцию в круглые скобки и справа в круглых скобках добавляем аргументы.

(*(*)[5])(char)

Что возвращает функция? Тип int. Дописываем слева.

int (*(*)[5])(char)

Таким образом, мы имеем указатель на массив из пяти указателей на функции, принимающие char и возвращающие int. Не пытайтесь повторить на трезвую голову. 😀

А чтобы совсем весело стало, добавим внутрь слово static.

int (*(*)[static 5])(char)

Получили указатель на массив из не менее чем пяти указателей на функции, принимающие char и возвращающие int.

Comments

[juan_gandhi]

Вот этот пример - вечный вопрос на засыпку на интервью.

А ещё добавить звёздочку, если функция возвращает указатель на int.

[vak]

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

[juan_gandhi]

Это ж было до грока, до гугла, до интернета, и чуть ли не до фидо. Писали код на бумажке, ответы на загадки искали в книжке (KR).

[vak]

Помню то время. Тогда и формальная грамматика Си в виде YACC не была доcтупна.

[x86128]

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

[ircicq]

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

[malyj_gorgan]

> ... кандидат имел дело с Си поглубже уровня учебников,...
Залежить від того, на що це кандидат. Можна було писати дофіга всього обчислювального і навіть десь в чомусь нетривіального, але ніколи далі простих скалярів і тензорів не далі 3-4 порядку не рухатися.
Для наукових чиінжерених обчислень Сі зручний в першу чергу динамічною алокацією-деалокацією памʼяті і парочкою додаткових фіч, завʼязаних на поінтери. (Дисклеймер: злі язики кажуть, що фортран 90 то всьо теж має. Не знаю, не пробував)

[juan_gandhi]

Слава те господи, последний раз мне подсовывали си в 1999-м году. Я не возражал тогда писать на си, но они меня пытались взять на понт, мол, ты годик кюеем поработаешь, а потом уже это. И так далее, всякая туфта.

[chaource]

Когда я изучалъ С, то я выучилъ, какъ пишутся и читаются всѣ эти типы указателей на функцiи изъ указателей. Справа налѣво, снизу вверхъ. Я умѣлъ это дѣлать. И быстро забылъ. Но сейчасъ я знаю, что это было ошибочно, и языкъ системы типовъ можно было сдѣлать простымъ, и это было извѣстно (правда, лишь въ кругахъ академическихъ ученыхъ) уже въ 1975 году. См. мой комментарiй ниже.

[chaource]

А вотъ какъ это работаетъ въ современныхъ языкахъ.

"Указатель на массивъ изъ указателей на функцiи, принимающiя char и возвращающiя int."

"Указатели" мы вообще не пишемъ, потому что всѣ типы являются указателями по умолчанiю. Компиляторъ самъ найдетъ, когда можно написать просто int вмѣсто указателя на int.

(Указатель на int и просто int - это одно и то же, потому что вѣдь всѣ значенiя являются константами и ихъ нельзя модифицировать на мѣстѣ.)

Итакъ, намъ нуженъ "массивъ функцiй изъ char въ int". Просто записываемъ эту фразу:

Array [Char => Int]   // Scala. Alias for: Array[Function1[Char, Int]]

Array Int (Char -> Int)   -- Haskell, needs an additional `Int` as the index type.

(char -> int) array   (* OCaml *)

И все. Читается и пишется легко. Благодаря такому синтаксису, можно и гораздо болѣе сложные типы опредѣлять и использовать безъ существенныхъ проблемъ. Никакихъ звѣздочекъ и скобокъ безъ конца, никакихъ этихъ "*(*(*)[*(*)])", которые всѣхъ совершенно запутываютъ и дѣлаютъ кодъ нечитаемымъ.

Если мы все-таки хотимъ явно выписать указатели (скажемъ, если мы пишемъ библiотеку для работы съ устарѣвшими языками, такими, какъ B или C), то мы дѣлаемъ конструкторъ Pointer и пишемъ:

Pointer[Array[Pointer[Char => Int]]]        // Scala

Pointer (Array Int (Pointer (Char -> Int)))     -- Haskell

Немного сложнѣе, но все равно читаемо.

Теперь, если мы хотимъ указать минимальную длину массива, это отдѣльная задача. Обычно это рѣшается съ помощью рафинированныхъ типовъ ("refinement types"). На Скалѣ это выглядитъ такъ (библiотека refined https://github.com/fthomas/refined )

Validate[Array[Char => Int], MinSize[W.`5`.T]]

На Хаскелѣ тоже есть полностью аналогичная библiотека refinement types, но я недостаточно съ этимъ пока знакомъ, чтобы такъ навскидку написать примѣръ использованiя. (Спрашивать объ этомъ ИИ - зашкваръ.)


И можно задавать любыя дополнительныя условiя на длину массива. Скажемъ, что длина массива отъ 5 до 10 элементовъ, или что массивъ всегда нечетной длины - нѣтъ проблемъ.

Идея, что типы должны быть написаны на понятномъ человѣку языкѣ, такъ что типы любой сложности будетъ можно достаточно легко читать и писать, была реализована уже въ 1983 году въ языкѣ Standard ML, изъ основныхъ идей котораго и произошли сегодняшнiе языки OCaml, Haskell, Scala.

https://smlfamily.github.io/history/SML-proposal-11-83.pdf

А первыя идеи, приведшiя къ этому языку, были еще въ 1975 году открыты.

https://dl.acm.org/doi/10.1145/3386336

Языкъ СAml, изъ котораго вышелъ сегодняшнiй OCaml (продолжающiй ту же традицiю строго типизированныхъ языковъ съ полнымъ выводомъ общихъ типовъ и доказанной непротиворѣчивостью семантики типовъ):

https://web.archive.org/web/20220120003835/https://caml.inria.fr/about/history.en.html

[vlad_m]

Забавно, что я именно так (рекурсивно-пошагово) сам себе объяснил (и пытался объяснять другим) устройство сложных типов.
В суслике (golang) операции с типом Type "объясняют" то же самое, только сверху-вниз.

А конструкция типа static 5 это что то новое в сишной грамматике?

[vak]

Ну как новое. Больше четверти века прошло: C99.

https://en.cppreference.com/w/c/language/array

[vlad_m]

О как!
Отстал от прогресса.

Попытался сходу придумать, зачем бы это мне пригодилось. Сходу не вышло.
Но, как я понимаю, реализация в компиляторе несложна. Просто ещё один параметр (или флажок) в аст-дереве в объекте array.

[vak]

Я тоже не знал про эту фичу, пока не столкнулся при написании самодельного парсера. Ни в каких сишных исходниках не попадалось. Там и другие странности есть. Можно написать:

void func(int arr[const volatile restrict]);

Зачем - не понимаю.

[vlad_m]

Кмк, это какой-то backdraft от гиперактивности C++ комитетов.
Incorporate into C what was invented for C++.