A few questions about Felix

[Ari Bellamy]

So, now that I've got Felix set up with VS2019 and I've got some time again, I'm going to sit down and try to learn Felix sometime soon here. But first, I had a few questions.

1) What is the best way to go about learning Felix? I'm not particularly concerned about the more imperative parts, but documentation seems sparse for some of the more "advanced" features (and some features, like the kinding system, simply have "TBD" on their tutorial pages) and a lot of the samples seem sparse on usage of said advanced features.

2) What is the general use case for Felix? I was initially drawn to it because it's a high-perfomance scripting language that can interop with C++ fairly easily. I mainly am a hobbyist that makes games (but I'm also quite interested in programming language design and theory, as well as several other non-gamedev fields) and generally don't like working with C++, so Felix would potentially let me work with a lot of the C++-focused ecosystem in a more comfortable setting.

3) How does the garbage collector work? I'm having issues finding documentation on it other than casual references to certain data being garbage collected in the tutorial.

Thanks in advance!

[John Skaller2]

> On 19 Mar 2020, at 12:44, Ari Bellamy <arabella....@gmail.com> wrote:
>
> So, now that I've got Felix set up with VS2019 and I've got some time again, I'm going to sit down and try to learn Felix sometime soon here. But first, I had a few questions.
>
> 1) What is the best way to go about learning Felix?

Write some code :-)

This list is a good place to ask questions. Once you get started with some basic stuff
the evidence is that it becomes a lot easier. A few good programmers previously were
contributing to the compiler and library within a week. That is actually a good way to learn.
You’ll find something missing or wrong and I can help you fix it and that’s your first commit :-)

> I'm not particularly concerned about the more imperative parts, but documentation seems sparse for some of the more "advanced" features (and some features, like the kinding system, simply have "TBD" on their tutorial pages) and a lot of the samples seem sparse on usage of said advanced features.

There’s a lot of documentation all over the place. A large part of the system is literate
programmed so you can read source on your local machine by running

flx_web —port=1234

This plus other stuff was available online but I ran out of money to pay the virtual
machine provider. So I did a lot on “read-the-docs”. There are also some PDF files.

> 2) What is the general use case for Felix?

Its a general purpose high speed strongly typed programming language with native
C++ interfacing. So everything from systems programming up. I wouldn’t use it for kernel
development at this stage.

> I was initially drawn to it because it's a high-perfomance scripting language that can interop with C++ fairly easily. I mainly am a hobbyist that makes games (but I'm also quite interested in programming language design and theory, as well as several other non-gamedev fields) and generally don't like working with C++, so Felix would potentially let me work with a lot of the C++-focused ecosystem in a more comfortable setting.

Yes, hopefully. Felix is designed for game development in particular. Originally it was designed
for telecommunications: lots of small objects, lots of context switching, small messages.
Perfect for games too.

I have a friend with a game written in C++ and Felix for iPhone. you can embed Felix in C/C++
code as well, that is, inside event loop frameworks. Its a bit tricky though :-)

>
> 3) How does the garbage collector work? I'm having issues finding documentation on it other than casual references to certain data being garbage collected in the tutorial.

The GC is a world-stop mark-sweep collector, conservatively scans the stacks, but
precsiely scans the heap. The mark phase can run multiple threads although it defaults
to one at the moment. Each heap allocated object has an associated “shape” or RTTI
which tells the collector where the pointers are (actually its more sophisticated, you can
write custom scanners).

The GC tracks objects using a Judy1Array, so there’s a penalty on allocation.

But you can of course used C++ reference counting, or you can use manual
allocation and deallocation, or you can use uniqueness typing to reduce the
load on the GC. If you write more or less “C like” programs the GC use will
be small enough to ignore.

—
John Skaller
ska...@internode.on.net

[John Skaller2]

>
> 3) How does the garbage collector work? I'm having issues finding documentation on it other than casual references to certain data being garbage collected in the tutorial.

Read the intro in the code:

https://github.com/felix-lang/felix/blob/master/src/packages/gc.fdoc

—
John Skaller
ska...@internode.on.net

[John Skaller2]

A few tips. Develop code incrementally with test cases as well. Some wag decided
to call the former “Agile” and the latter “Extreme” decades after I was doing it.

The reason is that sometimes the compiler is going to give you incomprehensible
error messages. If that happens, you know its in the last piece of code you wrote.
If necessary post the code and compiler output here. I may spot the problem
faster than you, and I also then can try to improve the compiler diagnostic
so it reports the problem better, because now I have a test case.

Don’t try to learn everything at once. There’s too much. Some of the stuff
is highly experiemental. Some stuff I really need input from users to sort out.
In particular, there’s lots of half finished subsystems and user priorities should
drive where I focus my effort.

One of the critical things is the paradigm shift to coroutines. You don’t need these
for basic stuff, but they become increasing useful for things like games.

A coroutine is basically a procedure which is spawned to produce a fibre
of control, each coroutine has its own stack. The “stack” is made from
heap allocated frames. Coroutines don’t use the machine stack, except
transiently.

Coroutines communicate by reading and writing on channels. You can think
of processes doing that, but coroutines are a sequential programming construct,
there’s no concurrency. [At least there’s wasn’t until recently .. but that’s an advanced
topic]


—
John Skaller
ska...@internode.on.net

[Ari Bellamy]

> There’s a lot of documentation all over the place. A large part of the system is literate programmed so you can read source on your local machine

Ah, I didn't realize that a lot of it was literate programmed (not used to code being literate programmed). I'll go through that.

> The GC is a world-stop mark-sweep collector, conservatively scans the stacks, but precsiely scans the heap.

> Read the intro in the code

I'll definitely go through that. I'm actually highly interested in working with uniqueness types in the context of gamedev, so I might experiment with using those to reduce GC times.

[John Skaller2]

I have to go to school now, hopefully its still open. The university next door is closed
due to pandemic. Be back in 8 hours or so.

—
John Skaller
ska...@internode.on.net

[John Skaller2]

>
> > The GC is a world-stop mark-sweep collector, conservatively scans the stacks, but precsiely scans the heap.
> > Read the intro in the code
>
> I'll definitely go through that. I'm actually highly interested in working with uniqueness types in the context of gamedev, so I might experiment with using those to reduce GC times.

Right. So there’s a major unsolved problem there: “borrowing”.
There are also some other interesting issues.

The core library stuff is here:

https://github.com/felix-lang/felix/blob/master/src/packages/unique.fdoc

An example use, implementing C like null terminated strings with uniqueness
typing to make the use safe, is here:

https://github.com/felix-lang/felix/blob/master/src/packages/ucstring.fdoc

When reading literate code in the library the lines like this one:

@tangler cstring.flx = share/lib/std/strings/cstring.flx

tell you (and the system) which file the code goes in.
In the above case you will find code in:

FLX_INSTALL_DIR/share/lib/std/strings/cstring.flx

and you can examine that code too, with the literate stuff removed.
Edits to be committed to the repo have to be done to the lp code though.




—
John Skaller
ska...@internode.on.net

[John Skaller2]

One of the “delights” of writing documentation (ugghh) is that trying to make
a simple presentation often suggests better ways of doing things:

struct thread_frame_t {
int argc;
char **argv;
FILE *flx_stdin;
FILE *flx_stdout;
FILE *flx_stderr;
::flx::gc::generic::gc_profile_t *gcp;
::flx::run::flx_world *world;
thread_frame_t(
);
// program dependent global variables here ...
};

This is the standard structure. So why not”

struct base_thread_frame_t {
int argc;
char **argv;
FILE *flx_stdin;
FILE *flx_stdout;
FILE *flx_stderr;
::flx::gc::generic::gc_profile_t *gcp;
::flx::run::flx_world *world;
thread_frame_t(
);
};

stuct thread_frame_t : base_thread_frame_t {
// program dependent global variables here ...
};


—
John Skaller
ska...@internode.on.net

[John Skaller2]

I think i have solved a major problem in computer science.

In C, you have expressions which may or may not be have side effects.
You cannot tell from the syntax of use, nor from the type.

In Felix there are generators, these do not have side effects, but
they do store internal state. Also functions, even though they’re
not allowed side-effects, need not be pure.

In Haskell, some functions are strict, others not.
This is equivalent to the fact that most functions in eager languages
are actually partial functions, though some are total.

We can arrange the types of these functions in a lattice based
on badness. Purity is required for transparency. However forcing
a language to only have pure function weakens the language
expressivity significantly. But if we remove the constraint as in C,
then its hard to reason about a program.

For pedagogic purposes only, lets say we have notations
for kinds of functions like

D -> [props] C

which is actually implemented in Felix. Suppose the props entry
is a type with subtyping rules so that the function subtyping
rules follow the props subtyping rules, that is, is structure preserving
wrt subtyping.

We might say pure side effect free functions are a subtype of
ones that are impure but side effect free, which are subtypes of
those with side effects.

Now we need a composition rule. If we compose a function with property
P1 with one with property P2, the result has both properties and we use
the least bad property which contains both as the property of the composite.
This is a standard construction for subtyping lattices.

We must also consider product types when thinking of expressions.
The problem is that code doesn’t just consist of linear compositions
like

h (g (f x))

but we have trees like

k (l x, m y)

because we have tuples. So expressions themselves must have types
that “carry” the properties.

For products, its clear that if the components are formed from say
functions where one has a side effect, the expression has
a side effect too.

So we need enhanced expression types which have more information
than the type of value the expression represents, instead we use a pair
with the value type and badness property.

When a function is applied to an expression the expression type badness property
is again the least bad of the argument badness and function badness.

HOWEVER .. and this is important .. let bound variables have badness,
but statement variables have no badness!

With a let bound variable we imagine that the expression it is bound to
replaces the use of the variable, so the badness must be propagated,

But with statement variables, the whole idea is to *decouple* an expression
NOT for convenience, but to split out the badness types into several
expressions to allow local reasoning.

Felix does this “automatically” for generators which is a design fault.

The problem is we have expressions like

sin (*p++)

and we want to FORCE the user to indicate the side effect expicitly.
If we wrote that as

sin (deref ( postinc p ))

you couldn’t reason about it easily without knowing the types badnesses:
sin is pure an effect free, deref is effect free but not pure, postinc is a mutator
so is not pure and it does it have effects. So explicitly we write

impure effects sin (impure effects deref (impure effects postinc p)))

Although sin is pure, the impurity and effects of the postinc are propagated
up the expression tree and the user is required to write them expliitly.
It is now evident if an expression is referentially transparent because
now the badness is transparent.

HOWEVER as mentioned you can use statement splitting:

var x = impure effects postinc p;
var y = impure deref x;
var z = sin y;

This preserves the ability to reason about expressions based on their badness,
but is simpler, because the use of a statement variable extinguishes badness.

Of course the notation is ugly. For expressions we could use different kinds
of parens instead of identifiers: eg if <> meant effects and [] meant merely impure
we could even allow

sin (deref [ positinc <p>])

on the basis that it is visually apparent the “badest” parens are inherited even if
not written. Alternatively we can use different assignment operators:


var resuilt =[effect] sin (*p++);


The point is now, expressions can be written exactly as in C, without regard
to badness PROVIDED the correct assignment operator is used. If it isn’t
the type system barfs.

An equivalent idea is that all expression must be strict, pure, and effect free
but you can “cast away” badness. Then we can reason about the expressions
because there is an explicit cast visible.

I think these results extend to linear functions and also uniqueness typing.
In fact, they *unify* them.

There’s something really interesting there! Uniqueness typing is DUAL to
linear functions. Unique values are guarranteed unshared, but you can
share them freely if you want. Linear function promise NOT to share
their argument, but the argument doesn’t have to be unique.

More generally, badness types are the same. A function with some
badness property promises to propagate that property to its result,
but applies no constraint on its argument. On the other hand an
expression with some badness property means that it is no badder
than the stated type bad can freely be made badder. for example
just because sin x is pure doesn’t mean you cannot pass it
to a function with a side effect.

The critical thing in this analysis is that actually we don’t need to worry
about badness except on two kinds of entities, we can compute it
mechanically, But it must be given for primitives, and it must be
specified for variables, in particular, for type variables and in particular
for HOFs, an argument or result which is a function must specify
a badness.

The GOOD thing here is that to do this we really have to introduce
badness variables too!

And the key result is this: we can do subtyping unification because badness
variables for a lattice. And the rules for product formation and composition
are structure preserving so propagate these results into the subtyping
unification for the expressions types themselves.

TO BE DONE: some concrete notation is require which implements the
requirements in a way that is convenient and doesn’t break too much code.
Function types in Felix already have an effects slot in the type, but variables
dont.

The key result here is that expression badness properties are DUAL
to function badness property in the same way uniqueness types
are dual to linear functions.

—
John Skaller
ska...@internode.on.net

[Keean Schupke]

Hi John,

I think this is interesting, and reminds me of algebraic effects. Just a thought regarding the badness being cast away:

var x  = impure effects postinc p;
var y = impure deref x;
var z = sin y;

I think this is wrong 'z' is still impure. I think what you mean is:

var xx = \p -> impure effects postinc p
var yy = \x -> impure deref x;
var zz = \y -> sin y

now "zz" is pure, but in the first case I don't think it is. Likewise we still have to track impurity, so when zz is applied to yy and xx like this:

zz (yy (xx p))

This whole expression is impure (it has side-effects).

Of course its possible I'm missing something, but that's how it seems to me at the moment.

Cheers,

Keean.

--
You received this message because you are subscribed to the Google Groups "Felix Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to felix-languag...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/felix-language/24D65508-6CB0-43A1-BDA9-F2FF996A29BE%40internode.on.net.

[John Skaller2]

>
> I think this is interesting, and reminds me of algebraic effects.

Yes. But effects are somehow wrong.

> Just a thought regarding the badness being cast away:
>
> var x = impure effects postinc p;
> var y = impure deref x;
> var z = sin y;
>
> I think this is wrong 'z' is still impure.

Ah. Dependence on a variable makes

sin y

impure. But z is a variable, and variables discard attributes .. (but see below)
I mean, a variable can’t be “referentially transparent” in itself, for example.
But using one in an expression does make the expression impure and thus
not transparent. Using an immutable binding, however, doesn’t make the containing
expression impure (because it’s immutable). However felix “val” are not addressable
but they CAN be reassigned in a loop “Val” just means non-addressable “single assignment”
form.

> I think what you mean is:
>
> var xx = \p -> impure effects postinc p
> var yy = \x -> impure deref x;
> var zz = \y -> sin y
>
> now "zz" is pure, but in the first case I don't think it is.

The idea is, we’re interested in reasoning about expressions because
an expression, potentially, just defines a value, there is no well specified
execution order.

OTOH when we have a sequence of statements, the execution order
is explicit, and so we only need to reason about the variable initialisers.

This doesn’t hold if we consider uniqueness though. But maybe it SHOULD be lost
when assigned to a variable.

> Likewise we still have to track impurity, so when zz is applied to yy and xx like this:
>
> zz (yy (xx p))
>
> This whole expression is impure (it has side-effects).
>
> Of course its possible I'm missing something, but that's how it seems to me at the moment.

Maybe I am too. You’re right it’s like effects algebra, where a region is controlled by
a handler. The handler cancels the effects (or propagates another). Much like a
static exception handling try/catch.

—
John Skaller
ska...@internode.on.net

[Keean Schupke]

I think this relates to execution, something I have been thinking about for a while.

You view 'z' in the imperative sense, a memory location that can store a value, and is in a sense 'pure' - except that locations and storage are by very definition impure. So actually viewed as an imperative variable 'z' is always impure.

In the functional sense 'z' represents the computation. The computation cannot discard the impurity, because the computation represented by 'z' is impure.

This brings me to a critical point, execution order, or time. There is no time in mathematics, there is no before and after. Z is the computation, and the result of the computation is the same as the computation itself.

1 + 1 = 2

Is a 'truth' and true for all time. 1 + 1 _is_ 2 there is no computation, there is no before and after.

This is the view taken by functional programming.

In the imperative view, computation is a mechanical process, inputs are set, the handle is turned and outputs are generated. There is a before (only the arguments exist) and and after (we have a result). This is by definition impure because it is not a mathematical truth that holds for all time.

Now in computing there is a duality, pure functions can be both, they represent a true for all time fact, but a CPU is a machine that has time (before/after).

So coming back to 'z = sin y' in the functional view, 'z' is the computation which is the value, and hence z cannot discard the impurity.

From the imperative view, 'z' is impure because it has time, it is not initialised until after 'sin y' is executed, and hence _all_ imperative variables are impure.

I have a long running disagreement with some functional programming people that only imperative systems can be implemented. In effect I believe the universe is imperative, and that the pure ( true for all time ) functional view is a construct of the human imagination. This does. It however undermine the value of mathematics, as proofs are only possible with such a view. Or to put it another way, in mathematics you have proofs, in physics you have experiments, a mathematical model can never be 100% accurate, it's just a model, not reality.

Cheers,

Keean.

--
You received this message because you are subscribed to the Google Groups "Felix Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to felix-languag...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/felix-language/B494D762-6E26-4AE3-82A2-005B01F303C3%40internode.on.net.

[Keean Schupke]

Sorry typo:

On Sun, 5 Apr 2020, 09:41 Keean Schupke, <ke...@fry-it.com> wrote:

I think this relates to execution, something I have been thinking about for a while.

You view 'z' in the imperative sense, a memory location that can store a value, and is in a sense 'pure' - except that locations and storage are by very definition impure. So actually viewed as an imperative variable 'z' is always impure.

In the functional sense 'z' represents the computation. The computation cannot discard the impurity, because the computation represented by 'z' is impure.

This brings me to a critical point, execution order, or time. There is no time in mathematics, there is no before and after. Z is the computation, and the result of the computation is the same as the computation itself.

1 + 1 = 2

Is a 'truth' and true for all time. 1 + 1 _is_ 2 there is no computation, there is no before and after.

This is the view taken by functional programming.

In the imperative view, computation is a mechanical process, inputs are set, the handle is turned and outputs are generated. There is a before (only the arguments exist) and and after (we have a result). This is by definition impure because it is not a mathematical truth that holds for all time.

Now in computing there is a duality, pure functions can be both, they represent a true for all time fact, but a CPU is a machine that has time (before/after).

So coming back to 'z = sin y' in the functional view, 'z' is the computation which is the value, and hence z cannot discard the impurity.

From the imperative view, 'z' is impure because it has time, it is not initialised until after 'sin y' is executed, and hence _all_ imperative variables are impure.

I have a long running disagreement with some functional programming people that only imperative systems can be implemented. In effect I believe the universe is imperative, and that the pure ( true for all time ) functional view is a construct of the human imagination.

This does not however undermine the value of...

[John Skaller2]

> On 5 Apr 2020, at 18:41, Keean Schupke <ke...@fry-it.com> wrote:
>
> I think this relates to execution, something I have been thinking about for a while.
>
> You view 'z' in the imperative sense, a memory location that can store a value, and is in a sense 'pure' - except that locations and storage are by very definition impure. So actually viewed as an imperative variable 'z' is always impure.
>
> In the functional sense 'z' represents the computation. The computation cannot discard the impurity, because the computation represented by 'z' is impure.

Yes, I agree with the idea. However it is the use of z that is impure, not the variable.

That is,

* the value type of the variable is “int”,
* but the expression type of the variable is “int,{impure}”

because actually, in an expression a variable is not a value, but an address
which from which the value is fetched. So really the type is int& in C++ terms.

>
> This brings me to a critical point, execution order, or time. There is no time in mathematics, there is no before and after.

Precisely. Computational expressions can’t be reasoned about based on the order
things are done. Instead we add the badness attributes like purity, side-effects,
etc etc. These are computed timelessly .. in fact at compile time.

> Z is the computation, and the result of the computation is the same as the computation itself.
>
> 1 + 1 = 2
>
> Is a 'truth' and true for all time. 1 + 1 _is_ 2 there is no computation, there is no before and after.
>
> This is the view taken by functional programming.

Yes, and it is the right view for expressions, but making them the complete language
is wrong. in Felix, we have a functional subsystem.

There are two defects of great importance in the functional model”

1. Most operations are not typeable, that is, they’re partial functions,
and we cannot write the exact type.

2. Computing is Science NOT Mathematics. In particular, the notion
of observation is critical.

My example is that a list, usually considered finite by functional people
is infinite because the only observation you can make about its length
is that there is a lower bound. No function can establish that a list has
an upper bound. You can only observe list tails.

>
> In the imperative view, computation is a mechanical process, inputs are set, the handle is turned and outputs are generated. There is a before (only the arguments exist) and and after (we have a result). This is by definition impure because it is not a mathematical truth that holds for all time.

But by pure I mean a function is pure if it only depends on its arguments.
Impure means it depends on some external variable as well, as so isn’t
referentially transparent.

> From the imperative view, 'z' is impure because it has time, it is not initialised until after 'sin y' is executed, and hence _all_ imperative variables are impure.

Yes, but it is not z that has time but the use of it. you can use it in an expression with value 1,
and use it later and then it has value 2. The value depends on time, so the value of the
containing expression also depends on time.

But as I said before, z is actually not the name of a value but the name of
a storage location, and in an expresion “z” actuallyt means to fetch the store
value at the named location. So *actually* you’re doing a dereference operation,
and that operation is what introduces the impurity, not the variable itself.

In other words what is REALLY happening is that z is a constant address
and in an expression “z” actually means “*z”.

In Felix, we wrote &z for the address, and assignment is written

storeat (&z,1);

The variable is actually &z, z is just shorthand for *(&z). In particular & is
not an operator. It’s just a character in the name of the variable.
Anyone writing assembler will understand, variables are constant addresses
(actually usually offsets to some register, usually the stack pointer or more
generally some frame pointer).

> I have a long running disagreement with some functional programming people that only imperative systems can be implemented.

Yes. Haskell has at least two sources of imperative behaviour.

1. At the very top level there is an implicit “print” of the result.
There has to be, otherwise the result isn’t observable.

2. Primitive operations like addition are always strict and imperative,
so Haskell can ALSO be driven from the bottom up.

> In effect I believe the universe is imperative, and that the pure ( true for all time ) functional view is a construct of the human imagination. This does. It however undermine the value of mathematics, as proofs are only possible with such a view. Or to put it another way, in mathematics you have proofs, in physics you have experiments, a mathematical model can never be 100% accurate, it's just a model, not reality.

Right.

The “category” used to model functional programming is set theory.

It lacks the concept of action which is basic. Physically, CPU occupies space,
requires time to operate, and energy flows, generating heat.

Programming abstracts this to a high level, but you cannot eliminate
the fundamentals.

My belief is that product types are functional in that you can fetch components
any time, and any one of them. But sum types are NOT a pair of a discriminat
tag and a value of suiable type, that’s a model. An actual sum is a lazy
control bifurcation. When you hit a conditional one of two branches is actually
taken, and this is intrinsically imperative.

If you consider this C code:

{ block0; }
{ block1; }

the stack frame of the containing function has

union { data0; data1; }

i.e. a the local variables of block 0 are data 0, and of block 1 are data 1.

There’s is no tag. The program counter is the discriminant. We execute block 0
first and the stack is data 0, then block 1, and the data is data 1.

So the actual discriminated union is the C union with the PC discriminating,
that is TIME is the discriminant.

therefore in a conditional, bool is stored time. That is, a lazy computation.
Its the actual branch that is the sum type. Sum types are CONTROL
types with temporal domain, not a spatial domain like products.




—
John Skaller
ska...@internode.on.net

[John Skaller2]

>
> This does not however undermine the value of...

of course not, physics would be screwes without maths.
But it isn’t just maths.

Programming would be screwed without functional calculations.
But it isn’t just functional.

—
John Skaller
ska...@internode.on.net

[John Skaller2]

I’m trying to figure out the difference between type classes and Ocaml style
functors. Functors are nominally typed and you can for example have two
for the same types with the same, or different methods, more generally
overlap in types is arbitrary.

Something in Felix like

class NewClass [T] = instance OldClass[T * T, int] { .. }

would create a named instance. However the implementation and semantics
have a problem. If the NewClass is like other classes it has to be instantiated
first, before monomorphisation, so it could then be opened or used with
qualified name NewClass. Worse, since it’s a class, it can be instantiated
with another functorisation.

In Ocaml, sequential lookup handles this. New Ocaml may have recursive
modules and hence functors, but they’re at least in a “let rec” style mutual
binding, whereas recursion in Felix is implicit due to setwise lookup so is
harder to sort out (although not impossible perhaps).

Another method would be to just have a dedicated functor statement,
but its not clear what this would gain. Its clear functors are more powerful
than type classes but as in Ocaml a bit harder to use if the result is
nominally typed.

If we could depend on run time dictionaries it would add benefit.

===

Which bring up the lame java like object things. They can be anonymous.
However the “implements” feature doesn’t work. What i mean is that the
return type of the object constructor (a record of functions) must match it
exactly, and there can be only one. It should support subtyping. Anonymous
objects would be hard to check. For defined objects, its a statement so an
extra type check could be added. We’d have to “lift” anonymous objects
as we lift anonymous functions and give them names so the lifted construction
was a statement. Lifting out of expressions is suspect, even for lambdas.

What’s really needed with objects is proper variance for “derived” objects.
I’m not sure how to do that. In principle, if you want to “upcast” an object,
you’re just doing a subtyping coercion on a record of functions which should
be straight forward but doesn’t seem to be ;(


—
John Skaller
ska...@internode.on.net

[Keean Schupke]

From memory, if you want anonymous 'classes' you have to have structural typing. So the type of a record is the structural type, you can then use row-polymorphism to subtype the records.

Keean.

--
You received this message because you are subscribed to the Google Groups "Felix Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to felix-languag...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/felix-language/EA76802D-8243-474C-BAE2-B41D1C3F6259%40internode.on.net.

[John Skaller2]

> On 30 Apr 2020, at 16:38, Keean Schupke <ke...@fry-it.com> wrote:
>
> From memory, if you want anonymous 'classes' you have to have structural typing. So the type of a record is the structural type, you can then use row-polymorphism to subtype the records.
>

This is for the Felix object stuff (not Felix classes).

That is how Ocaml does OO, using row polymorphism AND subtyping. Its objects are anonymous.
Felix objects are just function that return a record of functions closed over the local data.
The compiler has support for using the “method” keyword to specify which functions
go in the record (i.e. its really just syntactic sugar). The method is roughly the
same as CLOS I believe.

The syntax is made to look like Java:

interface thing { … }
object blag(x:int) implements thing { …. method fred … }

interface is a synonym for record.
object is a synonym for function.
method just means to return a record of functions.

i did this as a joke to poke fun at Java .. but actually it turned out
to be very useful for plugins to return all their service functions
in a single package, since that only needs a single dlsym() symbol
instead of many.

Felix should be able to do subtyping, however objects are quite dynamic
and run time functions can’t be polymorphic.

Also, Felix doesn’t have polymorphic types, not real ones.
It uses type schema instead. In other words:

binder [T] defn { … }

is just universal quantification but it really means an indexed family
of monomorphic defn thingos.

In particular this also applies to row polymorphism.

This means in general existential (output) types don’t work.
[They work in type classes but not in general code]

Ocaml’s object stuff needs the row polymorphism in the output position,
i.e. existentials and/or higher order polymorphism. Higher order polymorphism
does not play well with overloading.




—
John Skaller
ska...@internode.on.net

[John Skaller2]

At the moment, Felix can build for any specified target.
To build for two targets, you have to do two runs.
The second run clobbers the cache entirely so it’s expensive time and resource wise.

I’d like to be able to

flx —target=host —target=iphone ….

and have flx build both without clobbering the cache. At the moment you can avoid
clobbering the cache with separate runs:

flx —target=host —cache=tmp/host …
flx —target=iphone —cache=tmp/iphone …

This means the standard library and user code is parsed and bound once each time,
but subsequent use of that cache with the same target will not have to rebuild
the standard library.

Felix is designed so the parse of any file is entirely platform independent.
Conditional compilation occurs AFTER parsing, unlike C macro processing.

However parsing IS dependent on the standard library path so it can be
dependent on external factors, although usually isn’t. Sharing parses isn’t
well supported. The cache is actually split into binary and text subdirectories,
the idea being platform dependent stuff is separated but platform independent
stuff can be shared. I’m not sure exactly what is stored where actually implements
this correctly.

A second thingthat doesn’t work and should is batch mode C++ only builds.
This is because the data structures used to control building are designed for
one build of some kind, and the loop that does batch mode building just
hacks things in such a way that it only works properly for Felix builds.

Batch mode for multiple targets is even trickier, especially as the platform model
isn’t fully implemented. For example, if you’re building for MacOS and iPhone,
actually running the iPhone stuff can’t be automated or even run on the Mac.
However if the build is for the iPhone emulator it can be run, but I don’t know
if it can be automated or if input and output data used to verify correctness
(input and expect files) on the Mac can be made available to the iphone
emulator.

Similar issues arise with many other cross platform builds. For example
building on Windows under Ubuntu could be made to work because
the file Windows file system is accessible from Ubuntu (but not the other
way around). Ditto for building for Windows under Linux, if the two boxes
are connected via a network. Or even sneaker net .. :-)

Also Swift builds are partially implemented but are sure to have he same
problem as C++ builds.

In addition, flx can compile Ocaml but not link it. However Felix build tools
can also build Ocaml libraries and link them, flx_build_flxg does this and
most of it is in library code that could be reused in flx if only I organised
the control and internal data structures driving it better.

======

In addition to all this, the Felix system rebuild run after the bootstrap
is very flexible but the makefile(s) dirving it are a bit brain dead.
In theory you can just rebuild the RTL, for example, but it doesn’t
actually work because it assumes a previous step has put stuff
in a temporary location.

When Felix is built, Python is used to build “bootflx”. This is a different
program to “flx” but it uses most of the same sources. I have to hand
edit the mainline when I change things, but the core is the same.
Bootflx source includes the code normally found in plugins,
the toolchain drivers. It only includes host level toolchains
(not toolchains for iPhone etc that can’t be hosts).

Bootflx is then used to build flx and the toolchains plugins.
However flx static links and preloads the host level plugins
so no directory searching is required to run it for standard
targets. Only extra targets build by the user actually require
dynamic loading.

Flx has extra capabilities (stuff like batch mode I think don’t work
with bootflx but I’m not sure .. most of the code is identical
except in bootflx “include” statement is used instead of plugin
loading commands)

The bottom line is I need to do some refactoring and redesign of
flx which is very hard because any mistakes mean the rebuild process
will not work and the bootstrap will probably fails as well.

—
John Skaller
ska...@internode.on.net

[John Skaller2]

I’ve had a good look at the cache location issue and unfortunately it all goes
a long way back right to configuration and profile setup. Also, targets are
specified ultimately by an absolute pathname which optionally is composed
from a top level target directory, which is quickly forgotten, and a subdirectory.

So any qualification of the cache location would have to use the absolute
pathname of the target directory as a prefix. Also there are actually two caches,
one called “binary” and one called “text”. This was originally so the Felix compiler
output went in “text” and the C++ compiler output went in “binary”. The problem is
that these two directory become distinct absolute pathnames and this can happen
*before* the target is known.

The construction of pathnames in Felix is complicated and the dependencies
non-trivial. For example the parsing of a file depends ONLY on the current
grammar, and the top level grammar specification is basically given by a single
absolute directory name (it can’t currently be split up). The technically the
parsed files could be cached with the absolute pathname of the grammar
top level as a prefix to keep them unique. Note that Felix already does
dependency checking on the grammar to see if it changed, if not, an existing
cached parse can be kept and parsing skipped if the file being parsed
also hasn’t changed. Splitting the parse output into several files prefixed
by grammar directory avoid reparsing when multiple grammars are used
on the same file (meaning, multiple directories with unchanging grammars
in them). But this is rare so it’s not clear it’s worth the effort anyhow, even though
parsing is very expensive. And the prefixing is only sustainable whilst grammars
can live only in one directory. If a path was used to allow searching multiple
directories, the prefix would have to be the search path.

*** So it’s probably reasonable to have a single, shared, parse cache. ***

The next level of caching is bindings of the parses. Before binding,
macro processing occurs. This includes conditional compilation and so is
dependent on the macro file(s) specified. Usually it’s only one file,
flx.flxh, which contains a few macro variables that specify the OS.
The OS is usually target dependent. This is one of the few text files that
belongs in the target directory and isn’t shared. Binding ALSO depends
on the include files found, which depends on the search path.

At least the standard library is usually going to be invariant for each target.
Although paths for third party libraries might vary per program, they will all
usually use the same standard library.

The C++ produced is generally dependent only on the bindings.
That is, it is deterministic once the Felix code is bound.
The object files produced by C++ are compiler and switch dependent
but generally Felix goes to great lengths to fix these per target.
Optimisation level might be an exception. However Felix dependency
checks these things in great detail using the compiler itself and some
record of some of the settings (but this may not be completely reliable,
not sure but if it isn’t its a bug).

*** So bound code, object code, and ultimately linker output can be
prefixed by the target. ***

Although this isn’t enough to ensure uniqueness it doesn’t matter.
It just saves some work IF the dependency checker believe a
result would be invariant.

Other files: the resh files contain abstract package dependencies,
and could be dependent on Felix conditional compilation. This could
be quite likely, eg Windows and Unix need different libraries to do TCP/IP.

The bindings of abstract package is path dependent, but usually restricted
to the target and fixed third party packages. So again, the binary cache
is the right place.

So almost everything except parser output should be in the binary cache.
That is, the target dependent cache.

The big tradeoff is that a lot of closely related targets will have the same C++.
For example product and debug builds at the C++ level have the same C++
input (but not at the Felix level, where instrumentation does change the C++ output).
Another example: compiling on Mac with both clang and gcc will use the same C++
input. Two distinct targets, but sharable C++ code (differences are usually handled
with C++ macros).

So there is a conflict here. Felix to C++ translation time is a BIG cost.
if I’m producing a program for Mac, Linux, iPhone, etc all at once,
with the same C++ it would be a pain to have to regenerate the C++
each time, but because of Felix conditional compilation, we may need to.

SDL2 code for example will be invariant because SDL itself handles
the conditional compilation and linking stuff, the same C++ SDL code
will run on all platforms (that’s what SDL does!)

Note a faulty splitup of the cache will never impact correctness,
since the dependency checking is (supposedly) robust. It only
impacts build times.



—
John Skaller
ska...@internode.on.net

[John Skaller2]

OK, I do my best work asleep.

The design principle is that the cache holds the results of a build, so that
when a developer changes one or two files, or perhaps deletes or adds one,
only the changed files of stuff coupled to them needs to be rebuilt.

If the developer is building for two or three targets, the target dependent
parts of the cache should be separated so switching targets also switches
caches. But common parts, such as, typically, the parses, will be shared.

If the developer is working on several projects at once, switching projects
should also switch caches for the user files, however the bound standard library
will be the same for a given target.

To get all this right in details is very hard. Consider just changing optimisation
setting, the C++ optimisation level only impacts object files.Felix optimisation,
however, impacts inlining depth and thus the generated C++. A developer using
the debugging usage switching to production and back occasionally shouldn’t need
to rebuild everything, the cache again might be split.

The organising principle is that the cache should be rebuilt when source code files
change, and split when the processing instructions change. Processing instructions
include:

the root mainline program file name
search paths
compiler binary
grammar
optimisation switches
target
configuration database

source is diffs in actual source files, period.
In fact, adding or deleting a file is irrelevant! Because
adding a file to a directory does nothing unless another
file actually uses it, requiring a diff to an existing file.

So the idea is the cache location is based on some master top level,
PLUS a key, PLUS the file whose translation is cached, the cache
is made stale if the file changed from last run with the same key.

The key is the KEY. The key is just a directly name that splits the
top level cache directory. The obvious choice would be the
target subdirectory, but that is currently lost AND it
encapsulates a lot of information BY DESIGN. For example
changes in compiler switches generally aren’t allowed in Felix.
If you want different switches its a different compiler, and you need
a different target. Where this isn’t true, you’re going to suffer a
rebuild into the same cache.

OTOH for multiple projects sharing a standard library, we don’t
want the bound library rebuilt. It varies by target OS but not
by C++ compiler and not by project.

So the core idea is this: for any output list the dependencies including
program files and processors. Processors include say C++ compilers,
noting that changing a compiler mode switch is conceptually using
a distinct compiler. This includes changing system include paths!

Now from the list mark those things as either program files or
processing files, and split the cache on changes to the latter and rebuild it
on changes to the former.

It’s hard to detect changes to processing objects. For actual binaries
we can use the system time stamp, but changes in the time stamp
should rebuild the cache, not split it! We want to split when switches change.
So the compiler binary file is treated more like a program file. All hell breaks
loose if a C++ library changes though.

Note again the dependency checking already (supposedly) takes account
of everything. It doesn’t (shouldn’t) go wrong. It just does too many rebuilds
when splitting would save time at the cost of some more storage.


—
John Skaller
ska...@internode.on.net

[John Skaller2]

So after extensive analysis … the best solution is to do nothing.
Just leave the user to set the cache location.

The flx program is not well written. It started off as a simple script to replace
use of bash and python. Using global variables. It’s more modular now,
but the flow of data setting control variables has been hacked so many times
it really needs a rewrite to be more flexible. The batch processing only just
works and only for Felix, not C++. Ocaml can be compiled but flx doesn’t
understand libraries well. The build tool flx_build_flxg does Ocaml better.

Given the large number of users it does not seem worth the effort at the moment.


—
John Skaller
ska...@internode.on.net

[arabella....@gmail.com]

Was something like "badness types" ever implemented?

[John Skaller2]

> On 13 Dec 2020, at 06:13, arabella....@gmail.com <arabella....@gmail.com> wrote:
>
> Was something like "badness types" ever implemented?

not so far, no.


—
John Skaller
ska...@internode.on.net

[Brandon Barker]

Hi John, 

Just curious if these ideas ended up being implemented in Felix. It sounds like, as a specialized case, this would allow for purity checking, which I seem to recall wasn't implemented a few years ago.

Best,

--
You received this message because you are subscribed to the Google Groups "Felix Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to felix-languag...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/felix-language/24D65508-6CB0-43A1-BDA9-F2FF996A29BE%40internode.on.net.

[John Skaller2]

The uniq typing in Felix is pretty lame. There’s no convenient way to do safe borrowing.
instead, a uniqely typed variable is borrowed by cheating, by taking its address,
because Felix ignores address taking in the unqueness checking algorithm.

i think using a combinator

uniq T

is just wrong. In some general papers EVERY type consists of a pair consisting of what you’d
usually call a type, and also an access permission.

This looks interesting:

https://core.ac.uk/download/pdf/187383998.pdf

The approach here has a calculus of permissions and a notion of restoring permissions
which implements borrowing by using some local permissions. The approach here ONLY
allows permissions on pointers.

The disadvantage is that a non-pointer reference such as an integer in Unix used as
a file handle, cannot be managed. The advantage, especially for Felix, is that
pointers ALREADY have a permissions field. Currently R, W, RW, or none
for readonly, writeonly, readwrite, or noaccess pointers. And it we already
have permission subtyping: you can use a RW pointer where a R or W pointer
is required.

In Felix, operator new creates a RW pointer to a heap object. You can assign this
to a variable of R or W or RW kind because of the subtyping rules.

However you can NOT do this:

var px : &int = new 1;

because the type of the RHS is:

Uniq (&int)

It’s safe to throw uniqueness away but you have to do it explicitly in Felix:

var px: &int = unbox (new 1);

You can do this:

var px = new 1;

but then you get a BIG surprise if you try to pass it to a function requiring
an readonly pointer to int, even though that is safe PROVIDED the pointer
is not passed on by the function (except, recusively, to another function
obeying the same condition). In other words, if the function simply forgets
the pointer after possibly reading from it, all is fine: it just borrowed the pointer.

Borrowing is equivalent to taking and then putting back implicitly.
To implement this explicitly is a serious pain: a function such as “length”
applied to a uniq pointer to a char array, passes a variable containing it,
will deaden the variable which means to reliven it the variable must
be assigned to part of the function’s result.

Now it MAY be possible to use a combinator like this:

Permission(perm, T)

which combines an “unpermissioned” type T with some permissions perm.
to make this work, the Permission combinator would have to be universally
used and then to retain compatibility we’d just say of there was no Permission,
and just a raw T, the permissions would be defaulted:

T == Permission (defaultperm, T)

where defaultperm would probably be “shared” or something. This is more general
that just pointer permissions.

however in the paper above linked, permissions and changes are explicit parts
of the language which gives considerable power and simplicity.

In particular there is some control over aliasing, whilst Felix current machinery
completely ignores address taking because it cannot track the address of a uniquely
typed variable.

—
John Skaller
ska...@internode.on.net

[John Skaller2]

Here’s my current idea.

A realtime(RT) thread is an ordinary Felix thread, except that:

1. It does not respond to a world stop request
2. It cannot call the GC
3. It cannot do anyt async operations
4. It must not use Felix mutex condition variables, or other synchronisation
operations that check for world stop, it can use spnlocks and atomic data.
5. RT threads can use channels to communicate with non-RT threads.
(because communication is done using spinlocks).

An RT thread is created from an ordinary Felix ‘pthread’ class thread
by a service call that does nothing other than increment a count
of realtime threads. Haven’t figured out demotion yet but it will
probably just decrement the count.

World stop is achieved when the GC caller notes that

active_threads - realtime_threads == 1

where the remaining thread is the caller.

There are some nasty issues with higher order stuff. An RT thread
using a higher order function will cause a clone to be created,
and that will involve an allocation, breaking rule 2, since allocations
can trfigger the GC. I’m not sure about invoking procedures through
variables at the moment: they can be recursive and so should be
cloned too.

But roughly RT code should “C like”. In particular most ordinary C++
operations including thread synchronisations are OK. However in
principle, RT code should be a finite state machine (or at least
uses a pre-allocated bounded stack) otherwise it cannot meet
real time performance constraints.

The main hassle with RT threads is to ensure that objects are
always reachable in time separated steps via a path on the heap.
This is because the GC may stop seeing a NULL pointer and
start tracing a path which contains the live pointer, only for the
values to be swapped, in which case the pointed at object is
missed and will be reaped.

The circuit statement has been modified so both channels
and fibres created are stored in local variables of
the current procedure. This means they will be reached,
provided the procedure frame is, even though pointers
to the fibres get moved about during operation by the
synchronous scheduler.



—
John Skaller
ska...@internode.on.net

[John Skaller2]

Control.
=====

Felix programs begin with a main thread for which an scheduler is constructed.
The thread registers with the thread control object.
The main thread may complete operation before other threads however
it does not return control until all other threads have terminated.

The scheduler consists of two parts. The async and sync schedulers.
The operation begins by the construction of a scheduler data object which
is initially an empty set of active fibres and a single running fibre which
executes a continuation of the initial procedure representing the user program.

New fibres can be spawned by the initial fibre. In principle the spawner and spawnee
are added to the active set and on is picked by the scheduler to as the currently
running fibre, however Felix always selects a newly constructed fibre so that
a spawn has the same behaviour as a subroutine call.

A fibre may also launch a coroutine as a process. In this case a new pthread
is created with a scheduler, but it spawnee and spawner share the same active
set. However now, two pthreads are pulling fibres out of the active set to
run instead of one, so the running fibres are now executing concurrently.

The initial scheduler cannot return until the active set is empty and
all processes, including itself, are hung waiting, and, there are no
asynchronous events pending for the (now shared) scheduler data
object. Spawned process scheduler also cannot terminate until
these conditions are met. When there is no work to do the spawned
processes terminate and the main (initial) scheduler then returns.

A fibre can also run a new scheduler. In this case a new scheduler and
scheduler data object is created and runs the initial coroutine as a fibre by a
subroutine call which only returns control when there is no work to do,
as above. Note that during the call the launcher fibre remains the currently
running fibre which suspends the scheduler which is running it.
However another process thread for that schedulers data object
sharing it may continue processing fibres in the scheduler data object.

In other words schedulers can be stacked, with a single thread running
the top of the stack, and the rest of the schedulers in the stack suspended
until it returns, popping the stack. Each of these schedulers is associated
with a distinct scheduler data object (however any one may still be active
if there are other threads sharing access).

Memory
======

Felix manages most objects using a world stop mark sweep garbage collector.
The key to understanding the memory management system is to understand
reachability of objects. Unreachable objects are occasionally reaped by the
collector.

The set of active fibres of a scheduler data object are reachable if one or more
schedulers sharing that data object are reachable. The running fibre of
a scheduler is reachable if the scheduler is reachable. A channel is reachable
if one or more reachable fibres can reach it, and a fibre is also reachable
if a channel on which it is suspended is reachable.

When all the fibres of a scheduler data object are neither running,
active, nor rooted by a pending asynchronous event, there is no work
for that data object or any scheduler sharing the data object, then if no
channels are known other than by fibres of that object, all the fibres
and channels can be deleted. Note that this condition is is best achieved
if channels are only known to fibres of the scheduler object group.
If a channel is saved in a global variable, the channel and fibres
suspended on it cannot be reaped. in the usual case, after construction
of a network, only the fibres which read or write channels should know them.


NOTE: Go-lang gets the correct operation of channels completely wrong.
Felix gets it right. It is not possible to test a channel to see if there is data
available, nor to test if there is a reader for data being written. If there
is no data a reader will suspend permanently: the need to read is
called hunger, and the eternal lack of supply called starvation.
Similarly the need to write when no reader will come is
permanent blockage (constipation .. :-)

Starvation and blockage are the CORRECT way to terminate a fibre
because provided channels are anonymous, it makes the channels
and fibres unreachable.

Asynchronous Events
=================

Felix handles asynchronous events by removing the calling fibre
as the running fibre, making it a root, and handing the fibre
over to an asynchronous event service thread. These are not Felix threads,
Felix supports two async operations at present.

A clock object provides an interface to a thread that manages timed
sleeps for fibres. The thread organises for the OS to signal it when
the earliest timeout will occur, and then unroots the fibre and places
it back on its original scheduler data object. Felix provides a single
system clock, but the user can create any number of clocks.
Each clock runs a separate thread.

CAVEAT: during garbage collection, the final action or returning
a fibre to its original scheduler data object must be inhibited
because the state of the schedulers and data objects must remain
unchanged or the GC may fail. [I don’t think I am checking this!
CHECK AND FIXME IF NECESSARY. Locking the root stl map object
may suffice]

Felix also provides a thread to manage socket events using the OS
native socket notification service.

Synchronisation
============

Channel I/O operations are atomic, and use system spinlocks to ensure atomicity.
Channel I/O can be across threads and schedulers. One machine word is transfered
each time a reader and writer match up. No allocations occur. Channels are the primary
synchronisation device which enable high speed user space context switching
between fibres.

Non-preemptable spinlocks ensure correct operation if available. A pre-emption
in the middle of a spinlock mayl leave on CPU spinning for an unbounded time.

System mutex can be used with caution. If there is a contention, it should
be rapidly resolved by the lock holder. A pre-emption is possible and will
delay lock release. Allocations are NOT permitted inside a system spinlock
because they may trigger a GC which in turn calls for a world stop which
the contending thread cannot respond to because it is waiting on the
lock release. Felix provides a GC aware mutex which is actually a slow
spinlock. After a period, if the lock has not been release, the attempt
at acquisition is abandoned, the world stop flag checked, and if not
set, the a timed wait is again performed on the lock. In addition,
the Felix lock registers the timed wait for notification by a signal if
a world stop is called for, to wake it up more quickly to check
the world stop flag. A thread detecting a world stop suspends until
notified the GC cycle is complete, saving the bounds of it machine
stack in the thread control object so that the GC may conservatively
scan it. This allows allocations in functions, which would not otherwise
allow them. The suspension also save the machine registers on
the stack first, using setjump().

Felix provides condition variables using the same machinery.
Note that locks and condition variables lock the WHOLE PTHREAD not just
a fibre.

Real time threads
==============

A thread can use OS facilities to put it in real time mode.
This usually consists of requesting a certain amount of CPU
with a given time period. The OS should provide that amout
of CPU withing ANY such time period.

A HARD realtime thread also disables preemptions.

Real time threads MUST NOT respond to world stop requests
and so cannot use Felix mutex or condition variables.

RT threads can synchronise with ordinary threads using condition variables:

(a) if the waiter is RT, a standard condition variable is used
(b) if the waiter is Felix, a Felix condition variable is used

This is because signalling is a non-blocking operation and does not involve
a delay or world stop, the signaller does not need to hold the a lock to signal,
although it does need to hold a lock to set the condition being signalled.
[INVESTIGATE!] The same lock must be used. The crucial thing is NOT the holding
of the lock, but (a) atomicity of setting the condition and (b) a barrier to ensure the
condition propagates to the other thread when it comes out of its wait.

NOTES
======

The spinning of condition variables to check world stop should NOT be necessary because
they should be registering for a signal on world stop.

Locks on the other hand are a pain.In principle a mutex is a device which is used to serialise
selected operations so that these operations do not interleave with certain other operations
of other threads. In principle, the period for which a thread holds a lock must be bounded.
In this sense, world stop checks should not be needed for locks.

What this means is that allocations done whilst holding a lock should not trigger a GC.
Unfortunately whilst a no-collecion can be enforced by an explicit memory request,
some memory requests, such as closure formation, are implicit.

More generally the REAL pain with Felix world stop is a fault in OS design:
if a collection is required the collector should be able to forcibly freeze all
threads. Posix does not support this. Llinux, however, does provide thread
stopping signals.

Purpose
======

The main purpose of this article is to highlight the current Felix architecture.
At present, some data like the kind of thread is stored in the scheduler
instead of being associated with a thread. Therefore introducting a “realitime”
thread type is not going to work properly, because the data is in the wrong place.

In addition, code in a coroutine cannot access a lot of data because the pointers
go in the wrong direction: a fibre owns a continuation, but a continuation
cannot find its fibre. Similarly it cannot directly find its scheduler or scheduler
data object. Every continuation and fibre is owned by a particular scheduler
data object however it can be shared by scheduler and thread so it doesn’t
make sense for a coroutine to discover its thread, since the property
is transient not persistent.

—
John Skaller
ska...@internode.on.net

[John Skaller2]

So I was thinking to put thread data in the thread data object.
There are three kinds of threads at the moment: mainline, ordinary, and process.

Additionally we want an indication if a thread is realtime. Currently, an existing thread,
usually and perhaps necessarily, is dynamically promoted to realtime.

The thread kind and real time status do not belong in the async scheduler(s) for the thread
as they are at the moment. If an RT thread runs a nested scheduler, it is operating RT.

Now, I thought to savea pointer to a thread data object of a thread in that thread’s
thread data object, however an ordinary thread can create another and then terminate,
so the pointer would be invalid. So the parent of a scheduler can safely be stored in it,
because parenting by run command creates a stack.

A scheduler, however, can store a pointer to a thread data object, because the system
always “deletes" the scheduler before the thread running it is terminated. [Not sure if it
is deleted or reaped though .. ]

The problem I am trying to resolve is how to manage the world stop condition.


—
John Skaller
ska...@internode.on.net

[John Skaller2]

Dang. I decided to put the thread type in the thread data object and give async scheduler
a pointer to it.

For some reason I don’t understand everything went through until I hit embedding package.
It manages the mainline thread, which is special because it is already running when Felix
starts up.

Then I found the thread control stores the object in an STL map. Pointers to the data
may become invalid if the map is modified .. I don’t know.

On closer inspection of the spawning .. the wrong thread data pointer is passed anyhow:
I’m passing it in to the async scheduler but its thread isn’t spawned yet: the thread data
is created during the spawning.

But there’s worse: in the embed package, the main thread can return control to
the caller, allowing Felix to be embedded. In this case the thread data object
is deleted and the thread count decremented, This is because other threads can
still be running, and the mainline can no longer respond to a world stop request.
It no longer has a stack with Felix pointers on it.

I have to note again a possible race/bug if Felix mainline is started again by the main
thread, which sets up a new async scheduler and re-registers the thread. This had better
not happen during a collection! I need to check the logic is correct.
Actually worse, if the mainline returns whilst the GC is waiting for a world stop,
the thread count is decremented which may complete the world stop, provided
the deparrting mainline remembers to signal the condition variable!! Again I need to
check!

Anyhow the problem is simple: the STL map has to contain a pointer to the thread
data object, not the actual object. It should be new’d with C++ new, and deleted
the same way when a thread returns (including the mainline in an embedding
situation). This should be safe, the async object should be deleted as the
thread returns. Make sure at exactly the right time! This means the pointer
in the async scheduler will disappear. no need to ref count.




—
John Skaller
ska...@internode.on.net

[John Skaller2]

So I have done some tweaks to the control system so the thread kind is associated with
a pthread, and not its scheduler. Every Felix pthread has a scheduler however
with realtime threads coming, the thread kind might change dynamically.

The pthread or process kind are Felix detached threads. The scheduler is created first,
and passed as an argument to the OS thread startup routine. The thread then registers
itself whilst the spawner waits on a condition variable for the registration to complete.
The actual Felix prun routine starts scheduling, but first setting a cache pointer to the
thread data object created on registration, so the scheduler can discover the thread
kind quickly. The scheduler is destroyed before the thread data object so the weak pointer
should always be valid.

The mainline thread is a bit different because it is already running. So it has to be
registered by itself, without a condition variable. Also the mainline thread can
return control to the caller if Felix is embedded, without other threads terminating.
This requires unregistration. If the mainline re-enters Felix, the mainline thread
has to re-register itself.

If a pthread or mainline spawns a process thread, it is just an ordinary new pthread
with its own scheduler EXCEPT that it shares the active fibre list. Thus we now
have a thread pool. Process threads may not terminate until the thread pool
they’re part of has no work to do, and there’s no async jobs pending either.
Then all the process threads terminate, and the pthread that initiated the
pool can return to its caller. If the fibre list was created by the run subroutine,
the calling fibre continues, using the callers pthread (otherwise the pthread terminates,
note this could also be a mainline which terminates Felix, but it might be a separate
detached thread as well.)

The idea for realtime threads is that they work the same as a pthread or process
EXCEPT that they do not respond to world stop requests and don’t issue them either.
In order for this to work the GC must operate whilst the RT thread is running.
For this to work all objects in the RT system must have a stable path from a root.
Note pointer assignments don’t even have to be atomic, the GC will at worst not
mark an object reachable when it is, but the stable path will ensure it is marked
anyhow.

—
John Skaller
ska...@internode.on.net