Re: [Felix-language] [felix] Return from

[john s. <sk...@us...>]

On 20/08/2012, at 5:48 PM, Dobes Vandermeer wrote:

> On Sun, Aug 19, 2012 at 10:50 PM, john skaller <sk...@us...> wrote:
> 
> On 20/08/2012, at 3:07 PM, Dobes Vandermeer wrote:> Maybe I've been overly brainwashed by the "goto haters" out there but I don't think returning an opt[] or other union type is all that bad.
> 
> You're missing the context. Consider this:
> 
>         fold_left (fun (acc:bool) (elt:bool) => acc and elt) somelistofbool;
> 
> This calculates the "and" of all the bools in the list. On average it is twice
> as slow as it needs to be because it doesn't exit as soon as the accumulator
> becomes false. Once you're inside the fold, you cannot stop it.
> 
> Wouldn't it sense to define a "contains" operations that searches for "false" instead?

Probably yes, but that's just a solution to one simple example, which is merely
intended to illustrate a point.

> 
> It seems like any algorithm that requires a goto can be rearranged into one that doesn't require it and is just as fast.

No. I already cited several common cases where you cannot do so.

Try merging two sorted lists. You cannot do it optimally without a goto.
Optimally means you never test anything more than once, or perform
any operation more than once.

So you may "advance" a list, or test the head of a list, at most once
before deciding which element to output. You can use lines in files
instead if you want. There's a difference between Pascal files
where you must test for eof before reading, and C files where
to "have a go" and check if it worked afterwards.

The core of  the problem is that when both lists are exhausted you have
to exit, you're finished. But when only one list is exhausted you copy the
rest of the other one out.

Remember. You cannot test the value on the list more than once.

It's quite clear this is trivial with a finite state machine -- which of course
is a fundamental control structure exclusively based on gotos.

BTW: you may find a solution. I never did. I had to write a lot of merges
in the days of tape drives :)

> Strange, in Scala they just offer versions of the operation with an early exit.  For example you can define operations like foldWhile() that stop if you return None and return the last non-None value it got.

That would be interesting. And you can probably implement such a function with iter and
fast exit. That's what its for, use in libraries to make operations that themselves don't
need such dangerous things as gotos.

> This non-local goto thing looks more like something you were intending to make use of ...
>  
> Non-local gotos sound evil, but we have to have them, to allow wrapping
> code in blocks (functions or procedures) temporarily, then inlining them.
> That makes the previously non-local goto local again, but this happens
> after type checking.
> 
> Hmmm I don't understand what you're saying here, maybe it's too late at night.

When felix sees something complicated, it just translates it into functions/procedures
and applications/calls. 

It doesn't know what high level things are.

There are no conditional expressions
because .. if/then/else is a macro .. it actually reduces to ..

	match cond with
	| true => trueexpr
	| false => falseexpr
	endmatch

And there are no matches in Felix either! It actually reduces to ..
a chain of conditional gotos.

But we need an expression! What to do?? Felix is stupid,
it can't make complicated expressions (because C can't either).

So put the statements in a function and apply it!

That's what the desugaring does. It puts every complicated expression construction
into a function and converts it to statements using assignments and goto, then just
applies the function.

There's name for this: all compilers do it. Its called lambda-lifting.

Most compilers lambda lift late. I wish Felix did too, but it doesn't.
It lambda-lifts early. Matches get removed in desugaring phase,
long before the symbol table is built.

Variable declarations like:

	val x = 1

are split into a declaration:

	var x :  typeof(1);

and an assignment:

	x = 1;

Desugaring reduces your code to the a very small set of primitive operations.
binding reduces the set even further.

Felix is actually a rich language, it has something like 12 operations.
most functional languages only have 2 or 3 : almost everything is "application"
and "closure formation".

> I'm not a huge fan of exceptions either, but at least they can be "caught" and you can use a "finally" block to release any resources you've accumulated on the way in.  The non-local goto doesn't just bypass that, it makes it impossible.

So don't use it when you're holding on to resources!

> Perhaps this just means another feature is needed which allow one to do a try ... finally ... sequence that the non-local goto agrees to call on its way by.

No it just means you have to learn how to program in a language that doesn't use
exceptions like Java does. The problems you talk about just don't arise because
you cannot get asynchronous exceptions like "invalid cast" or "typeerror" or
whatever crap you get in Java when you least expect it.

It can't happen. you only get an exception when you deliberately throw one,
and you don't need exceptions much because you have a host of other ways
to do things .. such as option types.

In any case the non-local goto isn't an exception, its just a jump to a statically
visible target. It is in fact a very bugged type of delimited continuation.

--
john skaller
sk...@us...
http://felix-lang.org