Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Have you read your PFDS today?

Name: Anonymous 2015-11-13 21:39

Purely Functional Data Structures
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
When a C programmer needs an efficient data structure for a particular problem, he or she can often simply look one up in any of a number of good textbooks or handbooks. Unfortunately, programmers in functional languages such as Standard ML or Haskell do not have this luxury. Although some data structures designed for imperative languages such as C can be quite easily adapted to a functional setting, most cannot, usually because they depend in crucial ways on assignments, which are disallowed, or at least discouraged, in functional languages. To address this imbalance, we describe several techniques for designing functional data structures, and numerous original data structures based on these techniques, including multiple variations of lists, queues, double-ended queues, and heaps, many supporting more exotic features such as random access or efficient catenation.

In addition, we expose the fundamental role of lazy evaluation in amortized functional data structures. Traditional methods of amortization break down when old versions of a data structure, not just the most recent, are available for further processing. This property is known as persistence, and is taken for granted in functional languages. On the surface, persistence and amortization appear to be incompatible, but we show how lazy evaluation can be used to resolve this conflict, yielding amortized data structures that are efficient even when used persistently. Turning this relationship between lazy evaluation and amortization around, the notion of amortization also provides the first practical techniques for analyzing the time requirements of non-trivial lazy programs.
 
Finally, our data structures offer numerous hints to programming language designers, illustrating the utility of combining strict and lazy evaluation in a single language, and providing non-trivial examples using polymorphic recursion and higher-order, recursive modules.

Name: Anonymous 2015-12-01 19:35

>>63
since I'm not completely satisfied with any lisp implementation, I've taken my own route.
This is exactly what lisp excels at. At the level you appear to be working, there is no reason to use anything other than lisp, as >>34 says. It's a traceable tower of abstraction from macros down to asm if you write it to be -- and yes, you can write the whole thing yourself without relying on someone else's code generator. It is done and it is done to death.

I write programs that calculate complicated efficient designs starting from simpler ideas.
Is that your job then? Or a hobby? As we discussed in >>31,32 - is the reason you are programming to implement the ideas you are talking about? Because if so, again, you are completely generalising to "GC is shit" and "if you are using GC, you aren't OMG OPTIMISING enough" because that is the domain you are working in. Everybody else is working on something else, and GC or otherwise is just a detail of implementation of the underlying system. You may well have only convinced yourself that bare-metal asm generation is the only way to go because of your current goals.

Of course, if that is not the case, feel free to elaborate on how GC and no GC are relevant to metalinguistic abstraction for anything other than a compiler.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List