Lambda the Ultimate

To get right to the point, my main question is:

Is there any guarantee that setTimeout() calls will be executed in the order in which they are requested?

Discussion:

I believe I have made two improvements to the general CPS mechanism that was described in this forum by Anton van Straaten some time ago here. My main questions involve the 2nd adaption that I describe below.

As an amusement, I've been working on a JavaScript-based, client-side maze generator. In order to support very large mazes I've avoided recursion and adapted the aforementioned CPS mechanism in order to maintain responsiveness.

The main adaptions:

1. Using iteration instead of recursion in the loop() function. I found that the Safari browser allows such a small stack that the level of recursion made necessary caused the algorithm to run unacceptably slow.

2. To support nesting of continuations, the continuation function k() is called in the context of a setTimeout(). My implementation of the maze generator involves several passes across a multidimensional array (e.g., initialization, generation, rendering) each of which is a continuation of the previous step. I found the original example did not allow nested continuations since the hand-off to k() would normally be done before the previous stage had truly completed (i.e., before most of the setTimeout() requests had been handled).

The idea behind this change is that the setTimeout("k()", 0) would cause k() to be executed only after all the previous setTimeout requests had been handled. I'm making a huge assumption here I realize, which is that the calls to setTimeout are in essence serialized by the processor. Given the nature of the algorithm, it's guaranteed that the call to setTimeout for k() will happen after all the other setTimeouts requested by a particular stage, but does that actually guarantee that it will be *handled* after all the other requests? In my particular case it works well, but I don't know if this is just pure luck.

If there is a more general way to handle nested continuations (that does not rely on this potentially invalid assumption) I would appreciated hearing about it.

A somewhat simplified version of the iteration function I have employed in my code is shown here:

/*
 * f    - a function that takes a state parameter and returns an updated state
 * initial - the initial state
 * done - the final state that indicates that iteration is complete
 * k   - an optional continuation function that is called when processing is complete
 */
function iter(f, initial, done, k)
{
    var max   = 50; // a reasonable number
    var count = 0;    

    /* define the loop function that will manage the calls to f() */
    var loop = function (state)
    {
        while((state = f(state)) != done) {   
            if (count < max) {
                count++;
            } 
            else {
                count = 0;
                setTimeout(function() { loop(state) }, 0);
                break;
            }
        }
          
        if(k && (state == done)) {
            setTimeout(function() { k() }, 0);
        }
    }
    
    /* call the loop function with the initial state */
    loop(initial);
}

5 minute video - from useful & unsafe and useless & safe to useful & safe

101 Ways To Know Your Software Project Is Doomed may be amusing, but item 28 is clearly meant as a LtU flamebait...

I am doing C# 2.0. Recently I'v struggled hardly with ORM ideas. Before that I was struggling with a add-in architecture. In last 2 years I'v tried to extend my views by digging into Ruby, Haskell, Erlang, ... and even JavaScript more deeply! In many many situations after a hard battle I came across with a "set of elements" idea. Imagine you'v had trapped in a dessert; you will only concentrate what is essential! I felt that and always some lights came to me! Not in form of an angle! In form of a list! Please tell me what's wrong here! I can even think more than this! Were we walking backward in last 20 years to reach lisp??!!

This is a bit premature, the conference papers aren't available on the Clean iTasks website yet, but

• Tasks are statically typed.
• Tasks are fully dynamic: what a task is doing may depend on the work produced.
• One can define user defined tasks.
• Tasks can be defined recursively.
• Thanks to polymorphism and overloading user defined re-useable tasks can be defined.
• Tasks are fully compositional: any combination of tasks made with the combinators can be re-used again as a task.
• Tasks can be higher order: not only values can flow from one task to another, but it can be tasks!

ppt presentation
demos

As part of a move, I recently took a truckload of books to the local used book purveyor, and now have about $350 in credit to use either there or at their sister store, which sells new books (hurrah). I figure this is free license to get a couple of FP-oriented (or other-interesting-software-oriented) volumes.

But I know there have been a few recent books coming out since I last looked at FP books several years ago. I'm looking closely at the new Erlang book by the Pragmatic Programmer guys (not out yet, but soon), and I already have SICP. Most people don't seem to go for Practical OCaml. Is there a "standout best" Haskell book, or any particular book on FP that's just a can't-miss?

I'm afraid I'm doing it mostly for the knowledge, not that I have an application in mind; I'm going into computational physics, and as much as I'd love to see FP languages make headway there, particularly with recent things like Nvidia's CUDA and other such things, it still seems to be primarily the domain of C and Fortran. I guess my point being that I probably don't need deep theory stuff--mostly expand-your-mind stuff.

Any standout recommendations?

Some folks are floating a proposal to hook Erlang to OCaml, in a bid to get around each other's weak spots! Garbage collection is the obvious challenge here; but are there more subtle impedances?

Hello everybody, this is my first post, so please be gentle... (actually i was passive around here for years, and find LtU a great source of inspiration and wisdom).

I'm not at all into dynamic typing, i find static type-checking superior in any way. However, recently i just had the thourght:

"If all I want to write is a single side-effect-free, IO-free, terminating function F(x), with well defined argument- and return-types. And further, if I am able to come up with an x which trigger all branches (selections and pattern matches) of F, then i can get static (compile time) typing of F in a dynamically strong typed language."

Suppose i write F in the dynamically strong typed language, which does the following:

Immediatly after each compile of F, evaluate F(x), (yes, please). If it does not crash (or loop forever) F is type-safe, else report an error. The idea is that type-checking F is no harder than evaluating it on a sufficiently large test set argument.

Is this sound? If yes, what about the next step:

If it shows be the evaluation that F(x) has a strong typing, would it be possible to record all types of all expressions and create G, equivalent to F decorated with type annotations?

I do realize i'm asking for (usually turing-complete) type-infernce for free...

Tom integrates pattern matching and rule based programming facilities into Java. It is particularly well-suited for programming various transformations on trees/terms and XML based documents.

Tom adds new constructs to Java that enable information retrieval and transformation (via conditional rules) in lists and trees. Traversals of trees and transformations are based on a strong theoretical background. Tom compiler is mature enough to be used for large scale developments and applications, and integrating Tom in any existing application is straightforward, as Tom produces Java source code.

Some applications developed in Tom (both in academia and industry):
- requests transformations (ex: XQuery requests' optimizations )
- the Tom compiler itself
- languages semantics, interpreters and program transformation tools
- a generator of canonical abstract syntax trees (Gom)
- a Just In Time strategy compiler using dynamic Java bytecode transformation
- a proof assistant for supernatural deduction
- a compilation algorithm for anti-pattern matching and disunification

A guided tour of Tom can be found here, and the release notes here.

Tom is available, in open source (GPL/BSD License), from the web page: http://tom.loria.fr/

Looking into Halgreen's Fun with Functional Dependencies and Shan/Kiselyov's Lightweight static capabilities, I am curious has there been any work done on prettifying the syntax involved in doing computation on the type level. Has camlp4 or Template Haskell been used in making the syntax for like the native language? Perhaps even maybe more Prolog-like?"

Thanks in advance for any suggestions