Lambda the Ultimate

Should nested types capture type parameters?

type Map(K,V) {
  counters: List(Count)
  elements: List(Pair)

  type Count {
    key: K
    count: Int
  }
  type Pair {
    key: K
    value: V
  }
}

let c: Map(Int,Int).Count = ...
let e: Map(Int,Int).Entry = ...

type Map(K,V) {
  counters: List(Count(K))
  elements: List(Pair(K,V))

  type Count(K) {
    key: K
    count: Int
  }
  type Pair(K,V) {
    key: K
    value: V
  }
}

let c: Map.Count(Int) = ...
let e: Map.Entry(Int,Int) = ...

Some observations:

• "Yes" is more concise in the type definitions.
• "No" is more concise when the type parameters aren't necessary (second-to-last line).
• "Yes" feels more natural to me right now, whatever that means.
• Java chose "No".
• Maybe a nested type can opt-in to capture?

I'm working on a data description language and can't decide which way to go on this. I'm hoping someone here has information or opinions that might tip me one way or the other.

I am trying to work out the distributed or parallel semantics in a new language, and not making as much progress as I would like. I will present the main ideas that I would like to implement and request some feedback or relevant pointers.

1. Abstract state
Although that is not necessarily related to parallelism, I believe that may be important when coding in that context. The main structure of the language is the object, and an object can declare various abstract states. For example the built-in list and dictionary both have declared states "fullAccess" and "readOnly". The transition from fullAccess to readOnly corresponds to the method "const()". There is no reverse transition in that case.

Fields and methods of the object may pertain to a specific abstract state. Methods can also have a different body depending on the current abstract state. For example, there is no setter method in the readOnly state.

New states declared in subclasses can refine an inherited state, or they can be top-level (in which case the inherited state and the new state form the combined abstract state).

The reason I believe this is relevant for parallelism is that the transition from one state to the other can be used as a trigger for an action, in other words the action "waits" for the transition-- a form of lock.

2. Services
Services wait for requests and perform the requested actions. This is a multi-tiered system which has roughly the following components:

A. Capability
The capability is issued by the service and held by the client process/task. It is a special identifier that is recognised by the service when it is part of a request. The capability gives rights to do a specific set of requests, for example it could be the capability to open a file with read access.

B. Enqueuer
There is one enqueuer per process/task that maintains a queue of requests. The requests are queued locally until the queue is full. Once a request is enqueued, the enqueuer returns a handle to the client that gives access to the result of the request. The service picks requests from the queue as fast as it can process them.

C. Service
This is the main component. It collects requests from various clients according to an algorithm of its choice. Then it processes each request and sends back the result to the client.

D. Resource
Each service may manage any number of resources, which often correspond to objects of the OS. A typical resource is a file. A capability typically gives access to a set of methods on a specific resource. A resource can be directly manipulated by a service only.

3. Transactions
A transaction is a piece of code that is guaranteed to execute atomically, at least from the point of view of the shared variables it uses. There are two kinds of shared variables:

A. Simple shared variable
A simple shared variable can be modified by a single process/task at once, or read by multiple processes/tasks at once. That can be implemented by a "shared" service that manages the shared memory at the appropriate level (module, application, OS, network).

B. Versioned variable
A versioned variable can exist as multiple copies in different processes/tasks at once. Each copy point to a single, simple shared variable. At the beginning and/or the end of a transaction the versioned variable copies are synchronised with the shared copy.

In case of conflict between different versions of the variable a conflict handler is called. The conflict handler can implement the following strategies:

a) Fail
The changes of the transaction are rolled back: no change to a versioned variable is committed, and an exception handler is in charge of reverting other changes (simple shared variables, files etc).

b) Overwrite
A single version of the variable is selected and all others are discarded.

c) Merge
The handler attempts to merge all the disparate versions of the variable, attribute by attribute. A custom handler can be written to perform the merge provided a list of conflicting attributes.

Modifiers to the handler are "retries" and "timeout" (in case of conflict retry up to "retries" times after "timeout" is elapsed), "usenew" and "useold" (use the last modified of first modified version of the variable or attribute)

4. Parallel execution
Various procedures are launched in parallel, with the execution plan based on a dynamic dependency graph. This should be based on the work related to Athacaspan.

Many ideas, but I stumble on both theorical and implementation details (notably wrt versioned variables and abstract state). I would be grateful for some solid advice and material to look at.

Hello,

This article uses an old piece of COBOL code to see if it really is understandable after 14 years.

Do you agree?

Erlang's actor concurrency model is a good fit for a wide range of concurrent applications. One domain that would seem ideal is real-time control of concurrent physical processes. But as it stands right now Erlang is best suited for soft real-time applications - there's really nothing in the language or runtime geared towards hard real-time constraints. Towards Hard Real-Time Erlang talks about one piece of the puzzle: a hard real-time scheduler.

In the last decades faster and more powerful computers made possible to seriously take into account high–level and functional programming languages also for non–academic projects. Haskell, Erlang, O’CAML have been effectively exploited in many application fields, demonstrating how high–level languages can help in writing efficient, readable and almost bug–free code, rapidly stealing the prominent position gained in many fields by OO languages such as Java and C++. One of the fields where low–level imperative languages are still preferred to functional programming is that of hard real–time applications, since usually programmers (and managers) think that high–level languages are really not able to cope with the complex and critical requirements of real–time.

In this paper we propose an implementation of a hard real–time scheduler entirely written in Erlang, and perfectly integrated with the Erlang BEAM emulator. Performance analysis show that the proposed solution is effective, precise and efficient, while remaining really simple to use as expected by Erlang programmers.

The paper closes with mentions of two more pieces of the puzzle.

Real–time message passing will be introduced in a future version...

...

A solution to the unpredictable behaviour of garbage collection should be implemented before a really hard real–time scheduling can be done in Erlang.

Besides the scheduler, message passing, and garbage collector, what else do you think is needed before Erlang or something like it is a viable alternative in this domain? Or is the actor model really not such a great fit?

*Edit: Based on a comment from renox added closing quotes about message passing and garbage collector and added message passing to the editorial question.

Machine learning consists of a lot of math and AI have traditionally used logic and functional languages, not imperatives.

So Haskell should be fit for this stuff no? Yet I don't say much applications using Haskell for AI. What is the standard AI-language today? Still LISP?

For some time my colleagues and I have been working on the idea of representing software behaviour as a composition of partial behavioural descriptions, using the parallel composition operator P||Q of CSP.

This gives rise to a pure mixin style behaviour modelling paradigm, with models that have executable semantics. A short description (presented at the 3rd International Conference on Evaluation of Novel Approaches to Software Engineering in Funchal, Madeira earlier this year) can be found here: http://www.metamaxim.com/download/documents/enase.pdf

We are not sure, though, whether what we have produced can be classed as a programming language or not; and if not, what it is.

Any thoughts on this?

Thanks
Ashley

When I was describing my API design adventures in the Practical API Design book (btw. if there is anyone who would like to review the book for LtU, I am ready to provide a copy), I could not realize that many of these problems would not even appear if we had better languages, or systems more suitable for the DistributedDevelopment.

I may be wrong, but I do not know about any language that would support modularity. And here I mean not compilation piece by piece, but also modularity in time. Because that is the kind of modularity that is needed quite often during development of APIs for our libraries.

At one point of time we release a version of a library and distribute it to others by publishing it on the website. Now people unknown to us, distributed all around the world download it and use it. As a result, the amount of applications built on top of such library is increasing, which implies also that the amount of bugs and feature requests is growing too. After a while the time to release new version of the library comes. However what if the first version used to have a class:

public abstract class View {
  public abstract String getDisplayName();
}

What if one of the feature requests demands to add an HTML title to each view. Can we change the view class to following form:

public abstract class View {
  public abstract String getDisplayName();
  public abstract String getHTMLTitle();
}

Indeed, this cannot be done. Existing subclasses of View would no longer compile, because the change is not source compatible. Also, even if someone links already compiled subclass with the new version of the library, the Java virtual machine will complain and throw some kind of linkage error, as definition of an abstract super class method is missing.

I would love to see a language or system that would fail the compilation whenever I want to modify my already released classes in a style that could prevent some of their users to continue to use them in previously working way. This would be the real modularity, which is ready for changes in time. So far it seems to me that the current languages do not deal with changes in time really well. Just like Andrei described in his Enums in APIs blog, it seems that our languages do not think about the process of API evolution much and include constructs that one needs to avoid to make DistributedDevelopment possible.

Releasing new version of libraries with modified APIs is really common and our software engineering practices cannot live without it, yet it seems that there is no language in the world that would make this easy and clueless. Or am I wrong?

Franklyn A. Turbak and David K. Gifford with Mark A. Sheldon (2008). Design Concepts in Programming Languages. MIT Press.

I read portions of this textbook in draft form, and it's a near-encyclopedic take on programming language semantics, which includes what other textbooks on the subject are missing: a plethora of concrete examples and exercises, in the context of a series of small but practical programming languages. The book's friendly and informal tone makes even the most forbidding and formal topics seem accessible.

The linked page includes a table of contents and sample chapter.

(Disclaimer: the first author taught me most of what I know about computer science when I was an undergraduate at Wellesley.)

*newbie alert* I'm hoping this is a permissible question to ask here. I looked at the FAQ and it doesn't seem to explicitly disallow it. :)

[haskell]
I was learning haskell a few years ago and I was recommended mr. Hudak's book "The Haskell School of Expression". This was my first foray into functional programming and it turned out this wasn't a great book to start with. Having done some amount of Haskelling by now I regret to realize that when I see an expression like "map map" I continue to scratch my head. Hudak gives this and similar examples as exercises, but there are no solutions in the back of the book.

The funny thing is that I've written map map to map a function over items in lists contained in a list. But I still don't understand this at all:
map map :: [a -> b] -> [[a] -> [b]]
Let alone how you derive it.
[/haskell]

David A. Wheeler: Ada, C, C++, and Java vs. The Steelman

This paper compares four computer programming languages (Ada95, C, C++, and Java) with the requirements of "Steelman", the original 1978 requirements document for the Ada computer programming language. This paper provides a view of the capabilities of each of these languages, and should help those trying to understand their technical similarities, differences, and capabilities.