Archive for November, 2010

Odersky, Armstrong, Syme

November 26, 2010

There is an interesting video with a discussion of Odersky, Armstrong and Syme about programming language. My favorite part is by Armstrong around 3 minutes before the end of the video:

  • There should be smart repositories / version control systems that know about the language
  • Instead of optimizing your code of a solution to a problem, making the code unreadable in the process, write the solution in a (possibly solution-specific) high-level language, and then write a compiler for this high-level language that emits optimized code.

The second suggestion is basically what I will be doing with my next Android phone project by implementing large parts of it in Babel-17, and tweaking the Babel-17 compiler / interpreter to yield acceptable performance. The first suggestion I already had a lengthy discussion about with a former colleague of mine who thought that for example “git” is good enough as it is. “Git” is definitely great, but I also can imagine specialized repositories. For example in interactive theorem proving, a repository that knows about the structure of proven lemmata and so on would be immensely helpful to the user, I think.

Advertisements

Pragmas

November 22, 2010

Certain issues inevitably come up when programming:

  • How do I test my program?
  • How do I keep track of what my program is doing?
  • What system resources does my program gobble up?

To support dealing with these issues, Babel-17 has pragmas. Pragmas can be placed everywhere in a Babel-17 program where a statement could be placed, too. Currently there are three pragmas available:

#log expr

This logs a string representation of the value expr evaluates to.

#assert condition

This evaluates the condition and checks if the result is true. If not so, an assertion failure results.

#profile expr

This evaluates expr and profiles the evaluation. Right now just the time that the evaluation takes is measured, but of course more detailed information like memory consumption etc. would be nice.

The details of the execution of pragmas depend on the Babel-17 runtime environment the program is in. Usually, this environment should provide mechanisms to ignore pragmas or to customize them, for example in order to determine where the logging information goes, or if a failed assertion should stop the program and so on.

 

Response to Reviews

November 21, 2010

3 times “reject” and one “strong reject”. I braced myself for a negative result of submitting my paper “Purely Functional Structured Programming” to the ESOP 2011 conference, but this is way below any review score I have previously received for any of my papers. So what went wrong?

First, I clearly misunderstood the scope of the conference. On its conference site it says:

ESOP 2011 is the twentieth edition in this series and seeks contributions on all aspects of programming language research including, but not limited to, the following areas:

Programming paradigms and styles: functional programming, object-oriented programming, aspect-oriented programming, logic programming, constraint programming, extensible programming languages, domain-specific languages, synchronous and real-time programming languages.

They forgot to mention:

  • If you present an operational semantics, don’t make it too operational. DO NOT PROVIDE ANY WORKING CODE. If you do, it is great, but I, the reviewer, cannot be bothered to actually run the code to confirm that an example I am wondering about is correct. Even that last one on page 11 (EDIT: for n == 0, the result in the last example degenerates from a list of length 1 to an integer, so I guess I owe reviewer 1 an apology, if he/she was referring to this) .
  • If you present a new paradigm of coding, focus on the technical difficulties of this paradigm. If there are no major technical difficulties because the paradigm just works, invent new ones. Oh, it is blindingly obvious that Mini Babel-17 code can be easily transformed to pure Standard ML code, especially after the whole “shadowing” stuff? Not to me. Thats why I designate my confidence level as “Expert”.
  • If you have something important to say, say it in 20 pages, even if you could say it  in 12. You can fill up the remaining space easily with inference rules that have cryptic symbols above and below them.
  • Present a type system. If you cannot say what you want to say by dressing it up as a type system, better refrain from saying it in the first place.

Well, obviously, I have written the above lines in a frustrated state of mind. I should say that I am thankful to the reviewers for investing their time in reviewing my paper. And I am. Clearly the paper has failed to communicate what it is all about. It is not about the technical difficulties on how to hide mutable state inside functions that are pure when watched from the outside. It is not about presenting an alternative way to Haskell monads when dealing with mutable state. It is about how I can easily and naturally use “For” and “While” loops in a purely functional setting in those cases where I feel that these loops are the best way to express my intent. It is about how


let
val a = ....
in
let
val b = ...
in
...
end
end

is clearly less readable than


val a = ...
val b = ...
...

It is about how the inventors of Scala clearly understood this, but failed to recognize that then


val a = ...
val a = ...
...

should be allowed too (via the correspondence to let-constructs). And it is about how this seems to be a minor issue, but that this minor issue prohibits the language design to get the integration of loops with purely functional programming right.

Anyway. Words are cheap. Back to coding again. A full implementation of Babel-17 v0.21 is close.

Reviews for “Purely Functional Structured Programming”

November 21, 2010

—————————- REVIEW 1 ————————–

PAPER: 11

TITLE: Purely functional structured programming

 

OVERALL RATING: -2 (reject)

REVIEWER’S CONFIDENCE: 4 (expert)

 

The author proposes a way of combining “purely functional” programming

and “structured” programming. The term “purely functional” is used in

the conventional sense. “Structured” programming means imperative

programming with assignable variables and blocks such as while loops,

conditional statements etc.

 

The main idea of the paper is to add assignable variables to a

functional language, in a different way from the established Haskell

approach of using a monad. The technical idea proposed in the paper is

“linear scope”, and it is explained in the setting of the author’s

language Babel-17; actually in a cut-down version called Mini

Babel-17. A nice feature of the paper is that an interpreter for Mini

Babel-17 is available on the web, and this enables the examples in the

paper (and others) to be tested.

 

Here is the key idea, as I understand it. Variables are introduced

with what looks rather like an ML-style let-binding, e.g. val x = 1. A

variable can be updated by an assignment like x = x + 1, etc. I think

what is going on here is that the initial val declaration introduces

an ML-style reference cell; subsequent occurrences of x are implicitly

dereferenced unless they are on the left hand side of an

assignment. So, because of the implicit dereferences, it is not

possible to use the reference cell itself as a value.

 

There is a further refinement, which justifies the statement that we

still have purely functional programming. The section of code within

which a variable such as x can be referred to, with the implicit

dereference, is called the “linear scope” of x; it is a subset of the

standard lexical scope of x. But the linear scope does not extend into

lambda-expressions within the lexical scope. This means that a

function cannot have behaviour that depends on a reference cell

defined outside the function. It is possible for a function to create

reference cells internally, but because the cell is not available as a

first-class value, these internal reference cells cannot escape.

 

The idea that a function can use reference cells internally but remain

a true function (in the sense of referential transparency) is not new,

I think; for example it can be found informally in Section 8.2 of “ML

for the Working Programmer”.

 

The paper presents a few examples, and gives what it calls an

operational semantics of Mini Babel-17; what is actually presented is

the source code, in Standard ML, of an interpreter for Mini Babel-17.

 

The author claims that this integration of structured and purely

functional programming is an attractive alternative to Haskell’s

approach of using a monad to encapsulate mutable state.

 

So, that’s my understanding of the technical content. Now for my

assessment.

 

I am not sure how original the idea is in a conceptual sense. It is

interesting as part of a complete language design. But I don’t think

there is enough here for an ESOP paper. My summary above is quite

short but I think it captures the whole of the paper; I don’t think it

would be possible to summarise a typical ESOP paper so briefly. The

paper itself is fairly short, indicating that the technical content is

rather light.

 

The operational semantics doesn’t have the usual form for papers in

this area, i.e. a reduction relation defined by inference rules.

 

The paper doesn’t present any technical results. What would I expect

to see? My summary above suggests that Mini Babel-17 can be translated

into ML, so one possibility would be to present a translation; this

could serve directly as a semantics or could complement a more formal

operational semantics. I also mentioned above that a key idea of the

paper seems to be that mutable references can be used, without

producing impure functions, if references are always local to

functions and cannot escape. It should be possible to prove a result

along those lines, although I am not sure how original it would be;

maybe it is just folklore (as suggested by the reference to Paulson’s

book).

 

It would also be interesting to give a more thorough comparison with

the Haskell approach.

 

The paper is well written and quite easy to follow. I think there is a

small problem with the final example on page 11. The text states that

the function returns a list, but the function body seems to return an

integer.

 

As I said earlier, the availability of a working interpreter for the

language is admirable and was very helpful in understanding the

examples.

 

In summary, I am not sure there is an ESOP paper here even if the

technical details are formalised and some results proved. But I could

imagine this material appearing as part of a longer paper on the

design of Babel-17.

 

I do not have any specific questions for the rebuttal phase.

 

 

 

—————————- REVIEW 2 ————————–

PAPER: 11

TITLE: Purely functional structured programming

 

OVERALL RATING: -3 (strong reject)

REVIEWER’S CONFIDENCE: 4 (expert)

 

This paper claims to “make structured programming in integral part of

purely functional programming”.  What it actually does, as far as I

can tell, is to identify an idiom that one could follow in an ML

language, or in Haskell with a state monad, in which one refrains from

mutating a reference cell except top-level linearly sequenced control

flow (but not in the arguments of a binary operator, for example).  It

does this with a notion of “linear scope”, and the author correctly

writes “Maybe the rules of linear scope sound confusing at first”.

The simple relation between the syntactic structure of programs and

conventional static scoping is not something to be given up lightly.

 

If there really is something here, then perhaps it could be better

captured by identifying whatever reasoning principles are enabled by

that idiom.

 

 

 

—————————- REVIEW 3 ————————–

PAPER: 11

TITLE: Purely functional structured programming

 

OVERALL RATING: -2 (reject)

REVIEWER’S CONFIDENCE: 4 (expert)

 

The paper has serious flaws in the following three main categories.

 

1. Motivation and relevance

 

We read in the introduction that purely functional programming (PFP) is

becoming popular because pure expressions lack ‘side-effects’, mutable state,

etc, and are therefore ‘straightforward’ to turn into parallel executable

code. That PFP is popular only within niche communities such as theorem

proving. That today’s popular programming paradigm is structured programming

(SP), defined simply as programming with if-branches and while-loops

[imperative programming, one guesses]. That PFP rejects SP because it smells

of side effects, destructive updates, and mutable state.

 

Linear scope [to be discussed in point 2 of this review] is proposed as a way

to marry PFP and SP. PFP would become more mainstream if it looked more like

SP, and linear scope is the paper’s proposed means to achieve this goal.  The

toy language Mini Babel-17 is introduced to illustrate the workings of linear

scope.

 

Let’s begin by pointing out that ‘side-effects’ are undesirable in any

language. ‘Effects’, on the contrary, are not only desirable but unavoidable.

The growing popularity of purely functional programming languages such as

Haskell are due to the principled integration of purity and effects which yet

remain separated *by type*, helping compilers optimise pure and effectful

code and exploit their suitability for parallelism accordingly—a task

that’s anything but ‘straightforward’. I emphasise the word *type* because,

as we learn on Section 3, linear scope is presented in a dynamically typed

example-language of which we are not given the type expressions nor the type

rules, only informal descriptions of behaviour like that at the end of page

7. If linear scope and mini-Babel-17 were what we want for PFP, the reader

cannot tell if they’d be suitable for parallelism which was the main reason

for propping PFP. Wouldn’t the dependency of a variable on the place on which

it is defined complicate optimisations? [see below] When introducing a

feature into a language, one must study the consequences on the rest of the

language.

 

Impure functional languages exist, and they have imperative features. As the

author points out, ML has a while keyword that, he complains, is rarely

used. Perhaps the reason is that one can program alternatively, and much

better, without it. The purpose of monads is not only to deal with effects.

And monads should be learnt for many reasons. I don’t understand why we

should have to avoid knowing them, this purporting to be one of the

advantages of using linear scoping, as stated in the abstract.

 

(Also in the abstract: ‘a second advantage is that professional purely

functional programmers can often avoid hard to read functional code by using

structured programming syntax that is often easier to parse mentally’. I take

that professional functional programmers can parse mentally functional code

much better than imperative code. The ‘benefit’ would be for imperative

programmers to think they’re still doing Pascal.)

 

The most popular programming paradigm today is not SP but OOP, of which

Scala, a language cited by the author, is an example.

 

PFP does not reject SP. Functional programs have structure, only that the

notion of computation is based on function application. If-branches are common

in PFP and defining while-loops in a pure setting, even without monads, is a

textbook exercise. The author knows this for he provides a ‘semantics’ of his

mini-Babel language in ML.

 

Whether PFP becomes more mainstream or not will depend, among other things,

on its advantages and on various other social issues. But the point of PFP is

to liberate programming from the Von Neumann (imperative) style. Going back

to it would not benefit ‘professional purely functional programmers’ who

don’t need it. It wouldn’t benefit imperative or OO programmers wishing to

learn PFP either. They’d have the impression that they’re still programming

imperatively. Types, first-class functions, higher-order functions, powerful

abstractions, computation by means of function application and composition.

That’s what PFP is about.

 

 

2. Contribution

 

Linear scope is the rediscovery that a restricted form of mutable variable

can be obtained by nesting scopes or variable renaming appearing on l-value

position. Take the last example in Section 2:

 

(x : Int) => { var y = x*x

val h = () => y

y = y * y

h() * y }

 

This function implements \x.x^8 but, according to the author, with

‘shadowing’ it should implement \x.x^6. But shadowing involves a

re-declaration.  Where’s the redeclaration of ‘y’? Are we to take ‘y = y*y’

as a re-declaration? Despite the missing ‘var’ keyword, we should, according

to the author. A new ‘y’ enters the picture but h()’s ‘y’ refers to the one

defined before the function. Thus, the position of a function matters, move h

down and it’s meaning changes, a side effect.

 

However, use renaming and we get what we want without side-effects:

 

(x : Int) => { val y = x*x

val h = () => y

val z = y * y

h() * z }

 

In fact, the author could argue at this point that he’s not after mutable

variables, in which case h’s body would refer to the ‘y’ in scope, the one

just mutated, delivering x^8 as well. Mutable and immutable variables are

separated in Scala for very good reasons—one taking us back to the

separation between purity and effects code touted in the paper’s

introduction. ‘Successfully married’, says the abstract, indeed, thanks to

separation. Global scope for global variables means they can be placed

anywhere in the code. Being immutable, they stand for values and expressions

using them are still pure.

 

Could linear scope be implemented by means of renaming of variables as in the

above example. The author should address this question.

 

Section 2 is confused on the sales pitch. Shadowing is *not* wrong in PFP,

it’s very well supported, and variables are not state, for a state is meant

to mutate. The main issue is not shadowing or programming with if-branches,

or while-loops.  Linear scope is concerned only with assignment, in giving

the impression or mutation by means of nesting new scopes.  But, as the

purported semantics in Section 6 show, the meaning of linear scope requires

mutable environments (middle of page 8). One can simulate assignment by

moving the change of state (variable renaming) to the environment.

 

That ‘shadowing is purely functional’ (Sec 3, p3) is well known since the

lambda-calculus (e.g., \x.\x.x). What linear scope is doing is not your purely

functional shadowing. The paper’s imperative semantics also illustrate that.

 

 

3. Written style

 

Despite it’s intended tutorial style, the paper is poorly written regarding

structure, aims, contributions, etc. Most of it is devoted to the syntax and

so-called semantics of Mini Babel 17, after a cursory description (via

examples) of linear scope which is the main contribution. Related work is

poorly discussed. Describing the semantics of linear scope monadically would

be a good exercise. Also, the rough corners should be addressed in more

detail: the interaction between a linear scope and regular scope, whence

those ‘x = x’ strange declarations (Sec.5, middle paragraph) and the seeming

non-determinism (list of values, Sec.6, page 7), etc.

 

 

 

—————————- REVIEW 4 ————————–

PAPER: 11

TITLE: Purely functional structured programming

 

OVERALL RATING: -2 (reject)

REVIEWER’S CONFIDENCE: 3 (high)

 

The paper presents the initial design of a programming language combining features of pure functional languages and imperative programming languages. After introducing the notion of linear scope, a mechanism which limits the imperative use of variables, an interpreter for a small core language is presented.

 

I like the general intent of the paper, namely to enable the use of familiar imperative

constructs within a functional languages in the syntax that an imperative programmer is familiar with.

However, I have several reservations on presentation and contents.

 

I found the discussion on shadowing quite confusing. I would have expected the discussion to concentrate on whether a variable can be used in an imperative way or not, rather than on the mechanism with which a variable already in scope can be shadowed by another variable declaration with the same name. I would keep shadowing as a side comment, that variables can be re-bound and transformed from non-linear to linear.

For terminology, I would rather use “imperative scope” than “linear scope”, also to avoid possible confusion with the same notion used in the context of linear types.

 

When reading the paper, I felt that it stopped suddenly at the end of section 7, leaving the reader hanging.

I would have expected some form of evaluation of the design choices, and a more in-depth analysis

of the properties of the language. For example, I would expect that some sort of equational reasoning

is supported by the language, since the imperative features seem encapsulated inside blocks of instructions.

 

In terms of presentation, I was initially confused by the fact that the interpreter is written

using mutable state inside linear environments, and it took me a while to realise that eval_e can in

fact modify the environment despite its type. While I liked the concreteness of presenting the

semantics as an interpreter, I think that some separate formalisation of linear scope would help the reader

grasp the concept without having to understand the details of the interpreter. Also, I feel that the

well-formedness criterion on p.10 could be made more readable by presenting it as an ordinary

type system with inference rules.

 

Where are programming languages going?

November 19, 2010

I found this talk of one of my all-time heroes, Anders Hejlsberg. Turbo Pascal was my second programming language after QBasic, and therefore it is great seeing him firing up Turbo Pascal in the beginning of this video 🙂 Takes me back 17 years. Here is the link.

In this video, I especially like his conclusion that the evolution of PL lies in the intersection of declarative languages, concurrency, and dynamic languages. Actually, I hope that I can develop Babel-17 to conquer the very heart of this intersection. In the end he says, expect it to happen, but not too fast, because we programming language designers are a slow bunch. Yep, I totally agree. It will have taken me about 1.5 years to advance Babel-17 from the first prototype implementation in 2009 to the more refined language that Babel-17 will be at the end of 2010. A big part of this refinement is “purely functional structured programming”. Even Anders Hejlsberg distinguished between imperative and functional programming by the possibility of something like “x = x + 1” as opposed to “y = x + 1” in imperative languages. Clearly he should know better and must know in the back of his head that the only difference is shadowing. Spelling this out explicitly in my pfsp paper has helped me enormously to give Babel-17 a simple yet very powerful core that does not represent the end, but the beginning of the line of development of Babel-17.

Babel-17 for Android

November 18, 2010

Development of Babel-17 will proceed at a much better pace from December on. I have aligned two interests of mine and will develop the Android port of an iPhone app in Babel-17! As Android effectively runs Java, it should be easy to get the Babel-17 reference implementation running on Android. Because the Android port is a big project (is has taken me about 4 months to develop the iPhone app), Babel-17 should have a very mature reference implementation after the port has been done. I will add features to Babel-17 on an as-needed basis. Of course I won’t get away with the “purely functional” approach entirely, as this is a real-world app with lots of state. But this state should be encapsulated in and confined by suitable abstractions, so that about 90% of the final program is purely functional, and 5% deals with state, and another 5% is just pure magic 🙂 The Android port should be done faster this way, not slower, because I know already a lot about what kind of abstractions I need from the original iPhone app. I can support these abstractions directly in Babel-17 (for example in a “Babel-17 for mobile” extension), so the actual code I am writing will be concise and elegant and, very importantly, short. And of course, it will be so much fun that I have no problem to continuously work for 3 months on it, which should yield much higher productivity than just coding the Android port in Java, which would inevitably lead to at least 50% downtime because of Java boredom (I have seen this with the iPhone app and Objective-C boredom… This could have been done in two months instead of four…). Can’t wait to put the finishing touches on the iPhone client and start with the Android one 🙂

Design without Designers

November 18, 2010

I just read this article, Design without Designers, and I totally agree with it.

And here is an interesting video about how you have to abandon crap in order to be creative. It is actually part two of a series of videos, which all seem to be interesting.

Well, and here is why you should go for purely functional whereever you can, at least if you care about simple and efficient parallel programming: Mindblowing Python GIL. It also is a partial answer to the question “What about Python?”, which regularly comes up when I start explaining why I need Babel-17.

Lists

November 11, 2010

In statically typed functional languages, the type of lists is typically recursively defined to consist of the empty list, or of some value (the head of the list) consed to another list (the tail of the list).

So, if we write “::” for the consing operator, and “[]” for the empty list, then for example 4::[] is the list consisting of only one element, which is 4. Similarly, we can have a list 1::2::3::4::[], which consists of 4 elements.

Something like 1::2 is not a valid list in statically typed languages, because 2 is not a list. So rather than write 1::2, you have to write 1::2::[].

To just blindly mimic this behavior of lists in Babel-17 causes problems. In Babel-17, two issues combine to make conventional lists problematic:

  1. We can have lazy and concurrent lists, for example 1::lazy(2::[]) or 1::concurrent(2::[]).
  2. An expression should always have one deterministic value.

Now look at the following code:

val x = 1::lazy(2)
x.head

Which value has “x” ? And which value is returned by above block? If we mimic how lists usually behave, then the evaluation of 1::lazy(2) should lead to a dynamic exception, because 1::2 is not a proper list. This means that the above block also evaluates to a dynamic exception. But in order to determine that 1::lazy 2 is not a proper list, we need to defy the purpose of the lazy attribute! This is not problematic if the argument of lazy is just 2. But if the argument of lazy is some complicated expression that takes a minute to evaluate, then it becomes problematic.

Therefore, in Babel-17, we need to allow that 1::2 is a valid list. Then the above block simply evaluates to 1.

To make this work smoothly, we furthermore identify 1::2 and 1::2::[]. Therefore, the value of

(1::2).tail

is not 2, but 2::[].

Division and Modulo in Babel-17

November 11, 2010

The upcoming Babel-17 v0.21 will only know integer numbers, no real numbers; but  real numbers in form of interval arithmetic will be part of the next version of Babel-17.

Therefore, what should for example


7/4

evaluate to? Because Babel-17 currently only has integers, the result 1 seems to make sense. But factoring in the fact that eventually, there will be real numbers in Babel-17, this could be a major source of confusion, because the similar expression


7.0/4.0

would not evaluate to 1, but to 1.75 .

Therefore two new binary operators are introduced in Babel-17, “div” and “mod” which will denote euclidean division and modulo operations. Therefore the following will evaluate to true in later versions of Babel-17:


7 / 4 == 7.0 / 4.0 == 7 / 4.0 == 7.0 / 4 == 1.75  &

7 div 4 == 1 & 7 mod 4 == 3

In Babel-17 v0.21, u/v will always result in a DomainError for integers u and v.
The operator “%” will vanish. Its function is taken over by the new operator “mod”.

Books on Sound

November 11, 2010

Feynman was the right place to start. So, sound is just variation of air pressure, where normally (except in special cases like explosions) the magnitude of the variation is tiny compared to the ambient air pressure. From there, I found the following  very useful and interesting books (I only give the names, google them for details):

  • Real Sound Synthesis for Interactive Applications
  • Musimathics (Volume I, II)
  • A Digital Signal Processing Primer

These books seem to cover most of the state of the art of what interests me in sound. It seems to me that there is big potential in making the knowledge in these books available in the form of a sound programming language. This sound programming language could be built on top of Babel-17, or maybe just be a library for Babel-17 with possible improvements of Babel-17 to make the integration as smooth as possible. So I have two side projects now: finishing Babel-17 v0.21, and working through above pile of literature.