Lambda the Ultimate

Long time no see. Your inspiring comments in Review NP-complete Library Versioning Problem and especially encouragement like

show us why this needs solving and can't just be avoided

made me think about possible solutions. One of them was the suggested adherence to backward compatibility, however as that is not always possible, I searched more.

As a result I came to idea of complete module repositories. As far as I can tell (and prove) they seem to eliminate the NP-Completeness of the general problem. However I have to admit I am not absolutely sure. This is a new, just born formalization (although I suspected this is the case for a while) and it might be even less consistent than the previous NP-Complete proof. It would not be wise to mix them together. Thus I am starting new thread to isolate your comments from the previous claim.

Please comment on Proper Library Versioning no longer NP-Complete proof. Thanks.

(via Ars Technica's review of Mac OS X 10.6)

Apple's version of GCC in Snow Leopard, its new operating system, has a C extension that looks like closures. I'm not sure whether to be marveled that C programs will get lambdas, or appalled that someone will have to figure out manual memory allocation bugs in these. It seems like Apple is moving towards LLVM for its compiler toolchain, and I imagine this extension requires the use of LLVM.

Dr. Victor Pankratius is scheduled to give a talk this Friday at UT Austin entitled, "Transactional Memory versus Locks - A Comparative Case Study". The presentation is here, a technical report is forthcoming.

The study is a side-by-side comparison of Transactional Memory with traditional multi-thread programming; general features of the study are:

• 12 students, apparently not experienced with multi-threaded programming, divided into six teams: three using Pthreads, three using Pthreads and Intel's STM C compiler.
• All teams worked on the same project, a parallel desktop search engine. Competition was for best performance.
• TM "improve[s] quality of parallel code [as judged by Dr. Pankratius and the STM compiler team at Intel], reduce[s] implementation and debugging effort, and provide[s] acceptable performance".
• "If subjects are inexperienced, then TM does not help them either. Parallel programming remains difficult."

If anyone knows more, or can go to the presentation, I would like to hear more.

(I am posting his to the forum since I cannot find a detailed description other than the presentation.)

A psychologist looks at Programming Languages:

Programming languages are not only useful to command computers, they also increasingly are a medium for human communication. I will use the framework of distributed cognition to discuss how knowledge is shared in a team of programmers and to show that computer code plays an important role in it. The resulting model of how programmers comprehend code suggests that common grounds play an important role in it. I propose two hypotheses concerning the means used by programmers to refer to common grounds from within their code. The hypotheses imply that modern languages, such as Scala, offer advantages as human communication mediums. I describe an experiment, using an eye-tracking device, that measures the performance of code comprehension. The hypotheses are tested by varying the degree of reference to common grounds.

Computer Code as a Medium for Human Communication: Are Programming Languages Improving?

While investigating the relationship between modules, their versions and mutual dependencies I came across one hard problem: Given a repository of modules (like the one provided by maven), select such configuration of the module versions so all their dependencies are satisfied.

After a little bit of thinking I concluded that this is NP-complete problem. I have even written down a proof.
I guess many LtU members are qualified to review the proof for soundness. Would you be so kind and tell me if there is anything wrong with it? Thanks.

Visit the proof.

I was just reading this paper from the home page

http://pauillac.inria.fr/~fpottier/slides/fpottier-2007-05-linear-bestiary.pdf

and realized I can't remember the meaning of many of the symbols after not using them for some time. Is there a reference somewhere that explains these symbols. I'm finding it hard to locate one.

Thank you.

PartI:
------
Goul: I want to couple values together, in a statically strongly typed manner in C# (3.5) which has not an internal support for tuples in it's compiler; without defining new types.

Code:

namespace TypePiling
{
    using System.Text;
    using System;
    using System.IO;

    public static class Ex
    {
        public static Tuple<T, U> Glue<T, U>(this T t, U u)
        {
            return new Tuple<T, U> { First = t, Second = u };
        }
    }

    public class Tuple<T, U>
    {
        public T First { get; set; }
        public U Second { get; set; }

        public override string ToString()
        {
            var result = new StringBuilder();

            if (this.First != null) result.Append(string.Format("{0}", this.First.ToString()));
            if (this.Second != null) result.Append(string.Format(", {0}", this.Second.ToString()));

            return string.Format("{{ {0} }}", result.ToString().TrimStart(',').Trim());
        }
    }

    public static class Test
    {
        public static void Test1()
        {
            var i = 10;
            var g0 = i.Glue("Hi");
            var g1 = g0.Glue((byte)0xFF);
            var g2 = g1.Glue(100.0);
            var g3 = g2.Glue('A');
            var g4 = g3.Glue((float)1000);

            using (var sw = new StreamWriter("output.txt"))
            {
                sw.WriteLine(g0);
                sw.WriteLine(g1);
                sw.WriteLine(g2);
                sw.WriteLine(g3);
                sw.WriteLine(g4);

                sw.Flush();
            }

            System.Diagnostics.Process.Start("output.txt");
        }
    }
}

This code does what I want and g4 will be:
{ { { { { 10, Hi }, 255 }, 100 }, A }, 1000 }

This is my first problem; as you see I do that by put previous value and next value in a new container. So previous values are pile down in First. I want them be piled up in Second, so g4 should be:
{ 10, { Hi, { 255, { 100, { A, 1000 } } } } }

I it possible in C# 3.5? If not why?

Part II:
--------
In trying to answer Part I; I have wrote another Extension Method in class Ex:

public static Tuple<T, Tuple<U, V>> Glue<T, U, V>(this Tuple<T, U> t, V v)
{
    return new Tuple<T, Tuple<U, V>> { First = t.First, Second = t.Second.Glue(v) };
}

This should do it in a recursive manner. Let see what is the out put:
{ 10, Hi }
{ 10, { Hi, 255 } }
{ 10, { { Hi, 255 }, 100 } }
{ 10, { { { Hi, 255 }, 100 }, A } }
{ 10, { { { { Hi, 255 }, 100 }, A }, 1000 } }

What? What happened at step 3? Sure the compiler recognized { Hi, 255 } as Tuple<string, byte>; but why the first version of Glue executed not the second one, overloaded for a Tuple<T, U>?

Is this something about generics in C#?

After all implementing tuples in a statically strongly typed manner without compiler support (internal or by a macro system) is pointless, I know. But from this pointless try I have touched another problem: In C# I can not have real accumulated types, but just parametrized types which does not provide enough tools for composition.

Thanks in advance

In the recent set of discussion on functions vs procedures a reference was made to the ADA language design choice neither to ban side effects in functions nor specify the order of evaluation of expressions.

So let me explain why this upsets me.

Thus thanks to our indecision coupled with human incompetence of the average programmer.. if you run a large program on a different compiler, or a different version of the same compiler, or with different optimization settings.... expect different results.

If you look at large modern commercial software systems... a large chunk of the cost (even worse schedule time) is in testing and retesting.

Mostly our test department goes hunting in areas where we have introduced change.

However, bad language design choices as made by the Ada design team add to the need for us to say to the test department... "Ah, we've had to change X (where X is one of that list above), so anything is possible. Sorry, you have to retest everything."

This can easily result in the vast proportion of the cost of a release being in the test phase. Which can be devastating to the release date schedule, as they are _always_ on the critical path. (Final test comes after everything else is done and dusted)

Determinism SHOULD feature highly as a design criteria for language designers.

Yes, programmers shouldn't code bugs.... but get real. In very large industrial systems there are hundreds even tens of thousands of bugs in shipped systems. Thus it is important that wherever possible, even if the program is just plain rong, different compilers, compiler versions, optimizer settings and memory layout, wherever possible produce the _same_ tested and accepted wrong behaviour.

Obviously it will not always be possible.

Obviously wherever possible defects should be prevented from being written, defects should be detected and fixed.

But simple language design choices that "prematurely optimize" by destroying determinism cost millions.

Determinism matters.

I have been reading about limits and colimits in Category Theory. Is it the case they are both universal arrows from a functor to the coresponding diagonal functor?
TIA.
Chad.

I read that one of the big things about F.P is the ability to reason about programs/prove them; is there also much more scope for code-generation.. automatically filling in the gaps after manually transforming one part of a system

lets say you have a known datastructure X and some known function F
and you want to transform the datastructure via G, and you want another H function to produce the same result..
F(X) = H(G(X))

my question is, in the functional programming world is there the ability to auto-generate 'H' given 'F' & 'G' (i guess even the ability to verify manually written functions fit the bill would be usefull)

has this sort of thing been used in practice to solve any real word problems, at what level of complexity..

Any pointers for things to read up on along these lines.