[racket] OPERATING SYSTEM ON A FPGA

From: Patrick Li (patrickli.2001 at gmail.com)
Date: Wed Dec 5 13:30:59 EST 2012
Previous message: [racket] OPERATING SYSTEM ON A FPGA
Next message: [racket] OPERATING SYSTEM ON A FPGA
Messages sorted by: [date] [thread] [subject] [author]
Hello,

I am personally also very interested in this topic, if Matthias and Erich
would shed some light on it.

I have only done system programming in assembly and C, and found that I
frequently did a lot of manual placement and shuffling of data in memory,
with the usual pointer tricks.

Off the top of my head, I do not how those same tasks would be accomplished
in a dynamically typed, and garbage-collected language like Scheme. Would
anyone be able to explain the gist of it?

Of course, there are real systems that are actually built upon such
languages. The Symbolics machines and Wirth's Oberon systems come to mind.
I am still reading through resources to figure out how they did it.

Thank you for any insight offered.
  -Patrick

On Wed, Dec 5, 2012 at 10:30 AM, Patrick Li <patrickli.2001 at gmail.com>wrote:

> Hello,
>
> I am personally also very interested in this topic, if Matthias and Erich
> would shed some light on it.
>
> I have only done system programming in assembly and C, and found that I
> frequently did a lot of manual placement and shuffling of data in memory,
> with the usual pointer tricks.
>
> Off the top of my head, I do not how those same tasks would be
> accomplished in a dynamically typed, and garbage-collected language like
> Scheme. Would anyone be able to explain the gist of it?
>
> Of course, there are real systems that are actually built upon such
> languages. The Symbolics machines and Wirth's Oberon systems come to mind.
> I am still reading through resources to figure out how they did it.
>
> Thank you for any insight offered.
>   -Patrick
>
>
>
>
> On Wed, Dec 5, 2012 at 9:30 AM, Rüdiger Asche <rac at ruediger-asche.de>wrote:
>
>> **
>> well, I hate to spoil the fun (and it IS fun - I once wrote a task
>> scheduler built on engines, and I thoroughly enjoyed it), but a) the last
>> thing the world needs is yet another operating system, and b) Scheme (and
>> in particular Racket) are pretty poor choices for underlying architectures.
>> In low level software design, you MUST a) have real time behavior at least
>> in the kernel (which doesn't go well with anything that has JIT and garbage
>> collection in it) and b) have some kind of control over hardware -
>> placement of code and data in memory, access to memory mapped peripheral
>> I/O, interrupt handlers and so on. By definition, none of the above blend
>> in well with the (otherwise very desireable) abstraction features of
>> Scheme. In fact, the predominant language Embedded systems are written in
>> is still C, sometimes C++ - but no language that does not support pointers
>> or address casts will ever have a chance to be a building block for
>> embedded systems.
>>
>> I've given this very issue a lot of thought recently (I am a full time
>> embedded software designer and planned on doing an embedded system
>> completly in Scheme myself), and eventually I decided that without
>> compromising a number of the fundamentail tenets of Scheme, there simply
>> isn't a point (you'd have to provide a number of extensions that plainly
>> contradict the Scheme philosophy). Of course I'll be happy to be proven
>> wrong. I am aware of a few attempts made at it, but as far as I can tell,
>> those were useful only in a very limited environment, and to my best
>> knowledge, none has ever made it into the commercial world.
>>
>> And of course, for academic purposes, there is always a place for a
>> project like that, but I don't see any money in the real world to be made
>> with that kind of thing, given that the first questions it must answer are
>> "will it run my iPhone apps" and "does it support the Graphmaster AX-B34x
>> series of graphics cards in accelerated mode?"
>>
>>
>> ----- Original Message -----
>> *From:* David Blubaugh <davidblubaugh2000 at yahoo.com>
>> *To:* Matthias Felleisen <matthias at ccs.neu.edu>
>> *Cc:* users at racket-lang.org
>> *Sent:* Wednesday, December 05, 2012 5:29 PM
>> *Subject:* Re: [racket] OPERATING SYSTEM ON A FPGA
>>
>>   Well
>>
>>
>> Is there a way I can obtain help in acquiring funding in developing
>> Racket into a real OS??  I would love to see how far we can take this
>> concept !!!
>>
>> Apple and MacOS watch out here comes something with more powerful
>> features !!!
>>
>> David Blubaugh
>>
>> --- On *Wed, 12/5/12, Matthias Felleisen <matthias at ccs.neu.edu>* wrote:
>>
>>
>> From: Matthias Felleisen <matthias at ccs.neu.edu>
>> Subject: Re: [racket] OPERATING SYSTEM ON A FPGA
>> To: "David Blubaugh" <davidblubaugh2000 at yahoo.com>
>> Cc: users at racket-lang.org
>> Date: Wednesday, December 5, 2012, 11:24 AM
>>
>>
>> In the mid 90s, we had this idea to go for a Scheme OS, SOS. As an
>> experiment, we asked a student to write a disk driver in Scheme (Bigloo)
>> and to see what we could do with it. One of the things he was able to do is
>> hot-swap policies for spinning the disk. This sounds so quaint in the age
>> of laptops w/o movable parts.
>>
>> In the late 90s, Matthew spent an afternoon so that we could boot Racket
>> (formerly known as PLT Scheme) on raw hardware. Since most of us had
>> dual-boot machines already (Linux and the other one), we went to
>> ternary-boot machines: Linux, PLT Scheme, and the other one. None of us
>> ever had the appetite to add enough device drivers to turn Racket into a
>> real OS but nothing stands in its way.
>>
>> Right now, a Darpa project enables us to experiment with Racket on the
>> Router (think RoR, though that acronym has been taken). Again, it's
>> systemish work. This email is going thru the DNS service that we have built
>> so far.
>>
>> In short, doable but we haven't done it.
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> On Dec 5, 2012, at 11:16 AM, David Blubaugh wrote:
>>
>> > To All,
>> >
>> >
>> > I was wondering if anyone has ever created a real time operating system
>> with Racket.  As well as, create applications within a FPGA device by
>> utilizing racket??  Can racket be a solution to ALL PROBLEMS that is the
>> question.
>> >
>> >
>> > David Blubaugh
>> >
>> >
>> >
>> > --- On Wed, 12/5/12, users-request at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users-request@racket-lang.org><
>> users-request at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users-request@racket-lang.org>>
>> wrote:
>> >
>> > From: users-request at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users-request@racket-lang.org><
>> users-request at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users-request@racket-lang.org>
>> >
>> > Subject: users Digest, Vol 88, Issue 18
>> > To: users at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users@racket-lang.org>
>> > Date: Wednesday, December 5, 2012, 10:30 AM
>> >
>> > Send users mailing list submissions to
>> >     users at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users@racket-lang.org>
>> >
>> > To subscribe or unsubscribe via the World Wide Web, visit
>> >     http://lists.racket-lang.org/users/listinfo
>> > or, via email, send a message with subject or body 'help' to
>> >     users-request at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users-request@racket-lang.org>
>> >
>> > You can reach the person managing the list at
>> >     users-owner at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users-owner@racket-lang.org>
>> >
>> > When replying, please edit your Subject line so it is more specific
>> > than "Re: Contents of users digest..."
>> >
>> >
>> > [Racket Users list:
>> > http://lists.racket-lang.org/users]
>> >
>> >
>> > Today's Topics:
>> >
>> >    1. Re: Whats the difference between a predicate and a flat
>> >       contract? (Harry Spier)
>> >    2. Re: Whats the difference between a predicate and a flat
>> >       contract? (Robby Findler)
>> >    3. Re: DRRacket right-click menu fragility in Linux. (Neil Toronto)
>> >    4. Re: minimum spanning tree (Matthias Felleisen)
>> >
>> >
>> > ----------------------------------------------------------------------
>> >
>> > Message: 1
>> > Date: Tue, 4 Dec 2012 21:59:42 -0500
>> > From: Harry Spier <vasishtha.spier at gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=vasishtha.spier@gmail.com>
>> >
>> > To: Robby Findler <robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>
>> >
>> > Cc: Carl Eastlund <cce at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=cce@ccs.neu.edu>>,
>> users <users at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users@racket-lang.org>
>> >
>> > Subject: Re: [racket] Whats the difference between a predicate and a
>> >     flat    contract?
>> > Message-ID:
>> >     <CAJ3b0o9_yd-j4U6tbEOQaB+JKWto_A1XwSrh3_xyRTk=Uviy=Q at mail.gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=Q@mail.gmail.com>
>> >
>> > Content-Type: text/plain; charset=UTF-8
>> >
>> > Are flat-contract and flat-contract-predicate equivalent?
>> >
>> > > ((flat-contract 'x) 'x)
>> > #t
>> > > ((flat-contract-predicate 'x) 'x)
>> > #t
>> > > ((flat-contract 'x) 'y)
>> > #f
>> > > ((flat-contract-predicate 'x) 'y)
>> > #f
>> > >
>> >
>> > Harry
>> >
>> > On Tue, Dec 4, 2012 at 9:41 PM, Robby Findler
>> > <robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>>
>> wrote:
>> > > It does that for symbols, but not everything.
>> > >
>> > > This is the place you should be looking, I think.
>> > >
>> > > http://docs.racket-lang.org/reference/contracts.html
>> > >
>> > > Robby
>> > >
>> > > On Tue, Dec 4, 2012 at 8:38 PM, Harry Spier <
>> vasishtha.spier at gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=vasishtha.spier@gmail.com>>
>> wrote:
>> > >> OK I see the docs to flat-contract? but not flat-contract
>> > >> http://docs.racket-lang.org/reference/contract-utilities.html#
>> (def._((lib._racket/contract/private/misc..rkt)._flat-contract~3f))
>> > >> mention that flat-contracts are more than predicates.  Those docs
>> > >> don't mention it, but it appears from experimentation that
>> > >> (flat-contract something) produces a procedure such that
>> > >> ((flat-contract something) x) is #t if something eq? x .
>> > >>
>> > >> Harry Spier
>> > >>
>> > >> On Tue, Dec 4, 2012 at 8:57 PM, Robby Findler
>> > >> <robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>>
>> wrote:
>> > >>> On Tue, Dec 4, 2012 at 7:28 PM, Carl Eastlund <cce at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=cce@ccs.neu.edu>>
>> wrote:
>> > >>>> On Tue, Dec 4, 2012 at 7:49 PM, Robby Findler <
>> robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>
>> >
>> > >>>> wrote:
>> > >>>>>
>> > >>>>> Flat contracts includes more things than contracts. For example:
>> > >>>>>
>> > >>>>> [robby at yanpu] ~/git/plt/collects/scribblings/reference$ racket
>> > >>>>> Welcome to Racket v5.3.1.9.
>> > >>>>> > (flat-contract? 'x)
>> > >>>>> #t
>> > >>>>> > (procedure? 'x)
>> > >>>>> #f
>> > >>>>>
>> > >>>>> The flat-contract function is a holdover from the days when flat
>> contracts
>> > >>>>> weren't able to be used directly as predicate functions.
>> > >>>>>
>> > >>>>>
>> > >>>>> I'll push a clarification to the docs for flat-contract.
>> > >>>>
>> > >>>>
>> > >>>> Isn't that the wrong way around?  The flat-contract function lets
>> you use a
>> > >>>> predicate as a contract, not a contract as a predicate.
>> Presumably it's
>> > >>>> from before predicates could be used as contracts, although I
>> hadn't
>> > >>>> realized there was such a time.
>> > >>>
>> > >>> There was a time when you had to call 'flat-contract' to turn a
>> > >>> predicate into a contract, yep. There was a housecleaning (anyone
>> > >>> remember the days when there were multiple suffixes (not just "/c")
>> on
>> > >>> the combinators?) and I probably should have gotten rid of it at
>> that
>> > >>> time, but I didn't.
>> > >>>
>> > >>> (Oh and I mean "contracts" where I wrote "preducate functions"
>> above. Oops.)
>> > >>>
>> > >>> Robby
>> >
>> >
>> > ------------------------------
>> >
>> > Message: 2
>> > Date: Tue, 4 Dec 2012 21:05:45 -0600
>> > From: Robby Findler <robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>
>> >
>> > To: Harry Spier <vasishtha.spier at gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=vasishtha.spier@gmail.com>
>> >
>> > Cc: Carl Eastlund <cce at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=cce@ccs.neu.edu>>,
>> users <users at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users@racket-lang.org>
>> >
>> > Subject: Re: [racket] Whats the difference between a predicate and a
>> >     flat    contract?
>> > Message-ID:
>> >     <CAL3TdOMVL4xerBMr9xWqNz3tPjxbSXDfjaiJro2N9j6fxrSrOQ at mail.gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=CAL3TdOMVL4xerBMr9xWqNz3tPjxbSXDfjaiJro2N9j6fxrSrOQ@mail.gmail.com>
>> >
>> > Content-Type: text/plain; charset=UTF-8
>> >
>> > Yes ..., I think so (well, eq? probably messes things up, as usual).
>> >
>> > But that's a funny question! What's really going on there is that
>> > flat-contract is coercing the value into a contract, and flat
>> > contracts also acts as predicate functions (matching what the
>> > contracts match). flat-contract-predicate takes its argument, turns it
>> > into the contract and then returns the predicate. This last step is
>> > useless, as flat-contracts are now predicates without any coercion
>> > (again, not something that was always the case).
>> >
>> > I'll add a similar note to the docs for this function too.
>> >
>> > Robby
>> >
>> > On Tue, Dec 4, 2012 at 8:59 PM, Harry Spier <vasishtha.spier at gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=vasishtha.spier@gmail.com>>
>> wrote:
>> > > Are flat-contract and flat-contract-predicate equivalent?
>> > >
>> > >> ((flat-contract 'x) 'x)
>> > > #t
>> > >> ((flat-contract-predicate 'x) 'x)
>> > > #t
>> > >> ((flat-contract 'x) 'y)
>> > > #f
>> > >> ((flat-contract-predicate 'x) 'y)
>> > > #f
>> > >>
>> > >
>> > > Harry
>> > >
>> > > On Tue, Dec 4, 2012 at 9:41 PM, Robby Findler
>> > > <robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>>
>> wrote:
>> > >> It does that for symbols, but not everything.
>> > >>
>> > >> This is the place you should be looking, I think.
>> > >>
>> > >> http://docs.racket-lang.org/reference/contracts.html
>> > >>
>> > >> Robby
>> > >>
>> > >> On Tue, Dec 4, 2012 at 8:38 PM, Harry Spier <
>> vasishtha.spier at gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=vasishtha.spier@gmail.com>>
>> wrote:
>> > >>> OK I see the docs to flat-contract? but not flat-contract
>> > >>> http://docs.racket-lang.org/reference/contract-utilities.html#
>> (def._((lib._racket/contract/private/misc..rkt)._flat-contract~3f))
>> > >>> mention that flat-contracts are more than predicates.  Those docs
>> > >>> don't mention it, but it appears from experimentation that
>> > >>> (flat-contract something) produces a procedure such that
>> > >>> ((flat-contract something) x) is #t if something eq? x .
>> > >>>
>> > >>> Harry Spier
>> > >>>
>> > >>> On Tue, Dec 4, 2012 at 8:57 PM, Robby Findler
>> > >>> <robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>>
>> wrote:
>> > >>>> On Tue, Dec 4, 2012 at 7:28 PM, Carl Eastlund <cce at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=cce@ccs.neu.edu>>
>> wrote:
>> > >>>>> On Tue, Dec 4, 2012 at 7:49 PM, Robby Findler <
>> robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>
>> >
>> > >>>>> wrote:
>> > >>>>>>
>> > >>>>>> Flat contracts includes more things than contracts. For example:
>> > >>>>>>
>> > >>>>>> [robby at yanpu] ~/git/plt/collects/scribblings/reference$ racket
>> > >>>>>> Welcome to Racket v5.3.1.9.
>> > >>>>>> > (flat-contract? 'x)
>> > >>>>>> #t
>> > >>>>>> > (procedure? 'x)
>> > >>>>>> #f
>> > >>>>>>
>> > >>>>>> The flat-contract function is a holdover from the days when flat
>> contracts
>> > >>>>>> weren't able to be used directly as predicate functions.
>> > >>>>>>
>> > >>>>>>
>> > >>>>>> I'll push a clarification to the docs for flat-contract.
>> > >>>>>
>> > >>>>>
>> > >>>>> Isn't that the wrong way around?  The flat-contract function lets
>> you use a
>> > >>>>> predicate as a contract, not a contract as a predicate.
>> Presumably it's
>> > >>>>> from before predicates could be used as contracts, although I
>> hadn't
>> > >>>>> realized there was such a time.
>> > >>>>
>> > >>>> There was a time when you had to call 'flat-contract' to turn a
>> > >>>> predicate into a contract, yep. There was a housecleaning (anyone
>> > >>>> remember the days when there were multiple suffixes (not just
>> "/c") on
>> > >>>> the combinators?) and I probably should have gotten rid of it at
>> that
>> > >>>> time, but I didn't.
>> > >>>>
>> > >>>> (Oh and I mean "contracts" where I wrote "preducate functions"
>> above. Oops.)
>> > >>>>
>> > >>>> Robby
>> >
>> >
>> > ------------------------------
>> >
>> > Message: 3
>> > Date: Tue, 04 Dec 2012 21:30:23 -0700
>> > From: Neil Toronto <neil.toronto at gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=neil.toronto@gmail.com>
>> >
>> > To: users at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users@racket-lang.org>
>> > Subject: Re: [racket] DRRacket right-click menu fragility in Linux.
>> > Message-ID: <50BECDDF.4030508 at gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=50BECDDF.4030508@gmail.com>
>> >
>> > Content-Type: text/plain; charset=UTF-8; format=flowed
>> >
>> > Could what you're experiencing have anything to do with tooltips? It
>> > seems my right-click menu doesn't stay up whenever there's a tooltip
>> > out. Which is, like, every time I want it.
>> >
>> > Neil ?
>> >
>> > On 12/04/2012 07:55 PM, Ray Racine wrote:
>> > > Yea, I didn't want to make a big deal out of it, but the up/down
>> button
>> > > change did not fix the issue.   In fact I'd say no impact positive or
>> > > negative.
>> > >
>> > > It seems to happen when there is additional drawing 'complexity' in
>> > > co-occurrence with the pop up drawing area.  I.e. the pop up menu is
>> > > drawing where arrows are drawn or error highlighting is occurring etc.
>> > > Also maybe when the pop up menu area is near the 'edge' of the Dr
>> window
>> > > and or pane area.  But again the problem is not consistently
>> > > reproducible yet happens more often then not.  Its not a once in a
>> blue
>> > > moon that thing.  Sometimes an attempt to right click pop up  menu
>> will
>> > > fail numerous times in a row then succeed for no apparent reason.
>> > >
>> > > On Dec 4, 2012 9:07 PM, "Robby Findler" <robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>
>> > > <mailto:robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>>>
>> wrote:
>> > >
>> > >     On Tue, Dec 4, 2012 at 6:11 PM, Stephen Chang <
>> stchang at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=stchang@ccs.neu.edu>
>> > >     <mailto:stchang at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=stchang@ccs.neu.edu>>>
>> wrote:
>> > >      > On Fri, Nov 2, 2012 at 9:33 PM, Robby Findler
>> > >      > <robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>
>> > >     <mailto:robby at eecs.northwestern.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=robby@eecs.northwestern.edu>>>
>> wrote:
>> > >      >> I've pushed a fix to this. Thanks to Matthew for looking into
>> it and
>> > >      >> sorting it out and sorry for the delay.
>> > >      >
>> > >      > I'm using git head and I'm still seeing this problem (Ubuntu
>> > >     11.10). I
>> > >      > can't reliably reproduce it but in case it helps, it most
>> recently
>> > >      > happened when I selected tack arrows and now I can't bring up
>> the
>> > >     menu
>> > >      > to untack the arrows anymore.
>> > >      >
>> > >
>> > >     The particular fix Matthew pointed me to is popping up the menu
>> on a
>> > >     mouse down event, not a mouse up event.
>> > >
>> > >
>> http://git.racket-lang.org/plt/blobdiff/27aa99944657c5827eee3772f715df7dd971d1e0..0377bda9474f8848a97509ace898174c83361006:/collects/framework/private/keymap.rkt
>> > >
>> > >     So I guess there's something else going on, too (because that's
>> the
>> > >     code that pops up the menu with the check syntax items).
>> > >
>> > >     Robby
>> > >
>> > >
>> > >
>> > > ____________________
>> > >    Racket Users list:
>> > >    http://lists.racket-lang.org/users
>> > >
>> >
>> >
>> >
>> > ------------------------------
>> >
>> > Message: 4
>> > Date: Wed, 5 Dec 2012 10:30:22 -0500
>> > From: Matthias Felleisen <matthias at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=matthias@ccs.neu.edu>
>> >
>> > To: Pierpaolo Bernardi <olopierpa at gmail.com<http://us.mc1133.mail.yahoo.com/mc/compose?to=olopierpa@gmail.com>
>> >
>> > Cc: Racket mailing list <users at racket-lang.org<http://us.mc1133.mail.yahoo.com/mc/compose?to=users@racket-lang.org>
>> >
>> > Subject: Re: [racket] minimum spanning tree
>> > Message-ID: <CE678990-63D0-4400-AF2A-C6B2880E4FFB at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=CE678990-63D0-4400-AF2A-C6B2880E4FFB@ccs.neu.edu>
>> >
>> > Content-Type: text/plain; charset="iso-8859-1"
>> >
>> >
>> > You are making a very good point here, especially the last one,
>> > which in a sense exposes the folly of Perlis's maxim (it is better
>> > to have one data type with a 100 operations than 10 data types
>> > with 10 operations each). One, the maxim biases programmers
>> > and before they know it, they have introduced bad dependences
>> > and performance problems and whoknowswhat.
>> >
>> > ---------------------------------------------------------------
>> >
>> > Having said that, I think Ian's point is equally good. So here
>> > is what I am wondering.
>> >
>> > Isn't the case of graphs worth a case study where we define
>> > a WIDE interface for graphs and their operations, which we
>> > can do so with contracts. Then we implement it in several
>> > different ways and conduct performance studies (small and
>> > large). And we advertise, which library is good for which
>> > kind of scenario.
>> >
>> > I am sure that some data structure person has done this
>> > for C++ or some such language. The Saarbr?cken MPI 1 comes
>> > to mind. BUT, I am also sure that we don't have it and that
>> > we would benefit from having one.
>> >
>> > NOW: as we conduct this study, we might be able to articulate
>> > performance "contracts" (that's probably the wrong word) and
>> > possibly learn how to add those to library implementations as
>> > a secondary interface. Doing so would once again distinguish
>> > Racket from other programming languages.
>> >
>> > It is probably a dissertation, possibly more.
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > On Dec 4, 2012, at 5:36 AM, Pierpaolo Bernardi wrote:
>> >
>> > > On Mon, Dec 3, 2012 at 5:07 PM, J. Ian Johnson <ianj at ccs.neu.edu<http://us.mc1133.mail.yahoo.com/mc/compose?to=ianj@ccs.neu.edu>>
>> wrote:
>> > >> Graph algorithms are often meant to be very fast, and different
>> algorithms necessitate different representations. Two popular
>> representations are adjacency lists and shared structures.
>> > >
>> > > The representations usually used in general purpose graphs libraries
>> > > are adiacency lists and incidence matrices.
>> > >
>> > > Two good examples that I know of are:  Knuth's Stanford GraphBase
>> > > (available from his home page and in published book form), and the
>> > > Combinatorica library for Mathematica (code available freely on the
>> > > net, manual available as a published book "Computational Discrete
>> > > Mathematics" by Skiena & Pemmaraju).
>> > >
>> > >> It also isn't right to call them lists unless you're talking about
>> multigraphs. Indeed successor nodes should be treated as a set, but
>> Racket's sets have quite a bit of overhead, especially for small sets.
>> Should it be fast to compute predecessor nodes? There are too many
>> considerations for there to be just one blessed representation, IMHO.
>> > >
>> > > Linked lists made of cons pairs are not the best data structure for
>> > > every possible use of a sequence data structure.  However, we find
>> > > this data structure very useful, don't we?  we force them into uses
>> > > for which they are not optimal, because of the convenience of having
>> > > available a vast library using them. And when we can't fit them to our
>> > > purpose we use a more specialized data structure.
>> > >
>> > > I think a similar compromise for a graph data structure would be very
>> useful.
>> > >
>> > > Cheers
>> > > P.
>> > >
>> > > ____________________
>> > >  Racket Users list:
>> > >  http://lists.racket-lang.org/users
>> >
>> > -------------- next part --------------
>> > A non-text attachment was scrubbed...
>> > Name: smime.p7s
>> > Type: application/pkcs7-signature
>> > Size: 4373 bytes
>> > Desc: not available
>> > URL: <
>> http://lists.racket-lang.org/users/archive/attachments/20121205/52954024/attachment.p7s
>> >
>> >
>> > End of users Digest, Vol 88, Issue 18
>> > *************************************
>> > ____________________
>> >  Racket Users list:
>> >  http://lists.racket-lang.org/users
>>
>>  ------------------------------
>>
>> ____________________
>>   Racket Users list:
>>   http://lists.racket-lang.org/users
>>
>>
>> ____________________
>>   Racket Users list:
>>   http://lists.racket-lang.org/users
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20121205/7b3dfa6c/attachment-0001.html>
Posted on the users mailing list.
Previous message: [racket] OPERATING SYSTEM ON A FPGA
Next message: [racket] OPERATING SYSTEM ON A FPGA
Messages sorted by: [date] [thread] [subject] [author]