Lambda the Ultimate

Dear fellow LtU members,

I took the initiative and started a petition for adding garbage collection to C++. You can find it here:

petition for adding garbage collection to C++.

Maybe if we get too many, the C++ standards committee will hear us!

Queensland University of Technology Programming Languages and Systems Research Group, which was behind Component Pascal and Modula compilers for CLR and JVM, has released a Ruby compiler for CLR and JVM. The compiler reportedly passes all 800+ tests in the Ruby 1.8.2 test.rb test suite.

On their web site the group stresses that this is a compiler, not a Ruby/.NET bridge, although further reading indicates there's a runtime library that mirrors the structure of the Ruby interpreter. The group is apparently looking for Ruby and/or .NET users to do testing and development; the full source is available under a liberal license.

The group's web site contains some comments about the implementation approach and some loot for programming language implementors: a YACC-compatible parser generator for C#, and a library for manipulating PE files.

In the June 2006 Issue of IEEE Computer (Volume 39, Number 6) Gerald J. Holzmann of the NASA/JPL Laboratory for Reliable Software authored "The Power of 10: Rules for Developing Safety-Critical Code" on pages 95-97.

I don't have an online link to the article text, but it can be summarized as:

Rule 1: Simplify Control Flow Banishing Recursion.

Rule 2: Set a fixed upper bound on all loops, excluding non-terminating event loops.

Rule 3: Banish Dynamic Memory Allocation and Garbage Collection.

Rule 4: Restrict each function's size to around 60 lines of source code.

Rule 5: Make liberal use of assertions to test any condition that can't be statically guaranteed.

Rule 6: Use static scoping to hide "data objects" to the greatest extent possible.

Rule 7: Check all return values and caller supplied parameters.

Rule 8: Banish any significant macro use (like "token pasting", "variable argument lists", and "recursive macro calls") beyond header file inclusions and simple defintiions.

Rule 9: Banish handles, macro-driven pointer manipulation, and function pointers while restricting pointer use to one level of dereferencing.

Rule 10: Continuously recompile all code with all compiler warnings turned on and ship no code until all warnings are eliminated and it passes strongly typed static analysis.

One gets the sense that these strictures are informed by life in the C/C++ discourse community, but they do raise deeper questions of whether the dynamic world and functional programming in general can support Safety-Critical Code. Could literate programming techniques be leveraged to further improve the reliability of such code?

Could we in effect replace these 10 rules with:

Rule 1: Code in Scheme, Haskell, or F#.

Rule 2: Embrace Literate Programming.

I have much more experience with imperative code (like most programmers) but I'm starting to branch out and have done a little bit of Ocaml and am endeavouring to learn lisp. So I stumbled on this article, "Functional Programming For The Rest of Us," thinking it might inform me about the benefits of my choice to learn some functional languages.

My question is: What am I missing? The article seems to ascribe a number of features to functional languages that don't seem to be particular to them. Treating functions as first class objects for instance. Or partial evaluation. He says that debugging is much easier because there's no global state -- but you can just view global variables as syntactic sugar for variables that are passed to every function.

He claims that patching Java code at runtime would be much harder than in FP -- but I don't see how that's something inherent about Java as a language (as opposed to implementation). He says this is because in an FP language "all state is stored on the stack." Which a nice thing to stay, but I could just as easily say, in a C program, "all state is stored in the global segment, the code segment, the data segment, and the stack segment." So if saving and modifying the stack is so easy, why can't I do it for a C program? Apparently we have some method for restoring the stack segment, the code and data segments are constant, and the global segment is just a list of values.

Closures are also described as being a functional language thing. I see them as a "easier to implement if you're delaying compilation until runtime" sort of thing. Python 2.5 can supports all the coding techniques described in the article and it certainly feels more imperative than functional, and certainly lacks the most distinguishing feature of FP I know of (no side effects).

Is he just confusing functional languages implementing certain features before imperative languages did with there being an inherent advantage to functional languages?

Admittedly, one advantage that he does bring up that seems accurate to me is that functional languages are easier to mathematically reason about. Although I remain skeptical of the practical advantages of this -- for all the cheering about it, every functional language implementation I've seen has been slow compared to C (yes I know it hard to objectively state that one language is faster than another, but one somehow becomes remarkably better at determining this when there's a paying client that needs something super performant). If lack of side effects and lazy evaluations provide such an optimization bonanza, why haven't I seen it yet?

I have posted a new version of the Cat interpreter and documentation at http://www.cdiggins.com/cat/. Cat is a programming language designed as a high-level intermediate language. Cat is inspired by Joy, and resembles a cross between Scheme and Forth.

Comments, questions and suggestions welcome!

It feels as though that advancement of OO is reaching it's peak in the context of PLT, even with Cecil/Diesel being beyond there time in OO languages i feel as though this is far as one can't take with it.

One only has to look into the results of newer OO programming languages resorting to adding features from other paradigms to make them more expressive, quite often being functional and then there was that recent paper about advance procedural languages. So is there a clear direction that OO research is taking?

Recently I've been working on a language for programming some of the higher-end PIC microcontrollers. These are very resource-constrained machines, but they can be programmed in C; the one I use the most, the PIC18F4520, has only 32 Kbytes of flash program memory and a whopping 1536 bytes of RAM.

The problem is, while C is a semi-decent language (at least compared to PIC assembly), it still sucks for PIC programming. A lot. In order to make any non-trivial program, you need to set up a bunch of the onboard hardware modules which all have low-level access methods, and you need to do a bunch of interrupt programming (pragmas everywhere!) which gets you mired in a mess of low-level details -- did you remember to clear a certain bit in some obscure configuration register?

For most of the PIC programs I write, I actually think about the problem in terms of data flowing between blocks, similar to Simulink. For example, I might envision a program which performs analog to digital conversions and passes those values on to a bank of LEDs as a simple block diagram with two blocks, one for the A/D converter and another for the LED output. If blocks of arbitrary C code are supported and blocks for other hardware modules are added, this concept turns out to be powerful enough to handle almost every PIC program I've written, and without the pain of writing C code for the PIC. For example, here's a fairly simple program in a lisp-like syntax:

;; Define the configuration for the hardware devices
(config-bits
 (a/d :an1)
 (trisb 0)
 (trisd 0))

;; Define a custom block of C code
(defcode-inline inverter (x)
  "(~x)")

;; Connect analog input 1 (an1) to a bank of LEDs (latb)
(-> an1 latb)
;; Another bank of LEDs (latd) will be the bitwise inverse of latb
(-> an1 inverter latd)     ; Equivalent to (-> an1 inverter) (-> inverter latd)

This would be a lot harder to write in C, and I've got a partial implementation of a compiler for this language which is working fairly well, so I think I'm onto something good here.

Unfortunately, there's probably a mess of useful information about these sorts of blocks-and-connections languages, and I don't know any of it. So, better informed people: what do you think of this type of programming language? Are there any practical issues I should know about? And how would I go about typechecking this sort of language? Since type mismatches are likely to be caught by the C compiler and presented as baffling error messages complaining about perplexingly named mangled symbols, some form of static typechecking before the intermediate C code is generated takes on more than a little urgency.

There's been much discussion of Epigram, but I have yet to see much discussion of Applied Type System. There have been a few stories here on LTU, but relatively little discussion. This surprises me as ATS seems quite advanced.

As a relative newcomer to type theory, I'm interested in the relative merits of ATS vs. Epigram vs. any other dependently typed languages that might exist. From my understanding, Epigram is a Pure Type System that seeks to unify types and terms, where ATS distinguishes the statics and dynamics of the language. What benefits and limitations do these approaches have on complexity for both developer and implementor?

Why is there still the trend to create languages where most functionality is implemented in some standard-libraries und not in the language itself?

Quite often lots of time and effort are invested to make a language as extensible as possible and to create every feature (even standard datatypes, like arrays, lists etc) in the library and not as part of the languages itself. I think that's really antiquated thinking from the early years of CS where the usual usage patterns of programming languages where not so well known and an extensible language seemed much more powerful. But this has changed a lot: Today most usage patterns are commonly known and while there are lots of them, the total number of those patterns seems quite manageable.

Often it's unneccessary difficult to use those 'library implemented' features. Think of using lists in a language without native list-support (like Java, C++ etc) and compare that to a language with native list-support. It's so much easier and much more readable in the latter.

But why stop with those 'low-level' features? Why not try to build a language with ALL common used features directly in the language: From strings to maps to general graphs. From loops to threading to database-access. From visitor to observer to MVC. A language without much of a 'standard-lib' because it's mostly integrated in the language itself. Instead of inventing Systesm to create DSL why not simply create and integrate all those 'DSLs' in a single language?

Sure, such a language would be less 'cute' than a minimal one. But I suspect we could gain lots of productivity, safeness and performance.

Apologies if this has been posted already, but I haven't seen this mentioned on LtU before.

HLVM is...

"A complete compiler developer's toolkit for creating new languages easily. To write a new compiler, language designers simply write a plugin that describes the language to HLVM and how to translate the grammar productions into HLVM's comprehensive Abstract Syntax Tree (AST). After that, HLVM handles all aspects of code generation, bytecode storage, XML translation, JIT execution or interpretation, and native compilation."

"Aimed at supporting dynamic languages such as Ruby, Python, Perl, Jython, Haskell, Prolog, etc."

"A language interoperability framework."

I'm not sure if "dynamic" means dynamically typed or truly dynamic in that the semantics of the language can be changed from within the language itself.

HLVM is implemented on top of the LLVM that has been discussed on LtU a few times.

http://www.hlvm.org
http://www.llvm.org