Talk:Unlambda

Okay. Now I understand why s and k are all that's needed: s "distributes" a value between two other values, which can either reject it via k or use it in some way. --Ihope127 04:01, 30 Oct 2005 (GMT)

I invented a slow unlambda interpreter in PHP. Some programs can run fast and some slow. Can you please look and see it? Tell me if is any bugs or anything? http://zzo38computer.cjb.net/esoteric/unlambda/slow_unlambda_php.zip --Zzo38 18:27, 28 April 2007 (UTC)

I don't have php to test it, but the basic idea looks sound although as you say, slow. Apart from your trick of putting evaluated functions in single cells, it resembles how I would evaluate Unlambda by hand. I guess most of the slowness comes from all the array splicing, which seems hard to avoid without using a more nested datastructure. But the flat array is also how you avoid most of the trouble with continuations, so I guess that is a tradeoff.

Apart from efficiency, I would suggest a change to the e function: The specification says that the argument is the final result of the program, so you might change the code to (assuming I understand php and your program correctly)

$s=array($s[$i+2]); $i=0;

--Ørjan 06:23, 29 April 2007 (UTC)

Well, I fixed the e function. I didn't have time to change other things right now. --Zzo38 15:17, 29 April 2007 (UTC)

My attempt at compiling Unlambda to D

I've written an almost working Unlambda to D compiler [1]. Although David thought the d builtin would be difficult or impossible to compile, I actually found it straightforward with the help of D's lazy parameters.

What I can't get working right is c. Using exceptions, it works if the continuation remains within the c call. David suggested using continuation passing style, but it seems that this would stop the implementation of d from working.

It ought to be possible to get it working using the C setjmp API. But so far, my attempts at getting setjmp to work in D haven't been successful. [2]

Does anybody have any thoughts on this? -- Smjg 17:41, 15 July 2007 (UTC)

Note that the d function as implemented in most Unlambda interpreters (I vaguely recall Jacob Mandelson's interpreter getting something about this wrong) does not remember the result of evaluating the expression - it is reevaluated each time `dE is applied. The specification may not make this clear, so I thought I should warn you, especially if you are using another language's builtin lazy evaluation.

You may want to look at my Unlambda to Ocaml "compiler" - it is merely a proof of concept (as I recall, it's not even faster than the Ocaml interpreter), but it does show one way of doing the d function, by letting Unlambda functions take an unevaluated expression and a continuation as parameters. --Ørjan 21:08, 15 July 2007 (UTC)

I'm not familiar with OCaml, so it's going to take me a while to make sense of your work. But still, my implementation of d does work. What actually happens with D's lazy parameters is that a function delegate is generated from the expression passed in. The implementation of d saves this delegate for later use; for everything else, it evaluates it there and then. See runtime.d. BTW, while I've used the declaration style

Function opCall(Function delegate()[1] exp...)

the more usual style for lazy parameters in D is

Function opCall(lazy Function exp)

which generates a delegate in the same way, but doesn't provide a means to extract the delegate. Rather, it evaluates the expression each time it is referenced in the function body. -- Smjg 13:55, 16 July 2007 (UTC)

Ok, so it's call-by-name laziness. It would only be a problem if it were call-by-need, evaluating only the first time. --Ørjan 18:08, 16 July 2007 (UTC)

Another thing, in Unlambda continuations are essential every time you do input. So you don't want them to be too expensive, especially since Unlambda can force you to use it many times per character, once per value you compare it against. --Ørjan 21:23, 15 July 2007 (UTC)

Every time? The cat example takes input, but doesn't use continuations at all. But I'll believe you that you probably need to use continuations if you want to do any real manipulation of the input rather than merely outputting it. -- Smjg 13:55, 16 July 2007 (UTC)

Right, it's when you use the ?x function. --Ørjan 18:08, 16 July 2007 (UTC)

Actually I no longer think native c-based continuations are strictly essential for real input manipulation, I think it is possible to use continuation passing style and e to avoid them. --Ørjan 02:18, 10 August 2011 (UTC)

I've now more or less figured how I would go about implementing CPS in D such that it would support c and d. It's basically a matter of applying the functions together in a similar way to your OCaml effort.

But there's a caveat: what I've come up with seems to make the code as much like data as code. The output of my existing Unlambda to D compiler already treads the line between code and data, but I think it's still more like code, in that evaluation is on the fly. I think the only real shortcoming is that the generated code manipulates class objects rather than functions, because D doesn't support either function currying (except by this indirect means) or recursive function types.

On the other hand, in my new design, the applications are essentially building up a data structure that is then applied to the default continuation in order to evaluate it. The continuations also become data structures. This is probably a consequence of trying to do this in a procedural language rather than a functional one.

That said, my guess is that functional language compilers tend to turn certain things into data structures anyway. But that is indeed a guess. Moreover, in what I'm thinking of doing, the structures would still directly reference the class objects in which specific functionalities are implemented. So maybe I could still get away with it to a point.... -- Smjg 18:39, 22 July 2007 (UTC)