Lambda the Ultimate

Chris Double's recent post mentioning Thinking Forth reminded me of FreeTechBooks.com.

Looks like a good place for everybody to check and add their entries, in case they haven't been submitted yet.

For example, neither of the two books mentioned recently by Ehud is listed in the Common Lisp category yet.

I am in the process of designing a few domain specific languages. Thus I wondering about if people have suggestions about the design of syntaxes. It's generally not a topic of LtU. Nonetheless it is a practical problem for language designers. In a few cases, syntax does make a difference. e.g. Python and Lisp. Maybe it's a vague question. However I don't know how I could bring orderness to this topic.

This paper explores the empirical results of a number of recent (and not-so-recent) papers showing that larger software components are proportionately much more reliable than smaller software components within the same system up to a certain size after which they rapidly deteriorate. This is strongly counter-intuitive to basic notions of software engineering such as modularisation.

The paper first demonstrates that a logarithmic distribution of fault with component complexity closely fits the observed data over a range of component sizes and languages up to around 200 lines or so, (deemed medium size here), after which approximately quadratic behaviour is observed. The paper will review mitigating influences for this non-intuitive behaviour before concluding that none is really satisfactory. It then unites this complex behaviour in a simple mathematical model of the physiology of the human two-level memory system. The resulting component fault rate model accurately predicts the observed data for all languages in this study.

JavaDocs for those who hesitates to download it.

Since this seems to be a popular topic within the OOP thread, I thought I'd break it out on its own and toss in my $2e-2 worth.

Now, it seems that expressivity has something to do with how we use languages to solve problems. In particular, it seems to be a measure of how easy it is to write a solution to a problem in a given language. "Ease" is fairly nebulous to define, so let's try some simple-minded metrics as a starting point. I argue that compressed program length is a reasonable metric. A shorter program has fewer overall symbols to parse and comprehend. If the meaning of those symbols is very intricate and codependent, very terse code might be difficult to understand (like, say, sed/awk). However, nobody can argue that a short string of symbols with lots of meaning is lacking in *expressivity*. So ease of comprehension should not really be a factor in this measure.

Now, how do we use program length to measure expressivity? First, we need a problem set. Since a Turing machine is a solution to some problem, let us simply consider the set of all Turing machines whose length is less than or equal to N. Call this set P. Next, let us suppose that we have a magical function M, a given language L and a specific Turing machine T in P. M(L, T) gives us the compressed length of the smallest program in L that is equivalent to T. To determine the average expressivity of L, we simply take the average of M(L, T) / M(T, T) for all T in P. Let us call this value E(N).

I claim that E(N) is a reasonably objective metric for the expressivity of L. It measures how many symbols are needed to solve a given problem in L. Naturally, M is most likely undecidable, so we can't actually compute it. But I hope it's apparent that if we could at least *estimate* M to a high degree of confidence, that E(N) would be computable, and possibly even useful.

Wouter van Oortmerssen's thesis on Aardappel is a pretty fascinating read, and I like some of the concepts behind visual programming, but is it practical? is there any way VPL's will ever catch on?

While trying to learn the formal notation used in TAPL (and many other papers), I found this paper ... Syntactic Theories of Sequential COntrol and State by Matthias Felleisen. I didn't find this mentioned in any previous discussion on LTU (even though it is from 1992). This paper, as far as I can tell, seems to represent the same idea of TAPL notation in a much more concise manner. For example (horrible 'summary' follows), in Pierce's book (page 72), some rules are listed as follows:

Syntax:
t::= x | Lx.t | t t
v::= Lx.t

For t -> t'

t1 -> t1' | t1 t2 -> t1' t2 [E-APP1]
t2 -> t2' | v1 t2 -> v1 t2' [E-APP2]
(Lx.t12) v2 -> [x -> v2]t12 [EAPPABS]

According to Felleisen's paper, these rules could be written as:

For t -> t'

C[t] -> C[t']

If we extend the syntax with the following:
C::=[] | (e C) | (C e) | Lx.C

In other words, we don't have to have such verbose rules because 'C' can represent a 'hole' for a term or its reduction.

Ok, this is obviously not a summary of the paper but a question. Is my understanding correct? Is it of any value? I would think so, if one is trying to build 'executable' operational semantics. No?

by the way, I found this article through another paper on Operational Semantics for Scheme. This paper (I haven't attempted reading it yet) has further discussion of Felleisen's paper.

An interesting project.

Kont came out of an attempt to design a programming language in which every program was expressed in continuation-passing style. A concatenative language is a language in which programs are formed by the concatenation of smaller primitives, ala Forth.

On one (methodological) hand, objects are thought to represent "real-world entities". On the other (scientific?) hand, objects are mostly "gobs of recursion" (at least, in single-dispatch OOPLs).

Assuming you agree with the previous statements, when you read some code, how do you tell, whether specific object/class was created because the programmer needed "gobs of recursion" (dispatch via "this") or because he wanted to model a "real-world entity"? Should it be documented? Is it important at all? What is your experience? (mine is pretty limited as for some reason I always end up developing very abstract systems without any "real-world" meaning :-) )

I feel I should not post this to "objective scientific" thread.

What's your take on the GPL and GPL'd source code and how it affects the way businesses write code and make money from their intellectual investment?

I've read the comment that the GPL is considered by some to be 'boobytrapped', can anybody please explain this stance?