LtU Forum

Slate 0.3 released

Slate 0.3 has been released. Slate is a language similar to Smalltalk with a prototype based object system and multi-method dispatch.

First-class labels for extensible rows (draft)

Daan Leijen. Submitted to the 32nd ACM Symposium on Principles of Programming Languages (POPL'05), Long beach California, January 12, 2005. (PDF, BibTeX)
This paper describes a type system for extensible records and variants with first-class labels; labels are polymorphic and can be passed as arguments. This increases the expressiveness of conventional record calculi significantly, and we show how we can encode intersection types, closed-world overloading, type case, label selective calculi, and first-class messages. We formally motivate the need for row equality predicates to express type constraints in the presence of polymorphic labels. This naturally leads to an orthogonal treatment of unrestricted row polymorphism that can be used to express first-class patterns. Based on the theory of qualified types, we present an effective type inference algorithm and efficient compilation method. The type inference algorithm, including the discussed extensions, is fully implemented in the experimental Morrow compiler.

Always trust Daan to come up with something both elegant and practical...! However the examples involving bottom (undefined) labels left me skeptical.

breve: a 3D simulation environment

breve is a free software package which makes it easy to build 3D simulations of decentralized systems and artificial life. Users define the behaviors of agents in a 3D world and observe how they interact. breve includes physical simulation and collision detection so you can simulate realistic creatures, and an OpenGL display engine so you can visualize your simulated worlds.

I guess the on-topic bit is this:

breve simulations are written in an easy to use language called steve. The language is object-oriented and borrows many features from languages such as C, Perl and Objective C, but even users without previous programming experience will find it easy to jump in.

but frankly steve is probably not so interesting in itself; rather breve is just a lot of fun to play with.

Apparently, several AI/robotics groups use breve for their research, but it's very easy to get started and comes with a simple IDE and several demos, of which the most interesting is undoubtedly the Walker, a genetic algorithm which evolves four-limbed walking "plates".

Tail of Nil and Its Type

Epigram: practical programming with dependent types

Find the type error in the following Haskell expression:


if null xs then tail xs else xs


Found it? Of course you haven't. But this program is obviously nonsense! Unless you're a typechecker, that is. The trouble is that only certain computations make sense if the null xs test is True, whilst others make sense if it is False. However, as far as the type system is concerned, the type of the then branch is the type of the else branch is the type of the entire if . . . then . . . else . . ..

Statically, the test is irrelevant. Which is odd, because if the test really were irrelevant, we wouldn't bother doing it.

We mentioned this issue in discussions. LtU recently featured Epigram with emphasis on its interactive programming abilities, but I would like to add that Conor McBride's papers are mostly about practical use of dependent types for programming. They are also fun to read, though I can easily imagine how his experiments with presentation, like this one, can annoy some people.

Oberon Day @ CERN 2004

Presentations

Besides the expected language designer presentations -

    J. Gutknecht
  • Criteria for Exclusion of a Construct
    • Superfluous, covered by existing construct
    • Problematic, contibution to problem set is
      larger than contribution to solution set
    • Hidden overhead, no straightforward and
      efficient mapping to runtime exists
  • Criteria for Inclusion of a Construct
    • Is extremely useful
    • Has generic character
    • Adds to completeness

and slide 9 "Complexity of syntax of programming languages" in Niklaus Wirth's presentation,

Tkachov (physicist as-end-user/programmer) provides a different perspective

and Brega's robotic art...

techniques for JIT (parallel?) compilation of straight line numerical code

Reading A Methodology for Generating Verified Combinatorial Circuits, which involved some code generation/staging and AST optimization, I found myself wondering if there are libraries for just-in-time compilation (and then dynamic loading/linking) of simple numerical code. C seems like a decent language as a generation target (in that it's fairly assembly-like, and in its later (C99?) incarnations has fairly portable support for low level types like (and operations for) e.g. 80-bit floating point values.

Further, although I'm tempted to write everything in one language (currently C++) since it has made interoperability trivial, there must be some reasonable argument that the overhead of launching an optimizing C compiler surely gives you the leeway to say, invoke Meta-Ocaml routines that do the code-generation magic (never having embedded another language in a C++ program or called wrapped C++ in another language, I'm not sure how expensive or hard this is).

Anyone have some good references (to theory or practical implementations) or advice? Even the basic technique necessary to say, compile and dynamically load/link C code into another language (while probably somewhat platform specific) is foreign to me :)

I'm not at all committed to C as the code generation target; I just want something that compiles and optimizes loopless straight-line numerical computation well, and bonus points if it can split up the computation so that it runs in a distributed parallel fashion (N cpus per node, local memory on each node, relatively expensive network communication). It would also be great if code could be reordered to take advantage of cache locality and processor parallel-numeric abilities as well (of course this should be handled by the compiler and not addressed directly by the person generating the numerical code?). I have no idea which compilers (Intel's C compiler might be good) can do such analyses and how to encourage them to do so; by default I use gcc, which I understand is somewhat basic.

My intended application is repeated Estimation-Maximization (EM) parameter optimization; the computation for accumulating counts for each parameter as a function of the previous iteration's count can be compiled and made branchless, optimized (sharing common subexpressions, etc.), and then run a few hundred times. Thus I want to compile and load compiled code on the fly (the generated code of course depends on the input automata I'm estimating parameters for). For historical reasons, my work so far has been entirely C++, but obviously, switching to code generation/compilation would allow me to use any language as the driver as long as it can access the results of the compiled code without expensive marshalling or interprocess communication.

(apologies if this is more a compilers/tools than a language question)

IronPython: First public version released

IronPython is a new Python port for the CLR. The recently released version 0.6 is the first public version.

Mind the Gap

I am very happy that I found GAP as it allowed me the opportunity to make a bad pun, I just had to try it when I read their description of how their web site had been organized.

I think the Grouping capabilities are pretty cool

Vyper is missing

In case any language collector around here still has a copy of Vyper (the Python interpreter written in Ocaml by John Skaller that used to live at http://vyper.sourceforge.net/) flying around: Don't delete it, it may be the last existing copy, since neiter the author nor sourceforge still have one.

(So much for the permanence of electronic reccords in the internet age...)

A Functional Semantics of Attribute Grammars

A Functional Semantics of Attribute Grammars

A definition of the semantics of attribute grammars is given,
using the lambda calculus. We show how this semantics allows us to prove
results about attribute grammars in a calculational style.

I didn't encounter attribute grammars since school, so it was refreshing to see them in this light.
I have to check yet, whether "abstract interpretation" used in this paper is related to the one from Oleg's paper.

XML feed