bluuebunny/crossref_metadata_2025 huggingface dataset:
It is time to emphasize arraylists over arrays in Java-based first programming courses
Authors: Jacobson Norman , Thornton Alex
Published: January 2005

The array is typically the first aggregate collection taught in first programming courses. Arrays are commonly introduced as a way to implement variable-sized lists, despite their fixed size and, in first courses using Java, the availability of the ArrayList class, which represents variable-sized lists directly. It appears the array has been used mainly because of ArrayList's limitations. However, with the recent release of Java 5.0, the ArrayList structure now has properties that make it the better structure for representing contiguous lists, both conceptually and in terms of implementation. We argue that it is the list structure that should be introduced first, and the one emphasized, in a Javabased first course.
Conceptualizing data structures
Authors: Nair Achuth Sankar S. , Mahalakshmi T.
Published: January 2005

This paper discusses a pedagogical approach to conceptualizing data structures. Currently there appears to be a need for consistent, logical, and extensible visual representation for conceptualizing data structures. A very simple graphic representation of memory is shown to be highly useful in conceptualizing data structures and in introducing pointers. It is also pointed out that the model could be translated into a multimedia equivalent where additional pedagogic advantages can be derived.
Teaching by analogy
Authors: Mason John
Published: January 2005

Many beginning programming students have difficulty mastering the C++/Java concept of the
switch
statement. This paper provides a classroom tested analogy that allows students to map a "real world" concept that they already understand to the
switch
statement, thus making comprehension much easier.
Towards a more effective way of teaching a cybersecurity basics course
Authors: Shumba Rose
Published: January 2005

The Cybersecurity Basics course is an interdisciplinary course for the Criminology, Management Information Systems and Computer Science students at IUP. The course introduces computer security by focusing on host security. This paper describes laboratory exercises developed as part of a project to augment and improve on the teaching of the Cybersecurity Basics course. Nine Linux-based laboratory exercises were developed. A poster paper, based on the developed laboratory exercises was presented at the SIGSCE Symposium [5]. The developed lab exercises are being pilot tested in the Cybersecurity Basics course at IUP.
A multi-national study of reading and tracing skills in novice programmers
Authors: Lister Raymond , Adams Elizabeth S. , Fitzgerald Sue , Fone William , Hamer John , Lindholm Morten , McCartney Robert , Moström Jan Erik , Sanders Kate , Seppälä Otto , Simon Beth , Thomas Lynda
Published: January 2005

A study by a ITiCSE 2001 working group ("the McCracken Group") established that many students do not know how to program at the conclusion of their introductory courses. A popular explanation for this incapacity is that the students lack the ability to problem-solve. That is, they lack the ability to take a problem description, decompose it into sub-problems and implement them, then assemble the pieces into a complete solution. An alternative explanation is that many students have a fragile grasp of both basic programming principles and the ability to systematically carry out routine programming tasks, such as tracing (or "desk checking") through code. This ITiCSE 2004 working group studied the alternative explanation, by testing students from seven countries, in two ways. First, students were tested on their ability to predict the outcome of executing a short piece of code. Second, students were tested on their ability, when given the desired function of short piece of near-complete code, to select the correct completion of the code from a small set of possibilities. Many students were weak at these tasks, especially the latter task, suggesting that such students have a fragile grasp of skills that are a prerequisite for problem-solving.
Total order broadcast and multicast algorithms
Authors: Défago Xavier , Schiper André , Urbán Péter
Published: January 2005

Total order broadcast and multicast (also called atomic broadcast/multicast) present an important problem in distributed systems, especially with respect to fault-tolerance. In short, the primitive ensures that messages sent to a set of processes are, in turn, delivered by all those processes in the same total order.
Is security engineering really just good software engineering?
Authors: Wolf Alexander L.
Published: January 2005

These days, if you say that you are doing research in the area of computer security you instantly receive attention. Sadly, the same cannot be said of software engineering. But are the two areas really so different? Both seem to be concerned with issues that range from the finely technical to the broadly social and that force us to make difficult tradeoffs among cost, performance, quality, and usability. Both seem to require that we conduct our research in an interdisciplinary context. In the end we realize that fully solving the security problem for ever larger and more complex systems is as intractable as fully solving the traditional software engineering problem.

In this talk I will attempt to relate the challenges of security engineering and software engineering, and will argue that security engineering is more of a software engineering problem than many people would like to admit.
Explaining abstract counterexamples
Authors: Chaki Sagar , Groce Alex , Strichman Ofer
Published: January 2005

When a program violates its specification a model checker produces a counterexample that shows an example of undesirable behavior. It is up to the user to understand the error, locate it, and fix the problem. Previous work introduced a technique for explaining and localizing errors based on finding the closest execution to a counterexample, with respect to a distance metric. That approach was applied only to concrete executions of programs. This paper extends and generalizes the approach by combining it with predicate abstraction. Using an abstract state-space increases scalability and makes explanations more informative. Differences between executions are presented in terms of predicates derived from the specification and program, rather than specific changes to variable values. Reasoning to the cause of an error from the factthat in the failing run x < y, but in the successful execution x = y is easier than reasoning from the information that in the failing run y = 239, but in the successful execution y = 232. An abstract explanation is automatically generalized

Predicate abstraction has previously been used in model checking purely as a state-space reduction technique. However, an abstraction good enough to enable a model checking tool to find an error is also likely to be useful as an automatically generated high-level description of a state space --- suitable for use by programmers. Results demonstrating the effectiveness of abstract explanations support this claim.
Correlation exploitation in error ranking
Authors: Kremenek Ted , Ashcraft Ken , Yang Junfeng , Engler Dawson
Published: January 2005

Static program checking tools can find many serious bugs in software, but due to analysis limitations they also frequently emit false error reports. Such false positives can easily render the error checker useless by hiding real errors amidst the false. Effective error report ranking schemes mitigate the problem of false positives by suppressing them during the report inspection process [17, 19, 20]. In this way, ranking techniques provide a complementary method to increasing the precision of the analysis results of a checking tool. A weakness of previous ranking schemes, however, is that they produce static rankings that do not adapt as reports are inspected, ignoring useful correlations amongst reports. This paper addresses this weakness with two main contributions. First, we observe that both bugs and false positives frequently cluster by code locality. We analyze clustering behavior in historical bug data from two large systems and show how clustering can be exploited to greatly improve error report ranking. Second, we present a general probabilistic technique for error ranking that (1) exploits correlation behavior amongst reports and (2) incorporates user feedback into the ranking process. In our results we observe a factor of 2-8 improvement over randomized ranking for error reports emitted by both intra-procedural and inter-procedural analysis tools.
A classification system and analysis for aspect-oriented programs
Authors: Rinard Martin , Salcianu Alexandru , Bugrara Suhabe
Published: January 2005

We present a new classification system for aspect-oriented programs. This system characterizes the interactions between aspects and methods and identifies classes of interactions that enable modular reasoning about the crosscut program. We argue that this system can help developers structure their understanding of aspect-oriented programs and promotes their ability to reason productively about the consequences of crosscutting a program with a given aspect.

We have designed and implemented a program analysis system that automatically classifies interactions between aspects and methods and have applied this analysis to a set of benchmark programs. We found that our analysis is able to 1) identify interactions with desirable properties (such as lack of interference), 2) identify potentially problematic interactions (such as interference caused by the aspect and the method both writing the same field), and 3) direct the developer's attention to the causes of such interactions.
Heuristic-guided counterexample search in FLAVERS
Authors: Tan Jianbin , Avrunin George S. , Clarke Lori A. , Zilberstein Shlomo , Leue Stefan
Published: January 2005

One of the benefits of finite-state verification (FSV) tools, such as model checkers, is that a counterexample is provided when the property cannot be verified. Not all counterexamples, however, are equally useful to the analysts trying to understand and localize the fault. Often counterexamples are so long that they are hard to understand. Thus, it is important for FSV tools to find short counterexamples and to do so quickly. Commonly used search strategies, such as breadth-first and depth-first search, do not usually perform well in both of these dimensions. In this paper, we investigate heuristic-guided search strategies for the FSV tool FLAVERS and propose a novel two-stage counterexample search strategy. We describe an experiment showing that this two-stage strategy, when combined with appropriate heuristics, is extremely effective at quickly finding short counterexamples for a large set of verification problems.
The predecessor attack
Authors: Wright Matthew K. , Adler Micah , Levine Brian Neil , Shields Clay
Published: January 2005

There have been a number of protocols proposed for anonymous network communication. In this paper, we investigate attacks by corrupt group members that degrade the anonymity of each protocol over time. We prove that when a particular initiator continues communication with a particular responder across path reformations, existing protocols are subject to the attack. We use this result to place an upper bound on how long existing protocols, including Crowds, Onion Routing, Hordes, Web Mixes, and DC-Net, can maintain anonymity in the face of the attacks described. This provides a basis for comparing these protocols against each other. Our results show that fully connected DC-Net is the most resilient to these attacks, but it suffers from scalability issues that keep anonymity group sizes small. We also show through simulation that the underlying topography of the DC-Net affects the resilience of the protocol: as the number of neighbors a node has increases the strength of the protocol increases, at the cost of higher communication overhead.
Traducement
Authors: Walcott Tom , Bishop Matt
Published: January 2005

Security models generally incorporate elements of both confidentiality and integrity. We examine a case where confidentiality is irrelevant to the process being modeled. In this case, integrity includes not only the authentication of origin and the lack of unauthorized changes to a document, but also the acceptance of all parties that the document is complete, signed by all parties, and cannot be modified further. This is especially critical when the document is recorded, so that it is legally the agreement or statement of record, and any copies of the document have no legal force. We show that current security models do not capture the details of this process. We then present a new security model for this process. This model captures the recordation process, and augments, rather than supplants, existing models. Hence it can also be used with existing security models to describe other situations.
Essential classification rule sets
Authors: Baralis Elena , Chiusano Silvia
Published: January 2005

Given a class model built from a dataset including labeled data, classification assigns a new data object to the appropriate class. In associative classification the class model (i.e., the classifier) is a set of association rules. Associative classification is a promising technique for the generation of highly accurate classifiers. In this article, we present a compact form which encodes without information loss the classification knowledge available in a classification rule set. This form includes the rules that are essential for classification purposes, and thus it can replace the complete rule set. The proposed form is particularly effective in dense datasets, where traditional extraction techniques may generate huge rule sets. The reduction in size of the rule set allows decreasing the complexity of both the rule generation step and the rule pruning step. Hence, classification rule extraction can be performed also with low support, in order to extract more, possibly useful, rules.
Centralization momentum
Authors: Evaristo J. Roberto , Desouza Kevin C. , Hollister Kevin
Published: January 2005

Discussing whether IT architecture should be centralized or decentralized is as old as the technology itself. We propose that, notwithstanding the various perspectives that have been brought to the debate, what is missing thus far is the seesaw between centralization and decentralization. The reasons for this important phenomenon relate not only to IT-centric issues but also to current events pervading other areas of the organization. One key issue is how management has changed its IT focus from a "must have/keeping up with the Joneses" investment to a value-based "where's the beef?" approach pragmatically emphasizing the relevance of data and its uses. A second consideration is the business requirements for a reliable, available, fault-tolerant, backed-up, secure IT environment, even in the face of catastrophic events, including the 9/11 terrorist attacks. Executives cannot afford to not know why the renewed focus on IT architecture centralization has happened and how it might affect their organizations.
Trust in e-commerce
Authors: Salam A.F. , Iyer Lakshmi , Palvia Prashant , Singh Rahul
Published: January 2005

Web-based businesses succeed by cultivating consumers' trust, starting with their beliefs, attitudes, intentions, and willingness to perform transactions at Web sites and with the organizations behind them.
Examining differences across journal rankings
Authors: Rainer R. Kelly , Miller Mark D.
Published: January 2005

Many have studied and ranked the quality of computing journals over the last 15 years. This composite of the top 50 was created by examining how those rankings fared over time and across studies.
Intelligent mobile crisis response systems
Authors: Yuan Yufei , Detlor Brian
Published: January 2005

Systems to help coordinate responder communication and response efforts in order to minimize the threat to human life and damage to property.
Hepatic surgery simulation
Authors: Delingette Herve , Ayache Nicholas
Published: January 2005

The goal of surgical simulation is to provide highly realistic training to increase the diffusion of innovative and less-invasive procedures while decreasing the surgeon's learning curve. Consider, for instance, the development and refinement of laparoscopic surgery. In this type of surgery, abdominal operations such as hepatic (liver) resections are accomplished through small incisions. The abdomen of the patient is inflated with gas to create open space inside and a video camera is inserted into the abdomen through one of the small incisions. The video image is magnified and transmitted to a high-resolution monitor, allowing the surgeon to see the abdominal anatomy with great clarity. The surgery is performed using special instruments introduced through the other incisions. The advantages of surgical simulation for the patient include less pain and less strain for the body, faster recovery, and reduced overall illness time. The surgeon, however, must acquire specific skills and develop advanced hand-eye coordination before attempting to perform such a procedure in a real-world setting.
Incorporating 3D virtual anatomy into the medical curriculum
Authors: Imielinska Celina , Molholt Pat
Published: January 2005

The introduction of the Visible Human Project by Ackerman in 1995, described in the seminal paper in 1996 [9], brought a promise to anatomists that these two frozen, milled, and digitized cadavers---the Visible Male and Female---would revolutionize anatomy teaching by providing the most complete and detailed anatomical images ever. This vision could be compared to the proverbial "man on the moon" program for medical education and has proven to be much more challenging than expected. Although the ramifications of this project are not of the same scale as the shock created five centuries ago by the Padua physician Andreas Vesalius when he challenged the ancient Greek physician Galen's description of the human body, the original interest created by the availability of the Visible Human data was enormous.
Combinatorial techniques for mixed-size placement
Authors: Adya S. N. , Markov Igor L.
Published: January 2005

While recent literature on circuit layout addresses large-scale standard-cell placement, the authors typically assume that all macros are fixed. Floorplanning techniques are very good at handling macros, but do not scale to hundreds of thousands of placeable objects. Therefore we combine floorplanning techniques with placement techniques to solve the more general placement problem. Our work shows how to place macros consistently with large numbers of small standard cells. Proposed techniques can also be used to guide circuit designers who prefer to place macros by hand.We address the computational difficulty of layout problems involving large macros and numerous small logic cells at the same time. Proposed algorithms are evaluated in the context of wirelength minimization because a computational method that is not scalable in optimizing wirelength is unlikely to be successful for more complex objectives (congestion, delay, power, etc.)We propose several different design flows to place mixed-size placement instances. The first flow relies on an arbitrary black-box standard-cell placer to obtain an initial placement and then removes possible overlaps using a fixed-outline floorplanner. This results in valid placements for macros, which are considered fixed. Remaining standard cells are then placed by another call to the standard-cell placer. In the second flow a standard-cell placer generates an initial placement and a force-directed placer is used in the engineering change order (ECO) mode to generate an overlap-free placement. Empirical evaluation on
ibm
benchmarks shows that in most cases our proposed flows compare favorably with previously published mixed-size placers, Kraftwerk, and the mixed-size floor-placer proposed at the 2003 Conference on Design, Automation, and Test in Europe (DATE 2003), and are competitive with mPG-MS.
RL-huffman encoding for test compression and power reduction in scan applications
Authors: Nourani Mehrdad , Tehranipour Mohammad H.
Published: January 2005

This article mixes two encoding techniques to reduce test data volume, test pattern delivery time, and power dissipation in scan test applications. This is achieved by using run-length encoding followed by Huffman encoding. This combination is especially effective when the percentage of don't cares in a test set is high, which is a common case in today's large systems-on-chips (SoCs). Our analysis and experimental results confirm that achieving up to an 89% compression ratio and a 93% scan-in power reduction is possible for scan-testable circuits such as ISCAS89 benchmarks.
A sort-based DDM matching algorithm for HLA
Authors: Raczy C. , Tan G. , Yu J.
Published: January 2005

The High Level Architecture (HLA) is an architecture for reuse and interoperation of simulations. It provides several Data Distribution Management (DDM) services to reduce the transmission and reception of irrelevant data. These services rely on the computation of the intersection between "update" and "subscription" regions. Currently, there are several main DDM filtering algorithms. Since each approach still has some shortcomings, we have focused our research on the design and the evaluation of intersection algorithms for the DDM. In this article, we introduce a new algorithm in which extents are sorted before computing the intersections. Our experiments show that usually the sort-based algorithm has the best performance among all approaches. The improvement of its performance ranges between 30% and 99% over the brute force and hybrid approaches.
Pragmatic parsing in Common Lisp; or, putting
defmacro
on steroids
Authors: Baker Henry G.
Published: January 2005

We review META, a classic technique for building recursive descent parsers, that is both simple and efficient. While META does not handle all possible regular or context-free grammars, it handles a surprisingly large fraction of the grammars encountered by Lisp programmers. We show how META can be used to parse streams, strings and lists---including Common Lisp's hairy lambda expression parameter lists. Finally, we compare the execution time of this parsing method to the built-in methods of Common Lisp.
AN SQL interface for Common Lisp
Authors: Gunderson Alan S.
Published: January 2005

Access to persistent database storage from Common Lisp applications is an increasingly frequent requirement. This paper discusses a software module that allows a Common Lisp program to access a relational database management system. Database queries are expressed as SQL statements. In Common Lisp, the SQL query is represented as a string, which allows sequence functions to be used to construct the query. Through a foreign function interface, the SQL query is passed from Lisp to a C component. The C component contains embedded database statements to utilize the dynamic SQL facility provided by the database management system. The database result table is returned to Lisp. Functions are provided to convert the returned data into a list of structures. Each structure corresponds to one row in the database result table. Structure accessor functions allow each individual attribute (field) in the structure representation of a row in the result table to be obtained.
Lisp view
Authors: Muller Hans
Published: January 2005

This paper is a review of the Lisp View project. The paper focuses on our experiences in two areas: interfacing Common Lisp with a large complicated C library, and using the Common Lisp Object System[2] (CLOS) to implement the Lisp View application programmer's interface (API). We've also included a short survey of similar Common Lisp packages.
A guided tour of the Common Lisp interface manager
Authors: Rao Ramana , York William M. , Doughty Dennis
Published: January 2005

The Common Lisp Interface Manager (CLIM) is a powerful Lisp-based system that provides a layered set of facilities for building user interfaces. These facilities include a portable layer called Silica that includes basic windowing, input, output services, and mechanisms for constructing window types and user interface components; stream-oriented input and output facilities extended with presentations and context sensitive input similar to the work pioneered in the Genera UI system; and a gadget-oriented toolkit similar to those found in the X world extended with support for look and feel adaptiveness. In this article, we present an overview of CLIM's broad range of functionality and present a series of examples that illustrates CLIM's power.
A syntactic approach to fixed point computation on finite domains
Authors: Chuang Tyng-Ruey , Goldberg Benjamin
Published: January 2005

We propose a syntactic approach to performing fixed point computation on finite domains. Finding fixed points in finite domains for monotonic fuctions is an essential task when calculating abstract semantics of functional programs. Previous methods for fixed point finding have been mainly based on semantic approaches which may be very inefficient even for simple programs.

We outline the development of a syntactic approach, and show that the syntactic approach is sound and complete with respect to semantics. A few examples are provided to illustrate this syntactic approach.
On extending computational adequacy by data abstraction
Authors: Breazu-Tannen Val , Subrahmanyam Ramesh
Published: January 2005

Given an abstract data type(ADT), and algebra that
specifies
it, and an implementation of the data type in a certain language, if the implementation is “correct,” a certain principle of
modularity of reasoning
holds. Namely, one can safely reason about programs in the language extended by the ADT, by interpreting the ADT operation symbols according to the specification algebra. The main point of this paper is to formalize correctness as a local condition involving only the specification and the implementation and to prove the equivalence of such a condition to the modularity principle. We conduct our study in the context of a language without divergence (in subsection 2.1), and for languages with divergence and general recursion (in subsections 2.2 and 2.3). We also describe a sufficient condition under which, given an implementation, there may be a finite set of observational equivalences which imply the local condition. Further, we illustrate a technique for proving in a practical situation that a given implementation of an abstract data type is correct.
Type inference in the presence of overloading, subtyping and recursive types
Authors: Kaes Stefan
Published: January 2005

We present a unified approach to type inference in the presence of overloading and coercions based on the concept of
constrained types
. We define a generic inference system, show that subtyping and overloading can be treated as a special instance of this system and develop a simple algorithm to compute principal types. We prove the decidability of type inference for the class of
decomposable predicates
and develop a canonical representation for principal types based on
most accurate simplifications
of constraint sets. Finally, we investigate the extension of our techniques to
recursive types
.
WCL
Authors: Hennessey Wade
Published: January 2005

Common Lisp implementations for Unix have traditionally provided a rich development environment at the expense of an inefficient delivery environment. The goal of WCL is to allow hundreds of Lisp applications to be realistically available at once, while allowing several of them to run concurrently. WCL accomplishes this by providing Common Lisp as a UNIX shared library that can be linked with Lisp and C code to produce efficient applications. For example, the executable for a Lisp version of the canonical “Hello World!” program requires only 40k bytes under SunOS 4.1 for SPARC. WCL also supports a full development environment, including dynamic file loading and debugging. A modified version of GDB, the GNU Debugger, is used to debug WCL programs, providing support for mixed language debugging. The techniques used in WCL should also be applicable to other high-level languages that allow runtime mappings from names to objects.
Reasoning about programs in continuation-passing style.
Authors: Sabry Amr , Felleisen Matthias
Published: January 2005

Plotkin's λ-value calculus is sound but incomplete for reasoning about βeegr;-transformations on programs in continuation-passing style (CPS). To find a complete extension, we define a new, compactifying CPS transformation and an “inverse”mapping,
un
-CPS, both of which are interesting in their own right. Using the new CPS transformation, we can determine the precise language of CPS terms closed under β7eegr;-transformations. Using the
un
-CPS transformation, we can derive a set of axioms such that every equation between source programs is provable if and only if βη can prove the corresponding equation between CPS programs. The extended calculus is equivalent to an untyped variant of Moggi's computational λ-calculus.
Fast parallel implementation of lazy languages—the EQUALS experience
Authors: Kaser O. , Pawagi S. , Ramakrishnan C. R. , Ramakrishnan I. V. , Sekar R. C.
Published: January 2005

This paper describes EQUALS, a fast parallel implementation of a lazy functional language on a commercially available shared-memory parallel machine, the Sequent Symmetry. In contrast to previous implementations, we detect parallelism automatically by propagating exhaustive (normal form) demand. Another important difference between EQUALS and previous implementations is the use of reference counting for memory management instead of garbage collection. Our implementation shows that reference counting leads to very good scalability, low memory requirements and improved locality. We compare our results with sequntial SML/NJ as well as parallel (
v, G
-machine and GAML implementations.
The Boyer Benchmark at warp speed
Authors: Baker Henry G.
Published: January 2005

We show how to speed up the Boyer Benchmark by an order of magnitude (46 X faster than the Cray-1) on a Common Lisp system (80860-based OKIstation) using better programming techniques. The resulting program fits nicely within next generation on-chip caches and kills almost all potential parallelism, thus becoming worthless as a general-purpose Lisp benchmark.
A tachy “TAK”
Authors: Baker Henry G.
Published: January 2005

We show how to speed up the Tak Benchmark by an order of magnitude---5X faster than the Cray-1---on a Common Lisp system (40MHz 80860-based OKIstation) using memoizing. The list-based Takl Benchmark improves even more---30X faster than the Cray-1. Given the speed attainable through memoizing, the possibility of further speedups using parallelism seems unlikely.
dpANS Common Lisp
Authors: Pitman Kent M.
Published: January 2005

"It sure is big." I have made the rounds proudly showing off my copy of the final document to my friends and colleagues, and this is invariably their first comment. Counting cover sheets, tables of contents, etc.---it's about 1350 pages. It
is
big---no doubt about that.
What's in a Name?
Authors: Pitman Kent M.
Published: January 2005

Every now and then, when leafing through the trade rags or rummaging the shelves at a nearby computer store, I notice that some concept that I've known from the research community has crossed the magic threshold into commodity producthood and joined the ranks of other ubiquitous, meaningless, must-have product buzz phrases.
The scheme of things
Authors: Rees Jonathan
Published: January 2005

I have been hearing some complaints that Scheme's new lexically scoped macro facility is difficult to implement. There are two components to the proposal: the pattern language and lexical scoping. The two pose independent problems. I agree that the ellipsis-enriched pattern language can be tricky to implement; implementations that I have seen take anywhere from 250 to 1400 lines of Scheme code. However, I believe that it is conceptually straightforward, and several implementations have been around for many years (see [9]). On the other hand, many people are unnecessarily getting tripped up on lexical scoping, which, unlike the pattern matcher, is very simple to implement.
An experimental toolbox for advanced interactive learning environments
Authors: Schneider D. , Borcic B. , Dillenbourg P. , Hilario M. , Mendelsohn P.
Published: January 2005

The design of educational software has evolved during three decades, reflecting technical advances and changes in theories of instruction. In this project, we implemented some features of advanced interactive learning environments (ILEs): the multiplicity of teaching styles (the same content may be taught in several ways), the multiplicity of learning sources (experience, coaching, hypertext browsing), the use of a rich interface allowing direct manipulation and free exploration, the use of artificial intelligence techniques for creating complex problem situations and for supporting pedagogical reasoning.We developed an Experimental Toolbox for Interactive Learning Environments (ETOILE) and an application (MEMOLAB). ETOILE provides designers with a set of tools and resources allowing them to create their own ILE. Globally, ETOILE provides the pedagogical architecture while the designer provides the domain expertise and creates the specific parts of the interface. ETOILE is not an authoring tool that can be mastered by any genuine author, it is a toolbox to be used by designers with programming skills in Common Lisp and in CLIM (Common Lisp Interface Manager). ETOILE namely includes an Object-Oriented Production System, a hypertext, various interface management facilities and pedagogical knowledge bases.MEMOLAB is a learning environment for acquiring basic skills in experimentation methodology for human sciences. It illustrates the kind of systems that can be designed with ETOILE. MEMOLAB includes several components. The 'Lab' allows learners to build an experiment on human memory. The 'Simulation' produces the results of this experiment. The 'Data Tools' allow the learner to visualize the results and to compute basic statistics. During their activities, learners receive the assistance of a tutor. The system includes five different tutors, implementing various teaching styles. The learner may also explore the various hypertextes in which he can find knowledge about designing experiments and knowledge about human memory.The design of ETOILE and MEMOLAB reflects our efforts to translate a theory of development in terms of system specifications, namely to structure a learning session into a sequence of micro-worlds, each microworld being characterized by a specific interface language. The psychological theory is encoded in the relationship between the languages of successive microworlds. This kind of learning environment architecture is supported by the knowledge structures embedded in ETOILE.ETOILE and MEMOLAB currently have Beta Status. Both are available to the research community from our FTP server (Please contact the authors via e-mail for more information). A User Guide, and partially completed User Manual and Reference Manual are available.
Bungee jumping off the ivory tower
Authors: Hodgkinson John
Published: January 2005

From the viewpoint of at least one corporate consumer of computer education, Lisp-based training confers many professional advantages, even if the student never goes on to use Lisp in real life. Among these advantages are a grasp of computer science fundamentals that comes from simply knowing the Lisp language (Whorf was right, in this domain at least) and good software engineering habits (incremental development, abstraction, modularity, object-orientation). These habits are widely believed to be advantages, but Lisp is not widely seen as helping students acquire them. This paper will corroborate the connection between Lisp-based training and these good habits. On the other hand, some of these habits may not be good at all (this is one reading of Gabriel's "worse is better" theory). This paper will argue that Lisp-based training is more flexible than training based on popular imperative languages at discouraging the bad in these habits. Then this paper will describe some true drawbacks of Lisp-based training. These drawbacks include stylistic jingoism, excessive delegation of performance issues to the Lisp implementor or to the machine, superstitious avoidance of the more complex (albeit more casually implemented) Lisp facilities, stubborn reluctance to distinguish between compilation, runtime, and delivery environments, and a tendency to make use of Lisp's extensibility to re-invent the wheel merely because the tread size is not quite right. Ironically, Lisp itself contains the cure for the diseases it spreads. This paper concludes by offering, from real-world experience, some suggestions for modification, not abandonment, of Lisp-based training.
Knocking down the corporate barriers to Lisp
Authors: Zoeller Randal V. , Galarneau Jeff
Published: January 2005

It is a well-known fact that the software development industry has not embraced Lisp as a mainstream language. Despite the flexibility, power, and heritage of the language, the fact still remains---Lisp is a niche development language. While there remain staunch proponents of Lisp, their recommendations, proposals, and productivity gains are often overlooked. In many cases, the programming language used to develop an application is mandated by management, often for reasons that appear to make sense (e.g., availability of tools, portability of the application, and acceptability by the customer). How then do Lisp advocates gain acceptance against the groundswell generated by mainstream languages such as C and C++? Knocking down the barriers to Lisp involves not only co-existing with the mainstream languages but also complementing them. This paper describes business issues that must be addressed to enable Lisp to become accepted in the computer industry and in Corporate America as a whole. Additionally, it explains what it means to "complement" mainstream languages and describes some mechanisms used to accomplish this task.
SENEX
Authors: Ball Sheldon S. , Mah Vei H.
Published: January 2005

SENEX is a computer program in the domain of molecular pathology. The application allows an individual to ask a sequence of questions in a single interactive session, thereby facilitating the development and testing of several hypotheses in a short period of time. Cartoon representations of molecules and molecular events enable individuals to grasp spatial and functional relationships among molecules, cellular compartments, and cell regions. Well-defined reasoning capabilities allow an individual to ask sophisticated questions and to predict novel molecular events or pathways. SENEX contains information about: 1) the molecules and the motifs that impart function to these molecules; 2) the molecular events; 3) cell-specific expression of genes, 4) disease processes. SENEX is being developed through object-oriented programming in a portable programming environment supported by COMMON LISP and the COMMON LISP INTERFACE MANAGER.
Supporting complex flight scheduling tasks using CLOS and Statice
Authors: Grund Matthias , Timmermann Gerd
Published: January 2005

In the context of the actual trends towards downsizing and client-server architectures, new opportunities and also new requirements to integrate innovative solutions into conventional environments arise. In the future workstations will not just handle office activities and office communications, but moreover services like decision support systems and complex information systems will be available in a transparent way.
The Boyer benchmark meets linear logic
Authors: Baker Henry G.
Published: January 2005

Of the Gabriel Lisp Benchmarks, the Boyer Benchmark ("Boyer") is the most representative of real AI applications, because it performs Prolog-like rule-directed rewriting, and because it relies heavily on garbage collection (GC) for the recovery of storage. We investigated the notion that such programs are unsuitable for explicit storage management---e.g., by means of a "linear" programming style in which every bound name dynamically occurs exactly once. We programmed Boyer in a "linear" fragment of Lisp in both interpretive-rule and compiled-rule versions, using both true linear (unshared) and reference count methods.We found that since the intermediate result of rewrite is unshared, the linear interpreted version is slower than the non-linear interpreted version, while the linear compiled version is slightly faster than the non-linear compiled version. When sharing is allowed, requiring reference counts for the linear versions, the linear shared versions are not competitive with the non-linear versions, except when "anchored pointers" are used. The anchored pointer reference count version, which reclaims storage, is still 1.25X slower than the non-linear version, which reclaims no storage.
To nreverse when consing a list or by pointer manipulation, to avoid it; that is the question
Authors: Waters Richard C.
Published: January 2005

A situation that arises all the time in Lisp is the need to create a list of elements where the order of the elements in the list is the same as the order that they are created in time---i.e., the first element computed is the first element in the list, the second element computed is the second element in the list, etc. There are two basic ways of doing this: the
nreverse
approach and the
rplacd
approach. In the
nreverse
approach, you push the elements onto the list as they are computed and then use
nreverse
to put the list into the correct order after all of the elements have been computed. In the
rplacd
approach, you maintain a pointer to the end of the list and use
rplacd
to put each element directly into its proper place in the list.
EQUAL rights—and wrongs—in Lisp
Authors: Pitman Kent M.
Published: January 2005

Operations in Lisp, Scheme, and other dynamically-typed languages typically dispatch on representational type information rather than intentional type information. Several broad classes of bugs and confusions can be traced to improper attempts to recover intentional type information from representation types.
Sweet harmony
Authors: Davis Harley , Parquier Pierre , Séniak Nitsan
Published: January 2005

A tight, transparent, and portable integration between C++ and LISP is desirable and feasible. This paper describes the C++ interface supplied with, a modern LISP dialect which extends the proposed ISLisp standard with a module system, a metaobject protocol, and an extensive set of libraries. The interface parses C++ header files and generates C++ stub interface files, as well as TALK modules which implement proxy classes and TALK foreign function definitions for C++ functions. The programmer then has nearly complete access to the functionality of a C++ library.
A randomized implementation of multiple functional arrays
Authors: Chuang Tyng-Ruey
Published: January 2005

The array update problem in the implementation of a purely functional language is the following: once an array is updated, both the original array and the newly updated one must be preserved to maintain referential transparency. Previous approaches have mainly based on the detection or enforcement of single-threaded accesses to an aggregate, by means of compiler-time analyses or language restrictions. These approaches cannot deal with aggregates which are updated in a multi-threaded manner.

Baker's shallow binding scheme can be used to implement multi-threaded functional arrays. His scheme, however, can be very expensive if there are repeated alternations between long binding paths. We design a scheme that fragments binding paths randomly. The randomization scheme is on-line, simple to implement, and its expected performance comparable to that of the optimal off-line solutions. All this is achieved without using compiler-time analyses, and without restricting the languages.

The expected performance of the randomization scheme is analyzed in details, and some preliminary results are shown. Applications of the randomization technique to other functional aggregates, as well as its implications, are briefly outlined.
An efficient implementation of multiple return values in Scheme
Authors: Ashley J. Michael , Dybvig R. Kent
Published: January 2005

This paper describes an implementation of the new Scheme multiple values interface. The implementation handles multiple values efficiently, with no run-time overhead for normal calls and returns. Error checks are performed where necessary to insure that the expected number of values is returned in all situations. The implementation fits cleanly with our direct-style compiler and stack-based representation of control, but is equally well suited to continuation-passing style compilers and to heap-based run-time architectures.
Concurrent replicating garbage collection
Authors: O'Toole James , Nettles Scott
Published: January 2005

We have implemented a concurrent copying garbage collector that uses replicating garbage collection. In our design, the client can continuously access the heap during garbage collection. No low-level synchronization between the client and the garbage collector is required on individual object operations. The garbage collector replicates live heap objects and periodically synchronizes with the client to obtain the client's current root set and mutation log. An experimental implementation using the Standard ML of New Jersey system on a shared-memory multiprocessor demonstrates excellent pause time performance and moderate execution time speedups.
Using the run-time sizes of data structures to guide parallel-thread creation
Authors: Huelsbergen Lorenz , Larus James R. , Aiken Alexander
Published: January 2005

Dynamic granularity estimation is a new technique for automatically identifying expressions in functional languages for parallel evaluation. Expressions with little computation relative to thread-creation costs should evaluate sequentially for maximum performance. Static identification of such threads is however difficult. Therefore, dynamic granularity estimation has compile-time and run-time components: Abstract interpretation statically identifies functions whose complexity depends on data structure sizes; the run-time system maintains approximations to these sizes. Compiler-inserted checks consult this size information to make thread creation decisions dynamically.

We describe dynamic granularity estimation for a list-based functional language. Extension to general recursive data structures and imperative operations is possible. Performance measurements of dynamic granularity estimation in a parallel ML implementation on a shared-memory machine demonstrate the possibility of large reductions (>20%) in execution time.