Ethereum

[bairui]

Excellent. That should sort things out, one way or another.

[TedWalther]

Patricia trees look cool, and are used in big data applications like BGP routing, etc.  Very useful for quickly comparing/locating data organized by IP address, etc.



I wonder if Lutz would be open to adding Patricia Trees as a first class data type the way lists, arrays, and red-black trees are?



Patricia is a classic algorithm dating back to 1968.



http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/">http://www.csse.monash.edu.au/~lloyd/ti ... /PATRICIA/">http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/



Great comparison of Patricia and Red-Black trees:



http://www.mcdowella.demon.co.uk/Patricia.html">http://www.mcdowella.demon.co.uk/Patricia.html



So then updated this:

Code Select Expand


(new Tree 'blah)


with this:

Code Select Expand


(new RedBlackTree 'blah)
(new PatriciaTree 'argh)


While still leaving RedBlack as the default, so all old code with Tree still works.  The idea kind of excites me.

[TedWalther]

Jane, what exactly are they looking for?  A VM implementation?  newLISP is indeed ideal for that.  My first estimate stands.



newLISP can easily do the deduplication and the crypto optimizations.

[janeTA]

... Today programming is done by many who are not programming professionals. Programming is just one tool among many. That is why today much higher demands are present for the readability of a language.

Sorry. I have been reflecting on this.

[janeTA]

But I must admit I am still confused about newLISP's possible Ethereum interface. Surely if there was a newLISP interface, it would be... newLISP... right? The causal non-programmer newLISP *users* of the newLISP Ethereum interface would be using newLISP. It's only the newLISP-Ethereum API/library designer who has to know & understand the Ethereum forth api and care about stack stability... no?

Having browsed Ethereum, the impression I immediately had was newLISP (any Lisp, actually) could be profitably put to work throughout the whole Ethereum space - the whole evolving Ethereum ecosystem if you like - from the foundational level right up through the whole applications space and beyond? Here was (almost) a "tabla rasa" where newLISP could possibly "sing its song" better, faster and smarter than perhaps anything else? Here was what looked to be a vacant "natural" fit for Lisp (AI winters aside)? Far too often Lisp seems to cede such nascent spaces to be filled by other "lesser" technologies? Perhaps this time Lisp could move more swiftly? ...

[janeTA]

... If Ethereum wants a virtual machine, why not use newLISP's internal cell-based representation?  More flexible than the current stack based one they have now.  And newLISP already compiles to it.

Yes, I think I agree? However, I suspect that far "down" the Ethereum foundational chain might already now have been "captured"? Perhaps you might care to elaborate a little for a few of us mere mortals?  Perhaps show us some "layers" where you think newLISP (in your example (and (better) more)) could intercede?

[TedWalther]

Compiling newLISP to run on the etherium VM, I leave that for Lutz to say if it is easy or hard.  He just got it compiling into Javascript, so it may not be too hard.



It would be much easier to implement the Etherium VM in newLISP.  That would be practical, fun, and easy.



The Etherium developers already have their "pythonesque" language to let people use the etherium.  Using newLISP to compile the etherium variant of python to the etherium op-codes, would also be reasonably straight-forward.

[janeTA]

@TedWalther: I'm honestly not sure *what* Ethereum _wants_ from newLISP. Perhaps that's something @janeTA can clarify. I had assumed though they they were happy with their VM/API and were looking for others to ratify their party.

I'm not sure "Ethereum wants" anything? Perhaps its more what newLISP/ers can bring to the table (or even  better, just how fast they can do that)? Three "language" layers look to be immediately in place within Ethereum? Their now ES2, their CLL, and perhaps something (else) for "writing" contracts? One suspects newLISP can be put to work somewhere in/around these (for starters), say? It looks entirely open for newLISP to move into what is the now relatively "vacant" space above that level - "clients" obviously but far far further up than that? The "tree" of possible development spaces looks very open to me? Perhaps someone can visualise and talk to this far better than I ever can?

[janeTA]

If there is $$ on the table, I wouldn't be surprised if they could hire someone to get newLISP to compile for the VM.  If Lutz, Kazimir, or one of the other newLISP stalwarts don't want it, I'd step up to the plate.  I'm guessing $10,000 to $15,000.  Standard consulting deal, 1/3 up front, with milestone reports.

Nice opening gambit @TedWalther!



were newLISP a vendor-product one could likely hustle them for support at that $level? (I've tried a few) I'm unclear how large the newLISP communty actually is (clearly there are at least three alpha males within it, capable of handling the proposal) and whether the level of funding cited could be garnered from within it? one suspects perhaps not? one suspects also the "alphas" may also be overloaded with "$career" work?



rather than let this slip, though, perhaps some "local crowd" funding could be organised? could, say, a newLISp bitcoin address be set up against which such $funds could be pooled and work offset? would something like that work? btc could then be traded for ether later once Ethereum's ether hits the exchanges?



so for $15K the newLISP community gets what? like to perhaps map out the milestones/deliverables and ballpark schedule? sounds like it might be just the machine for generating quality Ethereum vmcode which by virtue of being quality gets used often and everywhere within the Ethereum community, which in turn generates ... ether ... for the newLISP pool (down the track)?

[janeTA]

Sorry, my posts are becoming increasingly turgid :(  I'm not flash with words, preferring visuals.  I shall try to do better!

[janeTA]

Patricia trees look cool, and are used in big data applications like BGP routing, etc.  Very useful for quickly comparing/locating data organized by IP address, etc.



I wonder if Lutz would be open to adding Patricia Trees as a first class data type the way lists, arrays, and red-black trees are?



While still leaving RedBlack as the default, so all old code with Tree still works.  The idea kind of excites me.

Yes! Agree! I would second that. Good thinking!

[Lutz]

Pure by theory radix trees seem to be faster but in practice the bit fiddling required is expensive. Looking at the implementation, I see source code about 6 to 7 times bigger than our RB-tree implementation. What exactly would patricia trees add? We have already execellent speed and scaling, better than hashes for big numbers (tens or millions) of keys in newLISP.



In general, I have no objections adopting a new dictionary algorithm. We already switched once from ordinary binary tree algorithm to the current RB-tree algorithm. What other things would Patricia bring to the table, we don't have already?



If anyone wants to implement this in C for testing/benchmarking in newLISP, they should go ahead. I am not convinced enough to try myself.



Ps: this also caught my attention:    

"Standard Patricia imposes a restriction on the strings stored in the tree: no string can be a prefix of any other string. One reason for this is that distinguishing between the two strings would then require testing for presence of bits, as well as testing their value. "

[TedWalther]

Ps: this also caught my attention:    

"Standard Patricia imposes a restriction on the strings stored in the tree: no string can be a prefix of any other string. One reason for this is that distinguishing between the two strings would then require testing for presence of bits, as well as testing their value. "

Thank you Lutz, that does look like a show-stopper!

[janeTA]

meanwhile ...

Etherium lispy-things are charging onwards & upwards ...

https://github.com/ethereum/cpp-ethereum/wiki/LLL-Tutorial">https://github.com/ethereum/cpp-ethereu ... L-Tutorial">https://github.com/ethereum/cpp-ethereum/wiki/LLL-Tutorial

where LLL = Low-level Lisp-like Language?

[janeTA]

What would be useful would be some de-compilers from Ethereum-script (ESn where n = 1 or now 2) to their CLL or better LLL or even better LISP and so on?