Re: [Felix-language] [felix] Set form

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

I am going to investigate set forms now.

There is a serious issue with specialisation and deduction here.
Felix is "less than capable" doing this. It's a hard problem.

C++ is a bit better. It can deduce the T in "vector<T>".
Felix can do that kind of thing too, given a functor constant
such as vector, but it cannot do this given a type U instantiated
as F[U] for some F, that would require polyadic deduction.
Note, it CAN do it for array[T,N] because that's just a typedef
for T^N.

So now, the problem is roughly: to, say, fund the union
of two lists representing a set we can just concatenate the lists.
For two set forms, which are also sets, we just make a set form
whose predicate is the disjunction of the argument set forms.
Note, we cannot actually find these predicates, so we have to use

	A \cup B = { x | x \in A or x \in B }

which is horribly inefficient because it makes an object linked
to two other objects and has to use indirect dispatch, and so
cannot optimise the predicate. Eg not (not A) is A but we can't
do that optimisation with set forms.

Anyhow the purpose of this post is to talk about patterns:

	(?x,?y)

At present you can match against

	Some x

you do not need Some ?x or Some var x. This ONLY works in some
cases, where the variable is explicitly the argument of a constructor,
that is, in a form like

	F x

recursively. The choice is made very early in compilation where
pattern matching is reduced to conditionals, in other words,
it is entirely syntax driven, not type information is available.
no lookups can be done.

The solution is found in ATS. In ATS, all constructors have an argument,
possibly unit.  So universally in the form

	F x

x is a variable and F a constructor. The only exception is literals:

	1.0, "hello"

So for example

	Empty

is NOT allowed, it requires an argument:

	Empty ()

because in ATS there's no such thing as a "constant constructor" other
than literals. Felix copies Ocaml, and allows constant constructors
(even though the idea is basically nonsense).

In particular in theory you would have to write

	true(), false()

everywhere (although the parser could define true -> True () to fix that).

BUT luckily in Felix there's another way:

	#Empty

because that means  Empty () in an expression anyhow. And this notation
is ALREADY available in pattern matching.

So now the BIG question: should I enforce the rule??

It is not necessary to change any unions or whatever at this stage.,
It is not necessary to write

	Empty () or #Empty

in any expressions (YET).  That's because the compiler, at the stage
of binding expressions, has type information and can do lookups,
so it knows Empty is a constant constructor. In fact, #Empty will
not work!!!

The only rule is that you must write

	#Empty

in patterns to tell the compiler it is a constant constructor, not a variable
name.

The impact: EVERY SINGLE PATTERN MATCH including ones generated
by the parser WILL HAVE TO BE CHECKED. Every program, every library
file. 

It may be possible to "hack" more than true/false, for example, Empty, None
could just be "hacked".

Another option would be to get rid of constant constructors entirely.
The edits would be easier -- just replace Empty with #Empty everywhere.
IN fact we could even allow

	union opt = Some of int | #None

to mean

	union opt = Some of int | None of unit

But, I don't want to mess with the compiler at the moment...

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