merging records and tuples

[john skaller]

I need some help with notation!
And perhaps theory. Here is the idea.

Felix has records with scoped labels. This means
you can have duplicate labels:

var r = (a=1, a=2, b=3, a=4);

Currently,

r.a

returns 1, that is, the projection a returns the first a it finds.
You can get the second a like this:

(r without a).a

[Thanks to Ryan for the without keyword]

However this is clearly messy! A more general notation
would be like:

r # a @ 0

where the a projection fetches ALL the a’s, and then the
numerical index fetches the n’th one. This notation conflicts
with the existing notation (which is the main problem I suspect).

But now here is another record:

(=1, =2, =3)

you see I left out the field label. We could just write that like this:

(1,2,3)

i.e. it is nothing more than a tuple! So using the above notation:

r # @ 0

would be 1, that is, we leave out the field name. We can view

#@

as tuple access. So the theoretical view is of two operators,
a field projection returning a tuple of all the values of a given
field and a tuple projection selecting one of them. The currect
field projection is composed of the new field selector
followed by a projection getting the first value. The current
tuple projection becomes instead a field selector for the empty
field followed by the new tuple projection.

We want a notation which is transparent in the sense it
LOOKS like we have records and tuples, but actually we
have only one type: a scoped record type allowing empty
field names.

Note that with a polyrecord like r below:

fun f[T] (r: (a=1, b=2 | T) ) => …

there is an obvious constraint on the field grabber and
numeric selector (you can’t fetch field x, even if its in T,
or element 5 of field a, even if it is in T).

SO unifying tuples and records into a single structural
type seems like a good idea, if only I can find suitable
notation.

Note BTW that the tuple form

U ** V ** W …

now must also be unified with the record form.



—
john skaller
ska...@users.sourceforge.net
http://felix-lang.org

[Garrett Bluma]

On Fri, Dec 11, 2015 at 7:43 AM, john skaller <ska...@users.sourceforge.net> wrote:

I need some help with notation!
And perhaps theory. Here is the idea.

Felix has records with scoped labels. This means
you can have duplicate labels:

        var r = (a=1, a=2, b=3, a=4);

Currently,

        r.a

returns 1, that is, the projection a returns the first a it finds.
You can get the second a like this:

        (r without a).a

I can follow this easily so far.

 

[Thanks to Ryan for the without keyword]

However this is clearly messy! A more general notation
would be like:

        r # a @ 0

If I understand it right, 

    # means 'with-only' or 'prune-all-except' and returns a tuple

    @ means 'take the nth element' or standard projection.

It seems to me like we there are a couple issues.

1.) We already have a projection function (the dot operator and a number) and we should think twice about adding a second one that does the same thing. 

    my_record # a @ 0

is equivalent to

    (my_record # a).0

Yet the second one is the standard for projection for tuples. Also, how is

    r # @ 0

intended to be different from this?

    r.0

In my mind, they are functionally similar. In the #@ version, we are applying an operation to remove labels and then access an element by position. What if the projection on a named record could do this conversion automatically? That would simplify the language instead of encumbering it. The naive approach of just trying to get the 2nd element of a record could "just work". Instead, you might go through the process

  * user writes "r.0" in their program

  * compiler error, "r is a named record, cannot do projection on this"

  * user says "what the heck?, it's supposed to be a tuple"

  * user looks into syntax to see that tuples and records share some functionality

  * user eventually stumbles on to the r # @ 0 example in one page of the docs

  * user adds the line and can now get the projection, but doesn't understand why

I do understand that there's some difficulty here. Namely, how do we differentiate between names and variables?

If we want to get the nth element of a tuple, we could do this:

    var n = 0;

    println$ r.n;

but if we want to get the 'fname' field of a record, we do this:

    println$ r.fname;

So how do we decide if 'fname' is a variable (for projection) or it's own projection function? One idea is to just look at the bindings:

* if the identifier to the right of the period is bound and numeric, then we can use it as a projection;

* if the identifier to the right of the period is a function, treat it like as normal (reverse composition);

* if the identifier to the right of the period is not bound, error out.

Perhaps there may even be a way to just make things "Projectable," like an instance of class. That way, if a row polymorphic record were an instance, we could use the specific projection (like #@) to do something tailored to the data type, while opening doors for other data types.

Like what if we could do something like this?

    instance Projectable[CSV_File] {

        gen proj_get(n:int):string => ...;

        proc proj_set(n:int, s:string) => ...;

    }

    var a = CSV_File("filename.csv");

    var line0 = a.0;

2.) The # symbol is part of a group of operations that should be similar in appearance. I'm suggesting 'withonly' as a substitution.

    r with (metadata=(likes_ice_cream=True))

    r without metadata

    r withonly email_address   // r # email_address in your notation

The # is just a little jarring. If we wanted to go with symbolic notation, I'd argue for something more arithmetic. Extension is like addition, exclusion is like subtraction, and isolation to a single name (or set of names) is like modulation.

    r + (metadata=(likes_ice_cream=True))   // "+" equivalent to "with"

    r - metadata                   // "-" equivalent to "without"

    r % email_address         // "%" equivalent to "withonly"

On a different train of thought, we could include exponentials in the selector expressions, this could also provide the means of taking some number of elements from a list. 

    r without a^3 // eliminate 3 a's from r

    r withonly a^3  // select only three a's from r

Or arithmetically,

    r - a^3

    r % a^3

--

Garrett

[john skaller]

> If I understand it right,
>
> # means ‘with-only' or 'prune-all-except' and returns a tuple

no actually it returns a super-record

> @ means ‘take the nth element' or standard projection.

and @ selects the n’th scoped field of a record.

Neither of these operations is the current record or tuple
projection.

Then we just define

r.a —> r # a @ 0 // define record projection
r.1 —> r # _ @ 1 // define tuple projection

where I wrote _ for “blank name” (not a match all).

In other words these two new operators combine to make
“ordinary records” and “tuples” a special case of
scoped records (which we already have) with missing
field names (which we already have too).

You can actually have a blank name already!

You may not know it but Felix allows ANY string to be an identifier.
There is a special notation when the parser won’t recognise it:

n”#$%^&*”

It’s called a name string. So of course you can do

n””

for a name of no characters.

So the point I am trying to make is this: instead of separate record and tuple
types, we move to a SINGLE unified record type, tuples are just a
special case of records, as arrays are again a special case of tuples.

To make this work, we need two new operators: a field name extractor
which takes a record, and returns a record with supertype consisting
of the record with all the fields of the given name, and a sequence extractor
which picks the n’th one. The first operator is well defined in all cases,
it can return an empty record () if the field doesn’t exist.

The second operator requires the n’th argument to exist so it can
fail.

Given those new operators, the existing record and tuple projections are
just composite functions, and I mean *composite* literally. The special
cases are created by adding a constant function into the mix, i.e.
“currying” the general projection with a blank field constant function
and a 0 sequence selector constant function.

This is mathematically very beautiful.

There is actually more. Felix has a thing called a generalised projection.

Given a tuple normally you have to use a constant index so you know
the return type of the projection. Except for arrays, where the index
can be an expression, since all the elements have the same type.

But this is all a special case of a generalised projection! In general
you can index a tuple with an expression! For example given a tuple
of type

int * string * long

a generalised projection is a map

int * string * long -> 3 -> int + string + long


In other words every tuple type T is ALREADY an array, with elements having
the type ~T where ~ means “dual”. Sums are the dual of products.

So actually AGAIN we really ONLY need a generalised projection plus specialising
operators. In category theory:

\delta = diagonal function = dup

is the pairwise version of this:

fun diag[T] (x:T) => x,x


and there is a corresponding

\nabla = codiagonal function = select_one

is the pairwise version of this. \nabla is an upside down greek delta.
The operator requires both arguments have the same type, and is
returns either the first or second value depending on the selector
value. The operator is also named “forget cases”. The most well
understood one is:

x: R+R -> R

I.e. given a blue number or a green number, just return me the blue
number with plain colour.

So, generalising the diagonal and codiagonal to n>2 instead of
n=2 for pairs, we use the generalised projection, and we can
recover the more specialised projections (AND also the same
thing for sums).

In fact Felix does not yet provide the isomorphism

N * T = T + T + T + T .. + T

which it should, its the dual of the rule

T ^ N = T * T * T * T … * T

This is partly because that would force a new physical representation
of sum types:

struct { int tag; union { S1; S2; S3 … Sn; }}

This is always what Felix SHOULD have used: expanded types, NOT
tagged pointers. The problem was C++89 could not do this.

But C++11 can.

[john skaller]

> On 12 Dec 2015, at 04:06, Garrett Bluma <garret...@gmail.com> wrote:
>
> On Fri, Dec 11, 2015 at 7:43 AM, john skaller <ska...@users.sourceforge.net> wrote:
> I need some help with notation!

> r # a @ 0
>
> If I understand it right,
>
> # means 'with-only' or 'prune-all-except' and returns a tuple
> @ means ‘take the nth element' or standard projection.

Those operators are not actually available, I just picked
them for demonstration.

However @ is not really the standard projection. Technically the
idea is that

#a selects a sequence of fields (NOT an actual tuple)
#5 selects the fifth one of the sequence

and

r.5 means r# _ . 5

where the field name _ is used to mean “whitespace”. In other words,
a tuple IS a record. Its just a record with all the field names blank.

There is no mathematical problem with this I can see, in the Felix compiler
there is an issue with ** and ,, tuple form, but that actually agrees
well with the record (a=1 | T) form: both are inductive, i.e. lists
formed by “pushing” a new value onto the front.

In fact If I can add a “red herring” compact linear types could be defined
that way too.

So the proposal is that inside the compiler, I merge tuple, record, and array
representations logically. There will still be physical terms for these
things separately.

> 1.) We already have a projection function (the dot operator and a number) and we should think twice about adding a second one that does the same thing.

Actually that’s parser sugar. There is a REAL projection function too.

//$ Tuple projection function.
x[scase_literal_pri] := "proj" sinteger "of" x[ssum_pri] =># "`(ast_projection ,_2 ,_4)";

For example:

proj 2 of int * long * double

This is the syntax for the actual projection.

There is actually no syntax for a record projection. I should add that :)

Remember operator . is just reverse application. So

x.1

REALLY and TRULY means

1 x

Obviously 1 is not a projection, its an integer, but when used like
the above the term

apply (1, x)

is translated to

apply( proj (1,typeof x), x) )

>
> Yet the second one is the standard for projection for tuples. Also, how is
>
> r # @ 0
>
> intended to be different from this?
>
> r.0

It’s not. It’s intended to be “the definition” of r.0.

> In my mind, they are functionally similar. In the #@ version, we are applying an operation to remove labels and then access an element by position. What if the projection on a named record could do this conversion automatically?

It does. Thats the whole point. It does this ALREADY. The problem is if we
allow a record with empty labels

(=1, =2)

and make

(1,2)

syntactic sugar for that, then we can only get the FIRST element of the record.

> I do understand that there's some difficulty here. Namely, how do we differentiate between names and variables?

That’s not a problem. Felix already has to do that.

>
> If we want to get the nth element of a tuple, we could do this:
>
> var n = 0;
> println$ r.n;

Not unless r is n array.

>
> but if we want to get the 'fname' field of a record, we do this:
>
> println$ r.fname;
>
> So how do we decide if ‘fname' is a variable (for projection) or it's own projection function?

Based on the type of the argument.

>
> 2.) The # symbol is part of a group of operations that should be similar in appearance. I’m suggesting 'withonly' as a substitution.

The use of words helps with this because one tends to ensure the words
somehow mean what they say :)

[Ryan Gonzalez]

What about "where"? Kind of (but not really) like K?

> r with (metadata=(likes_ice_cream=True))
> r without metadata
> r withonly email_address // r # email_address in your notation
>
>The # is just a little jarring. If we wanted to go with symbolic
>notation,
>I'd argue for something more arithmetic. Extension is like addition,
>exclusion is like subtraction, and isolation to a single name (or set
>of
>names) is like modulation.
>
> r + (metadata=(likes_ice_cream=True)) // "+" equivalent to "with"
> r - metadata // "-" equivalent to "without"
> r % email_address // "%" equivalent to "withonly"
>
>On a different train of thought, we could include exponentials in the
>selector expressions, this could also provide the means of taking some
>number of elements from a list.
>
> r without a^3 // eliminate 3 a's from r
> r withonly a^3 // select only three a's from r
>
>Or arithmetically,
>
> r - a^3
> r % a^3
>
>--
>Garrett

--
Sent from my Nexus 5 with K-9 Mail. Please excuse my brevity.

[Garrett Bluma]

On Sat, Dec 12, 2015 at 2:08 AM, john skaller <ska...@users.sourceforge.net> wrote:

However @ is not really the standard projection. Technically the
idea is that

        #a selects a sequence of fields (NOT an actual tuple)
        #5 selects the fifth one of the sequence

and

        r.5 means r# _ . 5

Thinking about this more, it seems like I was focused on projection over blank-named elements only. Which, if we ignore that there could be elements with actual names then it should work to treat them as tuples directly. That is, if we have a special case of the data, then we can get away with a single projection (by index). But, of course, it should be obvious that this won't work for richer data. Entries in the record can have names, so a more complex projection is necessary.

In fact, it seems fair to say that these scoped-set records appear to act like two-dimensional objects. One axis is names, the other is index. So in order to get at a single element we would provide two coordinates--the name and the index--and likewise we need two kinds of projection functions to probe deeper. 

So, with that being the case, I withdraw my suggestion that we treat records as unidimensional objects--where the user can access rows and indexes willy-nilly and let the compiler figure it out which we mean. This is not just prone to failure, but could never work well.

So I'm back on board with the original proposal for now.

    r # name @ index

seems like a fair syntax. Here's a different one that (I admit) is less good, but which could elicit some ideas.

    r.(name,index)

In my mind this seems intuitive because it's a projection in two dimensions. Much like accessing a two dimensional array. The downside is that it's not an array. Though, we could consider this too.

    r.name.index

or expanded

    var tmp = apply( proj (name,typeof r), r) );

    var out  = apply( proj (index,typeof tmp), tmp) );

r is a record, "name" would capture the row from the record, and "index" would choose the nth element from the row. Perhaps we could do this already if we add the record projection. I'm not sure. The unfortunate thing is if we just do 

    r.name

we have a tuple, instead of (naively) the first entry of the tuple of that row.

--

Garrett

[john skaller]

> On 13 Dec 2015, at 04:59, Garrett Bluma <garret...@gmail.com> wrote:
>
> On Sat, Dec 12, 2015 at 2:08 AM, john skaller <ska...@users.sourceforge.net> wrote:
>
> However @ is not really the standard projection. Technically the
> idea is that
>
> #a selects a sequence of fields (NOT an actual tuple)
> #5 selects the fifth one of the sequence
>
> and
>
> r.5 means r# _ . 5
>
>
> Thinking about this more, it seems like I was focused on projection over blank-named elements only. Which, if we ignore that there could be elements with actual names then it should work to treat them as tuples directly.

You’re missing the point. We can’t treat “the sequence of fields with the same name”
as a tuple. Because I’m trying to define a tuple as a RECORD which HAPPENS to
have all blank names. In other words, it’s a special case of a record. Which
means there are NO tuple operators: there is no index operator for tuples
because tuples no longer exist.

What I’m trying to do is define “scoped record operators” as axiomatic
and then *define* the usual tuple and record operators ON RECORDS
using them. For example:

(a=1,a=2,b-1) . 1 ==> ERROR, no field name “”
(a=1).b ==> ERROR, no field name “b”
(a=1,a=2).a ==> OK, field name a has at least one occurence

This is all because the definition of a field projection by name is the
first found field or error, and the projection by index is the n’th
field named “”.

There are no tuples. There are no records with unique fields.
There is only ONE type: a scoped record (record with duplicate fields).

[Garrett Bluma]

On Sat, Dec 12, 2015 at 1:23 PM, john skaller <ska...@users.sourceforge.net> wrote:

> On 13 Dec 2015, at 04:59, Garrett Bluma <garret...@gmail.com> wrote:
>
> Thinking about this more, it seems like I was focused on projection over blank-named elements only. Which, if we ignore that there could be elements with actual names then it should work to treat them as tuples directly.

You’re missing the point. We can’t treat “the sequence of fields with the same name”
as a tuple. Because I’m trying to define a tuple as a RECORD which HAPPENS to
have all blank names. In other words, it’s a special case of a record. Which
means there are NO tuple operators: there is no index operator for tuples
because tuples no longer exist.

Haha.. Whoops. At that point, I was referring to bogus circumstances, but it turns out that even my revision was wrong for similar reasons. I just can't get over the idea that tuples and records are the same thing! :) 

 

What I’m trying to do is define “scoped record operators” as axiomatic
and then *define* the usual tuple and record operators ON RECORDS
using them. For example:

        (a=1,a=2,b-1) . 1 ==> ERROR, no field name “”
        (a=1).b ==> ERROR, no field name “b”

        (a=1,a=2).a ==> OK, field name a has at least one occurrence

This is all because the definition of a field projection by name is the
first found field or error, and the projection by index is the n’th
field named “”.

There are no tuples. There are no records with unique fields.
There is only ONE type: a scoped record (record with duplicate fields).

This clarifies things. Thanks! It even seems pretty simple.

I guess I just got caught up in the extension and isolation of scoped records. Seemed like we were going to add some bizarre syntax for a corner case. :) But that doesn't seem to be the case anymore.

--
Garrett

 

[john skaller]

> There are no tuples. There are no records with unique fields.
> There is only ONE type: a scoped record (record with duplicate fields).
>
> This clarifies things. Thanks! It even seems pretty simple.
>
> I guess I just got caught up in the extension and isolation of scoped records. Seemed like we were going to add some bizarre syntax for a corner case. :) But that doesn't seem to be the case anymore.

It’s an idea only, but unification of things always seems good
at least to consider.

The issue is at least partly notation.

[Garrett Bluma]

>
> On Dec 13, 2015, at 4:31 AM, john skaller <ska...@users.sourceforge.net> wrote:
>
>
>> There are no tuples. There are no records with unique fields.
>> There is only ONE type: a scoped record (record with duplicate fields).
>>
>> This clarifies things. Thanks! It even seems pretty simple.
>>
>> I guess I just got caught up in the extension and isolation of scoped records. Seemed like we were going to add some bizarre syntax for a corner case. :) But that doesn't seem to be the case anymore.
>
> It’s an idea only, but unification of things always seems good
> at least to consider.
>
> The issue is at least partly notation.
>

Agreed. I'm just saying I thought it was more bizarre than it is.

--
Garrett

[Sod Almighty]

On Friday, 11 December 2015 13:44:00 UTC, skaller wrote:

I need some help with notation!
And perhaps theory. Here is the idea.

Felix has records with scoped labels. This means you can have duplicate labels:

        var r = (a=1, a=2, b=3, a=4);

Currently,

        r.a

returns 1, that is, the projection a returns the first a it finds.
You can get the second a like this:

        (r without a).a

[Thanks to Ryan for the without keyword]

However this is clearly messy!

Agreed.

 

A more general notation would be like:

        r # a @ 0

where the a projection fetches ALL the a’s, and then the numerical index fetches the n’th one. This notation conflicts with the existing notation (which is the main problem I suspect).

But now here is another record:

        (=1, =2, =3)

you see I left out the field label.  We could just write that like this:

        (1,2,3)

i.e. it is nothing more than a tuple! So using the above notation:

        r # @ 0

would be 1, that is, we leave out the field name. We can view

        #@

as tuple access. So the theoretical view is of two operators, a field projection returning a tuple of all the values of a given field and a tuple projection selecting one of them. The currect field projection is composed of the new field selector followed by a projection getting the first value. The current tuple projection becomes instead a field selector for the empty field followed by the new tuple projection.

I understood all of the above. Sounds good.

I understood none of the subsequent.

[Sod Almighty]

On Friday, 11 December 2015 17:06:14 UTC, Garrett Bluma wrote:

1.) We already have a projection function (the dot operator and a number) and we should think twice about adding a second one that does the same thing. 

    my_record # a @ 0

is equivalent to

    (my_record # a).0

Anything that reduces the number of redundant goddamn parentheses is fine by me!

To my way of thinking, parens should only be used to force precedence in mathematical expressions, and to enclose function arguments. Having to wrap code in parens to force precedence is just ugly.

 

Yet the second one is the standard for projection for tuples. Also, how is

    r # @ 0

intended to be different from this?

    r.0

In my mind, they are functionally similar. In the #@ version, we are applying an operation to remove labels and then access an element by position. What if the projection on a named record could do this conversion automatically? That would simplify the language instead of encumbering it. The naive approach of just trying to get the 2nd element of a record could "just work".

I think it's a mistake to conflate records with tuples. A record without labels is a tuple, and should be accessed using dot notation, or possibly @ notation.

A record with labels is not a tuple, and should require # notation.

Furthermore, why the hell does a record permit duplicate labels in the first place?

2.) The # symbol is part of a group of operations that should be similar in appearance. I'm suggesting 'withonly' as a substitution.

    r with (metadata=(likes_ice_cream=True))

    r without metadata

    r withonly email_address   // r # email_address in your notation

The # is just a little jarring. If we wanted to go with symbolic notation, I'd argue for something more arithmetic. Extension is like addition, exclusion is like subtraction, and isolation to a single name (or set of names) is like modulation.

    r + (metadata=(likes_ice_cream=True))   // "+" equivalent to "with"

    r - metadata                   // "-" equivalent to "without"

    r % email_address         // "%" equivalent to "withonly"

You may have a point there.

[Sod Almighty]

On Friday, 11 December 2015 23:16:04 UTC, skaller wrote:

given a blue number or a green number, just return me the blue
number with plain colour.

So, generalising the diagonal and codiagonal to n>2 instead of
n=2 for pairs, we use the generalised projection, and we can
recover the more specialised projections

See, now this is a perfect example of why I still haven't written anything in Felix: I understand pretty much nothing that you say. You might as well be speaking Portuguese! :(

[Ryan Gonzalez]

On January 22, 2016 7:17:07 PM CST, Sod Almighty <sod.al...@gmail.com> wrote:
>
>
>On Friday, 11 December 2015 23:16:04 UTC, skaller wrote:
>>
>>
>> given a blue number or a green number, just return me the blue
>> number with plain colour.
>>
>> So, generalising the diagonal and codiagonal to n>2 instead of
>> n=2 for pairs, we use the generalised projection, and we can
>> recover the more specialised projections
>>
>
>See, now this is a perfect example of why I still haven't written
>anything

>in Felix: I understand pretty much *nothing* that you say. You might as

>
>well be speaking Portuguese! :(

Neither do I, but I do understand Felix. Sort of. ;)

[srean]

Google translate doesn't handle John speak yet :)

I would be the first to be a paying member.

At least I have nagged John enough about the book.

--
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 post to this group, send email to felix-l...@googlegroups.com.
Visit this group at https://groups.google.com/group/felix-language.
For more options, visit https://groups.google.com/d/optout.

[srean]

Furthermore, why the hell does a record permit duplicate labels in the first place ?

Very good question, would love to know. Would probably take years for me to understand. But I do eventually get there.

 

[john skaller]

> On 24 Jan 2016, at 01:14, srean <srean...@gmail.com> wrote:
>
> Furthermore, why the hell does a record permit duplicate labels in the first place ?
>
> Very good question, would love to know. Would probably take years for me to understand. But I do eventually get there.

Same reason a list of pairs does: its simpler **

Basically, row polymorphism:

(a=1, b=2 | R)

where R is some arbitrary record to which fields a and be are added by
pushing them on the front, is hard to restrict the R to not contain a and b
labels. Furthermore the restriction gets in the way.

Read Meijer’s paper.

** by simpler I mean Felix could not implement anything else.
The standard unification algorithm cannot handle row polymorphism
unless you use scoped labels: you have to add constraints, so the
type variables involved are no longer free, but carry around constraints.

[srean]

I have postponed understanding what row-polymorphism is about for now.
May be someday.

[john skaller]

> On 24 Jan 2016, at 04:48, srean <srean...@gmail.com> wrote:
>
> I have postponed understanding what row-polymorphism is about for now.
> May be someday.

Simple enough:

fun f[R] (x: (a:int | R) ) => (b=2 | x);

This function matches any record with a field named “a” of type int.
It returns the same record with field b=2 added.

Unlike subtyping the “unspecified fields” are not lost,
even though you don’t know what they are.

In the literature R above is a row. Which is just a list of field/type pairs.
In Felix R is actually a record type not a row.

[Sod Almighty]

On Sunday, 24 January 2016 04:51:26 UTC, skaller wrote:

> On 24 Jan 2016, at 04:48, srean <srean...@gmail.com> wrote:
>
> I have postponed understanding what row-polymorphism is about for now.
> May be someday.

Simple enough:

fun f[R] (x: (a:int | R) ) => (b=2 | x);

This function matches any record with a field named “a” of type int. It returns the same record with field b=2 added.
Unlike subtyping the “unspecified fields” are not lost, even though you don’t know what they are.
In the literature R above is a row. Which is just a list of field/type pairs. In Felix R is actually a record type not a row.

Somewhere in this world, there will exist people who understand what you just said. I'm not one of them, however.

[john skaller]

> > I have postponed understanding what row-polymorphism is about for now.
> > May be someday.
>
> Simple enough:
>
> fun f[R] (x: (a:int | R) ) => (b=2 | x);
>
> This function matches any record with a field named “a” of type int. It returns the same record with field b=2 added.
> Unlike subtyping the “unspecified fields” are not lost, even though you don’t know what they are.
> In the literature R above is a row. Which is just a list of field/type pairs. In Felix R is actually a record type not a row.
>
> Somewhere in this world, there will exist people who understand what you just said. I'm not one of them, however.

Its simple. If you have a class A with method X and a derived class B with method Y also,
then if you pass a B to a function expecting an A, you lose the Y method.

That’s subtyping.

With row polymorphism you don’t lose the Y method. You can’t use it.
But you can pass the whole object out of the function.

I stated that for objects, but the more general form is for records.
A record is basically a tuple with named fields.

Here is an example:

/////////
fun f[R] (x: (a:int, b:int | R)) => x.a, x;

var myrec = (a=1, b=2, c=3);
var x,r = f myrec;

println$ x,_strr r;
////////

~/felix>flx te
(1, (a=1,b=2,c=3))

What you see is that you pass in the record with a,b,c labels
to a function that accepts any record with a and b labels
which are ints, and returns the value of the a label
and the original record.

If you use subtyping, instead:

fun f (x: (a:int, b:int) => x.a;
… f (myrec :>> (a:int,b:int)) ..

you lose the extra fields. In the above, :>> is a coercion or cast
which throws out the “c” field.

Felix does not allow an argument to be a subtype of a parameter type
so we have to manually coerce it.

Note: a subtype of a record type is any type with “at least” all
the fields of the record type, that is, subtypes have “more” fields.
Our argument above “myrec” is a subtype, but we have to coerce
it to the supertype of the parameter to actually call the function.
Clearly this causes the “c” field to be lost.

This is quite general, not just in Felix. Upcasts throw away
information. In OO an “upcast” goes from a concrete type
to a more abstract supertype (clearly throwing away detail).

Row polymorphism merely hides the detail without throwing it away.

note again: although this is defined for records, objects with methods
are just records with some “fields” being the methods. So most theoreticians
ignore OO completely because records subsume them. In Felix the
dynamic (java like) objects are LITERALLY just records.

[srean]

Ah I see. Thanks for the explanation.

[Sod Almighty]

On Sunday, 24 January 2016 16:50:44 UTC, skaller wrote:

Its simple. If you have a class A with method X and a derived class B with method Y also,
then if you pass a B to a function expecting an A, you lose the Y method.

That’s subtyping.

With row polymorphism you don’t lose the Y method. You can’t use it.
But you can pass the whole object out of the function.

Isn't this the same as slicing?

Slicing only happens with value objects anyway, not pointers or references.

Besides, what use have we for the Y method, given that the value returned by the function is, by necessity, of type A? We can never call Y, so it might as well not be there.

[john skaller]

>
> With row polymorphism you don’t lose the Y method. You can’t use it.
> But you can pass the whole object out of the function.
>
> Isn’t this the same as slicing?

No.

>
> Slicing only happens with value objects anyway, not pointers or references.

True, but nevertheless the information is lost. Virtual dispatch continues
to work with the pointer but additional methods can’t be recovered.

> Besides, what use have we for the Y method, given that the value returned by the function is, by necessity, of type A? We can never call Y, so it might as well not be there.

That’s not true .. its lost inside the function. Bot the function can
return the whole object with it’s original static type.

This may not be surprising for someone used to dynamic typing
where there’s no problem with losing static type information
because there isn’t any in the first place.

[Sod Almighty]

On 26 Jan 2016, at 9:09 am, john skaller <ska...@users.sourceforge.net> wrote:

>> Besides, what use have we for the Y method, given that the value returned by the function is, by necessity, of type A? We can never call Y, so it might as well not be there.
>
> That’s not true .. its lost inside the function. Bot the function can return the whole object with it’s original static type.

But the function declares its return type. How can it return a different type?

[john skaller]

fun[R] f (r: (x:int | R) ) => x,r;

The return type isn’t declared but it is

int * (x:int | R)

where R is the record type of the argument minus the x:int field.
So it returns the x field and the original record. So

f (x=1, y=2) == 1, (x=1, y=2)
f(x=1, y=2, z=“Hello”) == 1, (x=1, y=2,z=“Hello”)

Any record with an x field or type int matches.
However whilst the function is accepting any subtype of record (x:int)
it is not using a supertype coercion to extract the x. It’s splitting
the record into the x field and “all the rest” denoted by type variable R.

Of course this is trivial to do in a dynamic language, however note
we are passing by VALUE here not reference.

So roughly: subtyping uses slicing, row polymorphism uses
splitting instead.

Note that inside the function the fields denoted by R are not
known. But the caller of the functions knows what they are.
So the caller knows the complete type of the result, even
though the function itself does not.

When you do subtyping with pointer you ALSO get slicing.
The only difference is that virtual functions don’t lose their
overridden meaning. But this is immediately obvious if
you consider that a virtual function is just a function pointer.
In fact in say C++ its the same function for every object
of a class so they use a virtual table an an optimisation,
that only requires ONE pointer in the object instead of
one per function. But semantically you can see that
because its just an optimisation, actually yes, you lose
the the extra methods by slicing. And once lost they
can’t be recovered.

Row polymorphism retains the whole record. It does not
know the other fields but it doesn’t lose them.

I will show some use for this in the next email.

[john skaller]

[BTW: the weird character crap is my stupid F’ing email client
replacing the “ with “nice looking quotes’ .. stupid moronic crap]

Ok so consider:

/////////////////////////

// Define an employee object constructor
object employee (name:string, boss:string) = {
method fun get_name () => name;
method fun get_boss () => boss;
}

// sample employee
var jms = employee ("john", "none");
println$ jms.get_name () + " is employed by " + jms.get_boss ();

// function using row polymorphism to replace the boss
fun new_boss[R] (
e: (get_boss:unit -> string | R),
boss: string
) =>
let fun newboss () => boss in
(get_boss = newboss | (e without get_boss))
;

// the boss is replaced
var jms2 = new_boss (jms, "sod");
println$ jms2.get_name () + " is employed by " + jms2.get_boss ();

// Define a company object constructor
object contractor (company: string, boss: string) = {
method fun get_company() => company;
method fun get_boss () => boss;
}

// make a sample company
var acme = contractor ("Acme P/L", "joe");
println$ acme.get_company () + " has boss " + jms.get_boss ();


// the boss is replaced
var acme2 = new_boss (acme, "sod");
println$ acme2.get_company () + " has boss " + jms2.get_boss ();
/////////////////////////////////

Note all this code you see (except the diagnostic prints) is PURELY FUNCTIONAL.
There is nothing mutated anywhere.

The function to replace the boss works but we really need a functional
update syntex

( e with get_boss = new+boss)

instead of having to first remove the get_boss field then
add the new one (but the semantics would be the same).

The point is that the new_boss function works for BOTH an
employee and company. In fact it works for ANY object
with a “get_boss” function.

Just remember a Felix “dynamic object” is nothing more than
a record of function closures returned by the constructor function.
So row polymorphism works REALLY well with these objects.

The “new_boss” function doesn’t know what “the other” fields are,
other than “get_boss” field, but they’re not lost, as you can see:
the client gets the same record type back as they put in,
whatever that is.

So you will also note that despite the strong static typing this
system is extremely dynamic. In fact its probably MORE
dynamic than Ruby .. :-)

[Sod Almighty]

On Tuesday, 26 January 2016 16:18:49 UTC, skaller wrote:

> But the function declares its return type. How can it return a different type?

        fun[R] f  (r: (x:int | R) ) => x,r;

Isn't this a function which can take an integer or an R? It doesn't look exactly like that, but I'm having trouble parsing the declaration. It looks a little like a destructuring assignment.

 

The return type isn’t declared but it is

        int * (x:int | R)

where R is the record type of the argument minus the x:int field.

Nope, that makes no sense to me whatsoever. This syntax is alien to me.

 

It’s splitting the record into the x field and “all the rest” denoted by type variable R.

I think I see. But I don't understand the syntax.

 

So roughly: subtyping uses slicing, row polymorphism uses splitting instead.

Sounds interesting. If I understood it, it might be useful ;)

[john skaller]

> On 27 Jan 2016, at 06:05, Sod Almighty <sod.al...@gmail.com> wrote:
>
>
> On Tuesday, 26 January 2016 16:18:49 UTC, skaller wrote:
>
> > But the function declares its return type. How can it return a different type?
>
> fun[R] f (r: (x:int | R) ) => x,r;
>
> Isn’t this a function which can take an integer or an R?

No, the notation is taken from the academic literature, the “|” doesn’t
mean “or”.

[Sod Almighty]

On Tuesday, 26 January 2016 22:11:20 UTC, skaller wrote:

> On 27 Jan 2016, at 06:05, Sod Almighty <sod.al...@gmail.com> wrote:
>
> Isn’t this a function which can take an integer or an R?

No, the notation is taken from the academic literature, the “|” doesn’t
mean “or”.

Then - and bear in mind you're talking to someone who isn't a mathematician - what does it mean?

I had a very basic introduction to set theory and logic when I was at university, but I never fully understood it.

[john skaller]

>
> No, the notation is taken from the academic literature, the “|” doesn’t
> mean “or”.
>
> Then - and bear in mind you’re talking to someone who isn't a mathematician - what does it mean?

It doesn’t mean anything. Its a puncturation mark. The format for a row polymorphic record type
is given by the syntax

( field=value, field=value, … | TYPEVARIABLE )

and that’s the end of it. The “|” is part of the whole multisymbol syntactic
form.

[Brandon Barker]

I know this is an old thread. But I can't help myself. I programmed in Scala for about three years, a bit less than half time, before beginning to wish that records (really, Scala case classes) and tuples were the same. Sometimes you want to treat data as a tuple, sometimes as a record.

[John Skaller2]

> On 22 Nov 2018, at 02:37, Brandon Barker <brandon...@gmail.com> wrote:
>
> I know this is an old thread. But I can't help myself. I programmed in Scala for about three years, a bit less than half time, before beginning to wish that records (really, Scala case classes) and tuples were the same. Sometimes you want to treat data as a tuple, sometimes as a record.

In Felix they are the same type. However probably not quite what you were thinking of.

If a record has all blank field names .. its a tuple.
Also if a tuple has all the same type components, its an array.

Records can also have duplicate fields:

(a=1,a=2).a == 1

Functions which are written like:

fun f(x:int,y:double)

accept BOTH tuples:

f (1,2.1)

and records:

f (x=1,y=2.1)

Field names can be used to disabiguate function calls.
The order doesn’t matter if you use names, except for duplicates.

You can also have default arguments. You have to use records for
that to work.

An extension of records called “polyrecords” provides row polymorphism.

Unfortunately I can’t think of a syntax for getting all the field with a particular
name out of a record (as a tuple).


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

[Brandon Barker]

On Wed, Nov 21, 2018 at 11:53 AM John Skaller2 <ska...@internode.on.net> wrote:

> On 22 Nov 2018, at 02:37, Brandon Barker <brandon...@gmail.com> wrote:
>
> I know this is an old thread. But I can't help myself. I programmed in Scala for about three years, a bit less than half time, before beginning to wish that records (really, Scala case classes) and tuples were the same. Sometimes you want to treat data as a tuple, sometimes as a record.

In Felix they are the same type. However probably not quite what you were thinking of.

I started reading about these because duplicated field names seemed like an odd thing to me, but it made sense after digging around. And actually, other than that, seems to be pretty much what I'd expect, on paper at least. 

If a record has all blank field names .. its a tuple.
Also if a tuple has all the same type components, its an array.

Records can also have duplicate fields:

        (a=1,a=2).a == 1

Functions which are written like:

        fun f(x:int,y:double)

accept BOTH tuples:

        f (1,2.1)

and records:

        f (x=1,y=2.1)

Field names can be used to disabiguate function calls.
The order doesn’t matter if you use names, except for duplicates.

You can also have default arguments. You have to use records for
that to work.

Interesting, it is always annoying to have to cast between tuples and an arguments in some languages, and I see that Felix goes a step farther with getting named arguments as an immediate result of having tuples and records being the same - pretty cool!

 

An extension of records called “polyrecords” provides row polymorphism.

Unfortunately I can’t think of a syntax for getting all the field with a particular
name out of a record (as a tuple).

What was the primary issue with the original proposal (r # a earlier in this thread) ? - or have things progressed beyond it:

        r.a —> r # a @ 0  // define record projection 

        r.1 —> r # _ @ 1 // define tuple projection 

 

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

--
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 post to this group, send email to felix-l...@googlegroups.com.
Visit this group at https://groups.google.com/group/felix-language.
For more options, visit https://groups.google.com/d/optout.

--

Brandon Barker
brandon...@gmail.com

[John Skaller2]

>
> I started reading about these because duplicated field names seemed like an odd thing to me, but it made sense after digging around. And actually, other than that, seems to be pretty much what I’d expect, on paper at least.

Based on

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/scopedlabels.pdf

In Felix, row polymorphism doesn’t use a separate kind of row variable:

var x = (b=1,c=“hello”);
var y = (a=1 | x);

Here y is a polyrecord form, so x is an actual record, not a row.
WIth polymorphism (the syntax needs some work … :-)

fun g[T] (point: (x:int, y:int | T)) =>
(point with x=point.x+1, y=point.y+1)
;
fun f[T] (point: (x:int, y:int | T)) =>
(x=point.x+1, y=point.y+1 | (point without x y))
;

println$ (f (x=1,y=1, colour="red"))._strr;
println$ (g (x=1,y=1, colour="red"))._strr;

~/felix>flx rp
(colour='red',x=2,y=2)
(colour=‘red',x=2,y=2)

I would like this syntax but haven’t gotten around to implementing it:

fun g[T] (point: (x:int, y:int | r:T)) =>

i.e. naming the extension part.

Note if you just put

(x=point.x+1, y=point.y+1 | point)

you get two x and two y fields. However the projections x and y only see
the leftmost (most recent) ones. What I would also like is:

point @ x

returns (2,1) and then you can do

point @ x . 1

returns 1. You can do

(a=1, 42, 66) . 1

which is 66. In other words if you use an integer it assumes
the “blank field”.




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

[John Skaller2]

>
> What was the primary issue with the original proposal (r # a earlier in this thread) ? - or have things progressed beyond it:
>
> r.a —> r # a @ 0 // define record projection
> r.1 —> r # _ @ 1 // define tuple projection

It’s purely an issue of “available ascii characters”.
We have a limited supply of ascii art operators.

We have this already:

#constant —> constant ()

which is a special form of function application. So if you see

a # b

is that

a (#b)

or

(a) # (b)


You can always try an experiment. The grammar is in

src/packages/grammar.fdoc

or you can play with

build/release/share/lib/grammar/*.fsyn

which is a bit safer (generated, not in repo). If you change the grammar,
you don’t need to rebuild anything. “flx” detects it and reparses everything
automatically. So you can do a change and run make test to check you haven’t
broken a regresion test.

@T

is the type of a possibly null pointer. So @ was used too.
However, the grammar for types is now split from expressions so it may be
available.

[HMM .. on checking @x is in the grammar but probably shouldn’t be!]

Still there’s a concern, felix already has a LOT of weird syntax the average
programmer won’t grok. There’s a point where its better to use magical
names instead of ascii art symbols. Its easy to get distracted and leave features
incomplete :-)


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

[John Skaller2]

Stuff you may want to try:

(a) examine src/test/regress/rt/*

You’ll find files, regression tests, like:

@title test stuff
@h1 heading
Blah
@felix
code
@
@expect
result
@


(b) add interesting tests

The more tests the better!

=======================

run the webserver:

flx_web &

Now run your browser on localhost:1234

It should work and show you a tutorial option.

If you click through that and compare with

src/web/tut/*

you will see, the webserver dynamically formats Felix.
Does C++ too. Ocaml. And Python.

This was the real documentation: 100% literate programmed.
Unfortunately we don’t have a server to run it online.

Try

http://localhost:1235/share/src/packages/stdlib_toc.fdoc

and click on some links.

This isn’t documentation! This is the actual library code!

Notice Felix AND C++ includes are hyperlinked.
Try holding mouse over keywords .. you get a short mouseover description.
You can also expand and collapse sections.


We were using Rackspace, but the lowest cost option was still way too expensive.
We need an actual machine (or virtual machine), preferably running Linux.
Normal usage: minimal. The webserver is efficient, it doesn’t use much memory.
Disk use: minimal. HOWEVER the machine sometimes has to build Felix
and that requires around 2G due to the cost of running C++ compilers.

The reason this machinery is better is that the tutorial code is REAL CODE.
It gets run when you build Felix and the correctness of the examples verified.
And because the web server is written in Felix and is part of the system ..
it can do anything. There is even “almost working” ability to run Felix
through a browser. (You can actually run shell scripts right now).

You can use the web server to view any file on your machine. Use $ as the
Unix root directory.


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