Lambda the Ultimate

Hi! I have just finished supervising a student whose thesis was about the impact of modeling the logic of a videogame with various approaches: oo imperative, oo immutable, functional immutable and functional monadic.

I was wondering if anyone here could suggest a conference where we could submit this kind of work :)

Cabinet, a self-described magazine of art and culture, features in issue 36 (Winter 2009/10) a short and rather amusing piece by Lev Bratishenko entitled "Technomasochism: Getting spanked by INTERCAL". Unfortunately it is not available online, but if you come across Cabinet in your public library or bookstore, do take a look, it will make you smile (or at least grin). As you can imagine, the PLEASE keyword is used to good effect.

Hello, I am trying to figure out a schema to implement
multithreading on multiple cores for an language that
I'd like to design. First of all I came to the
conclusion that you cannot use native threads. Using
native threads means that your language implementation
can interrupt at any time, making a single asm-insn
the unit of atomicy. You need tons of synchronication
and need to think about raceconditions etc. which
explodes code complexity. The benefits of native
threads can better be achieved using custom programmed
threads, meaning: simple stack switching with a few
assembler insn. I found that the latest google-go
gcc branch of Ian Tailor is working on gcc support
for variable size stacks and split stacks: that means
you can increase the stack size dynamicaly while
executing. The only need for native threads would be
for blocking i/o, therefore I'd partition by langauge
implementation in 2 native threads, one handling the
I/o and the other implementing the threading in
custom fashion. Implementing threading myself means:
I can implement cooperative threading.
I can define blocks of atomicy without need of synchronisation.
I can derive a garbage collection schema where I can
ignore stack references.
Now I was thinking quite a long time on how to handle
multicore. Having handled mutithreading the easy way
i dont want to start over with synchronication on insn
level. Up till now didnt came up with a enlighting solution

therefore I'd like to know weather someone can give
me a idea...

The only thing that I came up would be
cross calls: A object belongs to a CPU. Every CPU
has a worker-thread running on every other CPU. If a CPU
tries to modify a object that doesnt belong to himself
if has to do a crosscall: If need to wake up the worker-thread
on the owner's cpu....
With only a few global objects this scheme might be applicable,
however it will shurely kill the system if you have
a lot of global objects...
Is there some other way to avoid the synchronization
overkill in multicode mode....
-- Greetings Konrad

Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation, by Simon Peyton Jones, João Dias and Norman Ramsey (ICFP 2010.)

Abstract. Dataflow analysis and transformation of control-flow graphs is pervasive in optimizing compilers, but it is typically tightly interwoven with the details of a particular compiler. We describe Hoopl, a reusable Haskell library that makes it unusually easy to define new analyses and transformations for any compiler. Hoopl's interface is modular and polymorphic, and it offers unusually strong static guarantees. The implementation is also far from routine: it encapsulates state-of-the-art algorithms (interleaved analysis and rewriting, dynamic error isolation), and it cleanly separates their tricky elements so that they can be understood independently.

A vastly different paper than the last one by the same trio (available here,) this one is more of an example of how to write a client for the Hoopl optimization library, and describes some of Hoopl's innovative static guarantees for making sure the analysis is correct. It also describes the newer implementation of the Lerner/Grove/Chambers algorithm for interleaving analysis and transformations. There's even more good news: Hoopl is now on hackage, so you can get started writing your own optimizers!

The new iPhone developer agreement as quoted at http://daringfireball.net/2010/04/iphone_agreement_bans_flash_compiler:

3.3.1 — Applications may only use Documented APIs in the manner prescribed by Apple and must not use or call any private APIs. Applications must be originally written in Objective-C, C, C++, or JavaScript as executed by the iPhone OS WebKit engine, and only code written in C, C++, and Objective-C may compile and directly link against the Documented APIs (e.g., Applications that link to Documented APIs through an intermediary translation or compatibility layer or tool are prohibited).

Now think about this. Basically, they have said "you can only use these PLs to originally write your code, use of any other PLs breaks this agreement." Now, assume iPhone continues to be widely successful and that...eventually PCs are replaced by iPad devices. And say everyone starts copying Apple's locked fortress model, where will PL innovation go?

I'm very disappointed at Apple over this.

While reading up on OO and Algorithms vs. Interaction, I re-encounter the adage that OO's flexibility is at odds with verification formalisms. It makes me wonder what various, er, formalisms people use to split a program up into those parts which are a non-verifiable 'interaction machine' vs. those parts which are formalizable algorithms, cf. monads used to make sequencing explicit. (I shall be reading more of Wegner's papers. [Edit: and old LtU threads about 'interactive machines'.])

We think it may be of interest to LtU readers and we got Ehud's blessing, so here is our job posting, infomercial-style.

Our team has built a people search engine in OCaml starting in 2006 at Wink.com. An acquisition later we are more than 5 OCaml programmers and we are looking for more people who share our passion.

In a nutshell, our duties consist in collecting, ingesting and indexing a growing collection of about a billion records from a variety of public sources, and then serving those records in volume with low latency. This represents a large amount of data of heterogeneous content and quality. Doing smart and useful things with such data requires a bit of imagination and good programmers, but also tools that allow us to combine expressiveness and high performance. We find that the OCaml language and its libraries offers a good balance between the two, and we don't have to switch to lower-level languages when we need high performance.

We would love to get in touch with programmers interested in the intensive use of functional programming. We are located in the heart of the Silicon Valley in Mountain View and we are always open to meeting new people either informally or for traditional job interviews. Feel free to contact me privately or to send your resume to the hiring manager.

In parsing, (non-dependent) type systems, and semantics, we have made remarkable progress in specification. In the first two areas, we have reference processing models and reference specification languages that tell us, definitively, whether a program is admissible or not. That is: they are definitive both positively and negatively. In the last, we have definitive specification provided the program is well-formed and well-typed.

The situation seems less clear for solvers. We appear to have reference models for how a solver operates, and reference languages for specifying what a solver may do (that is: the legal operations) but no way of specifying what the solver must do, nor the conditions under which convergence with a solution (or at least certain types of convergence) are guaranteed.

One consequence of this is that the specification of languages that rely on general-purpose solvers is necessarily reduced to "the implementation is the definition", and in some cases this leaves us in a state where the admissibility of a program may depend on the details of a particular solver implementation or even the performance of the CPU on which the compile occurs.

I see no problem with stronger vs weaker compilers. My concern here is to ensure that there exists a precise specification of the language that all correct implementations must accept in order to be conforming implementations.

Is there work or progress along these lines that I should look at?

Languages like CL or Scheme may have complex lambda lists, but still have a single "calling convention."

OTOH, Haskell, just for example, supports multiple arity functions via a single tuple argument or via curried function definitions.

So now we look a some function like map, or say map/2 if arity overloading is not allowed. Let's presume that map/2 is a curried function. We might call it like this.

map/2 plus [1,2,3] [2,3,4]
  => [3,5,7]

Now, should plus here be a curried function or a function that takes a tuple of two arguments?

This is NOT a "factual" question about Haskell specifically.

I'm more interested in how higher order functions might or might not support functions of multiple "calling conventions" (more below) in some more or less elegant manner. Should the "calling convention" be considered part of the type of the function and a kind of "type parameter" of higher order functions like map/2 above?

Just for the sake of argument, imagine that we supported a variety of calling conventions typical of the Windows and some C compilers - fastcall, c, pascal, stdcall, etc. - that are language level keywords.

Can we imagine a function type signature such as:

iplus :: stdcall Int -> Int -> Int  -- what do arrows really mean at this point?
iplus x y = x + y

map/2 iplus [1,2,3] [4,5,6] -- What happens now?

Presumably this is no longer "really" a curried function, and we might devise some other syntax to make this more clear, something like:

iplus :: stdcall Int * Int -> Int
iplus x y = x + y

map/2 iplus [1,2,3] [4,5,6] -- What happens now?

My point is to show that a more flexible language with regard to calling convention, here facilitating direct integration with OS supported calling conventions, further complicates cleanly implementing simple higher order functions like map or filter or any? or every? or foldl and so on - unless I'm missing something (which I hope I am).

Any words of wisdom on defining/implementing higher order functions (and compiling these) in the face of multiple language supported calling conventions?

Mucho thanks!

I am currently thinking about building an interpreter or compiler system for the scheme language but I am a bit uncertain (given that my goal is to construct something small) which version of the language to use. Should I go with rsr6? My understanding is that rsr6 is a bit controversial.