Talk:ELIP

A little birdie told me that chaos-pp uses something called exponential expansion, which isn't actually Turing-complete, just a large finite state machine. So this project is mostly impossible. (Of course, it's also impossible in C itself, due to the techniques usually being used to implement an infinite tape (e.g. malloc) being unable to allocate infinite memory.) —ehird 23:51, 13 July 2011 (UTC)

I don't actually know what exponential expansion is, mind you. —ehird 00:04, 30 July 2011 (UTC)

I think what you're talking about has something to do with CHAOS_PP_LIMIT_MAG and CHAOS_PP_LIMIT_EXPR being set to 512, but maybe the arbitrary-precision library could be used to get around this. For functional languages like Unlambda, this limit probably won't be a problem since it would use combinators made from higher-order macros, and wouldn't need operations based around the saturating INC/DEC functions like Chaos's FOR, REPEAT, or WHILE loops. Would you be interested in making an interpreter for ELIP? If you do, try it in gcc's cpp since that's the only one that runs all of the examples in Order and Chaos correctly (even mcpp and Wave are broken). Ian 02:31, 30 July 2011 (UTC)

"maybe the arbitrary-precision library could be used to get around this" — if this is the fundamental computation mechanism of the libraries, then you can't really use an arbitrary-precision data type and operations on them defined using that mechanism to subvert it. I'm no cpp wizard myself, but I'm sceptical that cpp is Turing-complete. —ehird 03:47, 30 July 2011 (UTC)

The arbitrary-precision library doesn't use the EXPR/recursion state mechanism, but a method called sequential iteration which allows it to operate on sequences of any size (Chaos docs: "This macro uses sequential iteration. As a result, the algorithm is theoretically capable of processing sequences containing an unrestricted number of elements."). Surprisingly to me, sequences can even be reversed by using only sequential iteration, without using EXPR at all (but the EXPR version is faster). As for CHAOS_PP_LIMIT_EXPR, the problem is that while nested macros can be repeated any number of times (see the CAR/CDR/CONS and CHAOS_PP_DYNAMIC), the depth of recursion is limited. EXPR(EXPR(EXPR(...))) is legal and invokes EXPR three times, but EXPR(...) where the ... uses EXPR inside its definition isn't, so Chaos makes the inner EXPR expand to EXPR_1 using preprocessor magic (but I don't know how that macro is able to work multiple times, or how it knows which one to expand to). The main "flaw" of Chaos is using the fixed numbers for everything instead of the arbitrary-precision (for speed and memory savings) because even the FOR and REPEAT algorithms are capable of much more than 512 iterations (I think the _X versions allow up to 2^512 for each nested EXPR macro?), and the sequence/arbitrary-precision libraries can work on numbers that are truly any size by using this sequential iteration method. Unfortunately the Chaos docs aren't complete, so I can't read about the other techniques like continuation machines, parametric resumption, and exponentials (the exponential expansion you mentioned), and it's hard to figure out complicated preprocessor techniques just by looking at the source and usage docs. Ian 06:50, 7 September 2011 (UTC)

I think (and this is just a guess, not being familiar with chaos-pp) that the real limit that prevents Turing completeness may not be memory but looping. You'll note that the Repeat macro in techniques can only repeat a finite, predefined maximum number of times. On the data side, arithmetic seems to deal with finite values only (the lookup-table-based increment). (Though this last one might be circumventable with arbitrary-precision floats, it definitely wouldn't be pretty.) —Maharba 15:12, 30 July 2011 (UTC)

Right, it's not Turing-complete. If you only have bounded loops, you can only express primitive recursive functions. Removing the include depth limit might get you the rest of the way there, though. EvincarOfAutumn 00:11, 26 August 2011 (UTC)

This isn't impossible, and in fact, it's been done before, with a little cheating (running the preprocessor on the code repeatedly). See [1] --Revcompgeek 07:38, 4 August 2011 (UTC)

Well, that cheating can turn a decidedly sub-TC system into a TC one. —ehird 04:04, 25 August 2011 (UTC)