Docs

[John Skaller2]

I am currently updating the ReadTheDocs reference manual, it was never even
close to complete. I hope to fix this but HELP IS NEEDED, at least proof reading!
If not CONTRIBUTING!

https://felix.readthedocs.io/en/latest/

There is A LOT TO DO.

There’s also code to validate, complete, fix, and write, especially C++ thread stuff
some of which currently bombs!

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

[John Skaller2]

Patterns come in two forms: refutable and irrefutable. An irrefutable pattern
is one that can’t fail. Here is the algo:

let rec is_irrefutable pat =
let irf pat = is_irrefutable pat in
match pat with
| PAT_alt _ -> assert false
| PAT_none _ -> assert false
| PAT_literal _ -> false

(* ranges *)
| PAT_range _ -> false

(* other *)
| PAT_name _ -> true
| PAT_tuple (_,pats) -> fold_left (fun acc v -> acc && irf v) true pats
| PAT_tuple_cons (_,p1,p2) -> irf p1 && irf p2
| PAT_tuple_snoc (_,p1,p2) -> irf p1 && irf p2
| PAT_any _ -> true
| PAT_setform_any _ -> true
| PAT_const_ctor _ -> false
| PAT_nonconst_ctor _ -> false
| PAT_ho_ctor _ -> false
| PAT_subtype _ -> false
| PAT_const_variant _ -> false
| PAT_nonconst_variant _ -> false
| PAT_record (_,rpats)
| PAT_polyrecord (_,rpats,_) -> fold_left (fun acc (_,p) -> acc && irf p) true rpats

| PAT_expr _ -> assert false
| PAT_as (_,pat,_) -> irf pat
| PAT_with (_,pat,_) -> irf pat
| PAT_when (_,pat,_) -> false
| PAT_coercion (_,pat,_) -> irf pat


To understand this: product matches, for tuples or records, are *potentially* irrefutable
meaning they’re irrefutable if their sub-components are. Match on anything or a variable
is irrefutable. Technically a match on a value is irrefutable if the type has only one value,
such as unit.

SO here’s the thing: we should allow any irrefutable pattern match as a function parameter.
At present, only a tuple of variables or tuples (recursively) is allowed, although direct calls
also allow a record with the parameter names as fields (but no recursion there!).

OTOH let forms allow any pattern eg:

let Some x = ….

and just abort if the match fails.

Option types are a special case because there’s some good reason to force extract the
some case inline with a single operator: Swift does that. At present you can do it in Felix
with

(let Some v = e in v)

or

fun get[T] (e:opt[T) = match e with Some v => v endmatch;
… e.get …

Swift writes

e!

for this (and defines the type as T? as well .. nice .. and a value of the type
is also written v? … mmm ok !!

ANYHOW the interesting thing here is that the algorithm is dynamic but
we can do it *statically* with polymorphic variants and subtyping using
open recursion!

This means I could replace the parameter data for (unbound) function definitions
with irrefutable patterns.I just extended it to nested tuples. The change took ages
and we never completed (axiom check still isn’t fixed for example).


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

[John Skaller2]

I’m having to rething slices as bit.

What’s a slice? Well, lets try this definition:

“A slice is any compact subset of a totally ordered set.”

For the integers including +/- infinity with the usual ordering there are exactly five
classes of slice:

* the empty set
* all the integers
* all the integers above and including N
* all the integers below and including X
* a subrange N to X inclusive

Note I had to throw in +/- infinity as upper and lower bounds.

Set intersection is a binary operation on the set of all slices.
(the intersection of two slices is a slice).

In computing integer representations like “int” or “long” etc can be
considered as subranges of the integers, so each type can be
considered as a slice. In this case, min and max value the type
can represent are the ends of the slice.

The current representation is:

union slice[T] =
| Slice_all
| Slice_from of T
| Slice_from_counted of T * T /* second arg is count */
| Slice_to_incl of T
| Slice_to_excl of T
| Slice_range_incl of T * T
| Slice_range_excl of T * T
| Slice_one of T
| Slice_none
;

Now the problem I’m trying to solve is this:

At present you can do this:

astring.[slice]

and it calculates a substring:

fun subscript (x:string, s:slice[int]):string =>
match s with
| #Slice_all => substring (x, 0, x.len.int)
| Slice_from (start) => copyfrom (x, start)
| Slice_to_incl (end) => copyto (x, end + 1)
| Slice_to_excl (end) => copyto (x, end)
| Slice_range_incl (start, end) => substring (x, start, end + 1)
| Slice_range_excl (start, end) => substring (x, start, end)
| Slice_from_counted (start, count) => substring (x,start, start + count)
| Slice_one (index) => string x.[index]
endmatch
;

However it cheats!

fun substring: string * !ints * !ints -> string =
"::flx::rtl::strutil::substr($1:assign,$2:assign,$3:assign)" requires package "flx_strutil";

// normalise string positions Python style
// note substr requires 0<=b<=size, 0<=n,
// however n>size is OK
template<class T>
basic_string<T> substr(basic_string<T> const &s, int b, int e)
{
int n = s.size();
if(b<0) b=b+n;
if(b<0) b=0;
if(b>=n) b=n;
if(e<0) e=e+n;
if(e<0) e=0;
if(e>=n) e=n;
int m = e-b;
if(m<0) m=0;
return s.substr(b,m);
}

The idea is from Python, that -1 is the last char in the string,
-2 is the second last, etc. The reason is to get the tail of a string,
you have to refer to the end of the string and work backwards.
The algorithm above allows negative indices, it translates them
to positive ones by adding on the length of the string,
and then clips the resulting “slice” by intersecting it with the
slice 0..n-1 where n is the string length. At least I hope it does :)

At the moment you cannot slice arrays! So what I was looking
at was slicing varray to a varray, darray, bsarray, and sarray.
A slice of an farray (T^N kind of array) can’t be an farray because
the arguments of the slice are not known at compile time
so if done it would have to be at least a darray.

I was also thinking about slicing lists.

Also on top of that compehensions with slices, that is,
building a varray, etc or list from a slice (that is,
a list comprehension based on a slice would be a list
of integers in the range of the slice). For example:

([ 1..3 ]) == ([1,2,3])

The “negative indices” thing worries me. The math doesn’t feel right.

There’s another problem. Given a slice over int, suppose we want
to “convert” that to say long, or size. The union representation used
at the moment handles that fine provided the conversions go through.
More generally, the idea would be to define the result as the
intersection of the theoretical slice with the slice of the subrange
of integers supported by the target type. So the math is well founded,
even if the target is an unsigned type.

Now consider a slice of a varray. Obviously the definition is
to elements in the positions which are the intersection of the
range of the array 0..n-1 where n is the length of the array,
and the slice, converted to type size.

The conversion is tricky! If the slice contains say integer value -42,
we cannot just convert it to unsigned because that would be

#maxval[size] - 42uz

which is a rather large number. Actually we have to clip the -42
to zero.

The problem is that #minval[T] and #maval[T] are cleverly
well defined because they’re of type T. So promotions and demotions
are kind of tricky!

The core problem of negative indices is that given a string *expression*
we want to grab the tail of, there is no “logical” representation for
the end of the string. You would have to write this with only non-negative
indices:

let s = expr in
let n = len s in
let first = if first < 0 then n + first in
let last = if last < 0 then n + last in
s.[first..last]

The problem is that we don’t know the length of the string and its hard
to know it because its an expression. That’s why the substring function
“cheats” by hacking the slice, because the function has an actual string
now to get a length of. The problem is that

-3 .. -1

is a valid slice: -3,-2,-1 and its intersection with the range of the string
is always empty. The “cheat” depends on a second way of indexing
strings from the end, using negative numbers, but the WRONG
results are calculated for

s.[3 .. -1]

The calculation I’m using yields elements 3,4,5…n-1, but the
slice 3..-1 is actually empty!

What I need is a way to get stuff from the end of a string or varray
or whatever which isn’t hacked!

C++ uses a special value for the end which is the maxval of type size_t:

static const size_t npos = -1;

But this is a hack too.

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

[blu...@fi.muni.cz]

Hi,

> The idea is from Python, that -1 is the last char in the string,
> -2 is the second last, etc.

[...]

> The calculation I’m using yields elements 3,4,5…n-1, but the
> slice 3..-1 is actually empty!
>
> What I need is a way to get stuff from the end of a string or varray
> or whatever which isn’t hacked!

To do this cleanly, I think you cannot use integers as indices. Instead
you need a time that contains transfinite natural numbers:

0,1,2,3,... ...,omega-2,omega-1,omega,omega+1,omega+2,...

Then omega-1 would refer to the last element of an string/array.
As you probably don't need indices above omega-1, we can simplify this
to:

0,1,2,3,... ... omega-3,omega-2,omega-1.

We can get this type by equipping the integers with a different ordering:

0,1,2,3,... ...,-3,-2,-1

where the negative numbers are larger than the positive. So, we get
exactly what you are using right now, except that conceptually you are
not working with a slice of type int but of type "transfinite int".

Achim

[John Skaller2]

But what does a slice look like?

Slices aren’t just used for extracting substrings. you can do this:

for i in first .. last do …

you can also do this:

for i in first.. do ….


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

[blu...@fi.muni.cz]

> >> The idea is from Python, that -1 is the last char in the string,
> >> -2 is the second last, etc.
> > [...]
> >> The calculation I’m using yields elements 3,4,5…n-1, but the
> >> slice 3..-1 is actually empty!
> >>
> >> What I need is a way to get stuff from the end of a string or varray
> >> or whatever which isn’t hacked!
> >
> > To do this cleanly, I think you cannot use integers as indices. Instead
> > you need a time that contains transfinite natural numbers:
> >
> > 0,1,2,3,... ...,omega-2,omega-1,omega,omega+1,omega+2,...
> >
> > Then omega-1 would refer to the last element of an string/array.
> > As you probably don't need indices above omega-1, we can simplify this
> > to:
> >
> > 0,1,2,3,... ... omega-3,omega-2,omega-1.
> >
> > We can get this type by equipping the integers with a different ordering:
> >
> > 0,1,2,3,... ...,-3,-2,-1
> >
> > where the negative numbers are larger than the positive. So, we get
> > exactly what you are using right now, except that conceptually you are
> > not working with a slice of type int but of type “transfinite int".
>
> But what does a slice look like?

The same as an integer, i.e., twos-complement.

> Slices aren’t just used for extracting substrings. you can do this:
>
> for i in first .. last do …
>
> you can also do this:
>
> for i in first.. do ….

These would iterate over all values between first and last, or first and
the maximal value. Which values these are depends, of course, on the
type of i. If i is an integer,

for i in 5 .. -3 do ...

would iterate over nothing, if it is a "transfinite int" it would
iterate over

5,6,7,..., max_int, min_int, min_int+1,..., -3

(which is not that useful).

Achim

[John Skaller2]

>>
>> But what does a slice look like?
>
> The same as an integer, i.e., twos-complement.
>
>> Slices aren’t just used for extracting substrings. you can do this:
>>
>> for i in first .. last do …
>>
>> you can also do this:
>>
>> for i in first.. do ….
>
> These would iterate over all values between first and last, or first and
> the maximal value. Which values these are depends, of course, on the
> type of i. If i is an integer,
>
> for i in 5 .. -3 do ...
>
> would iterate over nothing, if it is a "transfinite int" it would
> iterate over
>
> 5,6,7,..., max_int, min_int, min_int+1,..., -3
>
> (which is not that useful).

It is if you intersect it with some other range, or, if you take its complement.

The problem I have is that

-1 .. +1

is defined as the values

{ i | i >= -1 & i <= +1 }


There are no i >= -1 that’s the maximum value (with your ordering).
Therefore the range is empty.


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

[blu...@fi.muni.cz]

> The problem I have is that
>
> -1 .. +1
>
> is defined as the values
>
> { i | i >= -1 & i <= +1 }
>
> There are no i >= -1 that’s the maximum value (with your ordering).
> Therefore the range is empty.

Yes. That means you want to support both types of indices: ints and
"transfinite ints".

for i : int in -1 .. +1 => -1, 0, 1
for i : tint in -1 .. +1 => empty

Achim

[John Skaller2]

Maybe, but that requires an actual design.

Currently the driver is syntax:

a..b
a..<b
a..+n
a..
..b
..

These notations are what i have at the moment, mapping to the variant type I showed before.
In princple, the relevant rangers are the intersection of the theoretical integer ranges and
the span of the the type the arguments are expressed in. Hence

..b

actually means from min of typeof(b) to b. The notation .. has no type .. :-)

Underneath the variant is explicit about the “open” ends so that if, for example,
a slice is converted from “short” to “long” the min and max span will increase
from minal[short]..maxval[short] to minval[long]..maxval[long].

This could also be done using an \infinity symbol.

Now, Felix has notation for strings:

s.[a to b]
s.[to b]
s.[to]

etc .. this is old notation. There is also

s.[i]

These notations support negative indices like Python.
However “a to b” is not an object, its just special syntax for
calling functions:

copyfrom(s,a)
copyto(s,b)
substring(s,a,b)

What’s worse is that Felix has loops:

for i = a upto b do …
for var j = b downto c do …

which is more special notation. The idea is that slices get rid of the need
for this special stuff.

Slices admit iterators which generate the values in the given range:

iterator: slice -> 1 -> opt[int]

which can be used with for loops:

for i in slice do …

and the notation:

s.[i] // i integer, means subscript, the char at position i
s.[slice] // means the chars of s indexed by the slice iterator

Note that the implemention of s.[slice] doesn’t actually run the slice
iterator, it just calculates the range needed to give to “substr” function.
And it cheats by doing the negative values crap.

I can define

slice s == s.slice

to mean something different. But really I want to get rid of the special s.[..] notation.

Note Felix has “generalised slices” too (which allow intersections, unions,
complements maps and filters). I’m not sure I like them.

At present, I’m documenting Felix:

https://felix.readthedocs.io/en/latest/index.html
https://felix-library-packages.readthedocs.io/en/latest/

and some other stuff. In writing the manual I had a lot of hassles deciding
how to organise it. In the end I decided the key organising principle
should be ALGEBRA.

Its amazing how, when trying to explain something one finds incoherencies,
bad syntax, bugs, incompleteness and other stuff. I want to say slices
can be applied to strings and arrays and lists and indeed any sequential
data structure. BUT the string slicing is hacked (as being discussed here)
and there is actually NO slicing for arrays.

And there’s another principle: the notation (syntax) should reflect the algeraic
structure. Roughly this is what type classes can do. Contrary to popular belief
type classes don’t have any important semantics. All they do is package up
related functions to make it easy to pass the package around. There’s nothing
you cannot do with parametric polymorphism, its just a pain passing
all the arguments. And type classes help enforce consistent notation.

BTW: what R does is actually interesting. It uses modular arithmetic.
For example

(1,2,3,4) * (1,2) = (1,4,3,8)

Anyhow the point is, we don’t just need an algebra but notation that makes
sense to the user as well.


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

[blu...@fi.muni.cz]

> > Yes. That means you want to support both types of indices: ints and
> > "transfinite ints".
> >
> > for i : int in -1 .. +1 => -1, 0, 1
> > for i : tint in -1 .. +1 => empty
> >
>
> Maybe, but that requires an actual design.

Well, that's the joy of language design. ;-)

Anyway, as far as I can see you need to decide on:

- whether slices are types or values
- a good syntax for slices
- a set of operations associated with slices

Something like (in pseudo code):

slice(a) := a * a

x .. y := (x,y)

iterate : slice(a) -> (a -> 1) -> 1
subarray : array(a) -> slice(a) -> array(a)
iter_array : array(a) -> slice(a) -> (a -> 1) -> 1



By the way, yesterday I stumbled upon the language "Pony" which, like
Felix, tries to get concurrency right. In particular, it has a linear
type system modelling ownership and they have a notion of when two
fibres are independent and when they must be scheduled serially. In case
you haven't seen it yet, you might want to take a look for inspiration.

Achim

[blu...@fi.muni.cz]

blu...@fi.muni.cz wrote:
> iterate : slice(a) -> (a -> 1) -> 1
> subarray : array(a) -> slice(a) -> array(a)
> iter_array : array(a) -> slice(a) -> (a -> 1) -> 1

Of course that should read:

subarray : array(a) -> slice(int) -> array(a)
subarray : array(a) -> slice(tint) -> array(a)
iter_array : array(a) -> slice(int) -> (a -> 1) -> 1
iter_array : array(a) -> slice(itnt) -> (a -> 1) -> 1

Achim

[John Skaller2]

> On 7 Aug 2018, at 20:30, blu...@fi.muni.cz wrote:
>
>>> Yes. That means you want to support both types of indices: ints and
>>> "transfinite ints".
>>>
>>> for i : int in -1 .. +1 => -1, 0, 1
>>> for i : tint in -1 .. +1 => empty
>>>
>>
>> Maybe, but that requires an actual design.
>
> Well, that's the joy of language design. ;-)

Yeah .. if only i were paid for the pain :)

>
> Anyway, as far as I can see you need to decide on:
>
> - whether slices are types or values

They’re values because they’e constructed dynamically.
[Of course there is a slice type too]

This means a slice of a Felix array T^N cannot be a
Felix array T^M because M would have to be known at
compile time.

> - a good syntax for slices

Actually the hardest part.

> - a set of operations associated with slices

Yes. But the problem is how to model the idea of getting
the “last n chars of a string”.

Its easy to get the n chars starting at position m
but how do you *also* get from the end.

Perhaps two operations:

slice_from_start (str, slice)
sliice_from_end(str, slice)

where the second operation simply starts the coordinates of a string
at the end and goes backwards like this:

43210

So slice 1..3 “from end” would be 321. That’s not what Felix does now ..
but it makes sense. One kind of simple slice, two ways to use it to get
a substring.

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

[John Skaller2]

Ah ok. Here we go:

s = “filename.ext\n”

Get the extension!

Solution:

s.rev.(1..3).rev

Reverse the string, get chars 123 (exclude the trailing newline and the dot), then reverse the result.

So we need two operations: apply a slice to a sequence, and, reverse the sequence.

Of course that’s the definition, we don’t want to *actually* reverse the sequence.

The point is that we only need ordinary slices to do this, if we define that,
the other operation follows.

If you want to get the middle of the string skipping the first N and last M chars,
then we use

s.(N..).rev.(M..).rev

I think these two operations (apply slice and reverse data) can do everything.
Any counter examples??

So now the main problem is a notation which expresses this but allows
the calculations to be done without actually reversing the string.

Actually for lists .. to extract a sublist you always end up with a reversed
sublist anyhow!

So if a string has length N then

s.rev.(B..E).rev = s.(N-E-1 .. N-B-1)

So in our original example:

filename.ext\n
0-7, dot at 8,9-11 for ext, \n at 12, lenth=13
rev.(1..3).rev = 13-3-1 ..13-1-1 = 9..11

Yep.

The nasty here is that we can’t write

rev.(B-E).rev

in Felix because we cannot overload “rev” without an argument type.
If you write

“kihjkhg”.rev

its

rev: string -> ?

and we fine ? by looking up rev of string. So actually we define:

backindex: slice -> int -> slice

in other words, backindex take a slice and returns a function
accepting an int and returning a slice. Actually we do

fwdindex: slice->int->slice

as well because we need the string length argument to clip
the slice in that case anyhow.

Hmm .. ok .. the math is fine .. just need the notation.




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