Lambda the Ultimate - LtU Forum, Site Discussion

OOPSLA 08

Sun, 12 Oct 2008 22:31:03 -0400

I went over the OOPSLA'08 program, and these two items caught my eye:
(1) Constrained Types for Object-Oriented Languages
(2) Whiteoak: Introducing Structural Typing into Java

Looking at the abstracts of these papers (and also other abstracts from the program) brought up a thought that's been wrapping around my mind for sometime: The border between programming paradigms not as clear as it used to be.

Personally, I think this is a good thing. For example, I believe that closures are very useful in OO. My only problem with this line of thought is that I also believe in the beauty of minimalism. A language that borrows constructs from several paradigms will (usually) not be minimal. A conundrum?

On the (perceived) equivalence of static and dynamically typed reflective programming languages

Sat, 11 Oct 2008 19:06:01 -0400

Hi. I'm new here.

I've dug up some old topics on the issue of the dynamic/static-typing cold-war/debate, and considering this to be a predominantly pro-static, all-determinism and pro-PF message-board, I would lay down this question as a test of either my misunderstanding, or as a fair argument for a particular point which I think hasn't been mentioned.

One claim that's been in many topics (especially on this forum) and recent papers on modern type theory (even though I have no idea about its origins) is the possibility to construct a 'Universal' type to capture the notion of run-time typing:

data Univ = Inte Int | Str String | ...

This has been used to justify the claim that, since such a hack can be used to bypass the type-checker, statically typed languages can directly express all programs in dynamically typed ones, but such a statement isn't true in the reverse.

One argument that has been thrown against this is that, currently, this isn't very convenient (especially in SML, Haskell and any other widely used language with type-inference). One would be forced to work with explicit type-constructors, functions would have to be 'lifted' (lift (+) :: (Int -> Int) -> (Univ -> Univ)) in order to operate on data of this sort, and would have to be 'flattened' again (Univ -> Int) to be of any use in order to interact with the outside program.
One rebuttal has been made is that the blame lies /not/ with type-systems in general, but how they are currently used and implemented.
And so I attempt to debunk this claim, by stating that the perceived shortcomings of latent typings lie not with the concept as a whole, but with how (the majority of) current languages (Ruby, Python, PHP) go about it. I should mention now that I am most familiar with Scheme (and Lisp in general) and intend to use this to put forward my arguments.

Static typing is essentially a method by which a program can be mechanically checked to guarantee that when two functions (f and g) are composed (f o g)( x ): x belongs to the domain of g; the codomain of g is the domain of f; and as such all functions and/or operators are consistent in this fashion. I know very well that static typing has a much greater potential than that (as evidenced in the possibilities of dependent types, GADTs, type/module hierarchies and so on). This checking is performed during program compilation (in other words, prior to the program actually being run) and does NOT add any capability or structure to the code, and has no effect upon the execution of the algorithm.

Many modern (mostly dynamically typed) functional languages are implementing a form of compile-time metaprogramming, and allow direct access to manipulate or query the source code of the surrounding program. My question is, isn't static type checking already possible to implement through that, and therefore a dynamically-typed programming language with metaprogramming features (like Lisp) is MORE expressive in the criteria of compile-time validation. PLT Scheme programmers will be aware of this if they've ever read up on or used MrSpider and/or MrFlow.

Of course, statically-typed languages with such features would be capable of doing the same. But I'd like to digress for a moment to say that the pain of Template Haskell, F# and integrating features like macros on them is plain hell.
Anyway, to deny the above the above statement (not about the criticism of Template Haskell which is sure to start a flame-war) is plain hypocritical for advocates of static-typing and the argument about its superiority previously mentioned. A programming language with features allowing compile-time reflection and processing would easily be capable of isolating a few-modules, marking them 'typed' and sweeping them with the Hindley–Milner magic.

Of course, this would all be quite impractical. Implementing / extending a type-system is a difficult task (even though so far I'm cool with the current and most popular soft-typing attempts) but the same could be set for the Universal type constructor and all the baggage that comes with it. Getting the two worlds to talk to each other is a pain.

Static typing is a limited form of compile-time sweeping. Q.E.D?

Once again, the playing field is level, and the choice between the two is almost entirely about preference.

Syntactic/Semantic Control in MDA Framework

Fri, 10 Oct 2008 11:46:36 -0400

Hi at all,
I'm an italian student and I'm working on a thesis about semantic verification of xml models in MDA (Model Driven Architecture) context.
MDA is an OMG standard based on visual programming languages and automatic generation of code.
In particoular i'm working on a framework that allows programmers to define SOA three tiers web applications.
The programmer can define frontend and backend of these applications in terms of workflows (i.e. graphs).
The problem is that the syntax of these visual programming languages (the graphs for frontend and backend) is underconstrained, so a programmer can define senseless combinations of states.
There are at least two types of errors:

1) Two (type of) states are connected with a transition, but this transition is semanticaly senseless

2) Two (type of) states are connected with a transition, but a pre/post-condition involving other states doesn't hold. For example a transition between two (type of) states is admitted if and only if there is a transition from the fomer/latter state to another state.

The first type of constraints is easy to impose: a simple table could be added to the framework so these type of senseless cuold be checked on-the-fly.

The second type of constraints involve more complex reasoning, and i think there are basically two types of solutions:

a) To check the models (graphs) defined by the programmers, using techniques inherited from Model Checking (formal verification). In this case the control is a post-development control.

b) To define a precise syntax and semantic using graph grammars. I'm quite ignorant in the domain of graph grammars, so i don't know if these instuments are intended for this purpose.

I'm writing to you 'cause i think the problem about syntax and semantic of visual programming languages is undertheorized.
The first solution i proposed has some problems: model checking is intended to check concurrent system, and not to check the problem i described. On the other and, logic, and CTL logic in particoular, is general enough to represent every type of constraint. Still, there are some computational complexity problems (i.e. state explosion).
The second solution is only a vague idea: i don't know graph grammars...
I would like some opinions, references, suggestions or something else.
I know this post is quite general, but there are too much questions that i will describe later, on demand, in order to avoid to write a too long post.
Best regards,

Alberto

DSL or dialects used inside compilers

Thu, 09 Oct 2008 09:32:38 -0400

Hello All,

I am interested in languages used inside compilers. Of course, for front-ends, there are lot of parser code generators (like ANTLR, bison, menhir, ...) and some more sophisticated ones (e.g. attribute grammar based).

Also, functional languages are not only used for their own compilers (eg ocaml being coded in ocaml) but also in other source code related tools like Frama-C (a C static analyzer framework coded in Ocaml).

And code generation also uses specialized formalism (e.g. GCC machine description) and all the BURG like tools.

And even GCC has a middle end lisp dialect (my MELT branch) designed for middle end transforamtion and static analysis.

But there have surely been many other dialects or DSL used inside compilers. Any hints?

Regards.

Swarm- distributed stack based programming language

Wed, 08 Oct 2008 02:29:09 -0400

Ian Clarke presents the prototype for Swarm -a distributed stack based programming language to be written in Scala. The fundamental concept behind Swarm is that we should "move the computation, not the data".

Inspiring Papers

Sun, 05 Oct 2008 19:41:26 -0400

In the interest of discovering some further reading material,
I have created a quick survey open to all LtU'ers..

Please name:

1) One of your favourite papers of all time
2) A recent paper you consider ground-breaking in some way
3) A lesser-known paper that you feel ought to be more widely read

Any PL topics welcome!

FringeDC Formal Meeting Oct 11th 6PM- Writing a compiler for a functional programming language

Sun, 05 Oct 2008 13:42:58 -0400

www.lisperati.com/fringedc.html

FringeDC is a group for people interested in fringe and functional programming languages (Lisp, Haskell, Erlang, Prolog, etc) in the DC area.

This Saturday Andrew Harris will discuss the geeky internals of his EmbeddedML project, which aims to bring functional programming to the world of microcontrollers. It's a lightweight system that generates generic C code, allowing it to support many low resource devices.

This meeting will be presented in conjunction with HacDC, the one-and-only workshop for microcontroller geekery in DC. After the presentation, we'll go out for some beer to discuss all the latest programming topics of the day. Everyone is welcome to join us!

Date: Oct 11th 6PM
Address: HacDC headquarters- 1525 Newton St NW, Washington DC 20010 USA
(Near corner of 16th and Newton NW)
The closest MetroRail station is Columbia Heights (Green Line). You can check online to see the next train arriving there. The S1-2-4, H1, and H2-3-4 buses go right by our location.
Approach on the 16th St side of the building. Look for the red doors. We are on the third floor. Follow the signs to our space after signing in with the guard.

http://maps.google.com/maps/ms?ie=UTF8&hl=en&msa=0&msid=112368426664365520724.00044a72684e313eb7ebd&ll=38.932307,-77.03521&spn=0.008813,0.007253&z=17&iwloc=00044a727d23d707d87b9

-Conrad Barski, M.D.

Clojure talk videos

Fri, 03 Oct 2008 21:54:29 -0400

Clojure was mentioned here before and the Boston Lisp talks from Rich Hickey are amazing: Part 1 and Part 2. Just the idea of imutable vectors, sets and maps as additional first class data structures with different kind of parentheses already makes it the best lisp for functional programming ever.

Visual Programming Language Syntax Formalisms

Wed, 01 Oct 2008 18:19:08 -0400

What formalisms are available for specification of visual (i.e., graphical, two-dimensional, diagrammatic) programming languages? Which of these, if any, are popular?
If readers feel that few are popular because visual languages are of limited use, do these readers refute the premise that visual syntax is a superset of character sequence syntax?

C# and Computer World

Wed, 01 Oct 2008 16:24:14 -0400

The Computer World series is continuing with Anders Hejlsberg on C#. Of particular interest is his discussion of F#:

Q:What do you think of functional programming in general?

I think that functional programming is an incredibly interesting paradigm for us to look at, and certainly if you look at C# 3.0, functional programming has been a primary inspiration there, in all that we’ve done with LINQ and all of the primitive language features that it breaks down to. I think the time has finally come for functional programming to enter the mainstream. But, mainstream is different from taking over the world.

I definitely think that there is a space for functional programming today, and F# is unique in being the first industrial strength functional programming language with an industrial strength tooling language behind it, and an industrial strength platform underneath it. The thing that’s really unique about F# compared to all of the other functional programming languages is that it really offers first class support for object oriented programming as well, and first class interoperability with the .NET framework. Anything we have in the .NET framework is as easy to use from F# as it is from C# as it is from VB – it does not feel forced.

A lot of functional programming languages have lived in their own little world, and they’ve been pure and mathematical and so forth, but you couldn’t get to the big library that’s out there. If you look at languages today, they live and die by whether they have good framework support, as the frameworks are so big and so huge and so rich that you just cannot afford to ignore them anymore. And that’s why you’re seeing so many languages being built on top of .NET or on top of Java as opposed to being built in their own little worlds.

And what he sees as the importance of the entire software ecosystem to programming.

closure-based object-oriented programming languages

Wed, 01 Oct 2008 15:19:21 -0400

It's common for Scheme programers to develop object systems based on closures. An object's methods are closures whose free variables comprise the object's instance variables. The object itself is represented by a method lookup function. See for example Ken Dickey's "Scheming with Objects".

Have any programming languages been based on closures as the fundamental building block?

Lazy Graph Reduction and abstract machines

Wed, 01 Oct 2008 11:28:48 -0400

I'm trying to find some interesting abstract machines that support lazy graph reduction. Haskell implementations seem to prefer the Spineless Tagless G-Machine (GHC, NHC, YHC), and the G-Machine (Hugs). I've heard that Clean is based on the ABC Machine, but I can't really find any literature on it. I've also seen the machines that SP Jones mentions in his "Implementing functional languages, a tutorial", which IIRC includes: Template Instantiation, the G-Machine, and the Three Instruction Machine (TIM).

I have a couple of questions about this:

1) Are there any other interesting machines out there?
2) Where can I find some information on the ABC machine?
3) Why do Haskell implementers love STG so much?

EDIT: Spineless Tagless G-Machine, not Stackless...

Programming Languages Aren’t

Mon, 29 Sep 2008 19:34:07 -0400

What is a programming language? The common definition generally only includes the syntax and semantics of, for lack of a better description, the “text” of a program. For instance, we think of languages as defining how variables are declared, how loops are specified, functions defined, if certain mechanisms like continuations or closures are first-class (or close to it), etc.

This definition fails to capture how the languages are really used, though. Just because a handy library is written in C++ doesn’t mean it will integrate nicely into my present C++ program. The reason is that it is the APIs that are the real language - not the obscure rules that define what a loop looks like or which characters are allowed in a variable name.

I realize this is a (potentially mis-informed) blog post (from my own blog, no less), but I'm not familiar enough with the research to know if this phenomenon has been widely studied or not. (And if so, where I can read more about it.)

In my experience, the integration of multiple libraries with different styles is one of the primary reasons large programs often devolve into an incomprehensible mess over time. It's not the only reason, of course, but I think it contributes - especially when some programmers on the team are more familiar with one library vs. another, etc.

What could be done in the context of a programming language to mitigate this? Or, what has been done? It doesn't seem like the mainstream languages are very good at keeping this problem at bay. (Or is it perhaps not a problem for anyone but me?)

Can function pointers be "fixed"

Mon, 29 Sep 2008 17:20:35 -0400

Whilst thinking on the subject of language design, specifically lowish-level (C++ level), I came up against the seeming brick wall of function pointers. Now, whilst function declarations can be modified to allow for such niceties as closures, coroutines and multiple return values, function pointers, it seems, can never be harnessed for the power of good. The reason for this seems to be the way that functions are declared in C-type languages, i.e. completely differently from data and, I might add, rightly so. I much prefer:
int doIt(int a) CODE
or even something along the lines of:
int,int iHandle:swapInt(int a, int b) CODE
as a more elaborate coroutine with a multiple returns and a handle to its own instance, compared to more object based delcarations:

(int)function(int) doIt = new (int)function(int) CODE
(note: this is just an example in a sugarless but statically typed language, I'm sure there are nicer ways of having OOP function declaration)
which, in any case also brings up the question of integrating return types into the declaration (hint: Pascal is also very ugly)
However, even for the modest simple function, the C function pointer of
int(*fp)(int);

is just completely whack compared to the rest of the data declarations.
int a; char c; int(*fp)(int);
(spot the odd one out)

So my question is this, has anyone encountered a statically-typed function/funcpointer declaration system that is at all elegant?

-DNQ

To CPS or not to CPS

Mon, 29 Sep 2008 14:03:08 -0400

Old question, still difficult. I am in the process of moving from a compiler which compiles the source code to an AST representation in C and then runs a trampolining interpreter on top of it, towards full-blown C compilation.

I am puzzled whether to do the CPS transform or not (major code expansion, seems like a large performance hit? Or am I using the wrong transform?). I can also go ANF but actually, I am not too sure how to compile the ANF representation efficiently.

And actually, is there any _real_ difference between CPS and ANF? Seems to me that the CPS transform just makes the return pointer explicit in the lambda representation.

Any thoughts?