Lambda the Ultimate

Dear All,

Just wanted to let you know that Jekejeke Minlog 0.6.2 is
out. There was some functionality in the Jekejeke Minlog
extension module that lay dormant until now. With this release
of Jekejeke Minlog we provide a first batch of built-ins for
hypothetical and counterfactual reasoning. Internally these
built-ins work with clause references and trailed undos.

To introduce hypothetical and counterfactual reasoning to
logic programming is not new, we draw here on work from
the 80's.

Jekejeke Minlog also provides variants that work without a
sub-goal and keep the update for the duration of the continuation.
The continuation variants of hypothetical and counter factual
reasoning form the update component of the continuation version of
forward chaining, which is used to implement constraint solvers.
Since new constraints, similar to unification results,
stay for the duration of the continuation.

Now that we have hypothetical and counter factual reasoning: Is
it useful and does it perform? To some extend we have already
answered this question by the implementation of our CLP(FD)
constraint solver. But the constraint solver makes also use
of the forward closure computation, so are there some interesting
applications not integrated with the forward closure?

Interestingly the answer seems yes. We managed to implement
tic-tac-toe via the continuation variant of the new Jekejeke
Minlog tool box.

In the old solution the board state is passed around in predicate
arguments. In the new solution we perform updates on the facts
via hypothetical/counter factual operations. Since the board state
is not anymore passed around we do not need a move/3 predicate.
Instead we can work with a move/1 predicate that has only one
parameter and that updates the knowledge base:

% move(+Player)
move(P) :-
   clause_ref(board(-,M,N), true, R),
   compile_ref(board(P,M,N), S),
   retire_ref(R),
   assume_ref(S).

Astonishingly the new solution is also performant. Our measurements
show the following figures for checking whether there exists
a winning strategy:

Old Parameter Solution: 124ms
New Update Solution: 224ms

Theoretically a certain advantage could be gained for bigger boards
via the update method, since it works only locally. Further forward
closure could come to the picture again to model complex moves.

Comments welcome.

Bye

Jekejeke Minlog 0.6.2

Tic-Tac-Toe with Parameter

Tic-Tac-Toe with Update

The other day I was thinking about "visability", state, and algorithms and decided to search the expression "algorithms have state". I was thinking about Yiri Gurevich's paper on the subject. Instead I found three video's by
Gurevich himself. Lecture three. answers the question "What is an algorithm". The same search turned up this very topical video "How Algorithms Shape our World".

Edit: Why don't the links connect? fixed.
http://www.ted.com/talks/kevin_slavin_how_algorithms_shape_our_world.html
The Gurevich link seems to be too long to cut and paste. You can find it under Channel 9, Gurevich. This seems to work, select the lecture.
http://channel9.msdn.com/Series/C9-Lectures-Yuri-Gurevich-Introduction-to-Algorithms-and-Computational-Complexity/

See Letter to Editor of CACM January 2013 at http://bit.ly/WWXsDK

I've not found any simple introductions or tutorial to Row Polymorphism theory and its applications via google. Can you all send me up some links or book titles to research. Note that I'm still a language design white-belt, so please aim for that audience if possible. Thank you kindly for your time!

I've come up with a new concept, called 'alternative programs', where expressions can have multiple alternatives. I wonder if there are any papers out there that discuss a similar concept. I'm having trouble defining the concept, but here is a try:

Every expression takes the form of a sequence of alternative expressions, syntactically enclosed within curly brackets and separated by commas (in the case of a single alternative, curly brackets are omitted).

The combination of two alternative expressions results in the cartesian product combination of their alternatives.

Example alternative expressions:

1 + 2         => 3
{1,2} + 3     => {1+3,2+3}         => {4,5}
1 {+,*} 2     => {1+2,1*2}         => {3,2}
{1,2} + {9,7} => {1+9,1+7,2+9,2+7} => {10,8,11,9}

I've taken the bold step to generalise the above into the following:

Consecutive alternatives in a sequence that are equal are compressed into singletons, then prefixed with a colon, together with the multiplicity of the consecutive equal alternatives. A compressed representation of a sequence is called the canonical representation of a sequence.

Next to that, multiplicities are of type rational and can be negative (where negative multiplicities are prefixed with an underscore). Luckily, the cartesian product of alternatives can be naturally defined over negative and rational multiplicities.

Example canonical representations:

{1,1,1/4:2,2,_1/2:2,1,_3,_3,_3,3,1} =>
{2:1,3/4:2,1,_2:3,1}

{1/2:1,1/4:2} + {4:3,_2:4}      => 
{2:(1+3),_(1+4),2+3,_1/2:(2+4)} =>
{2:4,_5,5,_1/2:6}               =>
{2:4,_1/2:6}

In a language with inheritance, the evolution of type during construction (and devolution during deconstruction, if appropriate) is a bit tricky. I was recently asked for pointers to papers or references on this, and came up dry on a Google search.

Can anyone suggest papers or references addressing this issue?

Our web site subscript-lang.org goes officially live today. SubScript is a way to extend common programming languages, aimed to ease event handling and concurrency. Typical application areas are GUI controllers, text processing applications and discrete event simulations. SubScript is based on a mathematical concurrency theory named Algebra of Communicating Processes (ACP).

ACP is a 30 year old branch of mathematics, as solid as numeric algebra and as boolean algebra. In fact, you can regard ACP as an extension to boolean algebra with 'things that can happen'. These items are glued together with operations such alternative, sequential and parallel compositions. This way ACP combines the essence of compiler-compilers and notions of parallelism.

Adding ACP to a common programming language yields a lightweight alternative for threading concurrency. It also brings the 50 year old but still magic expressiveness of languages for parser generators and compiler compilers, so that SubScript suits language processing. The nondeterministic style combined with concurrency support happens to be very useful for programming GUI controllers. Surprisingly, ACP with a few extras even enables data flow style programming, like you have with pipes in Unix shell language.

For instance, to program a GUI controller for a simple search application as shown here, takes about 15 lines of code in Java or Scala, if you do threading well. In SubScript it is only 5 lines.

At the moment SubScript is being implemented as an extension to the programming language Scala; other languages, such as C, C++, C#, Java and JavaScript, would be possible too. The current state of the implementation is mature enough for experimentation by language researchers, but not yet for real application development. If you have the Eclipse environment with the Scala plugin installed, it is easy to get SubScript running with the example applications from our Google Code project.

We hope this announcement will raise interest from programming language researchers, and that some developers will get aboard on the project.

In the second half of February 2013 we will very probably give a presentation and a hands on workshop at EPFL in Lausanne, the place where Scala is developed. We hope have a SubScript compiler ready then, branched from the Scala compiler scalac. A more detailed announcement will follow by the end of January on our site.

There are certainly whole program compilers with the aim of making higher level languages compile far more efficient runtime executables. But as I currently understand these compilers, their practical usefulness for large scale program development is limited due to efficiency of the compilation process itself.

So, I was wondering if any languages - more specifically, the types of higher level languages that feature language abstractions that might benefit most whole program compilation - supported a compilation model and associated language abstractions that tried to encompass a wider spectrum of optional efficiency oriented language abstractions and features between whole program model compilation and separate compilation in the name of runtime efficiency.

As for "whole program compilation," what I have in mind instead is some kind of limited "library" - or "package" or "unit" (etc.), let's use "library" for now - abstraction comprised of multiple source files that are subject to "whole library compilation. This would allow programming teams to decide when to apply a more limited scope of "whole program compilation" just to performance critical libraries in their programs.

Between these "libraries" (however they are compiled), we have "separate compilation" made safe via traditional module "signatures," or unit "interfaces" or whatever (pick your lingo and preferred module header styled feature).

But additionally, within the "separate compilation model," we might also support other language features that assist the compiler in generating more efficient code. Some low hanging fruit might be: annotations and/or compiler driven function inlining, annotation or compiler driven loop unrolling, C++ or D style template data types and functions (as an alternative to "normal" generic, parametric polymorphic functions and data types), C (and Smalltalk, interestingly)-styled variable length data structures, full blown Scheme styled macros (no, not always or even primarily an efficiency tool, but still...), annotations for "destructured" function argument data types (potentially avoiding memory allocation for passing many function arguments), and so on and so forth.

Once could write entire programs in the language without using these features, but one could also write entire libraries (say, just for example, a performance oriented OpenGL or encryption library) using these directives and alternative language level abstractions - and then pull out all the stops by subjecting the "library" to whole program compilation. Aside from segregation of the program into discrete libraries (yes, not always an easy task in the general case), most of these efficiency oriented features could be utilized incrementally in modifying a program in response to profiling.

Skipping the not-so-high-level C++ (simple macros, templates), are there any higher level languages that support such a "spectrum of efficiency oriented language abstractions and features." I'm particularly interested in the concept of a more limited scope for "whole program compilation" via some kind of more selective "library" abstraction.

I'd welcome any wisdom on efficacy, usability and implementation challenges.

I strongly believe that prolog-like unification (programming with holes) should be incorporated in every new programming language. One of my arguments is that unification is more general than pattern matching, and that unification is just as natural as pattern matching.

In contrast, I find the unification of two sets hardly intuitive. Set unification is not only non-intuitive but also NP complete. Still, I believe that set unification, as a first class operation, is an interesting programming construct.

Actually, I'm more interested in the unification of multimaps because they extend sets. My intuition also tells me that multimap unification can be made more efficient in most use-cases.

I'm not sure however. Are there any unification 'theorems' that I should consider that counter my intuition?

I have always looked at recursion very pragmatically. A well formed recursive function is a function which calls itself during its execution. In order to avoid infinite loops, some of its arguments have to be constantly decreasing on each recursive call and there has to be a branch where no recursive calls are made.

Certainly in theoretic computer science fixpoints are introduced and from a mathematical point of view a recursive function is the solution of a fixpoint equation. But diving into the subject deeper there are a lot of interesting aspects in this connection between recursive functions and fixpoints. There is a connection to closures, to induction etc.

I have tried to write down some of these interesting aspects into the little paper Closures and fixpoints. All needed math is expressed within a programming language in a manner that the compiler can verify all derived facts. Maybe some of you are interesting in reading this.