jds@duke.cs.duke.edu (Joseph D. Sloan) (06/25/87)
It's common practice in comparative programming languages courses to assign the same problem in several different languages to compare and contrast different features of those languages. For example, consider the effort involved in coding a solution to "Who owns the zebra?" in C and in Prolog. Ideally the problems should be simple and to the point so that a number of problems/languages can be assigned. In this sense the zebra problem is probably too hard. Would folks that have such problems or collections of such problems be willing to share? Please describe 1) the problem, 2) proposed languages, and 3) what langage features are being contrasted. I will be happy to summarize mail to the net but I suspect this is of general interest so replying directly to the net is appropriate. Please folks, lots of problems! Many thanks, jds@duke
hwe@beta.UUCP (Skip Egdorf) (06/26/87)
In article <9819@duke.cs.duke.edu>, jds@duke.cs.duke.edu (Joseph D. Sloan) writes: > It's common practice in comparative programming languages > courses to assign the same problem in several different languages to > compare and contrast different features of those languages. > ... > > Would folks that have such problems or collections of such > problems be willing to share? Please describe 1) the problem, > 2) proposed languages, and 3) what langage features are being contrasted. > I will be happy to summarize mail to the net but I suspect this is > of general interest so replying directly to the net is appropriate. > Please folks, lots of problems! > > Many thanks, > jds@duke This might provoke some interesting discussion! At the point where students have had enough programming to understand the difference between engineering a solution to a problem and artfully composing a program for the fun of it, I would recomend the problem of the self reproducing program. For those who have not run into it, this problem is to write a program that, when run, prints its original text on its output. No fair opening the source file and copying it, the program must be totally self contained. The program is usually done by having a character string that is data, and is also a part of the program, and then cleverly printing the string two or three times, sometimes as data. e.g. in C something like char s = "char s %s ... main(){printf(s, s, ...)"; main(){printf(s, s, ...)} works. extra credit for the shortest, clearest, most obfuscated, etc. The problem is most easily done in C and Lisp (ok, my opinion.) and is doable in most others. Definitly try it in FORTRAN and PL/I. FORMATS work. BASIC and PASCAL will be difficult due to lack of compile-time initializations. This problem should not be used at the impressionable place where the students think that this is really the way to write programs. Leave it until they know both the engineering of and the art of programming. This problem is really a joy to play with in the ART side of the house. This problem seems to impress the young mind with a strong impression of which languages are true power tools for solving problems, and which are "more in the problem set than the solution set." I am not sure just which language features produce this feeling, but it is a very good problem for letting the students discover the fact that some languages try to get in your way more than others. Save the problem until they understand WHY you sometimes want the language to get in your way. Skip Egdorf hwe@lanl.gov
steve@hubcap.UUCP (Dennis Stevenson) (06/26/87)
The problem of writing a program which writes a copy of itself is a fundamental concept in computability. For your theory classes, let them try for each language. You'll separate the wheat from the chaff really quickly. Steve
costanzo@rochester.arpa (John N. Costanzo) (06/26/87)
In article <6835@beta.UUCP> hwe@beta.UUCP (Skip Egdorf) writes: >In article <9819@duke.cs.duke.edu>, jds@duke.cs.duke.edu (Joseph D. Sloan) writes: >> It's common practice in comparative programming languages >> courses to assign the same problem in several different languages to >> compare and contrast different features of those languages. ... >> >> Would folks that have such problems or collections of such >> problems be willing to share? Please describe 1) the problem, >> 2) proposed languages, and 3) what langage features are being contrasted. >> Many thanks, >> jds@duke >This might provoke some interesting discussion! >...I would recomend the problem of the self reproducing program. >This problem is really a joy to play with in the ART side of the house. >This problem seems to impress the young mind with a strong impression >of which languages are true power tools for solving problems, and which >are "more in the problem set than the solution set." I'm not entirely sure what this problem shows. As a spare time, have-some-fun, rec.puzzles kind of mind-bending brain teaser, it's great. But it's really all about some coincidental happenstance concerning the essentially arbitrary syntax of a language. (OK, before I get flame broiled by the language designers out there: the syntax of a language is certainly not arbitrary. But this problem does not address any of the fundamental aspects of a language's syntax.) I guess I just don't see how this speaks of what the language buys you and how you might do things with it later on (except in Obfuscated C Contests 8-). >...it is a very good problem for letting the students discover the fact >that some languages try to get in your way more than others. I don't think it does show much about the power or ease of use of the language. I think more appropriate problems might involve aspects that play on the strong suit of a particular language. (So called "rigged contests".) Things like implementing record structures and dynamic memory in Fortran and then in Pascal (or C). This will demonstrate how useful a language's data structuring facilities are. How about giving a simple assignment (like implementing stacks operations with arrays) in, say, Modula-2 and then giving a followup assignment to change the implementation to use linked lists? The second assignment, if done right, ought to be absolutely trivial -- a matter of changing 3 or 4 functions and a type definition. This ought to point out how a language might encourage the benefits of modularity. Or if we want to talk about how the syntax of a language influences it's "power", how about something that calls for a program to build code on the fly, like the managing of rules for a mini expert system? LISP's uniformity of code and data as well as PROLOG's code<-->structure mapping functions would be clear wins here while it would take some more thought in other languages. I think a good example of a kind of problem *NOT* to assign is the standard classic of: ``OK we're going to learn LISP today; LISP uses recursion, here is how you write a factorial program (or Towers of Hanoi or quicksort)'' As an introductory lesson to recursion this might not be bad, but the job of teaching recursion is only half done when it teaches HOW. It should also mention WHEN to use recursion (and when not to). An important point to get across to students is that just because something *can* be done recursively, doesn't necessarily mean ought to be. Especially if the non-recursive version is as easy to write and as clear to read, and more efficient. (The above argument based on current commonly available compiler technology. Your mileage may vary.) These, I think, highlight some interesting properties of languages. But I'm sure others have better examples. > Skip Egdorf > hwe@lanl.gov =John Costanzo __________ ARPA: costanzo@cs.rochester.edu UUCP: ..!{allegra,decvax,seismo}!rochester!costanzo USnail: CS Dept., University of Rochester, Rochester NY 14627 Phone: (716)275-7747 Spoken: Hey You! -- ARPA: costanzo@cs.rochester.edu UUCP: ..!{allegra,decvax,seismo}!rochester!costanzo USnail: CS Dept., University of Rochester, Rochester NY 14627 Phone: (716)275-7747 Spoken: Hey You!
prins@speedy.WISC.EDU (Jan Prins) (06/28/87)
In article <6835@beta.UUCP> hwe@beta.UUCP (Skip Egdorf) writes: >For those who have not run into it, this problem is to write a program >that, when run, prints its original text on its output. > [...] >The problem is most easily done in C and Lisp (ok, my opinion.) and is doable >in most others. The APL expression 1 returns itself as a result. In APL it is the shortest self-replicating expression and also the narrowest! I agree with the observation that the value of this exercise to the comparative study of programming languages is mostly limited to their syntax. Jan
pmontgom@sdcrdcf.UUCP (Peter Montgomery) (06/29/87)
In article <9819@duke.cs.duke.edu> jds@duke.cs.duke.edu (Joseph D. Sloan) writes: > > It's common practice in comparative programming languages >courses to assign the same problem in several different languages to >compare and contrast different features of those languages. > ... >Please folks, lots of problems! > The operation I miss most in higher-level languages is: Given three integers a, b, n where 0 <= a, b < n, find integers q, r such that a*b = q*n + r and 0 <= r < n. We allow n to be very large; in particular the product a*b need not fit in a positive integer. Note q will also satisfy 0 <= q < n. This is a critical operation (typically with n being a power of 2) when writing multiple-precision arithmetic routines. If the hardware supports double-length multiplication and division instructions (e.g., EMUL and EDIV on a VAX), then this is trivial in assembly. We may also be able to use floating point arithmetic: if we assume that numbers below n*n can be represented exactly in floating point, then we can compute the double precision floating point product for a*b and work from there. Use of floating point would illustrate how type conversions are done in each language, esp. if the students are told to avoid unnecessary temporary variables. For example, the FORTRAN code could be integer a, b, n, q, r intrinsic DBLE, DMULT, INT, MOD, REAL q = INT( DMULT(REAL(a), REAL(b)) /DBLE(n)) r = INT(MOD(DMULT(REAL(a), REAL(b)), DBLE(n))) (intrinsic statement optional - I consider it good programming practice). But PASCAL lacks explicit conversion from integer to floating point, and C lacks a floating point remainder function. The students should also be required to do a solution using all-integer arithmetic. If the language already supports multiple-precision arithmetic, then it will be easy. Otherwise the pseudocode might resemble: aa <- a bb <- b q <- 0 r <- 0 WHILE bb <> 0 DO /* a*b = aa*bb + q*n + r */ /* 0 <= aa, bb, r < n */ IF bb is odd THEN bb <- bb - 1 IF r < n - aa THEN r <- r + aa ELSE r <- r - (n-aa) q <- q + 1 END IF END IF /* a*b = aa*bb + q*n + r */ /* 0 <= aa, bb, r < n */ /* bb is even */ bb <- bb/2 IF aa < n - aa THEN aa <- aa + aa ELSE aa <- aa - (n-aa) q <- q + bb END IF END WHILE This (untested) code takes time O(log(b)) <= O(log(n)). All intermediate results are between 0 and n. BTW, those of us who do extensive multiple-precision integer arithmetic must either make frequent calls to assembly-language subprograms (and it can be very expensive to make 100 procedure calls when multiplying two numbers each occupying ten machine words) or must write much larger subprograms in assembly language (making our programs much less portable). Future higher-level languages should include this as a primitive construct. -- Peter Montgomery {aero,allegra,bmcg,burdvax,hplabs,ihnp4, psivax,randvax,sdcsvax,trwrb}!sdcrdcf!pmontgom Don't blame me for the crowded freeways - I don't drive.
waldau@kuling.UUCP (Mattias Waldau) (07/04/87)
Newsgroups: comp.lang.misc Subject: Re: Problems needed! Summary: Expires: References: <9819@duke.cs.duke.edu> Sender: Reply-To: waldau@kuling.UUCP (Mattias Waldau) Followup-To: Distribution: Organization: Dept. of Computing Science, Uppsala University, Sweden Keywords: A problem that I have studied is representing a structure (PROLOG-term) or a complex list (LISP-term) as a tree. For example a(b(c),d(e,f)) as a | ---- | | b d | | | --- | | | c e f and a(b(c),david(e,f)) as a | ----- | | b david | | | --- | | | c e f In the first example determines c and e the structure of the tree, and in the second b and david. I am only interested in the absolut positions of the nodes and bars, not how the arcs are represented on the screen. The problem can be complicated by also restricting the width of the tree. I have made some programs in PROLOG and at last got a rather efficient and declarative solution, and if I took that solution and implemented it in LISP, I would get a lot of parameters and a program I wouldn't understand in 2 months time. I am very interested in other peoples solutions of this problem, so please mail them to me.