Extending Hindley-Milner to type mutable referencesType inference for imperative statements other than assignmentNested automatization of type inference of forall eliminationHow are imperative languages more different from each other than functional languages?Type inference for imperative statements other than assignmentOccurs check in type inferencePractical implementation of Hindley–Milner with typeclasses — matching vs most general unifierIs this behavior in a programming language inconsistent?Can type inference be classified in two groups: unification-based and control-flow-based?Decidability of parametric higher-order type unificationHigher-rank polymorphism over unboxed typesLanguage/type system closest to Haskell without general recursion
Is it necessary to use pronouns with the verb "essere"?
Why is so much work done on numerical verification of the Riemann Hypothesis?
Which Article Helped Get Rid of Technobabble in RPGs?
The IT department bottlenecks progress, how should I handle this?
Is this part of the description of the Archfey warlock's Misty Escape feature redundant?
What kind of floor tile is this?
Did the UK lift the requirement for registering SIM cards?
Pre-mixing cryogenic fuels and using only one fuel tank
How can I write humor as character trait?
What fields between the rationals and the reals allow a good notion of 2D distance?
Why can't the Brexit deadlock in the UK parliament be solved with a plurality vote?
What is the difference between lands and mana?
Is there a RAID 0 Equivalent for RAM?
Why is it that I can sometimes guess the next note?
Why should universal income be universal?
Has any country ever had 2 former presidents in jail simultaneously?
What to do when eye contact makes your coworker uncomfortable?
Permission on Database
How do I tell my boss that I'm quitting soon, especially given that a colleague just left this week
I found an audio circuit and I built it just fine, but I find it a bit too quiet. How do I amplify the output so that it is a bit louder?
15% tax on $7.5k earnings. Is that right?
Why Shazam when there is already Superman?
Can I turn my anal-retentiveness into a career?
A variation to the phrase "hanging over my shoulders"
Extending Hindley-Milner to type mutable references
Type inference for imperative statements other than assignmentNested automatization of type inference of forall eliminationHow are imperative languages more different from each other than functional languages?Type inference for imperative statements other than assignmentOccurs check in type inferencePractical implementation of Hindley–Milner with typeclasses — matching vs most general unifierIs this behavior in a programming language inconsistent?Can type inference be classified in two groups: unification-based and control-flow-based?Decidability of parametric higher-order type unificationHigher-rank polymorphism over unboxed typesLanguage/type system closest to Haskell without general recursion
$begingroup$
I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let
is used to declare a variable as opposed to a bare assignment.
However, I'm now trying to add mutability into the language, specifically in the syntactical form
let mut x = 1
where x
is now a rebindable variable. This is effectively the same as
let x = ref 1 in ...
in ML, but my type-checker inserts the dereference operator (!
) automatically. So something like ref
is never directly used. Any instance of x
has a !
applied to it. So, if you do
let mut x = 1
let y = x
x = 2
Then x
is still rebindable, and has the value of 2
, but y
is immutable and has the value 1
.
I am having great difficulty extending my implementation of Hindley-Milner 's unification to support mutable references. The main paper I was reading was Standard ML-NJ Weak Polymorphism and Imperative Constructs by John Mitchell, as I was hoping to get an inference algorithm that had similar behavior to OCaml's weak polymorphism implementation.
This paper is pretty good and explains most things well enough, but it lacks a formal description of the type inference algorithm for its language. Are there any good resources on extending Hindley-Milners unification algorithm, that is, not the type system, with mutable references. I know the two go hand in hand, but I'm just having a really hard time jumping from the type inference rules from the paper I'm using to extending my implementation. I'm wondering if there is at least a description of an algorithm that unifies types in a language that supports mutable references.
Lastly, I saw this question here asking something similar. The asker states "I only find solutions for a language with mutable references but without genuine imperative control structures", I would like to see those references! I completely understand how to extend my language to have imperative control structures once I get my mutable references working, but this is where I am stuck now.
reference-request pl.programming-languages type-theory type-inference imperative-programming
New contributor
$endgroup$
add a comment |
$begingroup$
I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let
is used to declare a variable as opposed to a bare assignment.
However, I'm now trying to add mutability into the language, specifically in the syntactical form
let mut x = 1
where x
is now a rebindable variable. This is effectively the same as
let x = ref 1 in ...
in ML, but my type-checker inserts the dereference operator (!
) automatically. So something like ref
is never directly used. Any instance of x
has a !
applied to it. So, if you do
let mut x = 1
let y = x
x = 2
Then x
is still rebindable, and has the value of 2
, but y
is immutable and has the value 1
.
I am having great difficulty extending my implementation of Hindley-Milner 's unification to support mutable references. The main paper I was reading was Standard ML-NJ Weak Polymorphism and Imperative Constructs by John Mitchell, as I was hoping to get an inference algorithm that had similar behavior to OCaml's weak polymorphism implementation.
This paper is pretty good and explains most things well enough, but it lacks a formal description of the type inference algorithm for its language. Are there any good resources on extending Hindley-Milners unification algorithm, that is, not the type system, with mutable references. I know the two go hand in hand, but I'm just having a really hard time jumping from the type inference rules from the paper I'm using to extending my implementation. I'm wondering if there is at least a description of an algorithm that unifies types in a language that supports mutable references.
Lastly, I saw this question here asking something similar. The asker states "I only find solutions for a language with mutable references but without genuine imperative control structures", I would like to see those references! I completely understand how to extend my language to have imperative control structures once I get my mutable references working, but this is where I am stuck now.
reference-request pl.programming-languages type-theory type-inference imperative-programming
New contributor
$endgroup$
$begingroup$
I'm not sure I fully understand your question. Are you asking about how to do type inference when types of variables depend on whether they occur on the LHS or RHS of an assignment? And: based on what information does your type-checker insert dereference operators automatically?
$endgroup$
– Martin Berger
yesterday
$begingroup$
BTW, there is a subtlety with automatic dereferencing on the RHS: assume you declarelet mut x = 1
and thenlet mut y = x
orlet z = x
. With auto-derefering,y
will have typeRef Int
andz
will have typeInt
, but this is not always what you want. Sometimes you wanty
to have typeRef Ref Int
, hence be an alias ofx
, orz
be of typeRef int
. How does your language handle this edge case?
$endgroup$
– Martin Berger
yesterday
$begingroup$
I edited my question to clarify about the use of mutable bindings.let mut x = 1
meansx
has typeInt
, and can be used anywhere where anInt
is accepted. Basically, ifx
was created withlet mut
, then anywhere anx
appears it is actually treated as!x
.
$endgroup$
– Enrico Borba
yesterday
add a comment |
$begingroup$
I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let
is used to declare a variable as opposed to a bare assignment.
However, I'm now trying to add mutability into the language, specifically in the syntactical form
let mut x = 1
where x
is now a rebindable variable. This is effectively the same as
let x = ref 1 in ...
in ML, but my type-checker inserts the dereference operator (!
) automatically. So something like ref
is never directly used. Any instance of x
has a !
applied to it. So, if you do
let mut x = 1
let y = x
x = 2
Then x
is still rebindable, and has the value of 2
, but y
is immutable and has the value 1
.
I am having great difficulty extending my implementation of Hindley-Milner 's unification to support mutable references. The main paper I was reading was Standard ML-NJ Weak Polymorphism and Imperative Constructs by John Mitchell, as I was hoping to get an inference algorithm that had similar behavior to OCaml's weak polymorphism implementation.
This paper is pretty good and explains most things well enough, but it lacks a formal description of the type inference algorithm for its language. Are there any good resources on extending Hindley-Milners unification algorithm, that is, not the type system, with mutable references. I know the two go hand in hand, but I'm just having a really hard time jumping from the type inference rules from the paper I'm using to extending my implementation. I'm wondering if there is at least a description of an algorithm that unifies types in a language that supports mutable references.
Lastly, I saw this question here asking something similar. The asker states "I only find solutions for a language with mutable references but without genuine imperative control structures", I would like to see those references! I completely understand how to extend my language to have imperative control structures once I get my mutable references working, but this is where I am stuck now.
reference-request pl.programming-languages type-theory type-inference imperative-programming
New contributor
$endgroup$
I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let
is used to declare a variable as opposed to a bare assignment.
However, I'm now trying to add mutability into the language, specifically in the syntactical form
let mut x = 1
where x
is now a rebindable variable. This is effectively the same as
let x = ref 1 in ...
in ML, but my type-checker inserts the dereference operator (!
) automatically. So something like ref
is never directly used. Any instance of x
has a !
applied to it. So, if you do
let mut x = 1
let y = x
x = 2
Then x
is still rebindable, and has the value of 2
, but y
is immutable and has the value 1
.
I am having great difficulty extending my implementation of Hindley-Milner 's unification to support mutable references. The main paper I was reading was Standard ML-NJ Weak Polymorphism and Imperative Constructs by John Mitchell, as I was hoping to get an inference algorithm that had similar behavior to OCaml's weak polymorphism implementation.
This paper is pretty good and explains most things well enough, but it lacks a formal description of the type inference algorithm for its language. Are there any good resources on extending Hindley-Milners unification algorithm, that is, not the type system, with mutable references. I know the two go hand in hand, but I'm just having a really hard time jumping from the type inference rules from the paper I'm using to extending my implementation. I'm wondering if there is at least a description of an algorithm that unifies types in a language that supports mutable references.
Lastly, I saw this question here asking something similar. The asker states "I only find solutions for a language with mutable references but without genuine imperative control structures", I would like to see those references! I completely understand how to extend my language to have imperative control structures once I get my mutable references working, but this is where I am stuck now.
reference-request pl.programming-languages type-theory type-inference imperative-programming
reference-request pl.programming-languages type-theory type-inference imperative-programming
New contributor
New contributor
edited yesterday
Enrico Borba
New contributor
asked yesterday
Enrico BorbaEnrico Borba
1134
1134
New contributor
New contributor
$begingroup$
I'm not sure I fully understand your question. Are you asking about how to do type inference when types of variables depend on whether they occur on the LHS or RHS of an assignment? And: based on what information does your type-checker insert dereference operators automatically?
$endgroup$
– Martin Berger
yesterday
$begingroup$
BTW, there is a subtlety with automatic dereferencing on the RHS: assume you declarelet mut x = 1
and thenlet mut y = x
orlet z = x
. With auto-derefering,y
will have typeRef Int
andz
will have typeInt
, but this is not always what you want. Sometimes you wanty
to have typeRef Ref Int
, hence be an alias ofx
, orz
be of typeRef int
. How does your language handle this edge case?
$endgroup$
– Martin Berger
yesterday
$begingroup$
I edited my question to clarify about the use of mutable bindings.let mut x = 1
meansx
has typeInt
, and can be used anywhere where anInt
is accepted. Basically, ifx
was created withlet mut
, then anywhere anx
appears it is actually treated as!x
.
$endgroup$
– Enrico Borba
yesterday
add a comment |
$begingroup$
I'm not sure I fully understand your question. Are you asking about how to do type inference when types of variables depend on whether they occur on the LHS or RHS of an assignment? And: based on what information does your type-checker insert dereference operators automatically?
$endgroup$
– Martin Berger
yesterday
$begingroup$
BTW, there is a subtlety with automatic dereferencing on the RHS: assume you declarelet mut x = 1
and thenlet mut y = x
orlet z = x
. With auto-derefering,y
will have typeRef Int
andz
will have typeInt
, but this is not always what you want. Sometimes you wanty
to have typeRef Ref Int
, hence be an alias ofx
, orz
be of typeRef int
. How does your language handle this edge case?
$endgroup$
– Martin Berger
yesterday
$begingroup$
I edited my question to clarify about the use of mutable bindings.let mut x = 1
meansx
has typeInt
, and can be used anywhere where anInt
is accepted. Basically, ifx
was created withlet mut
, then anywhere anx
appears it is actually treated as!x
.
$endgroup$
– Enrico Borba
yesterday
$begingroup$
I'm not sure I fully understand your question. Are you asking about how to do type inference when types of variables depend on whether they occur on the LHS or RHS of an assignment? And: based on what information does your type-checker insert dereference operators automatically?
$endgroup$
– Martin Berger
yesterday
$begingroup$
I'm not sure I fully understand your question. Are you asking about how to do type inference when types of variables depend on whether they occur on the LHS or RHS of an assignment? And: based on what information does your type-checker insert dereference operators automatically?
$endgroup$
– Martin Berger
yesterday
$begingroup$
BTW, there is a subtlety with automatic dereferencing on the RHS: assume you declare
let mut x = 1
and then let mut y = x
or let z = x
. With auto-derefering, y
will have type Ref Int
and z
will have type Int
, but this is not always what you want. Sometimes you want y
to have type Ref Ref Int
, hence be an alias of x
, or z
be of type Ref int
. How does your language handle this edge case?$endgroup$
– Martin Berger
yesterday
$begingroup$
BTW, there is a subtlety with automatic dereferencing on the RHS: assume you declare
let mut x = 1
and then let mut y = x
or let z = x
. With auto-derefering, y
will have type Ref Int
and z
will have type Int
, but this is not always what you want. Sometimes you want y
to have type Ref Ref Int
, hence be an alias of x
, or z
be of type Ref int
. How does your language handle this edge case?$endgroup$
– Martin Berger
yesterday
$begingroup$
I edited my question to clarify about the use of mutable bindings.
let mut x = 1
means x
has type Int
, and can be used anywhere where an Int
is accepted. Basically, if x
was created with let mut
, then anywhere an x
appears it is actually treated as !x
.$endgroup$
– Enrico Borba
yesterday
$begingroup$
I edited my question to clarify about the use of mutable bindings.
let mut x = 1
means x
has type Int
, and can be used anywhere where an Int
is accepted. Basically, if x
was created with let mut
, then anywhere an x
appears it is actually treated as !x
.$endgroup$
– Enrico Borba
yesterday
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
To get behaviour similar to Ocaml, simply avoid generalizing the type of mutable variables.
With ordinary let-bindings, you generalize if you bind a value, and don't generalize otherwise. With mutable variable bindings, you never generalize.
The standard ML-like behaviour is then:
let xs = [] // xs : forall a. list a
let as = 1 :: xs // as : list int -- instantiate a to int
let bs = true :: xs // bs : list bool -- instantiate a to bool
The mutable variable typing will go:
let mut xs = [] // xs : list ?a -- a is an unification variable
let as = 1 :: xs // as : list int AND ALSO
// xs : list int, since ?a gets resolved to int
let bs = true :: xs // TYPE ERROR, since xs : list int
$endgroup$
$begingroup$
This is probably what I should do. I'll try to find some resources on what exactly OCaml treats as a value. Then, I'll try to relax the value restriction using Jacques Garrigue's paper, Relaxing the Value Restriction. Thanks
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Man I really feel goofy. I've been spending the past week trying to implement the type system described in the paper by John Mitchell that I mentioned in the question. OCaml's value restriction was much easier to implement. Took me about 1 hour to implement lack of generalization for non-expansive values, and to get mutability working. Thank you so much for this suggestion.
$endgroup$
– Enrico Borba
yesterday
$begingroup$
According to legend, this is basically what the whole research community felt when Andrew Wright came up with the value restriction.
$endgroup$
– Neel Krishnaswami
11 hours ago
add a comment |
$begingroup$
As Martin Berger points out in his comment, it is not actually entirely obvious what the semantics of your language is supposed to be and what "automatically inserting !" means. Consider the following bindings:
let mut x = 1
let y = x // x or !x ?
let mut z = x // x or !x ?
let f a = (y := a) // legal?
let g a = (z := a; x) // will this modify x?
let h r = (r := 4) // is this possible?
Are these all legal in your language? For those that are, what are their types?
FWIW, in ML, all of the above is allowed with !
inserted in the right places (and mut replaced with ref). The only way I can imagine this working in a language with second-class references but H/M typing is such that y is immutable, z is a separate reference from x, f hence is ill-typed, g does not mutate x, and h is impossible to write.
Once you have figured out the answers to this, i.e., the actual typing rules for your language, inference should be straightforward, following Neel's hint. You would treat mutability as an attribute separate from types. Then unification is not affected at all, only generalisation. But as the last example shows, this language is less expressive than ML.
$endgroup$
$begingroup$
I edited my question to clarify about the exact semantics of mutable bindings. Your guess was correct about how the semantics would work. I'll try to implement OCaml's standard value restriction then. Thanks!
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Note: the ambiguities above only exist if you think in terms of an encoding of his language using ML-stlye ref-cells. If you look at it from an imperative programming language with mutable variables there is no ambiguity:x
is not a ref-cell but a mutable variable.
$endgroup$
– Stefan
yesterday
$begingroup$
@Stefan, yes, but as I mention, that requires tracking mutability separately from types, otherwise type inference will be ambiguous. And that in turn requires introducing first-class references (a.k.a. pointers) as a separate concept that retains explicit dereferencing, because this strategy does not scale to the first-class case.
$endgroup$
– Andreas Rossberg
yesterday
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "114"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Enrico Borba is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f42554%2fextending-hindley-milner-to-type-mutable-references%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To get behaviour similar to Ocaml, simply avoid generalizing the type of mutable variables.
With ordinary let-bindings, you generalize if you bind a value, and don't generalize otherwise. With mutable variable bindings, you never generalize.
The standard ML-like behaviour is then:
let xs = [] // xs : forall a. list a
let as = 1 :: xs // as : list int -- instantiate a to int
let bs = true :: xs // bs : list bool -- instantiate a to bool
The mutable variable typing will go:
let mut xs = [] // xs : list ?a -- a is an unification variable
let as = 1 :: xs // as : list int AND ALSO
// xs : list int, since ?a gets resolved to int
let bs = true :: xs // TYPE ERROR, since xs : list int
$endgroup$
$begingroup$
This is probably what I should do. I'll try to find some resources on what exactly OCaml treats as a value. Then, I'll try to relax the value restriction using Jacques Garrigue's paper, Relaxing the Value Restriction. Thanks
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Man I really feel goofy. I've been spending the past week trying to implement the type system described in the paper by John Mitchell that I mentioned in the question. OCaml's value restriction was much easier to implement. Took me about 1 hour to implement lack of generalization for non-expansive values, and to get mutability working. Thank you so much for this suggestion.
$endgroup$
– Enrico Borba
yesterday
$begingroup$
According to legend, this is basically what the whole research community felt when Andrew Wright came up with the value restriction.
$endgroup$
– Neel Krishnaswami
11 hours ago
add a comment |
$begingroup$
To get behaviour similar to Ocaml, simply avoid generalizing the type of mutable variables.
With ordinary let-bindings, you generalize if you bind a value, and don't generalize otherwise. With mutable variable bindings, you never generalize.
The standard ML-like behaviour is then:
let xs = [] // xs : forall a. list a
let as = 1 :: xs // as : list int -- instantiate a to int
let bs = true :: xs // bs : list bool -- instantiate a to bool
The mutable variable typing will go:
let mut xs = [] // xs : list ?a -- a is an unification variable
let as = 1 :: xs // as : list int AND ALSO
// xs : list int, since ?a gets resolved to int
let bs = true :: xs // TYPE ERROR, since xs : list int
$endgroup$
$begingroup$
This is probably what I should do. I'll try to find some resources on what exactly OCaml treats as a value. Then, I'll try to relax the value restriction using Jacques Garrigue's paper, Relaxing the Value Restriction. Thanks
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Man I really feel goofy. I've been spending the past week trying to implement the type system described in the paper by John Mitchell that I mentioned in the question. OCaml's value restriction was much easier to implement. Took me about 1 hour to implement lack of generalization for non-expansive values, and to get mutability working. Thank you so much for this suggestion.
$endgroup$
– Enrico Borba
yesterday
$begingroup$
According to legend, this is basically what the whole research community felt when Andrew Wright came up with the value restriction.
$endgroup$
– Neel Krishnaswami
11 hours ago
add a comment |
$begingroup$
To get behaviour similar to Ocaml, simply avoid generalizing the type of mutable variables.
With ordinary let-bindings, you generalize if you bind a value, and don't generalize otherwise. With mutable variable bindings, you never generalize.
The standard ML-like behaviour is then:
let xs = [] // xs : forall a. list a
let as = 1 :: xs // as : list int -- instantiate a to int
let bs = true :: xs // bs : list bool -- instantiate a to bool
The mutable variable typing will go:
let mut xs = [] // xs : list ?a -- a is an unification variable
let as = 1 :: xs // as : list int AND ALSO
// xs : list int, since ?a gets resolved to int
let bs = true :: xs // TYPE ERROR, since xs : list int
$endgroup$
To get behaviour similar to Ocaml, simply avoid generalizing the type of mutable variables.
With ordinary let-bindings, you generalize if you bind a value, and don't generalize otherwise. With mutable variable bindings, you never generalize.
The standard ML-like behaviour is then:
let xs = [] // xs : forall a. list a
let as = 1 :: xs // as : list int -- instantiate a to int
let bs = true :: xs // bs : list bool -- instantiate a to bool
The mutable variable typing will go:
let mut xs = [] // xs : list ?a -- a is an unification variable
let as = 1 :: xs // as : list int AND ALSO
// xs : list int, since ?a gets resolved to int
let bs = true :: xs // TYPE ERROR, since xs : list int
answered yesterday
Neel KrishnaswamiNeel Krishnaswami
26.8k77151
26.8k77151
$begingroup$
This is probably what I should do. I'll try to find some resources on what exactly OCaml treats as a value. Then, I'll try to relax the value restriction using Jacques Garrigue's paper, Relaxing the Value Restriction. Thanks
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Man I really feel goofy. I've been spending the past week trying to implement the type system described in the paper by John Mitchell that I mentioned in the question. OCaml's value restriction was much easier to implement. Took me about 1 hour to implement lack of generalization for non-expansive values, and to get mutability working. Thank you so much for this suggestion.
$endgroup$
– Enrico Borba
yesterday
$begingroup$
According to legend, this is basically what the whole research community felt when Andrew Wright came up with the value restriction.
$endgroup$
– Neel Krishnaswami
11 hours ago
add a comment |
$begingroup$
This is probably what I should do. I'll try to find some resources on what exactly OCaml treats as a value. Then, I'll try to relax the value restriction using Jacques Garrigue's paper, Relaxing the Value Restriction. Thanks
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Man I really feel goofy. I've been spending the past week trying to implement the type system described in the paper by John Mitchell that I mentioned in the question. OCaml's value restriction was much easier to implement. Took me about 1 hour to implement lack of generalization for non-expansive values, and to get mutability working. Thank you so much for this suggestion.
$endgroup$
– Enrico Borba
yesterday
$begingroup$
According to legend, this is basically what the whole research community felt when Andrew Wright came up with the value restriction.
$endgroup$
– Neel Krishnaswami
11 hours ago
$begingroup$
This is probably what I should do. I'll try to find some resources on what exactly OCaml treats as a value. Then, I'll try to relax the value restriction using Jacques Garrigue's paper, Relaxing the Value Restriction. Thanks
$endgroup$
– Enrico Borba
yesterday
$begingroup$
This is probably what I should do. I'll try to find some resources on what exactly OCaml treats as a value. Then, I'll try to relax the value restriction using Jacques Garrigue's paper, Relaxing the Value Restriction. Thanks
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Man I really feel goofy. I've been spending the past week trying to implement the type system described in the paper by John Mitchell that I mentioned in the question. OCaml's value restriction was much easier to implement. Took me about 1 hour to implement lack of generalization for non-expansive values, and to get mutability working. Thank you so much for this suggestion.
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Man I really feel goofy. I've been spending the past week trying to implement the type system described in the paper by John Mitchell that I mentioned in the question. OCaml's value restriction was much easier to implement. Took me about 1 hour to implement lack of generalization for non-expansive values, and to get mutability working. Thank you so much for this suggestion.
$endgroup$
– Enrico Borba
yesterday
$begingroup$
According to legend, this is basically what the whole research community felt when Andrew Wright came up with the value restriction.
$endgroup$
– Neel Krishnaswami
11 hours ago
$begingroup$
According to legend, this is basically what the whole research community felt when Andrew Wright came up with the value restriction.
$endgroup$
– Neel Krishnaswami
11 hours ago
add a comment |
$begingroup$
As Martin Berger points out in his comment, it is not actually entirely obvious what the semantics of your language is supposed to be and what "automatically inserting !" means. Consider the following bindings:
let mut x = 1
let y = x // x or !x ?
let mut z = x // x or !x ?
let f a = (y := a) // legal?
let g a = (z := a; x) // will this modify x?
let h r = (r := 4) // is this possible?
Are these all legal in your language? For those that are, what are their types?
FWIW, in ML, all of the above is allowed with !
inserted in the right places (and mut replaced with ref). The only way I can imagine this working in a language with second-class references but H/M typing is such that y is immutable, z is a separate reference from x, f hence is ill-typed, g does not mutate x, and h is impossible to write.
Once you have figured out the answers to this, i.e., the actual typing rules for your language, inference should be straightforward, following Neel's hint. You would treat mutability as an attribute separate from types. Then unification is not affected at all, only generalisation. But as the last example shows, this language is less expressive than ML.
$endgroup$
$begingroup$
I edited my question to clarify about the exact semantics of mutable bindings. Your guess was correct about how the semantics would work. I'll try to implement OCaml's standard value restriction then. Thanks!
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Note: the ambiguities above only exist if you think in terms of an encoding of his language using ML-stlye ref-cells. If you look at it from an imperative programming language with mutable variables there is no ambiguity:x
is not a ref-cell but a mutable variable.
$endgroup$
– Stefan
yesterday
$begingroup$
@Stefan, yes, but as I mention, that requires tracking mutability separately from types, otherwise type inference will be ambiguous. And that in turn requires introducing first-class references (a.k.a. pointers) as a separate concept that retains explicit dereferencing, because this strategy does not scale to the first-class case.
$endgroup$
– Andreas Rossberg
yesterday
add a comment |
$begingroup$
As Martin Berger points out in his comment, it is not actually entirely obvious what the semantics of your language is supposed to be and what "automatically inserting !" means. Consider the following bindings:
let mut x = 1
let y = x // x or !x ?
let mut z = x // x or !x ?
let f a = (y := a) // legal?
let g a = (z := a; x) // will this modify x?
let h r = (r := 4) // is this possible?
Are these all legal in your language? For those that are, what are their types?
FWIW, in ML, all of the above is allowed with !
inserted in the right places (and mut replaced with ref). The only way I can imagine this working in a language with second-class references but H/M typing is such that y is immutable, z is a separate reference from x, f hence is ill-typed, g does not mutate x, and h is impossible to write.
Once you have figured out the answers to this, i.e., the actual typing rules for your language, inference should be straightforward, following Neel's hint. You would treat mutability as an attribute separate from types. Then unification is not affected at all, only generalisation. But as the last example shows, this language is less expressive than ML.
$endgroup$
$begingroup$
I edited my question to clarify about the exact semantics of mutable bindings. Your guess was correct about how the semantics would work. I'll try to implement OCaml's standard value restriction then. Thanks!
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Note: the ambiguities above only exist if you think in terms of an encoding of his language using ML-stlye ref-cells. If you look at it from an imperative programming language with mutable variables there is no ambiguity:x
is not a ref-cell but a mutable variable.
$endgroup$
– Stefan
yesterday
$begingroup$
@Stefan, yes, but as I mention, that requires tracking mutability separately from types, otherwise type inference will be ambiguous. And that in turn requires introducing first-class references (a.k.a. pointers) as a separate concept that retains explicit dereferencing, because this strategy does not scale to the first-class case.
$endgroup$
– Andreas Rossberg
yesterday
add a comment |
$begingroup$
As Martin Berger points out in his comment, it is not actually entirely obvious what the semantics of your language is supposed to be and what "automatically inserting !" means. Consider the following bindings:
let mut x = 1
let y = x // x or !x ?
let mut z = x // x or !x ?
let f a = (y := a) // legal?
let g a = (z := a; x) // will this modify x?
let h r = (r := 4) // is this possible?
Are these all legal in your language? For those that are, what are their types?
FWIW, in ML, all of the above is allowed with !
inserted in the right places (and mut replaced with ref). The only way I can imagine this working in a language with second-class references but H/M typing is such that y is immutable, z is a separate reference from x, f hence is ill-typed, g does not mutate x, and h is impossible to write.
Once you have figured out the answers to this, i.e., the actual typing rules for your language, inference should be straightforward, following Neel's hint. You would treat mutability as an attribute separate from types. Then unification is not affected at all, only generalisation. But as the last example shows, this language is less expressive than ML.
$endgroup$
As Martin Berger points out in his comment, it is not actually entirely obvious what the semantics of your language is supposed to be and what "automatically inserting !" means. Consider the following bindings:
let mut x = 1
let y = x // x or !x ?
let mut z = x // x or !x ?
let f a = (y := a) // legal?
let g a = (z := a; x) // will this modify x?
let h r = (r := 4) // is this possible?
Are these all legal in your language? For those that are, what are their types?
FWIW, in ML, all of the above is allowed with !
inserted in the right places (and mut replaced with ref). The only way I can imagine this working in a language with second-class references but H/M typing is such that y is immutable, z is a separate reference from x, f hence is ill-typed, g does not mutate x, and h is impossible to write.
Once you have figured out the answers to this, i.e., the actual typing rules for your language, inference should be straightforward, following Neel's hint. You would treat mutability as an attribute separate from types. Then unification is not affected at all, only generalisation. But as the last example shows, this language is less expressive than ML.
edited yesterday
answered yesterday
Andreas RossbergAndreas Rossberg
1,111911
1,111911
$begingroup$
I edited my question to clarify about the exact semantics of mutable bindings. Your guess was correct about how the semantics would work. I'll try to implement OCaml's standard value restriction then. Thanks!
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Note: the ambiguities above only exist if you think in terms of an encoding of his language using ML-stlye ref-cells. If you look at it from an imperative programming language with mutable variables there is no ambiguity:x
is not a ref-cell but a mutable variable.
$endgroup$
– Stefan
yesterday
$begingroup$
@Stefan, yes, but as I mention, that requires tracking mutability separately from types, otherwise type inference will be ambiguous. And that in turn requires introducing first-class references (a.k.a. pointers) as a separate concept that retains explicit dereferencing, because this strategy does not scale to the first-class case.
$endgroup$
– Andreas Rossberg
yesterday
add a comment |
$begingroup$
I edited my question to clarify about the exact semantics of mutable bindings. Your guess was correct about how the semantics would work. I'll try to implement OCaml's standard value restriction then. Thanks!
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Note: the ambiguities above only exist if you think in terms of an encoding of his language using ML-stlye ref-cells. If you look at it from an imperative programming language with mutable variables there is no ambiguity:x
is not a ref-cell but a mutable variable.
$endgroup$
– Stefan
yesterday
$begingroup$
@Stefan, yes, but as I mention, that requires tracking mutability separately from types, otherwise type inference will be ambiguous. And that in turn requires introducing first-class references (a.k.a. pointers) as a separate concept that retains explicit dereferencing, because this strategy does not scale to the first-class case.
$endgroup$
– Andreas Rossberg
yesterday
$begingroup$
I edited my question to clarify about the exact semantics of mutable bindings. Your guess was correct about how the semantics would work. I'll try to implement OCaml's standard value restriction then. Thanks!
$endgroup$
– Enrico Borba
yesterday
$begingroup$
I edited my question to clarify about the exact semantics of mutable bindings. Your guess was correct about how the semantics would work. I'll try to implement OCaml's standard value restriction then. Thanks!
$endgroup$
– Enrico Borba
yesterday
$begingroup$
Note: the ambiguities above only exist if you think in terms of an encoding of his language using ML-stlye ref-cells. If you look at it from an imperative programming language with mutable variables there is no ambiguity:
x
is not a ref-cell but a mutable variable.$endgroup$
– Stefan
yesterday
$begingroup$
Note: the ambiguities above only exist if you think in terms of an encoding of his language using ML-stlye ref-cells. If you look at it from an imperative programming language with mutable variables there is no ambiguity:
x
is not a ref-cell but a mutable variable.$endgroup$
– Stefan
yesterday
$begingroup$
@Stefan, yes, but as I mention, that requires tracking mutability separately from types, otherwise type inference will be ambiguous. And that in turn requires introducing first-class references (a.k.a. pointers) as a separate concept that retains explicit dereferencing, because this strategy does not scale to the first-class case.
$endgroup$
– Andreas Rossberg
yesterday
$begingroup$
@Stefan, yes, but as I mention, that requires tracking mutability separately from types, otherwise type inference will be ambiguous. And that in turn requires introducing first-class references (a.k.a. pointers) as a separate concept that retains explicit dereferencing, because this strategy does not scale to the first-class case.
$endgroup$
– Andreas Rossberg
yesterday
add a comment |
Enrico Borba is a new contributor. Be nice, and check out our Code of Conduct.
Enrico Borba is a new contributor. Be nice, and check out our Code of Conduct.
Enrico Borba is a new contributor. Be nice, and check out our Code of Conduct.
Enrico Borba is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Theoretical Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f42554%2fextending-hindley-milner-to-type-mutable-references%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I'm not sure I fully understand your question. Are you asking about how to do type inference when types of variables depend on whether they occur on the LHS or RHS of an assignment? And: based on what information does your type-checker insert dereference operators automatically?
$endgroup$
– Martin Berger
yesterday
$begingroup$
BTW, there is a subtlety with automatic dereferencing on the RHS: assume you declare
let mut x = 1
and thenlet mut y = x
orlet z = x
. With auto-derefering,y
will have typeRef Int
andz
will have typeInt
, but this is not always what you want. Sometimes you wanty
to have typeRef Ref Int
, hence be an alias ofx
, orz
be of typeRef int
. How does your language handle this edge case?$endgroup$
– Martin Berger
yesterday
$begingroup$
I edited my question to clarify about the use of mutable bindings.
let mut x = 1
meansx
has typeInt
, and can be used anywhere where anInt
is accepted. Basically, ifx
was created withlet mut
, then anywhere anx
appears it is actually treated as!x
.$endgroup$
– Enrico Borba
yesterday