Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!boingo.med.jhu.edu!haven!ni.umd.edu!uc780.umd.edu!cs450a03
From: cs450a03@uc780.umd.edu
Newsgroups: comp.lang.apl
Subject: implementing J
Message-ID: <19APR91.08155946@uc780.umd.edu>
Date: 19 Apr 91 08:15:59 GMT
Sender: usenet@ni.umd.edu (USENET News System)
Organization: The University of Maryland University College
Lines: 24
Nntp-Posting-Host: uc780.umd.edu

This is a continuation of my last post:  vauge ruminations about how
to implement J efficiently.

Problem:  building a list of length n from n scalar operations is O(n
squared), rather than O(n)

LISP people would laugh, and say you need cons cells.  That might
actually be a way to go:  have catenate build an internal structure
specially optimized for catenate, then the first time something
besides catenate operates on that object, a post processing stage
kicks in and produces a flat list for use by whatever this new
function is.

There would be a tradeoff there--for some things this could really
waste time.  Also note that this is similar to using APL's indexed
assignment assignment to build arrays, although indexed assignment
takes advantage of being able to estimate storage requirements ahead
of time.

Most likely, the people at ISI and IPS have already gone over this
issue a number of times, and already have some favored solutions.  Any
comments from over there?

Raul Rockwell