Slashdot Mirror

One advantage over Scheme is ease of integration with C/C++

Aye, one of my favorite such sites:

Borked:
http://call-with-current-continuation.org/

Fine:
http://www.call-with-current-continuation.org/

Aye, one of my favorite such sites:

Borked:
http://call-with-current-continuation.org/

Fine:
http://www.call-with-current-continuation.org/

``Also though it is slightly off-topic I also think that Java under GPL would not benefit as much because the model of contribution is really not as easily understood as the OS world.''

With all the complaints about the Java community process being slow and bureaucratic, and the free Java implementations lagging behind in features, I think having a good, open source Java implementation is a Good Thing in it's own right.

Also, I don't know what you mean by the model of contribution for Java not being as easily understood as the OS world. It's not like there aren't any successful open source programming language implementations yet.

Felix, the author of Chicken Scheme, a fairly popular Scheme implementation, doesn't seem very fond of R6RS.

I just thought my fellow Slashdot readers could want to hear his informed opinion. :-)

Chicken Scheme is also quite nice. Compiles to C code, has a lot of libraries, and is supported by things like SWIG, so it's (relatively) easy to call functions written in C/C++.

Try chicken scheme. http://www.call-with-current-continuation.org/ most of what you want and an (IMHO) elegant language.

Someone might add pointers

Someone might add pointers

No, CHICKEN is cross-platform, not just for Macs.

I've never been able to get the speed of OpenMCL-compiled code to compare the SBCL-compiled code. Every now and then I find myself switching back to SBCL for that reason, as I do some hacking in my free-time that is numerically intensive.

;; simple use of foreign-lambda*
 
(define yo
  (foreign-lambda* void ((int x))
  "printf(\"yo: %d\\n\", x);"))
 
(yo 33)
 
;; simple use with callback
 
(define-external (back) void
  (print "I'm back!"))
 
(define call
  (foreign-safe-lambda* void ()
  "back();"))
 
(call)

GC systems in a similar steady state tend to roam all over their heap, touching lots of pages. This can cause the OS to keep more physical pages mapped to the process's virtual memory space, even though the process isn't actually using more memory.

Not necessarily. Modern GCs tend to take advantage of the generational hypothesis which suggests that most objects die young. One can code with generational GC with fast handling of deaths in the "nursery" of recently-created objects in mind.

A typical generational GC with two generations of old objects and a nursery works like this.

You maintain four pointers:

G1, the top of the oldest generation.
G0, the top of the 2nd oldest generation.
FREE, the top of the nursery.
CEIL, which limits the size of the heap.

At initialization, the first two of these all point to the bottom of the heap.
CEIL will point to a memory location half way between the bottom and the top of the heap, or higher.

Set FREE to CEIL, so we begin allocating in of the top of the heap.

When we allocate an object, we simply increment FREE.

When FREE reaches the top of the heap, we collect the nursery.

We do this by sliding down all live objects between FREE and the top of the heap to the area between G0 and CEIL.

In a tracing GC system, live objects are those pointed to by the roots (registers, for example, or live stack frames) as well as objects in the older generations. We can optimize the identification of the latter by maintaining a write barrier on the older generations, which tells us whether a section (perhaps a page) in the older generation was touched since the last garbage collection. A page which hasn't been touched since the last gc cannot point to live objects in the nursery. A page which has been touched might point to live objects in the nursery, so we have to trace the pointers in the page as if they were roots.

The slide-down relocation is usually done by copying the object and leaving behind a forwarding pointer. In the case of linked lists and the like, the lists are walked recursively, often breadth-first, although depth-first can give better locality of reference.

During the migration of the live objects, we can increment G0 as we go, reusing the allocation mechanism, or we can adjust G0 after the slide-down relocations are finished. Either way, when we are done, we have expanded the area between G1 and G0, and no longer care what's above CEIL. If there is sufficient space between G0 and CEIL, we set FREE to CEIL and operate as usual.

If we are tight on space between G0 and CEIL we can either expand the heap (and increase CEIL) or we can collect one or both of the older generations. Again, we identify live objects and slide them down to the earlier generation.

In the case where we are creating lots of short-lived objects we are doing very little copying during the nursery collection -- we can end up effectively doing nothing but writing objects into the top of the heap then resetting the FREE pointer when we get there. If there are many more pages between CEIL and the top of the heap then yes we will be touching more pages than if we had a very disciplined explicit allocate-and-free mechanism. If our nursery is small, however, that is not the case.

There are other ways of handling the nursery, including the Cheney on the MTA approach of using C's runtime stack (alloca() and friends) to store young objects. We still have to find and live objects when our nursery gets too large, but the C "return" reclaims all the dead ones. The implementation is straightforward for a continuation-passing-style language compiled into C, works well with small nursery sizes, and has been implemented in the Chicken implementation of Scheme.

Optimizing the speed of nursery handling, and partitioning the

would be nice for hardware to provide tag bits so integers and floats wouldn't have to be twiddled before doing arithmatic on them

Tag bits are nice so you can precisely distinguish pointers from everything else.

This lets you implement a precise garbage collector rather than a conservative one. This makes modern tracing GC (fast, compacting (especially to increase locality of reference), incremental, even backgroundable) much easier to implement.

If you sacrifice one bit from your native machine's word size, you can distinguish pointers from all other objects.

Most modern systems use byte addressing rather than word addressing, and if you word-align all your data, you don't need your least significant bits. So on a 64-bits-per-word machine, you can sacrifice your LSB and still have 63 bits to play with; on a 32-bits-per-word machine, you have 31, hell, on a 16-bits-per-word machine you have 15. Don't ask about truly 8-bit machines like the 6502. :-)

Word-alignment on a byte-addressed 16-bit machine gives you 15 bit pointers -- you only have to address every second byte, starting at all zeros. Address 1 is part of the very first word, so 0000000000000001 (binary) is something we don't need to address directly. We can use that 1 bit to indicate that the object is NOT a pointer.

We can do the same for 32 and 64 bits: ...00 (binary) is the address of a 32-bit word on a byte-addressed architecture; ...0000 (binary) is the address of a 64-bit word, and so forth.

All you need is a shift-all-the-bits-in-the-word-left instruction.

Instead of: load register,memory; , store memory,register, we:

1. Load register

2. Shift word to the right. bit0 goes away, most-significant-bit is now 0.

3. Perform arithmetic operations as usual, leaving result in register.

4. Shift word one bit to the left, immediate-or the word with 1.

5. Store the word into memory.

This works great for 2s complement integer arithmetic, with an absolute range of values of 2^wordsize-1.

As noted, on 32-bit architectures and 64-bit architectures, we have more bits that are meaningless in pointers to word-aligned objects. We just do more shifts.

Typechecking involves a step between 1 and 2, where we look at whether the least significant bit is really 1 before doing integer arithmetic.

If we have more tag bits, we can have more typechecking along these bit-testing lines.

The cost of the register shifting can be small or large depeding on architecture. Usually it's small on modern chipsets.

It's not clear that hardware tagging would be a clear win. Mostly it would have to be evaluated in terms of decreasing the number of instructions by consolidating dropping back to e.g. three to do an untypechecked integer load-add-store from six (load-shift-add-shift-or-store). That is, the extra three instructions are unlikely to add so much extra dependency or processing time, or rob users of sufficient fixnum precision, that pushing distinguished and precise identification of pointers into the processor becomes worthwhile.

Moreover, with foreign-function-interfacing, one can jump into another language (like C) to do full native untypechecked integer (or other) maths, just so long as it doesn't put results that look like pointers into GC-managed memory.

Chicken is one example of this approach. It uses Cheney-on-the-MTA to do the nursery area of its fast, compacting, generational garbage collector *portably* to byte-addressed 32-or-64-bit word architectures. Since all objects are word-aligned, that gives two or four bits of "tag", which it uses to precisely identify pointers, integers, and a few other types, both for typing and for GC purposes.

By comparison, the CADR's hardware architecture ultimately supports polymorphism

Wow... 12 years. Lots has changed since in far fewer years than that!

Maybe you should check out PLT Scheme, a modern scheme interpreter and compiler and IDE, with several "Teachpacks" which help one come up to speed in doing clever things with Scheme. DrScheme is the thing to download, for various platforms.

There are plenty of other Scheme implementations out there, interpreted and compiled.

Personally I do a lot in SCSH, the Scheme Shell which is handy for writing scripts and tools close to the metal on on UNIX/POSIX systems, however PLT and other environments are incorporating more and more of SCSH-like goodies into their libraries, and write stuff that needs to be fast in Chicken or Gambit, which compile Scheme to C. On the Common Lisp front, on a Mac, there is also OpenMCL, which compiles to *particularly fast* native PowerPC code and has a straightforward way of communicating with Cocoa and a number of other Mac-development-friendly features. In fact, all of these implementations have foreign-function-interface abilities which let you call e.g. C functions from Scheme/Lisp, or vice-versa, so you can write performance-critical sections in a low-level language of your choice, and use higher-level languages to develop "smarts".

Try this implementation for instance. It has all the features you are looking for.

You should learn Scheme or LISP. In addition, they don't have to be interpretted. Chicken is a great Scheme compiler, with easy-to-use methods for interfacing with any external function.

The great thing about Scheme/LISP is that you can extend the languages themselves through macros (real macros, not crap like C/C++ has). In fact, you could probably implement the COBOL language as macros if you wanted to, and still get all of the advantages of Scheme - continuations, closures, the ability to do lazy evaluation, etc.

The problem w/ COBOL is that it's verbose, and very hard to simplify. Newer versions of COBOL are probably better at this, but compared to the amount of code reduction you can get from languages like Scheme and LISP, I have trouble believing that COBOL matches up.

The one thing I can probably agree with is your #2, though. Few other programming languages put as much thought into fixed-point representations of numbers.