Closed Night-walker closed 10 years ago
I actually had thought about supporting immutable data in Dao long time ago, but I quickly abandoned the idea since it means a huge amount of work to support strict immutability.
Technically, val is easy to implement for Dao: take the runtime nature of var plus compile-time constraints of const. It actually can substitute const entirely, albeit it isn't clear what to do with compile-time evaluation then.
Such partial support still sounds interesting. But it cannot substitute const entirely. Currently, const has a critical property that is, it is copied (if possible) when it is "moved" (or assigned) to a different memory location (for example, in const a={1,2}; b = a
, b
will be a copy of a
). Implicit copying is what immutable data should avoid.
And it may not be as easy as you think to implement it for Dao. Compiling time checking of constraints of const does not work across function call boundary, so the following will not be properly handled for immutable data by the current type system,
immutable alist = { 1, 2, 3 }
routine Test( a : list<int> )
{
a.append( 4 )
}
Test( alist )
In order to handle this at compiling time, Dao type system would require a huge (or complete) change, and the resulting type system may be huge which is clearly not something in the line of design principle of Dao. Another way is the handle it at running time, of course, it also means a huge amount of work.
So it is a bit over optimistic to say,
Technically, val is easy to implement for Dao: take the runtime nature of var plus compile-time constraints of const.
But there is indeed a approach that is just a bit more than taking the runtime nature of var plus compile-time constraints of const:).
The approach I just realized is to add a new type, say immutable
(I really don't like val
, it just looks too like var
). And support the declaration syntax immutable name : type
such that it declares a variable of type immutable<type>
which can only be matched to immutable<type or a parent type>
. Such variables can be used in the same way as type
variables, but are applied with the same compiling constraints of const
.
So the above example would have to be rewritten as the following in order to be handled properly,
immutable alist = { 1, 2, 3 }
routine Test( a : immutable<list<int>> )
{
a.append( 4 ) # compiling error for this!
}
Test( alist )
Support for such immutable
would be fairly simple.
Well, the immutability is a really nice and helpful feature, but I have a couple of questions.
immutable x = { 1, 2, 3 }
and const x = { 1, 2, 3 }
?
I.e. will be immutable a = {1, 2, 3}; a.append(4)
or const b = {1, 2, 3}; b.append(4)
allowed? If not, will it raise any error? If yes, will it be a compile-time one or run-time one?m={1, 2}; m.append(3) #{ this is allowed => no error #}; routine r(immutable<x>){x.append(5)}; r(m) #{ this will be caught in compile-time #}
(which is pretty much a flag for each variable, which'll get set on each routine-call and checked before use of that variable). Or will it be kind of a synonym to const
?As you can see, I'm a bit confused - could you please clarify it?
I actually had thought about supporting immutable data in Dao long time ago, but I quickly abandoned the idea since it means a huge amount of work to support strict immutability.
There is no need for strict immutability. Scala doesn't guarantee it, for example -- it has no notion "const" or "val" methods, so it can't ensure immutability for mutable types. As I said, technical constraints are less important then the logical ones.
Currently, const has a critical property that is, it is copied (if possible) when it is "moved" (or assigned) to a different memory location (for example, in const a={1,2}; b = a, b will be a copy of a). Implicit copying is what immutable data should avoid.
That's a problem indeed, as far as variables and parameters are mutable by default. I thought it's possible to just add immutability on top of existing variable model. It's apparently impossible.
The approach I just realized is to add a new type, say immutable (I really don't like val, it just looks too like var). And support the declaration syntax immutable name : type such that it declares a variable of type immutable
which can only be matched to immutable . Such variables can be used in the same way as type variables, but are applied with the same compiling constraints of const.
Unfortunately, that creates too much obstruction, particularly for routine parameters. And it is not compatible with the rest of Dao API which will make no use of immutable
in order to retain simplicity, even though most routines don't actually change their parameters. Using such feature would then be rather destructive for readability, simplicity and consistency.
The only variant to support immutability seamlessly is probably to make it default. That is, all variables, routine parameters and whatever else there is are created immutable unless they are marked by var
. Similar to how Rust handles things with its mut
modifier.
But even if it's technically feasible, it may be a rather radical change for many users. The interoperability with C/C++ would also be affected. But I don't have any other idea at the moment.
Now, to @dumblob.
What will be the difference between immutable x = { 1, 2, 3 } and const x = { 1, 2, 3 }? I.e. will be immutable a = {1, 2, 3}; a.append(4) or const b = {1, 2, 3}; b.append(4) allowed? If not, will it raise any error? If yes, will it be a compile-time one or run-time one?
Prohibiting mutating methods like list.append()
requires marking those (or all other) methods in some way. But it's not necessary -- as I mentioned, Scala doesn't care about that at all, and it's OK. So both your examples could pass the compilation. The difference between the two is that const
is to be copied to ensure that the original value stays intact, while immutable
would have relied on type checks.
Will the immutability be respected only in routine/method interfaces? I.e. m={1, 2}; m.append(3) #{ this is allowed => no error #}; routine r(immutable
){x.append(5)}; r(m) #{ this will be caught in compile-time #} (which is pretty much a flag for each variable, which'll get set on each routine-call and checked before use of that variable). Or will it be kind of a synonym to const?
I suppose, T
and immutable<T>
would have been two different types technically, though their interoperability seems unclear. Either way, it would have introduced too much fuss around typing and routine prototypes and interfaces and etc.
By the way, how exactly const
copying is implemented? How often a constant may be copied?
# converts encoding of str using reserve_char for invalid characters
routine convertEncoding(str: string, reserve_char: int) => string {
const conv = {152 -> 1034, 164 -> 1240, ... } # large encoding conversion table
return std.string(%str){ [i]
var node = conv.find(str[i]) # what about conv copying here?
node == none? reserve_char : node.value
}
}
Will conv.find()
trigger copying of conv
on each call? If so, it may cause dangerous performance issues.
I think I have an idea on how to deal with immutability without sacrificing too much. Rather then trying to support truly immutable values, we could simply provide fixed variables.
A fixed variable x
does not give guarantees that the object a
it points to cannot be changed. Nevertheless, the direct modification of a
via x
is forbidden. You can freely pass the value of x
anywhere, possibly changing the content of a
in the process, but assignments to x
such as x = b
or x += c
are prohibited. Think of it as of local immutability.
First, this allows to easily implement val
(maybe other keyword, but in this case definitely not immutable
) without making dramatic changes to the existing variable model. It is just what I was talking about: var
plus few static checks from const
, with no aliasing analysis or additional constraints.
Then, primitive data like numbers, enums, strings and any inherently "frozen" objects will be guaranteed true immutability with val
. For everything else, the reliability is mostly put on the programmer. Of course, logical errors will be possible, but the value of val
still outweighs them.
Even if you cannot reliably assume that the data pointed by val
stays untouched, it is still a useful hint about its usage. And when dealing with code which utilizes val
where possible, you can be sure that the value pointed by var
is meant to be modified at some point. That should be sufficient.
@Night-walker This proposal looks good from the technical point of view, however I doubt it`s overall useful.
In my eyes immutability is mostly useful when passing some value somewhere (e.g. into some routine, code section...) which's body I don't see at the time of using it (because it's in an external module or bytecode or whatever) and which's body is supposed to use the passed value read-only. In this case I (the programmer) want to be super-sure nothing will change inside the whole structure (even if it's a tree, list, file, whichever complex entity) and therefore I'll flag the variable before passing it (usually this is being denoted in the routines/code_section
s interface, but it seems more natural to denote it exactly there, where the routine/code_section is called).
Crazy demonstration of the principle:
x = {1, 2, 3}
some_routine(set_flag_immutable_temporarily_for_one_passing(x))
x.append(4) // no problem
or rather
x = {1, 2, 3}
set_flag_immutable(x)
ret = some_routine(x) // if the routine wants to anyhow change the list, an exception (compile-time or at least run-time one) will be raised
if (ret) return x // the immutable flag will remain (one can use frame{ defer{ unset_flag_immutable(x) }; set_flag_immutable(x); some_routine(x) }) to handle this issue
unset_flag_immutable(x)
x.append(5) // no problem
I don't see therefore much usefulness in using immutability only in the "outmost scope" (code-section, routine body, etc.) becase one can see everything at a first glance anyway.
As I already pointed out, even mighty Scala with its sophisticated type system doesn't do what you want. But val
is still used extensively (virtually everywhere) in Scala without problems. If you want to be super-sure about immutability, just use immutable data structures. For instance, Scala-like immutable lists based on structural sharing are pretty trivial to implement and are quite effective most of the time. I actually had an experimental implementation of such lists for Dao.
Full control is only possible when all data is immutable by default -- not just variables, but routine parameters and routines themselves (regarding self
). But that is a questionable solution for a language like Dao.
What @dumblob suggested is very hard support and not affordable for Dao's size and intended lightweight. On the other hand, what @Night-walker suggested is very easy to support, but its usefulness is quite limited for frozen/immutable value. I don't feel it quite convinced to introduce new keyword and changes to the language for this feature.
However, after considering all the possibilities that I can think of at this moment, it seems to me that enhancing const
is probably the most feasible alternative. The new const
will be fully compatible with the current const
, so it has to be defined with constant expressions. The new const
can be passed around without triggering copying, like val
in @Night-walker's suggestion. They are represented by a new type const<typename>
, which is effectively a typename
type with a special flag, so that they can used just as typename
without casting. Such type names can be used in parameter list as hints, so that type checking rules (compiling time) for constant can be applied to such parameter in the same way. Running time checking may be supported for some cases without tagging the parameter values. This way the immutability mentioned by @dumblob can also be achieved in certain degree (probably fully achievable if the programs are written to obey some guidelines).
@Night-walker
Will conv.find() trigger copying of conv on each call?
Yes, it will. Because it is not known if conv.find()
will modify the parameter, conv
has to be copied to ensure it is not modified. This can be solved with the new const
support.
@daokoder
Great idea! I'm looking forward to using the new const
.
The moral of the const
story: if you have feeling that something "just magically works", it must have been using dark rituals and dreadful sacrifices to sustain itself, sealing the terrible truth deep inside the secluded catacombs.
However, after considering all the possibilities that I can think of at this moment, it seems to me that enhancing const is probably the most feasible alternative.
Demons lurking within const
must be exorcised in any case -- its current implementation is simply not viable.
They are represented by a new type const
, which is effectively a typename type with a special flag, so that they can used just as typename without casting. Such type names can be used in parameter list as hints, so that type checking rules (compiling time) for constant can be applied to such parameter in the same way.
Given that const<type>
is rather cumbersome and obtrusive, it is not going to be used much in the explicit form. Most functions in a language like Dao don't need to change their arguments (except self
), so strict code style will demand piling up const<...>
in large quantities -- which is a rather dismal option (tagging mutable data instead would certainly be much simpler). And without appearing in routine prototypes, the usefulness of such const
is no better then that of the approach I proposed.
Running time checking may be supported for some cases without tagging the parameter values. This way the immutability mentioned by @dumblob can also be achieved in certain degree (probably fully achievable if the programs are written to obey some guidelines).
It's better not to transfer such responsibility on the programmer, as it will not make his life any eaiser and will not guarantee anything unless he's a robot which makes no mistakes.
Given that const
is rather cumbersome and obtrusive, it is not going to be used much in the explicit form. Most functions in a language like Dao don't need to change their arguments (except self), so strict code style will demand piling up const<...> in large quantities -- which is a rather dismal option (tagging mutable data instead would certainly be much simpler). And without appearing in routine prototypes, the usefulness of such const is no better then that of the approach I proposed.
I saw this inconvenience, and had a shortcut in mind for using constant parameter. I just forgot to mention it in the previous comment, here it is,
routine M( par :: type )
would be equivalent to,
routine M( par : const<type> )
It's better not to transfer such responsibility on the programmer, as it will not make his life any eaiser and will not guarantee anything unless he's a robot which makes no mistakes.
Well, it is just like val
in your proposal, const
is more a hint than a constraint for temporary
constant, so it will not be enforced in every places (that would make it fully immutable and would require unacceptable amount changes in the implementation).
To ease programmers writing code like a robot (as @Night-walker said above), I'd suggest disallowing them passing a const-flagged variable to a non-const interface. This would force the whole call-stack to mimic the nature of the deepest routines/methods.
I'd suggest disallowing them passing a const-flagged variable to a non-const interface.
Of course.
I saw this inconvenience, and had a shortcut in mind for using constant parameter. I just forgot to mention it in the previous comment, here it is,
routine M( par :: type ) would be equivalent to,
routine M( par : const
)
You should have mentioned this before, it's a game changer.
However, if you bind const
directly to a type, there might be a need to short-tag nested types as well. That is, const<list<@T>>
is not a complete guarantee of list's immutability. Using something like... like... [HERE I WANTED BACKQUOTE] :) So, ahem, a backquote or so to prefix any type component would solve this (given that the type system won't choke with such nesting). And there would be no need for const<...>
form, it would always be simply... [the character which does not exist for Github].
Alternatively, the shortcut symbol could simply affect all the subtypes recursively as well, which would actually be simpler to deal with.
If the "short-tagging of nested types" is feasible in scope of Dao simplicity, I'm definitely in favour of it.
But the use of backtick/backquote (i.e. that small, almost invisible character) itself doesn't suit me well. I agree that writing const<>
before each nested type is tedious, but I'd rather choose this long way because of clarity.
Single quote is also an option given the possible changes around string
. It's larger than two dots which form additional colon in ::
:)
But as I said, it's not necessary to stick to a type: it may be simpler to be able to write l::lst<@T>
(or maybe l: 'lst<@T>
) rather then l: 'lst<'@T>>
to produce l: const<list<const<@T>>>
. By the way, note that the full const
notation can hardly be an example of clarity.
To me the prorities are still the same :)
l: const<list<@T>>
with auto-nesting of constantnessl: const<list<const<@T>>>
l: 'list<@T>
with auto-nesting of constantnessl: 'list<'@T>
l::list<@T>
with auto-nesting of constantnessThe question is: do we need this auto-nesting (I'd call it "recursive propagation" -- sounds very scientific and cool :) ), or we need precise control over nested types, e.g to be able to write l: list<'@T>
which boils down to l: list<const<@T>>
.
I think recursive propagation is simpler to deal with as one knows that an object is simply "totally constant to the very bones", which in most cases is what is required.
In the name of simplicity and immutability and functional languages, I'd go for the choice with "recursive propagation" (btw it sounds really cool :) ) as the "precise control" shouldn't be needed in high-level languages like Dao (I usually call such attitudes "C++ onanism" and I mean it really mean :) ).
Normally, one does not need to write type names with nested const
type. Once you specified the outermost const
(with or without the aid of shortcut), it is clear that all the value and nested values should be const and immutable (at least theoretically). Adding const
to the nested types of a const
type is simply redundant, because the following types (for example) can be safely matched to each other:
const<list<list<string>>>
const<list<list<const<string>>>>
const<list<const<list<string>>>>
Because they all mean that a value of these type cannot be modified. The type list< list<int> >
can also be safely matched to the above types, since no operations on a value of these types are supposed to modify the value, so no harm will be done to the value.
Of course, const
can be added to nested types of non const types, for example list<const<string>>
will simply mean a list of constant strings. But such usage is rare, I don't think it is necessary to add abbreviated way to write it.
the "precise control" shouldn't be needed in high-level languages like Dao (I usually call such attitudes "C++ onanism" and I mean it really mean :) )
Yeah, I would express it similarly, albeit translating the exact words into English would be problematic :)
Normally, one does not need to write type names with nested const type.
Well, C++ forces to do just that. If you can do that lst: const<list<@T>>
would also ensure that not only lst.append(some)
but also lst[0].modify()
is disallowed, then it's fine.
lst: const<list<@T>>
would also ensure that not onlylst.append(some)
but alsolst[0].modify()
is disallowed
This should be the case.
More or less done. It should be ready for testing :)
Any other variants other than ::
? It's not a bad choice, but type prefix instead of const<...>
is a tempting alternative.
What type prefix do you have in mind?
As a shortcut, I do tend to prefer ::
, given that there isn't many choices we have due to the limited symbols on the keyboard. Another shortcut I have supported is ':=', which is for parameters with default values. Since types of such parameters are often implicit, I thought a shortcut may be handy to indicated them to be const. These shortcuts make updating the method signatures of standard and builtin types much easier.
The ::
and :=
suit me well.
Another shortcut I have supported is ':=', which is for parameters with default values
Hmm, how about prefixing the parameter name instead? It could eliminate the need for extra syntax variations...
Hmm, how about prefixing the parameter name instead? It could eliminate the need for extra syntax variations...
Not necessarily. Suppose, we use the prefixing approach like in C/C++,
routine Meth( const abc : list<int> ) { return 123 }
What is the type of Meth
? Currently, it would be
routine<abc:const<list<int>>=>int>
. With the prefixing approach, how would you express this type name? Also const<type>
is the type inferred for constant declarations, and can be passed around.
It's about the notation, not the type. Currently, extra :
in p::typename
and p:=value
may actually be viewed as a suffix to p
, after which you have normal :typename
or =value
form, even though ::
and :=
may actually be indivisible pseudo-operators. I'm considering a prefix form, e.g. 'p: typename
and 'p = value
, which would not require two different notations. By the way, it would also allow to write just 'p
, with neither type nor default value, which is not possible with the current syntactic forms.
By the way, it would also allow to write just 'p, with neither type nor default value
Do you have any use-cases in Dao for having such const variable? I can't think of any and I'm glad it's not possible right now.
By the way, it would also allow to write just 'p, with neither type nor default value Do you have any use-cases in Dao for having such const variable? I can't think of any and I'm glad it's not possible right now.
It's not idiomatic but possible to write functions like routine f(a, b){...}
, in the manner of other scripting languages. Some folks could thus prefer to benefit from const
correctness without explicit typing, albeit it's not a very important case.
I see ::
is already put to use. However, it's strange that it is used for non-self strings and not used for arguments of code section methods.
By the way, it would also allow to write just 'p, with neither type nor default value, which is not possible with the current syntactic forms.
I don't think that would be a common case. Think about it, why would I use const parameters, while letting users to guess what types should the parameters accept? I believe one should not be encouraged to do so. Besides, 'p
just doesn't look right.
However, it's strange that it is used for non-self strings and not used for arguments of code section methods.
Do you mean the normal arguments or the arguments inside code section? But in either case, no need. For the former, there is no guarantee what users will do inside the code sections. For the later, those parameters should be used just as local variables, one can modify without problem, because at the next invoking of the section, they will be reset. Not enforcing const on them, also leaves the possibility of modifying them when necessary.
Do you mean the normal arguments or the arguments inside code section? But in either case, no need. For the former, there is no guarantee what users will do inside the code sections.
I meant normal arguments. The method may (and should) give guarantees that the passed values cannot be changed implicitly within it, that is what matters. The code section itself is provided by the user, so he knows and controls what's inside and thus guarantees aren't necessary. But the main body of code section method is outside the reach of the user in this case, so guarantees are naturally expected.
And about strings. If I got it right, they are always passed by value excluding self
parameter of the methods of string
itself. Thus, for instance, in find( self :: string, str :: string, ...
there should be no need for ::
after str
.
I meant normal arguments. The method may (and should) give guarantees that the passed values cannot be changed implicitly within it, that is what matters. The code section itself is provided by the user, so he knows and controls what's inside and thus guarantees aren't necessary. But the main body of code section method is outside the reach of the user in this case, so guarantees are naturally expected.
This would also require some code section parameters made constant. Doable, but I need to check if it might be problematic for some cases.
Thus, for instance, in
find( self :: string, str :: string, ...
, there should be no need for::
afterstr
.
It makes no difference for variable, but it could make difference for constant strings: copying can be avoided with a minor internal change (not yet done).
Thus, for instance, in find( self :: string, str :: string, ..., there should be no need for :: after str. It makes no difference for variable, but it could make difference for constant strings: copying can be avoided with a minor internal change (not yet done).
The user should not care about internal string implementation and related optimizations (and it's just a fast shallow copying, no?). string
is a primitive type in Dao, so const
mark on a string which is a (non-self) routine parameter is confusing and redundant.
And what about possible usage of a parameter prefix instead of ::
and :=
?
The user should not care about internal string implementation and related optimizations (and it's just a fast shallow copying, no?).
Yes, just shallow copying for string. So I also questioned if it is really necessary to add const
to string parameters. Not using them is certainly clearer, but I don't find it confusing. Anyway, shallow copying has made it less relevant to have const string non-self parameter, might well be removed for good.
And what about possible usage of a parameter prefix instead of
::
and:=
?
Prefixing for const parameter is not consistent with how routine types are expressed.
@Night-walker
Is there anything I miss when I say that routine r(x: const<any>, y: const<any>)
should work and is sufficient for the case you demonstrated in https://github.com/daokoder/dao/issues/173#issuecomment-42216239 ?
Is there anything I miss when I say that routine r(x: const
, y: const ) should work and is sufficient for the case you demonstrated in #173 (comment) ?
Well, yes. But it's not an important case anyway, I only mentioned it to show the shift in semantics.
A minor issue with ::
for me is that one has to write either p :: value
or p::value
, with the first being somewhat too lengthy for my taste, and the second being too tight :) Neither of the two are compatible with the notation p: value
which I prefer and which is common in other languages with similar syntax. p:: value
just looks weird :)
That's why I'm considering options for shifting the extra character somewhere else.
I find it a bit strange that you consider 'p: value
looks better than p:: value
:).
Well, yes.
I hope you didn't mean the syntax, but rather some semantics :)
But it's not an important case
I'm curious - what is that case?
But it's not an important case I'm curious - what is that case?
I already described it. Untyped parameters.
I find it a bit strange that you consider 'p: value looks better than p:: value :).
Well, it doesn't have to be '
. I just have seen it as a prefix already, at least in Rust, Haskell and Lisp, and it's also easy to type. For me, something like 'p: value
looks more semantically natural then p:: value
.
Untyped parameters.
But what are they good for if any
works "the same": routine r(x: any) { io.writeln(x ?< type(string)) }; r('abc')
?
Untyped parameters. But what are they good for if any works "the same": routine r(x: any) { io.writeln(x ?< type(string)) }; r('abc')?
They aren't exactly the same, as far as I know. They are "good" for those who don't like explicit typing.
By the way, using const
parameters for arguments of code section routines is absolutely necessary for proper use of const
values (variables). Without it, one won't even be able to use trivial list::map()
on a constant list.
And yes, there is still an option of using a type prefix instead of ::
, e.g. p: 'type
.
It is not applicable in case of p = value
, but the latter is almost always used with primitive types, so it doesn't matter much.
Indeed, they are not the same. If you try,
load meta
routine r( a ) { meta.trace( $print ) }
r( 1 )
r( 'a' )
you will see two versions of r()
are called: one specialized for int
parameter, and the other specialized for string
. If you use routine r( a : any ) { ... }
, no specialization will be done.
Still, const<any>
is quite useful in case one wants "untyped" parameters. There is just higher probability that a type error will be discovered later (which shouldn't matter anyway if one uses untyped parameter).
The most apparent and strong tendency in modern programming is the growing interest to functional paradigm. Most recent languages like Scala, Ceylon and Rust are built around the principles of functional programming, which clearly makes its way into mainstream.
One peculiar thing about such languages is separation of mutable and immutable data, for instance via using
var
andval
when declaring variables. Whileval
may not necessary give strict guarantees of immutability, its very semantics is helpful in making the code more readable and safe. The trade-off here is that you must pay extra attention to how the variables you declare are going to be used.It was more then once when I thought about whether such concept would be useful in Dao and how could it be implemented. I think it is worth discussing.
Technically,
val
is easy to implement for Dao: take the runtime nature ofvar
plus compile-time constraints ofconst
. It actually can substituteconst
entirely, albeit it isn't clear what to do with compile-time evaluation then.It would be sufficient to allow to specify
val
wherevar
can currently be expected, without making deep changes in handling of data in Dao code. The only related change could be the ability to assign "vals" of a class in its constructor, just as C++ allows such thing for constants.Overall, it would not lead to any enforcements -- one could still ignore any immutability constraints and use ordinary variables where he pleases. And it would not require new data structures like immutable lists or so -- the intention behind
val
is what matters most, technical constraints are less important. More importantly, Dao has enough means to process data without visible side effects, soval
could be used quite often -- more so thenvar
.The downside of
val
is that it requires extra attention when writing the code -- you need to keep the specifiersvar
andval
in accordance with how you operate the related variables. However, it would not add much complexity ifval
takes over the role ofconst
as well.Personally, I would have used
val
. It can make the logic put in the code and its data flow more apparent. Though maybe the difference would not often be as significant as I think.