Lambda the Ultimate

I read about these two new PHP 6 language changes on SitePoint Blogs today and left scratching my head.

Hi all,
So I'm working on a simple project where I am specifying relatively large sets of chemical reactions (graph transformations) with these things called SMILES strings.

It's kinda neat that once you start working with many strings, it feels like you need to look at the science of programming languages. How does on specify large sets of transformations efficiently in such a way that those specifications are maintainable and debugable etc. I like to think of the SMILES strings as assembly language, and I hope to create something a little higher level to make the job of specification a little easier.

It turns out I am in need of a simple preprocessor type language where I can specify and apply functions in a very "embedded" way. I think it would be pretty simple to do, I should be able to do it myself, but I really want to make sure that I am doing it the "right" way. I.e. under the guidance of someone who really knows a lot about the science programming languages. It'd be really nice to see if this work gives anyone any new good ideas.

Why am I doing this? Well it turns out there is a very important question about chemistry I can answer with this system in hand..it don't want to clutter this post, but it has to do with predicting what sorts of molecules will manufactured in the future.

I wonder if there are people other than chemists who would need to specify and maintain large sets of graph transformations and run them on large data sets...

I'm technically a chemistry grad student who does crystallography for living. I've written a lot of of the other parts I need already (i.e. some plumbing to apply a set of rules over the linux cluster at our instiute). I've got a good publication record and I'd be happy to forward my cv to anyone that would be interested in devoting a little time with me to this project. It's weird, I already have enough publications to graduate, but I am kinda using this last little bit of time to try to do something different instead of slumbering into retirement like I see a lot of grad students do.

If you have a strong knowledge of programming languages and would be interested in doing something simple, but unique and very useful, please write me at yadavm with the domain name scripps.edu. Maybe your interested in using your talents in something closer to chemistry and biology.

Famous words, but I expect to write the whole thing up in just a month or two, of course just about all I can offer to you is co-authorship. Lunch if you're in San Diego.

The Scala language fuses object-oriented and functional programming while staying completely interoperable with Java. It is compiled to JVM class files, subclassing is allowed both ways between Java and Scala classes, and no glue code needs to be written by users.

Scala also adds several important and convenient constructs, such as:

- mixin composition with traits,
- first-class functions,
- case classes and pattern matching,
- XML expressions and patterns,
- virtual types,
- for-comprehensions,
...

The second major version of Scala is now publicly available. This version adds some new constructs to the language and simplifies some idioms (http://scala.epfl.ch/docu/scala2.html).

There are also the following new tools:

- a new `scalac' compiler, which is completely written in Scala

- a new `scalaint' interpreter shell, which is integrated with the compiler and which drops most restrictions of the previous version.

- a new Eclipse plugin. See http://scala.epfl.ch/docu/eclipse/index.html

- a new tool `sbaz' to manage and distribute Scala packages. See http://scala.epfl.ch/downloads/sbaz.html

This implementation runs on the Java VM, JDK 1.4 or 1.5. An automatic installer is available for Windows, MacOS X, Linux, Solaris, and most other operating systems.

For further information and downloads, please visit:

http://scala.epfl.ch

I've recently been looking at high-level ontologies, such as CYC and SUMO for a project I'm working on. Clearly, there is a connection between techniques used for organising class hierarchies and those used for organising ontologies (class hierarchies are ontologies, at least superficially). Going further, there seems to be an overlap between languages' standard class libraries and these high-level "common sense" ontologies. Each describes quite general concepts like "objects", "processes", "sets" and "classes", and then provide more specific concepts for particular domains. With RDF and OWL becoming popular (or not?), I wonder if there will be a merging between these two similar areas. Are there any languages that come with a standard ontology? Are there languages whose tools for modelling class hierarchies more closely resemble those of ontology authoring tools? For instance, supporting more than just "subtype" and "instance" relations (i.e., more like first-order logic or a description logic). Haskell's type-classes come to mind. Is there any restriction on the kinds of relations between types that can be expressed by type-classes? Are there techniques that can be applied to type/class-level organisation from ontology modelling?

We have a new apprentice programmer here at work, and I was trying to explain to her the difference between complete and lazy boolean evaluation, and why she should be always be mindful of side effects when it's turned on or off. While she grasped the concept well enough, she confounded me in asking why the distinction exists in the first place (seeing as it creates side effects).

This got me thinking whether "semi-complete" boolean evaluation would be an asset to an imperative PL.

For example:


// Scenario A:
if (boolVar1) and (boolVar2) then
.
.
.
endif;



// Scenario B:
if (boolVar) and (someObjectInstance.someBoolMethod) then
.
.
.
endif;



//Scenario C:
if (someObjectInstance1.someBoolMethod) and (someObjectInstance2.someBoolMethod) then
.
.
.
endif;


In scenario A, completely lazy evaluation is the preferred way, because the expressions being evaluated are boolean variables, pure and simple, and the compiler should automatically enable lazy evaluation for that conditional.

In scenario B, someObjectInstance.someBoolMethod might do some internal processing that we want regardless, yet the ordering of the expressions determines that that might not happen if BoolVar is false and the expression is evaluated "lazily". This in some ways spoils the pure nature of boolean logic because expression order becomes important in determining the result, and switching lazy eval on/off becomes an issue.

Similarly, in scenario C, the same issues apply.

I realise that these issues can be avoided by reordering or splitting the conditional statements into multiple if/then's, but what about if the language, as a rule, ALWAYS evaluated expressions, if they were methods or function calls, regardless of where they occured in the conditional. For scenario B, for example, that would mean that even if boolVar was false, the someObjectInstance.someBoolMethod still gets called, except that the conditional statements below get skipped .

The overall effect would be that the language always presents complete evaluation to the programmer (who then does not have to factor in expression order), but can benefit from lazy evaluation if the compiler deems it appropriate.

It could perhaps also be possible to have a language construct to force the lazy evaluation, for example:


ifl (BoolVar) and (someObjectInstance.someBoolMethod) then...


or


if (BoolVar) and ?(someObjectInstance.someBoolMethod) then...


or suchlike, with the compiler giving appropriate warnings where neccessary.

I understand that allowing expression order to be an issue, is A Bad Thing regardless, to be avoided by careful code habits. I am also not neccessarily advocating the "semi-lazy" method, as I recognise how it introduces a new way of creating undesirable side effects (namely what happens inside the called methods), but I am nevertheless interested in hearing your comments on the topic.

Regards,
Riaan

One of my best friends is a Ph.D. student in a well-respected geology department, and an avid R user. He informs me that the programming language "R" is highly fashionable in his department, and is increasingly popular across his field.

I mention this because R encourages functional programming, and I have not heard it mentioned on LtU. Here is a quote from the language manual:

R is a system for statistical computation and graphics. It provides, among other things, a programming language, high level graphics, interfaces to other languages and debugging facilities. This manual details and defines the R language.

The R language is a dialect of S which was designed in the 1980s and has been in widespread use in the statistical community since. Its principal designer, John M. Chambers, was awarded the 1998 ACM Software Systems Award for S.

The language syntax has a superficial similarity with C, but the semantics are of the FPL (functional programming language) variety with stronger affinities with Lisp and APL. In particular, it allows “computing on the language”, which in turn makes it possible to write functions that take expressions as input, something that is often useful for statistical modeling and graphics.

It is possible to get quite far using R interactively, executing simple expressions from the command line. Some users may never need to go beyond that level, others will want to write their own functions either in an ad hoc fashion to systematize repetitive work or with the perspective of writing add-on packages for new functionality.

Here is another quote from the FAQ:

The design of R has been heavily influenced by two existing languages: Becker, Chambers & Wilks' S and Sussman's Scheme. Whereas the resulting language is very similar in appearance to S, the underlying implementation and semantics are derived from Scheme.

The upshot is that "S" is dynamically scoped while "R" is lexically scoped. I applaud R for getting this right, but the FAQ makes an interesting counterpoint that I paraphrase here:

Nested lexically scoped functions also imply a further major difference. Whereas S stores all objects as separate files in a directory somewhere (usually .Data under the current directory), R does not. Having everything in memory is necessary because it is not really possible to externally maintain all relevant environments of symbol/value pairs. This difference seems to make R faster than S.

The down side is that if R crashes you will lose all the work for the current session. Saving and restoring the memory images can be a bit slow, especially if they are big. In S this does not happen, because everything is saved in disk files and if you crash nothing is likely to happen to them. (In fact, one might conjecture that the S developers felt that the price of changing their approach to persistent storage just to accommodate lexical scope was far too expensive.)

Other than scope, R tries to be as close to S as possible. I'll end with two amusing remarks from the introduction:

Warning: for() loops are used in R code much less often than in compiled languages. Code that takes a `whole object' view is likely to be both clearer and faster in R.

Note that any ordinary assignments done within the function are local and temporary and are lost after exit from the function. Thus the assignment X <- qr(X) does not affect the value of the argument in the calling program.

Enjoy.

Is it possible to do type inference of an object oriented language (such as Java) without any type annotations? I've never seen it done and I'm curious about why that is. During my limited exposure (to type inference in general) I've been taught that it is possible to do type inference of rank 1 polymorphic functions but the general case (rank 2 and up) is undecidable without type annotations. How does this relate to the type of polymorphism used in object oriented languages?

Even though message passing can be thought of as a special case of the generic functions approach, there still seems to be something appealing about grouping procedure implementations and their shared data into logical units as in Smalltalk. I understand that polymorphic dispatch need not be conflated with program modularity / encapsulation, but for some reason it still feels like a good idea to me. I looked around this afternoon for a good discussion of multi-methods vs. message passing and came up empty, so I'm wondering if anyone could point me to one or share their thoughts on the issue.

I am interested in writing a lispy scripting language that integrates with the Apple's Cocoa environment, which is based on Smalltalk and therefore hardcore message-passing based. I would like a seamless connection into that world from this language. But I also want the power of multi-methods. I am imagining a language in which first-class namespaces could be blended with the Smalltalk approach to objects, exposing methods that respond to messages. But within these namespaces multi-methods could be used when they seemed appropriate. Therefore, in the large, the program would be assembled out of modules that resembled Smalltalk objects, but the implementation of methods exposed by these modules could have a lispier style. This is all very vague I know... and there's the obvious question of where multi-methods would belong. Any ideas?

Reading Martin Oderski's paper Scalable Component Abstractions, I ran across citations to the languages CeasarJ and Gbeta, both realizing a concept called virtual classes. This concept is explained, and a calculus given in the paper A Virtual Class Calculus by Erik Ernst, Klaus Ostermann, and William R. Cook.

Virtual classes are class-valued attributes of objects. Like virtual methods, virtual classes are defined in an object's class and may be redefined within subclasses. They resemble inner classes, which are also defined within a class, but virtual classes are accessed through object instances, not as static components of a class. When used as types, virtual classes depend upon object identity -- each object instance introduces a new family of virtual class types. Virtual classes support large-scale program composition techniques, including higher-order hierarchies and family polymorphism. The original definition of virtual classes in BETA left open the question of static type safety, since some type errors were not caught until runtime. Later the languages Caesar and gbeta have used a more strict static analysis in order to ensure static type safety. However, the existence of a sound, statically typed model for virtual classes has been a long-standing open question. This paper presents a virtual class calculus, VC, that captures the essence of virtual classes in these full-fledged programming languages. The key contributions of the paper are a formalization of the dynamic and static semantics of VC and a proof of the soundness of VC.

Lately I have been coming across a set of ideas which seem to be related:
Logic/constraint/relational programming, unification, back tracking, business rules, logic variables, Gentzen, sequent calculus and so on.

Is there a comprehensive introduction to all of the above? I would like to know the meaning of the terms mentioned above and, if possible, how to implement them.

Krishnamurthi's book Programming Languages: Application and Interpretation mentions prolog, but doesn't show how to implement those ideas in scheme. The Reasoned Schemer is not easy to follow (due to the style of the book). It is not the kind of book one can read once a week after work. There are a few constraint logic books on Amazon, but I obviously don't even know enough to understand if they are good introductions.

There is a lot of talk of how functional programs operate at a higher level of abstraction (compared to imperative programs)...don't these logic/constraint programs operate at an even higher abstraction? Lisp defenders always make sure newbies understand that Lisp is not just for AI. Is the same true of prolog? I have read that logic programs are not very efficient; however, if they are related to relational databases (as claimed somewhere), then can't an 'index' be added to a list of 'facts' to make sure logic program's operation is as efficient as any other program?

I'm just trying to get a sense of the field, its benefits, its pitfalls and reasons why it is not so popular. Thanks.