From icon-group-sender Wed Dec 7 22:16:49 1994 Received: by cheltenham.cs.arizona.edu; Wed, 7 Dec 1994 17:07:13 MST To: icon-group-l@cs.arizona.edu Date: Wed, 7 Dec 1994 22:16:49 GMT From: vorbeck@cs.sfu.ca (Martin Vorbeck) Message-Id: <1994Dec7.221649.10939@cs.sfu.ca> Organization: Faculty of Applied Science, Simon Fraser University Sender: icon-group-request@cs.arizona.edu Subject: [Q] Algorithm for Regexp Subsumption Errors-To: icon-group-errors@cs.arizona.edu Hi, are there any algorithms out there for checking whether a regular expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a "brute-force" solution along these lines: 1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2). 2. Compute A3 = A1 intersected with the complement of A2. 3. Test L(A3) = empty ==> E2 subsumes E1. But I wonder if this couldn't be done directly on the regular expressions E1 and E2? As an aside note, just a reminder that regexp inequivalence is NP-Hard (Garey & Johnson), so I don't expect anything extremely efficient. Any help would be very much appreciated. Please Email any replies to vorbeck@cs.sfu.ca as I don't usually read these newsgroups. Thanks ! -- Martin Vorbeck From icon-group-request Wed Dec 7 21:35:25 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 7 Dec 1994 20:14:26 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA08246; Wed, 7 Dec 1994 20:14:24 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id TAA23465; Wed, 7 Dec 1994 19:06:56 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: Wed, 7 Dec 1994 21:35:25 GMT From: "Brian D. Wilson" Message-Id: <1994Dec7.213525.20288@llyene.jpl.nasa.gov> Organization: JPL Sender: icon-group-request@cs.arizona.edu Subject: Where does one get ProIcon for the Mac? Newbie to Icon has two questions: Where does one get the (newly free) ProIcon for the Mac? Is there a source repository somewhere? ------------------------------------------------------------------------- Brian D. Wilson | I used to drive a Heisenberg Uncertainty car, Jet Propulsion Laboratory | but I could never read the speedometer bdw@logos.jpl.nasa.gov | without getting lost. -- Not mine ------------------------------------------------------------------------- From icon-group-request Tue Dec 6 22:35:14 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 7 Dec 1994 21:59:47 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA13370; Wed, 7 Dec 1994 21:59:45 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id UAA25601; Wed, 7 Dec 1994 20:47:25 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: 6 Dec 1994 22:35:14 GMT From: jeffery@ringer.cs.utsa.edu (Clinton L. Jeffery) Message-Id: <3c2ov2$pms@ringer.cs.utsa.edu> Organization: University of Texas at San Antonio Sender: icon-group-request@cs.arizona.edu References: Subject: Re: Status of Icon on the Mac? Tim Gilbert (gilbert@marin.cc.ca.us) wrote: : Hi. Does anyone know what the status of icon on the Mac is? I wonder if : version 9.x will ever be ported. I don't care so much about the graphics : stuff as about the preproccessor... We are doing an Icon 9.0 on the Mac here at UT San Antonio, and while our main emphasis is on adding the graphics features, we will certainly also be providing all the other Icon 9.0 improvements such as the preprocessor. Our implementation is presently in alpha testing. We don't have the resources to orchestrate a separate non-graphics release, sorry. : On a related note, will the source code to ProIcon be publicly released : ant time in the forseeable future? I'd be willing to make a stab at : hacking up version 9... ProIcon uses various proprietary code that can never be released. Some of the features in it are non-proprietary and might make it into other Mac versions of Icon at some point. -- Clint Jeffery cjeffery@cs.arizona.edu, jeffery@ringer.cs.utsa.edu The University of Texas at San Antonio From cliff Wed Dec 7 22:38:56 1994 Date: Wed, 7 Dec 1994 22:38:56 MST From: "Cliff Hathaway" Message-Id: <199412080538.AA16734@cheltenham.cs.arizona.edu> Received: by cheltenham.cs.arizona.edu; Wed, 7 Dec 1994 22:38:56 MST To: icon-group Subject: Re: Where does one get ProIcon for the Mac? ProIcon can be ftp'd from ftp.cs.arizona:/icon/packages/macintosh/mep*. Also available on diskettes for a nominal charge ($15, which includes shipping to addresses in the US, Canada and Mexico. $5 more covers postage anywhere else on the planet). If you'd like to receive the Icon Newsletter, published 3 times a year at no cost to its subscribers, send us your postal mailing address. The source code for ProIcon contains proprietary material, so we don't expect that it will be released. Source code for Icon itself is in the public domain, and is also available via ftp, or on magnetic media. The Icon Program Library is a compendium of useful and interesting programs and procedures written in Icon, also available via ftp or on magnetic media. Cliff Hathaway, Icon Project Dept. of Computer Science (602)621-4291 University of Arizona cliff@cs.arizona.edu (internet) Tucson, Ariz. 85721 {cmcl2,noao,uunet}!arizona!cliff (uucp) From icon-group-sender Wed Dec 7 21:38:35 1994 Received: by cheltenham.cs.arizona.edu; Wed, 7 Dec 1994 23:00:02 MST To: icon-group-l@cs.arizona.edu Date: 7 Dec 1994 21:38:35 -0700 From: dave@cs.arizona.edu (Dave Schaumann) Message-Id: <3c62kb$pnu@caslon.CS.Arizona.EDU> Organization: University of Arizona CS Department, Tucson AZ Sender: icon-group-request@cs.arizona.edu References: <1994Dec7.221649.10939@cs.sfu.ca> Subject: Re: [Q] Algorithm for Regexp Subsumption Errors-To: icon-group-errors@cs.arizona.edu In article <1994Dec7.221649.10939@cs.sfu.ca>, Martin Vorbeck wrote: } are there any algorithms out there for checking whether a regular }expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a }"brute-force" solution along these lines: } }1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2). }2. Compute A3 = A1 intersected with the complement of A2. }3. Test L(A3) = empty ==> E2 subsumes E1. } }But I wonder if this couldn't be done directly on the regular }expressions E1 and E2? Another possibility would be to compute the minimized DFAs, then compute the minimized DFA of the union. If it's the same as either of the originals, you've got a match. Hard to say which method would be quicker. Since they're essentially duals of each other, I wouldn't be surprised if it was a wash. -Dave From icon-group-sender Thu Dec 8 10:11:20 1994 Received: by cheltenham.cs.arizona.edu; Thu, 8 Dec 1994 11:14:08 MST Date: Thu, 8 Dec 94 10:11:20 PST From: cynthia@usenix.org (Cynthia Deno) Message-Id: <9412081811.AA21627@usenix.ORG> To: icon-group@cs.arizona.edu Subject: USENIX Association 1995 Technical Conference Errors-To: icon-group-errors@cs.arizona.edu 1995 USENIX ASSOCIATION TECHNICAL CONFERENCE January 16-20, 1995, New Orleans, Lousianna *************************************************** The latest technical developments in UNIX and advanced computing systems. . . Choose from among 20 Tutorials, attend Invited Talks, and learn details of never-before-published researchin the refereed papers sessions. Don't miss Mark Weiser's keynote talk on Ubiquitous Computing. Meet your peers and discuss common problems. Discuss with industry experts in a relaxed environment. And, get a hands-on look at the latest products in the Vendor Display. A partial list of topics includes: UNIX Security, Firewalls, System Administration, UNIX Programming, COM OLE, BSD, Mass Store, Streams, SIFT, Tcl/Tk, World Wide Web, Libraries, File Systems, Sendmail 8, Internet Cash and Commerce, and more. Program Chair: Peter Honeyman, CITI, University of Michigan TO OBTAIN FULL PROGRAM AND REGISTRATION INFORMATION: ==================================================== Telephone: 714 588 8649; Fax: 714 588 9706 Email: conference@usenix.org Automatic mailserver: Email to: info@usenix.org. Your message should contain the line "send conferences catalog". Conference information will be returned to you. World Wide Web: The USENIX URL is: http://www.usenix.org From icon-group-sender Thu Dec 8 20:58:20 1994 Received: by cheltenham.cs.arizona.edu; Thu, 8 Dec 1994 14:01:17 MST To: icon-group-l@cs.arizona.edu Date: 8 Dec 1994 20:58:20 +0100 From: antimiro@loria.fr (Valentin Antimirov) Message-Id: <3c7ogs$i9t@myrtille.loria.fr> Organization: CRIN & INRIA-Lorraine - Nancy - FRANCE Sender: icon-group-request@cs.arizona.edu References: <1994Dec7.221649.10939@cs.sfu.ca>, <3c62kb$pnu@caslon.CS.Arizona.EDU> Subject: Re: [Q] Algorithm for Regexp Subsumption Errors-To: icon-group-errors@cs.arizona.edu In article <3c62kb$pnu@caslon.CS.Arizona.EDU>, dave@CS.Arizona.EDU (Dave Schaumann) writes: |> |> In article <1994Dec7.221649.10939@cs.sfu.ca>, |> Martin Vorbeck wrote: |> |> } are there any algorithms out there for checking whether a regular |> }expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a |> }"brute-force" solution along these lines: |> } |> }1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2). |> }2. Compute A3 = A1 intersected with the complement of A2. |> }3. Test L(A3) = empty ==> E2 subsumes E1. |> } |> }But I wonder if this couldn't be done directly on the regular |> }expressions E1 and E2? |> |> Another possibility would be to compute the minimized DFAs, then |> compute the minimized DFA of the union. If it's the same as either |> of the originals, you've got a match. |> |> Hard to say which method would be quicker. Since they're essentially |> duals of each other, I wouldn't be surprised if it was a wash. |> |> -Dave Yes, it is possible to prove any regular inequality E1 =< E2 (as well as any regular equation E1 = E2) in a pure algebraic way -- without constructing DFA's for the expressions involved. 1. As far as regular equations are concerned, such a way has been described in [1]. It is an algebraic calculus presented in the form of a term-rewriting system. I have written a program in OBJ3 (an algebraic programming language) implementing this calculus. If someone is interested in getting the program (together with quite complete instructions how to run it, examples, etc.), send me please a request by e-mail. 2. Since E1 =< E2 is equivalent to E1 + E2 = E2, the abovementioned calculus can also be used for proving/disproving regular inequalities. However, there exists a more direct (and more efficient) algebraic procedure based on so-called "partial derivatives". Below I outline it. Consider the set Reg of regular expressions on a given alphabet A: Reg ::= 0 | 1 | x | Reg . Reg | Reg + Reg | Reg * where 0 denotes the empty language, 1 is a unit language, x is a letter from A, and the three other operations -- concatenation, regular union, and Kleene star -- have standard meaning. Let Reg0, Reg1 be subsets of Reg defined by the following grammars: Reg0 ::= 0 | x | Reg0 . Reg | Reg . Reg0 | Reg0 + Reg0 Reg1 ::= 1 | Reg1 . Reg1 | Reg1 + Reg | Reg + Reg1 | Reg * One can check that Reg is a disjoint union of Reg0 and Reg1 and that for any a0 \in Reg0 and a1 \in Reg1 the inequality 1 =< a0 is false and 1 =< a1 is true.) Let Set[Reg] denote the set of all finite sets of reg. expressions. DEFINITION ( [3] ) Given x \in A, the function d_x : Reg -> Set[Reg], computing the set of partial derivatives of its argument w.r.t. x, is defined recursively by the following equations: d_x(0) = d_x(1) = {} (* an empty set *), d_x(y) = if y == x then { 1 } else {} fi, d_x(a+b) = d_x(a) \cup d_x(b), d_x(a0.b) = d_x(a0).b, d_x(a1.b) = d_x(a1).b \cup d_x(b), d_x(a*) = d_x(a).a* for all y\in A, a,b \in Reg, a0 \in Reg0, a1 \in Reg1. Here the extension of concatenation _._ to Set[Reg] is defined in the following way: R . 0 = {}, {} . t = {}, {0} . t = {}, {1} . t = {t}, {a} . t = {a.t} if a =/= 0, a =/= 1, (R \cup R').t = (R.t)\cup (R'.t) for any R, R' \in Set[Reg], t \in Reg, t =/= 0, a\in Reg. -------------------- Given a set R \in Set[Reg], let \sum R be either 0 if R={}, or a sum (regular union) a + b + ... of non-zero elements a, b, ... of R. Note that here the regular union _+_ is considered to be associative, commutative and idempotent (while in the above definition of d_x() all regular expressions are treated as free terms). DEFINITION ( [2] ) Given a, b \in Reg, x\in A, and p \in d_x(a), the inequality p =< \sum d_x(b) is called a "partial derivative of a regular inequality a =< b w.r.t. the letter x". Let pd_x(a =< b) be the set of all partial derivatives of a =< b w.r.t. x. Given a set S of inequalities, let pd_x(S)=\bigcup_{s\in S}pd_x(s). ------------------ Iterating this definition, one obtains partial derivatives of a =< b w.r.t. non-empty words on A: pd_{wx}(a =< b) = pd_x(pd_w(a =< b)). for all w\in A^+, x \in A. THEOREM ( [2] ) 1. The set PD(a= Organization: University of Wisconsin - Milwaukee, Computing Services Division Sender: icon-group-request@cs.arizona.edu References: <1994Dec7.200144.18976@llyene.jpl.nasa.gov> Subject: Re: Where can one get ProIcon for Mac? Errors-To: icon-group-errors@cs.arizona.edu In article <1994Dec7.200144.18976@llyene.jpl.nasa.gov> Brian D. Wilson writes: > >Newbie to Icon has two questions: Two questions posted twice over? Have you been frequenting that new restaurant "Twins" in Manhattan? -- Alan D. Corre Emeritus Professor of Hebrew Studies University of Wisconsin-Milwaukee From icon-group-sender Fri Dec 9 00:58:42 1994 Received: by cheltenham.cs.arizona.edu; Thu, 8 Dec 1994 20:00:00 MST To: icon-group-l@cs.arizona.edu Date: Fri, 9 Dec 1994 00:58:42 GMT From: jfriedl@nff.ncl.omron.co.jp (Jeffrey Friedl) Message-Id: Organization: Omron Corporation, Kyoto Japan Sender: icon-group-request@cs.arizona.edu References: <1994Dec7.221649.10939@cs.sfu.ca> Reply-To: jfriedl@nff.ncl.omron.co.jp Subject: Re: [Q] Algorithm for Regexp Subsumption Errors-To: icon-group-errors@cs.arizona.edu vorbeck@cs.sfu.ca (Martin Vorbeck) writes: |> are there any algorithms out there for checking whether a regular |> expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a |> "brute-force" solution along these lines: |> |> 1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2). Make sure you keep the context of your problem (whetever that might be) in mind when doing this. For example, the two regexes (a|a long regex) a( long regex)? (translate to your favorite flavor) are exactly equivalent in a true DFA engines (i.e. emacs), but not equivalent in some others (perl, python, etc.). FWIW, POSIX says they're the same. And FWIW, it's my opinion that being different is much more powerful. |> Please Email any replies to |> vorbeck@cs.sfu.ca |> as I don't usually read these newsgroups. Now might be a good time to start. *jeffrey* ------------------------------------------------------------------------- Jeffrey E.F. Friedl Omron Corporation, Kyoto Japan See my Jap/Eng dictionary at http://www.omron.co.jp/cgi-bin/j-e or http://www.cs.cmu.edu:8001/cgi-bin/j-e From icon-group-sender Fri Dec 9 15:27:47 1994 Received: by cheltenham.cs.arizona.edu; Fri, 9 Dec 1994 08:46:06 MST To: icon-group-l@cs.arizona.edu Date: Fri, 9 Dec 1994 15:27:47 GMT From: goer@quads.uchicago.edu (Richard L. Goerwitz) Message-Id: <1994Dec9.152747.7762@midway.uchicago.edu> Organization: University of Chicago Sender: icon-group-request@cs.arizona.edu References: <1994Dec7.221649.10939@cs.sfu.ca>, Reply-To: goer@midway.uchicago.edu Subject: Re: [Q] Algorithm for Regexp Subsumption Errors-To: icon-group-errors@cs.arizona.edu jfriedl@nff.ncl.omron.co.jp writes: >vorbeck@cs.sfu.ca (Martin Vorbeck) writes: >|> are there any algorithms out there for checking whether a regular >|> expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a >|> "brute-force" solution along these lines: >|> >|> 1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2). > >Make sure you keep the context of your problem (whetever that might be) >in mind when doing this. To be sure. If you create a new DFA, L(E1) or L(E2), then the if you remove extra states correctly you should end up with the same DFA when your done if in fact L(E1) is a subset of L(E2). So in many computa- tional contexts, the question of whether one is a subset or not is not important. Put more succinctly, the regexp a|a* is going to result in the same DFA as a*, if done "by the book." -- -Richard L. Goerwitz goer@midway.uchicago.edu sorry, no witty saying From icon-group-sender Fri Dec 16 15:51:50 1994 Received: by cheltenham.cs.arizona.edu; Fri, 16 Dec 1994 09:32:02 MST To: icon-group-l@cs.arizona.edu Date: Fri, 16 Dec 1994 15:51:50 GMT From: dkuhlman@netcom.com (G. David Kuhlman) Message-Id: Organization: NETCOM On-line Communication Services (408 261-4700 guest) Sender: icon-group-request@cs.arizona.edu Subject: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu An article in the latest "Icon Analyst" reported frequency of use of various control structures in Icon programs, but backtracking was mentioned only briefly. When I first learned about backtracking and goal seeking behavior in Icon I thought, "Wow. Now I can have backtracking like I had in Prolog, AND I don't have to try to write loops and if statements in screwy ways." But now, in spite of the fact that I have a language with a strong backtracking mechanism, I find that I don't use it much, except of course, for trivial constructs like: (checkValid(x) | write("error")) which I feel I have to write instead of an 'if' statement so that I can feel like a cool Icon programmer. Anyway, I'd be interested to know if others use backtracking more heavily, or whether maybe this is just a "neat" but not so useful feature of Icon. Or, could it be that the fact that Icon does not have logical variables, as Prolog does, make backtracking and goal seeking evaluation less usable? -- ---------------------- Dave Kuhlman Reify, Redwood City, CA Internet: dkuhlman@netcom.com ---------------------- From icon-group-sender Fri Dec 16 09:46:11 1994 Received: by cheltenham.cs.arizona.edu; Fri, 16 Dec 1994 09:46:13 MST Date: Fri, 16 Dec 1994 09:46:11 MST From: "Ralph Griswold" Message-Id: <199412161646.AA26875@cheltenham.cs.arizona.edu> To: dkuhlman@netcom.com Subject: Re: Backtracking in Icon Cc: icon-group Errors-To: icon-group-errors@cs.arizona.edu Backtracking is something that occurs at runtime. The article on static analysis in the last issue of the Icon Analyst deal only with static analysis -- that appears in programs, not how they are used. Future issues of the Analyst will address dynamic analysis and show, for example, how many times expressions are resumed to produce alternative results. Ralph E. Griswold ralph@cs.arizona.edu Department of Computer Science uunet!arizona!ralph The University of Arizona 602-621-6609 (voice) Tucson, AZ 85721 602-621-4246 (fax) From icon-group-sender Fri Dec 16 19:49:16 1994 Received: by cheltenham.cs.arizona.edu; Fri, 16 Dec 1994 10:47:05 MST Date: Fri, 16 Dec 1994 19:49:16 +0200 (WET) From: Zvi Lamm To: icon-group@cs.arizona.edu Subject: Re: Backtracking In-Reply-To: <9412161745.AA256230@pluto.mscc.huji.ac.il> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Errors-To: icon-group-errors@cs.arizona.edu A couple of months ago I asked about backtraking and got about 3 answers.. One was neat example of course scheduling. I can send it to anyone interested (if the original programmer is not around...). I still think that backtracking is not used and explained enough. It is really a great trick! It is a rather important control structure, and, when part of a language enriches the ways in which porblems are solved. Ehud Lamm From icon-group-sender Fri Dec 16 14:44:13 1994 Received: by cheltenham.cs.arizona.edu; Fri, 16 Dec 1994 13:45:52 MST Date: Fri, 16 Dec 94 14:44:13 CST From: johnp@utafll.uta.edu (John Paolillo) Message-Id: <9412162244.AA19530@utafll.uta.edu> To: icon-group@cs.arizona.edu Subject: Re: Backtracking Errors-To: icon-group-errors@cs.arizona.edu Dave Kuhlman writes: >Anyway, I'd be interested to know if others use backtracking >more heavily, or whether maybe this is just a "neat" but >not so useful feature of Icon. I have just finished teaching a course "The Computer and Natural Language" using Icon. Through this course, Icon's backtracking became one of my fondest friends, so to speak. I do not have the page numbers, but in the section on pattern matching of Griswold and Griswold, there is a description of language recognizers and parsers that involves writing pattern matching functions. Backtracking is an essential part of the functioning of such recognizers, and makes it possible to teach linguistics students how to write parsers by applying a simple translation process to get from a formalism they know: NP -> (Det) N to something that can actually be used to parse sentences procedure N() suspend ["NP", N()] | ["NP", D(), N()] end (note that this is out of context -- it is used inside a scanning expression, and it is the backtracking that makes it work) I have recently tried to implement something similar in another language that I use (because it is visual), which even employs failure, but which does not have built-in backtracking. The result was an indescribable mess. I would rank backtracking among the most important features of Icon for what I do. There are many many problems you can solve very elegantly with built-in backtracking, and once you finally understand it, it is hard to live without. BTW, one of my students wrote an Icon program to transcribe Tibetan in roman transcription into Tibetan orthography, using techniques exactly like those referred to above. Tibetan graphemes have different shapes (i.e. different ascii codes for us) depending on the position within the syllable that they occur in. Using a phonotactic parser that exploits Icon's backtracking allows an elegant solution to this otherwise difficult problem. John C. Paolillo Linguistics Program University of Texas at Arlington From icon-group-sender Sat Dec 17 12:54:04 1994 Received: by cheltenham.cs.arizona.edu; Sat, 17 Dec 1994 04:54:13 MST Date: Sat, 17 Dec 94 12:54:04 +0100 From: karczma@univ-caen.fr (Jerzy Karczmarczuk) Message-Id: <9412171154.AA22688@milou.univ-caen.fr> To: icon-group@cs.arizona.edu Subject: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu Dave Kuhlman (dkuhlman@netcom) finished his last posting with a remark and a question: > Anyway, I'd be interested to know if others use backtracking > more heavily, or whether maybe this is just a "neat" but > not so useful feature of Icon. > Or, could it be that the fact that Icon does not have logical > variables, as Prolog does, make backtracking and goal seeking > evaluation less usable? John Paolillo (johnp@utafll.uta.edu) decided then to share his experience: > I have just finished teaching a course "The Computer and Natural Language" > using Icon. Through this course, Icon's backtracking became one of my > fondest friends, so to speak. ... > Backtracking is an essential > part of the functioning of such recognizers, and makes it possible > to teach linguistics students how to write parsers by applying a > simple translation process to get from a formalism they know: > NP -> (Det) N > ... etc. > I have recently tried to implement something similar in another > language that I use (because it is visual), which even employs > failure, but which does not have built-in backtracking. The result > was an indescribable mess. I would rank backtracking among the > most important features of Icon for what I do. There are many > many problems you can solve very elegantly with built-in backtracking, > and once you finally understand it, it is hard to live without. A short (?) comment. Backtracking is essential when you use non-deterministic parsing strategies. For linguists, people who read grammar production rules rather conceptually than technically, obviously this is a great thing. You won't teach them the LALR methods, left recursion removal by Greibach normalization, etc., unless you want them to strangle you... Unfortunately, in the domain of computer languages, we have a 30 years old (bad?) tradition - the quest for efficiency, and backtracking is used mainly for teaching, and not for the parser construction. My students might be fascinated by the non-deterministic parsers written in Prolog and using heavily the differential lists, but if they have to write a serious project, they take YACC... But, fortunately, there are other domains where backtracking may be helpful, for exemple other kind (than syntaxical) generators: all kind of combinatorial problems, code-breaking, game playing, task planning etc. Is the existence of the logical variable essential? I don't know, but I doubt. The only place, where this IS essential, and you cannot reproduce this by the reversible instantation is the usage of incomplete data structures in Prolog, e.g. the differential lists. But maybe I am wrong. In the Artificial Intelligence domain, when you have to schedule a solution of a non-deterministic problem, the backtracking IS the only way of doing it reasonably fast (in terms of human time, not the efficiency of the algorithm). Then, it is necessary sometimes to memorize a partial solution. In Prolog this is simply lousy. In Icon this is easier and elegant. I think that Icon may eventually become more popular thanks to its plethora of data structures, and the legibility of the programs. But somebody has to write a serious book showing how to solve real life problems with it. Any takers? Still, another word of critics of gnikcartkcab: "once you finally understand it, it is hard to live without". No Sir, not necessarily. You may replace the backtracking, whose role is to provide you an alternative collection of solutions to a given problem, by a LAZY LIST of these solution. So, the lazy functional languages give you an alternative. You may find some information about this in quite respectable books, for example Henderson, or Abelsson&Sussman. You may wish to read the paper "Painless parsing in Haskell", where this idea is applied to the syntactic analysis. On the other hand, implementing lazy evaluation in Icon is a real pleasure, although it is not natural (as the parameters are passed by value), and it is not very efficient. Jerzy Karczmarczuk Dept. d'Informatique, Universite de Caen, Normandy, France. From icon-group-sender Sat Dec 17 15:33:01 1994 Received: by cheltenham.cs.arizona.edu; Sun, 18 Dec 1994 04:49:38 MST To: icon-group-l@cs.arizona.edu Date: 17 Dec 1994 15:33:01 GMT From: ruiter@ruls41.fsw.LeidenUniv.nl (Jan-Peter de Ruiter) Message-Id: <3cv0bd$gdv@highway.LeidenUniv.nl> Organization: Leiden University, The Netherlands Sender: icon-group-request@cs.arizona.edu References: Subject: Re: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu G. David Kuhlman (dkuhlman@netcom.com) wrote: : But now, in spite of the fact that I have a language : with a strong backtracking mechanism, I find that I : don't use it much, except of course, for trivial : constructs like: : (checkValid(x) | write("error")) I must admit that in the thousands of Icon programs that I've written, I've used serious backtracking only once. But when I used it, it turned out to be very handy. I had this large lexicon of nouns, and had to devise 4tuples of word pairs like this: toilet paper paper cloth cloth builder builder toilet (NOTE: this is a nonsense example, only for illustration - in Dutch you have compounds, that look like "toiletpaper", and then it makes more sense to look for these 4tuples for not all compounds exist in the Dutch lexicon) I could just write a statement with &'s specifying the relations I needed, and generate them all using backtracking. Very nice indeed! There's one more thing I'd like to point out, and that is that the construct you used as an example can also be programmed in C. If you just write (checkValid(x) || printf("error")); you'll have the same thing. So it isn't really backtracking here. It's actually "short circuit evaluation". The same thing can be done in LISP or SCHEME, without backtracking. What _can't_ be done in C, and is very convenient in Icon, is nlines := +argument[1] | 10 thereby establishing a default value for nlines that can be overwritten by a commandline argument. This is a very natural formulation that I use very often in my Icon programs. Hoping to have been informative, Jan From icon-group-sender Mon Dec 19 14:54:50 1994 Received: by cheltenham.cs.arizona.edu; Mon, 19 Dec 1994 08:32:31 MST To: icon-group-l@cs.arizona.edu Date: Mon, 19 Dec 1994 14:54:50 GMT From: bsa@kf8nh.wariat.org (Brandon S. Allbery) Message-Id: <1994Dec19.145450.20178@kf8nh.wariat.org> Organization: Brandon's Linux box and AmPR node, Mentor, OH Sender: icon-group-request@cs.arizona.edu References: , <3cv0bd$gdv@highway.leidenuniv.nl> Subject: Re: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu Also sprach ruiter@ruls41.LeidenUniv.nl (Jan-Peter de Ruiter) (<3cv0bd$gdv@highway.leidenuniv.nl>): +--------------- | G. David Kuhlman (dkuhlman@netcom.com) wrote: | : But now, in spite of the fact that I have a language | : with a strong backtracking mechanism, I find that I | : don't use it much, except of course, for trivial | | : constructs like: | | : (checkValid(x) | write("error")) | | nlines := +argument[1] | 10 | thereby establishing a default value for nlines that can be | overwritten by a commandline argument. This is a very natural | formulation that I use very often in my Icon programs. +------------->8 I think the problem with general use of backtracking is that, while convenient, it's less efficient than improved algorithms are for any given task. (Compare recursive vs. nonrecursive algorithms as another example.) Nevertheless, when it's needed (no readily available non-backtracking algorithm available in a timely fashion) backtracking is very useful. ++Brandon -- Brandon S. Allbery KF8NH [44.70.248.67] bsa@kf8nh.wariat.org Linux development: iBCS2, JNOS, MH ~\U Controlling application developers is like herding cats. --Oracle DBA Manual From "WMCV01::CHRISR"@vmsmail.gov.bc.ca Mon Dec 19 10:39:50 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Mon, 19 Dec 1994 11:39:54 MST Received: from MARS.GOV.BC.CA by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA14930; Mon, 19 Dec 1994 11:39:52 MST Date: Mon, 19 Dec 1994 10:39:50 -0800 (PST) From: Chris Rines <"WMCV01::CHRISR"@vmsmail.gov.bc.ca> To: icon-group@cs.arizona.edu X-Vmsmail-To: GALAXY::IN%"icon-group@cs.arizona.edu",chrisr Message-Id: <941219103950.26219920@vmsmail.gov.bc.ca> Subject: SGML Parser ? Hi all, I was wondering if anyone has greated a validating SGML parser with Icon and would be willing to share the source code. If not is there some good samples kicking around that I could use to learn from and then apply that knowledge towards creating an SGML parser. Thank You for your time, Chris From icon-group-sender Mon Dec 19 10:42:52 1994 Received: by cheltenham.cs.arizona.edu; Mon, 19 Dec 1994 11:42:59 MST Date: Mon, 19 Dec 1994 10:42:52 -0700 (PDT) From: Chris Rines Subject: Windows and Mac Icon To: icon-group@cs.arizona.edu Message-Id: <01HKTPEWZQCY9NGKFG@VENUS.GOV.BC.CA> X-Vms-To: intnet::"icon-group@cs.arizona.edu",chrisr Mime-Version: 1.0 Content-Type: TEXT/PLAIN; CHARSET=US-ASCII Content-Transfer-Encoding: 7BIT Errors-To: icon-group-errors@cs.arizona.edu Hi again, Could someone out there give me some info about the latest Windows & Mac port of Icon (version, etc). Also is the graphics library being ported to these to platforms ? Will they be wrappers around the given operating systems APIs so that the Icon code will be portable ? Thanks, Chris From icon-group-sender Mon Dec 19 09:54:03 1994 Received: by cheltenham.cs.arizona.edu; Mon, 19 Dec 1994 11:54:18 MST Message-Id: <9412191846.AB00763@iias.images.alaska.edu> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 19 Dec 1994 09:54:03 +0000 To: icon-group@cs.arizona.edu From: sysmgr@iias.images.alaska.edu (IIAS System Manager) Subject: Re: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu >> >>"once you finally understand it, it is hard to live without". >> >No Sir, not necessarily. You may replace the backtracking, whose role is to >provide you an alternative collection of solutions to a given problem, by >a LAZY LIST of these solution. So, the lazy functional languages give you >an alternative. You may find some information about this in quite respectable >books, for example Henderson, or Abelsson&Sussman. > He didn't say it was impossible to live without backtracking once you have seen the light, just difficult. I'm not sure what you mean by "lazy lists" - I haven't heard that term before, but if I understand what you mean then isn't using arrays/lists to hold intermediate results then returning to one of those previous states to continue along another path also backtracking? That's what I call it, but perhaps I am misusing the term. Walter R. From icon-group-sender Mon Dec 19 21:10:33 1994 Received: by cheltenham.cs.arizona.edu; Mon, 19 Dec 1994 12:10:20 MST Date: Mon, 19 Dec 1994 21:10:33 +0200 (WET) From: Zvi Lamm To: icon-group@cs.arizona.edu Subject: Backtracking is a way of thinking (was: Re: Backtracking) Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Errors-To: icon-group-errors@cs.arizona.edu The question isn't really if you can program without backtracking. Sure you can, all you need for programming are those little micro-code instructions... The question should be made clear: which programming constructs provide better tools for us to use? Icon is a good language since it give you some important tools that help you work (goal directed evaluation, generators, lists, tables etc...) It is important to rank the different tools by how useful they are. And I am sorry to conclude that since people here say they rarely use it, backtracking doesn't seem to be a very popular or useful tool. I just want to emphesize that this is all part of the larger picture- that is what language you use and what it offers. In prolog, for example, bakctracking is of the essential... Perhapse in Icon we don't need it so much. What do we use instead? Lazy-lists? supension? Is this choice of other tools justified? These qustions I hope will be answered by some Icon gurus... Ehud Lamm From icon-group-sender Mon Dec 19 14:08:33 1994 Received: by cheltenham.cs.arizona.edu; Mon, 19 Dec 1994 14:08:59 MST Date: Mon, 19 Dec 1994 14:08:33 +0700 From: swampler@noao.edu Message-Id: <9412192108.AA04964@orpheus.gemini.edu> Subject: Re: Backtracking in Icon To: icon-group@cs.arizona.edu Content-Length: 4346 Errors-To: icon-group-errors@cs.arizona.edu Brandon Allbery wrote: >> >> I think the problem with general use of backtracking is that, while >> convenient, it's less efficient than improved algorithms are for any given >> task. (Compare recursive vs. nonrecursive algorithms as another example.) >> Nevertheless, when it's needed (no readily available non-backtracking >> algorithm available in a timely fashion) backtracking is very useful. >> Undoubtably true. However, if the speed of execution isn't particularly important (for example, if the program is interactive and likely to be dominated by the 'idle user loop'...), then backtracking solutions can be easy to implement *if* one is thinking that way. The following code fragment is one that Ehud mentioned as an example of backtracking. The original author is Dan Higdon (are you out there, Dan?), way back in '88. I just added some additional features needed by the university I was at during that period. It's the heart of a course scheduling application to let students work out schedules that suit their needs in an environment where there might be 10's and 100's of sections of some courses. The algorithm is a bit daunting if you're not used to (1) Icon, (2) backtracking and (3) combining recursion with backtracking, but I think it's pretty straightforward given those constraints. It takes out a class, schedules the remaining classes (that's the recursion), then tries to find a section of the 'deleted' class that fits in the student's schedule and meets a series of constraints {for example, the campus is 1.5 miles long, north to south (with a green belt in the middle), so the routine nonConflicting() includes a check for how much time there is between classes at opposite ends of campus. It also checks to see if there is room in the class, etc. If the class cannot be scheduled or the schedule is rejected by the student running the program, then the algorithm backtracks to try another section of the previous class. (and so on...) Oh yes, for classes with required labs, it automatically adds those to the schedule as well. Enough of that, here's the heart of the algorithm: -------------------------------------------------------------------------------- # In order to preserve the backtracking idea, schedule is # a generator which generates the possible schedules at # that level of recursion. # # clist is a list of class names # # The algorithm is as follows: # If clist is null, fail # otherwise, # Generate every remaining schedule and do the following with each: # get the class name # Generate every non-null and unconflicting time for each class and # insert it into the set # suspend this schedule, then delete the entry # procedure schedule (cs) local t, schedl, class, tlab if *cs = 0 then return cs # end the recursion, the set of classes is done delete(cs,class := ?cs) # randomly pick out a class... # then schedule all the others # before fitting this one in. every schedl := schedule(cs) & freespace(t := !classdb[class]) & nonConflicting(t, schedl) & (/t.lab | nonConflicting(tlab <- !\t.lab,schedl)) do { # Got it! Put it (and lab) into schedule suspend set([t, \tlab] | [t])\1 ++ schedl } end ------------------------------------------------------------------------------- If you've lasted this long, give the program a try...telnet to pine.cse.nau.edu and login in as 'sch'. You'll need an ANSI compatible terminal to see the schedules themselves. Try the command 'help', then (say) 'help new'. You can get a list of classes in a department by using the 'courses' command, e.g. courses cse will list all the courses offered by the Computer Science and Engineering department. courses cse4 will list all the 400-level (senior) courses. (So Icon devotees will immediately infer that match() is used to look up courses, and yes, courses "" will list every course offered at the university (I hope you have a *fast* connection!.) Do the school a favor and don't print out any schedules! -- Steve Wampler - swampler@gemini.edu [Gemini 8m Telescopes Project (under AURA)] -- The Gods that were smiling when you were born are laughing now. -- found in a fortune cookie From icon-group-sender Mon Dec 19 23:42:51 1994 Received: by cheltenham.cs.arizona.edu; Mon, 19 Dec 1994 17:32:31 MST To: icon-group-l@cs.arizona.edu Date: Mon, 19 Dec 1994 23:42:51 GMT From: rpereda@wotangate.sc.ti.com (Ramon Pereda) Message-Id: <1994Dec19.234251.8715@newshost.micro.ti.com> Organization: Texas Instruments Inc. Sender: icon-group-request@cs.arizona.edu References: Reply-To: rpereda@wotangate.sc.ti.com Subject: Re: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu I've found bactracking to really shine when used to build very powerful parsers with a minimum of effor. Pages 184-186 of the Icon Book gives just an inkling of what is possible. --- Ray Pereda rpereda@tools.micro.ti.com From icon-group-sender Tue Dec 20 06:36:10 1994 Received: by cheltenham.cs.arizona.edu; Tue, 20 Dec 1994 01:18:11 MST To: icon-group-l@cs.arizona.edu Date: 20 Dec 1994 06:36:10 GMT From: Will Mengarini Message-Id: <3d5u0q$ocp@news.halcyon.com> Organization: Northwest Nexus Inc. Sender: icon-group-request@cs.arizona.edu References: Subject: Re: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu dkuhlman@netcom.com (G. David Kuhlman) writes: >[...] in spite of the fact that I have a language >with a strong backtracking mechanism, I find that I >don't use it much, except of course, for trivial >constructs like > (checkValid(x) | write("error")) >which I feel I have to write instead of an >'if' statement so that I can feel like a cool Icon programmer. >I'd be interested to know if others use backtracking more heavily [...] Here are two Icon programs that backtrack for parsing. I hope their length doesn't inconvenience anybody; I thought they were worth posting because the backtracking control structures look weird, & I'd be interested in seeing how other people prettyprint theirs. -------------------------------------------------------------------- # FNortPth.Icn (Full Norton Path) - Will Mengarini - 10 Aug 92 # Filter Norton FA | FS output so each line is 1 full file path # Sample FA output excerpts preceded by column-ruler line: # # 123456789012345678901234567890 # D:\-\I # deldupln.icn # fnortpth.icn Archive # gug Archive # # 33 files shown # no files changed # # D:\-\I\^ # deldupln.asv # deldupln.icn Archive # reverse.icn # scrap.b Archive # _.rst Archive # # 9 files shown # no files changed # # Total of all files # 42 files shown # no files changed # Sample FS output excerpts preceded by column-ruler line: # # 123456789012345678901234567890 # D:\-\I # whug 1,344 bytes # fnortpth.icn 215 bytes # # 30,272 total bytes in 33 files # 77,824 bytes disk space occupied, 61% slack # # D:\-\I\^ # deldupln.asv 1,122 bytes # deldupln.icn 1,058 bytes # # 12,399 total bytes in 9 files # 24,576 bytes disk space occupied, 50% slack # # Total of all files found # 42,671 total bytes in 42 files # 102,400 bytes disk space occupied, 58% slack # # Drive usage # 33,435,648 bytes available on drive D: # 12,103,680 bytes unused on drive D:, 36% unused procedure main() while read() ?( # All & only lines containing "\\" are directories. They begin (after # leading whitespace) with the drive letter, & end with "\\" only if # they specify the root. There are no other words on such lines. tab(many(' ')), dir := tab(upto('\\')) || tab(0) || (move(-1) ~== "\\" | "") )|( # Lines containing file names begin with leading whitespace. Then # come the name & extension as a single word with a separating "."; # there's no whitespace between the name & extension, unlike the # columnar format of FI & Dir. If the extension is empty, the "." is # omitted. In FS, all file names are on lines ending with "bytes"; no # other lines end with "bytes". In FA, file names are followed by a # list of attributes like "Archive"; no other lines contain the words # denoting those attributes; the list may be empty, in which case the # line has only 1 word; no other lines have only 1 word except # directory lines. Therefore, file names are all & only the initial # words on lines that either have no other words & are not directory # lines, | end with "bytes" | a word denoting an attribute. (( ( tab(many(' ')), tab(many(~' \\')), pos(0) # We already know this isn't a directory line since control # can't get this far unless the alternative that handles # directory lines fails. However, the code is more robust if # it doesn't depend on that, & inserting an extra char in a # cset entails no extra run-time computation. )|( reverse(&subject) ? match(reverse( "bytes" | "hive" | "d-Only" | "dden" | "stem" )) ) ) & &pos:=1 & ( tab(many(' ')), write( dir || tab(upto(' ')|0) ) )) )|1 end -------------------------------------------------------------------- # IconGrp.Icn - Will Mengarini - 20 Oct 93 # Takes a //cs.arizona.edu/.../icon/newsgrp/*.txt, which is unthreaded, & # rewrites it in threaded order. The [input, output] file is arg[[1,2]]. # A 2-level ISAM is required to get everything right. First, index file 1 # is written with each line corresponding to a message in the download. # Sorting this file by subject groups together all messages for each thread. # Then, index file 2 is written with each line corresponding to an entire # thread of messages. Index file 1 is then rewritten with the threads still # grouped, but now in chronological rather than alphabetical order; finally, # the same rewriting routine (procedure lookup) is used for the target file. # All this temporary data is kept in temporary files on disk rather than # in RAM, so large newsgroup files can be threaded. # The top line of each article is assumed & required to be the line that # begins with the heading "From icon-group-sender". This line not only marks # the beginning of an article, it also contains the date in a consistent # format, whereas "Date: " lines' formats vary. # This program was developed on a MS-DOS system, & requires the presence # of a sort utility that can accept I/O redirection using "<" & ">", & can # be told the starting column of the sort key using a syntax like # "/+41" (to start in column 41). If you want to run on a different system # that has a system sort with these functions but a different invocation # syntax, you need to change the 2 system() calls in main(). # The temporary files have names ending in ".tmp". global subjectLength, whenLength, startAtLength, linesLength procedure main(arg) subjectLength := 40 whenLength := 14 startAtLength := 12 linesLength := 05 arg[1] || arg[2] | stop( "Usage: IconGrp " ) write( "Writing index file 1" ) index1( arg[1], "IcnGrp1a.tmp" ) write( "Sorting index file 1" ) system( "sort IcnGrp1b.tmp" ) write( "Writing index file 2" ) index2( "IcnGrp1b.tmp", "IcnGrp2a.tmp" ) write( "Sorting index file 2" ) system( "sort IcnGrp2b.tmp /+" || subjectLength + 1 ) write( "Using index file 2 to rewrite index file 1" ) lookup( "IcnGrp2b.tmp", "IcnGrp1b.tmp", "IcnGrp1c.tmp" ) write( "Using index file 1 to rewrite BBS file" ) lookup( "IcnGrp1c.tmp", arg[1], arg[2] ) write( "IconGrp finished." ) end procedure writeIndexLine( out, subject, when, startAt, lines ) writes( out, left( subject, subjectLength ) ) writes( out, left( when , whenLength ) ) writes( out, right( startAt, startAtLength ) ) write ( out, right( lines , linesLength ) ) return end procedure index1( in, out ) months := ["jan","feb","mar","apr","may","jun", "jul","aug","sep","oct","nov","dec",""] in := open( in, "r" ) | stop( "Couldn't open " || in ) out := open( out, "w" ) | stop( "Couldn't open " || out ) lineNumber := 0 while at := where(in) & line := !in & lineNumber +:= 1 do { line ? (( = "From icon-group-sender", # # Write data for previous article if there was one # if writeIndexLine( out, subject, when, startAt, \lines ) then { write( " index1: at = ", at ) } else { "do not fail" }, lines := 0, startAt := at, # # Parse the date; the line looks like # From icon-group-sender Thu Mar 18 12:24:03 1993 # We are here --------------^ # map(tab(0)) ? ( tab(find( months[month := (1 to *months)] )), # We're now at the *start* of the month name tab(many(~' ')), tab(many(' ')), date := tab(many(&digits)), tab(many(' ')), time := tab(many(~' ')), tab(many(' ')), year := tab(0) ), if month = 13 then { stop("Month not found on line # ",lineNumber) } else { when := year[3:0] || " " || right(month,2,"0") || " " || right(date,2,"0") || " " || time[1+:5] } )|( ="Subject: ", subject := tab(0), # # Extract the subject (which will define the thread) # ( map(subject) ? (= "re:", tab(many(' ')), subject[1:&pos] := "") )|( "do not fail" ) )) lines +:= 1 } writeIndexLine( out, subject, when, startAt, lines ) every close( in | out ) end procedure index2( in, out ) in := open( in, "r" ) | stop( "Couldn't open " || in ) out := open( out, "w" ) | stop( "Couldn't open " || out ) while at := where(in) & line := !in do { if subject ~=== line[1+:subjectLength] then { write( " index2: at = ", at ) writeIndexLine( out, \subject, when, startAt, lines ) line ? ( subject := move(subjectLength), when := move(whenLength) ) lines := 0; startAt := at } lines +:= 1 } writeIndexLine( out, subject, when, startAt, lines ) every close( in | out ) end procedure lookup( index, in, out ) index := open( index, "r" ) | stop( "Couldn't open " || index ) in := open( in, "r" ) | stop( "Couldn't open " || in ) out := open( out, "w" ) | stop( "Couldn't open " || out ) every !index ? ( move(subjectLength + whenLength), at := move(startAtLength), lines := move(linesLength) ) do { write( " lookup: at == \"", at, "\", lines == \"", lines, "\"" ) seek( in, at ) every 1 to lines do write( out, read(in) ) } every close( index | in | out ) end -------------------------------------------------------------------- Will Mengarini Be gentle, I'm from Delphi "(sorry, I can't figure out how to edit with this mail-reader)" --Marvin Minsky, quoted by Tom Maddox From icon-group-sender Tue Dec 20 19:29:21 1994 Received: by cheltenham.cs.arizona.edu; Tue, 20 Dec 1994 15:47:42 MST To: icon-group-l@cs.arizona.edu Date: 20 Dec 1994 19:29:21 GMT From: norman@flaubert.bellcore.com (Norman Ramsey) Message-Id: <3d7bah$q2e@lowell.bellcore.com> Organization: Bellcore, Morristown NJ Sender: icon-group-request@cs.arizona.edu References: Subject: Re: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu I use goal-directed evaluation (backtracking) heavily, mostly to implement predicates of the form ``there exists an X such that P(X).'' I occasionally find other uses. I wish there were an equally nice way to write ``forall'' predicates (I usually negate everything in sight to get an ``exists'' predicate). From icon-group-sender Tue Dec 20 16:45:29 1994 Received: by cheltenham.cs.arizona.edu; Tue, 20 Dec 1994 17:17:42 MST To: icon-group-l@cs.arizona.edu Date: 20 Dec 1994 16:45:29 -0700 From: scott@cs.arizona.edu (Scott E Gilbert) Message-Id: <3d7qap$ni2@caslon.CS.Arizona.EDU> Organization: University of Arizona CS Department, Tucson AZ Sender: icon-group-request@cs.arizona.edu References: , <3d7bah$q2e@lowell.bellcore.com> Subject: Re: Backtracking in Icon Errors-To: icon-group-errors@cs.arizona.edu In article <3d7bah$q2e@lowell.bellcore.com>, Norman Ramsey wrote: > >I use goal-directed evaluation (backtracking) heavily, mostly to >implement predicates of the form ``there exists an X such that P(X).'' >I occasionally find other uses. I wish there were an equally nice way >to write ``forall'' predicates (I usually negate everything in sight >to get an ``exists'' predicate). > Could you post an example of this? I'm very curious to see what it is you are doing. I would also like to see what type of "forall" predicates you want to implement. Thanks. -- Scott Gilbert ( scott@cs.arizona.edu ) From icon-group-sender Wed Dec 21 18:17:55 1994 Received: by cheltenham.cs.arizona.edu; Wed, 21 Dec 1994 11:33:09 MST To: icon-group-l@cs.arizona.edu Date: 21 Dec 1994 18:17:55 GMT From: mdmcdo01@vulcan.spd.louisville.edu (Mark D. McDonald) Message-Id: <3d9rgj$qkc@hermes.louisville.edu> Organization: University of Louisville, Louisville KY USA Sender: icon-group-request@cs.arizona.edu Subject: icon-mode lisp package for icon Errors-To: icon-group-errors@cs.arizona.edu does anyone have the icon-mode lisp package for the emacs editor? i would appreciate a pointer to it. thanks -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~ mark d. mcdonald | mdmcdo01@starbase.spd.louisville.edu ~ ~ speed scientific school | phone: (812) 738-7194 ~ ~ university of louisville | ~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From ralph Wed Dec 21 11:51:28 1994 Date: Wed, 21 Dec 1994 11:51:28 MST From: "Ralph Griswold" Message-Id: <199412211851.AA20727@cheltenham.cs.arizona.edu> Received: by cheltenham.cs.arizona.edu; Wed, 21 Dec 1994 11:51:28 MST To: icon-group Subject: Forwarded request From gkt@glen-ellyn.iit.edu Wed Dec 21 10:56:43 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 21 Dec 1994 10:56:42 MST Received: from glen-ellyn.iit.edu by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA18669; Wed, 21 Dec 1994 10:56:40 MST Received: by glen-ellyn.iit.edu (4.1/SMI-4.1) id AA13543; Wed, 21 Dec 94 11:56:25 CST Date: Wed, 21 Dec 1994 11:52:28 -0600 (CST) From: George Thiruvathukal Subject: Icon & Unix pipes To: ralph@cs.arizona.edu Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Hi, Prof. Griswold, I am using Icon to develop a collection of tools called the Web Construction Set. Icon is proving to be very useful for the task at hand, but I am having some trouble using pipes. It does not appear to be possible to open a full-duplex pipe between processes. This is sort of a pain, because I will then be forced to use files to communicate results between processes. One of the goals of WCS is to generate pages without using intermediate files on the Web server. Thanks for any suggestions on how to proceed. -George From cliff Wed Dec 21 12:53:09 1994 Date: Wed, 21 Dec 1994 12:53:09 MST From: "Cliff Hathaway" Message-Id: <199412211953.AA21738@cheltenham.cs.arizona.edu> Received: by cheltenham.cs.arizona.edu; Wed, 21 Dec 1994 12:53:09 MST To: icon-group Subject: Re: icon-mode lisp package for icon ftp.cs.arizona.edu:/icon/contrib/emacs From abrahams@equinox.shaysnet.com Wed Dec 21 23:03:40 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 21 Dec 1994 21:06:48 MST Received: from relay1.UU.NET by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA23215; Wed, 21 Dec 1994 21:06:46 MST Received: from equinox.shaysnet.com by relay1.UU.NET with SMTP id QQxvie08554; Wed, 21 Dec 1994 23:06:39 -0500 Received: by equinox.shaysnet.com (4.1/SMI-4.1) id AA06292; Wed, 21 Dec 94 23:03:40 EST Date: Wed, 21 Dec 94 23:03:40 EST From: abrahams@equinox.ShaysNet.COM (Paul Abrahams) Message-Id: <9412220403.AA06292@equinox.shaysnet.com> To: icon-group@cs.arizona.edu Subject: Where is icon-mode.el for Emacs? A recent post suggested that an Icon mode file for Emacs could be found at ftp.cs.arizona.edu in directory icon/contrib/emacs. I looked there and found only icon-describe.el and cognate files. So is there somewhere I can get the Lisp code for editing Icon programs under Emacs? Paul Abrahams abrahams@acm.org From jeffery@runner.jpl.utsa.edu Thu Dec 22 06:43:19 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Thu, 22 Dec 1994 05:43:41 MST Received: from runner.utsa.edu (runner.jpl.utsa.edu) by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA15125; Thu, 22 Dec 1994 05:43:37 MST Received: by runner.utsa.edu (5.0/SMI-SVR4) id AA03475; Thu, 22 Dec 1994 06:43:19 -0600 Date: Thu, 22 Dec 1994 06:43:19 -0600 From: jeffery@runner.jpl.utsa.edu (Clinton L. Jeffery) Message-Id: <9412221243.AA03475@runner.utsa.edu> To: abrahams@equinox.ShaysNet.COM Cc: icon-group@cs.arizona.edu In-Reply-To: <9412220403.AA06292@equinox.shaysnet.com> (abrahams@equinox.ShaysNet.COM) Subject: Re: Where is icon-mode.el for Emacs? Content-Length: 19913 I was under the impression that GNU emacs came with an icon-mode.el At least, I know *I* didn't have to write one. Here's what I've been using; its hacked a bit from the real one. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Icon code editing commands for Emacs ;; Derived from c-mode.el 15-Apr-88 Chris Smith convex!csmith ;; Copyright (C) 1988 Free Software Foundation, Inc. ;; This file is part of GNU Emacs. ;; GNU Emacs is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY. No author or distributor ;; accepts responsibility to anyone for the consequences of using it ;; or for whether it serves any particular purpose or works at all, ;; unless he says so in writing. Refer to the GNU Emacs General Public ;; License for full details. ;; Everyone is granted permission to copy, modify and redistribute ;; GNU Emacs, but only under the conditions described in the ;; GNU Emacs General Public License. A copy of this license is ;; supposed to have been given to you along with GNU Emacs so you ;; can know your rights and responsibilities. It should be in a ;; file named COPYING. Among other things, the copyright notice ;; and this notice must be preserved on all copies. (provide 'icon-mode) (defvar icon-mode-abbrev-table nil "Abbrev table in use in Icon-mode buffers.") (define-abbrev-table 'icon-mode-abbrev-table ()) (defvar icon-mode-map () "Keymap used in Icon mode.") (if icon-mode-map () (setq icon-mode-map (make-sparse-keymap)) (define-key icon-mode-map "{" 'electric-icon-brace) (define-key icon-mode-map "}" 'electric-icon-brace) (define-key icon-mode-map "\e\C-h" 'mark-icon-function) (define-key icon-mode-map "\e\C-a" 'beginning-of-icon-defun) (define-key icon-mode-map "\e\C-e" 'end-of-icon-defun) (define-key icon-mode-map "\e\C-q" 'indent-icon-exp) (define-key icon-mode-map "\177" 'backward-delete-char-untabify) (define-key icon-mode-map "\t" 'icon-indent-command)) (defvar icon-mode-syntax-table nil "Syntax table in use in Icon-mode buffers.") (if icon-mode-syntax-table () (setq icon-mode-syntax-table (make-syntax-table)) (modify-syntax-entry ?\\ "\\" icon-mode-syntax-table) (modify-syntax-entry ?# "<" icon-mode-syntax-table) (modify-syntax-entry ?\n ">" icon-mode-syntax-table) (modify-syntax-entry ?$ "." icon-mode-syntax-table) (modify-syntax-entry ?/ "." icon-mode-syntax-table) (modify-syntax-entry ?* "." icon-mode-syntax-table) (modify-syntax-entry ?+ "." icon-mode-syntax-table) (modify-syntax-entry ?- "." icon-mode-syntax-table) (modify-syntax-entry ?= "." icon-mode-syntax-table) (modify-syntax-entry ?% "." icon-mode-syntax-table) (modify-syntax-entry ?< "." icon-mode-syntax-table) (modify-syntax-entry ?> "." icon-mode-syntax-table) (modify-syntax-entry ?& "." icon-mode-syntax-table) (modify-syntax-entry ?| "." icon-mode-syntax-table) (modify-syntax-entry ?\' "\"" icon-mode-syntax-table)) ; this used to be 4 (defconst icon-indent-level 3 "*Indentation of Icon statements with respect to containing block.") (defconst icon-brace-imaginary-offset 0 "*Imagined indentation of a Icon open brace that actually follows a statement.") (defconst icon-brace-offset 3 "*Extra indentation for braces, compared with other text in same context.") ; this used to be 4 (defconst icon-continued-statement-offset 3 "*Extra indent for lines not starting new statements.") (defconst icon-continued-brace-offset 0 "*Extra indent for substatements that start with open-braces. This is in addition to icon-continued-statement-offset.") (defconst icon-auto-newline nil "*Non-nil means automatically newline before and after braces, and after colons and semicolons, inserted in C code.") (defconst icon-tab-always-indent t "*Non-nil means TAB in Icon mode should always reindent the current line, regardless of where in the line point is when the TAB command is used.") (defun icon-mode () "Major mode for editing Icon code. Expression and list commands understand all Icon brackets. Tab indents for Icon code. Paragraphs are separated by blank lines only. Delete converts tabs to spaces as it moves back. \\{icon-mode-map} Variables controlling indentation style: icon-tab-always-indent Non-nil means TAB in Icon mode should always reindent the current line, regardless of where in the line point is when the TAB command is used. icon-auto-newline Non-nil means automatically newline before and after braces inserted in Icon code. icon-indent-level Indentation of Icon statements within surrounding block. The surrounding block's indentation is the indentation of the line on which the open-brace appears. icon-continued-statement-offset Extra indentation given to a substatement, such as the then-clause of an if or body of a while. icon-continued-brace-offset Extra indentation given to a brace that starts a substatement. This is in addition to icon-continued-statement-offset. icon-brace-offset Extra indentation for line if it starts with an open brace. icon-brace-imaginary-offset An open brace following other text is treated as if it were this far to the right of the start of its line. Turning on Icon mode calls the value of the variable icon-mode-hook with no args, if that value is non-nil." (interactive) (kill-all-local-variables) (use-local-map icon-mode-map) (setq major-mode 'icon-mode) (setq mode-name "Icon") (setq local-abbrev-table icon-mode-abbrev-table) (set-syntax-table icon-mode-syntax-table) (make-local-variable 'paragraph-start) (setq paragraph-start (concat "^$\\|" page-delimiter)) (make-local-variable 'paragraph-separate) (setq paragraph-separate paragraph-start) (make-local-variable 'indent-line-function) (setq indent-line-function 'icon-indent-line) (make-local-variable 'require-final-newline) (setq require-final-newline t) (make-local-variable 'comment-start) (setq comment-start "# ") (make-local-variable 'comment-end) (setq comment-end "") (make-local-variable 'comment-column) (setq comment-column 32) (make-local-variable 'comment-start-skip) (setq comment-start-skip "# *") (make-local-variable 'comment-indent-hook) (setq comment-indent-hook 'icon-comment-indent) (run-hooks 'icon-mode-hook)) ;; This is used by indent-for-comment ;; to decide how much to indent a comment in Icon code ;; based on its context. (defun icon-comment-indent () (if (looking-at "^#") 0 ;Existing comment at bol stays there. (save-excursion (skip-chars-backward " \t") (max (1+ (current-column)) ;Else indent at comment column comment-column)))) ; except leave at least one space. (defun electric-icon-brace (arg) "Insert character and correct line's indentation." (interactive "P") (let (insertpos) (if (and (not arg) (eolp) (or (save-excursion (skip-chars-backward " \t") (bolp)) (if icon-auto-newline (progn (icon-indent-line) (newline) t) nil))) (progn (insert last-command-char) (icon-indent-line) (if icon-auto-newline (progn (newline) ;; (newline) may have done auto-fill (setq insertpos (- (point) 2)) (icon-indent-line))) (save-excursion (if insertpos (goto-char (1+ insertpos))) (delete-char -1)))) (if insertpos (save-excursion (goto-char insertpos) (self-insert-command (prefix-numeric-value arg))) (self-insert-command (prefix-numeric-value arg))))) (defun icon-indent-command (&optional whole-exp) (interactive "P") "Indent current line as Icon code, or in some cases insert a tab character. If icon-tab-always-indent is non-nil (the default), always indent current line. Otherwise, indent the current line only if point is at the left margin or in the line's indentation; otherwise insert a tab. A numeric argument, regardless of its value, means indent rigidly all the lines of the expression starting after point so that this line becomes properly indented. The relative indentation among the lines of the expression are preserved." (if whole-exp ;; If arg, always indent this line as Icon ;; and shift remaining lines of expression the same amount. (let ((shift-amt (icon-indent-line)) beg end) (save-excursion (if icon-tab-always-indent (beginning-of-line)) (setq beg (point)) (forward-sexp 1) (setq end (point)) (goto-char beg) (forward-line 1) (setq beg (point))) (if (> end beg) (indent-code-rigidly beg end shift-amt "#"))) (if (and (not icon-tab-always-indent) (save-excursion (skip-chars-backward " \t") (not (bolp)))) (insert-tab) (icon-indent-line)))) (defun icon-indent-line () "Indent current line as Icon code. Return the amount the indentation changed by." (let ((indent (calculate-icon-indent nil)) beg shift-amt (case-fold-search nil) (pos (- (point-max) (point)))) (beginning-of-line) (setq beg (point)) (cond ((eq indent nil) (setq indent (current-indentation))) ((eq indent t) (setq indent (calculate-icon-indent-within-comment))) ; ((looking-at "[ \t]*#") ; (setq indent 0)) (t (skip-chars-forward " \t") (if (listp indent) (setq indent (car indent))) (cond ((and (looking-at "else\\b") (not (looking-at "else\\s_"))) (setq indent (save-excursion (icon-backward-to-start-of-if) (current-indentation)))) ;;; ((or (= (following-char) ?}) ;;; (looking-at "end\\b")) ((looking-at "end\\b") (setq indent (- indent icon-indent-level))) ((= (following-char) ?{) (setq indent (+ indent icon-brace-offset)))))) (skip-chars-forward " \t") (setq shift-amt (- indent (current-column))) (if (zerop shift-amt) (if (> (- (point-max) pos) (point)) (goto-char (- (point-max) pos))) (delete-region beg (point)) (indent-to indent) ;; If initial point was within line's indentation, ;; position after the indentation. Else stay at same point in text. (if (> (- (point-max) pos) (point)) (goto-char (- (point-max) pos)))) shift-amt)) (defun calculate-icon-indent (&optional parse-start) "Return appropriate indentation for current line as Icon code. In usual case returns an integer: the column to indent to. Returns nil if line starts inside a string, t if in a comment." (save-excursion (beginning-of-line) (let ((indent-point (point)) (case-fold-search nil) state containing-sexp toplevel) (if parse-start (goto-char parse-start) (setq toplevel (beginning-of-icon-defun))) (while (< (point) indent-point) (setq parse-start (point)) (setq state (parse-partial-sexp (point) indent-point 0)) (setq containing-sexp (car (cdr state)))) (cond ((or (nth 3 state) (nth 4 state)) ;; return nil or t if should not change this line (nth 4 state)) ((and containing-sexp (/= (char-after containing-sexp) ?{)) ;; line is expression, not statement: ;; indent to just after the surrounding open. (goto-char (1+ containing-sexp)) (current-column)) (t ;; Statement level. Is it a continuation or a new statement? ;; Find previous non-comment character. (if toplevel (progn (icon-backward-to-noncomment (point-min)) (if (icon-is-continuation-line) icon-continued-statement-offset 0)) (if (null containing-sexp) (progn (beginning-of-icon-defun) (setq containing-sexp (point)))) (goto-char indent-point) (icon-backward-to-noncomment containing-sexp) ;; Now we get the answer. (if (icon-is-continuation-line) ;; This line is continuation of preceding line's statement; ;; indent icon-continued-statement-offset more than the ;; first line of the statement. (progn (icon-backward-to-start-of-continued-exp containing-sexp) (+ icon-continued-statement-offset (current-column) (if (save-excursion (goto-char indent-point) (skip-chars-forward " \t") (eq (following-char) ?{)) icon-continued-brace-offset 0))) ;; This line starts a new statement. ;; Position following last unclosed open. (goto-char containing-sexp) ;; Is line first statement after an open-brace? (or ;; If no, find that first statement and indent like it. (save-excursion (if (looking-at "procedure\\s ") (forward-sexp 3) (forward-char 1)) (while (progn (skip-chars-forward " \t\n") (looking-at "#")) ;; Skip over comments following openbrace. (forward-line 1)) ;; The first following code counts ;; if it is before the line we want to indent. (and (< (point) indent-point) (current-column))) ;; If no previous statement, ;; indent it relative to line brace is on. ;; For open brace in column zero, don't let statement ;; start there too. If icon-indent-level is zero, ;; use icon-brace-offset + icon-continued-statement-offset instead. ;; For open-braces not the first thing in a line, ;; add in icon-brace-imaginary-offset. (+ (if (and (bolp) (zerop icon-indent-level)) (+ icon-brace-offset icon-continued-statement-offset) icon-indent-level) ;; Move back over whitespace before the openbrace. ;; If openbrace is not first nonwhite thing on the line, ;; add the icon-brace-imaginary-offset. (progn (skip-chars-backward " \t") (if (bolp) 0 icon-brace-imaginary-offset)) ;; here we are (current-indentation)))))))))) (defun icon-is-continuation-line () (let* ((ch (preceding-char)) (ch-syntax (char-syntax ch))) (if (eq ch-syntax ?w) (assoc (buffer-substring (progn (forward-word -1) (point)) (progn (forward-word 1) (point))) '(("do") ("dynamic") ("else") ("initial") ("link") ("local") ("of") ("static") ("then"))) (not (memq ch '(0 ?\; ?\} ?\{ ?\) ?\] ?\" ?\' ?\n)))))) (defun icon-backward-to-noncomment (lim) (let (opoint stop) (while (not stop) (skip-chars-backward " \t\n\f" lim) (setq opoint (point)) (beginning-of-line) (if (and (search-forward "#" opoint 'move) (< lim (point))) (forward-char -1) (setq stop t))))) (defun icon-backward-to-start-of-continued-exp (lim) (if (memq (preceding-char) '(?\) ?\])) (forward-sexp -1)) (while (icon-is-continued-line) (end-of-line 0)) (beginning-of-line) (if (<= (point) lim) (goto-char (1+ lim))) (skip-chars-forward " \t")) (defun icon-is-continued-line () (save-excursion (end-of-line 0) (icon-is-continuation-line))) (defun icon-backward-to-start-of-if (&optional limit) "Move to the start of the last ``unbalanced'' if." (or limit (setq limit (save-excursion (beginning-of-icon-defun) (point)))) (let ((if-level 1) (case-fold-search nil)) (while (not (zerop if-level)) (backward-sexp 1) (cond ((looking-at "else\\b") (setq if-level (1+ if-level))) ((looking-at "if\\b") (setq if-level (1- if-level))) ((< (point) limit) (setq if-level 0) (goto-char limit)))))) (defun mark-icon-function () "Put mark at end of Icon function, point at beginning." (interactive) (push-mark (point)) (end-of-icon-defun) (push-mark (point)) (beginning-of-line 0) (beginning-of-icon-defun)) (defun beginning-of-icon-defun () "Go to the start of the enclosing procedure; return t if at top level." (interactive) (if (re-search-backward "^procedure\\s \\|^end[ \t\n]" (point-min) 'move) (looking-at "e") t)) (defun end-of-icon-defun () (interactive) (if (not (bobp)) (forward-char -1)) (re-search-forward "\\(\\s \\|^\\)end\\(\\s \\|$\\)" (point-max) 'move) (forward-word -1) (forward-line 1)) (defun indent-icon-exp () "Indent each line of the Icon grouping following point." (interactive) (let ((indent-stack (list nil)) (contain-stack (list (point))) (case-fold-search nil) restart outer-loop-done inner-loop-done state ostate this-indent last-sexp at-else at-brace at-do (opoint (point)) (next-depth 0)) (save-excursion (forward-sexp 1)) (save-excursion (setq outer-loop-done nil) (while (and (not (eobp)) (not outer-loop-done)) (setq last-depth next-depth) ;; Compute how depth changes over this line ;; plus enough other lines to get to one that ;; does not end inside a comment or string. ;; Meanwhile, do appropriate indentation on comment lines. (setq innerloop-done nil) (while (and (not innerloop-done) (not (and (eobp) (setq outer-loop-done t)))) (setq ostate state) (setq state (parse-partial-sexp (point) (progn (end-of-line) (point)) nil nil state)) (setq next-depth (car state)) (if (and (car (cdr (cdr state))) (>= (car (cdr (cdr state))) 0)) (setq last-sexp (car (cdr (cdr state))))) (if (or (nth 4 ostate)) (icon-indent-line)) (if (or (nth 3 state)) (forward-line 1) (setq innerloop-done t))) (if (<= next-depth 0) (setq outer-loop-done t)) (if outer-loop-done nil (if (/= last-depth next-depth) (setq last-sexp nil)) (while (> last-depth next-depth) (setq indent-stack (cdr indent-stack) contain-stack (cdr contain-stack) last-depth (1- last-depth))) (while (< last-depth next-depth) (setq indent-stack (cons nil indent-stack) contain-stack (cons nil contain-stack) last-depth (1+ last-depth))) (if (null (car contain-stack)) (setcar contain-stack (or (car (cdr state)) (save-excursion (forward-sexp -1) (point))))) (forward-line 1) (skip-chars-forward " \t") (if (eolp) nil (if (and (car indent-stack) (>= (car indent-stack) 0)) ;; Line is on an existing nesting level. ;; Lines inside parens are handled specially. (if (/= (char-after (car contain-stack)) ?{) (setq this-indent (car indent-stack)) ;; Line is at statement level. ;; Is it a new statement? Is it an else? ;; Find last non-comment character before this line (save-excursion (setq at-else (looking-at "else\\W")) (setq at-brace (= (following-char) ?{)) (icon-backward-to-noncomment opoint) (if (icon-is-continuation-line) ;; Preceding line did not end in comma or semi; ;; indent this line icon-continued-statement-offset ;; more than previous. (progn (icon-backward-to-start-of-continued-exp (car contain-stack)) (setq this-indent (+ icon-continued-statement-offset (current-column) (if at-brace icon-continued-brace-offset 0)))) ;; Preceding line ended in comma or semi; ;; use the standard indent for this level. (if at-else (progn (icon-backward-to-start-of-if opoint) (setq this-indent (current-indentation))) (setq this-indent (car indent-stack)))))) ;; Just started a new nesting level. ;; Compute the standard indent for this level. (let ((val (calculate-icon-indent (if (car indent-stack) (- (car indent-stack)))))) (setcar indent-stack (setq this-indent val)))) ;; Adjust line indentation according to its contents (if (or (= (following-char) ?}) (looking-at "end\\b")) (setq this-indent (- this-indent icon-indent-level))) (if (= (following-char) ?{) (setq this-indent (+ this-indent icon-brace-offset))) ;; Put chosen indentation into effect. (or (= (current-column) this-indent) (progn (delete-region (point) (progn (beginning-of-line) (point))) (indent-to this-indent))) ;; Indent any comment following the text. (or (looking-at comment-start-skip) (if (re-search-forward comment-start-skip (save-excursion (end-of-line) (point)) t) (progn (indent-for-comment) (beginning-of-line)))))))))) From icon-group-request Thu Dec 22 18:46:58 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Thu, 22 Dec 1994 12:03:10 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA04818; Thu, 22 Dec 1994 12:03:05 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id LAA06686; Thu, 22 Dec 1994 11:00:27 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: 22 Dec 1994 18:46:58 GMT From: qhuynh@site.gmu.edu (Quoc Huynh (CS 332)) Message-Id: <3dchj2$p6t@portal.gmu.edu> Organization: George Mason University, Fairfax, Virginia, USA Sender: icon-group-request@cs.arizona.edu Subject: HELP: conver gif -> icon OR gif -> ansi does anyone know of a program, to convert GIF to ICON (win 3.1) and GIF to ANSI Thank you, qhuynh@site.gmu.edu From icon-group-request Fri Dec 23 13:58:36 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Fri, 23 Dec 1994 07:18:18 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA27375; Fri, 23 Dec 1994 07:18:16 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id GAA01514; Fri, 23 Dec 1994 06:07:15 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: 23 Dec 1994 13:58:36 GMT From: ruiter@ruls41.fsw.leidenuniv.nl (Jan-Peter de Ruiter) Message-Id: <3del2c$1in@highway.LeidenUniv.nl> Organization: Leiden University, The Netherlands Sender: icon-group-request@cs.arizona.edu References: <3dchj2$p6t@portal.gmu.edu> Subject: Re: HELP: conver gif -> icon OR gif -> ansi Quoc Huynh (CS 332) (qhuynh@site.gmu.edu) wrote: : does anyone know of a program, to convert GIF to ICON (win 3.1) : and GIF to ANSI The Icon newsgroup is on the comp.lang hierarchy, indicating to the initiated that is is about a _programming language_. Not surprisingly, this programming language is called "Icon". Icon is a magnificent programming language, but representing GIF images as Icon source is, although certainly possible in principle, not the most obvious use of the language. Jan From icon-group-request Fri Dec 23 21:38:08 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Fri, 23 Dec 1994 15:29:46 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA25629; Fri, 23 Dec 1994 15:29:44 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id OAA07719; Fri, 23 Dec 1994 14:12:27 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: Fri, 23 Dec 1994 21:38:08 GMT From: jsampson@cix.compulink.co.uk ("John Sampson") Message-Id: Organization: Sole Trader Sender: icon-group-request@cs.arizona.edu Subject: Graphics for Windows Is anyone developing the graphics aspect of Icon to work on Windows - the one that sits on top of MS-DOS, not X-Windows? _John Sampson_ From icon-group-request Fri Dec 23 19:24:30 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Fri, 23 Dec 1994 18:31:47 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA05417; Fri, 23 Dec 1994 18:31:45 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id RAA11212; Fri, 23 Dec 1994 17:10:55 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: 23 Dec 1994 19:24:30 -0500 From: Bobr@voyager.cris.com (BobR) Message-Id: <3dfpnu$otg@voyager.cris.com> Organization: Concentric Research Corporation Sender: icon-group-request@cs.arizona.edu Subject: Help- Another Prob.? To: ALL Subject: Help- Another Prob.? Many thanks to all for responding to the problem that I was having with the ICON Config file. I ran MAKE on both the compiler and interpeter and everything seemed to go well until I received the following message: xfmonitr.o Undefined Symbol -profile Referenced from text segment /root/icon/src/runtime I'm using Linux...... and working with Icon V8.10 I found that I had an executable for both the compiler and interpeter and when I ran the Make Test, everything looked OK. I also wrote a couple of small Icon programs and tried both the compiler and interpeter and everything worked as planned. Do I still have a problem? Many Thanks, Have a great holiday Bob Randall --- ~ OLX 1.53 ~ Dogs come when you call. Cats have answering machines. From icon-group-request Sun Dec 25 05:56:46 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Sun, 25 Dec 1994 04:30:18 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA00527; Sun, 25 Dec 1994 04:30:16 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id DAA11618; Sun, 25 Dec 1994 03:00:05 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: 25 Dec 1994 05:56:46 -0500 From: MENGARINI@news1.delphi.com (MENGARINI@DELPHI.COM) Message-Id: <3djj5e$7pd@news2.delphi.com> Organization: Delphi Internet Services Corporation Sender: icon-group-request@cs.arizona.edu Subject: DeMorgan's Law doesn't work I needed to find the first filename of the form "w[0-9][0-9]" that was not in use in either of 2 directories. This code ( nn := (0 to 9) || (0 to 9) , not exists( downloadDir || "w" || nn ) , not exists( targetDir || "w" || nn ) )|stop( "No names of the form w[0-9][0-9] were unused." ) works, but the separation of the 2 "not exists" calls is reminiscent of Algol-family languages' need to code things like if importantNumber = 1 | importantNumber = 2 where Snobol-family languages could just test whether importantNumber = 1 | 2 Analogously, Icon should be able to factor out the 2 "not exists" calls. But this ( nn := (0 to 9) || (0 to 9) , not exists( (downloadDir|targetDir) || "w" || nn ) )|stop( "No names of the form w[0-9][0-9] were unused." ) doesn't work because DeMorgan's Law doesn't work: if downloadDir || "w" || nn doesn't exist, exists() fails, not exists() succeeds, & the expression succeeds, without ever testing whether targetDir || "w" || nn exists. So far, this (every nn := (0 to 9) || (0 to 9) do { (exists( (downloadDir|targetDir) || "\\w" || nn ), next) | break })|stop( "No names of the form w[0-9][0-9] were unused." ) is the best I can do, but I dislike it because it makes use of a very obscure aspect of break; Griswold & Griswold 1990 p19 doesn't even mention it, altho it's in Appendix C on p285. (BTW, p19 seems to imply incorrectly that break only works with while & until, even tho every was introduced on p16; & Appendix C doesn't clarify this.) Can anybody suggest a more elegant expression? Can anybody suggest a language extension that would help? "Software is neither science nor engineering. It's really an obscure form of poetry." --Dirk Zoller Will Mengarini Hey, at least it's not AOL From icon-group-request Mon Dec 26 14:10:30 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Mon, 26 Dec 1994 16:33:28 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA28262; Mon, 26 Dec 1994 16:33:26 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id OAA12758; Mon, 26 Dec 1994 14:10:57 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: 26 Dec 1994 14:10:30 -0800 From: omalley@porte-de-st-ouen.ics.uci.edu (T. Owen O'Malley) Message-Id: <3dnf0m$85i@porte-de-st-ouen.ics.uci.edu> Organization: UC Irvine Department of ICS Sender: icon-group-request@cs.arizona.edu References: <3djj5e$7pd@news2.delphi.com> Subject: Re: DeMorgan's Law doesn't work In <3djj5e$7pd@news2.delphi.com> MENGARINI@news.delphi.com (MENGARINI@DELPHI.COM) writes: > ( nn := (0 to 9) || (0 to 9) > , not exists( downloadDir || "w" || nn ) > , not exists( targetDir || "w" || nn ) > )|stop( "No names of the form w[0-9][0-9] were unused." ) I was playing around with your example and the following code works: every nn := ((0 to 1) || (0 to 9) | stop( "No names of the form w[0-9][0-9] were unused." )) do { exists( (downloadDir | targetDir | break) || "w" || nn ) } Owen Department of ICS | omalley@ics.uci.edu (ARPA) UC Irvine | http://www.ics.uci.edu/~omalley/ (WWW) Irvine, CA 92717 | ucbvax!ucivax!omalley (UUCP) From kwalker@sirtur.premenos.com Tue Dec 27 09:26:09 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Tue, 27 Dec 1994 10:33:28 MST Received: from gatekeeper.premenos.com by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA14327; Tue, 27 Dec 1994 10:33:18 MST Received: from localhost (smap@localhost) by gatekeeper.premenos.com (8.6.5/8.6.5) id JAA12653 for ; Tue, 27 Dec 1994 09:33:14 -0800 Received: from sirtur.premenos.com(150.105.100.47) by mail.premenos.com via smap (V1.3mjr) id sma012651; Tue Dec 27 09:33:04 1994 Received: by sirtur.sirtur.premenos.com (5.x/SMI-SVR4) id AA04590; Tue, 27 Dec 1994 09:26:09 -0800 Date: Tue, 27 Dec 1994 09:26:09 -0800 From: kwalker@sirtur.premenos.com (Ken Walker) Message-Id: <9412271726.AA04590@sirtur.sirtur.premenos.com> To: icon-group@cs.arizona.edu Subject: Re: DeMorgan's Law doesn't work X-Sun-Charset: US-ASCII > From: MENGARINI@news1.delphi.com (MENGARINI@DELPHI.COM) > > I needed to find the first filename of the form "w[0-9][0-9]" that was > not in use in either of 2 directories. This code > ( nn := (0 to 9) || (0 to 9) > , not exists( downloadDir || "w" || nn ) > , not exists( targetDir || "w" || nn ) > )|stop( "No names of the form w[0-9][0-9] were unused." ) > works, but the separation of the 2 "not exists" calls is reminiscent > of Algol-family languages' need to code things like > if importantNumber = 1 | importantNumber = 2 > where Snobol-family languages could just test whether > importantNumber = 1 | 2 > Analogously, Icon should be able to factor out the 2 "not exists" calls. > > But this > ( nn := (0 to 9) || (0 to 9) > , not exists( (downloadDir|targetDir) || "w" || nn ) > )|stop( "No names of the form w[0-9][0-9] were unused." ) > doesn't work because DeMorgan's Law doesn't work: > if downloadDir || "w" || nn doesn't exist, exists() fails, not exists() > succeeds, & the expression succeeds, without ever testing whether > targetDir || "w" || nn exists. The second example does work! When exists() fails, the alternation is resumed and the existance of the file in the other directory is tested. The following program shows that DeMorgan's Law holds in Icon: ********** Cut Here ********* # Demonstrate DeMorgan's Law using &null as false and 1 as true. # record pair(a,b) procedure main() local x # # Print truth tables. # write("A B (not A) & (not B) not (A | B)") write("------------------------------------------") every x := comb() do { writes(format(x.a), " ", format(x.b), " ") if ((not \x.a) & (not \x.b)) then writes("T") else writes("F") writes(" ") if not (\x.a | \x.b) then write("T") else write("F") } write() write("A B (not A) | (not B) not (A & B)") write("------------------------------------------") every x := comb() do { writes(format(x.a), " ", format(x.b), " ") if ((not \x.a) | (not \x.b)) then writes("T") else writes("F") writes(" ") if not (\x.a & \x.b) then write("T") else write("F") } end # # comb() - produce all 4 pairs of "logical" values. # procedure comb() suspend pair(1 | &null, 1 | &null) end # # Convert a "logical" value to "T" or "F". # procedure format(x) if \x then return "T" else return "F" end From jeffery@runner.jpl.utsa.edu Tue Dec 27 23:02:06 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Tue, 27 Dec 1994 22:09:36 MST Received: from runner.utsa.edu (runner.jpl.utsa.edu) by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA15924; Tue, 27 Dec 1994 22:09:34 MST Received: by runner.utsa.edu (5.0/SMI-SVR4) id AA26928; Tue, 27 Dec 1994 23:02:06 -0600 Date: Tue, 27 Dec 1994 23:02:06 -0600 From: jeffery@runner.jpl.utsa.edu (Clinton L. Jeffery) Message-Id: <9412280502.AA26928@runner.utsa.edu> To: jsampson@cix.compulink.co.uk () Cc: icon-group@cs.arizona.edu In-Reply-To: (jsampson@cix.compulink.co.uk) Subject: Re: Graphics for Windows Content-Length: 488 From: jsampson@cix.compulink.co.uk ("John Sampson") > Is anyone developing the graphics aspect of Icon to work on Windows - > the one that sits on top of MS-DOS, not X-Windows? A version is in alpha testing. It passes the basic graphics test; at present, I am looking into portability and interface issues. It was developed under Windows NT 3.1, and making those binaries run comfortably under regular Windows 3.1, or building some 16-bit binaries, is our necessary next step. From mslamm@pluto.mscc.huji.ac.il Wed Dec 28 16:07:53 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 28 Dec 1994 07:07:58 MST Received: from pluto.mscc.huji.ac.il by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA09657; Wed, 28 Dec 1994 07:07:51 MST Received: by pluto.mscc.huji.ac.il (AIX 3.2/UCB 5.64/4.03) id AA78312; Wed, 28 Dec 1994 16:07:53 +0200 Date: Wed, 28 Dec 1994 16:07:53 +0200 (WET) From: Zvi Lamm To: icon-group@cs.arizona.edu Subject: Truth-Table generator Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII I had a need to write a program to output truth tables for boolean expressions. I used the programmming language J (a sister of APL). The 'program' was about two lines long. I wrote a program for the same task in Icon. I include it below. This Icon solution is ugly (because of the programmer, not the language..), but works. I would be happy to hear comments. Any idea for improvemnet is welcome. I got alot of help on comp.lang.apl when writing the J version - so don't let me down! I think I will write a short note comparing the solutions. My idea is to show the way different languages shape your thought. Both J and Icon are rather special in that they give the programmer tools not found in other languages. Does this interest anyone? Any way, here goes: # # Truth-Table genertor Ver -1.0 # 12.1994 # procedure main() n:=2 m:=2 # number of expressions # every write(Outl(t:=Truth_Table(n)),"--> ",Expr(t)); # shows many expr to many truth-table lines every { #write(repl("-",2*n-1+1+4*m))# t:=Truth_Table(n) & #------------------------# write(" ") & #<-force line break when # writes(Outl(t)) & # backtracking # every writes(" | ",Expr(t)) #------------------------# } end procedure Truth_Table(n) # # generates lines (as lists) of the truth table for n variables # works, but is ugly # tabl:=list(n,0) every i:=0 to 2^n-1 do # all lines { j:=i; # convert number to bits k:=n; while (j > 0) do { tabl[k]:=j % 2; k:=k-1; j:=j / 2; } suspend tabl # return line } end procedure Expr(vec) # # evaluates a list of bits (the logical expr) # when multiple expr are suspended a mechanism in main prints them side by # side # suspend (ior(vec[1],vec[2]) | ixor(vec[1],vec[2])) end procedure Outl(vec) # # prints a list # local s; s:="" every x:=!vec do s:=s||x||" " return s end From nowlin@iwtqg.att.com Wed Dec 28 10:55:00 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 28 Dec 1994 09:57:10 MST Received: from gw1.att.com by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA17049; Wed, 28 Dec 1994 09:57:08 MST Received: from iwtqg.UUCP by ig1.att.att.com id AA08398; Wed, 28 Dec 94 11:54:57 EST Message-Id: <9412281654.AA08398@ig1.att.att.com> From: Jerry Nowlin To: icon-group@cs.arizona.edu (Icon News Group) Subject: Re: Truth-Table generator Original-To: att!cs.arizona.edu!icon-group (Icon News Group) Date: Wed, 28 Dec 94 10:55:00 CST Original-From: Jerry Nowlin X-Mailer: ELM [version 2.3 PL11] > I had a need to write a program to output truth tables for boolean > expressions. I used the programmming language J (a sister of APL). The > 'program' was about two lines long. I wrote a program for the same task > in Icon. I include it below. This Icon solution is ugly (because of the > programmer, not the language..), but works. I would be happy to hear > comments. Any idea for improvemnet is welcome. > > I got alot of help on comp.lang.apl when writing the J version - so don't > let me down! I think I will write a short note comparing the solutions. > My idea is to show the way different languages shape your thought. Both J > and Icon are rather special in that they give the programmer tools not > found in other languages. Does this interest anyone? > > Any way, here goes: It's Christmas break (unless you have a real job) and I figured why not try this. I worked with what you had. There were a few little things I cleaned up but the major flaw was not in the Icon. This program didn't work with n larger than 2. That's not an Icon problem but what the heck. It's been a while since I worried about boolean anything but I took a shot. I also made it possible to pass in a larger n to verify the changes worked. I didn't include the original program so dig up the earlier mail for comparison. Jerry Nowlin # Truth-Table generator Ver -1.0 # 12.1994 # procedure main(args) local n, t n := get(args) | stop("I need a 'n'") # every write(Outl(t:=Truth_Table(n)),"--> ",Expr(t)) # shows many expr to many truth-table lines every t:=Truth_Table(n) & write() & writes(Outl(t)) & every writes(" | ",Expr(t)) write() end procedure Truth_Table(n) # # generates lines (as lists) of the truth table for n variables # list concatenation can't be that efficient but it's simpler # if n = 0 then return [] suspend [0|1] ||| Truth_Table(n-1) end procedure Expr(vec) # evaluates a list of bits (the logical expr) # when multiple expr are suspended a mechanism in main prints them side by # side # # you need copies of the list since it's eaten at it's booled # suspend Lior(copy(vec)) | Lixor(copy(vec)) end procedure Lior(vec) if *vec = 1 then return get(vec) suspend ior(get(vec),Lior(vec)) end procedure Lixor(vec) if *vec = 1 then return get(vec) suspend ixor(get(vec),Lixor(vec)) end procedure Outl(vec) # # prints a list # local s s := "" every s ||:= !vec || " " return s end From swampler@noao.edu Wed Dec 28 11:15:39 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 28 Dec 1994 11:16:08 MST Received: from noao.edu by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA21060; Wed, 28 Dec 1994 11:16:07 MST Received: from orpheus.gemini.edu by noao.edu (4.1/SAG-Noao.G96) id AA13049; Wed, 28 Dec 94 11:16:05 MST; for icon-group@cs.arizona.edu Received: by orpheus.gemini.edu (5.0/SMI-SVR4-SAG03X) id AA15224; Wed, 28 Dec 1994 11:15:39 +0700 Date: Wed, 28 Dec 1994 11:15:39 +0700 From: swampler@noao.edu Message-Id: <9412281815.AA15224@orpheus.gemini.edu> Subject: Re: Truth-Table generator To: icon-group@cs.arizona.edu Content-Length: 1800 > I had a need to write a program to output truth tables for boolean > expressions. I used the programmming language J (a sister of APL). The > 'program' was about two lines long. I wrote a program for the same task > in Icon. I include it below. This Icon solution is ugly (because of the > programmer, not the language..), but works. I would be happy to hear > comments. Any idea for improvemnet is welcome. > > I got alot of help on comp.lang.apl when writing the J version - so don't > let me down! I think I will write a short note comparing the solutions. > My idea is to show the way different languages shape your thought. Both J > and Icon are rather special in that they give the programmer tools not > found in other languages. Does this interest anyone? Well, I managed to delete your original program, but here's one that's probably similar, using generators rather than vectors. Can it be adapted to your case? procedure main() local t1, t2 every (t1 := (0|1)) & (t2 := (0|1)) do { every writes(format ( t1 | t2 | # variables "|" | # separator iand(t1,t2) | ior(t1,t2) | # functions ixor(t1,t2) )) write() } end procedure format(t) # pretty up things for output, the 'wide' field width (5 characters) # would let this be used to produce a table header, as in: # # every writes(format("A" | "B" | "" | "A&B" | "A|B" | "A^B")) # write() # # though the above main program doesn't do so... # since this is a one-liner, it could be embedded in place of the call # above, but that would be ugly! return center(map(t, "01", "FT"), 5) end From mslamm@pluto.mscc.huji.ac.il Wed Dec 28 20:32:06 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 28 Dec 1994 11:32:20 MST Received: from pluto.mscc.huji.ac.il by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA21911; Wed, 28 Dec 1994 11:32:15 MST Received: by pluto.mscc.huji.ac.il (AIX 3.2/UCB 5.64/4.03) id AA50464; Wed, 28 Dec 1994 20:32:06 +0200 Date: Wed, 28 Dec 1994 20:32:06 +0200 (WET) From: Zvi Lamm To: swampler@noao.edu Cc: icon-group@cs.arizona.edu Subject: Re: Truth-Table generator In-Reply-To: <9412281815.AA15224@orpheus.gemini.edu> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII On Wed, 28 Dec 1994 swampler@noao.edu wrote: > > I had a need to write a program to output truth tables for boolean > > expressions. I used the programmming language J (a sister of APL). The > > 'program' was about two lines long. I wrote a program for the same task > > in Icon. I include it below. This Icon solution is ugly (because of the > > programmer, not the language..), but works. I would be happy to hear > > comments. Any idea for improvemnet is welcome. > > > > I got alot of help on comp.lang.apl when writing the J version - so don't > > let me down! I think I will write a short note comparing the solutions. > > My idea is to show the way different languages shape your thought. Both J > > and Icon are rather special in that they give the programmer tools not > > found in other languages. Does this interest anyone? > > Well, I managed to delete your original program, but here's one that's probably > similar, using generators rather than vectors. Can it be adapted to your case? > > procedure main() > local t1, t2 > > every (t1 := (0|1)) & (t2 := (0|1)) do { > every writes(format ( t1 | t2 | # variables > "|" | # separator > iand(t1,t2) | ior(t1,t2) | # functions > ixor(t1,t2) > )) > write() > } > > end > > procedure format(t) > > # pretty up things for output, the 'wide' field width (5 characters) > # would let this be used to produce a table header, as in: > # > # every writes(format("A" | "B" | "" | "A&B" | "A|B" | "A^B")) > # write() > # > # though the above main program doesn't do so... > # since this is a one-liner, it could be embedded in place of the call > # above, but that would be ugly! > > return center(map(t, "01", "FT"), 5) > > end > I rather wanted an all generator solution myself. But the problem is that my truth tables ma have more than two variables (t1 and t2, above). Now this makes it a bit harder to do it like this... Ehud From swampler@noao.edu Wed Dec 28 11:41:10 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 28 Dec 1994 11:41:39 MST Received: from noao.edu by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA22417; Wed, 28 Dec 1994 11:41:38 MST Received: from orpheus.gemini.edu by noao.edu (4.1/SAG-Noao.G96) id AA13719; Wed, 28 Dec 94 11:41:37 MST; for icon-group@cs.arizona.edu Received: by orpheus.gemini.edu (5.0/SMI-SVR4-SAG03X) id AA15285; Wed, 28 Dec 1994 11:41:10 +0700 Date: Wed, 28 Dec 1994 11:41:10 +0700 From: swampler@noao.edu Message-Id: <9412281841.AA15285@orpheus.gemini.edu> Subject: Re: Truth-Table generator To: mslamm@pluto.mscc.huji.ac.il Cc: icon-group@cs.arizona.edu Content-Length: 1301 You wrote: >>I rather wanted an all generator solution myself. But the problem is that >>my truth tables ma have more than two variables (t1 and t2, above). Now >>this makes it a bit harder to do it like this... If the number of variables is fixed, you can extend the code (though it starts getting uglier, fast): procedure main() every (t1 := (0|1)) & (t2 := (0|1)) & (t3 := (0|1)) do { every writes(format( t1 | t2 | t3 # variables "|" | # separator iand(t1,t2) | ior(t1,t2) | # functions ixor(t1,t2) | iand(t1, ior(t2,t3)) | ior(iand(t1,t2),iand(t1,t3)) )) write() } end There are tricks lying around to generalize to the 'n'th case with generators, but I've forgotten them! I was hoping someone would take the solution I mailed and generalize it... If I remember, the tricks were pretty ugly. I think I'd just brute force, but maybe change the above formatting slightly to: every (t1 := (0|1)) & (t2 := (0|1)) & (t3 := (0|1)) do {... -- Steve Wampler - swampler@gemini.edu [Gemini 8m Telescopes Project (under AURA)] -- The Gods that were smiling when you were born are laughing now. -- found in a fortune cookie From swampler@noao.edu Wed Dec 28 13:33:14 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 28 Dec 1994 13:33:44 MST Received: from noao.edu by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA27716; Wed, 28 Dec 1994 13:33:43 MST Received: from orpheus.gemini.edu by noao.edu (4.1/SAG-Noao.G96) id AA16684; Wed, 28 Dec 94 13:33:42 MST; for icon-group@cs.arizona.edu Received: by orpheus.gemini.edu (5.0/SMI-SVR4-SAG03X) id AA15462; Wed, 28 Dec 1994 13:33:16 +0700 Message-Id: <9412282033.AA15462@orpheus.gemini.edu> From: swampler@noao.edu Date: Wed, 28 Dec 1994 13:33:14 GMT+447 X-Mailer: Mail User's Shell (7.2.3 5/22/91) To: icon-group@cs.arizona.edu Subject: Re: Truth Tables... Content-Length: 2952 I think I understand more of what the original problem was (maybe someone could mail to me again)? I like Jerry Nowlin's solution. Here's a version of it, recast to use strings instead of lists (because I like strings more than lists - must be my SNOBOL4 background raising its head again). I think it differs from Jerry's solution in the definition of XOR on more than 2 values. See the comment in my code on this point. I am curious as to how logicians define it. ------- procedure main(args) local n, t n := integer(args[1]) | 2 every t := gen_truths(n) do { every writes(format( !t | # values "|" | # separator s_and(t) | s_or(t) | s_xor(t) # functions )) write() } end procedure format(s) return center(s, 5) end # Generate all permutations of a n-wide boolean variable set procedure gen_truths(n) if n > 0 then suspend ("F"|"T") || gen_truths(n-1) else return "" end # AND of an arbitrary number of values procedure s_and(t) return if upto('F',t) then "F" else "T" end # OR of an arbitrary number of values procedure s_or(t) return if upto('T',t) then "T" else "F" end # XOR of an arbitrary number of values # # This raises an interesting point, just *what is* the definition # of 'xor' with more than 2 arguments? This solution assumes # definition is 'exactly one TRUE', which is different than # an answer build up through iterative (or recursive) applications # of xor on two values at a time. I chose this definition # because with the other, xor isn't associative. Consider: # # Case 1: XOR(v1,v2,v3) <- (v1 xor v2) xor v3 # Case 2: XOR(v1,v2,v3) <- v1 xor (v2 xor v3) # Case 3: XOR(v1,v2,v3) <- s_xor(v1||v2||v3) {used here} # # with the call XOR(T,F,F) # # Case 1: produces T # Case 2: produces F # Case 3: produces T # # Cases 1 and 2 become stranger as the number of arguments increase. # One can produce a solution using Case 3 to mimic either Case 1 or # Case 2, anyway, e.g: # # s_xor(s_xor(v1||v2)||v3) # # What do real mathematicians use? What happens in 'J'? # procedure s_xor(t) return if i := upto('T',t) then { if upto('T',t,i+1) then "F" else "T" } else "F" end -- Steve Wampler - swampler@gemini.edu [Gemini 8m Telescopes Project (under AURA)] -- The Gods that were smiling when you were born are laughing now. -- found in a fortune cookie From kwalker@sirtur.premenos.com Thu Dec 29 08:56:04 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Thu, 29 Dec 1994 10:04:04 MST Received: from gatekeeper.premenos.com by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA21891; Thu, 29 Dec 1994 10:03:57 MST Received: from localhost (smap@localhost) by gatekeeper.premenos.com (8.6.5/8.6.5) id JAA22460 for ; Thu, 29 Dec 1994 09:03:51 -0800 Received: from sirtur.premenos.com(150.105.100.47) by mail.premenos.com via smap (V1.3mjr) id sma022458; Thu Dec 29 09:03:06 1994 Received: by sirtur.sirtur.premenos.com (5.x/SMI-SVR4) id AA05637; Thu, 29 Dec 1994 08:56:04 -0800 Date: Thu, 29 Dec 1994 08:56:04 -0800 From: kwalker@sirtur.premenos.com (Ken Walker) Message-Id: <9412291656.AA05637@sirtur.sirtur.premenos.com> To: icon-group@cs.arizona.edu Subject: Re: Truth Tables... X-Sun-Charset: US-ASCII I've been writing too much C and not enough Icon lately, so I decided it was time to have some fun. Below is a different variation on the theme of truth table generators. Ken Walker, kwalker@premenos.com Premenos Coporation, Concord, Ca. 94520 -------------------------------- Cut Here ----------------------------- # # This program takes as input on the command line a logical formula # containing variables and produces a truth table for the formula. # See below for the formula grammar. # # Ken Walker 12/29/94 # # The following records are nodes in the syntax tree of a formula. # record True() record False() record Not(a) record And(a,b) record Or(a,b) record Xor(a,b) global vars, var_set procedure main(a) local formula, parsed, symtab, max_var_len, formula_len # # parse the formula, putting the variables in the 'vars' list. # vars := [] var_set := set() formula := a[1] | stop("please give a formula on the command line") formula ? { parsed := expr() pos(0) | stop("invalid formula") } # # compute some lengths for formating output # formula_len := 5 formula_len <:= *formula max_var_len := 6 every max_var_len <:= *!vars # # output header line with variable names and formula # write() every writes(center(!vars, max_var_len + 1)) writes(" | ") write(center(formula, formula_len)) write(repl("-", *vars * (max_var_len + 1) + 3 + formula_len)) # # compute and print each set of variable assignments and formula # results # symtab := table() every assign_bool(vars, symtab) do { every writes(center(type(symtab[!vars]), max_var_len + 1)) writes(" | ") write(center(type(eval(parsed, symtab)), formula_len)) } end # # For each variable in a list, assign boolean values in a symbol # table. Boolean values are represented by True and False records. # This is a recursive generator producing all combinations of # assignments. # procedure assign_bool(vars, symtab) local var if *vars == 0 then return # all variables are assigned var := vars[1] # variable this call assigns to vars := vars[2:0] # rest of variables symtab[var] := True() suspend assign_bool(vars, symtab) symtab[var] := False() suspend assign_bool(vars, symtab) end # # Evaluate the parsed formual, using the boolean assignments to variables # in symtab. Return a True record or a False record. # procedure eval(parsed, symtab) case type (parsed) of { "string": return symtab[parsed] "True" | "False": return parsed "Not": if type(eval(parsed.a, symtab)) == "True" then return False() else return True() "And": if type(eval(parsed.a, symtab)) == "True" & type(eval(parsed.b, symtab)) == "True" then return True() else return False() "Or": if type(eval(parsed.a, symtab)) == "True" | type(eval(parsed.b, symtab)) == "True" then return True() else return False() "Xor": if type(eval(parsed.a, symtab)) ~== type(eval(parsed.b, symtab)) then return True() else return False() } end # # primative parser for grammar: # # ::= | # and | # or | # xor | # # ::= true | # false | # | # | # ( ) # procedure expr() local e e := term() repeat { skip_whsp() if ="and" then { e := And(e, term()) } else if ="or" then { e := Or(e, term()) } else if ="xor" then { e := Xor(e, term()) } else return e } end procedure term() local t static ident_chars initial ident_chars := &letters ++ &digits ++ '_' skip_whsp() if ="(" then { t := expr() skip_whsp() if not =")" then stop("missing ')'") return t } else if ="not" then return Not(term()) else if ="true" then return True() else if ="false" then return False() else if t := tab(many(ident_chars)) then { if not member(var_set, t) then { insert(var_set, t) put(vars, t) } return t } else stop("invalid formula") end procedure skip_whsp() static white_sp initial white_sp := ' \t' tab(many(white_sp)) end From icon-group-request Thu Dec 29 21:43:13 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Thu, 29 Dec 1994 16:30:16 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA12674; Thu, 29 Dec 1994 16:30:14 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id OAA27888; Thu, 29 Dec 1994 14:33:22 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: Thu, 29 Dec 1994 21:43:13 +0000 From: Nic@skin.demon.co.uk (Nic Gibson) Message-Id: <788737393snz@skin.demon.co.uk> Sender: icon-group-request@cs.arizona.edu Reply-To: Nic@skin.demon.co.uk Subject: MS-DOS Icon and Ctrl C Just a quick thought/query. Has anyone got a suggestion that would allow me to handle ^C keypresses directly? I've putting together an interactive program that really could use the ability to read ^C as input, do some stuff and then quit. Any suggestions short of modifying the iconx source gratefully received. Cheers, Nic From TENAGLIA@MIS.MCW.EDU Fri Dec 30 06:45:22 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Fri, 30 Dec 1994 05:43:20 MST Received: from adm.mis.mcw.edu by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA24929; Fri, 30 Dec 1994 05:43:18 MST Received: from mis.mcw.edu by mis.mcw.edu (PMDF V4.3-7 #5595) id <01HL8U5S02G08WW8L6@mis.mcw.edu>; Fri, 30 Dec 1994 06:45:22 CST Date: Fri, 30 Dec 1994 06:45:22 -0600 (CST) From: Chris Tenaglia | 456-8765 Subject: Re: MS-DOS Icon and Ctrl C To: Nic@skin.demon.co.uk Cc: icon-group@cs.arizona.edu Message-Id: <01HL8U5S1OBM8WW8L6@mis.mcw.edu> Organization: Medical College of Wisconsin (Milwaukee, WI) X-Vms-To: IN%"Nic@skin.demon.co.uk" X-Vms-Cc: IN%"icon-group@cs.arizona.edu" Mime-Version: 1.0 Content-Type: TEXT/PLAIN; CHARSET=US-ASCII Content-Transfer-Encoding: 7BIT What version are you using? ^C functionality seemed to change after version 8.5. So if you're using V8.10 or V9.0 try going back to V8.5 and see if that does it. If you're 8.5 or earlier, try a later version. In DOS there is also BREAK ON and BREAK OFF which seem to control the way ^C is passed to a program. I have a password program that has to stay at V8.5 because of this. Chris Tenaglia (System Manager) | "The past explained, Medical College of Wisconsin | the future foretold, 8701 W. Watertown Plank Rd. | the present largely appologized for." Milwaukee, WI 53226 | Organon to The Doctor tenaglia@mis.mcw.edu > Just a quick thought/query. > Has anyone got a suggestion that would allow me to handle ^C keypresses > directly? I've putting together an interactive program that really could use > the ability to read ^C as input, do some stuff and then quit. Any suggestions > short of modifying the iconx source gratefully received. > Cheers, > Nic From icon-group-request Fri Dec 30 23:52:14 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Fri, 30 Dec 1994 19:30:26 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA07209; Fri, 30 Dec 1994 19:30:25 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id RAA10500; Fri, 30 Dec 1994 17:27:12 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: 30 Dec 1994 23:52:14 GMT From: todd.nathan@mccaw.com (Todd Nathan) Message-Id: <3e26fe$b0d@ftp-p.mccaw.com> Organization: McCaw Cellular Communications, Inc. Sender: icon-group-request@cs.arizona.edu Subject: Building for ICON for NS 3.3 Hello there folks. Been trying to build the ICON distribution from arizona state on NS 3.3 Intel. If anyone could help I would appreciate it. The following output is from the attempt. I copied the next config directory, and put the i386_linux rswitch.c into it to replace the m68k rswitch code. Was told this should work, but i get the following. Please respond to me via email since this is not too much of a public issue to discuss. Happy New Year! Todd PS. Got the distribution twice to make sure it was not corrupted. Also tried the rswitch.c from i486_linux also. ------------- output from the build attempt ----------- learfan> cp -r next i486_next learfan> cp i386_linux/rswitch.c i486_next learfan> ../.. learfan> make Configure name=i486_next make Clean cd docs; make Clean rm -rf *.bak cd ipl; make Clean rm -f *.bak cd src; make Clean cd iconc; rm -f *.o iconc cd common; rm -f *.o cd preproc; rm -f *.o pp cd rtt; rm -f *.o rtt cd runtime; rm -f *.c *.o rt.db rt.a rttcur.lst rttfull.lst iconx cd icont; rm -f *.o icont iconx.hdr hdr.h newhdr cd xpm; rm -f *.o *.a touch h/define.h cd tests; make Clean cd bench; make Clean rm -f *.out concord-[ct] deal-[ct] ipxref-[ct] queens-[ct] rsg-[ct] *.u? cd calling; make Clean cd extcall; make Clean rm -f *.o cd loadfunc; make Clean rm -f *.o *.so *.out so_locations btest rm -f foo cd general; make Clean rm -f local/* touch local/.placeholder cd graphics; make Clean rm -f foo cd ipl; make Clean rm -f local/* cd preproc; make Clean cd samples; make Clean rm -f local/* touch local/.placeholder cd special; make Clean rm -f keyboard save cd vtran; make Clean rm -rf vt rm -f tests/local/* cat config/unix/i486_next/vtran.hdr config/unix/Config/vt3.make >config/unix/Config/Makefile cp config/unix/Common/Makefile config/unix/i486_next cd config/unix/i486_next; make make -f ../Config/Makefile Setup make -f ../Config/Makefile Clean rm -f ../../../src/common/rswitch.[csS] make -f ../Config/Makefile Localcode cp define.h ../../../src/h cp rswitch.[csS] ../../../src/common if grep -s NoRanlib define.h; then touch ../../../NoRanlib; else rm -rf ./../../NoRanlib; fi make -f ../Config/Makefile Makefiles cat rtt.hdr ../Config/rtt.make > ../../../src/rtt/Makefile cat common.hdr ../Config/common.make > ../../../src/common/Makefile cat iconc.hdr ../Config/iconc.make > ../../../src/iconc/Makefile cat preproc.hdr ../Config/preproc.make > ../../../src/preproc/Makefile cat icont.hdr ../Config/icont.make > ../../../src/icont/Makefile cat runtime.hdr ../Config/runtime.make > ../../../src/runtime/Makefile cat vtran.hdr ../Config/vt2.make > ../../../src/vtran/Vtmake2 cp ../Config/vt1.make ../../../src/vtran/Vtmake1 make -f ../Config/Makefile VT rm -f icon_vt.c ln ../Config/icon_vt.c icon_vt.c cc -E icon_vt.c | egrep -v '(^#|^$)' > ../../../bin/icon_vt ./Config/icon_vt.h:1: illegal external declaration, missing `;' after `/me/languages/icon/bin/' ./Config/icon_vt.h:2: illegal external declaration, missing `;' after `Setting' ./Config/icon_vt.h:2: illegal external declaration, missing `;' after `structure' ./Config/icon_vt.h:2: undefined type, found `variant' ./Config/icon_vt.h:2: illegal external declaration, missing `;' after `translator' ./Config/icon_vt.h:4: undefined type, found `common' ./Config/icon_vt.h:5: illegal external declaration, missing `;' after `itran' ./Config/icon_vt.h:6: undefined type, found `h' ./Config/icon_vt.h:7: illegal external declaration, missing `;' after `rm' ./Config/icon_vt.h:7: illegal method definition, found `$CommonDir' ./Config/icon_vt.h:2: illegal method definition, missing `{' after `icon_vt.c' *** Exit 1 Stop. From icon-group-request Sat Dec 31 09:32:36 1994 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Sat, 31 Dec 1994 04:30:29 MST Received: from agate.Berkeley.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP id AA02500; Sat, 31 Dec 1994 04:30:26 MST Received: by agate.berkeley.edu (8.6.8.1/1.33) id CAA22674; Sat, 31 Dec 1994 02:30:20 -0800 Received: from GATEWAY by agate with netnews for icon-group@cs.arizona.edu (icon-group-l@cs.arizona.edu) To: icon-group-l@cs.arizona.edu Date: 31 Dec 1994 09:32:36 GMT From: Will Mengarini Message-Id: <3e38fk$4is@news.halcyon.com> Organization: Northwest Nexus Inc. Sender: icon-group-request@cs.arizona.edu References: <788737393snz@skin.demon.co.uk> Subject: Re: MS-DOS Icon and Ctrl C Nic@skin.demon.co.uk (Nic Gibson) writes: >Has anyone got a suggestion that would allow me to handle ^C keypresses >directly? I've putting together an interactive program that really could use >the ability to read ^C as input, do some stuff and then quit. Any suggestions >short of modifying the iconx source gratefully received. This procedure main(arg) writes( "Input a char: " ) c := getche(); write(); write( "c: ", image(c) ) end works for me, with Icon 8.8 for MS-DOS; both ^C & ^Break are echoed as the charset's graphic for Ascii ^C, then the program continues. Note that non-Ascii keystrokes like Alt-whatever will generate 2 getch{,e}() returns, the first null; if you use getch{,e}() you'll probably want to allow for that. Will Mengarini In a profound sense, we are ultimately all from Delphi "Walking is a prescribed health activity, buddy. If you go unsupervised, without a prescription, & then you get yourself in trouble, who gets the rap? The city does. So you got to have that prescription. Did you know that almost all auto damage involving auto-pedestrian accidents results from non-prescription walking?" --from a Mark Rich story in the Nov 94 /Analog Science Fiction & Fact/