Implementing "Elements of Programming" in Actor Script

In an effort to understand how ActorScript is to program with, and because I think Stepanov's "Elements of Programming" represents the best 'core' for any generic programming library, I want to try and translate the Elements into ActorScript. As there is no environment for actually testing code I thought I would post it here for comments from those who can tell if its correct or not. The idea is each top-level post should be a block of Elements code in ActorScript for comments. I will revise the top-level code according to the corrections and suggestions in the comments. I don't plan on using Unicode, but I will try and get the ASCII representations correct too.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

0.1 Mutable References in Actor Script

The first thing needed to implement a lot of the generic algorithms is an interface for mutable references, and a single mutable reference:

------------------------------------------------------------------------------
-- 0.1 Mutable References

Interface Readable<|t|> with
    [||] |-> t

Interface Writable<|t|> with
    [|:= x:t|] |-> Writable<|t|>

Interface Mutable<|t|> extends Readable<|t|> with
    [|:= x:t|] |-> Mutable<|t|>

Actor MutableRef<|t|>[value:t]
    current := x
    implements Mutable<|t|> using
        [||]:t -> current
        [|:= x:t|]:MutableRef<|t|> -> [:]MutableRef<|t|>
            afterward current := x


Mutable interface

The following is an interface for Mutable

Interface Mutable◅aType▻ with
  ⟦ ⟧ ↦ aType 
  ⟦≔ _:aType⟧ ↦ Mutable◅aType▻

Interface Readable◅aType▻ restricts Mutable◅aType▻ with ⟦ ⟧ ↦ aType

Interface Writeable◅aType▻ restricts Mutable◅aType▻ with ⟦≔ _:aType⟧ ↦ Writeable◅aType▻

The following is an implementation of Mutable:

Actor SimpleMutable◅aType▻[x:aType]
 current ≔ x  
 implements Mutable◅aType▻ using
    ⟦ ⟧ ↦ current,
    ⟦≔ y:aType⟧ →
       ⍠Mutable◅aType▻      //return this Actor as Mutable◅aType▻
         afterward current ≔ y

Edit Corrected bugs in definitions of Readable, Writeable, Mutable, and SimpleMutable

Writeable / Mutable

Something that is writeable may not be readable, so Writeable should return a Writeable not a Mutable. I think Mutable needs to be defined separately to make this work. I have corrected the rest.

Functional or Imperative

ActorScript distinguishes between a value and a function at the call-site, this makes it like an imperative language, yet the definitions of procedures seems functional, they evaluate to as value, but special keywords like afterward are provided.

What is the reason to not use traditional imperative constructs like ';' to separate commands, and 'return' for the result. From a functional viewpoint its a monad with ';' being bind and 'return'. We could then define:

Actor MutableRef<|t|>[value:t]
    current := value
    extends Mutable<|t|> using
        [|x|]:t ->
            return current
        [|y = x:t|]:MutableRef<|t|> ->
            current := x;
            return [:]MutableRef<|t|>

re Functional or Imperative

Functional or Imperative

Neither. Actor model.

What are the basic capabilities of an Actor?

Sending and receiving messages?

I would say sending and receiving messages. However sending a message, waiting for a response, where that response might be a simple 'done it' (Void?) before sending the next message is such a common pattern it would seem worth supporting with syntax?

A question: How does assignment (current := x) fit into the actor model? Is a variable an actor, that responds to [||] and [|:=x:t|] messages?

";" is too small a token to indicate  ("afterward")

";" is too small a token to indicate  ("afterward")

Sequential State Update

How would I actually implement this PRNG?

Actor XorShiftPlus[x : Unsigned_64, y : Unsigned_64] 
    s0 := x
    s1 := y
    implements PRNG<|Unsigned_64|> using
        next[size:Unsigned_32]:Unsigned_64 ->
            t1 := s0
            t0 := s1 
            t1 := xor[t1, shift_left[t1, 23]]
            s0 := t0
            t1 := xor[t1, xor[t0, xor[shift_right[t1, 17], shift_right[t0, 26]]]]
            s1 := t1
            Unsigned_32[shift_right[((t1 + t0) and 0xffffffff) * Unsigned_64[size], 32]]  

Note: the state update should happen before the calculation of the return value.

Maximizing referential transparancy

How about the following:

Actor XorShiftPlus[x:Unsigned_64, y:Unsigned_64] 
    s0 := x
    s1 := y。
    implements PRNG using
        next[size:Unsigned_32]:Unsigned_64 →
         Let t1 ← s0
             t0 ← s1, 
             t2 ← xor.[t1, shift_left.[t1, 23]],
             t3 ← xor.[t1, 
                       xor.[t0, 
                            xor.[shift_right.[t1, 17],
                                 shift_right.[t0, 26]]]]。
           Unsigned_32[shift_right.[((t2 + t0) and 0xffffffff) * Unsigned_64[size],
                                    32]]。
             afterward
                 s0 := t0,
                 s1 := t3。

Xor, Shift and Sizes

That's not too bad, again its probably just a matter of getting used to the syntax. There are a couple of bugs in your version, using the wrong 't' variable.

Are you happy with sized unsigned integers being Unsigned_32, Unsigned_64 etc, and that xor, and shift operation are procedures? What about the representation of Hex literals and the casting?

Do you only need the "end" symbol () if there are more than line, as it wasn't used in the MutableRef actor?

Does it need commas in the "afterward" statements?, or an "end" () symbol?

The other bit that is missing is the specialisation. Given the interface:

Interface Integer<|t|> with
    and[t] |-> t
    xor[t] |-> t
    add[t] |-> t
    mul[t] |-> t
    shift_left[t] |-> t
    shift_right[t] |-> t

Interface PRNG<|n:Integer|> with
    next[|n|] |-> n

How do we create an instance of this interface for particular n1 and n2? Note: Here integer is an interface for all integer types like Signed_32, Unsigned_64 etc.

Here's an updated version:

Actor XorShiftPlus[x:Unsigned_64, y:Unsigned_64]
    s0 := x,
    s1 := y ()
    implements PRNG<|Unsigned_32|> using
        next[size:Unsigned_32]:Unsigned_32 ->
            Let t0 <- s1,
                t1 <- s0,
                t2 <- t1.xor[t1.shift_left[23]],
                t3 <- t2.xor[t0].xor[t2.shift_right[17]].xor[t0.shift_right[26]] ()
            Unsigned_32.[t0.add[t3].and[0xffffffff].mul[Unsigned_64.[size]].shift_right[32]] ()
            afterward
                s0 := t0,
                s1 := t3 ()

What do you think about operators like '+', if they are part of the Integer interface should I write them "t1.add[t3]"? I think xor and shift make more sense this way. There are really three ways of doing it, I am not sure which is preferable:

add.[x, y]
x.add[y]
x + y

Which is the preferred way?

An Actor is allowed to directly update its own variables

An Actor is allowed to directly update its own variables with any required message passing.

re sending and receiving messages

What are the basic capabilities of an Actor?

I would say sending and receiving messages.

These might help:

Just this section: https://en.wikipedia.org/wiki/Actor_model#Fundamental_concepts

Just page 1: https://hal.archives-ouvertes.fr/hal-01163534

The first 4 minutes or so: letitcrash.com/post/20964174345/carl-hewitt-explains-the-essence-of-the-actor

Code should be as referentially transparent as possible

Code should be as referentially transparent as possible.

Consequently assignments should go after the expression for return value.

Referential Transparency

I thought that as soon as you have state in an actor, it is no longer referentially transparent, so why try and pretend it has a property it does not. Referential transparency means that you can cache the result, or that the result only depends on the arguments, as far as I remember. I think its either referentially transparent or not, there are no degrees of referential transparency.

Referential transparency:same expression referring to same thing

Referential transparency is the same expression referring to same thing in a program scope.

This statement is very hard to parse.

If I insert the word "only" and then negate the wording in the middle then it becomes:

Referential transparency is no two expressions referring to the the same thing in a program scope.

This is essentially the property of being "alias free". If this what you were implying then it would seem that you agree with Keeane about the definition, but disagree with him about his extension of it to a binary property.

If this is the case then it would be more helpful to provide him with a counter-argument: that it is not clear what referential transparency would imply on an actor as a whole - but the SSA transformation that you applied to his code removes false aliasing (caused by reusing the same variable names) and thus can be seen as maximising the number of sub-expressions that are referentially transparent.

Or not - as I said it was particularly difficult for me to parse what you wrote.

"referentially transparent" is *not* the same as "alias free"

Being "referentially transparent" is not the same as "alias free."

ActorScript uses several means to increase referential transparency including the following:
* placing assignment commands after expression for return value
* not allowing assignment command except to local instance variables of an Actor in a cheese continuation
* using tail recursion instead of assignment loops, e.g. do, for, while etc.

Readability

I get why these things can be a good idea, but I am more concerned about readability and understandability. For loops with indexes are very readable:

for i = 1 to 10 {
    v[i] = u[i] + w[i]
}

Especially with more complex nested loops.

1.7 Concepts in ActorScript

For the other interfaces I have something like:

------------------------------------------------------------------------------
-- 1.7 Concepts

Interface FunctionalProcedure<|u|> with
    [*] |-> u
    
Interface UnaryFunction<|t, u|> with
    [t] |-> u
    
Interface HomogeneousFunction<|t, u|> with
    [t*] |-> u 

However, I can't figure out how to construct these as a hierarchy building on FunctionalProcedure as it is done in the "Elements of Programming" book.

I am stuck on FunctionalProcedures. I need to declare an interface, where the message does not contain any mutable references, nor does the actor receiving it have any internal state? Can I reason in this way with ActorScript? My first impression is that this is impossible without "effects" in the type system. PureScript (based on Haskell) has an 'Eff' monad that would be ideal for controlling side-effects:
https://leanpub.com/purescript/read#leanpub-auto-side-effects-and-purity

No guarantees about implementations of interfaces

There are no guarantees about the implementations of interfaces.

However, implementation types are branded and the implementation is known.

Adding Effects

It seems I need to look at how the type system might be extended with effects if I am going to be able to do what I want with ActorScript. I should be able to carry on with unconstrained interfaces and rely on the programmer only making correct claims for now.

Homogeneous Functions

A homogeneous function is one where all the input arguments have the same type, but we don't care how many arguments there are. Is this constraint expressible in the current ActorScript type system?

[Integer*] is the type of a list with integer elements

[Integer*] is the type of a list with integer elements. Of course, argument lists are lists :-)

On the other hand [Integer, String] is the type of a two-element list with an Integer followed by a String.

Note that [ ]:[Integer*] is the empty list of integers.

Predicates on Types

I'm still stuck on this section. I need to declare:

- "UnaryFunction" which is a FunctionalProcedure with arity one.

- "HomogeniousFunction" which is a FunctionalProcedure with arity > 0 and all input types the same.

- "Predicate" which is a FunctionalProcedure where the codomain is Bool.

- "HomogeneousPredicate"

- "UnaryPredicate"

The problem is these should function like constraints, as in we don't care what the procedure is called. A clear example would be:

- "Operation" which is a HomogeneousFunction where the Codomain and Domain are the same.

- "BinaryOperation" which is an Operation with Arity 2.

I'll show the example in C++, we want to declare a "power_left_associated" function:

template <typename I, typename Op>
    requires(Integer(I) && BinaryOperation(Op))
Domain(Op) power_left_associated(Domain(Op) a, I n, Op op) {
    // Precondition: n > 0
    if (n == I(1)) return a;
    return op(power_left_associated(a, n - I(1), op), a);
}

How would I define this in ActorScript?

I want to write something like:

PowerLeftAssociated<|i:Integer, bin_op:BinaryOperation|>[a:op.domain[], n:i, op:bin_op]
    === if n = i.[1] then a else op.[PowerLeftAssociated.[a, n - i.[1], op], a]

I can define:

Interface BinaryOperation<|t|> with
    [t, t] |-> t

PowerLeftAssociated<|t|>[a:t, n:Integer, op:BinaryOperation<|t|>]
    === if n = i.[1] then a else op[PowerLeftAssociated.[a, n - i.[1], op], a]

Happy with these interfaces?

Do these interfaces look okay? They are slightly pretzeled (turned inside out) compared to the original type predicates. I won't find out if this is going to be a big problem until I get further, but you can already see you lose the hierarchical definitions, I cannot define a transformation in terms of homogeneous-function with arity one and domain and codomain the same, but I can define it.

2.1 Transformations in ActorScript


------------------------------------------------------------------------------
-- 2.1 Transformations

Interface Predicate with
    [*] |-> Boolean    // looks like Predicate can't be defined.

Interface HomogeneousPredicate<|t|>
    [t*] |-> Boolean

Interface UnaryPredicate<|t|>
    [t] |-> Boolean

Interface Operation<|t|>
    [t*] |-> t

Interface Transformation<|t|>
    [t] |-> t

Interface BinaryOperation<|t|>
    [t, t] |-> t

PowerUnary<|t|>[x:t, n:Integer, f:Transformation<|t|>]:t ===  
    // Precondition: n >= 0
    //     /\ forall i in N . 0 < i <= n => f^n(x) is defined
    n ? n.new[0] (:) x
     else (:) PowerUnary.[f.[x], n - n.new[1], f] 

Can I define the precondition in ActorScript rather than comment?

Somehow, redefining PowerUnary to use recursion instead of a while loop, makes it seem like a different algorithm. The original is:

template<typename F, typename N>
    requires(Transformation(F) && Integer(N))
Domain(F) power_unary(Domain(F) x, N n, F f) {
    while (n != N(0)) {
        n = n - N(1);
        x = f(x);
    }
    return x;
}

re 2.1 transformations....

Interface Predicate with
[*] |-> Boolean

Is there an Any type in ActorScript?

Also: "Integer.[1]" is persumably no different from "1".

I think you are reaching for a way to have a type parameter which is constrained to be a (possibly trivial) extension of some other type. (For which purpose maybe Hewitt can help.)

[*] and Integer

I suspect [*] is incorrect, i am trying to express any number of any type argument.

Integer.[1] Is because "Integer" as I am using it is an interface not the built in Integer type. I am imagining something like:

Interface Integer with ...
Actor Unsigned_32 implements Integer using ...
Actor Unsigned_64 implements Integer using ...
Actor Signed_32 implements Integer using

I don't suppose it quite works, as Integer.[1] is supposed to be whichever integer type is passed. I have changed it so the type of integer is a type parameter.

re i am trying to express any number of any type argument.

i am trying to express any number of any type argument.

There is no "Any" type in ActorScript and Direct Logic. You are not allowed to express that confused concept. That's because such a type opens the door to unwanted paradoxes.

It might help or it might cause confusion to mention that there *is* in DL a type (called Type) of all types. But while all types have type Type, it is not the case that all types are a subtype of Type.

Interface Integer with ...

I'm not sure off the top of my head how you express the concept of a type parameter that is constrained to be an extension of some other type, which is what you seem to be reaching for.

Unconstrained procedure

We can have unconstrained procedures, which have any number of any typed arguments. So what I want to do is constrain the return type, without constraining the arguments. It's not a confused concept, but trying to express it in ActorScript is confusing :-)

You are right, what I really need is to be able to constrain type parameters to be extensions or implementations of interfaces. Later it will need to be more than one, say a type that extends both Iterator and Readable for example.

re We can have unconstrained procedures, which have any number o

We can have unconstrained procedures, which have any number of any typed arguments.

Yes and no.

You can define an ActorScript type (let's call it "HaskelDomain") and, with suitable elaboration of that type, you get Haskel (up to syntax).

[Aside: An ActorScript specification of a Haskell interpreter could be an an amazing thing for exploiting latent concurrency in some Haskell programs.]

I presume that conversely, in Haskell, you can can define a type (call it "Actor"), and with suitable elaboration you get an ActorScript interpreter.

The situation is not entirely symmetric. The Actor description of Haskel will be complete and faithful but the converse, not so much absent extensions to Haskel.

Nevertheless, you can define actors that use "HaskelDomain" as if it were an Any type. But it is not an Any type in ActorScript.

ActorScript has no Any type.

I sense (perhaps incorrectly, perhaps correctly) that you do not really understand what the motivation is for excluding an Any type.

It is not a trivial question to answer but it relates to paradoxes and barbers. :-P

You are right, what I really need is to be able to constrain type parameters to be extensions or implementations of interfaces. Later it will need to be more than one, say a type that extends both Iterator and Readable for example.

I think that's right.

The "later" situation sounds like it refers to a type that could be called IteratorAndReadable.

ReadableIterator

You should be able to declare:

Interface ReadableIterator<|t|> extends Readable<|t|>, Iterator<|t|> ()

But its going to result in a needing to define a lot more types.

vague reply re ReadableIterator

But its going to result in a needing to define a lot more types.

Don't forget to consider what is necessary and what is not necessary. That which is concise-ish in C++ might be concisely accomplished in a different environment in a non-trivially different way.

Create new instance of type T.

The use case is we have a generic procedure, which accepts a parameter of type I (an interface). If this interface is Integer the implementation might be Signed_32 or Signed_64. The subtype of integer is important as, for example PRNG algorithms rely on the integer bit length.

In the generic procedure we need a new value of the subtype, not the interface type. We want a new instance of Signed_32 or Signed_64 depending on which type is actually passed to the procedure. Is there an idiomatic way to do this in ActorScript?

To enforce branding, implementation types cannot be subtytped

To enforce branding, implementation types cannot be subtyped.

Procedures can take as type parameters both interface types and implementation types.

[personal editorializing removed -- Ehud]

More details?

So given:

F<t:Interface>[x:t] === ...

Is this valid? Can I construct a "t" inside "F" by calling "t.[x]"?

Procedure with type parameter

The following is OK:

Actor aProcedure◅aType▻
    [x:aType] -> ...

Interfaces

So how do get a new instance of whatever type aType is, but at the same time constrain aType to be a particular interface?

A typical example might be wanting to reverse a read only collection, that only supports a forward iterator. The reverse procedure will need to create a fresh copy of the collection to put the reversed contents into. We want to write reverse generically, so we don't need a separate version for each collection type, and we want it to work on user defined collections that support a forward-iterator as well. We want the collection type returned from reverse to be the same as the one passed. We need the passed collection to implement the forward-iterator interface.

Can we specify an procedure in the interface to do this?

re interfaces

So how do get a new instance of whatever type aType is

The collection returned from reverse contains members from the collection passed to reverse. They have not changed implementation type,

You don't need a constructor for the unknown element implementation type.

Collection Constructor

You need a constructor for the unknown collection type. You might pass a doubly linked list, singly linked list, linked hash table, vector, map etc. Because the input collection is read-only, you need to construct the output collection before filling it with the elements. We want reverse to be generic over collection type to avoid having to write the same algorithm multiple times. Reverse using a forward-iterator is one algorithm, no matter which collection type it is operating on.

re "You need a..."

You need a constructor for the unknown collection type. You might pass a doubly linked list, singly linked list, linked hash table, vector, map etc. Because the input collection is read-only, you need to construct the output collection before filling it with the elements.

If you want the algorithm to take a constructor (or empty collection to use for output) as a parameter, do that.

We want reverse to be generic over collection type to avoid having to write the same algorithm multiple times.

That seems trivial if you don't begin from an assumption the type system will do that for you in a particular way.

See below.

Indeed, the solution below seems acceptable.

Is this valid?


Interface Cons with
    new[] |-> Cons

Actor Thing extends Cons using
    new[]:Thing -> Thing.[]

test[t:Cons] === t.new[]

Will test return a new instance of "Thing"?

Almost correct


Interface Cons with
    new[] |-> Cons

Actor Thing[]
  implements Cons using
    new[]:Thing -> Thing[]

Actor Test
   [t:Cons]:Thing -> t.new[]

Casting Numbers

How is casting between numeric types handled? Presumably you want to allow casting from unsigned to signed, 32 bit to 64 bit etc? I am assuming there would be types for infinite precision integer, rational and real, as well as the standard hardware types of signed and unsigned ints (8,16,32,64,128,256...) and floats (32,64...)?

Excellent question!

Keean,

Excellent question!

What do you think should be done?

Casting

It depends on the safety/performance trade off. Normally I would not want to introduce new syntax, as constructors can be re-used as in:

Unsigned_32.[1]

Would make sense, providing there is no performance cost, you would want to make sure literals were converted to the correct format at compile time. Obviously casting bigger is always safe, you might want to throw an exception when casting smaller if the number is too big, or if it is negative when casting from signed to unsigned. You may want to have an unsafe cast that truncates without an exception for performance reasons.

As I would have an interface for all integers, this allows casting from any integer type to any other to be handled by a single constructor. Of course as the casting relies on specific machine code, it either needs to be a built-in, or you would need to allow in-line assembler like GCC.

2.2 Orbits (and Associated Types) in ActorScript

The problem I have with orbits, is that I am not sure how to represent associated types in ActorScript. If types are actors, can I have a function that returns a type? For example a "Trandformation" should have an associated distance type, which represents a suitable metric such that:

Given a transformation type F, DistanceType(F) is an integer type large enough to encode the maximum number of steps by any transformation "f in F" from one element of T = Domain(F) to another

So we would like the interface for Transformation to look like this:

Interface Transformation with
    DomainType[] |-> Type,
    DistanceType[] |-> Type,
    [DistanceType.[]] |-> DistanceType.[] ()

If this is not possible we have to do something like

Interface Transformation<|dom, dist|> with
    [dom] |-> dom ()

Distance<|dom, dist|>[x:dom, y:dom, Transformation<|dom, dist|>]:dist ===
    // Precondition: y is reachable from x under f
    Orbit.[z:dom, n:dist] === 
        z ? y (:) n
         else (:) Orbit.[f.[x], n + dist.[1]]
    Orbit.[x, dist.[0]]

The problem with the above is that the transformation should define the domain and the distance, rather than being input type parameters.

So is there a way to have procedures that return a type in ActorScript? If types are actors, it seems like it should be possible.

2.3 Collision Point in ActorScript


------------------------------------------------------------------------------
-- 2.3 Collision Point

CollisionPoint<|dom, dist|>[x:dom, f:Transformation<|dom, dist|>,
p:UnaryPredicate<|dom|>]:dom ===
    // Precondition: p.[x] <=> f.[x] is defined.
    Orbit.[slow:dom, fast:dom] ===
        fast ?
            slow (:) Let slow1 <- f.[slow]
                p.[fast] ?
                    False (:) fast
                    True (:) Let fast1 <- f.[fast]
                        p.[fast] ?
                            False (:) fast1
                            True (:) Let fast2 <- f.[fast1]
                                Orbit.[slow1, fast2]
            else (:) fast
    p.[x] ?
        False (:) x
        True (:) Orbit.[x, f.[x]]
    // Postcondition: return value is terminal point or collision point

There are a few issues with this:

1. Even though the procedure "CollisionPoint" does not depend on the DistanceType, we have to pass it as a type parameter because of the lack of associated types. This could become a big problem later with many type parameters that are actually unused proliferating. I don't see any way around it at the moment. I hope there is, otherwise this seems a big problem with the ActorScript type system.

2. It is not clear how to define a transformation that is only valid on integers? Can interfaces be specialised in ActorScript?

3. It seems a lot less readable than the original imperative algorithm, included for comparison:

template<typename F, typename P>
    requires(Transformation(F) && UnaryPredicate(P) && Domain(F) == Domain(P))
Domain(F) collision_point(const Domain(F)& x, F f, P p) {
    if (!p(x)) return x;
    Domain(F) slow = x;
    Domain(F) fast = f(x);

    while(fast != slow) {
        slow = f(slow);
        if (!p(fast)) return fast;
        fast = f(fast);
        if (!p(fast)) return fast;
        fast = f(fast);
    }
    return fast;
}

Actors not functions

Perhaps it would be simpler if you avoided the mystery predicate "p" and used exceptions.

Also, you currently have it that actors of a type Transformation are strictly function actors, accepting only anonymous messages (".[args]").

Perhaps it would be simpler if Transformations also took messages like ".domain[]" (returning a Type actor).

For that matter, from a certain point of view a function actor is a special case of a more general kind of actors that accept one-way messages that include a "return" address parameter, and that send their result to that address. (The "return" address doesn't *have* to be the address of the sender of the "call".)

For that matter, the "return" address might be configured entirely separately from the ".[]" message.

From that point of view a Transformation might be seen as a kind of asynchronous signal processing unit -- taking an input signal of the domain type and sending an output signal of the same type.

Can concepts like CollisionPoint be adapted to that more circuit-like view of actors as signal processors?

Interesting Post

Only just saw this. Interesting things to think about.

Returning a type actor is something I wanted to do, how do I do this?

re lack of associated types

In general, if you find an abstraction that ActorScript seems to preclude (which would be surprising) that is more interesting than identifying abstractions not (necessarily) yet elaborated.

E.g.: is the "lack of associated types" (whatever you specifically mean) essential to ActorScript or incidental?

Proliferation of unused type arguments

The problem is shown above, CollisionPoint does not depend on the "dist" type parameter, but because it is needed for "Transformation", it has to be supplied. As we build up the library this is going to become a problem with algorithms requiring dozens of unused type parameters.

It is also a question of definition, the transformation should imply its domain and distance types.

Associated type is a well known concept in PL, so perhaps you should read up about them. You could look at ML or Haskell.

I not yet saying there is no suitable abstraction in ActorScript, I am asking what one might be. You can see the problem, what is the solution (there are many possibilities). For example can an ActorScript procedure return a type? I am not sure, but types are actors, and procedures can return actors, so is there specific syntax for this?

The C++ version shows what we are trying to achieve, a procedure "CollisionPoint" that depends on the type of the Transformation and the type of the UnaryPredicate, not the type of the Domain of the Transformation and the DistanceType of the Transformation which it the closest I can get at the moment.

Re: associated type

The Rust doc isn't half bad, I feel. https://doc.rust-lang.org/book/associated-types.html

Looks Nice

Yes, that does look good, if only I could get over the use of the term 'trait' for an interface.

Traits sometimes mean

Traits sometimes mean interfaces, sometimes they mean mixins, it really depends on your ideology.

Oh that's interesting.

It's interesting because it holds out (?maybe?) the promise of something like C++ templates that isn't so verbose as to be unreadable and unusable.

re Proliferation of unused type arguments

You are translating code written in a functional style to a language grounded in Actors, not functions. You care more about making code look the same or similar in two languages, than in taking apart the CollisionPoint concept and trying to figure out the ways in which it makes sense in an Actor-based world.

quoth

i think he wrote:

> I not yet saying there is no suitable abstraction in ActorScript, I am asking what one might be.

:-)

(minecraft) re quoth

Fair enough.

I wonder if today's kids that build programs out of parts in minecraft will find actors obvious and natural.

Collision Point

What actor script appears to be lacking is any way of expressing the relation between two types. Say I have a type map: A -> Int, B -> Float, where A, B, Int, Float are all types. If every time we use A we know some other type must be an Int, we don't want to manually pass the type parameter Int, we are increasing the chance of making a mistake in the program. It is also appears to be lacking a way to express the relations between Actors and types. For example we want to define a type large enough to contain the collision point of a procedure. This type depends on the definition of the procedure, not its type. How do I express the relationships between types and types that depend on actors in ActorScript? Note I say "appears" to be lacking. As far as I can see Direct Logic provides a way of expressing these type relationships, I just can't see a way of expressing what I want, I just can't find any examples or explanations of how (or if) it should work. One thing that could work would be to allow Interfaces to have output types as well as input types so that:
Interface Transformation[] -> dom, dist with
    [dom] |-> dom ()

PlusOne[x:Integer_32] implements Transformation ===
    Assert dom := Integer_32
    Assert dist := Integer_32 
    x + 1
Note: because the domain of the transformation is a 32bit integer, the maximum distance can be expressed using a 32bit integer as well, due to the values wrapping, but this is only true for this particular transformation. I cannot see that this breaks any of the rules of DL/IRDL, in fact ActorScript does not seem related to DL/IRDL, but is derived from C++/Java/JavaScript (obviously with the addition of actors, and the removal of imperative features), so I don't see any sacred cows here.

re That's the best algorithm

That's the best algorithm...There will a be proliferation of type arguments, this is a problem with ActorScript.

You can write the algorithms you're interested in (CollisionPoint, variations on Orbit, etc.) generically.

For example, I believe you can straightforwardly define:

The interface StepanoidDomainElement which provides an equality relation among elements.

The interface StepanoidDistance which provides a successor function and an order relation.

The interface Stepanoid which is a structure containing (for you examples) only a "zero" actor of type StepanoidDistance.

The interface StepanoidTransformation which is a structure comprising:

  • a function of type [StepanoidElement] |-> StepanoidElement
  • a stepanoid of type Stepanoid

I believe you can then write Orbit, CollisionPoint, etc. generically over those abstract types.

Note that this is not quite "associated types". This is more like the kind of abstraction you'd see in a graph theory or algebra text book: we abstract away everything but the essential mathematical structure.

There doesn't appear to be any need for type parameters in Orbit and CollisionPoint at all.

(Separately, given concrete domains, distances, and transform functions, you can write a little bit of code that assembles them into stepanoid structures.)

Generic

CollisionPoint needs to be generic over any type of transformation, which means it may be used several times in the same program with transformations of different types. It seems to me that the way you describe implementing it would not work for this requirement?

Also I don't think Interfaces can contain actors?

Interfaces define type constraints on actors (well more specifically require the actor / procedure to provide messages with certain type signatures - in other languages the type systems can express the total interface as type, for example Haskell record types).

StepanoidDomainElement will need to be parameterised on the type of the domain?

It would really help to see some code, because I don't understand how this could work.

re CollisionPoint

Please note that you completely rewrote your comment after I replied to it. As a result, my reply quotes comments you later erased. Please try to avoid doing that.

Regarding:

For example we want to define a type large enough to contain the collision point of a procedure. This type depends on the definition of the procedure, not its type. How do I express the relationships between types and types that depend on actors in ActorScript?

Structures will work fine but note that none of your Stepanov examples so far seem to need type parameters at all.

Rewriting

I realised which arguments were important and which were distractions, so i rewrote it to save everyone time, it is unfortunate you had already started replying to it.

re As for not needing type parameters

As for not needing type parameters, I don't think you have understood the examples,

Pretty sure I have. Taking your "Distance" example, I think the algorithm can be generically expressed this way:

Interface StepanoidElement with
  equal.[StepanoidElement] ↦ Boolean §▌

Interface StepanoidDistance with
  successor.[] ↦ StepanoidDistance §▌

Interface StepanoidTransformation with
  zero.[] ↦ StepanoidDistance,
  f.[StepanoidElement] ↦ StepanoidElement,
  definedAt[StepanoidElement] ↦ Boolean §▌

distance.[e:StepanoidElement, t:StepanoidTransformation] →
  Let orbit ← Function[x:StepanoidElement,d:StepanoidDistance] →
                t.definedAt[x] �
                  True ⦂ orbit.[t.f[x], d.successor[]] ⦶
                  False ⦂ d ⍰。
    orbit.[e, t.zero[]]▌

Self Referential Interfaces

Okay, first thing, I didn't realise you could have in Interface reference its own type. Are there any examples of this in the papers? It may solve some of the problems.

Stepanov defines a "RegularType" as one supporting equality, inequality and assignment. It would be good to replace 'StepanoidElement' with "RegularType" I think.

re self referential

Okay, first thing, I didn't realise you could have in Interface reference its own type. Are there any examples of this in the papers?

There is an example in an earlier comment by Hewitt in this thread.

Same Element.

It seems like there is nothing to constrain the Transformation so that it returns the same subtype of StepanoidElement that it is passed. So I don't think this imementaton meets the requirements for defining a transformation.

Edit: also the stopping condition looks wrong, the stopping condition is the current position in the orbit is equal to the terminating position. We pass distance two points on the orbit, x and y, and it calculates the distance between them. Your distance only takes a single element and the transform, so it can't be right. I don't think this is a major flaw, just a bug, but the first point about transformation not having the correct type is important.

re Same Element

It seems like there is nothing to constrain the Transformation so that it returns the same subtype of StepanoidElement that it is passed.

First, let's be more accurate about "subtype". In ActorScript, you will mean either another interface type that extends StepanoidElement, or you will mean an implementation type that provides StepanoidElement.

Second, nothing in the generic definitions of Distance, Orbit, or CollisionPoint require that transformations return actors of the same extension type or implementation type they are passed. To impose such a requirement would be to impose an arbitrary and needless restriction.

Third, of course, clients of these types and functions may want more specific types. Let's consider an example.

Suppose ClosedDictionary is an interface type for a data structure that is a map from words to definitions. It is "closed" in the sense that every word found in a definition also has an entry in the dictionary.

Suppose aClosedDictionary.longestInDefinition[Word] |-> Word: the longestInDefniition sent to a dictionary with a word as its argument returns the longest word found in the corresponding definition.

Now we can wrap any given word as a StepanoidElement using string equality as the equivalence relation. We can wrap 0 (of type Integer) as a StepanoidDistance. We can construct a StepanoidTransformation from a given dictionary using the longestInDefinition message.

You'll see that the transformation function we define takes and returns actors of type StepanoidElement but, internally, it must treat these actors as Word actors. Conditional downcasting is permitted for that (but in the general case may cause an exception to be thrown).

The run-time cost of that conditional downcast can be fully eliminated automatically if all the definitions are visible during compilation.

The conceptual cost of that conditional downcast can be eliminated by putting an invariant assertions in the definitions of the Stephanoid* wrappers.

The pattern of Stphanoid* wrappers with such invariants might turn out to be a common pattern. Finally, that pattern of wrapper can be usefully abstracted using parameterized types.

Orbits in a Domain

We are talking about orbits in a domain, for example the orbit of a PRNG for a given seed in the Integer domain.

If the Transformation is not restricted to a single domain, we cannot say what domain it is in.

A list of 'StepanoidElements' is a very different thing from a list of integers where an integer is a 'StepanoidElement' element.

I also think you would end up having to wrap every type in StepanoidElement, which I would rename RegularType, and include disequality, and assignment messages too (can you define assignment?)

re Orbits in a Domain

If you want something like versions of CollisionPoint that are specialized for some type, they are easy to construct from the generic implementation I gave you.

Really, the type system here is more flexible than the template system Stepanov is forced to use. Because it is more flexible, it requires fewer "hacks" like associated types. The type system here is also closer to the kind of vernacular usually used for basic math.

Algorithms

The point is I should not have to repeat the algorithm, to get type specialised versions. Stepanov is not as restricted by the C++ type system as you think. In fact it is too unrestricted, and adding type constraints to restrict the types is what is needed for C++.

There is nothing particularly clever or innovative about this type system. Its very similar to Java's.

You could look at 'G' to see how a language designed for generic programming might look: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.7221&rep=rep1&type=pdf

re I should not have to repeat the algorithm

The point is I should not have to repeat the algorithm, to get type specialised versions.

You do not. I can't imagine why you would think you would have to. I've laid out all the pieces of how to do it for you.

Because of the words you used.

If you want something like versions of CollisionPoint that are specialized for some type, they are easy to construct from the generic implementation I gave you.

You say "versions" of CollisionPoint, and "they" are easy to construct. This implies I need multiple "versions" of CollisionPoint for each specialised type, and I have to manually "construct" them.

re words

You say "versions" of CollisionPoint, and "they" are easy to construct. This implies I need multiple "versions" of CollisionPoint for each specialised type,

You only have to write the generic algorithm once, generically, similarly to how I gave you a generic version of Distance.

Already Generic

To be fair the version I wrote was also already generic, just different, and I think the solution I am looking for is somewhere in the middle. In any case its clear I misunderstood what you were saying above.

Something Like This?


Interface RegularType with
    Equal[RegularType] |-> Boolean ()

Interface Integral with
    Successor[] |-> Integral,
    Predecessor[] |-> Integral,
    Twice[] |-> Integral,
    HalfNonnegative[] |-> Integral,
    BinaryScaleDownNonnegative[] |-> Integral,
    BinaryScaleUpNonnegative[] |-> Integral,
    Positive[] |-> Boolean,
    Negative[] |-> Boolean,
    Zero[] |-> Boolean,
    One[] |-> Boolean,
    Even[] |-> Boolean,
    Odd[] |-> Boolean ()

Interface Transformation with
    Zero[] |-> Integral,
    F[RegularType] |-> RegularType ()

Distance.[x:RegularType, y:RegularType, t:Transformation]:Integral ===
    Orbit.[z:RegularType, d:Integral] ===
        z.Equals[y] ? True (:) d
                     False (:) Orbit.[t.F[z], d.Successor[]]
    Orbit.[x, t.Zero[]]

I am still concerned about maintaining the type constraints, for example a definition of Integer, successor should return the same type. So for example with the interface definition above you could define:

successor[x:Integer_64]:Integer_32 -> x + 1

Which would satisfy the interface, but would not make a lot of sense. There is also a problem with the parameters to Distance (x and y) which should be the same type, but in fact could be any regular type in this implementation.

re Interface Integer

There is a built-in type called Integer. Suppose you use the name IntegerLike, instead.

The signature of the "successor" message would be:

  successor[IntegerLike] |-> IntegerLike

a message signature like:

successor.[x:Integer_64]:Integer_32

is not related in any way to interface type IntegerLike.

The fact you wrote that suggests that may be you think interfaces are extensional. They are not. They are intensional. An actor implements a particular interface by explicitly saying it is implementing that interface and by providing message definitions that exactly match the signature of that interface. An actor does not implement an interface simply because it coincidentally implements messages that look similar.

Constraints

I could use Integral, its an adjective, so an Integral Value is an Integer. I think the C# docs use integral in this way.

Sorry, I wrote the wrong thing because I was trying to avoid typing the whole implementation. What I meant was:

Actor Integer_32[x:Integer_32] implements Integral using
   Successor[]:Integer64 -> x + 1,
   ... ()

As you can see, the interface definition of Integer allows one implementation to return a different implementation from the functions.

What I want is to be able to define the interface so that the actor implementing it must return the same type, so that the above is not allowed, but the below is:

Actor Integer_32[x:Integer_32] implements Integral using
   Successor[]:Integer32 -> x + 1,
   ... ()

The following looks okay for the definition of Distance:

Interface RegularType<|t|> with
    Equal[t, t] |-> Boolean ()

Interface Integral<|t|> with
    Successor[t] |-> t,
    Predecessor[t] |-> t,
    Twice[t] |-> t,
    HalfNonnegative[t] |-> t,
    BinaryScaleDownNonnegative[t] |-> t,
    BinaryScaleUpNonnegative[t] |-> t,
    Positive[t] |-> Boolean,
    Negative[t] |-> Boolean,
    Zero[t] |-> Boolean,
    One[t] |-> Boolean,
    Even[t] |-> Boolean,
    Odd[t] |-> Boolean ()

Interface Transformation<|dom, dist|> with
    Zero[] |-> Integral<|dist|>,
    F[RegularType]<|dom|> |-> RegularType<|dom|> ()


Distance<|dom, dist|>.[x:RegularType<|dom|>, y:RegularType<|dom|>,
t:Transformation<|dom, dist|>]:Integral<|dist|> ===
    Orbit.[z:RegularType<|dom|>, d:Integral<|dist|>] ===
        z ? y (:) d
         else (:) Orbit.[t.F[z], d.Successor[]]
    Orbit.[x, t.Zero[]]

It appears there is no way to get one of the types, so I have put a '?' to indicate where we cannot know the needed type. It would appear the type system is incomplete, as I can write programs where there are types I cannot actually write down. (edit: this is rubbish, its obvious what the type should be)

When we go to implement CollisionPoint, we end up needing to pass it the type parameter for "dist", which us not used by CollisionPoint. I think this can be fixed by splitting Transformation into:

Interface Transformation<|dom|> with
    F[RegularType]<|dom|> |-> RegularType<|dom|> ()

Interface MeasurableTransformation<|dom, dist|>
    extends Transformation<|dom|> with
        Zero[] |-> Integral<|dist|> ()

re Integral

Actor Integer_32[x:Integer_32] implements Integral using
   Successor.[]:Integer64 -> x + 1,

I stopped there since you have ignored what I told you about type signatures in interfaces.

Best so far?

I think this definition meets all the requirements?

Interface RegularType<|t|> with
    Equal[RegularType<|t|>] |-> Boolean ()

Interface Integral<|t|> with
    Successor[] |-> Integral<|t|>,
    Predecessor[] |-> Integral<|t|>,
    Twice[] |-> Integral<|t|>,
    HalfNonnegative[] |-> Integral<|t|>,
    BinaryScaleDownNonnegative[] |-> Integral<|t|>,
    BinaryScaleUpNonnegative[] |-> Integral<|t|>,
    Positive[] |-> Boolean,
    Negative[] |-> Boolean,
    Zero[] |-> Boolean,
    One[] |-> Boolean,
    Even[] |-> Boolean,
    Odd[] |-> Boolean ()

Interface Transformation<|dom|> with
    F[RegularType<|dom|>] |-> RegularType<|dom|> ()

Interface MeasurableTransformation<|dom, dist|>
    extends Transformation<|dom|> with
        Zero[] |-> Integral<|dist|>,

Distance<|dom, dist|>.[
    x:RegularType<|dom|>,
    y:RegularType<|dom|>,
    t:MeasurableTransformation<|dom, dist|>
]:Integral<|dist|> ===
    Orbit.[z:RegularType<|dom|>, d:Integral<|dist|>] ===
        z.Equal[y] ?  
            True  (:) d
            False (:) Orbit.[t.F[z], d.Successor[]]
    Orbit.[x, t.Zero[]]

We can then define CollisionPoint like this:

CollisionPoint<|dom|>.[
    x:RegularType<|dom|>,
    t:Transformation<|dom|>,
    p:UnaryPredicate<|dom|>
]:RegularType<|dom|> ===
    // Precondition: p.[x] <=> f.[x] is defined.
    Orbit.[slow:dom, fast:dom] ===
        fast.Equal[slow] ? 
            False (:) fast
            True  (:) Let slow1 <- t.F[slow]
                p.[fast] ?
                    False (:) fast
                    True  (:) Let fast1 <- t.F[fast]
                        p.[fast] ?
                            False (:) fast1
                            True  (:) Let fast2 <- t.F[fast1]
                                Orbit.[slow1, fast2]
    p.[x] ?
        False (:) x
        True  (:) Orbit.[x, t.F[x]]
    // Postcondition: return value is terminal point or collision point

re Best so far?

You wrote:

Interface RegularType with
Equal.[t, t] |-> Boolean ()

as defined, RegularType is a family of types, indexed by types.

An actor which is of a type in that family accepts messages "Equal" with two arguments of the index type and returns a boolean.

That is clearly not what you intended. Can you explain why?

Corrected

I was already (hopefully) correcting it. See above.

There is nothing wrong with having 'Equal[t, t] |-> Bool' but it would mean having to pass the RegularType actor separately from the two values I want to compare. However its not what I intended you are right.

re corrected

Distance does not type check. I mostly stopped there.

In general, the style is awkward because you are needlessly indexing these types. I suggest writing this stuff generically and if you want more specialized versions, do that in wrappers. But I repeat myself.

Distance type checking

I can't see any type errors (edit: I found some typos, maybe I've fixed it already). What error did you find? I don't understand what you mean by wrappers? Could you give an example?

I don't agree that the type parameters are unnecessary. An implementation of Integral that has as successor that returns a different Integral type is not what I want to allow.

Edit: looks like this approach isn't going to work because we want the 'Zero' message to define the type of Integral returned by Distance, but 'dist' is an input type parameter, so it won't work.

re distance type checking

I don't understand what you mean by wrappers? Could you give an example?

First, tell me what do you already know about type casting in ActorScript.

I don't agree that the type parameters are unnecessary. An implementation of Integral that has as successor that returns a different Integral type is not what I want to allow.

The restriction you want is a special case and can be solved with wrappers. So, again: tell me what do you already know about type casting in ActorScript. (The topic was already discussed on LtU.)

btw (re distance type checking again)

BTW, I am going somewhere with this. I think you can answer your own question about how to specialize using wrappers with just a little leading. Conversely, I am not confident you will get it any other way.

Once you say what you already know about casting, the next question is how you can use that to write a wrapper. What problem(s), if any, do you encounter with trying to write that wrapper?

Upcasting and Downcasting

If we are using the OO versions, upcasting can always be done, downcasting only if the type is correct, otherwise it throws an exception?

re Upcasting and Downcasting

[This replies to a comment on a different branch.]

If we are using the OO versions, upcasting can always be done, downcasting only if the type is correct, otherwise it throws an exception?

Consider the generic definition I gave earlier for a distance function, over abstract "Stepanoid" types.

1. Using casting, can you define distanceInt32.[Int32, [Int32] |-> Int32]:Int32?

Definition of parametric Distance with casting (outdented)


DistanceInt32.[x:Int32, y:Int32, t:[Int32] |-> Int32]:Int32 ===
    Actor TransformationInt32 implements Transformation using
        Zero[]:Int32 -> ?,
        F[x:Int32]:Int32 -> t.[x] ()
    Int32(.)Distance.[Int32(.)x, Int32(.)y, TransformationInt32.[]] ()

Note: we can't get the correct value for Zero, as we don't have a value of type Int32. We will need to write a new copy for every different domain, so we need to parameterise.

DistanceDom<|dom, dist|>.[x:dom, y:dom, t:[dom] |-> dist]:dist ===
    Actor TransformationDom implements Transformation using
        Zero[]:dist -> ?,
        F[x:dom]:dom -> t.[x] ()
    dist(.)Distance.[dom(.)x, dom(.)y, TransformationDom.[]] ()

Problems:
- casting other actors considered bad: http://lambda-the-ultimate.org/node/5150
- this is passing in a procedure 't' whereas what we want is to pass in an actor implementing TransformationInt32.
- We can't get the "Zero" for the TransformationInt32
- It requires excessive boiler-plate programming, and seems a step backwards from the type-class based techniques.

To fix some of these problems we need to pass in the transformation, so we get:

Interface Transformation<|dom, dist|> with
    Zero[] |-> dist,
    F[dom] |-> dom ()

DistanceDom<dom, dist|>.[x:dom, y:dom, t:Transformation<|dom, dist|>]:dist ===
    dist(.)Distance.[dom(.)x, dom(.)y, t] ()         

This only fixes the problems for Transformation, if we also fix for Integral, and RegularType, then we get back to the original parameterised versions of the interfaces I defined above (which are now correct hopefully), and the Distance wrapper becomes redundant.

We are still left with the problem of 'dist' being an input parameter, when it should be an output. in other words the particuar transformation used should propogate its distance type to be the return type of the "Distance" procedure. I don't see any way of fixing this. This becomes very important later, when we want to select different algorithms depending on type, for example selecting a different reverse algorithm depending on whether the iterator is a ForwardIterator or a BidirectionalIterator. When an interface returns an 'Iterator' we lose the information about which type of iterator, which prevents us providing overloaded definitions of reverse that are specific to iterator type. We could define a wrapper that tries each possible downcast, but this would be difficult to program with and requires a lot of boiler-plate, especially as the number of possible cast combinations will increase exponentially with the number of arguments we want to specialise on.

re Definition of parametric Distance with casting

DistanceInt32.[x:Int32, y:Int32, t:[Int32] |-> Int32]:Int32 ===
    Actor TransformationInt32 implements Transformation using
        Zero.[]:Int32 -> ?,
        F.[x:Int32]:Int32 -> t.[x] ()
    Int32(.)Distance.[Int32(.)x, Int32(.)y, TransformationInt32.[]] ()

That does not type check. An implementation of an interface must use the type signatures of that interface. The last line appears nonsensical but it is unclear what you mean.

Note: we can't get the correct value for Zero, as we don't have a value of type Int32.

Everything in that sentence is false.

That's as far as I got.

Type Checking

I suppose you could instantiate an Int32 by casting zero, but it appeared from earlier comments numeric casting is not defined yet in ActorScript. I could just assume this worked so I would get (okay I've spotted the mistakes so I'll fix in the version below):

DistanceInt32.[x:Int32, y:Int32, t:[Int32] |-> Int32]:Int32 ===
    Actor TransformationInt32 implements Transformation using
        Zero[]:Integral -> Integral(.)Int32[Int32(.)0],
        F[x:RegularType]:RegularType -> RegularType(.)t.[Int32(.)x] ()
    Int32(.)Distance.[RegularType(.)x, RegularType(.)y, TransformationInt32.[]] ()

I think I have understood what you meant about the type exactly matching, there is no implicit upcasting like in Java/C++ etc. Does this mean I always have to cast to the expected interface type when passing an implementation?

Defining a parameterised version:

Distance<|dom, dist|>.[x:dom, y:dom, t:[dom] |-> dom]:dist ===
    Actor TransformationDom implements Transformation using
        Zero[]:Integral -> Integral(.)dist[dist(.)0],
        F[x:RegularType]:RegularType -> RegularType(.)t.[dom(.)x] ()
    dist(.)Distance.[RegularType(.)x, RegularType(.)y, TransformationDom.[]] ()

Does this look right now?

re Does this look right now?

  ...
  Zero.[]:Integral -> Integral(.)Int32[Int32(.)0]
  ...

Does this look right now?

No, it looks like you are making up notation. I have no idea what you intend.

Do you have a suggestion?

There's no notation made up. 0 is an actor of type Integer, so we need to cast it to type Int32:

Int32(.)0

Then we need to create an actor of type Int32 (which is initialised with an Int32):

Int32.[Int32(.)0]

Finally we need to cast to an Integral:

Integral(.)Int32.[Int32(.)0]

So no notation made up at all. Just casting '0' to Integral will not work, as when we pass the 'new' message to clone the 'Zero' actor we would get an Integer, not an Int32 which is what we want.

I can't really guess what else you were thinking of? What else can I initialise Zero with. There is no guarantee that 'x' or 'y' will be the same type - they happen to be in this case, but not in general.

What about the rest? Am I to assume that everything else is now okay with this and the parameterised version?

notation

(Note: Because of the more basic problems in your comment I did not try to figure out how you came up with a (made up) "(.)" syntax but if I had tried, I would undoubtedly have concluded you meant that to be ASCII art for "⨀" which occurs in an earlier post by Hewitt and is part of the syntax for implementation re-use (not casting).)

Regarding:

Int32.[Int32(.)0]

First, that says something like "Call the function Int32 with peculiar argument Int32-end precondition-0," (which is of course nonsense).

To review casting, its syntax and rules, see the section about "type extension" in the Actorscript paper on Hal. ("self casting" is a little bit different and is described elsewhere; that's the form that uses "⍠".)

Second, you earlier said what you know about permissible upcasting and downcasting, but it doesn't look like you are applying that knowledge here. Whatever "Int32" is meant to be, it is unlikely that 0 can be cast to Int32.

It might help to look at the Actorscript paper and try to figure out and get clear on the meanings of:

  • interface
  • interface extension
  • implementation
  • implementation re-use
  • conditional downcasting
  • upcasting from an extension
  • self-casting to an interface

When you can sort those out you should Get the (rather simple) type system.

Needed extra functionality for ActorScript types?

Thomas,

Do you see any needed extra functionality for ActorScript types?

Thanks!
Carl

Casting

So what I can find out about casting is that the book does not seem to mention it (so no wonder it seemed missing). It seems the paper on HAL has been updated since the book was published. It's a shame, as I much prefer reading from a real book than off the screen, but anyhow I suppose I will have to look online for this bit.

There is still the problem of how to create an Int32. In other languages literal numeric constants are polymorphic, and hence it is possible to cast '1234' to any type implementing Integral. In Haskell for example such a literal has the type "forall t . (Integral t) => t". I don't see how the same thing can be done in ActorScript. If we assume an Int32 can be initialised from an Integer, then we can just write "Int32.[0]". Is this reasonable? As Int32 implements Integral there is no casting necessary to pass as an Integral.

Interface RegularType with
    Equal[RegularType] |-> Boolean ()

Interface Integral extension RegularType with
    Successor[] |-> Integral,
    Predecessor[] |-> Integral,
    Twice[] |-> Integral,
    HalfNonnegative[] |-> Integral,
    BinaryScaleDownNonnegative[] |-> Integral,
    BinaryScaleUpNonnegative[] |-> Integral,
    Positive[] |-> Boolean,
    Negative[] |-> Boolean,
    Zero[] |-> Boolean,
    One[] |-> Boolean,
    Even[] |-> Boolean,
    Odd[] |-> Boolean ()

Actor Int32[x:Int32] implements Integral using
    ...

Interface Transformation with
    Zero[] |-> Integral,
    F[RegularType] |-> RegularType ()

Distance.[x:RegularType, y:RegularType, t:Transformation]:Integral ===
    Orbit.[z:RegularType, d:Integral] ===
        z.Equals[y] ? True (:) d
                     False (:) Orbit.[t.F[z], d.Successor[]]
    Orbit.[x, t.Zero[]] () 

DistanceInt32.[x:Int32, y:Int32, t:[Int32] |-> Int32]:Int32 ===
    Actor TransformationInt32 implements Transformation using
        Zero[]:Integral -> Int32.[0]
        F[z:RegularType]:RegularType -> t.[z(^)Int32](v)RegularType ()
    Distance.[x(v)RegularType, y(v)RegularType, TransformationInt32.[]](^)Int32 ()

Edit: I fixed a typo in the construction of the Int32 value of Zero. I think the definition of F and the call to Distance might still be wrong, as I don't think you can cast to Int32, as its an implementation.

re numeric literals

Just assume some constructors that take Integer (or whatever "0" happens to be) and give back the address of an Int32.

extends and extension

Here: http://lambda-the-ultimate.org/node/5221
The example uses (^) to cast an interface to an actor that extends it. I can't find any examples of this in the paper, instead on p15 it defined Fork as in interface extension of Tree. To me it seems the former is implementation extension, and the latter interface extension. Can the upcast (^) be used for both? I don't think you can cast to an implementation of an interface, but when an actor extends an interface, does it implicitly create a new interface, as well as an actor that implements it?

If so I need to change the definition of Int32 above to:

Actor Int32.[x:Integer] extends Integral using
   ...

Then the casting to/from Int32 in "DistanceInt32" should work.

There is another problem, and that is that the size of the 'DistanceType' depends on the definition of the function argument "t:[Int32] |-> Int32" so we cannot assume the DistanceType is an Int32 in DistanceInt32. For example if the transform was

F.[x:RegularType]:RegularType -> (x(^)Int32 + 65536)(v)RegularType

Then the DistanceType (which is the smallest type that can contain the distance) would be Int16.

I don't see how this can be fixed at the moment. Any suggestions?

There is also going to be a problem defining '+' as when adding two Int32 we want he answer to be Int32, but if Int32 extends Integral, and we define '+' in terms of Integral, its going to require casting to integral, and then we won't get the correct behaviour, as Int32.+ is a different operation from Int64.+

I think you really want to overload '+' for readability. The alternative is you have to use "Add32.[x, y]" and "Add16.[x, y]" etc for addition.

Plus65536.[x:RegularType]:RegularType ===
    Add32.[x(^)Int32, Int32.[65536]](v)RegularType

re extends and extension

(I think the example you linked to is slightly messed up.)

Interfaces define intentional types, their message signatures, and their sub-type relations.

Interface name [extension supertypes] with
  message signatures

Example:

Interface Tree with getHash[] ↦ Integer▌

Interface Leaf extension Tree with
  getString[] ↦ String▌

Extensions are cast to supertypes using ↓.

Types are cast to extensions (sub-types) using ↑, which can generate an exception.

The operator ↑? tests if a a cast is permitted.

aLeaf↓Tree    yields an actor address of type Tree
aTree↑Leaf    yields an address of type Leaf or an exception
aTree↑?Leaf   yields a Boolean

Interfaces do not define how messages are implemented.

Implementations define how messages are implemented.

Example:

Actor SimpleLeaf.[aHash:Integer, aString:String] 
  implements Leaf using
  getHash[] → aHash,
  getString[] → aString▌

A constructor (like SimpleLeaf) is not a type and
so it is senseless to "cast to" a constructor.

Not illustrated here: Implementations can implement more than just one
interface. Every reference to such an actor (every address for that
actor) is of just one of the interface types, though.

Re your code:

Actor Int32.[x:Integer] extends Integral using ...

the newer syntax is clearer:

Actor Int32.[x:Integer] implements Integral using ...

however that would make Int32 a constructor, not a type, which is
probably not what you intend (or maybe it is).

There is another problem, and that is that the size of the
'DistanceType' depends on the definition of the function argument
"t:[Int32] |-> Int32" so we cannot assume the DistanceType is an Int32
in DistanceInt32.

The idea of suggesting that you try to write DistanceInt32 is that
later you can generalize what you did using (at last) parameterized
types. (And I still point out that transliterating Stepanov's C++
style this way isn't going to give much insight into Actors, but, OK.)

Meanwhile, I have no idea what you intend with your types Integral,
Int32, etc.

It seems to me that you've decided to try to work out how to define
machine-level types in a language you haven't mastered the basics of
first.

extends vs implement

It is difficult to understand a language when it keeps changing as you write stuff. The new version actually makes much more sense, so I guess I was not the only person who found the old version confusing. In fact the idea of defining the type hierarchy by interfaces only (so implementations just implement them) is something I was using myself in my own projects, it wasn't easy to see that was happening from the version of the paper in the book, there needs to be a second edition already :-)

This means to implement correctly Int32 needs to be an interface (with no extra messages):

Interface Int32 extension Integral

Then the above definition of DistanceInt32 should work, but it is not doing the right thing, because we need to pass in both the transformation and its distancetype, we cannot assume all transformations in the Int32 domain have a distancetype of Int32.

progress? re extends vs. implement

Then the above definition of DistanceInt32 should work, but it is not doing the right thing, because we need to pass in both the transformation and its distancetype, we cannot assume all transformations in the Int32 domain have a distancetype of Int32.

That was the issue my suggested StepanoidDistance and StepanoidTransform are meant to address.

As an analogy, there are abstract theories of graphs and abstract theories of stepanoids. A concrete graph is characterized by a set of nodes and by edges.

If you have a library that implements abstract graph algorithms, to use it, you have some glue code that says "these concrete things (e.g., a data structure of cities and distances) are the nodes and edges". You explain explicitly how the concrete things map onto the abstract things.

Similarly, you can figure out the components of a stepanoid and express all of the algorithms in terms of that abstract structure, then apart from that you have ways of building glue code to construct stepanoids out of more concrete things like machine integers.

What I find particularly refreshing about the ActorScript way of doing this is that while, yes, the syntax can be a bit verbose... nevertheless it freely expresses the type relations as they would be expressed in conventional mathematics. (By contrast, stuff like C++ templates just seems an ad hoc nightmare of idiosyncracies which, when it does wind up looking like normal math, that is an exception rather than the rule.)

Types and casting

Its weird but my reaction is the opposite. I find all the casting to be a sign that things are not right. We really want to be able to pass an Int32 around, and not have to repeatedly turn it into a RegularType and back again. If I could return a type actor, and use it in other definitions then I could do this:
Interface Transformation with
    Domain[] |-> Type,
    DistanceType[] |-> Type,
    F[Domain[]] |-> Domain[] ()

Actor MyTransform implements Transformation using
    Domain[] -> Int32,
    DistanceType[] -> Int16,
    F[x:Domain[]]:Domain[] -> Add32.[x, Int32.[65536]] ()
Then I can define the Distance like this:
Distance.[x:t.Domain[], y:t.Domain[], t:Transformation]:t.DistanceType[] ===
    Orbit.[z:t.Domain[], n:t.DistanceType[]] ===
        z ? y (:) n
        else  (:) Orbit.[t.F[z], n.Successor[]] ()
    Orbit.[x, t.DistanceType[0]] ()
This is a lot neater than either using type parameters or casting.

re Types and casting

I find all the casting to be a sign that things are not right.

This is an opinion you've formed while trying to transliterate C++ template code into Actorscript while not really having a grip on Actorscript. I understand that everyone is entitled to their opinion, but...

We really want to be able to pass an Int32 around, and not have to repeatedly turn it into a RegularType and back again.

A situation avoided in C++ solely by virtue of having certain low machine types built-in and treated as special cases that complicate and help to make the language irregular.

I am confident you could define an Actorscript front-end that gave similar short-hands if you really wanted to.

It's a very silly complaint.

Bigger problem than just machine types.

It's got nothing to do with the machine types or the fact they are built into the language, they just happen to be a simple example of a certain kind of type relationship. We definitely want to be able to do these kind of things with user defined types/interfaces.

I think I have also proved that the problem exists, despite any lack of knowledge of actor script. Most of the complaints about this seem to have been distractions like not having the casting syntax correct, that ultimately miss the point of the underlying problem. It certainly helps now having the syntax correct, because that seems to distract some people from the real issue.

I should point out that other (successful) languages also suffer from this problem, so its not essential for a language to support these kind of structures, but they do greatly simplify some code, that may occur because of the problem domain, and of course the larger the project the more likely you are to encounter these kind of problems. All I can express is my experience that neatly every program I have written recently has got to a size when I can see a clear advantage to these kind of structures. Personally I am looking for a language that provides these features, and until I find one I will continue my own language development project. I like actors as a model for concurrency, so I could add them to my own project in a similar way to other languages like Erlang have. I am hoping that I may have missed some encoding trick that will let me do what I need, but as I get further with learning ActorScript the hope recedes.

The ActorScript type system seems similar to others, and it is a problem in all languages with this style of type system, so its not an opinion formed lightly. I do not believe Stepanov's code is limited to C++, that was just the language that was available that was closest to the theoretical ideas. In fact the language in the book is not C++, but a very small subset of C++ augmented with additional non C++ functionality (concepts, requirements, axioms etc). There is no sign C++ is going to implement the axiom stuff any time soon. Yet you can just about program in this style in C++, but it involves a lot of verbose template meta-programming. Haskell type-classes offer a much better type-safe way of programming in this style and are probably where I would look for inspiration.

The example I gave above of allowing procedures to return types and be part of type signatures is definitely nothing like C++, but provides what ActorScript needs to define these kind of type structures. I note that whilst it seems the simplest solution, it probably breaks separate compilation or introduces runtime type checking in some way. Haskell's type-families provides probably the cleanest way of getting the required functionality at the cost of slightly more complexity.

re bigger [foo]

I think I have also proved that the problem exists, despite any lack of knowledge of actor script.

I guess we have different standards.

Existence or importance?

Are you denying the problem exists or claiming it is not important?

re Existence or importance?

Are you denying the problem exists

Since I've explained how to do what you started off saying you were trying to do, yes. I understand that you tend not to really notice much of what I say before you reply to it. I give up.

Not the same thing

I think my implementation with casting was what you were getting at. If it is now correct, I can say that it definitely does not do what I want. If you still think I am missing something, and there is a way of doing it that is not explored above, I am still interested to see it.

Further i have put a lot of effort into following up your suggestions, reading the information you have pointed me to, and rewriting the code examples until you were happy with them. So i think you are being disingenuous by suggesting that I have not read your replies. In fact I have read your replies, and I have put effort into understanding them, and having done so, I do not see a solution to the original problem.

re Not the same thing

I think my implementation with casting was what you were getting at.

The code in that comment hasn't been the same any two times I've looked at it.

At this writing it contains (for one example) a value cast to a cosntructor (aka nonsense, as previously mentioned).

Where?

Where is there a value cast to a constructor. Its not very helpful to post the problem without highlighting where it is. Its almost like you don't want me to find it? You did notice in the "extends vs implements" comment I changed the the definition of Int32 from an Actor to an Interface, but I did not go back and update the previous complete example?

Its probably best to repost it here with the changed definition of Int32, then I can get you to sign off on its correctness (or not).

Interface RegularType with
    Equal[RegularType] |-> Boolean ()

Interface Integral extension RegularType with
    Successor[] |-> Integral,
    Predecessor[] |-> Integral,
    Twice[] |-> Integral,
    HalfNonnegative[] |-> Integral,
    BinaryScaleDownNonnegative[] |-> Integral,
    BinaryScaleUpNonnegative[] |-> Integral,
    Positive[] |-> Boolean,
    Negative[] |-> Boolean,
    Zero[] |-> Boolean,
    One[] |-> Boolean,
    Even[] |-> Boolean,
    Odd[] |-> Boolean ()

Interface Int32 extension Integral

Actor Int32Impl[x:Integer] implements Int32 using
    ...

Interface Transformation with
    Zero[] |-> Integral,
    F[RegularType] |-> RegularType ()

Distance.[x:RegularType, y:RegularType, t:Transformation]:Integral ===
    Orbit.[z:RegularType, d:Integral] ===
        z.Equals[y] ? True (:) d
                     False (:) Orbit.[t.F[z], d.Successor[]]
    Orbit.[x, t.Zero[]] () 

DistanceInt32.[x:Int32, y:Int32, t:[Int32] |-> Int32]:Int32 ===
    Actor TransformationInt32 implements Transformation using
        Zero[]:Integral -> Int32Impl.[0]
        F[z:RegularType]:RegularType -> t.[z(^)Int32](v)RegularType ()
    Distance.[x(v)RegularType, y(v)RegularType, TransformationInt32.[]](^)Int32 ()

Is this exactly how you were thinking I could do this? Have I missed anything, or made any mistakes? If you are happy with it can go on to explain the problem in detail. If you are not happy just point out what you think I haven't done right, and I will make sure it agrees with what you were thinking before investigating whether it does what I want.

obnoxious

Where is there a value cast to a constructor. Its not very helpful to post the problem without highlighting where it is. Its almost like you don't want me to find it? You did notice in the "extends vs implements" comment I changed the the definition of Int32 from an Actor to an Interface, but I did not go back and update the previous complete example?

Now you are criticising me for not speaking about code you had not yet posted.

Your comments were about the code that was there.

I wasn't criticising you about code not posted, I was saying it wasn't helpful to not highlight the error in the code that was there and that you were commenting on. Something like this:

At this writing it contains (for one example) a value cast to a cosntructor (aka nonsense, as previously mentioned), in this line:

F[z:RegularType]:RegularType -> t.[z(^)Int32](v)RegularType ()
                                       ^Here

I had to guess which bits you were talking about, and I am not sure this was what you meant even now.

This point is completely independent of the other point, where you seem to have missed the changes I suggested in the post titled "extends vs implement", although I accept that it perhaps was not as clear as it could have been, and it may have been better to repost the code (or go back and edit the earlier version) rather than just explain the changes to it. So I was not criticising you for making the statement about casting to a constructor which I understand, but for not referencing the code.

So are there any problems with the reposted version in the post titled "Where?" ?

re So are there any problems with the reposted version in the po

I wasn't criticising you about code not posted, I was saying it wasn't helpful [....]

I think you have bad strategies for asking others to help you.

Unpleasant

"I think you have bad strategies for asking others to help you."

That's a prickly and obnoxious response.

I think it's only been a couple of weeks since a number of people chimed up and said that Keean must have unusually high tolerance for rudeness to keep trying to discuss this with you.

You shouldn't dismiss his observation when the fact is that he's right.

re That's a prickly and obnoxious response.

That's a prickly and obnoxious response.

I notice that you have not spoken in the slightest to any of the content of the discussion, only the isolated tone of one reply.

It is as if you are keeping up what I called long ago: the two of you trolling Hewitt threads.

I give up

I think my previous comment makes it very clear why I wouldn't want to be in a discussion that you're in.

Not Suitable For Generic Programming?

The above solution with casting is the best I have come up with, and in the absence of further comments I have to assume it is the solution that has been claimed to be possible.

The problem with the above solution is that a wrapper function has to be written for every algorithm (in the above example we wrapped Distance) multiplied by every transform (because the wrapper is unique to PlusOne, as the transform defines the DistanceType). More generally this will result in a wrapper for every unique combination of algorithm and associated type in its arguments. I am sure it is easy to see that the number of wrappers required is a big problem.

As I said above, many (successful) languages are not suitable for generic programming, and this thread was started to explore the suitability of ActorScript for generic programming. As such I do not see how anyone could consider my comments trolling. I have been straightforward and to the point, always posting my best efforts. I am not saying ActorScript is a bad language, just that it does not seem to be suitable for my requirements (and probably not suitable for anyone wanting to do generic programming). ActorScript has some good points, concurrency using actors in particular. The use of parametric types also seems interesting. I think it gets the separation between interface and implementation right too.

re: the absence of further comments I have to assume

the absence of further comments I have to assume

You have to assume you are being ignored.

Correct as far as I can tell.

Anyone is welcome to point out mistakes, but to the best of my knowledge what I have posted is correct. Besides as you responded to part of the post, it is clear you are not ignoring them, yet you choose to respond off-topic and without addressing any of the substantive points.