Lambda the Ultimate

In one sense, this is light enough that I feel bad posting it to LtU. In another, though, it's entirely relevant: this guy started out inventing a DSL for pen-strokes, combinations of them, and relations between these combinations, and ended up with a simple OCR-based 4-function calculator. This was one of the cleverest bits of just-because programming language work and contrived abstraction that I've seen in a long time. Sample:

   Zero is
          a large circle

     One is
          either
               a long vertical line
          or
               a long vertical line
               a very small slash line
               top of first joins top of second

I've noticed that several new members chose obscure user names, instead of using their regular names. This is discouraged around here. Please see the LtU policy regarding user names, and at least provide identifying information in your user profile (e.g., a homepage url), if you keep using a handle instead of your real name.

On top of the reasons explained in the policy pages, LtU is being constantly attacked by spammers these days. Spammers ususally use strange usernames, and this allows me to catch them before they beign posting. However, the effectiveness of this technique depends on genuine members using their real names, so please help by abiding to this policy.

Thanks.

Trickles: A Stateless Network Stack for Improved Scalability, Resilience and Flexibility (PDF) by Alan Shieh, Andrew C. Myers, Emin Gun Sirer (2005)

Abstract: Traditional operating system interfaces and network protocol implementations force system state to be kept on both sides of a connection. Such state ties the connection to an endpoint, impedes transparent failover, permits denial-of-service attacks, and limits scalability. This paper introduces a novel TCP-like transport protocol and a new interface to replace sockets that together enable all state to be kept on one endpoint, allowing the other endpoint, typically the server, to operate without any per-connection state. Called Trickles, this approach enables servers to scale well with increasing numbers of clients, consume fewer resources, and better resist denial-of-service attacks. Measurements on a full implementation in Linux indicate that Trickles achieves performance comparable to TCP/IP, interacts well with other flows, and scales well. Trickles also enables qualitatively different kinds of networked services. Services can be geographically replicated and contacted through an anycast primitive for improved availability and performance. Widely-deployed practices that currently have client-observable side effects, such as periodic server reboots, connection redirection, and failover, can be made transparent, and perform well, under Trickles. The protocol is secure against tampering and replay attacks, and the client interface is backwards-compatible, requiring no changes to sockets-based client applications.

What you get when you combine continuations and networking. The idea should be obvious to most LtUers.

I really can't believe this hasn't been mentioned on LtU before.

The site is here.

Ostensibly, The Lightspeed Automatic Interactive Lighting Preview System by Ragan-Kelly et al. is about graphics, not programming language theory, and the abstract would confirm that opinion:

We present an automated approach for high-quality preview of feature-film rendering during lighting design.

However, I think it is an interesting example of a practical application of partial evaluation and specialization. 3D rendering is a computationally expensive process, but often the work of graphics artists is to make incremental changes rather than rendering fresh images from scratch. Lightspeed performs static dependency analysis of code written in the C-like Renderman shader DSL (RSL). The code is then specialised so that a static part (including a large 'cache' containing a partial computation) runs in the usual way in Renderman shader language on (a virtual SIMD machine on) the CPU, and a dynamic part is generated so as to run on a different architecture: GPGPU. The dynamic part contains the parameters that artists need to update frequently, resulting in fast previewing of results.

PS Note the 'lighting' in rendering-speak can mean any computation performed at a piece of geometry at the point at which you would compute the interaction between light and surface. Often it doesn't actually mean lighting.

(Disclaimer: I'm not an author on this paper but I did have an almost negligible bit of involvement.)

I have been playing with the idea of adding a call-with-current-continuation primitive (callcc) to the Cat language. The type would be:

  callcc : ('A ('A ('A -> 'B) -> 'B) -> 'B) 

The formal semantics would be:

  [$A [$B] callcc $C] == [$A [$C] $B]

An example usage would be:

  >> define do_twice { dup [apply] dip apply }
  >> define test { 1 [do_twice] callcc inc }
  >> test 
  stack: 3

My questions are: am I doing this right? Does the type look correct? Is it a good idea to add continuations to Cat? Thanks in advance!

See Felix's explanations.

Say we have a declarative language, where a = b is an assertion that governs the rest of the code, not an assignment operation. To this language we add the notion of explicit scopes -- assignments only apply within a scope, it's okay to have multiple contradictory assignments in different scopes. On top of this, we add one more idea -- scopes can inherit from one another, which is to say that children can overwrite assignments of their parents but otherwise maintain the same environment. For example:

foo(a, b, c)
  gamma = a * b
  rho = b * c
  gamma * rho

bar(a, b, c) extends foo
  gamma = a * a

is a piece of code in which bar assigns a different value to gamma but otherwise runs exactly as foo does, computing gamma * rho and returning the result. What I am talking about is function inheritance. In the above example, foo and bar must have the same signature for it to work -- but there are ideas from object oriented programming that can be leveraged to get around that.

Of course, the above example is little bit simplistic. Far more interesting is the use of the implies operator (->) for matching:

foo(a, b, c)
  'a' -> a
  'b' -> b
  'c' -> c
  'foo' -> 'foo'

bar(a, b, c) extends foo
  'foo' -> 'bar extending foo'

Here we use the implies operator to mean "when x is injected into my symbol space there is y" or in other words "a message x gets a response of y". Now, this example also offers up some real problems -- how do we specify tail recursion or termination in this language? -- but I'm willing to bet that a little study would reveal straightforward syntactic forms for this kind of thing.

Now that I have thought this language up, I have to work on it. I swore there would never be a day when I would stray from the well settled lands of software development to wander in the wilds of language design! Alas, I am doomed. All I ask from ltu is some thoughtful criticism of my idea, some pointers to earlier work in this domain and some suggestions about the syntax. What I want in the end is a language that is process/message oriented like Erlang but also has straightforward syntax for the notion of 'inheritance'.

For those of you hep cats who are hep to the lolcat scene, there's a new programming language, lolcode, designed specifically for the needs of your cat, being developed by the best feline researchers.

Example:

HAI
CAN HAS STDIO?
I HAS A VAR
IM IN YR LOOP
	UP VAR!!1
	VISIBLE VAR
	IZ VAR BIGGER THAN 10? KTHXBYE
IM OUTTA YR LOOP
KTHXBYE

Happy caturday. KTHXBYE.

Chung-chieh Shan and I have submitted a paper on delimited contexts in operating systems and the zipper OS (which has not been formally published). Systems programmers do use contexts whether they are aware of that or not. The first version of UNIX on PDP-7 already implemented delimited continuations, in the form of co-routines between user programs and the shell. Being aware of delimited continuations may help systems programmers to better implement context switching, signal handling, etc., using the techniques developed in programming language research. It also leads to new insights, for example, that checkpointing a process and snapshotting a file system are essentially the same activity.

The final paper is available at http://okmij.org/ftp/papers/context-OS.pdf

There is little new there for long-time LtU members; however, this time the material is presented systematically and in context.

Hi all,

I'm looking for literature which focuses on proving context-free parsers correct. For example, I have work by Sikkel on Parsing Schemata and work by Cliff Jones on formalizing Earley's algorithm, and looking for other ways that people have formalized and proved those (and other context-free) parsers.

Thanks for any recommendations,
Dan