Talk:Lazy

Just some thoughts:

• I don't really like having to define separate cases for things like the fibonacci function, but I can't think of any other way to do it.
• I'd like to include lazy lists but I don't want to turn this into a haskell clone.
• I don't know what other built-in functions to include, (or really what built-in functions to include at all).
• I don't know what the best way to handle I/O is. Using an input and output function seems reasonable to me, but so does passing input into the main function (but that would probably require lazy lists).
• Should there be a function like eval(x,y) that evaluates x then y?

I've been thinking about making a language like this for a while, but I couldn't every figure out enough details.

You could add a built-in if(b, x, y) that evaluates to x if b is true and to y otherwise. However that would probably require lazy evaluation of its parameters in order to work like usual if-then-else constructs - to avoid unwanted side-effects and to reduce complexity: if if's parameters are always evaluated before if, then a fibonacci function defined as follow would never terminate (because fib(-1) and fib(-2) would have to be evaluated before fib(0) can yield a result).

fib(n)=
   if(eq(n, 0),
      1,
      if(eq(n, 1),
         1,
         +(fib(-(n, 1)), fib(-(n, 2)))
        )
     )

where eq(x, y) is a function that returns true if x and y are equal. --Koen (talk) 15:58, 16 October 2012 (UTC)

My take on this subject

Hi,

I had this exact same idea way back when I first found out about BF et al. Didn't get too far in the specs though. :) Anyway, I got interested about this idea again now that I read about your ideas. Have you had any new progress on this? I came up with a few ideas, including a function that uses recursion to loop N times by using Haskell like prefefined return values to finally terminate the recursion and also a kind of pointer that doesn't pass the return value as a parameter but the function itself.

I.e. "f(x)=y(x), main()=f(in())" would of course pass the read ascii code as the parameter for y() but "f(&x)=y(x), main()=f(in())" would execute in() two times, first at "f(in())" and then at "y(in())".

I think passing parameters for the program would be definitely cool (and useful...) but any kind of interactivity of course needs runtime input. And I'd love to see something like "+(*(in(),100),+(*(in(),10),in())" for reading a three digit number from the input. I think this one also needs some kind of stack, cell-memory or runtime function declarations to be Turing complete (if it even is possible).

62.248.142.104 16:24, 23 Nov 2006 (UTC) (xtmb atta kolumbus dotta fi)

• So you are using & to force the evaluation of parameters? Normally, "f(x) = y(x), main()=f(in())" would pass in() to f(x), then to y(x) and so on, until it couldn't avoid being evaluated. Now "f(x,y) = +(g(x),g(y)), main()=f(in(),in())" would eventually evaluate in() twice, but for "f(x) = +(g(x),g(x)), main() = f(in())", well, I don't really know. I'd say it should only evaluate in() once, but that might be hard to implement. As for the N loop, wouldn't "f(x,1) = x, f(x,n) = eval(x, f(x,-(n,1)))" work? (Assuming that eval(x, y, z, ...) evaluated x, then y, then z, etc.)

• • I think my approach is more C-like (or simple, less esoteric, if you will). I didn't even think of functions returning functions but evaluated integers (partly because I'm probably talking more about the language I devised, not Lazy which I admit seems to be a lot more esoteric :). However, in my vision of the language you could pass a parameter by reference or by value (so the reference would be evaluated only when it was eventually passed by value or simply was the return value which can't be but an integer).

Also, I was thinking that defining functions with a lot of parameters to emulate repetition as in your eval() example, the parameters should probably be evaluated in random order. Death to wimpmode. ;) Kometbomb 17:27, 29 Nov 2006 (UTC)

• Unfortunately, I haven't made any progress on this language. I put this up for the community to work on though, so if a couple of people think a feature should be added to the language, go ahead and add it.

• As for Turing completeness, I imagine it would be easiest to show using something along the lines of lambda calculus (like most functional languages). MagiMaster 18:24, 26 Nov 2006 (UTC)
  • Is it possible to define the s and k combinators and prove it Turing-complete in the same way as Unlambda? ais523 17:19, 27 Nov 2006 (UTC)
    • It seems likely, but I'm not very familiar with combinators. MagiMaster 06:43, 28 Nov 2006 (UTC)
      • Does the language allow on-the-fly definition of functions (like JavaScript does)? If so, writing

        k(x)(y)=x
s(x)(y)(z)=x(z)(y(z))

        would be enough to prove Turing-completeness; however, this doesn't seem to fit the syntax of the language. (The idea is that k(x) returns a function (call it k1) so that k1(y)=x, but I'm not sure how to express that in Lazy.) ais523 10:57, 28 Nov 2006 (UTC)
        • Well, the function definitions would be "k(x,y)=x, s(x,y,z)=x(z,y(z))" but what do you mean by on the fly? Anyway, later you could refer to k in another function, "z(x,y,z)=k(k(x,y),k(x,z))" (whether on not that actually makes sense). Or you could use some 0-ary function, "z(y)=k(g(),y)", which I think would just evaluate to "z(y)=g()". MagiMaster 17:16, 28 Nov 2006 (UTC)
          • The problem's that k(x,y) doesn't equal x; k only takes one argument. So k(x) is a function, and (k(x))(y) is applying that function to one argument, and the result is x; k's a combinator that creates constant functions. ais523 17:39, 28 Nov 2006 (UTC)
            • Oh right. I see (more or less). So it'd be more like "k(x)=x(y)", although, not exactly. I think you might could say "k(x)=x" and pass it a function... maybe. So, k is a function that takes a function as an argument, and returns what? MagiMaster
              • It returns a function which takes one argument, ignores it, and always returns x. (This function, by its nature, can't sensibly be defined anywhere beforehand (what if x is user input?), which is what I mean by on-the-fly function definitions.) ais523 08:56, 29 Nov 2006 (UTC)
                • Which is just closures by another name. It seems that this is the same as a well-known problem with trying to use the C language for higher-order functional programming: while you have first class function pointers, they can only be to predefined functions. --Ørjan 09:15, 29 Nov 2006 (UTC)

Turing completeness

Oerjan, can you explain a bit about your proof of turing completeness? I follow most of what your saying, but I don't know what you mean by μy f(y, x1, ..., xn). Is that supposed to define the function f, or the function μ or something else? MagiMaster 06:59, 29 Nov 2006 (UTC)

Oh wait. I think I might see. Wikipedia says the μ operator takes a function and returns another function. Ok I get it. You skipped the μ operator and just defined the μyf function. So I guess you could write it as μyf(x1, ..., xn) and have the number as the expected return type (in Lazy, at least). The μ operator itself shouldn't be too much harder to define. MagiMaster 07:05, 29 Nov 2006 (UTC)

The notation is a bit weird because μ is a binding operator like the λ of lambda calculus. So the notation actually is μyf(y,x1, ..., xn) with y written twice. It confused me as well when I first read the Wikipedia description.

As you say one could define the μ-operator itself:

mu(f) = mu_(0,f)
mu_(n,f) = if0(f(n),n,mu_(+(n,1),f))

There is however a problem when f has more than one argument. The way I understand the Lazy syntax you would either have to make one version for each number of arguments, or find some way of currying the arguments other than y. But the lack of λ-closures makes the latter difficult, perhaps impossible, as the discussion about combinators showed. It seems that for the first-class functions of Lazy to be useful, there needs to be some way to create a function closure (i.e. a function that can refer to arguments of the function that constructed it, in addition to its own.) --Ørjan 09:05, 29 Nov 2006 (UTC)

So how would a λ operator be defined, or is there another way of dealing with currying/closure that's more along the lines of what's already there? The basic problem is something like the need for a function to be able to return another function with more arguments than itself, right? (Since you can already define a function that returns any function with the same or fewer arguments.) Or is it more like the need to be able to return a function with an unspecified number of arguments? Maybe function calls/definitions could be redefined so that it never refers to a specific number of arguments? (Something along the lines of f=(g,(h,%1,%2),%3,%4)? Well, maybe not.) MagiMaster 17:41, 29 Nov 2006 (UTC)

Well, the k(x)(y)=x above is one way, admittedly not full lambda notation but enough to get around the restrictions. An unspecific number of arguments will only help with the mu definition, not with the general problem of not having closures.

As far as I can tell you are mistaken about being able to define a function with the same or fewer arguments. Note that saying that something like f(x1,x2) is a function is a dangerous oversimplification in our setting. Because, f(x1,x2) is not necessarily a function for our purposes, it is f that is the function and f(x1,x2) is just the result of applying it to the arguments x1 and x2, which may or may not be a function depending on the equations defining f. When dealing with functional programming, it is vitally important to distinguish between a function and its results. --Ørjan 22:07, 29 Nov 2006 (UTC)

Does that still apply when x1, x2, etc. are unbound variables? (For example, wouldn't f(x,y,z)=g(1,2,3,x,y,z) count as defining a new function with fewer arguments?) Would it help anything if all functions were defined as operating on a head:tail style list? MagiMaster 02:16, 30 Nov 2006 (UTC)

I suppose it counts sort of. The problem is that there is no way to make the 1,2,3 depend on variables other than x,y,z. I.e. you cannot construct a function f whose result depends on other variables than the function's arguments. Which is what you need to construct the k function, because it returns k(x) which is such a function: k(x)(y) depends on x, not y. It does not help to make the arguments a list, although if you had lists or tuples you could probably use them as a representation of closures, essentially building an interpreter for another language which has them. For example, in C which has the same basic problem, a closure can be represented as a struct which has a function pointer and the extra arguments (environment) as members. --Ørjan 07:25, 30 Nov 2006 (UTC)

Would it work if you could use unbound variables? For example f(x)=x(y,z) or f(x)=g(x,y) (assuming there was a rule to determine order of arguments later)? Also, I don't understand the lambda operator too well. How would that be used in a language like this? MagiMaster 22:09, 30 Nov 2006 (UTC)

Lambda expressions are not strictly necessary: they can be turned into a function application plus a definition, for example λx x(y) can be written as f(y) where f(y)(x) = x(y). However this requires you to have at least two levels of arguments. This rewriting is known as Wikipedia:Lambda lifting. But you really should read some tutorial on lambda expressions.

From what you write, I cannot say whether you want f(x)=x(y,z) to mean f(x)(y,z) = x(y,z), or f(y,z)(x) = x(y,z), or how you would determine the argument order in the second case (the first case can be rewritten as f(x) = x plus x(y,z) = whatever). And problems would arise if y or z happened to be defined globally. Mind you if you wanted your language to be awkward (not unusual here :) ) that would be appropriate. --Ørjan 09:04, 3 Dec 2006 (UTC)

Well, I meant f(x)=x(y,z) to imply (f(x))(1,2)=x(1,2) where the free variables would be taken in lexographic order. I suppose there'd be nothing wrong with f(y,z)=x(y,z) which would define f as returning two arguments waiting for a function. So, assuming that the rules for everything are well defined and that I'm not specifically trying to make things awkward, which style do you think would be better (f(x)=x(y,z) or f(x)(y,z)=x(y,z))? The two should be equivalent, right? Also, it seems like lambda lifting was saying that you can turn (f(x))(y,z)=x(y,z) into f(x,y,z)=x(y,z) but maybe I misunderstood something. MagiMaster 02:38, 4 Dec 2006 (UTC)

Worrying about lexicographic order doesn't seem to fit with the rest of the language; something of the form k(x)(y)=x or even s(x)(y)(z)=x(z)(y(z)) (which is more general as it returns a function which returns a function) would fit in better IMO. ais523 16:31, 5 Dec 2006 (UTC)

If the form f(x)(y)=x(y) is used, can μ be defined for an arbitrary number of arguments? Wouldn't K be K(x)(y)=x in this form? If the form f(x)=x(y) is used can K be defined correctly? Actually, how would μ be defined (for an arbitrary number of arguments) in either form? Does the technical difference come down to strength of typing? MagiMaster 01:26, 6 Dec 2006 (UTC)

Return types

I was just thinking about the return types of functions. Right now, it seems like all functions return more functions (including functions like 2, which is just a 0-ary, constant function). Does this sound reasonable? If so, how would you return a list? Construct a projection-like function (f(n) = nth member)? Also, if everything is a function, how is output(f) defined? MagiMaster 07:10, 29 Nov 2006 (UTC)

HereToAnnoy (talk) 18:22, 18 August 2017 (UTC)

What definition of the modulo function are you using? Just wondering, I would like to help with this language.