Lambda the Ultimate

Thank you very much for your comments, they are invaluable to me.

The docs you have online are long and mostly generic. I think you'll get more people to read about your language and give feedback if you write up a short description of what parts are actually different and why it's better than existing languages.

That's an excellent point. The problem for me was prioritizing: there's no single feature or maybe two that I would wish to emphasize and separate to draw the interest. I'll try to do what you suggest anyway; maybe the main doc with language description should be called 'Tutorial', and 'Getting Started' should be just a brief description of the main features with a few examples?

One is that conditionals are expressed as "nil" vs failure. What are the advantages of doing this over using Boolean values?
That's a good question.
First, programs consist of computations, right? Any computation can fail for whatever reason; when it fails, its output is invalid. Therefore, a computation always has an implicit 'Boolean' side result (success/failure). That's why I decided that having an explicit Boolean data type is a redundancy.
Moreover, I always thought that the Boolean data type is sort of artificial in the way it stands above all other data types (I'm not talking about languages where bool is just a case of integer).
Finally, regarding 'nil'. In cases when we are interested in the success/failure result only, it doesn't matter what value the expression returns, so we make it return 'nil'. Note that statements, unlike expressions, don't have to return anything.

The second is that it looks like the "world state" is explicitly threaded through the I/O functions.

There's no 'world state'. The 'state' I meant was the state of the application's variables. Large applications are divided into a number of smaller 'applications' (see "GUI Embedding"), each with its own state. So, I imagine any large application as multi-threaded, where each thread corresponds to a sub-application and holds its state. Did I explain clearly enough?

Have a look at ICON and UnIcon for a more complete investigation of the success/failure of a computation.

If a computation is successful then a result is returned (usually the RHS of the operation) otherwise failure. this means that the following is valid

A > B > C returns the Value of C if it succeeds otherwise failure if A

Returning nil is not generally useful as a result of computation unless you really don't care about the value. If on the other hand, you do care about the value then on success it is better to return a value.

Icon has been around since the mid 80's

regards

Are there any other reasons why I have to follow Icon's design, except that it's been around since 80's?

I don't think the interpretation of A > B > C you gave is very intuitive and/or close to the mathematical interpretation. In Aha!, the syntax is much more restrictive, which is good. The less ambiguousness, the better, in my opinion.

Returning nil is not generally useful as a result of computation unless you really don't care about the value. If on the other hand, you do care about the value then on success it is better to return a value.

That's exactly what I said. 'nil' is returned only when you don't care about the value, only care about the success/failure result. In Aha! 'nil' is not just a special value, it's a separate data type, and the language is statically typed. This means, you know in advance that an expression returns 'nil' (unless it fails) and not any other value.

Mathematically, one would look at a > b > c as being the relationship between a, b and c. Seems obvious that you are expecting a to greater than b and that b will be greater than c.

Failure is an indication that the computation has not successfully returned or completed. To have the result of the computation being successful as being nil seems to be relatively pointless. I would have expected that if it is performing a calculation, then the value of the calculation is probably useful.

One of the aspects of Icon with its success/failure regime is that it is applied mostly uniformly across all areas of the language. It applies in tests such as if and while, in function and procedure calls, in function returns, in calculations and assignments.

What it boils down to is that you appear to be making the conditional a special case, instead of applying the principle of uniformity across all of your language.

My question would then be, why bother doing this instead of using true and false? It seems to only fragment your language with special cases.

My first introduction to Icon was many years ago. From first picking up the langauage introduction to completely rewriting an existing system (that had taken 6 to 8 weeks to write and was having major problems with continual input file changes - it analysed log files) was 3 days. I found that the basic principles used throughout the Icon language and the uniformity of the language went a long way to making the translation process a success.

I personally find that languages that have special cases tend to make it more difficult to write clear and concise programs. YMMV.

One final point, if nil is being returned for a conditional value, what would be the result of


if (A > B and B > C) or (C > D and D > E) then
...


does this become

(nil and nil) or (nil and nil)

=== nil

or


A := (B > C) and (D > E)


does this become


A := nil and nil


and then


A := nil


Failure is an indication that the computation has not successfully returned or completed.

My interpretation: failure is an indication that the condition expressed by the statement doesn't hold. In particular, if the statement is an assignment (definition), like z = x / y, and y = 0, we can't ensure that statement's goal and therefore it fails. Similarly, when x < y, we can't ensure the statement (x > y)? and it fails too. The only difference between these two cases is that the second statement doesn't produce any output.

To have the result of the computation being successful as being nil seems to be relatively pointless. I would have expected that if it is performing a calculation, then the value of the calculation is probably useful.

You may have noticed that I avoid using the term 'result' and use 'output' instead. In fact, any computation in Aha! has the success/failure result, but its output may be zero, one, or more (if it's a complex statement) values. This is completely 'uniform' - unless you believe that zero is a number of a different kind than other numbers.

Unlike a statement, an expression must return some value - again, from the 'uniformity' requirement. Since the success/failure result already
has a 'Boolean' meaning, I didn't want to introduce another Boolean value. 'nil' was chosen because it's completely neutral. I consider 'nil' a particular case of a composite (record, structure) that has no fields.

I was familiar with Icon before starting my design, and even borrowed the idea of success/failure result from it. I didn't like its other solutions though.

If you look carefully at Aha!, you'll find more uniformity in it than in any other language.

One final point, if nil is being returned for a conditional value, what would be the result of

if (A > B and B > C) or (C > D and D > E) then
...
does this become
(nil and nil) or (nil and nil)
=== nil

Aha's syntax and semantics are completely different, if you have noticed. To check for the above condition you would have to write something like

any
  all (A > B)? (B > C)? end 
  all (C > D)? (D > E)? end
end

This is a statement (with no outputs) and not an expression. The 'nil' output of each conditional is ignored (due to the question marks). Remember the expression 'statement logic' in the Getting Started guide? This is an example of it.

Speaking of the second example... Hmmm... We could introduce the Boolean data type as a user-defined type if we wanted to. However, I have a feeling that with the declarative style of programming, in most cases the Boolean type can (and should) be avoided.

I don't really understand why you don't have a proper Boolean type. How do you represent a pair of Boolean values in Aha!? (That last sentence ends with 'Aha!' followed by a question mark, not 'Aha' followed by a bewilderment mark. I'm sure you can look forward to plenty of such confusion with this name.) How would you define 'r = (not p) or q'?

Why not just have have the question mark operator take a proper Boolean value (true | false) and convert it to a statement, succeeding only on true?

... I know how to define 'r = (not p) or q' in Aha!

to provide a parallel classic boolean operator set? If we want to define some shorter constructs? Although there can be a place for existential and universal operators.

Please read the last paragraph of my previous comment. I will introduce a user-defined Boolean data type into the Base Library once I see that it's necessary. I'm not convinced so far. Aha! is different to what you've seen before; it may be its weakness or strength, I don't know yet.
PS. I forgot to mention that Aha! Base Library already contains module Bits for bit/bitstring manipulation (see Wiki on my site). With it, Boolean expressions can be written pretty much in the standard way, e.g.: (((~not P) | Q) & R) (where P, Q and R are bit strings of length 1).

I sympathize with your approach to booleans.

For dodo, since the base language uses continuation-passing style I am using a shortcut:

if (a > b) 1 else 2

is transformed into:

(a > b) ->
  1
|
  2;

where 1 is the first continuation passed to the ">" operator, and 2 is the second continuation. There can be a third continuation for exceptions.

Comparison operators therefore return nothing, they just chose a continuation.

Note that getting a boolean value out of such an operator is easy: just replace 1 and 2 with true and false.

Dodo does have the boolean type, which is defined as a set type which can contain up to one value. True is {0}, false is {}. When representing the set as a bitset, this gives true = 1 and false = 0.

Logical operators || (union), && (intersection), ^^ (symetrical difference) and ! (complement) can be applied to boolean values and to other sets.

Is a bool type really necessary? I'm rather fond of Harper's suggestion to distinguish propositions from values. I went through a lot of my code and noticed that his allegation was correct: the interfaces would be much nicer if function parameters didn't have bools, but instead had algebraic types. The signature is then truly self-documenting.

This isn't easy enough to do in every language I know of since such parameters would require numerous explicit type declarations, so I'd love to see a language that makes this easy (anonymous/inline sums perhaps).

The right question is whether Booleans are really useful. What should the type of filter be? Should we use the following instead?

mapAndFilter::[a] -> (a -> Maybe a) -> [a]

In general, I agree with the point that a Boolean acting as a guard on data is occasionally best rewritten with algebraic types. But I'm suspicious of the trend to encode more and more complicated things with algebraic types. I think the costs quickly outweigh the benefits. IMO programs should be written in the most straightforward way possible, not in the way that makes proof as straightforward as possible.

I wasn't thinking in terms of proof, I was thinking in terms of self-documenting code. Any bool parameter absolutely requires the developer to consult the docs accompanying the code, possibly breaking their workflow. This is ameliorated somewhat if named parameters are available. By contrast, an inline anonymous sum could have self-descriptive names. This helps in all sorts of other ways too, like intellisense.

The benefits for proofs are purely incidental in my mind.

Edit: using maybe for mapAndFilter is possible, or just using an inline sum:

mapAndFilter::[a] -> (a -> Include | Exclude) -> [a]

An advantage of Boolean over an ad hoc Include | Exclude is that you don't have to recode operations. For example, given a list of Booleans you probably have a function 'all' laying around that will tell you if they're all true.

I thought you were endorsing a rather more substantial change, which I understood to be advocated in the Harper reference you gave, where Booleans are structurally tied to what you can do when they're true/false. For example, consider a red black tree. You can implement that as a type Node, accompanied by red/black tags (whether Booleans or Red|Black). Or, you can have RedNode and BlackNode and attempt to structurally enforce the properties of your tree by construction. I'm of the opinion that this latter approach is probably an anti-pattern, and what we should instead be doing is making it easier to layer additional structure on top of simple Trees. Incidentally, this is the same direction I would suggest for your ADT encoding -- use new tags, but import the structure of Booleans.

An advantage of Boolean over an ad hoc Include | Exclude is that you don't have to recode operations. For example, given a list of Booleans you probably have a function 'all' laying around that will tell you if they're all true.

I'd first have to establish the semantic meaning of a list of booleans. This is exactly the sort of use of bool that doesn't seem like a good idea. I don't question that it's sometimes convenient to do so when first writing the program, it's just semantically opaque to anyone reading it (yourself included!).

Regarding the more substantial structural change, I think there's a spectrum of design points. I have no opinion whether going all the way to Harper's world is good, but I do think going at least part way makes programs clearer and more self-documenting.

With the red/black tree example, I think using a variant type for the node color is far better than using a Boolean. Similarly to Boolean parameters, Boolean tags have no bearing as to what true or false means: red or black, so it must be documented somewhere (and I prefer self-documenting code, even though Aha! requires documenting each entry in a module's spec). With Aha's variant types, we could introduce a type NodeColor: ( red: nil | black: nil ) and to check of what color a node is, we could then write node.red? or node.black? and this would be it. In addition, if we later decide that the tree nodes can have more colors than two, we would simply extend the NodeColor type definition.

Sounds reasonable, but I think "far better" is far exaggerated. I agree your use of red? and black? seems to be a nice idiom, though, and it's your bikeshed :).

Regarding your decision to put Aha! Booleans in the standard library, doesn't that make for poor interoperability with other operators (like greater than) that succeed or fail rather than returning a boolean?

Regarding your decision to put Aha! Booleans in the standard library, doesn't that make for poor interoperability with other operators (like greater than) that succeed or fail rather than returning a boolean?

Not at all. Bit string expressions return bit strings, and to actually verify if a bit string represents 'true', one needs to write (b = True)?

If I understand, that doesn't let you write:

p = (x>10) and (y<100)

No, you'd have to write something like

unless
  let p = True where all (x > 10)? (y < 100)? end end
then
  p = False
end

This doesn't look nice, but it's only because you insisted on using Booleans :)

Right, so that's what we lose in the bargain. I'm trying to understand what we gained, specifically in comparison to the alternative I mentioned earlier, where (x > 10) returns a Boolean, and (x > 10)? succeeds (or is a true statement, or whatever your terminology is) when that Boolean is true.

Or is your position "booleans considered harmful" so that a little bondage is a good thing here?

If (x > 10) returned a Boolean, what its value would be? 'true' on success and 'false' on failure? Which means that 'false' would never have been returned, because failure means the output is ignored. Then what the difference would be between Boolean and 'nil'?

My point is, it doesn't matter what a conditional returns, because we only look at its success/failure result (which is not considered 'data' in Aha! and therefore has no data type).

The question 'what we gained' is tricky. Let's say now that we can't see what we gained on such small examples, taken out from the context. It's like asking, what did we gain by installing traffic lights everywhere - they only make me go slower!

I'm asking why not have (x > 10) always succeed and return Boolean data. If you want to fail on False, then you use a guard operator to convert that data to failure. I'm not sure about your analogy, since the purpose of traffic lights is pretty easy to explain.

Well, that's a possible solution. The condition validation then would look something like: (~true (x > 10))?

I'm not against Booleans in general, I'm against using them as a special "super-type" - the only type that conditional statements and loops understand immediately. Traditionally, a Boolean value serves as a proxy: first we compute it, and then a statement analyses if it's true and makes its decision based on it. My approach is to consider statements as entities with an implicit logical value (success/failure) and build the statement logic based on that value, without any proxy data type.

I agree, my analogy wasn't good. I had stronger metaphors in my mind, but decided to hold them in for the time being.

This looks like an efficiency-conscious choice that is related to the work on Multi-Return Function Call (Shivers and Fisher, 2004), which you may be interested in.

The link to the paper no longer works.

Looking at the discussion though, isn't it exactly what I talked about: a different continuation for each branch? My project at http://dodo.sf.net does that.

I think this is a reasonable alternative. You still use the success / failure model in branches and loops, but by leaving out the question mark you can get a Boolean value out of the expression.

Does Roman object to that?

I'll think about it.

No, sorry, I'm not convinced yet that I need to change the design of Aha!. It still looks perfect to me, even if some people don't like it or just want to use Booleans.

After thinking on the nil vs Boolean issue, I realized that the confusion here is caused by the word 'nil'. 'nil' is traditionally associated with failure, lack of value or invalidity of something. In Aha!, nil is a totally legitimate (only irrelevant) value that can be returned from a function only when it succeeds and has therefore a positive meaning.

To resolve the issue, I would suggest to change the word 'nil' in Aha! to something more positive, something that could be distinguished from 'no value', while remaining totally neutral. Any suggestions?

You're right about that, a value returned for success should not be named 'nil.' That violates programmer cultural expectations and the 'principle of least surprise.'

It could, however, very reasonably be named 'success'.

In various languages I have seen boolean 'true/false', logistic 'true/false/paradox/uncertain'('paradox' indicating contradictory evidence or inconsistent rules, and 'uncertain' indicating insufficient or irrelevant evidence), 'yes/no' as aliases to booleans used in directive contexts (ie, in response to a query about whether a given action is requested or not), 'success/failure' for responses indicating whether something succeeded, and 'success/failure/pending' with 'pending' being a thread handle/promise that would eventually turn into a 'success' or 'failure'. If you cared which, you needed to store a reference to the 'pending' value, and check back later.

'nil' has been used for no-value, or the-empty-list, or the-empty-collection, or false, or an error value, or failure. Never, AFAIK, for success.

I prefer 'nil' as a no-value, distinguished from both 'false' and 'empty-set'. The empty-set, under this reading, is something that returns 'nil' if you ask for one of its elements. Also, under this reading you can't store 'nil' in a collection.

Older lisp dialects treated nil, false, and the empty list as synonyms, and even today most dialects treat nil and the empty list as the same. Clojure at least gets this one right.

Bear

Thanks, I think 'success' would do for the value instead of 'nil', but how about the data type of it? The name should indicate that the value bears no useful information - that's what I mean by 'neutral'.

How about just 'done', or http's successful response code 'ok', or a TCP-like 'ack'?

If it bears no useful information, then why are you returning a value at all? One needn't report success unless failure is possibile.

First, any function that succeeds must return a value. In some cases, we are not interested in the actual value, but in the fact that the function succeeded. That's why I decided to use the nil datatype for the return value in such cases.

I consider 'nil' a particular case of a composite (record, structure) that has no fields. It is NOT a zero-length array/list, or an invalid pointer (Aha! doesn't have pointers), or an undefined value (Aha! doesn't permit such values). 'nil' can be used, for example, to define enumeration types as variant composites, like:

type PieceColor: ( white: nil | black: nil )

Similarly, 'nil' can be used to introduce 'nullable' data types:

arbitrary Value "base data type"
type Nullable: ( value: Value | novalue: nil )

I wish to emphasize that in Aha!, as described in the Language Reference Draft 1, 'nil' refers to both the zero-field composite data type and its only value.

Thank you for all the suggestions about a better name for 'nil'. I assume that the names 'success', 'done' apply to the value and 'unit' applies to the data type. Correct?

One needn't report success unless failure is possibile.

I think that we must always assume that failure is possible if we care about the correctness of the program. Whenever the program may not return the correct/expected value(s), it must fail. It is a huge mistake to assume that if a program failed then it's incorrect; on the opposite, it is an incorrect program that didn't fail but returned incorrect values.

In Aha!, we consider failure a normal and expected result of any computation. It's not like a fatal exception, it's just a signal that the program or its part didn't achieve its goal (or, alternatively, that some precondition doesn't hold).

How about unit (one value) or void (no information)?

Another way to handle this issue is by introducing a 'global' variable, say 'Ok', defined as:

Ok = nil

That's all, no language changes are needed! Given this definition, when defining a function that merely checks a condition, we just return 'Ok' instead of the literal 'nil' when the condition holds. This makes the code look more intuitive, while semantically it's the same as when just using nil. For example:

isPositive = { x: integer -> get Ok where (x > 0)? end }

defines function isPositive that succeeds when its argument is positive and fails when it's not.

Algebraic types in Aha! are called variant composite types. Functions and object actions (or methods) with parameters of such types are easy to declare and use. See for example the spec of module StrUtils. It contains function Search with a composite parameter of type SearchParams (you don't have to declare the type of a parameter unless you want to use it multiple times). This type has two fields: 'for' and 'in'. 'for' is a variant composite with three variants: 'string' for case-sensitive search, 'text' for case-insensitive search and 'regEx' for regular-expression search; each variant is a string (character array) field. The call Search(( for: ( string: "www." ); in: "http://www.google.com/" )) returns the sequence of all occurrences of "www." in "http://www.google.com/", consisting of one (composite) value. This example is below the actual spec of StrUtils in Wiki. To use the same function for case-insensitive search, one would have to just replace the word 'string' with 'text'.
Edit: just a minor correction, the regEx variant field is of type RegEx, not character array.

i have often thought, and agree with the comment i think from Andreas in that blog who pointed it out as well, that it ain't just bools that are too naked. any language w/out a good newtype/deriving/typedef is just asking for trouble.

Sorry, I don't understand. Aha! has user-defined types of course. Isn't it what you are asking?

the comment i was replying to was about how boolean values alone are to be seen as evil. i think the same is true for pretty much any primitive type. maybe we shouldn't define things as ints or strings ever, they should be a new type that is context-specific.

i don't know what Aha! has (just tried to find out in the docs and failed), i was talking in wider/popular language terms e.g. (shudder) java.

The reasons I didn't include Boolean as a primitive type are a little different. First, I didn't feel I needed it. Aha! has a statement logic which pretty much makes the Boolean type redundant. Second, I feel that having Boolean 'flags' is not the right way to do things when writing programs in the declarative style. Finally, Booleans can be simulated easily when really needed.

Beware leaving booleans undefined. If you do, then users will define them. In conflicting ways, leading to interlibrary incompatibilities and complicated conditional import configurations.

C left booleans undefined. Several important libraries defined them in conflicting ways. Intractable, subtle bugs and complicated "ifdef" requirements were the lasting legacy. Further, the conflicting definitions each had entrenched camps, preventing consensus from existing to allow standardization on any form for a long time.

1. If there's a failure within an "all"/"end" pair, is any action taken within the block backed out, as with a database rollback? If so, this would allow atomic operations of arbitrary complexity, which may be tough to implement but would be quite useful.

2, The bank account example shows "get" being used for an object with one member. The idea seems to be that updating an object involves constructing another object which is a modification of the old one. Won't this get unwieldy for complex objects? If a field is added during program maintenance, every method has to be modified.

3. Is a line break a delimiter? If not, is there a line continuation? Historically, languages with no or optional statement terminators have problems with long expressions. Javascript ran into this. The worst major case is probably the Bourne shell. Python has the unusual rule that you can continue a statement if you're within an open paren, which turns out to work reasonably well.

4. Using a new comment convention (enclosing in backquotes) is probably not a good idea. The trend is towards line-terminator comment markers ("--" in Ada, "//" in C++, C, Java, and JavaScript, "#" in Python) rather than enclosed comments ("(* *)" in Pascal, "/* */" in C and its successors.)

Thanks for your notes.

It seems that you don't realize it's a declarative language where every statement describes nothing else but computations. I recommend that you read the Getting Started guide carefully to understand the philosophy behind Aha!.

If there's a failure within an "all"/"end" pair, is any action taken within the block backed out, as with a database rollback?

Aha! statements are not 'actions' in the sense you seem to be putting in the word; they never have side effects. Statements only define variables and verify conditions. If there's a failure, the variables defined by the statement are left undefined (and no statements using them will be evaluated), that's all. Since there are no side effects, there's no need to 'roll back' anything.

The idea seems to be that updating an object involves constructing another object which is a modification of the old one. Won't this get unwieldy for complex objects?

It's so only semantically. In many cases, the operations on objects can be optimized so that no memory reallocation is required.

Is a line break a delimiter?

No, it's not. The syntax is designed in a way that no 'end-of-statement' markers are needed. There are optional semicolons and commas in some constructs, they can be used to make the code more readable where it seems appropriate.

Using a new comment convention (enclosing in backquotes) is probably not a good idea.

Maybe. In fact, the Language Reference states that All the text after a grave accent character is considered a comment and has no effect on the code semantics. I had to use an extra grave accent character in the examples to close each comment simply because the Wiki syntax highlighting of the code doesn't recognize the grave accent as an in-line comment starter. I didn't want to use any of the traditional starters because they look as good candidates for user-defined operators.

These constructs were introduced to simplify common tasks, such as search, filtering, sorting etc. The most powerful of these constructs is 'first'; it's effectively a while-loop, but with a limited number of iterations.

Otherwise, very brave formulation of an complete (I assume) programming language.

Thank you indeed. You are right, it's a complete language. I'm currently working on its implementation.

I don't believe recursion is possible in Aha! in any form. See FAQ on the website for a quick explanation. I don't have a mathematical proof of this yet, but I can't see how a recursive program could be written in Aha!. I realize this will deter from Aha! many potential users who strongly believe recursion is a good thing, but I'm not going to abandon my principles.

Speaking of recursive data types, I don't believe Aha! prevents from doing anything useful by forbidding forward declarations. It may help though avoid many design errors and spaghetti-style definitions. For an example of how 'inherently recursive' data types can be defined in Aha!, see the spec of module Trees in the Base Library.

Given a quick look, I have to say that I like some of your choices.

Some of the choices have taken a few years to make.

rmovchan: I don't believe recursion is possible in Aha! in any form.

Curiosity is killing me, so I hope you don't mind friendly questions. I have trouble believing that can be enforced, unless functions are not values (so no variable, array, or struct field can have a function as a value).

Even if anonymous, can a function be stored as a value in an array element? If so, then an array index is a name of the function and it's not anonymous anymore, if the function can be invoked by value out of the array.

You could seek to deny that via static analysis to make it illegal, but in the worst case it would be really hard to prove an indirect call does not occur. Did you really make it impossible? Or can a programmer go to an inordinate amount of trouble to evade static analysis? Just curious.

Could you please elaborate on this? I don't understand what an index in an array has to do with the function's name. Of course, a function can be assigned a name, but it's not known INSIDE the function body so it can't call itself by the name - that's what I meant by 'anonymous'. Did you mean that a function that processes an array can be placed into an array itself that is then passed to the same function as a parameter?

Sorry I wasn't clear the first time. I meant "name" in a somewhat abstract sense, meaning the way you identify something so you can access it, directly or indirectly. (For example, if you have a hash-based file system, where chunks are stored one time by unique crypographic hash, then each hash is the name of a chunk, in the sense that knowing a block's hash allows you to access that block.)

The FAQ says functions are first class, so I assume a data structure like an array can have function values inside. That's why I think the following will be possible. For array you can substitute any other compound data structure with a function value somewhere inside, reachable via lists, tuples, etc.

Suppose function F calls function G (which calls H, which calls I, which calls J etc. — we can use function names A through Z if we need a lot of function names). Let's pretend we only have two functions F and G, but we can make the call chain longer if that makes the construction easier to understand.

First define functions F and G, where F calls G. Now build map data structure M where F appears inside as a value. If M is an array, maybe index i is where F appears. If M is a hashmap, maybe key k has F as a value. But let's stick with an array so we can calculate index i dynamically at runtime.

Suppose the implementation of G takes a map argument like M, then calculates an integer value i from some complex dynamic expression, looks inside the map and invokes the function found using index i. Suppose the function is F; if so, this is recursion. If Aha! allows G to invoke any function from map M, but not F because that would be recursion, then the compiler has to prove G does not calculate index i, since that would return F from map M.

In that sense I'm saying i is a name of function F too, provided you have map M that turns index i into a value corresponding to F. (Is that confusing?) But it's a dynamic name, not a static name like F. I was suggesting you might prevent static recursion, but not dynamic recursion indirectly via data structures. If functions are first class, it would be hard to prevent that dynamic possibility.

I think you are absolutely right: recursion IS possible in Aha!, I've just realized this. I was able to come up with a couple of examples how to do it, much easier than you suggest. Here we go:

get f({ j: integer -> f({ i: integer -> i }) })
where
f = { fun: { integer -> integer } -> fun(0) }
end

This code defines function f that maps a function of type { integer -> integer } into an integer, by applying it to 0. It can be applied to itself indirectly as shown.

I don't know how to go about that yet. All I can say now, it's a huge disappointment to me. I'm thinking...

I guess the best way to handle this is to detect recursive calls at runtime (which can be done easily I believe) and signal failure straight away.

The reason I dislike recursion is that recursive calls may cause infinite computations, which is of course a failure; Aha! treats failures very well, but not those that can't be detected in a finite time.

I'll make corrections to the documentation in relation to this issue.

The example of "recursion" that you gave above does not lead to nontermination. Not just in the sense of that example terminating, but also there are total languages (every function terminates) which allow that sort of re-entrance (I wouldn't even call it recursion). See the simply typed lambda calculus for example.

Thank you Matt for your note. I've had a look at the simply typed lambda calculus but haven't decided yet if it's relevant to Aha!. It may very well be that it is, which means that my semi-intuitive assumption that recursion is not possible in Aha! was true. I will surely return to this issue before starting actually implementing the language; this will affect some implementation decisions. Thank you again, I appreciate it.

I've had a little read about typed lambda calculi, Curry-Howard isomorphism, total functional programming, etc. and so far as I can see Aha! is an example of a total language. Therefore, all programs are provably terminating! Can anyone disprove it?

My guess would be that it is not the case. I think any language supporting a style remotely close to object-oriented programming will have a hard time hiding the implicit recursion that comes along.

I'm thinking of something of the form (sorry for the approximate syntax):

obj { loop() }
  loop: return curr.loop()
end

Sorry, the syntax is not just approximate, it's completely wrong semantically as well. You cannot reference object's actions from inside the 'obj' construct. Of course, this would be recursion, and I wouldn't call it 'implicit'.

Pseudo-variable 'curr' refers to the internal state of the object, not to the object's 'interface'. Each action only computes a new internal state and can be considered just a functional value, or closure. BTW there are no 'virtual' methods in Aha! - instead you can use function-type parameters if needed.

Provably terminating functions are _not_ something you'ld wish for in a language. Even for the simplest of functions, Collatz, there are no known proofs of termination. Personally, I expect that if you could only express provably terminating functions, people wouldn't use your language.

(As far as the provability goes: If you can express Collatz in one form or another, you're language isn't provably terminating.)

If you can express Collatz in one form or another, you're language isn't provably terminating

Here we go (sorry, indentation is lost within posted code):

collatz =
{ start: integer ->
seq start then
get next where
any
let next = (curr / 2) where ((curr // 2) = 0)? end
let next = ((curr * 3) + 1) where ((curr // 2) = 1)? end
end
end
end
}

However, this doesn't prove anything. Aha! can express infinite sequences, but it can't express infinite computations on them: you can access only a finite number of sequence items at a time.

I expect that if you could only express provably terminating functions, people wouldn't use your language

Well, the decision whether to use a language or not depends on many factors, first of all on the practicality aspects, such as tools and libraries that come with it. What's important is what tasks one can solve with the language. I don't think many practical tasks rely on a language's ability to express non-terminating computations.

For starters, I can't read your definition of Collatz. No idea whether it is supposed to encode a list of Collatz numbers, the function, or just a step in the computation. If it is one of the first two, and your language is total, you would have given a termination proof, and I suggest you publish that result in a mathematical journal.

Second, most searches over abstract spaces fall into the category of programs most people don't give a termination proof for, but just run it a few times to see whether it terminates on trivial examples. Most typing algorithms fall into that category. If your language is total, it would be difficult to express most search algorithms in it, and I don't expect a lot of programmers to go for such a restrictive language.

The program implements a function that produces the sequence of Collatz numbers starting with a given number. It doesn't actually check that the sequence ends with 1.

just run it a few times to see whether it terminates on trivial examples

And how do they decide whether it terminates or not? Are they prepared to wait for the answer indefinitely?

The program implements a function that produces the sequence of Collatz numbers starting with a given number. It doesn't actually check that the sequence ends with 1.

So it produces an infinite sequence? I still can't read your example; there doesn't seem to be a check on one, that's true.

If it produces an infinite sequence your language isn't total, now is it?

And how do they decide whether it terminates or not? Are they prepared to wait for the answer indefinitely?

Most people don't care about formal termination proofs. If an algorithm terminates on most examples, it does the job.

If it produces an infinite sequence your language isn't total, now is it?

Yes, it produces a possibly infinite sequence. This has nothing to do with the termination issue. What's a sequence? It's an abstract data structure that we can process one item at a time. It's not like an array or list, it's a lazy data structure if you like.

If an algorithm terminates on most examples, it does the job

You didn't answer my question. So, as I understand, they wait for some arbitrary time and then decide that it didn't terminate, after which just cancel it, right? Hmm, strange approach. Highly informal. It implies that they don't really care about the correctness of the algorithm and whether it's going to work in the future. If so, then you are right, Aha! is not suitable for those applications.

A good program is one that works every time, not 'in most cases'.

Most people don't care about formal termination proofs

Did I say that Aha! requires such proofs? All it requires is some estimate of the maximum number of iterations, after which the iterative statement is considered failed. If you don't care if your program ever gives the expected result, then you probably shouldn't be programming at all.

All I am saying is that if your language is total, which implies that all functions terminate, then expressing the Collatz function in your language is equivalent to giving a proof of termination.

The reverse is true too. Since you don't really know whether your language is total and were able to express the Collatz function, your language isn't total, unless you would somehow magically know that it always terminates. And the latter is still an open question, as far as I know.

Of course most people often check termination of algorithms by running them for a bounded time. Don't you? Termination proofs are often too hard to even start thinking about unless you have some reasonable evidence that an algorithm usually terminates.

expressing the Collatz function in your language is equivalent to giving a proof of termination

Sorry, it looks like you don't hear what I'm saying. The function returns a lazy sequence of numbers that may or may not be infinite - this has nothing to do with the function being terminating. If I wrote a function which extracts a Collatz sequence and checks if it ends with 1, it would be possibly non-terminating, unless we set some limit of the number of sequence members we want to check.

Termination proofs are often too hard to even start thinking about unless you have some reasonable evidence that an algorithm usually terminates

I'd like to re-iterate that I don't insist on termination proofs. Aha! has no constructs that can run indefinitely; its construct closest to the while loop, the 'first-that' expression, extracts a finite number of items from a sequence before deciding that it failed to reach the target. Having a termination proof is helpful when providing the estimate of the iteration limit (e.g. to avoid early termination), but is not required.

most people often check termination of algorithms by running them for a bounded time

That's basically the same what I said above. The only difference is between the limited number of iterations and the 'bounded time'.

I am sorry, but that's because your construction is a red herring.

Every potentially terminating computation can be expressed as a possibly infinite sequence of total function applications. That's a no-brainer.

But you either expressed Collatz, or you didn't. It doesn't change the argument.

It turns out you didn't express Collatz. The moment you do, by, as you said, terminating on a one on the sequence, your language isn't total.

Your elaborate construction is irrelevant to the argument, hence I deliberately avoid it.

(Though the fact that you can express infinite sequences makes it likely that you language isn't total. But that's an argument I try to avoid since Collatz is more easy.)

What are you trying to prove to me? Your original claim was

If you can express Collatz in one form or another, you're language isn't provably terminating

Now, what did you mean by 'express Collatz in one form or another'? My example was to show that I can express the sequence of Collatz numbers, starting with any number, in Aha!. From the very start, I mentioned that the program was not meant to check that the sequence is finite, because THAT would involve possibly infinite computations and would require a non-total language. Or by 'express the sequence' you mean 'generate the full sequence and put it in an array'?

Well, we were debating whether your language is total. Now that already is a question with lots of red herrings around it, but my proposal was: "See whether you can express Collatz. If you can, you're done. And your language isn't total."

By moving to lazy infinite sequences you messed with the argument. For instance, if it were only possible to print a constant finite initial segment, and a thousand is probably more than enough for your integer width, of that lazy list, you could still theoretically claim that your language is total (since you would then artificially give an upper bound to the number of computation steps by binding the size of the list).

Unless you express a complete program which in a general manner computes Collatz until the number one, or prints the sequence until the number one, it is difficult to claim for sure your language isn't total.

Effectively, you gave half of the argument. Since you moved to lazy evaluating the Collatz function, it now becomes important what you _do_ with that lazy list to conclusively decide whether your language is total. In some sense, you only specified half of the Collatz function. (I.e., you specified how to 'step' once to another number, but you didn't specify how often you're going to step.)

(But I've seen enough. Since your list encodes a Collatz sequence, and there is little you can do with that except for print it (upto the number one), I would say your language isn't total.)

Since your list encodes a Collatz sequence, and there is little you can do with that except for print it (upto the number one), I would say your language isn't total

All I wanted to show by my example is that your criteria is at least vague. I could 'express Collatz' in a total language - yes, I still believe it is. Sorry, your argument didn't convince me: the fact that "there's little you can do with [the sequence]" doesn't prove anything. Red herring, as you say.
And I still can't see that there's something my language can't do what languages with non-terminating computations can. Aha! program can be 'non-terminating' in some sense: for example, it can be an interactive application that prints first 1000 items of an infinite sequence, then waits for users input, and unless the input is 'quit', prints the next 1000 items, and so on. Every computation terminates, but the user can initiate it as many times as he wants. Does that make it non-total?

The ability to guarantee progress up to input is valuable for reasoning, and use of input (e.g. a clock tick every 10 milliseconds) to express incremental behaviors is normal for real-time languages. Real-time is a stronger, more useful condition than terminating. If you can express Ackermann's function or naive recursive Fibonacci, you can easily express a computation that is non-terminating in practice.

A language that terminates up to input may be total.

I have not been convinced that Aha! is total. It gets tricky with mutual recursion expressed through maps or similar.

Speaking of Ackermann's function -- can Aha! express it? I suspect it only has predicative polymorphism and that every Aha! function is primitive recursive.

That's a good exercise. I'll try to do it.

- the above is no sneer. this line of questioning just reminds me of complexity class.

For arbitrary sequences? I guess that would be equivalent to asking: Can I decide whether a/any program halts in bounded time? Looks total to me, wouldn't know.

Ah well. Let's just conclude that there is an easy check to see whether your language _isn't_ total: If you could somehow express the complete Collatz algorithm (i.e., you need to provide a 'consumer' for the lazy list which prints it and ends on one), then you don't need to bother to give a probably very complex proof of totality. Now that's at least worth something, right?

The argument I use goes like this:

1a. My language is total, that is equivalent to

1b. Every computation terminates by construction

2. I can express Collatz in my language

3. 1b+2 gives: Collatz terminates

Now either a) I gave a proof that Collatz terminates -which I deem unlikely,- or b) I derived a contradiction, and my language isn't total.

I don't think there is a flaw in the above, but feel free to comment on it.

At the moment, you and rmovchan are really arguing over the meaning of 'express'.

When you say "I can express Collatz in my language", you mean something similar to: "I can represent the Collatz computation as a function." But in discourse about expression and modeling in a language, the "computation, as a function" criterion is not usually assumed. I would not assume it. rmovchan did not assume it. Languages are more than their functions, and problems are more than their computations. It is reasonable to say that a language "can express Collatz" by modeling it as an incremental or coinductive process, for example.

Further, you earlier said: "can express Collatz in one form or another". That positively invites an open interpretation of expression. Perhaps you should supply a bit more precision if you want a proof...

I deliberately stated 'computation' and never meant to imply anywhere that the modelling should somehow syntactically agree with the Collatz function as usually expressed.

You just need the Collatz function abstractly modeled as an equivalent computation for the argument I gave to work.

(I.e., something which given a number produces the sequence of numbers and terminates on one.)

You did not explicate your personal meaning for "express Collatz" until 9 posts after you mentioned Collatz. If you feel there was no miscommunication, you should ask the other guy.

You just need the Collatz function abstractly modeled as an equivalent computation for the argument I gave to work.
(I.e., something which given a number produces the sequence of numbers and terminates on one.)

Thank you for the precise description of the task.

What I didn't hear is whether my proposed interactive solution (up to 1000 sequence items at a time) would work for you, and whether you'd automatically consider such a language non-total.

About the sequences. Theoretically, I would argue that you then didn't show that the language isn't total since I think the best you proved is that for every possibly halting function, you just showed that you can compute whether it halts in bounded time. I.e., you didn't give an implicit termination proof on the Collatz, or any, function.

Pragmatically, though, it really makes it very likely that your language isn't total. But that isn't a proof, right?

About expressing Collatz. Okay, so it takes some time for us to understand each other. The main point I want to get across with 'some form or another' is that it doesn't matter how Collatz is expressed, only that it is expressed (by means of infinite sequences and a consumer function, by means of some Voodoo with storing continuations, or even by means of elaborate integer arithmetic tricks, I wouldn't know.) But it is very important that Collatz is expressed as a computation which is equivalent to it's functional description in order for the argument to work. I think you can see that, right? No equivalent expression, no proof, you don't know anything.

Best would probably be some formal reduction between your language an a recursive language in which Collatz is expressed, but I didn't give the exact formal argument much thought. Pragmatically, I would say that it is enough to produce the sequence and halt on one.

(Okay, so I gave it some thought on my bike. I guess the difference between the recursive language reduction and directly expressing Collatz is the difference between the argument "Look, this language can compute any recursive function, for which we know some don't terminate." and a more direct argument "Look, this language can express the Collatz function, a function for which we don't know that it terminates." The latter is a bit more sloppy than a reduction, but math is sloppy anyway, so I am not bothered. The only point of interest is whether you give a convincing argument.)

I was looking for examples that would prove that my language isn't total or arguments that it is. It turned into a discussion of the usefulness of total languages in general and ways of expressing Collatz. Can I do anything to turn the discussion back to the original question?

I do not believe the potential to `fail` should be present in a total functional language, except as an explicit part of the function's range. It is no different than divergence: return successful or not at all.

(Addendum: The word 'total' was not originally used to mean 'terminating' but rather that functions are mathematical functions, that properly map every element in their domain.)

In that case, I would prefer not to call the language 'total'. The concept of failure is crucial for the language and is a lot more important to me than it being classified as something. I still insist however that every computation in Aha! terminates, which I thought was the definition of 'total'.

I think you're right, we are arguing over the meaning of 'express'. I'm trying to prove that my language, being total, still allows one to express any reasonable task. Marco seems to believe that there are some tasks that can't be expressed unless the language isn't total. Because he didn't understand my code, he wasn't sure whether it does 'express' the Collatz sequence. By 'express' he apparently means to fully compute in non-lazy manner, which, you are right, is more specific than express Collatz in one form or another.

The thing is, instead of wondering about "Is my language total?" you went to "Can I express most functions?" I didn't, just made a side comment that it'll be hard, up to pragmatically impossible, to express some functions; I thought we were still discussing the totality question.

As someone developing a real-time paradigm, I'd express Collatz by manipulating state - incrementally, with each increment happening in real-time. And I'd call this a legitimate expression of the Collatz algorithm, which certainly is not real-time.

While it may have been your intention to focus on totality, the way you worded your question cast aspersions on the expressiveness of total languages. Naturally, someone developing a total language will be defensive about that.

As a programmer, you should know it's the behavior invoked by your words that matters, not your thoughts or intentions. :)

As a programmer, you should know it's the behavior invoked by your words that matters, not your thoughts or intentions. :)

And as an adult I know you can read whatever you want in words. The thing has been cleared, the discussion diverged into two separate discussions, that's enough for me.

So now that's out of the way, let's return to technicalities. The formal proof argument is out of the way; I'll not comment on that again.

I'd call this a legitimate expression of the Collatz algorithm

Yeah, well, I would agree on expressiveness. Moreover, from a theoretical point of view, I know you can argue that all functions can be expressed in a language which mostly allows total functions on a state space, and iterates that. Informally, that's exactly the relation between a CPU and memory: The CPU implements a total stepping function on a the memory, a large state space. And one could compile any recursive function to a small language expressed in the state space which is endlessly iterated.

But pragmatically, I would still worry about expressiveness in a language which only allows total functions. I mean, if you already need to go through to many hoops to express a simple function, then that doesn't bide well for more complex examples.

if you already need to go through to many hoops to express a simple function, then that doesn't bide well for more complex examples

Similar arguments have been presented against structured programming, type safety, effects typing or purity, object capability model, relational model, and logical consistency. Yet such constraints can offer features and freedoms for higher level reasoning and composition. Contrary to what you might expect, many "more complex examples" may prove easier to achieve due to the greater structure imposed on the component problems.

Requiring an incremental expression of Collatz becomes a valuable feature of the language for the larger, "more complex examples" of concurrent computation, formalizing job control, integration with UI, etc..

As someone developing a real-time paradigm

By the way, don't you find Aha! well-suitable for real-time tasks?

No. Aha! isn't real-time. Neither does Aha! support reasoning about time in any formal sense. Compare Chuck, or read up on Computing Needs Time.

At the very best, you could say that Aha! is slightly less unsuitable than some other languages.

What I meant is that since its iterations are limited, programs have no side effects, it may be suitable for real-time tasks given appropriate tool support (libraries, framework). True, it doesn't have built-in notion of time, but it could be provided via a library.

To support real-time programming through libraries, preferable language features would be linear types and dependent types. (Preferably, dependent types supporting rational values.) Alternatively, lifting algorithmic performance into the type system could work.

Supporting macro-expansions for limited iterations is a useful feature for reasoning about time, though it's hard to apply in the case of higher-order functions.

OK then, I may need to return to this issue in the future. The language wasn't meant specifically for real-time, but I thought it had some potential for it.

I can see a total language having merits in a _very_ _very_ small niche of application domains. Like, say, high performance network routers, or GPU programming.

But it is only one very limited quality. Do you compile to assembly for a number of microprocessors? Do you provide different schedulers, EDF/RMS, for your total functions? Do you (time-)count the generated assembly and are you then able to provide upper bounds for computation time? Do you provide logging and debugging tools for microcontrollers? Is your garbage collection real-time?

I don't agree with dmbarbour. For more complex (soft) real-time programming, like games or industrial controllers, it is just easier to express recursive, or looping, algorithms directly and time-slice them under a specific scheduling/compilation scheme. Complex real-time OSes provide more than enough abstraction models for _not_ having to go down to the bare assembly (which is where I see the sole use for total languages).

A primary use of total languages is Curry-Howard provable programming, where expression of a program constitutes a proof of a theorem expressed in its type system. Cf. Agda, Idris, F*, Coq.

"Total" is rarely real-time or statically bounded space. Total languages are often expressive enough for Ackermann function, and can easily express programs that won't terminate before heat death of this universe. The ability to prove an operation terminates is much weaker than any formal claim on its performance properties.

The main advantage of total languages for performance control is that you're much less likely to express an infinite loop or long-running program by accident (i.e. as a bug).

it is just easier to express recursive, or looping, algorithms directly and time-slice them under a specific scheduling/compilation scheme

That may be what you're familiar with, but expressing real-time algorithms and resource management, and composing them, becomes just as easy assuming a good language for it and support for staged abstractions.

You seem to believe that real-time programming must be low level, down to the assembler. But that's simply untrue. Real-time is all about the abstractions, whether they're coming from the OS or from the language. If you want consistent, portable, provable abstractions, it is best to reify them in the language. (One can still benefit from the real-time OS, of course.)

You seem to believe that real-time programming must be low level, down to the assembler.

I don't, I actually believe the opposite. What I said that I could possibly see a role for a total language in the context of (hard) real-time where you have little else but (time-)counting assembly instructions. A total language could have a role there since it should generate relatively straightforward assembly on which you could automate that tedious task.

As I stated, I believe the opposite, and generally agree with most what you said. But to put it concisely, if you believe you're going to solve real-time problems with a total language, you're concentrating on the wrong problem.

(And I don't buy into your 'by accident' formulation. I believe that's a non-problem in real-time. Moreover, you're probably more prone to reformulate a complex recursive algorithm badly, than to state it clearly and concisely directly, and use the primitives of scheduler to time-slice it. We do differ on this and unless you can give hard evidence, I don't believe your statement.)

I said that I could possibly see a role for a total language in the context of (hard) real-time where you have little else but (time-)counting assembly instructions. A total language could have a role there since it should generate relatively straightforward assembly on which you could automate that tedious task.

I have difficulty reconciling those sentences. If I have high level real-time languages, then I don't "have little else but (time-)counting assembly instructions". If I "have little else but (time-)counting assembly instructions" then I must not have higher level real-time languages.

You're sitting there saying total functional is somehow good for real-time. Shall I assume you haven't seen anything better?

if you believe you're going to solve real-time problems with a total language, you're concentrating on the wrong problem

Bah. Any notion of "wrong problem" from someone who brings up Collatz as an example problem should be taken with a shaker of salt.

Programming is about cyber-physical control systems: sensors, actuators, data, rules, and humans' interactions and relationships with them. ALL human problems are real-time problems. If you AREN'T developing a real-time solution, you've got a design bug.

Even for problems that are pure mathematical exploration, a program generally should interact with users in real-time, e.g. to visualize, or animate progress in a search, or provide job control.

I don't buy into your 'by accident' formulation. I believe that's a non-problem in real-time.

I did not suggest it was a problem that needed to be solved. However, if I want composition of real-time systems (i.e. latency as an inductively computable property), then I actually need stronger constraints than totality.

you're probably more prone to reformulate a complex recursive algorithm badly, than to state it clearly and concisely directly

Compare: "with structured programming, you're more prone to reformulate an complex goto algorithm badly, than to state it clearly, concisely, and directly" - true, but irrelevant in practice.

In practice, when faced with real-time constraints on expression, developers will find new algorithms that achieve the same cyber-physical requirements. We program to solve problems, not to express algorithms.

Your complex, recursive algorithms are the wrong solutions. Your need to rapaciously violate your programming abstractions through the OS scheduler and job control is, in fact, hard evidence that you're using the wrong abstractions in the first place. But it's difficult to see the Blub while you're immersed in it. To you, it's just the way things are.

dmbarbour, I give up. You consistently read things in my post which just are not there. Moreover, you are speculating on my motives. I have no idea where your preposterous ideas about my motives stem from.

If you have a better argument of proving mathematically that a language isn't total, I would be interested.

I have supervised enough students in real-time assignments to know what problems in real-time are, and how they are solved.

"cyber-physical"? This discussion is closed. Completely.

If you have a better argument of proving mathematically that a language isn't total, I would be interested.

A better argument would be presenting an example of a non-terminating program in that language. However, you apparently aren't willing to learn the language well enough to be able to present such an example. It's much easier to ask the author to do it himself.

If I wished to prove termination, I'd probably need to take your semantics and express them in a language that supports such analysis, probably Coq or Maude. Thing is, it takes a very deep understanding of the semantics to perform such a proof, and informal arguments aren't very good in this role.

Thing is, it takes a very deep understanding of the semantics to perform such a proof, and informal arguments aren't very good in this role.

So, I shouldn't have started this discussion in the first place? Maybe you're right. I'm asking too much I suppose: nobody is going to learn Aha! and do this for me. I need to present a proof of termination myself, at least semi-formal. So far my belief is based on the analogy with the typed lambda calculi.

No, it was a correct question and I responded with an easy manner of proving the opposite of what you asked. We got somewhat sidetracked on detail but I found it an interesting topic.

My first lines above described how your posts aren't internally consistent. Perhaps that explains why I consistently read things that aren't there.

cyber physical systems is a term of the art, and a common referent in papers on real-time systems (such as Computing Needs Time).

I am not convinced you are competent to supervise real-time programming tasks. To know how your students do them is not the same as understanding how they should be done.

You continue with ad-hominem attacks. I have a small real-time library at home and twenty years of reading, coding, and teaching behind me.

As far as I am concerned you don't understand a trivial proof unless somebody completely spells it out, you misread every post I made, and move the discussion from a specific topic to something not even closely related while mucking around with a number of buzzwords. I am not interested.

Ah well. I don't mind being misunderstood. I don't mind differing on an opinion. I don't even mind being wrong. I _do_ mind ad-hominem attacks. You had it coming.

I know of a teacher who does not mind being misunderstood, who claims "There is no miscommunication on that", who does not mind being wrong about that claim, and who shortly afterwards is quick to blame "misreading" on yet another correspondent. This teacher also closes conversations with disinterest and disrespect for terms of the art.

If such a teacher were to appeal to competence as a teacher and ability to communicate with students, I would feel skeptical about the strength of those claims. If I were to attack the basis, would that be an ad-hominem, or would it be a reasonable counter to an ad verecundiam? The personal nature of the claims would, I expect, make it difficult to separate those (emotionally, if not logically).

I do not feel that I have attacked your person, but I understand why you might feel otherwise. I am sorry you feel that way.

Man, I am sorry but you do need to brush up your online communication skills.

I have clarified all my posts notwithstanding the fact that you consistently made them more and more personal with each post, forcing me to expose some personal facts, after which you took up that ball and started doubting that.

I can and do expect some minimal effort and leeway from you in understanding my posts. If you would have tried to understand the mathematical construction, you wouldn't have misread it.

If you don't understand a post then you can simply ask someone to clarify instead of claiming "internal inconsistent," and from there moving to more personal attacks, and every thread would have ended there. Clarified instead of personal.

Your last remark was completely off the charts, and you don't even realize it. Go tell a random baker "You doubt his ability to bake pies," a random policeman "You doubt his ability to fight crime," and your best friend "You doubt his manhood." Not only does it not matter in a technical discussion, it is plain rude.

As far as the not-caring goes. You don't behave less socially adept as a number of students of mine, and you got a reprimand for that. And no, I don't care about it.

I think this discussion hasn't been relevant for LtU for a while. Please feel free to continue it privately.

Of course I wouldn't tell a random policeman he can't fight crime, or a random baker he can't bake pies. OTOH, if a baker said he can bake pies then fed me an awful pie... well, he'd no longer be a "random" baker.

I understood your purpose with the "express Collatz" argument immediately. I also understood rmovchan's interpretation of your words right away, and I happen to agree with his interpretation. Does that mean I misread you? Or that you miswrote you? If you had not attempted to defend your words, that argument would not have gone any further.

That's the only mathematical construct you've attempted. You made no such efforts for your silly assertions about real-time. (Your appeal to your expertise as a teacher certainly wasn't a technical argument.)

If you find me rude, that does not imply I miscommunicated anything. I will avoid engaging you again.

God man. I've got other things to do except discuss technicalities with someone whose only defense about that is to admittedly get personal about it.

Great going, dude.

I've read the article and have to say it's highly controversial. Adding temporal semantics to programming languages is a crazy idea. The semantics of PLs is already too complex and vague, so adding yet another dimension to it doesn't look to me as the right way to go.

With Aha! API, it will be possible to define temporal behaviours without injecting the concept of current/execution time into the computations. I'm convinced that the current time should NOT be directly accessible by any computations, and the execution time must be considered a side effect of computations - something that we want to get rid of completely as programming languages mature.

"Adding" temporal semantic to an already too complex programming model could make it more complex, indeed.

However, if you design temporal semantics into a language from the start, you can other aspects it a lot simpler. The temporal semantics can cover much expressiveness needed for representing and safely managing concurrency, state update, and orchestration of effects.

Existing models along these lines: Synchronous Reactive Programming, Functional Reactive Programming, Temporal Logic, Discrete Event Systems, Temporal Database, Timed Concurrent Constraint Programming. I am currently developing the paradigm Reactive Demand Programming, which supports reactive programming of open systems.

execution time must be considered a side effect of computations - something that we want to get rid of completely

We'll always have execution time. Often, temporal behaviors are contingent on data that will only become available in the future (such as the position of your mouse). And even when there is no dependency on future input, computing an infinite future would generally take infinite time and space.

One might speculate ahead a few seconds, or minutes, perhaps even hours or days. But to do so has a storage and buffering cost in addition to the compute costs, and any speculations based on probabilistic estimates for future inputs have a growing chance of needing to be recomputed.

Temporal systems must generally release old data while generating data for the the near future. (RDP simplifies this by forbidding direct dependencies on a signal's history.)

current time should NOT be directly accessible by any computations

I agree. I consider access to the current time to be an authority worth protecting, e.g. controlling access via a capability. Temporal semantics will thread time through data and behavior, but does not require access to time be granted to arbitrary code.

I consider access to the current time to be an authority worth protecting, e.g. controlling access via a capability.

That's not what I meant. In the execution model I plan for Aha!, there will be no function available AT ALL that returns the current time. This will be an event-driven environment where certain events will pass to the pure Aha! programs system info like the current time. There will be no other way for a computation to access the time. Since the time is passed as a parameter, it will be constant during the computation.

Often, temporal behaviors are contingent on data that will only become available in the future

I suppose this fits nicely into the event-driven model I mentioned.

In a temporal semantics, there is a logical time distinct from the physical wall-clock time. At any given logical "instant", all values are frozen, i.e. you would not be able to observe changes to the wall-clock within one instant. I suggest you read about the synchrony hypothesis. The model described in the linked slides is synchronous reactive, but other temporal semantics have similar characteristics.

When I spoke of "access to the current time to be an authority worth protecting", I was speaking of access even to the logical current time. One motivation for this: it's easy to hide security holes in code if the holes can wait for a particular time to open.

OK, I'll read it, looks interesting.

I just scanned your language spec doc and it looks like it would total for simple reasons. No polymorphism, no mutation, no recursion, strongly typed... not much to go wrong. I think your language should have a simple set theoretic interpretation. You should probably work through the proof to be sure. It should just an induction over syntactic forms.

IMO the most worrying features are the ones the language doesn't have.

IMO the most worrying features are the ones the language doesn't have

I would say, the most worrying features are the ones you are used to from your previous experience and look for in every new language you learn, ignoring what this language offers instead.

No polymorphism - not quite true. The language has generics, polymorphic operators, abstractions (such as objects). What do you mean by polymorphism?

I didn't notice the generics in modules. Your modules aren't recursive, so that shouldn't affect totality, but that does address one of my big concerns. I didn't notice polymorphic operators and a search in your language reference doesn't turn up any hits.

Speaking of modules, the language reference mentions the 'arbitrary' declaration - "Declare module’s type parameters". Collections and Dictionaries modules in Base Library are examples of parameterized modules (see the Wiki).

Speaking of operators, it doesn't say specifically that they can be polymorphic/overloaded (Getting Started does), but there's nothing that prevents from using the same symbol to refer to different functions (operators are just syntax sugar for functions). For example, module Float defines operator (Float + Float), module Time defines (Interval + Interval), Rational contains (Rational + Rational) etc.

Hmm. Runtime detection of recursion. Yeah, it's possible. You could have each function associated with a value in a table which it increments as it starts and decrements when it exits, and fail whenever a value is incremented beyond 1. (Or beyond 10, or whatever, if you want to allow limited recursion).

That said, I don't think you will make programmers happy by doing this. Recursion, like 'while' and 'until' loops, can result in infinite computations but is also pretty darn useful. If there's really no way to have an infinite computation, then there's provably an infinite set of problems that you can't solve.

To the extent that the set of problems you can't solve is disjoint from problems you're interested in solving, you win. But that's a very hard judgment call to make.

Ray

I think we need to clarify what 'infinite computation' means. No computation can run indefinitely to be useful, right? Nobody is going to wait for the result indefinitely, there is always a limit of time and resources we are prepared to dedicate to the problem. Aha! doesn't limit the class of problems that can be solved, it only makes the programmer estimate in advance the maximum number of iterations needed to achieve the goal.

I don't think you will make programmers happy by doing this. Recursion, like 'while' and 'until' loops, can result in infinite computations but is also pretty darn useful.

I don't want to start a discussion about the usefulness of recursion. I believe Aha! offers something in lieu of what it takes away (e.g. recursion, exceptions, pointers) in an elegant way, so developers won't be disappointed.

Three points
* There are many non-terminating computations that are quite useful. A few people have made billions of dollars off one particular kind (operating systems). There are many other examples.
* If you speak of side-effect free functions, then nontermination is not very useful. However, it is sometimes useful to have functions that terminate most of the time but occasionally take a long time, or never terminate at all. The user can hit control-c when the get tired of waiting. Its still a useful function.
* It is possible to write many useful computations, including compilers and complex systems, in a language that requires a proof of termination for every program. One such language is ACL2, a version of pure lisp with a theorem prover. ACL2 will not accept or run a program that it cannot prove will terminate. The ACL2 system is written in itself. Some useful ACL2 programs that have been written include a Java bytecode verifier and VM (which have, by the way, been proven correct). The VM had to have an artificial termination check added: it will only run N bytecodes before it dies :-)

There are many non-terminating computations that are quite useful. A few people have made billions of dollars off one particular kind (operating systems). There are many other examples.

Wrong. These are not 'non-terminating computations', they are interactive applications. I would not waste everyone's time proposing a language that doesn't even allow writing interactive applications.

Could you please be so kind to go and check out the materials on my web site before posting any criticism here? I meant this topic to actually discuss the Aha! programming language and not some non-existent issues.

If so, could you please update your website to indicate the affiliation and also update the Wikipedia page for your band?

The Norwegian band is actually called "a-ha" (in lower case) and Aha! programming language has no affiliation to it.

http://www.metrolyrics.com/take-on-me-lyrics-a1.html

Can you please be a little more polite in your interactions here? I was responding mostly to the previous comment, not your web site. Perhaps you could include pointers to the relevant parts of the web site, rather than criticizing your participants. The way you write your response is not very friendly sounding (despite the use of "please"). Finally, I will point out that I did read your web site, after which I suggested that you hadn't prevented recursion after all, which turned out to be true. So, perhaps you should keep better track of who has read your web site and who hasn't, if you are going to make such comments.

I didn't mean to sound unfriendly. I just get frustrated that the topic 'Aha! Programming Language' is flooded with posts that discuss things that seem unrelated to the actual language. Your particular post states that there is a wide class of tasks that require 'infinite computations' and are therefore impossible to program in Aha!, which led me into thinking that you hadn't seen the examples of such programs on my site.

I just get frustrated that the topic 'Aha! Programming Language' is flooded with posts that discuss things that seem unrelated to the actual language.

I have to say, this is the rather the norm on LTU. Discussions here do tend to be wide-ranging, and they also tend to revolve more around the study, design and implementation of programming languages in general and much less around the specifics of any one language. Frankly, I would be quite pleased, if I were you, that people are willing to discuss your pet project at all...

Frankly, I would be quite pleased, if I were you, that people are willing to discuss your pet project at all

I am! I was pleasantly surprised at first that posting at this forum had immediately created some traffic on my site. But I have to admit that despite my efforts, there haven't been really any discussion of the language itself. Well, almost. Of course, it's my problem and not LtU's. I need to think more about how to present the language so it's interesting to discuss.

I suggested that you hadn't prevented recursion after all, which turned out to be true

Well, that remains unclear. Someone else has referred me to the simply typed lambda calculus, and I still have doubts if a truly recursive program can be written in Aha! (my example wasn't really an example of it).

Once again, I apologize if my response was somewhat impolite, and thanks for spending time to look at my project!

Can you create vtables in Aha? For example, suppose you were going to implement Smalltalk in Aha!, and created method tables with a dispatcher sending a selector to each object which looks up a function and calls it. (This is just indirect function call through a lookup table, where selector symbols are a way of obfuscating identity of functions called.) If this works, then Aha! supports recursion fairly directly.

For example, if you find classic implementations of Lisp routines recursing over list elements, you can restructure them to do the same thing, also recursively, but in an object oriented formulation if you define a pair type with two fields named car and cdr, accessed by selector names car and cdr (and whatever internal function names you like dispatched when those selectors do a lookup in a method table). Does Aha! prevent that?

No, there's nothing like vtables or virtual methods. You can read the 'Objects' section in the Language Reference and you won't find them; the object paradigm in Aha! is pretty straightforward. If anyone is interested how things like dynamic dispatch can be implemented in Aha!, I can give a hint: first-class functions.

I'm mildly surprised you misunderstood me. I don't mean vtables that Aha! the language creates. I mean vtables a programmer creates manually, without Aha! help or cooperation beyond supporting first class functions.

(My vtables question omitted another element some folks might need to follow a literal recipe to re-create classic recursive algorithms. Any function which is itself recursive must become a method of the first argument, dispatched through that argument's vtable.)

Sorry, I didn't read your post carefully. Of course, vtables in that sense can exist - like arrays of functions, for example.

When you talk about the Lisp example, of what type the fields car and cdr are supposed to be? Bear in mind, Aha! is statically typed and it doesn't allow you to create recursive data types either (again, read FAQ).

If functions are first class, then an array of functions is a vtable, and an OO system coded up in a user-space library may use it as such and do method dispatch using it, whether the OO system you provide is aware of the concept or not.

First class functions mean people can do OO in whatever way they choose to, not just in the way you expect. If you provide first-class functions, anyone who feels constrained by the OO you provide will create an alternative OO system as a library.

This is why Common Lisp had to have such a completely extravagant OO system that it developed CLOS -- they didn't want anyone to have any possible motive to develop a competing OO library, so they put every feature in the universe into it.

Ray

If someone wants to develop their own library, why should I be worried? Aha! offers some good ways to do things, it strives to make possible reducing the complexity of software, but no language can (or should) protect the developer from creating a super-elaborate program that even he/she doesn't understand. I don't think what CL did was a wise thing to do.

What the CL committee did was to build an OO system which was very close to being a direct superset of every OO system used by all of the pre-existing lisp dialects that were all trying to converge into "common lisp."

That way all the existing code, in at least five major separate lisp implementations, could be directly ported to common lisp without any significant redesigns (ie, the translation could be automatic). Nobody would be "forced" to stick with a non-CL lisp by needing the object system provided with it to run legacy code, and nobody using a non-CL lisp would be able to develop code that couldn't be simply translated to CL when wanted.

I'm with you in considering the final product a bit excessively baroque. But that's where you wind up if you're trying to create a translation-target language. And now that I have realized that, I'm realizing that I'm probably going to have to implement something very much like it.... :-(

Ray

I don't want to talk you out of your plan. I was just wondering how you managed to get recursion restricted, since it seemed hard. But if I help you succeed, I feel bound to say I don't like this plan to prevent recursion, and I wish you wouldn't. :-)

rmovchan: detect recursive calls at runtime

That's do-able, at some cost, but building restrictions into a language can easily affect whether folks want to use it. For example, you would be unable to implement Scheme or Smalltalk in Aha! if you succeeded in shutting down recursion. (Someone might be able to Greenspun-up a suitable runtime anyway by hacking Aha! in way you didn't expect, but inspiring people to heroic effort like this seems unproductive.)

While I don't like a policy of preventing recursion, there are mechanisms to detect re-entrance by the same thread that are not prohibitively expensive. Cheapest in space and time seems to be a hashmap of entry points (the set of all functions you are now still inside) associated with the current thread. Then you can ask, "Am I already inside this function I'm about to call?" in constant time with space cost linear in stack depth. I still dislike that cost overhead, but I don't see how to make it less.

If you also intend to prevent concurrency (please say no :-), you can try to enforce single threaded execution by making code self-modifying to record whether anyone has entered but not yet exited. However, this has a really stone-age smell to it: self-modifying code will make lots of folks squirm. You would even be able to stop green threads that way, no matter how a scheduler was organized.

There are reasons why re-entrant code is a good idea, as well as recursion, in terms of expressing problem decomposition efficiently by using the same code on different state associated with sub-problems. Constraining programmers for their own good is historically a way to repel adopters, if you worry about that.

The rest of this is an aside to any readers who want to debug concurrent code which now has no locks, when you suspect locks might be needed. I had to do this a few years ago when I was told it was impossible for more than one thread to execute on this one object at the same time. (They were wrong.) It's easy to write a mock-mutex object which captures current thread ID, then complains if any other thread tries to "lock" the same instance using a different thread ID. In C++ you unlock in destructors to get RAII semantics. Even better, when you know there's a problem, have the mock-mutex capture a stack-backtrace so you can print the two conflicting backtraces when another thread tries to relock the same mock-mutex.

I didn't intend to discuss the implementation at this stage, but with the plan I had in my mind the solution looks quite simple. Regardless of the recursion issue, functions (i.e. closures) in Aha! would be implemented using "wrapper" objects having the only method that serves to compute the function with given parameters; the wrapper would hold the closure's context information (i.e. the values of the variables in the closure's context).

you can try to enforce single threaded execution by making code self-modifying to record whether anyone has entered but not yet exited

In the light of the above mentioned implementation, this wouldn't be "self-modifying code".

If you also intend to prevent concurrency (please say no :-)

I thought the language definition screams "parallel", so I'm surprised this question even came to your mind.

That's do-able, at some cost, but building restrictions into a language can easily affect whether folks want to use it.

Even if some folks find Aha! too restrictive, I think there is a wide class of tasks where using it is a very good idea.

I'll try to explain again why I see recursion as a problem. Aha! is based on a simple idea that every program, or even an individual statement (simple or complex) expresses the condition that it must satisfy, or fail. It is therefore crucial that the statement terminates in a finite time, otherwise we can't decide whether it's going to succeed or fail. That's why I prohibit non-terminating loops and recursion. To this date, I believed that recursion wasn't even possible because of other restrictions, but it appears I could be wrong.

For example, you would be unable to implement Scheme or Smalltalk in Aha! if you succeeded in shutting down recursion.

Well, that's questionable. Are you talking about an interpreter? While Aha! wouldn't permit a program to run without a response indefinitely, nothing prevents it from creating an interactive loop. You can read about this in the FAQ, for example.

Thanks for a polite followup, but I'm tapped out of useful ideas. I hope I didn't give offense in my casual comment about concurrency. I missed the way the definition screams parallelism by not reading it; my mind was hijacked by "recursion not possible" when I was skimming, and I wanted to hear more. It was nice of you to cater to my impulsive one-issue outburst.

I think you underestimate just how difficult this could be. You could keep functions in a table, but that would not account for recursive creation of functions that are each slightly different.

Consider some termination analysis techniques developed for term rewriting.

No correct examples proving that recursion is possible in Aha! have been given so far. I still believe it's not possible. But to be sure, I need to work on a proof - ideally, a formal one.

Okay, you've got an internal state, polymorphic functions that can change the internal state, 'interfaces' that describe a set of these functions, and an externally visible state which is a function of the internal state.

Yeah, looks like objects to me. Some other folks may hold out for inheritance, but I say being able to have multiple implementations that satisfy the same interface counts.

Now, tell me; aside from being able to state that something "is object-oriented," have you tried programming with these objects? Do they accomplish the tasks you need objects for? 'Cos that's way more important than whether you've met some arbitrary definition of OO.

Ray

Yes, I know that it 'looks like objects'. It's not important to me if my language is considered OO or not - in the Tutorial, I even note that Aha! "can't be considered an object-oriented language"! It is clear to me that OOP, or its particular definition, has been hugely over-hyped in the last 20 years.

I also agree that the only thing that matters is whether this model can be successfully used in practice. I haven't completed any large projects in Aha! yet, but so far the model works very well for me.

I have been lobbying for an update to the definition of OO:
http://wcook.blogspot.com/2012/07/proposal-for-simplified-modern.html

Note that "functional programming" is becoming as ambiguous and confusing a phrase as "object-oriented programming".

Also, we are just entering the era of widespread functional programming hype. (There has been lots of FP hype before, but nobody was listening.) I predict that it will be overhyped in the next few years until it gets to be just as bad as the OO hype.

Sigh.

How is FP becoming ambiguous and confusing?

(I'm not saying that it's not -- I just genuinely wasn't aware that it was.)

There are at least three definitions floating around. We can consider what "functional programming" is, and what a "functional programming language is".

I've been trying to understand the evolution of the term. When I heard it in the 1980s I was pretty sure what it meant, but when I hear somebody use it now, I'm never sure what they mean.

1) A functional programming language is one that has first-class functions
Usually higher-order functions are required too (but mutable state is fine)
This was the common definition up until about 1980, in my estimation
"functional programming" meant using one of these languages
Originally this Included Lisp, Scheme, ML (and Smalltalk, although nobody mentioned it), etc
But now almost all languages have first-class functions, so the definition is not
very useful any more.

2) Function programming is avoidance of effects, or limited effects, or controlled effects
A functional programming language is a language that eliminates or controls effects
Includes Haskell (mostly), ACL2, Agda, (and many experimental languages) etc
This definition started gaining prominence in the 1980s and is fairly common now

3) A style of programming that emphasizes the use of (higher-order) functions and tends to avoid effects
You can do functional programming in many languages, and its not meaningful
to say that a language is or is not functional, because most languages have a
subset that satisfies either definition #1 or definition #2. I've heard it said that this
style could be called "function-first" or "function-oriented" programming.

Note that ACL2 is strictly functional in the 2nd sense (more so than Haskell, because ACL2 prohibits the effect of nontermination) but ACL2 is not functional in the 1st sense, since it does not have first-class functions! Scheme and ML are functional according to definition #1, but not so much under definition #2. Whether Erlang is functional is something that I have wondered about! It does control effects to some degree, but it still has global mutable state, and it has functions too. My point is that the definitions are not so obvious as they might seem.

Wouldn't it be best to think about FP in terms of executions dominated by function application? Its like in C#, I'm writing some imperative and then I come to a line of code where I break out some LINQ to compose 4 or 5 functions together into a value that I then iterate over. I've briefly gone from imperative to functional and then back to imperative programming again.

Most languages are difficult to classify because they allow you to do more than just FP. Even Haskell with state or IO monads...ya, you are using functions, but the execution model in your mind is (or shoudl be) much more imperative at that point. Yes, Haskell heavily promotes the FP style, but you can still transcode many other styles on top of it.

So my point is, code can be functional, not programs or languages.

In my opinion, the fact that 'purely functional' languages like Haskell need to resort to effectively imperative constructs like monads is an evidence of the immaturity of FP, the language's weakness and not its strength. Going back and forth from imperative to functional isn't going to solve many (or any) of the problems of modern programming. One can't sit on two chairs at the same time.

In Aha!, there's no 'world state'. An application has an immutable state (a reflection of the business model) and a set of functions of two types: ones that provide information to the environment (e.g. messages displayed depending on the app state) and ones that generate new app state on various events (such as input from the user). This approach completely turns over the style of programming interactive applications, but it's the right way to do it. The main advantage of it is the complete separation of the concerns; e.g. the code that displays messages to the user is located in a single place and is not spread over the entire application's source code.

Some problems are intrinsically imperative, and their most natural solutions are imperative. Some problems are not imperative, and imperative is abused to solve them, that is where imperative programming gets a bad rap. Also, sometimes I de-functionalize my C# code just so I can debug it; turns out data-flow obscured code is much harder to debug than control-flow obscured code! One can definitely sit in two chairs at different times.

Very interesting. I'm thinking about doing something similar in the context of live programming, except that events create new "code" that get's executed in the program as if they always existed. It is quite limited however, in that you really do want to distribute logging throughout out your source code, so..much more work to do.

Some problems are intrinsically imperative, and their most natural solutions are imperative.

How we break features and requirements into problems is influenced heavily by our tools and abstractions. We developers choose our own problems. One might ask, given an imperative problem, whether we could exchange it for a declarative or functional problem if we just step back a little (or a lot).

How about: raise employee X's salary by $Y effective next month.

Of course, the declarative description of that is "employee salary increases over time as their performance increases." But processing that logic by a computer is impossible, and besides, it involves subjective made by a human somewhere. Or to put it another way, a user often has to "push" a button in UI, an inherently imperative operation, which must be dealt with imperatively somewhere (perhaps in an encapsulated procedure that someone wrote), even if button pushes are represented as an event stream. My point is that most of our solutions have necessary imperative components that have to be dealt with somehow.

Edit: often the only way we can get away from imperative logic is to bury it somehow (FRP); stepping back to a higher-level problem doesn't always work.

You seem to have leaped several levels of abstraction when switching from imperative to declarative. (I wonder if this is a common thing, that people think declarative is hand-wavy and high-level then turn it into a self-fulfilling prophecy.)

Declarative is about structure, not content. The relevant structure is that our programs are described as sets of declarations. Declarations can be recognized by their extensional properties: declarations are associative, commutative, idempotent, and monotonic. (Declarative does not imply `pure`, which becomes pretty obvious if you study concurrent constraint programming and similar.)

Your "raise employee X's salary by $Y effective next month" describes a non-idempotent action. (Addition of $Y does happen to be associative, monotonic, and commutative with other additions.)

An expression that achieves the same functionality is: "On 2012 October 1, employee X's salary is $Y greater than was employee X's salary on 2012 September 30". Here, I am effectively using a temporal logic (see Dedalus). This expression has all the properties of a declaration: it is idempotent (can be repeated without changing the program's meaning), commutative (with other such expressions), monotonic (can be added to a system without a destructive update), etc.

a user often has to "push" a button in UI, an inherently imperative operation

HCI can be understood in terms of a "human, being" rather than a "human, doing". Buttons have state that is sometimes up, sometimes down. This state is strongly correlated to the position of a human finger.

Is this view somehow less valid than your imperative one? Might it be more useful?

A single button press event is easy to recognize in an imperative system, but what about a chord (keyboard claw)? It can be easy to write declarative recognizers for arbitrary human gestures (especially if we have probabilistic logic and temporal semantics).

Further, we'd do well to avoid button abstractions anyway. Consider using a stateful abstraction instead, such as a checkbox instead of a submit button. If you want undo, cooperative work, UI mashups, synchronization across shoddy network connections, etc. then the stateful abstraction is very much superior.

My point is that most of our solutions have necessary imperative components that have to be dealt with somehow.

We can write adapters. Long term, we can create declarative operating systems and even declarative down-to-the-metal CPU, device, and network protocols. But, right now, we cannot fully ignore the imperative stack upon which we build our applications.

We cannot ignore imperative, yet, but we don't need imperative for anything. There are no "inherently imperative components" outside of human invention.

First my definitions: imperative code is aware of discrete points in time, or at least discrete orderings (X must occur before Y). Declarative code abstracts over those points; it is order and time free. Functional vs. imperative is a meaningless comparison with this definition, so perhaps we are arguing about the wrong things. Even temporal logic is a bit wonky to me because it has facilities that expose logic directly to time.

My point is that we have to solve imperative problems today, and imperative code is the most direct way to do that, in fact, its the only way to solve the problem, even if the imperative code is transcoded on top of some other paradigm. It is definitely true that some imperative problems are "worse" than others, and when we think about monotinicity, idempotence, etc...we can write some nice code that isn't so difficult to deal with, but actually that code still has imperative attributes. In your solution, the constraint is not imperative, but the timing of the constraint (when the constraint "starts") most definitely is.

I'm quite tired of figuring out how to contort my solution using elegant yet inexpressive paradigms that ideological languages are heavily biased toward. Really, if the solution is always "think about your problem differently," then its no wonder these languages are very niche.

There is a big difference between modeling time as a common part of many problem domains (as done by temporal logic, temporal databases, FRP, RDP, temporal generative grammars, temporal concurrent constraint, etc.) vs. implicit time as part of the computation model (procedural, message passing, event systems, state updates, etc.). In the latter case, time is a pervasive effect. In temporal logic, time is very little different than any other attribute, except (sometimes) for a few constraints on expression to enforce causality or support garbage collection.

But, yes, using your awkward definition of the word, we must use "imperative" code to model any problem with a date type.

the timing of the constraint (when the constraint "starts")

Constraints don't "start". Constraints "are". If you do put a starting time on my constraint, it should be when I wrote it (2012 September 10).

elegant yet inexpressive paradigms ... are very niche

Imperative is neither elegant nor expressive (in Felleisen's sense of expressive power). But it has excelled by being close to the machine, controlling performance, and supporting open systems. Most declarative paradigms (even using my definition, which allows use of time values) have failed at those critical aspects.

The "think differently" aspect is, I think, less an issue. Developers struggle to learn imperative, struggle with frameworks, struggle with cache maintenance, struggle with persistence, struggle with reentrancy and concurrency. Imperative programming is one hurdle after another, and each one requires you to "think differently". But if you've already passed many of those hurdles (or think you have), you don't think about them.

What we need are declarative paradigms that is elegant, expressive, that keeps an iron-fisted control over performance, and supports open systems. RDP is my own work on that.

data-flow obscured code is much harder to debug than control-flow obscured code

Of course, it is, when the tools you have support primarily the imperative programming style!

you really do want to distribute logging throughout out your source code

Why would I want to do this in a declarative language? I think you underestimate the impact of the paradigm on the entire process of software development, including debugging.

Actually, logging in a declarative runtime framework could be implemented quite easily. For example, in Aha! terminology, it could be implemented as an 'application extension'; one of the benefits of this approach is that the entire logging subsystem (extension) could be simply removed when not needed.

Its funny how declarative programming usually means "no debugging" or "obscure debugging;" it often amounts to debugging the imperative implementation of the declarative run-time itself! How do we even think about debugging code with no control flow?

Or to put it another way, what is a decent debugger look like for Haskell? I'm really hoping someone will come out with a link about a great debugger; I haven't been able to find anything myself!

I haven't really grocked Aha yet; there is a language manual and some examples, but I don't see anything on "what" exactly Aha is that makes it unique and interesting. Please consider writing some kind of manifesto or design philosophy document.

I haven't really grocked Aha yet; there is a language manual and some examples, but I don't see anything on "what" exactly Aha is that makes it unique and interesting. Please consider writing some kind of manifesto or design philosophy document.

Thank you for the advice, although I'm surprised to hear there's nothing on the site on what makes Aha! unique and interesting. Even the Getting Started document contains a list of features, some of which are unique to Aha! I believe. The modest examples also give some good insight into the features and the proposed programming style.

Laundry list does not a manifesto make. Save your reader some time and emphasize what is new/novel or, at the very least, what you think is better. A top-down description of your language starting with constants doesn't really help. Just dive into the interesting parts without worrying too much about details.

I just want to clarify about the Getting Started doc: has it too much detail or is not detailed enough? Or is it poorly written? You would help me a lot if pointed precisely what is wrong with the existing docs.

Your getting started doc is pretty mundane: you mention standard features like garbage collection, modules, higher-order functions. This is fine for a real getting started doc, but doesn't work well as an abstract for why I should care. First decide who you want to care, then tailor your message based on what they already know. For example, if you want to seduce Java programmers, you would start by comparing to Java. Reading your doc, I don't think you have an audience in mind. The PL research audience is the hardest to impress, but you can assume they know all the significant languages.

The next step is to emphasize what is cool about your language (compared to what's out there already), show us you aren't just itch scratching. A nice example helps, bonus if you can show a comparison.

Thank you very much for this. I will rework the Getting Started doc.

I suggest adding a separate manifesto or design philosophy document that solely focuses on "why we should be interested in Aha!".

Examples:

• The boo Programming Language
• The Flow language Manifesto
• Griff
• Circa Lang - they have a design philosophy, but really their whole site is about promotion.

Thank you for the good advice about the getting started guide. I'm working on a new version of it that will be a lot more informative and interesting to read. I will let you know when it's complete. In addition, the second draft of the Language Reference is coming too.

I've been thinking for some time about docs, after contemplating a new hobby project for over a year. (I don't expect to learn anything from it, so I need a pragmatic expectation about what it aims to achieve. I think what you say about a project strongly influences whether others find it useful.) If no suggestion below appeals to you, just ignore it, or adjust to taste.

One document should be professional in tone, the way you write at work, and may therefore be boring compared to a creative effort. But this document can be made more interesting by speed, say by blitzing quickly through points. Jaded audiences are easy to bore through verbose precision, especially if it sounds like something heard before. Very fast breadth, like an extended abstract, can give folks a reason to keep reading or dive into further detail.

Another far more creative effort can aim to simply be interesting, because the other boring professional document provides backing substance. For example, you can write a dialog between characters, and feel free to get slightly wild. This fun document can cause folks to read the boring one, because they want to see what the characters are actually discussing, without the creative distraction. If you can't make a project sound interesting (indirectly) in screenplay format, that's not a good sign. You can dramatize why anyone should care about a technology by having characters say why they care.

Designing good characters is hard, though. I have a small number I plan to use in my next docs, and you're welcome to use these or mutate them to fit your needs. The goal is to cover very different perspectives, but still have all of them be useful and realistic if you adopt the right perspective. (I don't recommend having an idiot character as a foil, because it's bound to offend somebody.) I plan to include a troll named Crash, but that one's probably hard to keep useful.

The list so far is all guys: Wil, Dex, Ned, Ulf, and Crash. Wil is most "normal" and represents a reasonable and conscientious developer who's just determined to get things done. Sometimes his justification for a tactic is, "Because I can." Wil is biased towards crafting things perfectly, so he worries about too much detail. If someone's an efficiency freak, it's Wil.

Dex is always right, and he knows because he only does things other folks say is the right way. He's driven by whims of fashion, and basically lives in fear others will say he's wrong. Dex is most likely to say you should never write an original line of code, that development is mainly use of existing software with the best reputation now. Invention gives him the willies. He's convenient to cite chapter and verse of some precept you plan to violate.

Ned only worries about things going wrong: bugs that are possible under the current plan. He's most apt to notice something can still fail despite best intentions and careful design. Ned tends to explore the space of what happens when code is abused or misapplied, and may resort to whining abuse is still possible. Ned's refrain may resemble, "But it's not bullet-proof yet."

Ulf favors quick and dirty results, and rarely worries about resource use. He says resources are someone else's problem, and his compiler uses 2GB of RAM when compiling 100K of source code. But hey, nobody was using that RAM, so why not? Ulf only designs code that works in build environments with plenty of resources. Wil won't let him touch anything in the production server. Ulf is useful to present prototypes grossly wasting memory or CPU cycles in phases when it works.

Crash is chronically bored out of his mind and says odd things for entertainment. He can only get a rise out of others by staying serious long enough that lunacy is contrast. (Crash shaves his head and has crash test dummy tattoos on both sides of his head. When asked about this, he lies, usually about his job as a crash test dummy.) If someone's a lunatic, it's Crash.

You can probably use them very sparingly as flavor text embedded in something more dry, to motivate a more careful treatment in non-dialog format. That's what I plan so far. If dialogs never suit you, maybe you'll think of something else to break up your format instead.

Oh my gosh, not "Why's poignant guide to Ruby," please! Unless you are a literary genius (and many of us are not), go with a basic formula, and to be honest, some people won't get it.

I'm totally going to try the dialog/comic strip approach myself in a future publication. But really, its something you should work yourself into over time.

Don't know Why's stuff, sorry. I gather my suggestion sounds like imitation.

Not at all, it sounds very cutting edge. But its something to play with once you've mastered the basics of communication; in this case, I say something simple would be sufficient to get started, and if you feel more creative later, great!

If you ever read Why's guide, be prepared to be baffled and shocked, its very post modern. Also see Bret Victors scientific communication as sequential art for something that is more effective.

You can get a direct link to most (maybe all) of Bret Victor's articles by eliminating the shebang. Much better performance that way. (Bret Victor's site moves terribly slowly on my machine.)

Dialogs strike me as safe, staid, and slightly high-brow, while cartoons are risky and low-brow enough to flirt with chancy reception. I wasn't thinking about cartoons in docs, but Why's usage was fun.

Sean McDirmid: If you ever read Why's guide, be prepared to be baffled and shocked, its very post modern.

I skimmed and it's quite interesting. The troll character Crash I mentioned actually comes from a half-designed comic strip I'm not sure I'll pursue named Vengeance Elf, where Crash is an occasonal sidekick. I was playing Skyrim a couple months ago and named a wood elf character Vengeance as a play on girl names like Charity. Next thing I knew, the idea morphed into a strip about a fantasy-prone girl named Vengeance (last name Elf) with pointed ears who either thinks she's an elf, or actually is one (never clarified). Guy: (joking) "So what kind of elf are you?" Elf: (showing ear) "A wood elf, obviously! Duh!" Guy: (stares, thinking).

She's a mildly violent do-gooder righting social wrongs with a fly-swatter (for example) to express censure, or someone's car antenna if they park diagonally across two spots. Dude: (backing up) "It's her." Guy: "I have a toy just like that on my car's antenna." Elf: "This is your car's antenna." Guy: (worried) "Are you going to hit me with that?" That's a common question. Witnesses may occasionally suggest, "Run!" If the cops are called, they just want her autograph, no matter what she's done.

I don't see any way this fits in tech docs, though, unless irrelevant comedy relief works, or it helps make one of the dialog characters less abstract. For example, seeing Crash in a strip like the following gives dialog readers an image to associate with him. Max: (snarky) "And you are?" Elf: "Elf, Vengeance Elf." Max: (smoothly) "Are you a dish best served cold?" [Closeup of Max's face, as Elf pokes him in the eyes three-stooges-style. Max: "Gah!"] Crash: (lecturing) "Revenge is served cold, you idiot."

Late one night Sandy and Pat go out on a date to the theatre to see a new play based on the lives of Charles Babbage and Ada Lovelace, drink almost enough wine, and wind up taking cabs back to their separate apartments, where they each have peculiar dreams....

In the morning, Sandy calls Pat, saying "This is totally weird, but in my dream I actually saw the function for Love! It's a binary function in seven variables, but now that I'm awake I can't remember the details of it."

Pat, who by an amazing coincidence (or possibly a plot device, it's hard to tell) has had a similar dream, inquires, "Was it a pure function?"

Sandy responds, "Yes. Yes, I'm certain that it was."

When the conversation is over, Pat quietly and sadly hangs up the phone, resolving to stop dating Sandy. According to Pat's reasoning, only false love is pure. If Love is True, it darn well better alter its arguments.

.....

But as Shakespeare's sonnet 116 said
"Love is not love. Which alters when it alteration finds,"

So obviously love is not an impure function.

Love often gets impure eventually.

Could you clarify what you mean by "effectively imperative constructs like monads"? Monads can be (and are) implemented using pure functions -- what is imperative about that?

I also don't understand how the ability to implement and use monads is a weakness of FP?

Monads can be (and are) implemented using pure functions -- what is imperative about that?

I think there's something wrong with the assumptions in your question. Consider turning it around: Shall we say that functions are imperative because they can be (and are) implemented using imperative C or x86 code? (what is pure about that?)

"Pure" and "imperative" are properties we attribute to abstractions. The implementation of said abstractions is irrelevant.

Developing code in `State` or `ST` - i.e. a mini-language described by the monad - is still imperative, even though there are "pure" implementations. Conversely, many Haskell functions are "pure", even though GHC provides "imperative" implementations.

I have seen the the same confusion from many Haskellers. But this is ever so simple. How can it possibly confuse anyone?

I'm sorry, I don't quite understand. Could you explain more?

What more is there to explain?

The structure of your argument is "X can be implemented with Y which has property Z, therefore X has property Z". In your case, X = some monads, Y = function, Z = pure. And you want to believe it, so you look no further. However, that logic is simply invalid. You can prove it is invalid by finding an example where the argument clearly doesn't hold, such as: X = fibonacci function, Y = x86 code, Z = imperative.

Throw that bad logic away. It's probably a source of more than one confusion for you.

In general, properties are not transitive across representations or implementations. I.e. the map is not the territory.

When we say functions are pure, we are speaking of various external features of the function abstraction: the ability to commute computation of functions, or to replicate computation without changing behavior, or to replace a function with the result of the computation. When we say a particular monad is pure (and there are pure monads such as Identity), we must (lest we equivocate) be speaking of the same properties. But monads in general only promise associative composition. Monads, in general, are impure.

You're misstating why it is that Haskell programmers think of their programs as pure; it's not because they can be implemented with functions. Rather, it's because the values being considered don't change. For example, a Haskell programmer does not consider "account balance" to be a changing value, and instead works with the unchanging monadic value "get account balance." Of course such a programmer may have impure thoughts, but that's merely a venial sin.

Haskell offers developers many valuable reasoning advantages by eliminating pervasive state and controlling where effects can be expressed. A significant fraction of program logic in Haskell can be expressed in pure functions. And Haskell is excellent for metaprogramming, e.g. using pure functions to build an immutable, imperative IO program.

But to confuse immutability with purity is a rather significant error. And I think many Haskell developers who have this confusion are simply parroting assertions without really understanding the words they're using. It makes me feel disgusted and annoyed.

Maybe Haskell developers would be more consistent if their type system was. Seems they grokked Curry Howard and think they can claim anything by leaving a few words undefined...

(I am a developer who uses Haskell. I quite enjoy it. But there have been many days where I contemplate switching to Agda.)

The last points of my previous post were tongue in cheek, but there really is something I'm not sure that you see. If you are just arguing that monadic programs have most of the same issues as imperative ones then fine, I'm not going to argue with you. Most Haskell programmers understand this, by the way.

The reason Haskell programs can be considered pure is that a Haskell programmer is set up as a meta-programmer of sorts. A value in IO is an imperative program. A Haskell program that builds a value in IO is a pure meta-program. Suppose you write a Haskell program that returns a String, which is to be interpreted as a C program. Is your Haskell program pure? Remember, the map is not the territory (or in PL parlance, the expression is not the value).

The C and IO example is something I've used repeatedly in discussion with Haskell developers and they rarely ever get it. Now, I'm sure much of that is a biased sample: the people I engage in such discussions are not the type who get this. Those who I engage will often insist, quite vehemently (and with a quick trigger on the Haskell redd.it downvote button, and many friends who think like they do), that the IO program is pure because it is an immutable value and was presumably created in a pure manner. Presented with the C-containing string example, they think "WTF does that have to do with Haskell?" (And a few clever bystanders will inevitably point to Conal's blog then wonder off.)

I know that you understand this. Just don't care about it anywhere near redd.it, and you'll be fine. ;)

The notion that a Haskell programmer is a "meta-programmer of sorts" is not that accurate with regards to IO or other monads. Typically, execution of an IO value is interleaved monadically with its pure expansion. This does not correspond to the C-containing string example: we do not execute a C string interleaved with its construction. It is unreasonable to insist that most of a typical IO program is created by pure computation.

If developers were to primarily use Control.Applicative to build their IO programs, it would be far more reasonable, I think, to call it staged metaprogramming. The recent Haskeller interest in "free" monads (which are the GADT variation of William Cook's Object Grammars) would also qualify.

It sounds like we probably agree on almost everything except how to say it. I prefer "Haskell is pure. IO is not." (A point that I really botched explaining in the comments of that Conal post -- no wonder he was annoyed at me).

I also agree with your sentiment in the last paragraph in that the amount of imperative flavor present depends on the way in which the IO program is built. But consider it from another angle: Whatever declarative constraint programming method you have in mind can be viewed as a way of building imperative programs in something like IO. Does that make your declarative constraint language imperative?

Programming with imperative abstractions will be imperative programming regardless of the host language. Even if hosted in a declarative constraint language, all the reasoning and refactoring I can perform would be constrained by my use of imperative abstractions.

Consider: if I express an immutable string containing C code, I cannot simply manipulate it as a string because most manipulations would result in an invalid or incorrect C program. Construction, refactoring, and reasoning about that string depends heavily on C's structure and semantics. The fact that C is hosted in a string is irrelevant. As far as a perceptive programmer is concerned, manipulation of that string is still imperative programming.

Here's what matters to our programming experience: the properties of the abstractions we programmers manipulate, construct, reason about, or refactor.

(OR: imperative programming is something programmers do, not something machines execute.)

Now, direct use of imperative abstractions is not the only way to use a declarative constraint system to build an imperative program. For example, I could abstract a capability-secure Hoare logic with preconditions, invariants, and postconditions, then use a constraint system to build a logical proofs - which just happen to be an imperative program. This would not be imperative programming, because I would not be manipulating imperative abstractions.

To say "Haskell is pure" mistakenly attributes to the full Haskell language a property that is true only of a few standard abstractions in that language. IO is as much a part of the Haskell standard as are the pure functions. And IO is far from the only imperative or impure abstraction used regularly by Haskell developers. But I do believe we could justify an assertion that the Haskell language and community encourage purity where it is feasible, and encourage careful control of effects where purity is not feasible.

You're arguing that Haskell supports imperative programming and thus isn't pure, but I don't see those two as mutually exclusive. It's pure and supports an imperative programming style. That's how I'd say it, anyway. IO values are impure, but IO values aren't Haskell programs.

I'm arguing that to call a language "pure" is a category error. It's a language that supports both purely functional and imperative abstractions and programming styles.

Also, Haskell programs are IO values. It's right there in the Haskell Report: Chapter 5 Modules, paragraph 2:

A Haskell program is a collection of modules, one of which, by convention, must be called Main and must export the value main. The value of the program is the value of the identifier main in module Main, which must be a computation of type IO Ï„ for some type Ï„ (see Chapter 7). When the program is executed, the computation main is performed, and its result (of type Ï„) is discarded.

How would you define "pure" then? As I argued in the comments to Conal's blog you linked to, the only way that "pure" makes sense to me is as a description of a semantics: all of the values of discourse are immutable.

Also, that quote doesn't say Haskell programs are IO values. It says the value of a program is of type IO. "The expression is not the value."

A subexpression is "pure" when the only meaning of that subexpression is its value, i.e. the result from evaluating it. This results in the following extensional characteristics:

1. We can replace a pure subexpression by any other pure subexpression that evaluates to the same value without changing the meaning of the surrounding program.
2. We can remove a pure subexpression from a program if we do not need its value, and to do so will not change behavior of that program.

The second characteristic is stronger than all the declarative properties combined (idempotent, commutative, monotonic, associative). We have much declarative ability to reorder and refactor `let` expressions, which are always pure in Haskell.

Pure abstractions are abstractions that only admit pure subexpressions.

The notion of pervasive mutability is orthogonal to purity. We could have mutable values with a pure program if we forbade aliasing (as with linear programming models). We would understand values as being mutable configurations, then. Any expression that returned the same mutable configuration would return an equivalent value.

Also, that quote doesn't say Haskell programs are IO values. It says the value of a program is of type IO. "The expression is not the value."

True. A program is ultimately one big expression, built of subexpressions. "Imperative" is a property of expression.

If I use pure non-imperative subexpressions to describe and reason about the bulk of my program's logic, I could reasonably say my program is not significantly imperative. OTOH, if I express a lot of logic in IO monads and event loops, my program will be heavily imperative.

I also don't understand how the ability to implement and use monads is a weakness of FP?
I didn't say that. I said that it's a weakness of a particular language, not FP in general. I consider monads a way to bring the imperative style of programming into a purely functional language, which completely defeats the purpose of functional, or declarative, programming.

My goal when designing Aha! was to fully part with the imperative style of programming. To see how I've done this and whether I succeeded, one needs first to read the materials on my web site.

I would tend to disagree that that's a good way to characterize FP -- what if the "functions" you've composed have side effects, or kick off concurrent threads that mess with shared data?

I think the more essential aspect of FP is referential transparency. Put the same thing in, get the same thing out. Always.

We can also write pure (referentially transparent) functions in C#, unenforced by the language of course, but when we apply and compose those functions, it is pretty much functional programming. How is that controversial at all?

Are we just arguing about what the language should enforce to ensure that code is really functional?

Then there is the whole mess of imperative programming with explicit side effects, technically these functions referentially transparent but the programming style is obviously still imperative.

Sorry, I don't quite understand your post.

I think what I'm trying to say is that the "what" of FP is referential transparency, and the "how" of FP implementations is typically functions, function application, and immutable state.

So maybe what I'm trying to say is that functions and applications don't imply FP, if there's no referential transparency. Or maybe not. I'm not sure. Sorry for equivocating.

I argue that FP is more about intent than mechanism, and then I think we are almost in violent agreement. You could have access only to referentially transparent functions and still transcode imperative or rule-based programming on top of that. It might not be pretty, but you'd be surprised how often people do this to "game" their language, so to speak. In that sense, Haskell is definitely biased toward functional programming, but its not limited to just functional program. Likewise, you can write functional programs in machine code, it just wouldn't be very pretty.

If this were a democracy, I think I'd vote for #2.

Maybe languages that fulfil #1 should be called higher-order? :)

I would propose at least one other definition of "functional programming":

4) The lineage and culture of practice descending from your 1 and 2 and in the context of which your 3 was largely developed.

As I've said here before, I favor a view of these terms that is mostly historical/sociological and not so much technical or rigorous.

I view OOP and FP as being the same kind of term as "Christianity", "analytical philosophy" or "science fiction," terms which in my view are best regarded as designating an ongoing historical conversation and its participants (even as they enter and leave the conversation, try to police the conversation's boundaries and participate in other conversations besides).

All of the trouble starts when one wants to "get serious" about questions like "What do Christians believe?" or "What distinguishes science fiction from literary fiction?" -- questions which of course have no precise answers divorced from historical contingency and the wider culture; although they of course do have broadly useful approximate answers.

Like another well-known cultural category, "I know it when I see it."

(And as I've said before, I realize that this is unlikely to be a very popular point of view.)

Good to hear that your definition of OO meets my understanding of objects that I put into the language :)

I'm not overly concerned about the classification of my language. I hope it took the best of the worlds: OO, FP, imperative, so it's not completely foreign to any of the groups of users. I still insist that it's a declarative language (as in #2 definition above) in the first place. Whether to consider it functional, or object-oriented, is up to one's taste.

we are just entering the era of widespread functional programming hype. (There has been lots of FP hype before, but nobody was listening.) I predict that it will be overhyped in the next few years until it gets to be just as bad as the OO hype.

I'm OK with that. This is just part of the programming language evolution. Imperative programming was born when computers had very little memory, and it has long been doomed in my opinion; FP looks like the most logical alternative to it.