Lambda the Ultimate

I'm a developper on a large project, and regulary have to deal with database performance and design issues. To solve them our DBAs have to explain us many internals of our database system, but tends to do it with the database vendor's point of view (Oracle) as much of their knowledge comes from the books published by the vendor.

As a consequences, I often can't know if the limitations/contraints they exlpain us are intrinsic to relational engines or are specific to Oracle, and this makes technical discussions difficult and frustrating.

I've read Codd's papers and much of the free papers of dbdebunk.com to learn about relational theory and vendors's positions and now I'm looking for a detailed paper or book that explain how to design/write a non-trivial relational database with the usual features (ACID, persistence ...) without being poluted by a vendor point of view.

Until now, I failed to find something that match this description: I only found beginner-level documents or some open source docs that explain technical issues with specific problems.

I hope it's not too implementation-related for LtU and that someone can help me.

We've got a survey with about 20 questions that ask for your practices relating to some commonly taught design principles for object-oriented programming. Please take 10 minutes of your time to answer these questions in terms of how you generally make design decisions.

Your answers will be anonymous. We do track IP addresses but only to check data integrity. The IP addresses will not be used for any analysis or published in any way, and the survey is totally anonymous! (+in keeping with the open source tradition, all survey results will be open source as soon as the analysis is done!).

In the famous paper "Can Programming Be Liberated from the von Neumann Style?", Backus describes the programming language FP. It has many properties that are clearly advantageous:

• Programs are written in terms of a well-understood set of combining forms that preserve termination properties
• Data structures are persistent and IO is well-structured
• Functions are not first class objects making certain forms of reasoning easier
• Programs are written primarily in terms of function composition, not application, which makes manipulation of programs easier (or at least, it does in my estimation)

There is one more prominent property: FP is a pointfree language. My question is, how advantageous is this really? Obviously it does make manipulation of programs easier in some sense, but its benefits seem to pale in comparison to the benefits derived from other properties (such as its first order nature).

There is also a big limitation that results from not having any sort of "substitution form": It is not possible to "lift" objects into functions. For example, if one wants to write a function that takes some value X and a list and multiplies every element in that list by X, there's no way to "lift" that X into the 'map' combining form. One must instead use 'distr' to transform the list into a list of pairs where one element of each pair is 'X', after which the multiplication function can be mapped over the list. Besides being a bit opaque, this is needlessly inefficient.

Of course, one could always write a new combining form to handle this particular situation (if the language were to permit it), but there's no way to write it in terms of the existing 'map' form without substitution or higher order functions (which would permit partial application); it must be written from scratch, and as such, can't trivially inherit any properties of 'map'. In some sense, the lack of substitution seems to work against the idea of programming with a well-understood set of combining forms.

This is hardly an attack on the idea of pointfree languages. I'm well-versed in concatenative languages (which typically do offer variables as an escape hatch), I've written non-trivial programs in FP, and I utilize the pointfree style in Haskell heavily. I do very much enjoy pointfree programming; I simply am having trouble justifying it in an objective manner.

All thoughts and pointers to relevant literature will be much appreciated. (To be clear, I'm looking for materials that directly address the benefits of doing away with variables, not the other properties of FP or SQUIGOL-like languages such as programming with a rich set of combining forms or morphisms.) More specifically, if anyone were able to comment on what one would lose if a substitution form were added to FP, you'd have my gratitude.

Programming languages are ultimately interfaces for people to interact with the world of computational possibilities. In that backdrop, I've recently been interested in the influence of cognitive models on programming language design and would like to hear the thoughts of the tU community on the topic.

I think the recent rise of DSLs warrants more research in this area. Past work has been largely populated by debates on completeness, compiling vs. interpreting, efficiency, dynamic vs. static, typed vs. untyped, parallel vs. sequential, distribution, designer idiosyncrasies and, not to mention, elegant vs. ugly.

While I don't deny the importance of the debates, the only one that comes anywhere near the territory of cognitive models is this notion of "elegance", but that's (as far as I know) never dealt with formally.

I see a few areas of work here -

1. Bringing schemes from models of brain function and cognition to programming languages.
2. Using findings of cognitive psychology in designing aspects of programming languages
3. Studying how we model the languages that we use and "like" - i.e. cognitive modeling of programming languages.

(Maybe others strike you.)

For an example of (1), Drescher's schema building mechanism seems a very interesting angle to building interfaces to the world of computation. (see Made-up Minds) .. and it does look like people are trying to apply that approach to special areas. Production rules (grammars) are another category. Of course, one can't forget Prolog.

AppleScript and Hypercard are simple examples of (2), 'cos they were intended to be usable by non-computer science folk and yet are powerful enough scripting languages. Elements of the language such as "tell ...", and "it" exploit our ability to refer to "at hand" and relative entities without much effort. The Logo world and, particularly, Scratch must be mentioned too. I myself got interested in this topic after I worked on adding "the" and "it" to my own scheme toy and found some cognitive modeling results such as working memory size useful in determining usage boundaries.

(3) is interesting as part of the design iteration loop.

Thots?

---
Link summary (extracted from posts) -

1. Chris Barker
2. Inform (language for interactive fiction)

Hi,

This is to announce the first official release of Dao.

Dao is a simple yet powerful object-oriented programming language with many advanced features including, soft (or optional) typing, BNF-like macro system, regular expression, multi-dimensional numeric array, closure, coroutine, asynchronous function call for concurrent programming etc. Dao provides a rich set of standard data types, methods and libraries. Dao is implemented as a light and efficient virtual machine with very transparent C programming interfaces, which make it easy to extend Dao with C/C++ or embed Dao into C/C++ programs.

There have been a lot of improvements since the last release including: a lot of bug fixing and some broken feature fixing; several large implementation changes to improve the structure and clarity of the codes; and some implementation of new features. For the details, please have a look at: http://www.daovm.net/?page=dao_whats_new.

Besides the improvements to the language and its implementation, the modules, tools, documentations and website associated with this language have also been improved greatly. The documentations are more complete than before, and are prepared in nice formats for easy referencing. A number of demos are also included in the release, including some programs for the The Computer Language Benchmarks Game, which can be tried out just for fun.

One automatic tool (tools/autobind.dao) was developed using Dao itself, and was used to create most of the released Dao extending modules, by generating wrappers directly from the header files of the corresponding C/C++ libraries. This tool could also be used to wrap other C/C++ library as necessary.

A new website that was developed using Dao itself too, has been setup at http://www.daovm.net, and is going to be the new official website of Dao. This new website will be established as a serious platform to promote the spreading of Dao and to grow a community of its users.

Have fun.

Links:
Home: http://www.daovm.net
Document: http://www.daovm.net/?page=document_en
Download: http://www.daovm.net/?page=download_en
Forum: http://www.daovm.net/?forum

(edit: fixed some links)

Registration is now open for this year's Code Generation conference. An early-bird booking period runs until 31st March offering significant savings on conference fees.

The conference has a strong practical focus and includes 30+ sessions on many aspects of code generation and model-driven software development.

The event is supported by IASA, OMG, ACCU, SkillsMatter and Cambridge Wireless and members of these organisations receive a further discount on conference participation.

Event sponsors include Microsoft, SoftFluent, itemis and Kennedy Carter.

Dynamic Logic is a topic that I don't recall seeing on Ltu previously. I am quite intrigued by the way it merges action (ie side effects) into a more or less conventional logic. It is also interesting that this is core computer science going back to the 1970's, and there is a nice text book. Can anyone really say that there is some problem with action semantics?

The sixth Commercial Uses of Functional Programming (CUFP) workshop is going to be held in sunny Edinburgh this year, and is now inviting talk proposals.

For those that haven't attended before, the workshop is a lively mix of academic and industrial uses of functional programming in all manner of areas and languages. This year the keynote will be Bryan O'Sullivan, co-author of Real World Haskell which was published a few months ago.

Check out the full Call For Papers at: http://cufp.galois.com/2009/call.html

... and hope to see you at the workshop in September!

Greetings,

I am having trouble wrapping my head around by-value substitution in lambda calculus. To try to warm up to lambda calculus I wrote a reducer, which works for leftmost outermost evaluation. However, when I tried to implement by-value it seemed to work fine, accept in a situation where by-value should have failed. Instead I get the same reduction as if I were using the left-outermost substitution (which in this case should succeed). I am using the definition given in Sestoft, Peter's "Demonstrating Lambda Calculus Reduction." Given this occurrence of an error, I am led to the conclusion that either (1) I got lucky on left-outermost reduction or (2) I am missing something on by-value reduction.

I would greatly appreciate any feedback or advice that this community can give.

Sincerely,

Jon

Hi,

I'm currently implementing an algorithm which allows one to synthesise coalgebras given various local/global specifications, these being coalgebras of a covariant endofunctor T on Set^m where Set is the category of sets and m >= 0.

I have a problem regarding the genericity of what I am trying to implement, which I hope someone can shed some light on. Although I'm using Haskell, I'd be interested if any other languages are capable of what I ask. My problem is not with the algorithm itself but rather with an initial preprocessing stage.

In general terms I want to construct a collection of interleaving data types given some specification of how they need to be interleaved. This needs to happen at runtime. Previously for my MSc I implemented a fragment of this algorithm, at that time I got round this problem by generating the Haskell code with a script -- kind of an ugly solution. On the other hand I guess its hardly a common thing for the user to create their own data types.

I'd very much appreciate any pointers,

Cheers,

Rob