Есть ли у Scala ограничение по стоимости, например, ML, если нет, то почему?

Question

Вот мои мысли по этому вопросу. Кто-нибудь может подтвердить, опровергнуть или уточнить?

Я написал:

Скала не объединяет ковариант List[A] с GLB ⊤, назначенным на List[Int], bcz afaics в подтипе "biunification" направление задания имеет значение. таким образом None должен иметь тип Option[⊥] (т.е. Option[Nothing]), то же самое Nil тип List[Nothing] который не может принять назначение от Option[Int] или же List[Int] соответственно. Таким образом, проблема ограничения ценностей возникает из-за бесцельного объединения, и глобальное объединение считалось неразрешимым до недавнего исследования, связанного выше.

Вы можете просмотреть контекст вышеупомянутого комментария.

Ограничение значения ML будет запрещать параметрический полиморфизм в ( ранее считавшихся редким, но, возможно, более распространенным) случаях, когда это было бы в противном случае целесообразно (т. Е. Безопасно для типов), например, особенно для частичного применения каррированных функций (что важно в функциональном программировании), потому что решения альтернативной типизации создают стратификацию между функциональным и императивным программированием, а также нарушают инкапсуляцию модульных абстрактных типов. У Haskell есть аналогичное двойственное ограничение мономорфизации. OCaml имеет ослабление ограничения в некоторых случаях. Я подробно остановился на некоторых из этих деталей.

РЕДАКТИРОВАТЬ: моя первоначальная интуиция, как выражено в приведенной выше цитате (что ограничение значения может быть устранено путем подтипирования) неверна. Ответы IMO хорошо объясняют проблему (и), и я не могу решить, какой из набора, содержащего слова Алексея, Андреаса или моего, должен быть лучшим ответом. ИМО они все достойны.

Answer 1

Как я объяснял ранее, необходимость ограничения значения - или чего-то подобного - возникает, когда вы комбинируете параметрический полиморфизм с изменяемыми ссылками (или некоторыми другими эффектами). Это полностью независимо от того, имеет ли язык вывод типа или нет, или язык также допускает подтипы или нет. Канонический контрпример

let r : ∀A.Ref(List(A)) = ref [] in
r := ["boo"];
head(!r) + 1

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

Следовательно, когда вы добавляете ссылки на F<: тогда вам нужно наложить ограничение значения, чтобы не потерять правильность. Аналогично, MLsub не может избавиться от ограничения стоимости. Scala уже применяет ограничение значения через свой синтаксис, поскольку нет способа даже написать определение значения, которое бы имело полиморфный тип.

Answer 2

Это намного проще, чем это. В Scala значения не могут иметь полиморфные типы, только методы могут. Например, если вы пишете

val id = x => x

его тип не [A] A => A,

И если вы берете полиморфный метод, например,

 def id[A](x: A): A = x

и попытаться присвоить его значению

 val id1 = id

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

Так что проблема не возникает.

РЕДАКТИРОВАТЬ:

Если вы попытаетесь воспроизвести пример http://mlton.org/ValueRestriction в Scala, проблема, с которой вы столкнетесь, заключается не в отсутствии let: val соответствует ему на отлично. Но вам нужно что-то вроде

val f[A]: A => A = {
  var r: Option[A] = None
  { x => ... }
}

что незаконно. Если ты пишешь def f[A]: A => A = ... это законно, но создает новый r на каждый звонок. В терминах ОД это было бы как

val f: unit -> ('a -> 'a) =
    fn () =>
       let
          val r: 'a option ref = ref NONE
       in
          fn x =>
          let
             val y = !r
             val () = r := SOME x
          in
             case y of
                NONE => x
              | SOME y => y
          end
       end

val _ = f () 13
val _ = f () "foo"

что допускается ограничением значения.

То есть правила Scala эквивалентны разрешению только лямбда-выражений в качестве полиморфных значений в ML вместо всего, что позволяет ограничение значений.

Answer 3

РЕДАКТИРОВАТЬ: этот ответ был неверным раньше. Я полностью переписал приведенное ниже объяснение, чтобы получить мое новое понимание из комментариев под ответами Андреаса и Алексея.

_{История редактирования и история архивов этой страницы на сайте archive.is содержит запись моего предшествующего недопонимания и обсуждения. Еще одна причина, по которой я решил отредактировать, а не удалить и написать новый ответ, - сохранить комментарии к этому ответу. ИМО, этот ответ по-прежнему необходим, потому что, хотя Алексей и правильно и кратко отвечает на заголовок темы - разработка Андреаса была для меня наиболее полезной для понимания - тем не менее, я думаю, что читателю-неспециалисту может потребоваться другой, более целостный (хотя, надеюсь, еще генеративная сущность) объяснение, чтобы быстро обрести некоторую глубину понимания вопроса. Также я думаю, что другие ответы не позволяют понять, насколько запутанным является целостное объяснение, и я хочу, чтобы наивные читатели имели возможность попробовать его. Предыдущие разъяснения, которые я обнаружил, не излагают все детали на английском языке и вместо этого (как математики склонны делать для эффективности) полагаются на читателя, чтобы отличить детали от нюансов примеров символического языка программирования и знания предметной области (например, общие сведения о дизайне языка программирования).}

---

Ограничение значения возникает, когда мы имеем мутацию параметризованных объектов ^1-го типа ². Тип небезопасности, который возникнет без ограничения значения, продемонстрирован в следующем примере кода MLton:

val r: 'a option ref = ref NONE
val r1: string option ref = r
val r2: int option ref = r
val () = r1 := SOME "foo"
val v: int = valOf (!r2)

NONE значение (которое сродни null) содержится в объекте, на который ссылается r можно присвоить ссылку с любым конкретным типом для параметра типа 'a так как r имеет полиморфный тип a', Это допускает небезопасность типа, потому что, как показано в примере выше, тот же объект, на который ссылается r который был назначен обоим string option ref а также int option ref может быть написано (то есть видоизменено) с string значение через r1 ссылка, а затем читать как int значение через r2 ссылка. Ограничение значения генерирует ошибку компилятора для приведенного выше примера.

Сложность типизации возникает, чтобы предотвратить ³ (повторное) количественное определение (то есть связывание или определение) параметра типа (иначе называемой переменной типа) упомянутой ссылки (и объекта, на который она указывает) на тип, который отличается при повторном использовании экземпляра упомянутая ссылка, которая была предварительно определена количественно с другим типом.

Такие (возможно, сбивающие с толку и запутанные) случаи возникают, например, когда последовательные приложения функций (или вызовы) повторно используют один и тот же экземпляр такой ссылки. IOW, случаи, когда параметры типа (относящиеся к объекту) для ссылки (ре) количественно оцениваются при каждом применении функции, но один и тот же экземпляр ссылки (и объект, на который она указывает) повторно используется для каждого последующего приложения (и количественная оценка) функции.

Тангенциально, их возникновение иногда не является интуитивно понятным из-за отсутствия явного универсального квантификатора the (поскольку неявное количественное определение лексической области преды ранга 1 можно сместить из порядка лексической оценки с помощью таких конструкций, как let или сопрограмм) и, возможно, более существенную нерегулярность (по сравнению со Scala) случаев, когда могут возникать небезопасные случаи в ограничении стоимости ML:

Андреас написал:

К сожалению, ML обычно не делает квантификаторы явными в своем синтаксисе, а только в правилах их набора.

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

Ограничение значения является компромиссом ML для предотвращения всех небезопасных случаев, в то же время предотвращая некоторые ( ранее считавшиеся редкими) безопасные случаи, чтобы упростить систему типов. Ограничение значения считается лучшим компромиссом, потому что ранний ( устаревший?) Опыт использования более сложных подходов к типизации, которые не ограничивали ни одного или столько же безопасных случаев, вызвал раздвоение между императивным и чисто функциональным (иначе аппликативным) программированием и утек инкапсуляции абстрактных типов в модулях ML-функторов. Я привел некоторые источники и подробно изложил здесь. Тангенциально, тем не менее, я размышляю, действительно ли ранний аргумент против бифуркации противостоит тому факту, что ограничение значения вообще не требуется для вызова по имени (например, ленивая оценка Haskell-esque, когда также запоминается по необходимости), потому что концептуально частичный приложения не формируют замыкания в уже оцененном состоянии; и вызов по имени требуется для модульного композиционного мышления и в сочетании с чистотой, а затем модульного ( теория категорий и эквациональное мышление) управления и композиции эффектов. Аргумент ограничения мономорфизации для вызова по имени на самом деле связан с принудительным введением аннотаций типов, однако явное указание, когда требуется оптимальное запоминание (иначе говоря, совместное использование), возможно, менее обременительно, учитывая, что указанные аннотации необходимы для модульности и удобочитаемости в любом случае. Call-by-value - это уровень контроля тонкой зубной щетки, поэтому, когда нам нужен этот контроль низкого уровня, тогда, возможно, мы должны принять ограничение значения, потому что редкие случаи, которые допускает более сложная типизация, были бы менее полезными в сравнении с императивом аппликативная настройка. Тем не менее, я не знаю, могут ли эти два слоя быть разделены / разделены на одном и том же языке программирования гладким / элегантным образом. Алгебраические эффекты могут быть реализованы на языке CBV, таком как ML, и они могут устранить ограничение значения. Итак, если на ваш код накладывается ограничение значения, возможно, это потому, что у вашего языка программирования и библиотек нет подходящей метамодели для обработки эффектов.

Scala накладывает синтаксическое ограничение на все такие ссылки, что является компромиссом, который ограничивает, например, те же и даже больше случаев (которые были бы безопасны, если не ограничены), чем ограничение значения ML, но является более регулярным в том смысле, что мы не будем почесать голову о сообщении об ошибке, относящемся к ограничению значения. В Scala нам никогда не разрешается создавать такую ​​ссылку. Таким образом, в Scala мы можем выражать только случаи, когда создается новый экземпляр ссылки, когда его параметры типа определены количественно. Обратите внимание, что в некоторых случаях OCaml ослабляет ограничение значения.

Обратите внимание, что как Scala, так и ML не позволяют объявить, что ссылка неизменна ¹, хотя объект, на который они указывают, может быть объявлен неизменным val, Обратите внимание, что нет необходимости в ограничении ссылок, которые не могут быть изменены.

Причина, по которой изменчивость ссылочного типа ¹ требуется для возникновения сложных случаев типизации, заключается в том, что если мы создаем экземпляр ссылки (например, в, например, предложении подстановок let) с непараметрическим объектом (т.е. не None или же Nil ⁴ но вместо этого, например, Option[String] или же List[Int]), тогда ссылка не будет иметь полиморфного типа (относящегося к объекту, на который она указывает), и, таким образом, проблема повторного определения никогда не возникает. Таким образом, проблемные случаи связаны с созданием экземпляра с полиморфным объектом и последующим назначением вновь квантифицированного объекта (т. Е. Мутирование ссылочного типа) в повторно квантифицированном контексте с последующей разыменовкой (чтением) из ссылки (на объект, на которую указывает) в последующей пересчитанный контекст. Как упомянуто выше, когда повторно определяемые параметры типа конфликтуют, возникает сложность при наборе, и небезопасные случаи должны быть предотвращены / ограничены.

Уф! Если вы поняли это без рассмотрения связанных примеров, я впечатлен.

---

¹ _{ИМО вместо использования фразы "изменяемые ссылки" вместо "изменчивость ссылочного объекта" и "изменчивость ссылочного типа" может привести к путанице, поскольку наше намерение состоит в том, чтобы изменить значение объекта (и его тип), которое на который ссылается указатель - не ссылаясь на изменчивость указателя того, на что указывает ссылка. Некоторые языки программирования даже явно не различают, когда они запрещают в случае примитивных типов выбирать мутацию ссылки или объекта, на который они указывают.}

² _{При этом объект может даже быть функцией на языке программирования, который допускает первоклассные функции.}

³ _{Чтобы предотвратить ошибку сегментации во время выполнения из-за доступа (чтения или записи) к ссылочному объекту с предположением о его статически (то есть во время компиляции) определяемом типе, который не является типом, который фактически имеет объект.}

⁴ _Какие NONE _{а также} [] _{соответственно в ОД.}