Closed JustusAdam closed 5 years ago
Thanks @JustusAdam for putting together this proposal.
This one is very important, so we should understand what that is conceptually. Here is my take on it:
I see this as an introduction of a special type into our language. One can view it like this: There exist two (higher-kinded) types in our system
Data a
This is the type for all value that flow in between the functions inside our algorithms.State a
This is the type for all values that stick with a function.More formally, "stick" means that this function actually turns a function f:: a -> b
into f:: (a,s) -> (b,s)
. I say stick because semantically, we/Ohua executes these functions for example inside an smap
by reusing the new state for the next invocation, i.e., the state sticks with the function (for its lifetime or until it is reassigned). In Haskell, such functions of the Kleisli category are represented in terms of the State
monad and the according Ohua-like execution is achieved via the concept of a value recursion using mfix
. This is also what we do: We essentially fold over the state.
I like the discussion above about making the state aspect obvious to the programmer in two places:
But after all, we are talking about a type-system aspect here, so if the programmer gets guided by the compiler then making it only obvious during creation is fine for me.
At the moment, I do favor the on
-variant.
But whatever syntactic sugar we decide upon, in the end this should desugar into a normal let
in the typed lambda caluclus of ALang.
(See issue #23 for my proposal to have a language for this syntatic sugar to keep ALang clean.)
I am currently in the process of implementing this both in the compiler and the parsers.
I decided to go with an operator named with
but with the semantics of on
. The reason is because I think with
, as a word, makes more sense.
I have the basic implementation in place. We will follow up aspects such as shared state etc. in other issues once we get there.
Problem description and solution requirements
The Rust backend for Ohua requires an explicit association between the state of a stateful function and the function itself. As a relic from Java this has up to this point been implicit (as a class) or linked using a backend mechanism such as clojure metadata.
This implicit approach is unfeasible in Rust, because the implicit association of a class is not present, and more importantly the reflection mechanisms for discovering initializers for state do not exist.
Furthermore we believe that an explicit state association will provide more flexibility for the user and may be used to implement state sharing stateful functions.
Requirements
Additionally our proposals so far are also designed such that they may be used in the future to express state sharing. While this is not a necessary property to solve the issue at hand, it is a desirable property.
Solution variants
We believe that new syntax may be necessary to implement state initialization and association in a user friendly way.
Three variants were discussed so far.
Arrow assignment with implicit association
In arrow syntax a special new assignment operator
<-
(or similar) is used to explicitly initialize a state cell. This binding (s
in the example) can only be used as a first argument to a stateful function and implicitly associates as thestatefulFunction
's state.Advantages
smap
), which will make it possible in the future to do dynamically created/auto resetting states
can be supplied to multiple functions, allowing state sharing.Disadvantages
s
cannot be used in the same way other bound values can, despite seeming to be a regularly bound value.<-
is not self explanatory. It bears no inherent association with state as such.<s-
arrow.Scoped intialization does not exist yet which means we have to require users to bind the state in the outermost scope so that their code does not subtly break one we introduce the feature. However doing this is tedious, especially in the presence of algorithms, where having to explicitly provide state not only bloats code, but to me also feels like leaking implementation detail.
Env
arg). This can be enforced via the compiler. As such, an algorithm can have its own initializers.Even in the presence of scoped bindings we may want to provide additional syntax for locally initializing state that is automatically bound at the outermost scope with the very reasons just mentioned.
State a
type. As such, finding out whether this is state or not is no harder than fixing any other type error. It is essentially the same problem for the programmer.s
.with
operator (explicit initializer association)The
with
operator associates a state initializer with a function.with
is a binary operator and its rhs must be a callable expression in the target language1. State sharing is done by either reusing an already bound function (boundSf
) or initializing multiple stateful functions with the same function (function1
andfunction2
).1: The precise nature of the RHS is variable. We can use a function or maybe even expression, which would allow for dynamically created state.
Advantages
let
bound values.with
always binds state globally, thus no need to pay special attention to the future possibility of scoped state.Disadvantages
local
keyword to scope state binding.let boundSf = statefulFunction with local initState in ...
.with
feels somewhat less flexible than using<-
.with
is to make state sharing more explicit but then it is possible to just use those created functions in different places. So, I essentially have the same problem again, such that we did not solve the problem of finding all function calls that share state in one place.Regular
let
with explicit state associationThis variant is a blend of
<-
andwith
. It explicitly associates a state cell with a stateful function usingon
. However unlikewith
it allows binding the state cell earlier usinglet
which enables state sharing by using the bound state with multiple functions or using anon
bound function multiple times.Depending on the availability of dynamic state binding and scoped state certain restrictions may be placed on what the RHS of
on
has to be. For instance, in the beginning we require that it resolve to an env binding.Advantages
<-
variant state can be bound in scopes. Enabling dynamic state binding and scoped state.s
.with
stateful functions are easy do distinguish from stateless ones, becauseon
occurs at the use site.Disadvantages
s
are unclear with respect to whether it is usable as a regular value. It is unclear whether it can or should be allowed to be used as regular data. If not, this may also lead to the same confusion as was the case with the arrow variant.s
.On new syntax
I think it is worth mentioning that we may not necessarily require actual new syntax for this feature. A similar effect may also be achieved by using a function (such as
init
) that is especially recognized by the compiler.Similar as with
<-
init
values would be traced through the code and implicitly become the state of a function to which they are the first argument.The same advantages and disadvantages as with
<-
apply.One advantage of this approach over all the others is that no new syntax needs to be introduced. This means that handling
init
can be entirely done in the core library with no change to any of the parsers. As a disadvantage, there can not be a stateful function namedinit
, similar to thenew
keyword in languages like Java.