Design question

On Sun, Aug 8, 2010 at 10:01 PM, Neo Anderson <javadeveloper999@yahoo.co.uk> wrote:

It seems that previously I posted to the wrong place. I apologize for the inconvenience.

I am new to scala and actor models.

Yesterday I read a website (http://scala.sygneca.com/patterns/start) talking about patterns. There is one pattern called `Reactive abstractions' which does  not have further explain but shows it is related to actors.

My question is when programming using actor models, is there any thing developers need to carefully pay attention to? For instance, I am planning to develop a system which may communicate through network. A server X may propose message to a server Y. After computation, the server Y may response back to the server X. Also, there may have many other server similar to X and Y involved as the system grows.

Considering such scenario, Is there any pattern can be applied? Or is there any article or resource that may talk about such issue?

Irrespective of whether Akka is a better choice for your needs, there's a lot of good documentation at http://akkasource.org/ -- not to mention a remote actors implementation that seems to work pretty well. :)
-0xe1a

Alex Cruise-2 wrote:
>
> On Sun, Aug 8, 2010 at 10:01 PM, Neo Anderson
> wrote:
>
>> It seems that previously I posted to the wrong place. I apologize for the
>> inconvenience.
>>
>> I am new to scala and actor models.
>>
>> Yesterday I read a website (http://scala.sygneca.com/patterns/start)
>> talking about patterns. There is one pattern called `Reactive
>> abstractions'
>> which does not have further explain but shows it is related to actors.
>>
>> My question is when programming using actor models, is there any thing
>> developers need to carefully pay attention to? For instance, I am
>> planning
>> to develop a system which may communicate through network. A server X may
>> propose message to a server Y. After computation, the server Y may
>> response
>> back to the server X. Also, there may have many other server similar to X
>> and Y involved as the system grows.
>>
>> Considering such scenario, Is there any pattern can be applied? Or is
>> there
>> any article or resource that may talk about such issue?
>>
>
> Irrespective of whether Akka is a better choice for your needs, there's a
> lot of good documentation at http://akkasource.org/ -- not to mention a
> remote actors implementation that seems to work pretty well. :)
>
> -0xe1a
>
>

Alex. It's quite helpful. The Remote Node fits my requirement.

Thanks again for your help.

I'd be interested in getting some feedback on a basic design question. The issue is not specific to Scala, but I'd like to know if there is a preferred approach in Scala.

I'm working on a prototype of a system for air traffic conflict detection and resolution. The flights are stored in a Map from flight ID to Flight object. The flight ID or call sign is a string, such as "AAL1234." The Flight class stores relevant information and data about a flight, such as the aircraft type, IFR status, assigned altitude and route, current position, current velocity, trajectory predictions, etc.

At any given time, some flights are actively tracked and checked for conflicts, while others are not yet flying or are outside the airspace of interest and are not yet being checked for conflicts. Let's call these tracked and untracked flights. A given flight can change from tracked to untracked over time.

My question is about how best to distinguish between tracked and untracked flights. Should I have two different Maps and move the flights between them when necessary, or should I have just one Map and use a var status flag in the Flight class to tell whether a flight is tracked or untracked? Or is it just a matter of personal preference? Or is there a third approach that is preferable to both of these approaches?

The same basic issue comes up in several contexts. For example, I have a Maneuver class, and I need to keep track of which maneuvers have been issued and which are pending (not yet issued). As before, I have a Map from flight ID to assigned maneuver. Should I have two Maps, or should each maneuver have a flag to indicate whether it has been issued?

The program is not currently multi-threaded, but I'd like to be able to make it multi-threaded in the future without too much pain if necessary.

Comments appreciated. Thanks.

Russ P.

On Saturday October 9 2010, Russ Paielli wrote:
> ...
>
> I'm working on a prototype of a system for air traffic conflict
> detection and resolution. ...
>
> At any given time, some flights are actively tracked and checked for
> conflicts, while others are not yet flying or are outside the
> airspace of interest and are not yet being checked for conflicts.
> Let's call these tracked and untracked flights. A given flight can
> change from tracked to untracked over time.
>
> My question is about how best to distinguish between tracked and
> untracked flights. Should I have two different Maps and move the
> flights between them when necessary, or should I have just one Map
> and use a var status flag in the Flight class to tell whether a
> flight is tracked or untracked? Or is it just a matter of personal
> preference? Or is there a third approach that is preferable to both
> of these approaches?

Is the tracked / untracked status an intrinsic property of the flight or
is it a matter of the dispensation or category assigned to it by by
some external entity? (It sounds more like the latter.) If it is the
latter, then I'd probably use separate maps and keep the flight
representation immutable. (Might it be the case that whether a flight
is tracked or not is dependent on which administrative entity
apprehends that flight? Then it clearly is not an intrinsic property.)

However, you mention other attributes of the flight that are clearly
time-varying and which appear to be intrinsic to the flight and not a
matter of how some other entity in the system views them. This
typically suggests mutability of the representation. I assume the
position, velocity, altitude etc. are empirical / actual values and
cannot be treated as pre-defined functions of in-flight time.

I'm sure the functional programming crowd can offer one or more stock
solutions to making your flight representation immutable and still
accommodating your design needs. At my own state of (ahem)
sophistication or lack thereof in Scala software design, I'd probably
just go with mutability of intrinsic and time-varying flight
parameters.

But I would strongly consider representing the external categorizations
as non-intrinsic (e.g., by using separate maps).

> ...
>
> Russ P.

Randall Schulz

On Sat, Oct 9, 2010 at 6:31 PM, Randall R Schulz <rschulz@sonic.net> wrote:

On Saturday October 9 2010, Russ Paielli wrote:
> ...
>
> I'm working on a prototype of a system for air traffic conflict
> detection and resolution. ...
>
> At any given time, some flights are actively tracked and checked for
> conflicts, while others are not yet flying or are outside the
> airspace of interest and are not yet being checked for conflicts.
> Let's call these tracked and untracked flights. A given flight can
> change from tracked to untracked over time.
>
> My question is about how best to distinguish between tracked and
> untracked flights. Should I have two different Maps and move the
> flights between them when necessary, or should I have just one Map
> and use a var status flag in the Flight class to tell whether a
> flight is tracked or untracked? Or is it just a matter of personal
> preference? Or is there a third approach that is preferable to both
> of these approaches?

Is the tracked / untracked status an intrinsic property of the flight or
is it a matter of the dispensation or category assigned to it by by
some external entity? (It sounds more like the latter.) If it is the
latter, then I'd probably use separate maps and keep the flight
representation immutable. (Might it be the case that whether a flight
is tracked or not is dependent on which administrative entity
apprehends that flight? Then it clearly is not an intrinsic property.)

From the perspective of the air traffic system, I'd say that the tracked/untracked status is an intrinsic property of each flight. That would argue for making it a data field of the Flight class. Since it can vary with time, I guess it would have to be a var.

Making it a field of the Flight class is simpler than using two separate Maps, but it is less efficient. With the two separate Maps, I need to be careful about moving flights back and forth correctly, but once I do that, I don't need to constantly check the tracked/untracked flag to determine whether to check the flight for conflicts. That check is very simple and fast, but it must be done n-squared times for each update cycle, where n is the number of flights (typically 200-300 or more). That may seem like a lot, but it is negligible compared to all the other computation that goes into a single pairwise conflict check.

However, you mention other attributes of the flight that are clearly
time-varying and which appear to be intrinsic to the flight and not a
matter of how some other entity in the system views them. This
typically suggests mutability of the representation. I assume the
position, velocity, altitude etc. are empirical / actual values and
cannot be treated as pre-defined functions of in-flight time.

Yes, the position obviously changes constantly (not many hovering helicopters out there!), and the velocity changes too to a lesser extent. They come from surveillance data (radar or ADS-B). The Flight class has many time-vary data fields, hence I have vars all over the place. I realize that vals are preferable, but I don't know how to use a val for time-varying data. Well, I guess I could make a new immutable Flight object at each surveillance track update, but that seems prohibitively inefficient. If I am missing something, someone please clue me in.

 

I'm sure the functional programming crowd can offer one or more stock
solutions to making your flight representation immutable and still
accommodating your design needs. At my own state of (ahem)
sophistication or lack thereof in Scala software design, I'd probably
just go with mutability of intrinsic and time-varying flight
parameters.

I'd love to hear how an FPer would deal with the problem. I certainly don't claim to be an expert on FP. but my sense is that FP by itself cannot efficiently solve highly dynamic problems with a large state space, which is what I am dealing with here. If true, that would explain why Haskell is still an academic language -- and may always be.
 
Russ P.

--
http://RussP.us

On 10/10/2010, at 5:06 PM, Russ Paielli wrote:

> I'd love to hear how an FPer would deal with the problem. I certainly don't claim to be an expert on FP. but my sense is that FP by itself cannot efficiently solve highly dynamic problems with a large state space,

I'm not functional programming guru, but I don't think that copy-on-write has to be inefficient.

My thought would be to split the static information (e.g. flight no) from the dynamic information (e.g. location). You then either track the two structures separately, or make the dynamic information structure point to the static information structure - I'll consider the second idea.

e.g.

class StaticData(val registration: String, val randomData: Int) {}

class DynamicData(val x: Double, val y: Double, val id: StaticData) {}

Note that both classes are immutable. When a plane moves you create an entirely new 'DynamicData' object for it with the new location. It will point to the same staticData object, so the static data doesn't have to be copied. Assuming all the dynamic data changes at once, this is not inefficient - the new x,y location is simply written to a new object rather than the old one.

In terms of efficiency, the only difference is that a) you also have to copy a reference to the static data, and b) you have the memory allocation overhead for the new object. a) is one reference copy and there's going to be more overhead in updating your hash table. As for b), most functional languages are extremely efficient at allocating and freeing large numbers of short lived objects like this (imagine allocating a pool of objects of similar type - you can free them all at once by simply deallocating the pool) - it is similar in cost to the mutable version (for many use cases - your mileage may vary). I don't know how well a java VM's GC does at this.

So I don't think that functional programming per se is an issue here - as long as you can easily partition your data into the bits that are changing and the bits that aren't. Copy-on-write is a very powerful idea. But I'm no expert - does anyone else have any ideas/suggestions/corrections?

Cheers,

Will :-}

Hi,

I think the answer depends on how you use the data structures in your
code. I think there is no one true way. It's always a matter of
designing your data structures for the access patterns of your
algorithms.

For example, you say you use a map from flight ID to flight object.
But from what you said about your algorithm, it seems that you mostly
need to iterate through your flight objects. In this case, you
shouldn't use maps at all, as most are quite inefficient for iterating
through their entries / values, unless you use one of the Linked*Maps.

Of course, I do not really know anything about your code, but actually
I can hardly imagine a use case for the maps at all. Isn't the ID also
a value of the flight object? Can't you just use references to the
flight objects themselves, instead of using lookup by ID?

I hope I'm not being offensive, that was just what came to my mind
when reading your mail. And sorry for not answering your question,
too! ^^

Cheers
Ruediger

2010/10/10 Russ Paielli :
> I'd be interested in getting some feedback on a basic design question. The
> issue is not specific to Scala, but I'd like to know if there is a preferred
> approach in Scala.
>
> I'm working on a prototype of a system for air traffic conflict detection
> and resolution. The flights are stored in a Map from flight ID to Flight
> object. The flight ID or call sign is a string, such as "AAL1234." The
> Flight class stores relevant information and data about a flight, such as
> the aircraft type, IFR status, assigned altitude and route, current
> position, current velocity, trajectory predictions, etc.
>
> At any given time, some flights are actively tracked and checked for
> conflicts, while others are not yet flying or are outside the airspace of
> interest and are not yet being checked for conflicts. Let's call these
> tracked and untracked flights. A given flight can change from tracked to
> untracked over time.
>
> My question is about how best to distinguish between tracked and untracked
> flights. Should I have two different Maps and move the flights between them
> when necessary, or should I have just one Map and use a var status flag in
> the Flight class to tell whether a flight is tracked or untracked? Or is it
> just a matter of personal preference? Or is there a third approach that is
> preferable to both of these approaches?
>
> The same basic issue comes up in several contexts. For example, I have a
> Maneuver class, and I need to keep track of which maneuvers have been issued
> and which are pending (not yet issued). As before, I have a Map from flight
> ID to assigned maneuver. Should I have two Maps, or should each maneuver
> have a flag to indicate whether it has been issued?
>
> The program is not currently multi-threaded, but I'd like to be able to make
> it multi-threaded in the future without too much pain if necessary.
>
> Comments appreciated. Thanks.
>
> Russ P.
>
> --
> http://RussP.us
>

On Saturday October 9 2010, Russ Paielli wrote:
> ...
> >
> > Is the tracked / untracked status an intrinsic property of the
> > flight or is it a matter of the dispensation or category assigned
> > to it by by some external entity? (It sounds more like the latter.)
> > If it is the latter, then I'd probably use separate maps and keep
> > the flight representation immutable. (Might it be the case that
> > whether a flight is tracked or not is dependent on which
> > administrative entity apprehends that flight? Then it clearly is
> > not an intrinsic property.)
>
> From the perspective of the air traffic system, I'd say that the
> tracked/untracked status is an intrinsic property of each flight.
> That would argue for making it a data field of the Flight class.
> Since it can vary with time, I guess it would have to be a var.

Does the flight decide whether it's tracked? Is every airport's or ATC
center's notion of whether a flight is tracked always the same?

It really does not sound like an intrinsic property to me.

> ...
>
> Russ P.

Randall Schulz

It sounds like a derived information to me, calculated based on some other information.  Possibly the current location of the plane or the anticipated location within some time threshold relative to the air traffic control center.

On Sun, Oct 10, 2010 at 9:48 AM, Randall R Schulz <rschulz@sonic.net> wrote:

On Saturday October 9 2010, Russ Paielli wrote:
> ...
> >
> > Is the tracked / untracked status an intrinsic property of the
> > flight or is it a matter of the dispensation or category assigned
> > to it by by some external entity? (It sounds more like the latter.)
> > If it is the latter, then I'd probably use separate maps and keep
> > the flight representation immutable. (Might it be the case that
> > whether a flight is tracked or not is dependent on which
> > administrative entity apprehends that flight? Then it clearly is
> > not an intrinsic property.)
>
> From the perspective of the air traffic system, I'd say that the
> tracked/untracked status is an intrinsic property of each flight.
> That would argue for making it a data field of the Flight class.
> Since it can vary with time, I guess it would have to be a var.

Does the flight decide whether it's tracked? Is every airport's or ATC
center's notion of whether a flight is tracked always the same?

It really does not sound like an intrinsic property to me.


> ...
>
> Russ P.


Randall Schulz

--
http://erikengbrecht.blogspot.com/

I recommend the book Domain Driven Design [1]. In particular, chapter
seven walks through and example in the domain of cargo shipping, which
would overlap in some ways with the problem you are solving.

-jason

[1] http://my.safaribooksonline.com/0321125215

On Sun, Oct 10, 2010 at 1:07 AM, Russ Paielli wrote:
> I'd be interested in getting some feedback on a basic design question. The
> issue is not specific to Scala, but I'd like to know if there is a preferred
> approach in Scala.
>
> I'm working on a prototype of a system for air traffic conflict detection
> and resolution. The flights are stored in a Map from flight ID to Flight
> object. The flight ID or call sign is a string, such as "AAL1234." The
> Flight class stores relevant information and data about a flight, such as
> the aircraft type, IFR status, assigned altitude and route, current
> position, current velocity, trajectory predictions, etc.
>
> At any given time, some flights are actively tracked and checked for
> conflicts, while others are not yet flying or are outside the airspace of
> interest and are not yet being checked for conflicts. Let's call these
> tracked and untracked flights. A given flight can change from tracked to
> untracked over time.
>
> My question is about how best to distinguish between tracked and untracked
> flights. Should I have two different Maps and move the flights between them
> when necessary, or should I have just one Map and use a var status flag in
> the Flight class to tell whether a flight is tracked or untracked? Or is it
> just a matter of personal preference? Or is there a third approach that is
> preferable to both of these approaches?
>
> The same basic issue comes up in several contexts. For example, I have a
> Maneuver class, and I need to keep track of which maneuvers have been issued
> and which are pending (not yet issued). As before, I have a Map from flight
> ID to assigned maneuver. Should I have two Maps, or should each maneuver
> have a flag to indicate whether it has been issued?
>
> The program is not currently multi-threaded, but I'd like to be able to make
> it multi-threaded in the future without too much pain if necessary.
>
> Comments appreciated. Thanks.
>
> Russ P.
>
> --
> http://RussP.us
>

On Oct 9, 2010, at 11:06 PM, Russ Paielli wrote:

On Sat, Oct 9, 2010 at 6:31 PM, Randall R Schulz <rschulz@sonic.net> wrote:

On Saturday October 9 2010, Russ Paielli wrote:
> ...
>
> I'm working on a prototype of a system for air traffic conflict
> detection and resolution. ...
>
> At any given time, some flights are actively tracked and checked for
> conflicts, while others are not yet flying or are outside the
> airspace of interest and are not yet being checked for conflicts.
> Let's call these tracked and untracked flights. A given flight can
> change from tracked to untracked over time.
>
> My question is about how best to distinguish between tracked and
> untracked flights. Should I have two different Maps and move the
> flights between them when necessary, or should I have just one Map
> and use a var status flag in the Flight class to tell whether a
> flight is tracked or untracked? Or is it just a matter of personal
> preference? Or is there a third approach that is preferable to both
> of these approaches?

Is the tracked / untracked status an intrinsic property of the flight or
is it a matter of the dispensation or category assigned to it by by
some external entity? (It sounds more like the latter.) If it is the
latter, then I'd probably use separate maps and keep the flight
representation immutable. (Might it be the case that whether a flight
is tracked or not is dependent on which administrative entity
apprehends that flight? Then it clearly is not an intrinsic property.)

From the perspective of the air traffic system, I'd say that the tracked/untracked status is an intrinsic property of each flight. That would argue for making it a data field of the Flight class. Since it can vary with time, I guess it would have to be a var.

I would keep the static and dynamic aspects of a flight separate, so I would go with two maps. My general principle here is to reduce "coupling" -- makes for more flexible systems.
I would also ask my users to some degree. Do air traffic controllers make a distinction between a flight as a static entity (something that happens weekly for example, flight 207 flys LA to NY), and a flight as a dynamic entity (todays incarnation of flight 207).

I'd love to hear how an FPer would deal with the problem. I certainly don't claim to be an expert on FP. but my sense is that FP by itself cannot efficiently solve highly dynamic problems with a large state space, which is what I am dealing with here. If true, that would explain why Haskell is still an academic language -- and may always be.
 
Russ P.

To me it isn't a question of FP vs OO, it is a question of de-coupling things that are independent.
graham

Why keep anything "stored" anywhere? Just have the actual unique ID stored as data, and have methods somewhere like "def flightLocation(flight: Flight): Location". You can then let these methods decide how to store the data, whether it's even worth it to store the information instead of just fetching it each time, and how long it should take before the data has to be refreshed etc. Forcing something to be static and take up memory when it doesn't necessarily need to when approaching a problem is just restrictive...

On 10 Oct 2010 19:06, "Graham Matthews" <graham@orangedogconsulting.com> wrote:
>
> On Oct 9, 2010, at 11:06 PM, Russ Paielli wrote:
>
>> On Sat, Oct 9, 2010 at 6:31 PM, Randall R Schulz <rschulz@sonic.net>
>> wrote:
>> On Saturday October 9 2010, Russ Paielli wrote:
>> > ...
>> >
>> > I'm working on a prototype of a system for air traffic conflict
>> > detection and resolution. ...
>> >
>> > At any given time, some flights are actively tracked and checked for
>> > conflicts, while others are not yet flying or are outside the
>> > airspace of interest and are not yet being checked for conflicts.
>> > Let's call these tracked and untracked flights. A given flight can
>> > change from tracked to untracked over time.
>> >
>> > My question is about how best to distinguish between tracked and
>> > untracked flights. Should I have two different Maps and move the
>> > flights between them when necessary, or should I have just one Map
>> > and use a var status flag in the Flight class to tell whether a
>> > flight is tracked or untracked? Or is it just a matter of personal
>> > preference? Or is there a third approach that is preferable to both
>> > of these approaches?
>>
>> Is the tracked / untracked status an intrinsic property of the
>> flight or
>> is it a matter of the dispensation or category assigned to it by by
>> some external entity? (It sounds more like the latter.) If it is the
>> latter, then I'd probably use separate maps and keep the flight
>> representation immutable. (Might it be the case that whether a flight
>> is tracked or not is dependent on which administrative entity
>> apprehends that flight? Then it clearly is not an intrinsic property.)
>>
>>
>> From the perspective of the air traffic system, I'd say that the
>> tracked/untracked status is an intrinsic property of each flight.
>> That would argue for making it a data field of the Flight class.
>> Since it can vary with time, I guess it would have to be a var.
>
> I would keep the static and dynamic aspects of a flight separate, so I
> would go with two maps. My general principle here is to reduce
> "coupling" -- makes for more flexible systems.
>
> I would also ask my users to some degree. Do air traffic controllers
> make a distinction between a flight as a static entity (something that
> happens weekly for example, flight 207 flys LA to NY), and a flight as
> a dynamic entity (todays incarnation of flight 207).
>
>
>> I'd love to hear how an FPer would deal with the problem. I
>> certainly don't claim to be an expert on FP. but my sense is that FP
>> by itself cannot efficiently solve highly dynamic problems with a
>> large state space, which is what I am dealing with here. If true,
>> that would explain why Haskell is still an academic language -- and
>> may always be.
>>
>> Russ P.
>
> To me it isn't a question of FP vs OO, it is a question of de-coupling
> things that are independent.
>
> graham
>

I'm not an FP expert or a scala expert, very much the beginner at both, so this thread is particularly interesting.
From your description, a flight doesn't decide whether it is tracked or untracked.  That's to the perspective of the "tracker" (by which I mean whatever is looking at the flight data).  The tracker decides for example the time window and airspace it is interested in and determines if a flight is tracked by logical processing of the flight's state.
So I would not make tracked a property of flight since that would increase coupling - either some central process would have to take responsibility for updating all flights or a flight would have to know the tracker's perspective.  Also, having more than one tracker with different perspectives over the same set of flight information would be messy.
I'd make flight immutable and "tracked" would be a partial function encapsulating the logic (and parameters) that determine whether the tracker is interested in the flight.  It could be evaluated whenever the tracker wants to conduct an operation over the flights in its scope.  I think this would help with multi threading in future as well since there is no need to share information between threads.
Hope that's of use.
Brian

On 10 October 2010 00:07, Russ Paielli <russ.paielli@gmail.com> wrote:

I'd be interested in getting some feedback on a basic design question. The issue is not specific to Scala, but I'd like to know if there is a preferred approach in Scala.

I'm working on a prototype of a system for air traffic conflict detection and resolution. The flights are stored in a Map from flight ID to Flight object. The flight ID or call sign is a string, such as "AAL1234." The Flight class stores relevant information and data about a flight, such as the aircraft type, IFR status, assigned altitude and route, current position, current velocity, trajectory predictions, etc.

At any given time, some flights are actively tracked and checked for conflicts, while others are not yet flying or are outside the airspace of interest and are not yet being checked for conflicts. Let's call these tracked and untracked flights. A given flight can change from tracked to untracked over time.

My question is about how best to distinguish between tracked and untracked flights. Should I have two different Maps and move the flights between them when necessary, or should I have just one Map and use a var status flag in the Flight class to tell whether a flight is tracked or untracked? Or is it just a matter of personal preference? Or is there a third approach that is preferable to both of these approaches?

The same basic issue comes up in several contexts. For example, I have a Maneuver class, and I need to keep track of which maneuvers have been issued and which are pending (not yet issued). As before, I have a Map from flight ID to assigned maneuver. Should I have two Maps, or should each maneuver have a flag to indicate whether it has been issued?

The program is not currently multi-threaded, but I'd like to be able to make it multi-threaded in the future without too much pain if necessary.

Comments appreciated. Thanks.

Russ P.

This sounds exactly right to me. If you had some function, the function would be member of Tracker:
trait Tracker {  def trackedFilter: Flight => Boolean}
Then if you have some nomadic collection of Flight CC[Flight], you extract to Flights tracked by a Tracker simply by
val allFlights: CC[Flight]val allTracked = allFlights filter tracker.trackedFilter

Sent from my iPhone
On Oct 10, 2010, at 12:07 PM, Brian Smith <bmjsmith@gmail.com> wrote:

I'm not an FP expert or a scala expert, very much the beginner at both, so this thread is particularly interesting.
From your description, a flight doesn't decide whether it is tracked or untracked.  That's to the perspective of the "tracker" (by which I mean whatever is looking at the flight data).  The tracker decides for example the time window and airspace it is interested in and determines if a flight is tracked by logical processing of the flight's state.
So I would not make tracked a property of flight since that would increase coupling - either some central process would have to take responsibility for updating all flights or a flight would have to know the tracker's perspective.  Also, having more than one tracker with different perspectives over the same set of flight information would be messy.
I'd make flight immutable and "tracked" would be a partial function encapsulating the logic (and parameters) that determine whether the tracker is interested in the flight.  It could be evaluated whenever the tracker wants to conduct an operation over the flights in its scope.  I think this would help with multi threading in future as well since there is no need to share information between threads.
Hope that's of use.
Brian

On 10 October 2010 00:07, Russ Paielli < (russ [dot] paielli [at] gmail [dot] com> wrote:

I'd be interested in getting some feedback on a basic design question. The issue is not specific to Scala, but I'd like to know if there is a preferred approach in Scala.

I'm working on a prototype of a system for air traffic conflict detection and resolution. The flights are stored in a Map from flight ID to Flight object. The flight ID or call sign is a string, such as "AAL1234." The Flight class stores relevant information and data about a flight, such as the aircraft type, IFR status, assigned altitude and route, current position, current velocity, trajectory predictions, etc.

At any given time, some flights are actively tracked and checked for conflicts, while others are not yet flying or are outside the airspace of interest and are not yet being checked for conflicts. Let's call these tracked and untracked flights. A given flight can change from tracked to untracked over time.

My question is about how best to distinguish between tracked and untracked flights. Should I have two different Maps and move the flights between them when necessary, or should I have just one Map and use a var status flag in the Flight class to tell whether a flight is tracked or untracked? Or is it just a matter of personal preference? Or is there a third approach that is preferable to both of these approaches?

The same basic issue comes up in several contexts. For example, I have a Maneuver class, and I need to keep track of which maneuvers have been issued and which are pending (not yet issued). As before, I have a Map from flight ID to assigned maneuver. Should I have two Maps, or should each maneuver have a flag to indicate whether it has been issued?

The program is not currently multi-threaded, but I'd like to be able to make it multi-threaded in the future without too much pain if necessary.

Comments appreciated. Thanks.

Russ P.

On Sun, Oct 10, 2010 at 12:48 AM, Rüdiger Keller <ruediger.keller@googlemail.com> wrote:

Hi,

I think the answer depends on how you use the data structures in your
code. I think there is no one true way. It's always a matter of
designing your data structures for the access patterns of your
algorithms.

For example, you say you use a map from flight ID to flight object.
But from what you said about your algorithm, it seems that you mostly
need to iterate through your flight objects. In this case, you
shouldn't use maps at all, as most are quite inefficient for iterating
through their entries / values, unless you use one of the Linked*Maps.

Of course, I do not really know anything about your code, but actually
I can hardly imagine a use case for the maps at all. Isn't the ID also
a value of the flight object? Can't you just use references to the
flight objects themselves, instead of using lookup by ID?

Let me briefly explain why I am using Maps. Each flight has an ID, which is a field in the Flight class, but I need to be able efficiently find the Flight object with a given ID. Searching through a List of Flights to find the one with the given ID would be inefficient. I also have "collections" of conflicts and maneuvers that correspond to particular flights or flight pairs. I need to be able to conveniently look up the flight for a given conflict or maneuver (to correctly predict the trajectory of the flight or to determine whether the conflict has passed and the maneuver should be released, for example). If I need to quickly find flight "AAL1234", what better way then to have a Map from ID to Flight?

You say that iterating through a Map is inefficient. I did a little test, and it seems to be approximately 2 to 3 times slower than iterating through a List. That's unfortunate, but I think I'm going to have to live with, because without Maps I think I would have to do a lot of complicated and error-prone bookkeeping. Also, I suspect that the actual iteration through the Map is a tiny part of the overall processing load.

 

I hope I'm not being offensive, that was just what came to my mind
when reading your mail. And sorry for not answering your question,
too! ^^

No problem. I appreciate the feedback.

Russ P.
 
--
http://RussP.us

On Sun, Oct 10, 2010 at 12:42 AM, William Uther <willu.mailingLists@cse.unsw.edu.au> wrote:

My thought would be to split the static information (e.g. flight no) from the dynamic information (e.g. location).  You then either track the two structures separately, or make the dynamic information structure point to the static information structure - I'll consider the second idea.

That is not a bad idea, but I'm not sure how well it would work for me. The problem is that the Flight class has lots of data that is either highly dynamic or can change occasionally. The actual static data is basically the flight ID, the aircraft type, and a couple other items. Even the IFR/VFR status, which rarely changes, can change occasionally. The Flight class has lots of dynamic stuff in it that I don't have time to get into now.

I do have a separate State class for the dynamic state (position and velocity) of the flight. Each Flight object contains a State object. The State class is not currently immutable, but making it immutable might not be a bad idea.

Russ P.

--
http://RussP.us

On Sun, Oct 10, 2010 at 6:48 AM, Randall R Schulz <rschulz@sonic.net> wrote:

On Saturday October 9 2010, Russ Paielli wrote:
> ...
> >
> > Is the tracked / untracked status an intrinsic property of the
> > flight or is it a matter of the dispensation or category assigned
> > to it by by some external entity? (It sounds more like the latter.)
> > If it is the latter, then I'd probably use separate maps and keep
> > the flight representation immutable. (Might it be the case that
> > whether a flight is tracked or not is dependent on which
> > administrative entity apprehends that flight? Then it clearly is
> > not an intrinsic property.)
>
> From the perspective of the air traffic system, I'd say that the
> tracked/untracked status is an intrinsic property of each flight.
> That would argue for making it a data field of the Flight class.
> Since it can vary with time, I guess it would have to be a var.

Does the flight decide whether it's tracked? Is every airport's or ATC
center's notion of whether a flight is tracked always the same?

No, the flight does not decide whether it's tracked. The air traffic system decides which entity tracks each flight. Flightplans are filed for a flight while it is still on the ground. My software has access to those flightplans, and it needs them so it knows the aircraft type and other information about the flight. When the flight departs the gate, it is under control of the tower. Shortly after takeoff, the TRACON takes control. A few minutes after that it is handed off to the "Center," which is my domain. The US has 20 Centers, and the flight is handed over from Center to Center as it flies. Reverse the process for arrival. My software is a prototype for a Center. The surveillance tracking data that I get tells me who is responsible for the flight at any given time. If "my" Center is responsible, then the flight is "tracked".

 

It really does not sound like an intrinsic property to me.

 
I guess that depends on how you define an "intrinsic property."  It seems intrinsic to me. No, the flight does not determine which ATC entity is responsible for it, but the pilot must know that at any given time.

Russ P.

--
http://RussP.us

It sounds as though you may be trying to solve the wrong problem here!
If I understand correctly, your situation is basically:- You have a list of flight information that gets frequently updated - With each update cycle, you also want to check for collisions- I'm assuming that by "collision" you mean that planes are physically close, and not that they've actually crashed - ... actually you didn't specify what you meant by collision at all, maybe it's nothing to do with position, but I'm inferring from the mention of trajectories- The check for a conflict is a costly operation, rising exponentially with the number of flights involved - You therefore want to efficiently filter this list in advance
If you were able to perform the conflict-check faster, then the other optimisations might become far less relevant.So I'd advise that you look into a structure more suitable for spatial data, such as an R-Tree (or variant thereof): http://en.wikipedia.org/wiki/R-tree

On 10 October 2010 22:26, Russ Paielli <russ.paielli@gmail.com> wrote:

On Sun, Oct 10, 2010 at 12:48 AM, Rüdiger Keller <ruediger.keller@googlemail.com> wrote:

Hi,

I think the answer depends on how you use the data structures in your
code. I think there is no one true way. It's always a matter of
designing your data structures for the access patterns of your
algorithms.

For example, you say you use a map from flight ID to flight object.
But from what you said about your algorithm, it seems that you mostly
need to iterate through your flight objects. In this case, you
shouldn't use maps at all, as most are quite inefficient for iterating
through their entries / values, unless you use one of the Linked*Maps.

Of course, I do not really know anything about your code, but actually
I can hardly imagine a use case for the maps at all. Isn't the ID also
a value of the flight object? Can't you just use references to the
flight objects themselves, instead of using lookup by ID?

Let me briefly explain why I am using Maps. Each flight has an ID, which is a field in the Flight class, but I need to be able efficiently find the Flight object with a given ID. Searching through a List of Flights to find the one with the given ID would be inefficient. I also have "collections" of conflicts and maneuvers that correspond to particular flights or flight pairs. I need to be able to conveniently look up the flight for a given conflict or maneuver (to correctly predict the trajectory of the flight or to determine whether the conflict has passed and the maneuver should be released, for example). If I need to quickly find flight "AAL1234", what better way then to have a Map from ID to Flight?

You say that iterating through a Map is inefficient. I did a little test, and it seems to be approximately 2 to 3 times slower than iterating through a List. That's unfortunate, but I think I'm going to have to live with, because without Maps I think I would have to do a lot of complicated and error-prone bookkeeping. Also, I suspect that the actual iteration through the Map is a tiny part of the overall processing load.

 

I hope I'm not being offensive, that was just what came to my mind
when reading your mail. And sorry for not answering your question,
too! ^^

No problem. I appreciate the feedback.

Russ P.
 
--
http://RussP.us

--
Kevin Wright

mail / gtalk / msn : kev.lee.wright@gmail.com
pulse / skype: kev.lee.wright
twitter: @thecoda

On Sun, Oct 10, 2010 at 3:22 PM, Kevin Wright <kev.lee.wright@gmail.com> wrote:

It sounds as though you may be trying to solve the wrong problem here!
If I understand correctly, your situation is basically:- You have a list of flight information that gets frequently updated - With each update cycle, you also want to check for collisions- I'm assuming that by "collision" you mean that planes are physically close, and not that they've actually crashed - ... actually you didn't specify what you meant by collision at all, maybe it's nothing to do with position, but I'm inferring from the mention of trajectories- The check for a conflict is a costly operation, rising exponentially with the number of flights involved - You therefore want to efficiently filter this list in advance
If you were able to perform the conflict-check faster, then the other optimisations might become far less relevant. So I'd advise that you look into a structure more suitable for spatial data, such as an R-Tree (or variant thereof): http://en.wikipedia.org/wiki/R-tree

The objective is to maintain a minimum separation standard of 5 nautical miles horizontally or 1000 feet vertically. The R-Tree appears to be very similar to what I am already developed independently for coarse checking. It cuts way down on the number of more detailed checks for minimum separation. I'll take a closer look at it when I get a chance. Thanks for the link.

Russ P.

--
http://RussP.us

On Sun, Oct 10, 2010 at 12:48 AM, Rüdiger Keller <ruediger.keller@googlemail.com> wrote:

For example, you say you use a map from flight ID to flight object.
But from what you said about your algorithm, it seems that you mostly
need to iterate through your flight objects. In this case, you
shouldn't use maps at all, as most are quite inefficient for iterating
through their entries / values, unless you use one of the Linked*Maps.

After thinking more about this, I am wondering if maybe I should be using something other than a Map. However, I am having difficulty finding good information on some of the other collection types. I see something called "ListMap," but I can't seem to find any good information on what it is intended for. Is it a Map that iterates efficiently? If not, what type should I be using? (The only "Linked*Map" I see is "LinkedHashMap," but it's mutable.) Thanks.

Russ P.
 --
http://RussP.us

Hi Russ,

hmm, I just thought of the mutable LinkedHashMap. It didn't realize
that there are no other linked maps in Scala. Especially no immutable
ones. Sorry about that!

If you need some advice on the various offerings of the Scala
collections, have a look at the collections overview:

http://www.scala-lang.org/docu/files/collections-api/collections.html

The performance characteristics page might be of interest. For
example, there you see that ListMap's lookup time is proportional to
the its size, which is quite inefficient. But on the other hand it is
implemented as a linked list and therefore it should have fast
itertation, althought that is nowhere stated explicitly, it seems.

You can also maintain two collections of you flights, one for fast
iteration (a list or vector maybe) and one for fast lookup (probably a
hashmap). Of course, that has its drawbacks, but depending on the
requirements it can be worth it.

Regards,
Ruediger

2010/10/11 Russ Paielli :
> On Sun, Oct 10, 2010 at 12:48 AM, Rüdiger Keller
> wrote:
>>
>> For example, you say you use a map from flight ID to flight object.
>> But from what you said about your algorithm, it seems that you mostly
>> need to iterate through your flight objects. In this case, you
>> shouldn't use maps at all, as most are quite inefficient for iterating
>> through their entries / values, unless you use one of the Linked*Maps.
>>
>
> After thinking more about this, I am wondering if maybe I should be using
> something other than a Map. However, I am having difficulty finding good
> information on some of the other collection types. I see something called
> "ListMap," but I can't seem to find any good information on what it is
> intended for. Is it a Map that iterates efficiently? If not, what type
> should I be using? (The only "Linked*Map" I see is "LinkedHashMap," but it's
> mutable.) Thanks.
>
> Russ P.
>
> --
> http://RussP.us
>

On Mon, Oct 11, 2010 at 2:59 AM, Rüdiger Keller <ruediger.keller@googlemail.com> wrote:

Hi Russ,

hmm, I just thought of the mutable LinkedHashMap. It didn't realize
that there are no other linked maps in Scala. Especially no immutable
ones. Sorry about that!

If you need some advice on the various offerings of the Scala
collections, have a look at the collections overview:

http://www.scala-lang.org/docu/files/collections-api/collections.html

I read that entire overview a few weeks ago, but then I forgot about it. Thanks for the reminder!

 

The performance characteristics page might be of interest. For
example, there you see that ListMap's lookup time is proportional to
the its size, which is quite inefficient. But on the other hand it is
implemented as a linked list and therefore it should have fast
itertation, althought that is nowhere stated explicitly, it seems.

Yes, that performance summary page is nice, but I'd like to see a column on iteration efficiency if that makes sense. Also, I assume that HashMap represents Map, but I think confusion would be reduced if Map and Set were shown explicitly.

 

You can also maintain two collections of you flights, one for fast
iteration (a list or vector maybe) and one for fast lookup (probably a
hashmap). Of course, that has its drawbacks, but depending on the
requirements it can be worth it.

Yeah, I considered that possibility, but I'd really rather avoid the extra complexity if possible. I suppose I could explicitly create a List (by using myMap.values.toList) whenever I need to iterate, but that's probably inefficient too. I'm still open to new ideas.

Russ P.

 

Regards,
Ruediger


2010/10/11 Russ Paielli <russ.paielli@gmail.com>:
> On Sun, Oct 10, 2010 at 12:48 AM, Rüdiger Keller
> <ruediger.keller@googlemail.com> wrote:
>>
>> For example, you say you use a map from flight ID to flight object.
>> But from what you said about your algorithm, it seems that you mostly
>> need to iterate through your flight objects. In this case, you
>> shouldn't use maps at all, as most are quite inefficient for iterating
>> through their entries / values, unless you use one of the Linked*Maps.
>>
>
> After thinking more about this, I am wondering if maybe I should be using
> something other than a Map. However, I am having difficulty finding good
> information on some of the other collection types. I see something called
> "ListMap," but I can't seem to find any good information on what it is
> intended for. Is it a Map that iterates efficiently? If not, what type
> should I be using? (The only "Linked*Map" I see is "LinkedHashMap," but it's
> mutable.) Thanks.
>
> Russ P.
>
> --
> http://RussP.us
>

--
http://RussP.us

>>>>> "Russ" == Russ Paielli writes:

Russ> I do have a separate State class for the dynamic state (position
Russ> and velocity) of the flight. Each Flight object contains a State
Russ> object.

In the FP mindset, I think this link would go the other direction
(a State would contain an immutable Flight).

The way it sounds like you're headed with this, you'll want efficient inserts/removes to your collection(s) here, which would suggest that a HashSet/HashMap/Vector might be your best choices.
If in doubt, profile.   All the usual disclaimers about effective profiling apply :)

On 11 October 2010 22:30, Russ Paielli <russ.paielli@gmail.com> wrote:

On Mon, Oct 11, 2010 at 2:59 AM, Rüdiger Keller <ruediger.keller@googlemail.com> wrote:

Hi Russ,

hmm, I just thought of the mutable LinkedHashMap. It didn't realize
that there are no other linked maps in Scala. Especially no immutable
ones. Sorry about that!

If you need some advice on the various offerings of the Scala
collections, have a look at the collections overview:

http://www.scala-lang.org/docu/files/collections-api/collections.html

I read that entire overview a few weeks ago, but then I forgot about it. Thanks for the reminder!

 

The performance characteristics page might be of interest. For
example, there you see that ListMap's lookup time is proportional to
the its size, which is quite inefficient. But on the other hand it is
implemented as a linked list and therefore it should have fast
itertation, althought that is nowhere stated explicitly, it seems.

Yes, that performance summary page is nice, but I'd like to see a column on iteration efficiency if that makes sense. Also, I assume that HashMap represents Map, but I think confusion would be reduced if Map and Set were shown explicitly.

 

You can also maintain two collections of you flights, one for fast
iteration (a list or vector maybe) and one for fast lookup (probably a
hashmap). Of course, that has its drawbacks, but depending on the
requirements it can be worth it.

Yeah, I considered that possibility, but I'd really rather avoid the extra complexity if possible. I suppose I could explicitly create a List (by using myMap.values.toList) whenever I need to iterate, but that's probably inefficient too. I'm still open to new ideas.

Russ P.

 

Regards,
Ruediger


2010/10/11 Russ Paielli <russ.paielli@gmail.com>:
> On Sun, Oct 10, 2010 at 12:48 AM, Rüdiger Keller
> <ruediger.keller@googlemail.com> wrote:
>>
>> For example, you say you use a map from flight ID to flight object.
>> But from what you said about your algorithm, it seems that you mostly
>> need to iterate through your flight objects. In this case, you
>> shouldn't use maps at all, as most are quite inefficient for iterating
>> through their entries / values, unless you use one of the Linked*Maps.
>>
>
> After thinking more about this, I am wondering if maybe I should be using
> something other than a Map. However, I am having difficulty finding good
> information on some of the other collection types. I see something called
> "ListMap," but I can't seem to find any good information on what it is
> intended for. Is it a Map that iterates efficiently? If not, what type
> should I be using? (The only "Linked*Map" I see is "LinkedHashMap," but it's
> mutable.) Thanks.
>
> Russ P.
>
> --
> http://RussP.us
>

--
http://RussP.us

--
Kevin Wright

mail / gtalk / msn : kev.lee.wright@gmail.com
pulse / skype: kev.lee.wright
twitter: @thecoda

Hi,

see my comments below.

>
> Yes, that performance summary page is nice, but I'd like to see a column on
> iteration efficiency if that makes sense. Also, I assume that HashMap
> represents Map, but I think confusion would be reduced if Map and Set were
> shown explicitly.
>

Indeed, information on iteration performance and less ambiguous naming
would be a plus for that page. I guess that iteration performance for
maps and sets is omitted because it is not considered to be one of
its' primary use cases?

>
> Yeah, I considered that possibility, but I'd really rather avoid the extra
> complexity if possible. I suppose I could explicitly create a List (by using
> myMap.values.toList) whenever I need to iterate, but that's probably
> inefficient too. I'm still open to new ideas.
>

Creating a list from the map involves iterating over the map, so that
only pays off if you iterate multiple times over the list, especially
since creating the list itself isn't free either.

Btw. are you sure that iterating over the map is really a performance
issue? Maybe it's way slower that iterating over a list, but if it's
still taking an insignificant amout of time in the whole program
execution then there is no reason to optimize for anything but the
readability of the code and the cleanliness of the design. ^^

As Kevin says, probably some profiling is in order?

Regards,
Ruediger

Hi all,

I have a piece of code that's serving me well but wonder if its design
could be improved.
At its core, it's a variation on the State/Strategy patterns: a base
trait Base defining operations returning Base,
and concrete implementations returning different instances depending
on the state.

My variation adds two things:
- Some subclasses do not know how to implement some operations, and
delegate to a val parent: Base.
- The root of this tree of subclasses needs to be changeable: I use
the code in two different contexts, and the operations
defined by the root have different implementations in the two contexts.

My current design is as follows:
trait Base {
def operation1(params: Foo) = operation1(params, this)
def operation1(params: Foo, delegator: Base): Base
def operation2(params: Foo) = operation1(params, this)
def operation2(params: Foo, delegator: Base): Base
...
}

abstract class AbstractDelegatingSubclass(parent: Base) {
def operation1(params: Foo, delegator: Base) =
parent.operation1(params, this)
def operation2(params: Foo, delegator: Base) =
parent.operation2(params, this)
...
}

class Root {
def operation1(params: Foo, delegator: Base) =
new Sub(delegator, rootSpecificTransform(params))
}

class OtherRoot {
def operation1(params: Foo, delegator: Base) =
new Sub(delegator, otherRootSpecificTransform(params))
}

class Sub(parent: Base, params: Foo) extends
AbstractDelegatingSubclass(parent) {
def operation2(params: Foo, delegator: Base) = ...
}

The reason for passing around delegators is that some operations
require access to the state held at the point of delegation,
but they are implemented higher up in the tree, in a node containing
older state. For operations that do not change the state, the
delegator is
used as the return value instead of this.

Like I said, this is serving me well, but I find it quite verbose. I
have quite a few Subs, and quite a few operations. I don't expect
either to change a lot,
it's more about making the whole thing easy to understand and maintain.

Any suggestions?

Cheers,
Olivier

Your example is very abstract but at first glance it seems your code would benefit from the pattern below to decouple the state transitions from their implementation. You can also use self-types in traits to assemble concrete classes of Base, see here:
http://jonasboner.com/2008/10/06/real-world-scala-dependency-injection-di.html

object App {

  case class FSM[S](run:S => S) {
    def andThen(next: FSM[S]) =
      new FSM[S]({s0 =>
       val s1 = run(s0)
       val s2 = next.run(s1)
       s2
     })
  }

  trait Base {
    def upper(i: Int):Base
    def lower(i: Int):Base
  }
 
  object Base {
    def upper(i:Int) =
      new FSM[Base](s0 => s0.upper(i))
    def lower(i: Int) =
      new FSM[Base](s0 => s0.lower(i))
  }
 
  def main(args : Array[String]) : Unit = {
       
    case class IntBase(n:Int) extends Base {
      def upper(i: Int):Base =
        IntBase(n + i)
      def lower(i: Int):Base =
        IntBase(n - i)
    }

    case class StringBase(s:String) extends Base {
      def upper(i: Int):Base =
        replace(i, _.toUpper)
      def lower(i: Int):Base =
        replace(i, _.toLower)
      private def replace(i:Int, f:Char => Char) =
        StringBase(s.substring(0, i) + f(s(i)) + s.substring(i + 1))
    }

    import Base._
   
    val fsm = upper(4) andThen lower(6)

    println(fsm.run(IntBase(44)))
    // => IntBase(42)

    println(fsm.run(StringBase("Hello World")))
    // => "StringBase(HellO world)"
   
  }
}



--
Sébastien