More todos

16 views
Skip to first unread message

John Skaller2

unread,
Feb 19, 2020, 7:53:52 PM2/19/20
to felix google
Gordon has lots of code breaking two rules:

* heaps of closures — inefficient but not illegal
* functions with side effects returning error codes

I have to do something about these. The closure problem comes from user defined
control structures. When the functional arguments are literal function expressions,
these should be optimised away. Felix should provide substitution guarrantees
but instead it’s actually quite bad at closure elimination.

For example:

proc forever (p:1-0) { again:> p; goto again; }

We’d like this to just inline p if it is given literally .. but in theory we can’t!
The problem is local variables have to be preserved across recursions.
So actually p is cloned on the heap each iteration.

This kind of problem cannot occur in a purely functional language.

Still, we expect

forever { … }

to just end up as

again:> … goto again;

since … is given literally. I have to look at closure elimination more closely.


Functions with side effects are used in C/C++ all the time. Felix initially didn’t
allow this: side effects in procedures, none in functions.

Then I added generators, which are functions with side-effects. The rule
to ensure correct sequencing is that calls to generators must be replaced
by variables which are initialised before the expression by calling the generator.

But there is not type for generators, its the same as functions. It also makes
for serious problems, so I changed the rules so that the effects of a generator
must be internal. That is, it can produce a different result each call, like:

rand()

but no one else is allowed to observe the effect. This allows iterators,
but disallows common idiomatic C like stuff where you do something
and return an error code.

the procedural model which is legal:

var x : int;
call operation(&x);
if x == 0 do ….


is way too clumbsy to be practical. And Gordon has code like:

dowhile { … } { func() };

which exhibits BOTH the above problems: closures and a side
effecting operation func(), the result of which controls looping.

It only works BECAUSE Felix is so bad at closure elimination!





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





John Skaller2

unread,
Feb 19, 2020, 9:10:29 PM2/19/20
to felix google
Well actually:

proc dowhile (bdy: unit->void) (cond: unit->bool) {
xrepeat:>
bdy;
if cond() goto xrepeat; //low level conditional jump
}

var x = 10;
dowhile { println$ "X"; --x; } { x > 0 };

generates:

void _init_(FLX_APAR_DECL_ONLY){
PTF x = 10; //init
xrepeat_L66176:;
{
_a17556t_66193 _tmp66201 = ::std::string("X") + ::std::string("\n") ;
::flx::rtl::ioutil::write(stdout,((_tmp66201)));
}
fflush(stdout);
{
int* _tmp66202 = (int*)&PTF x;
--*((_tmp66202));
}
if((0 < PTF x)) goto xrepeat_L66176;
}


So the two closures are actually both fully inlined. What gets me is that even if I say “noinline” on dowhile,
it’s still inlined!

Hmmm.. dang disobedient cat .. other tests show actually Felix is pretty good inlining closures
given literally!




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





John Skaller2

unread,
Feb 19, 2020, 9:19:24 PM2/19/20
to felix google

So how about if you have to name functions with side effects like:

sfun @fred (): int { … }

so in any expression it is clear there are effects?

x + @fred()

One could also required

!obs

if the function isn’t pure. Hmmm. We could then have

@++x

returning x + 1 as well as incrementing it.

There’s a trick though: neither is transitiive, that is, a function containing
an effectful function doesn’t itself necessarily have side effects. It depends
if the effects are local.



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





Keean Schupke

unread,
Feb 20, 2020, 3:22:43 AM2/20/20
to felix google
I don't think generators really have side effects. The output of a generator can be considered a lazy list, which is a fundamental type in purely functional languages like Haskell.

The generator function itself may have side-effects, but that is separate from its output stream. My best understanding of this would be that 'initialising' the generator has side effects, but sending a stream to or reading a stream fr does not, it's just lazily processing a list.

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/915A4B25-392D-42AC-9634-AEACC9C96C79%40internode.on.net.

John Skaller2

unread,
Feb 20, 2020, 6:56:45 AM2/20/20
to felix google


> On 20 Feb 2020, at 19:22, Keean Schupke <ke...@fry-it.com> wrote:
>
> I don't think generators really have side effects. The output of a generator can be considered a lazy list, which is a fundamental type in purely functional languages like Haskell.
>
> The generator function itself may have side-effects, but that is separate from its output stream. My best understanding of this would be that 'initialising' the generator has side effects, but sending a stream to or reading a stream fr does not, it's just lazily processing a list.

I agree. It’s a good viewpoint. Thanks!

I think this is reflected in my intuition that a generator may have
effects on its internal state only, recording where it is up to in the stream so to speak.

The problem is really syntax. Generators get used “like functions”. As usual lots of things
do not fit into the functional syntax of expressions: it means an expression containing a generator
is not referentially transparent.

I think this is just fine provided it is syntactically observable.

To be sure, I’d also like to distinguish impure functions (which read variables
that can change) and pure functions, which always produce the same value
for given arguments.

But in a language you cannot have too many distinctions.

The real problem is that Felix has to model C/C++ and so has to properly
reflect some idiomic usage. The strictly correct modelling of almost every
Posix function, which has an effect on the environment but returns an
error code, is very hard unless we make allowance for this idiom somehow.

Felix functions actually already have the general form:

D ->[E] C

where D is the domain, C the codomain, and E is some type indicating effects.
I have never used E, it defaults to unit. The idea is that polymorphism functions and
subtyping rules might help manage effects in HOFS. The problem is I do not
believe in the FP community's idea of effects at all. I think they try to lump
entirely unrelated things that don’t fit into the naive FP model into the notion
of effects and that’s just wrong.

A mutation is an effect .. unless it is managed by linear typing or a monad.
Its nonsense. Exceptions: its not an effect, if you correctly model it with
CPS. Its just not the usual subroutine idea of control flow. I/O .. etc etc ..
these are all quite different IMHO.

Anyhow, a certain class of effects can be managed by effect type:
a polymorphic function can “inherit” the aggregate of argument
effects easily. The problem is that this model only works for some
kinds of effects. So in the end I gave up trying to find a sane
way to use E.




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





Reply all
Reply to author
Forward
0 new messages