Rewriting something in Scheme
chr.m....@gmail.com
I'm currently trying to learn Scheme (so please be kind) and while
doing so, i had the idea of rewriting a (very) small game i've written
some months ago in C, in Scheme. My first attemt was to try it rather
functionally, but i failed to get the logic and the levels of
abstraction the way i wanted it, the 2nd attemt has become a (working,
but) ugly, imerative kludge. For and while loops became named lets,
but the rest is all set!s of global variables. (I suppose) This is not
what scheme code should look like.
Now i need your help to rethink my approach. The imperative approach
is just copying the C code structure 1:1, telling the code what to do.
Can imerative code be refactored into functional code, or will i have
to start from scratch and if so, should i plan it top down or write it
bottom up (for i already know exactly how the game should behave, the
design is fixed). I seem to fail at very trivial levels: for example,
i have one if clause altering 2 (or more) values. If i rewrite it
functionally, will i have 2 functions for these 2 values, both
containing the same if-clause (or both calling the same function that
contains the if-clause)? And, do i need to pass the whole gamestate on
every recursion of the main game loop or is it advisable to keep some
values global (or local to their mutable state functions)? (This game
is tiny, so it won't matter much)
Please share your thoughts and learning experiences with me,
.c
Benjamin L. Russell
I once helped write a Scheme version of Tetris, called "Schemetris,"
as part of a final project for a course, "Introduction to Computer
Science," which I had audited in college, so perhaps I can comment a
little.
There is very little overlap between imperative and functional
approaches, at least until graduate-level computer science (or so I
have heard), so ordinarily, you would need to choose between either of
the following alternatives:
1) investing very little time and coming up with a pseudo-imperative
Scheme program
2) investing a great amount of time and possibly coming up with an
elegantly functional Scheme program
A third, possibly alternative approach is to use a multi-paradigm
language, such as Mozart/Oz (see http://www.mozart-oz.org/), as an
intermediate step. This type of language allows expression of similar
behavior using a variety of different paradigms, including functional,
object-oriented, and logic (see
http://www.mozart-oz.org/features.html, under "Programming ->
Multi-Paradigm Programming").
You could write your program imperatively at first, then successively
refine parts of the program into a functional program as you find
time. Then, when you find a lot of time, you could try restarting
from scratch, and recasting your entire algorithm functionally.
Once your entire algorithm is expressed functionally, translating it
back into Scheme should be relatively straightforward, provided that
you don't depend on language-specific libraries.
-- Benjamin L. Russell
Benjamin L. Russell
<DekuDe...@Yahoo.com> wrote:
>[...]
>
>A third, possibly alternative approach is to use a multi-paradigm
>language, such as Mozart/Oz (see http://www.mozart-oz.org/), as an
>intermediate step. This type of language allows expression of similar
>behavior using a variety of different paradigms, including functional,
>object-oriented, and logic (see
>http://www.mozart-oz.org/features.html, under "Programming ->
>Multi-Paradigm Programming").
>
>[...]
I forgot to mention that the on-line documentation for Mozart/Oz has
been rumored by some to be relatively difficult to follow, so here are
references for alternative documentation:
Strasheela Tutorial
http://strasheela.sourceforge.net/strasheela/doc/StrasheelaTutorial.html
Although Strasheela itself is a constraint-based music composition
system, its user interface is Oz, and the Strasheela Tutorial contains
an Oz sub-tutorial that has been described as being easier to follow
than the main Oz tutorial at the Mozart/Oz Web site.
Another possible reference is the following:
Concepts, Techniques, and Models of Computer Programming
http://www.info.ucl.ac.be/~pvr/book.html
This is a paper book that has been referred to as being of somewhat
similar level and content as that of SICP (see
http://mitpress.mit.edu/sicp/). If you search hard enough on the net,
you may be able to find an online PDF draft of an earlier version of
CTM (there are actually two versions: an old draft of August 21,
2001; and a relatively newer draft of June 5, 2003). If you cannot
find one, please send me a private e-mail message, and I may be able
to help you.
-- Benjamin L. Russell
tom.g...@me.com
>
> A third, possibly alternative approach is to use a multi-paradigm
> intermediate step. This type of language allows expression of similar
> behavior using a variety of different paradigms, including functional,
> Multi-Paradigm Programming").
>
I don't understand this suggestion. Nothing against Mozart/Oz, but
Scheme is just as much a multi-paradigm language. One might go so far
as to call it an "any-paradigm" language. It supports of all of the
paradigms you mentioned (imperative, functional, object-oriented,
logic programming). And if these aren't enough, in Scheme you can
invent your own custom language.
So what's the point in using Mozart/Oz as an intermediate step if your
ultimate goal is to write the application in Scheme?
-Tom Gordon
Veer
will only lead to
more frustration. Best way to learn to program in scheme is to read
the books like HtDP and
SICP , both are available online. Both books introduce assignment/
mutation very late , and
you will find that you can solve complex problems without the
mutation.
Jens Axel Soegaard
> I'm currently trying to learn Scheme (so please be kind) and while
> doing so, i had the idea of rewriting a (very) small game i've written
> some months ago in C, in Scheme. My first attemt was to try it rather
> functionally, but i failed to get the logic and the levels of
> abstraction the way i wanted it, the 2nd attemt has become a (working,
> but) ugly, imerative kludge. For and while loops became named lets,
> but the rest is all set!s of global variables. (I suppose) This is not
> what scheme code should look like.
>
> Now i need your help to rethink my approach.
...
> And, do i need to pass the whole gamestate on
> every recursion of the main game loop or is it advisable to keep some
> values global (or local to their mutable state functions)? (This game
> is tiny, so it won't matter much)
>
> Please share your thoughts and learning experiences with me,
I'd recommend you try the world.ss PLT Scheme Teachpack in order to
see how a functional approach looks like. If nothing else just
to get a few ideas.
See "Interactive Games" on this page.
http://www.ccs.neu.edu/home/matthias/HtDP/Extended/index.html
Note: The note on interactive games were written for version 207.
Ask the PLT Mailing list whether, there is a newer
version available.
--
Jens Axel Søgaard
Jens Axel Soegaard
> Note: The note on interactive games were written for version 207.
> Ask the PLT Mailing list whether, there is a newer
> version available.
>
Found it! Here is a little book: "How to Design Worlds: Imaginative
programming in DrScheme" that is a perfect place to get a feel
for the functional approach.
The corresponding reference material is at:
http://docs.plt-scheme.org/teachpack/world.html
--
Jens Axel Søgaard
Benjamin L. Russell
>
>>
>> A third, possibly alternative approach is to use a multi-paradigm
>> language, such as Mozart/Oz (seehttp://www.mozart-oz.org/), as an
>> intermediate step. ?This type of language allows expression of similar
>> behavior using a variety of different paradigms, including functional,
>> object-oriented, and logic (seehttp://www.mozart-oz.org/features.html, under "Programming ->
>> Multi-Paradigm Programming").
>>
>
>I don't understand this suggestion. Nothing against Mozart/Oz, but
>Scheme is just as much a multi-paradigm language. One might go so far
>as to call it an "any-paradigm" language. It supports of all of the
>paradigms you mentioned (imperative, functional, object-oriented,
>logic programming). And if these aren't enough, in Scheme you can
>invent your own custom language.
>
>So what's the point in using Mozart/Oz as an intermediate step if your
>ultimate goal is to write the application in Scheme?
One possible advantage is that the textbook _Concepts, Techniques, and
Models of Computer Programming_
(http://www.info.ucl.ac.be/~pvr/book.html) was specifically written to
use Mozart/Oz to discuss multiparadigm programming, and could be
useful as a reference for this project. While Scheme does indeed
support multiparadigm programming, most actual programming in Scheme
is not done imperatively. In contrast, Mozart/Oz was designed
expressly for the purpose of supporting multi-paradigm programming.
-- Benjamin L. Russell
Benjamin L. Russell
<DekuDe...@Yahoo.com> wrote:
>[...]
>
>One possible advantage is that the textbook _Concepts, Techniques, and
>Models of Computer Programming_
>(http://www.info.ucl.ac.be/~pvr/book.html) was specifically written to
>use Mozart/Oz to discuss multiparadigm programming, and could be
>useful as a reference for this project. While Scheme does indeed
>support multiparadigm programming, most actual programming in Scheme
>is not done imperatively. In contrast, Mozart/Oz was designed
>expressly for the purpose of supporting multi-paradigm programming.
Incidentally, I just found a small Scheme program that translates
Scheme code into Oz syntax for Schemers:
Topics:CTM in other languages - CTMWiki (see under "Scheme syntax for
Oz")
http://codepoetics.com/wiki/index.php?title=Topics:CTM_in_other_languages
I also searched for a Scheme version of CTM itself, but unfortunately,
was not able to find one (although I did find a version for Alice at
http://www.codepoetics.com/wiki/index.php?title=Topics:CTM_in_other_languages:Alice_ML).
I myself use Scheme more than most other programming languages (my
other favorite being Haskell). If you know of a book or research
paper that specifically discusses translating from the imperative
paradigm to the functional paradigm in Scheme, I would be very
interested also.
-- Benjamin L. Russell
Benjamin L. Russell
<DekuDe...@Yahoo.com> wrote:
Incidentally, I just found a rather interesting page that contains
translations of Scheme code from _The Little Schemer_ (see
http://www.ccs.neu.edu/home/matthias/BTLS/), _The Seasoned Schemer_
(see http://www.ccs.neu.edu/home/matthias/BTSS/), and _The Reasoned
Schemer_ (see http://www.ccs.neu.edu/home/matthias/BRS/) into Oz:
Topics:TRS in other languages:Oz - CTMWiki
http://www.codepoetics.com/wiki/index.php?title=Topics:TRS_in_other_languages:Oz
There is also a corresponding list of SICP examples as well:
Topics:SICP in other languages - CTMWiki
http://www.codepoetics.com/wiki/index.php?title=Topics:SICP_in_other_languages
I would be interested in a corresponding list of translations from CTM
into Scheme as well. Alternatively, if you know lists of translations
of equivalent code from other textbooks in other languages into
Scheme, I would be interested in those lists as well.
-- Benjamin L. Russell
tom.g...@me.com
>
> One possible advantage is that the textbook _Concepts, Techniques, and
> Models of Computer Programming_
> (http://www.info.ucl.ac.be/~pvr/book.html) was specifically written to
> use Mozart/Oz to discuss multiparadigm programming, and could be
> useful as a reference for this project.
But the bible on multiparadigm programming has surely got to be
Abelson and Sussmans "Structure and Interpretation of Computer
Programs", which uses Scheme.
> While Scheme does indeed
> support multiparadigm programming, most actual programming in Scheme
> is not done imperatively. In contrast, Mozart/Oz was designed
> expressly for the purpose of supporting multi-paradigm programming.
>
What evidence do you have for this claim? The Scheme programs I'm
familiar with make use of, well, multiple paradigms.
I, for one, prefer the functional paradigm and have written a fairly
large Scheme application, Carneades <http://carneades.berlios.de>
almost entirely in the functional style.
So there is at least one counterexample.
-Tom
Benjamin L. Russell
>[...]
>
>But the bible on multiparadigm programming has surely got to be
>Abelson and Sussmans "Structure and Interpretation of Computer
>Programs", which uses Scheme.
On multiparadigm programming, really? I just visited the SICP Web
site (see http://mitpress.mit.edu/sicp/), and searched both the index
(see
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-38.html#%_index_start)
and the table of contents (see
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_start)
of SICP for the word "paradigm." There were 0 matches in the index,
and only 1 match in the table of contents, in reference specifically
to "the Stream Paradigm" only (see
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.3).
SICP is certainly the classic text for an introduction to computer
science. In fact, parts of it were used in my course, Introduction to
Computer Science, at college, and, IIRC, I currently own two copies of
the book (one from MIT Press, and the other from McGraw-Hill
Publishing). It is one of my favorite books on computer science, and
provides interesting motivation in referring to computer science as a
"procedural epistemology" in the Preface to the First Edition (see
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-7.html#%_chap_Temp_4),
and in drawing a simile between a computational process and a
sorcerer's idea of a spirit in Chapter 1 (see
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-9.html#%_chap_1).
Nevertheless, at least as far as I know, it does not really focus on
comparing different paradigms specifically. Rather, it focuses on
such topics as computational processes, abstractions, recursion,
symbolic data, modularity, objects, state, concurrency, streams,
metalinguistic abstraction, nondeterminism, some logic programming,
register machines, storage allocation, garbage collection, and
compilation. These mostly appear to be meta-paradigm (to use my own
term) issues, rather than issues specific to any particular paradigm.
>
>> While Scheme does indeed
>> support multiparadigm programming, most actual programming in Scheme
>> is not done imperatively. ?In contrast, Mozart/Oz was designed
>> expressly for the purpose of supporting multi-paradigm programming.
>>
>
>What evidence do you have for this claim? The Scheme programs I'm
>familiar with make use of, well, multiple paradigms.
Most textbooks on Scheme focus on the functional paradigm:
SICP
http://mitpress.mit.edu/sicp/
PLAI
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/
Concrete Abstractions
http://gustavus.edu/+max/concrete-abstractions-pdfs/ConcreteAbstractions.pdf
The Scheme Programming Language, Third Edition
http://www.scheme.com/tspl3/
In addition, most discussion threads on Scheme programs that I have
read on such Scheme mailing lists as, say, the plt-scheme mailing list
(see http://list.cs.brown.edu/pipermail/plt-scheme/) concern
functional-style programming.
When I was first exposed to Scheme at college with SICP, it was taught
in a functional style. As a result, I myself tend to prefer the
functional paradigm. In fact, I liked it so much that I even took a
course in formal semantics of programming languages, which became one
of my favorite computer science courses. It discussed the lambda
calculus, which forms a basis for Scheme.
However, the functional paradigm shares little with the imperative
paradigm. In fact, according to the Forward of SICP (see
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-5.html#%_chap_Temp_2),
there are key differences between the main data structures of Pascal,
an imperative programming language, and those of Scheme (here referred
to as "Lisp," but the actual language used in SICP is Scheme):
>It would be difficult to find two languages that are the communicating
>coin of two more different cultures than those gathered around these
>two languages. Pascal is for building pyramids -- imposing,
>breathtaking, static structures built by armies pushing heavy blocks
>into place. Lisp is for building organisms -- imposing, breathtaking,
>dynamic structures built by squads fitting fluctuating myriads of
>simpler organisms into place. The organizing principles used are the
>same in both cases, except for one extraordinarily important
>difference: The discretionary exportable functionality entrusted to
>the individual Lisp programmer is more than an order of magnitude
>greater than that to be found within Pascal enterprises. Lisp
>programs inflate libraries with functions whose utility transcends
>the application that produced them. The list, Lisp's native data
>structure, is largely responsible for such growth of utility. The
>simple structure and natural applicability of lists are reflected in
>functions that are amazingly nonidiosyncratic. In Pascal the plethora
>of declarable data structures induces a specialization within
>functions that inhibits and penalizes casual cooperation. It is
>better to have 100 functions operate on one data structure than to
>have 10 functions operate on 10 data structures. As a result the
>pyramid must stand unchanged for a millennium; the organism must
>evolve or perish.
Therefore, it would not seem to be easy to translate between the data
structures of Pascal, another imperative language, and those of
Scheme. By extension, it would not seem to be easy to translate
between data structures in most similar imperative languages and those
of Scheme, either.
>I, for one, prefer the functional paradigm and have written a fairly
>large Scheme application, Carneades <http://carneades.berlios.de>
>almost entirely in the functional style.
It looks like a wonderful application. I would be very interested in
trying it out.
I myself prefer the functional paradigm, too; that is the reason that
my favorite languages are Scheme and Haskell (another functional
programming language).
However, the issue here is conversion from code written in an
imperative style, in an imperative language, to Scheme. That was the
reason for a specifically multi-paradigm suggestion, which I thought
may facilitate conversion between the imperative and the functional
paradigms.
-- Benjamin L. Russell
tom.g...@me.com
wrote:
> On Fri, 24 Oct 2008 04:29:40 -0700 (PDT), tom.gor...@me.com wrote:
> >[...]
>
> >But the bible on multiparadigm programming has surely got to be
> >Abelson and Sussmans "Structure and Interpretation of Computer
> >Programs", which uses Scheme.
>
> On multiparadigm programming, really?
SICP shows how to *implement* various programming paradigms in Scheme,
including low-level assembly languages (Chapter 5, "computing with
register machines"), imperative programming (Chapter 3.3 "modeling
with mutable data"), object-oriented programming (Chapter 2.3.3 "Data-
Directed Programming" and Chapter 3.2.3, "Frames as the Repository of
Local State"), Programming with streams of data using filters and
pipes (Chapter 3.4 "Streams"), and logic programming (Chapter 4.4)
Oddly, functional programming doesn't seem to get much emphasis in
SICP, although it surely contains many examples of this style.
That said, maybe you are right, if you mean that SICP isn't so much
about *using* multiple paradigms to write applications as it is about
explaining and illustrating these various paradigms and showing how
they can be implemented.
Nonetheless, SICP was enough to get me started using these paradigms
in my own Scheme programs.
-Tom
tom.g...@me.com
wrote:
> >> While Scheme does indeed
> >> support multiparadigm programming, most actual programming in Scheme
> >> is not done imperatively. ?In contrast, Mozart/Oz was designed
> >> expressly for the purpose of supporting multi-paradigm programming.
>
> >What evidence do you have for this claim? The Scheme programs I'm
> >familiar with make use of, well, multiple paradigms.
>
> Most textbooks on Scheme focus on the functional paradigm:
>
Sorry, but I misread your claim. I though you said that most actual
Scheme programming *is* done imperatively, not functionally. But I'm
still not sure I agree. You cite various Scheme textbooks to support
your claim, but SICP surely is a very important counterexample. It
contains many, many examples of stateful, imperative programs.
And let's not forget that Scheme as *explicitly* inspired as much by
Algol as it was by Lisp and functional programming. Its not an
accident that the RnRS Scheme reports are entitled "Revised^n Report
on the Algorithmic Language Scheme".
-Tom
Grant Rettke
> To come from C and writing a program in scheme by reading a manual
> will only lead to
> more frustration. Best way to learn to program in scheme is to read
> the books like HtDP and
> SICP , both are available online. Both books introduce assignment/
> mutation very late , and
> you will find that you can solve complex problems without the
> mutation.
If this is your first functional programming language, do yourself a
favor read HtDP first. It will save your forehead from too much
banging.
Grant Rettke
wrote:
> Most textbooks on Scheme focus on the functional paradigm:
The first 75% is functional, which sets the stage for the remaining
25% which involves state and objects. There is always "How To Design
Classes" (which I haven't read yet).
Benjamin L. Russell
<gre...@gmail.com> wrote:
True. Another choice, for those who prefer learning in the
alternative exploratory style sans the banged head (and crushed wall)
is the following textbook:
Concrete Abstractions: An Introduction to Computer Science Using
Scheme
http://gustavus.edu/+max/concrete-abstractions.html
You may also wish to read the following blog entry by jaortega:
"A Scheme bookshelf"
http://jaortega.wordpress.com/2007/01/31/a-scheme-bookshelf/
He gives a subjective view of HtDP vs. Concrete Abstractions, arguing
in favor of the latter. It seems that both HtDP and Concrete
Abstractions have their respective advantages. HtDP, in my opinion,
tends to favor the systematic, rather than the exploratory, approach,
and some people prefer this approach, whereas others prefer the
exploratory approach. One's preference seems to depend on personal
style. Concrete Abstractions follows the exploratory style of SICP,
but at a somewhat more relaxed pace.
Another personal recommendation is the following series:
The Little Schemer
http://www.ccs.neu.edu/home/matthias/BTLS/
The Seasoned Schemer
http://www.ccs.neu.edu/home/matthias/BTSS/
The Reasoned Schemer
http://www.ccs.neu.edu/home/matthias/BRS/
Unfortunately, unlike HtDP, this series does not seem available
anywhere online.
This series is very different from most books on Scheme, and takes the
form of a question-and-answer dialogue between a student and a
teacher. The books make for an Alice in Wonderland-style adventure,
and make very good mental exercise and entertainment, especially for
those who enjoy doing mind-twisting while thinking about food. I used
to take The Little Schemer around with me when I went to Kinkos to
study at 3:30 AM, and read it to relieve the boredom of studying
databases. Now I don't study databases anymore, and study functional
programming in my spare time.
-- Benjamin L. Russell
Benjamin L. Russell
<DekuDe...@Yahoo.com> wrote:
>On Fri, 24 Oct 2008 12:58:31 -0700 (PDT), Grant Rettke
><gre...@gmail.com> wrote:
>
>>On Oct 24, 3:54?am, Veer <diggerr...@gmail.com> wrote:
>>> To come from C and writing a program in scheme by reading a manual
>>> will only lead to
>>> more frustration. Best way to learn to program in scheme is to read
>>> the books like HtDP and
>>> SICP , both are available online. Both books introduce assignment/
>>> mutation very late , and
>>> you will find that you can solve complex problems without the
>>> mutation.
>>
>>If this is your first functional programming language, do yourself a
>>favor read HtDP first. It will save your forehead from too much
>>banging.
>
>[...]
Another book that I forgot to recommend is the following:
Programming Languages: Application and Interpretation
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/
In particular, this book did a very good job of explaining the value
of continuations using stateful and stateless protocols vis-a`-vis
making multiple purchases from a single Web site. The style is rather
informal, but the explanations provide good motivation and reasoning
for the material covered.
-- Benjamin L. Russell
Grant Rettke
wrote:
> On Fri, 24 Oct 2008 12:58:31 -0700 (PDT), Grant Rettke
> >favor read HtDP first. It will save your forehead from too much
> >banging.
>
> True. Another choice, for those who prefer learning in the
> alternative exploratory style sans the banged head (and crushed wall)
> is the following textbook:
Ben listed a lot of good books (from what I've heard, not having read
them all myself) about Scheme and Programming and Functional
Programming.
HtDP is the only book that I've been able to find that is both
systematic and focuses on Functional Programming. I expect that by the
time I am finished, I will have a "standard approach" for FP that I
can then tailor to my own personal preferences. I wan to have a good
sense of "one way" for how FP works, and then pursue the exploratory
style of programming when it comes to Scheme and FP.
This is the approach that I am taking decidedly; starting with HtDP
before getting into PLAI or SICP.