Lambda the Ultimate

In the Cat language I found it neccessary to have primitives which have embedded values. For example store#N would place the value on the top of the main stack into the Nth position in the auxiliary stack. There are currently a couple of other primitives like this.

Upon examination, this syntax yields a limitation: you can't use an expression in place of N. For example: store#1 + 2 doesn't really make sense. This lead me to consider the notation: store<1 2 +>. This isn't perfect, but it has a certain familiarity which I am comfortable with. This also extends relatively nicely to primitives like: local<int>, which pushes a new integer onto the auxiliary stack.

When I step back and look at this differently, I am embedding compile-time expressions between angled brackets (lt; and >). This makes the language specification more complex because the semantics for compile-time code are necessarily different from those of run-time code. This leads me to ask the question, shouldn't I allow compile-time or type expressions to be expressed using precisely the same syntax as the rest of the language? In other words why not place types on the stack, and if a type-expression can be resolved at compile-time, then let the compiler do so.

The only problem that I can see is that some expressions are not resolvable at compile-time, but this would simply lead to dynamic type expressions. I can see people potentially getting confused about what expressions can be evaluated at compile-time, and which ones are evaluated at run-time, but does it really matter?

It seems to me at this point that freely intermixing static and dynamic typing and evaluation is the right thing to do, but I'd like some feedback and other points of view.

Hello All,
I recently happened upon the paper Prototypes with Multiple Dispatch by Salzman, and I decided to try implementing my own version of the PMD model he described in Scheme. As an extension to his model, I've added in support for CLOS style Method Combinations, such as the :after, :around, :before, and :standard dispatch orders.

Now, as near as I can tell, there haven't been any whitepapers written on the subject of combining PMD with Method Combinations, so I thought I'd ask you guys: Have you heard of anything like this? Even if you haven't, are there any pitfalls or oppertunties that you might be able to point out regarding this?

Thanks,
rhat

Edit: corrected ommision of the word "out".

Doctoral thesis for the degree of Doctor of Philosophy

Fudgets --

Purely Functional Processes with applications to Graphical User Interfaces

Magnus Carlsson
Thomas Hallgren

Carlsson and Hallgren's 1998 thesis on functional window gadgets is of course not new. However, I want to call attention back to it because it discusses the idea of an Oracle. I submit that the notion of a system that supplies oracles (as many as needed) from the runtime environment provides the best way to account for nondeterminism/indeterminism in a notation or a framework of reasoning that embraces Referential Transparency. I submit that Oracles should be more on the minds of those who write about designs for pure functional programming languages and systems than they seem to be today.

(Unfortunately, the term "Oracle" in this meaning is not in practice Googlable, because anything you'd turn up would be swamped by the returns about the Oracle brand database management system.)

When I say indeterminism, the kind of indeterminism I'm talking about is the kind where information comes from various sources over rough roads, and the right thing to do is act differently depending on what information happens to arrive first, affecting output. The right thing to do for the sake of the humans the computer is interacting with may also depend on the time required for various calculations. So there needs to be a way to model the fact that a routine needs to ask for a calculation that actually takes up time. A referentially transparent language can talk about what has to be calculated, but it has trouble dealing with the fact that calculations can cost something and sometimes one may finish before or after another, or before or after some system input (e. g., command from human to go get some other information, or maybe to query the status of the calculation, or change the resources devoted to it or the priority of their use, or suspend the calculation, or cancel it).

Given an oracle o from the environment, and two data sources a and b, we can have a function decide, where decide(o, a, b) returns something like (Left, a) if a is available before b, or (Right, b) if b is available first (assume Left and Right are just symbols, distinct from one another). This operation consumes the oracle o and no attempt must be made to use it again. The Referentially Transparent explanation for why this function application is able to determine whether the computation of a or b finished first is that from its magic knowledge from the gods, o knew all along which calculation was destined to finish first, hence the metaphor of an oracle as the term for this concept. Of course, an oracle can't be printed. It's just used once, at the point where the reality of the outcome is going to be determined, and of course the prediction never fails since it can't in practice be tested as a prediction.

An alternative way to model indeterminism in the framework of referential transparency is via the sets of Hughes and O'Donnell. I thank Fergus Henderson for his easy-to-understand explanation of the Hughes/O'Donnell approach. The outputs of indeterminate function applications are understood to be sets of all possible results. The implementation only outputs one of the results, however, at the exit to the system. I used to think I could articulate an argument why this approach will not satisfy so well as the oracles approach. In the Hughes/O'Donnel sets account, intermediate results are not understood to contain any decision about what result was computed (although of course in the implementation, the decision would be made and only its result stored). Since the result contains in concept all the possible results, I'm not sure there is a semantically sound way to think about storing it persistently so as to avoid having to repeat long calculations in case of a crash of the volatile memory. Maybe bye and bye I'll think of an argument again on the comparison of these approaches. Or maybe someone else will.

Does anyone propose a third answer?

It seems to me that in the design of a programming system demonstrating orthogonal persistence (transparent persistency), the consumption of an oracle may be a significant event. Or maybe not, maybe in such a design, all itermediate results are as significant as the time it took to calculate them. The real significant event is system output, because that embodies the decisions taken at all the indeterminate choice points that contributed to the output. Subsequent outputs have to honor those choices.

Lately, Joel on Software's discussion forums have been a hotspot for Lisp discussions, probably because Joel's been learning Lisp and hanging out with Paul Graham from time to time. There's a thread today called Lisp Lovers, how would you fix Lisp or bring it up to date?.

I'd like to ask the same question to people who hang out here. I think it would be best to keep the answers to the question at Joel's forum so it's all in one place.

I've posted my reply to Joel's forum. Please comment on it if you have any thoughts.

I've been looking at Coq and automatic theorem proving for a while, although I'm not sure if I completely understand it. From what I can tell, the idea is to create a core set of routines from which a function can be proven correct, given a detailed specification of what it should do. Is this right, or am I completely off track?

The Cat language has a primitive called while. The while construct takes two functions as argument, an invariant and a variant. Both functions consume the same number of elements from the stack. The variant (loop body) produces the same number and type of elements that it consumes. The invariant produces the same types as the variant, plus it leaves a boolean value on top of the stack. The while loop terminates when the evaluation of the invariant leaves the value false on top of the stack. The while loop pops the value false, before exiting.

So the question is: how should one express this in the type system?

Here is my current proposal:

define while : 
( 
  a:A=any* 
  variant:(b:A)->(c:A) 
  invariant:(d:A)->(d:A continue:bool)
)
  -> 
(
  result:A
)

What is good or bad about this notation? What other possibilities should I consider?

I have long had a gut feel that the ability to algebraic
refactor / rewrite / simplify programs is a killer feature of
Joy / concatenative languages.

See Manfred von Thun's Rewriting System for Joy paper for more info on this.

I have just noted an practical application for this...

Out here in the embedded computing world there is a vast body of Legacy
assembler applications which cannot be ported to new CPU's as the old
parts go obselete.

So how about this for a solution....

Write in a concatenative language of your choice fragments that exactly
duplicate the behaviour of each machine instruction.

"assemble" the assembler source code into the concatenative language.

Algebraically simplify as much as possible. (Quite likely to something
even simpler than the original source!)

Compile the concatenative language to new CPU.

The SQL based database servers have the facility to define dynamic views based on a SQL query. Can we define such dynamic sets in Haskell that are fully specified by the membership criteria? If we have an GUI engine that will handle the display and update to dynamic sets, then we can write the Client Server application using declaratations only. The application logic, GUI and persistence all can work using the same model and without the need to explicitly specify the IO details between various tiers.
Ashish's Niti

In some ML style languages there is no way for a function to be overloaded. Why is this? I have to assume it is related to the type inference engine.

Dear Everyone,

I have been a fan for lisp for a while. But I would like to know what is the most preferable way to start learning Lisp. What is the most preferable environment setting for learning lisp? And before starting to learn Common Lisp,is it good to learn MIT's scheme beforehand?

Thanks for your advice!

Marcus