Lambda the Ultimate

as seen previously on LtU, there's a new Mozart VM in the works, and a more recent post says here is some code.

Dyalog has the pleasure of announcing the start of the 2012 edition of our World Wide APL Programming Contest. The deadline for submissions this year is August 5th, 2012. The terms and conditions, and the tasks to be solved can be found at: http://www.dyalog.com/contest_2012

For students, the Grand Prize is US$2,500 plus round trip travel and registration to the Dyalog ‘12 Conference in Elsinore, Denmark, commencing October 14th 2012.

Second and third prizes are US$1,200 and US$600 respectively and up to 20 other contestants will receive $100 each.

This year’s contest also features a grand prize for non-students – a complimentary registration to the Dyalog ’12 Conference.

Additionally, the people or organisations that refer the winning students to the contest will receive the same dollar prizes – and they need not be students to make the introduction. This means that you (or if you prefer, your institution) will receive an amount equal to any prizes won by students that you have referred to the competition.

The purpose of the contest is encourage students and others to investigate APL; the organisers hope that participants will find that exposure to APL broadens their horizons and adds a new tool to their toolbox.

Students of other disciplines than Computer Science are also encouraged to participate; many of the most successful APL users have backgrounds in other sciences, and have found APL to be a “Tool of Thought” for expressing solutions to problems in a wide variety of fields. Our 2010 competition was won by Ryan Tarpine, a computational biologist from Brown University and last year’s grand prize winner, Joel Hough, discovered the contest through Lambda the Ultimate. Presentations by Ryan and Joel about their experiences and impressions of competing can be found on the contest website at: http://www.dyalog.com/contest_2012

There is no requirement to purchase a copy of Dyalog APL.

A fully featured copy of the latest release of Dyalog APL is available free of charge to students, whether or not they choose to participate in the contest.

Non-students may download a free, unregistered, version of Dyalog APL, also whether or not they choose to participate in the contest.

Contestants are also welcome to use other APL implementations, subject to the guidelines described on the contest website.

A total of US$12,600 in prize money has been provided by several sponsors, including US-based Fiserv, Italy-based APL Italiana, Denmark-based SimCorp and UK-based Dyalog Ltd., as well as several anonymous individuals and companies.

LtUers will appreciate the new security feature of the Linux kernel that lets you run Berkeley Packet Filter programs over system call arguments. After all, Userland already knows its ABI: system call numbers and desired arguments.

Adding more interpreter-like features to the kernel has been discussed before in the context of splice, a zero-copy data transfer API:

(Of course, the "kernel buffer" notion does allow for a notion of "kernel filters" too, but then you get to shades of STREAMS, and that just scares the crap out of me, so..)

With distributed capabilities we can send an object from computer X to computer Y. We do not want computer Y to be able to look at the internals of the object, hence we send a distributed reference to the object. If Y wants to do something with it, it will have to ask computer X to do it instead. This has two problems: (1) it causes latency on computer Y because of the network round-trip (2) it causes extra load on computer X.

In some cases the security we get from using references is not necessary. The data inside the object might not be secret, or it might be partially secret. For example suppose we have an Employee object, and send it over to computer Y. The name and ID of the employee are not secret, so we can send them over so that Y can do its work without further contacting X.

Another case is a mutable Employee object. Suppose that its name and ID are Mutable[String] and Mutable[Number] respectively. A Mutable is a mutable reference. When we send the object over to Y, we want to give it read access but not write access to the name and ID. Hence we should not send the distributed references to the Mutable[String] and Mutable[Number] objects, because then Y would have the ability to invoke the name.set(newname) method of the mutable reference. Instead we have to send over an immutable version of the Mutables.

Suppose the Employee object has a method incrementID that sets its ID to ID+1. When we invoke this on computer Y we will have to send a network request to X because we do not have write access to the ID. In this case it is not possible to eliminate problem (2) but it is still possible to eliminate (1). We can give Y write access to its own mutable ID reference. When Y calls incrementID it updates its local ID to ID+1, *and* it sends a network request invoking the method incrementID on X. This way Y can continue its further execution immediately, instead of waiting for the network request to complete. A malicious Y can do what it pleases with its own ID, for example it can decrement it. But it cannot mutate the ID stored on X other than via incrementID.

Is there a paper that describes primitives for doing this? Something along the lines of marking some objects as not secret, and then automatically provide either latency reducing operations (such as incrementID) or provide operations that completely eliminate network usage (such as getName), as appropriate. There might be problems with keeping the local and remote objects in sync, and not duplicating remote calls to other objects. Any ideas/input is appreciated.

A recent PhD dissertation by Adrian Kuhn; abstract:

Despite common belief, software engineers do not spend most time writing code. It has been shown that an approximate 50-90% of development time is spent on code orientation, that is navigation and understanding of source code. This may include reading of local source code and documentation, searching the internet for code examples and tutorials, but also seeking help of other developers.

In this dissertation we argue that, in order to support software engineers in code navigation and understanding, we need development tools that provide first-class support for the code orientation clues that developers rely on. We argue further that development tools need to tap unconventional information found in the source code in order to provide developers with code orientation clues that would be out of their reach without tool support.

...

Among the code orientation strategies used by developers, spatial clues stand out for not having a first-class representation in the ecosystem of source code. Therefore, we introduce Software Cartography, an approach to create spatial onscreen visualization of software systems based on non-spatial properties. Software maps are stable over time, embedded in the development environment, and can be shared among teams. We implement the approach in the CodeMap tool and evaluate it in a qualitative user study. We show that software maps are most helpful to explore search results and call hierarchies.

If one wants to iterate through all reachable states s1 from an initial state s0 in an imperative language (think of a chess board and a possible set of moves) one could do something like:

for i in 1..#changes {
    s1 := copy(s0)
    change(s1, i)
    // process s1
}

It is usually faster and less memory intensive to do the following instead:

for i in 1..#changes {
    change(s0, i) pushing undo data to the stack
    // process s0
    undo(s0) popping undo data from the stack
}

Are there general techniques for inferring the "undo data" that an operation should save, and possibly the corresponding undo operation?

A simple model of programs in an FRP style is "newtype Putter a b = Putter (a -> (b, Putter a b))".
Unfortunately this doesn't model programs which can change the type of input and output they have.

I tried using GADT's to fix this and got

data PushAndPull i o where
 PushAndPull :: i o2 -> (o i2, PushAndPull i2 o2)

but it doesn't type check. Instead I can only have

data Pusher i o where
 Pusher :: i -> (o u, Pusher u o)

and

data Puller i o where
 Puller :: i u -> (o, Puller i u)

Because I can't figure out a model which typechecks, I want to find out alternate FRP models of programs which can change the type of input and output they have. What work in FRP models programs which can change the type of output and input they have?

Hi!

I have an unusual question: is there any paper/essay/... that discusses the importance of having a coherent formal design of a programming language to guide and inform its implementation?

Thanks

Few Examples of Lisp Code Typography, spanning 54 years, collected by Newlisp's Kazimir Majorinc.

Modern Eiffel is a new language which is syntactically based on Eiffel but has a lot of concepts of functional languages like Haskell, OCaml or Coq. Modern Eiffel puts the emphasis on static verification, i.e. a compiler can statically check that a programm written in Modern Eiffel meets its specification.

The following article describes how Modern Eiffel's proof engine can be used to reason with inductive types.