|
Sarah Thompson's Lab Notebook
|
|
|
| Representing cyclic data structures in Haskell |
[Jul. 22nd, 2003|04:31 pm] |
Here are some notes relating to a recent thread on haskell-cafe, started by yours-truly with this question:
------------------------
What is the best way to represent cyclic data structures in Haskell?
Lists are trivial. Trees are trivial. But what if the thing you're trying to represent is shaped like an electronic circuit, with a (possibly large) number of nodes connected by multiple arrows to other nodes? In an imperative language like C++, I'd probably just model the circuit directly, with objects representing nodes and pointers representing links between nodes. A good way to model this in Haskell is less obvious, however.
A simplistic approach would be to represent such a structure as a list of nodes, where each node contained a list of other connected nodes. Containing the actual nodes within the sub-lists probably isn't feasible -- some kind of reference would be necessary in order to get around chicken-and-egg problems with instantiating the data structure. But, in this case, it's not so easy to see how one could 'walk' the structure efficiently, because moving from node to node would involve quite horrible (possibly slow) lookups. In C++, I'd simply follow a pointer, which would be an extremely fast operation.
I would also need to implement efficient indexes into the data structure -- flat searching will be too slow for non-trivial amounts of data. In C++, I'd implement one or more external (probably STL-based) indexes that point into the main data structure.
How do people typically solve this problem at the moment? I know a few people out there have written hardware compilers in Haskell and similar languages, so there should be some experience of this in the community. I can probably work something out soon enough, but reinventing the wheel is never a great idea.
------------------------
Here is a potted series of responses, some of which are definitely worth following up in more detail:
( Read more... ) |
|
|
| wxHaskell |
[Jul. 22nd, 2003|03:49 pm] |
This looks heavensent (if it works! -- need to try it and see!)
--------------
Announcement: wxHaskell 0.1
---------------------------
http://wxhaskell.sourceforge.net/
wxHaskell is a new portable GUI library for Haskell. The goal of the
project is to provide an industrial strength portable GUI library, but
without the burden of developing (and maintaining) one ourselves.
wxHaskell is therefore build on top of wxWindows -- a comprehensive
C++ library that is portable across all major GUI platforms; including
GTK, Windows, X11, and MacOS X. Furthermore, it is a mature library
(in development since 1992) that supports a wide range of widgets with
native look-and-feel, and it has a very active community (ranked among
the top 25 most active projects on sourceforge).
Since most of the interface is automatically generated from the
wxEiffel binding, the current release of wxHaskell already supports
about 75% of the wxWindows functionality -- about 2500 methods in 500
classes with 1200 constant definitions.
wxHaskell has been build with GHC 6.0 on Windows, MacOS X and Unix
systems with GTK. A binary distribution is available for Windows (and
we are working on a binary release for MacOS X).
And even if you don't intend to write GUI's yourself, it will be fun
to check out the screenshots at <http://wxhaskell.sourceforge.net>.
All the best,
Daan Leijen.
_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell |
|
|
| Arvind's talk [Fri 15 Aug, provisionally 09:30, room TBA (FW26?)] |
[Jul. 22nd, 2003|03:38 pm] |
Cross-posted from cprg-announce:
Bluespec: Why chip design can't be left to EE's
Arvind
CSAIL (formerly LCS and AI Lab)
Massachusetts Institute of Technology
A 5M-gate ASIC is common place in 180nm technology today. We may see 50M to
100M-gate ASICs within a decade as technology improves to sub 90nm. (Fully
custom-designed microprocessors are, of course, much denser and faster then
ASICs but also require dramatically more design resources). Numerous
problems related to process and design need to be solved before such large
chips will become commonplace. Some of these problems, e.g., leaky
transistors, porous oxide, controlling multiple Vt's are clearly in the
domain of EE's but computer scientists are much better equipped to solve
the new problems related to the design-in-the-large. Large designs have to
be conceived and executed in terms of a hierarchy of blocks. The hierarchy
cannot be constructed in an ad hoc manner but should use some method of
composition systematically. For example, the functionality of a proper
composition of blocks has to be derivable from the functionality of
individual blocks. Bluespec is a language/methodology that promotes
correctness-by-construction. Its underlying execution model is based on
atomic actions on state elements (flip-flops, registers, ...), i.e., any
legal behavior is explainable in a terms of a sequence of atomic actions on
the state. Bluespec has facilities for expressing highly parameterized
modules ('generic classes" in the language sense) and an expressive
language to compose modules. The expressivity of the language has no limits
because its semantics are orthogonal to hardware execution semantics -- the
source program is turned into a flat interconnection of modules by "static
elaboration" during the compile phase.
In this talk I will present Bluespec via examples and show some of the
designs done so far.
Bluespec is a joint work of people at MIT and Sandburst Corporation.
Arvind is the Johnson Professor of Computer Science and Engineering at the
Massachusetts Institute of Technology. As the Founder and President of
Sandburst, Arvind led the Company from its inception in June 2000 until his
return to MIT in August 2002. His work at MIT on high-level specification
and description of architectures and protocols using Term Rewriting Systems
(TRSs), encompassing hardware synthesis as well as verification, laid the
foundations for Sandburst. Previously, he contributed to the development of
dynamic dataflow architectures, and together with Dr R.S.Nikhil published
the book "Implicit Parallel Programming in pH". Arvind is an IEEE Fellow
and was awarded the Charles Babbage Outstanding Scientist Award in 1994. He
has received the Distinguished Alumni Awards from the Indian Institute of
Technology, Kanpur, and the University of Minnesota. |
|
|
| Lazy specialisation thesis |
[Jul. 22nd, 2003|03:38 pm] |
This looks interesting:
http://www-users.cs.york.ac.uk/mjt/thesis-thyer.pdf (temporary link),
see also:
http://www.cs.york.ac.uk/ftpdir/reports/ (permanent)
Alan Mycroft passed on the link. Looks interesting from the abstract:
This thesis describes a scheme to combine the benefits of lazy evaluation
with partial evaluation. By performing specializations only when needed
(lazily), the specialize-residualize decision is changed from being semantic
to operational. It is demonstrated that a completely lazy evaluator is
capable of eliminating towers of interpreters. The scheme is generalised,
devising a new implementation of optimal evaluation, and it is demonstrated
that optimal evaluators do not eliminate towers of interpreters.
It is argued that the concept of scope has too often been overlooked in the
lambda-calculus. A new system of depths is introduced in order to handle
the issue of scope. The new approach leads to a much richer understanding
of the issue of sharing in the lambda-calculus. Although optimal evaluators
are well known, it is argued that less well understood degrees of sharing,
in between the sharing of conventional functional languages and optimal
evaluators, are of more practical use. A new classification of possible
function body reduction strategies is shown to be analogous and orthogonal
to argument reduction strategies. |
|
|
| My Lab Notebook |
[Jul. 22nd, 2003|03:27 pm] |
I've created this second LiveJournal as a lab notebook. Don't expect to find any personal comments here -- this journal is purely intended as a convenient place to store notes, thoughts, links and other low grade meanderings related to my PhD studies. If you find anything of use here, you're welcome to it! ;-)
Sarah Thompson |
|
|
| navigation |
| [ |
viewing |
| |
most recent entries |
] |
| |
|
|
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
labnotes's journal