dorai@titan.rice.edu (Dorai Sitaram) (11/20/89)
Mark, I have cross-posted to comp.lang.scheme. If there is lack of interest in comp.lang.prolog (since I have digressed from the subject-line "Fun. vs. Logic"), you may consider restricting distribution to comp.lang.scheme. Here goes... In article <11610@phoenix.Princeton.EDU> markv@phoenix.Princeton.EDU (Mark T Vandewettering) writes: >In article <11500018@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) writes: >>These detract from the >>value of a Prolog program as a mathematical specification. The only impure >>constructs I've seen in functional programming are exceptions and >>destructive assignment, and these are very rarely used. > >AIIIGH! The horror! ASSIGNMENT? > >Exceptions are not necessarily a non-functional construct, it is >relatively simple to design a moderately effective exception handling >mechanism if you adopt a language in which continuations are first >class. > >Destructive assigment is an atrocity, and totally against the spirit of >functional programming, neatly messing up lots of nice properties. I am >for a language without the crutch of assignment. I have two questions for you, as I consider both continuations and assignment imperative, i.e., extrafunctional features. (I use "extrafunctional" non-pejoratively, since I have been caught using said features without qualms. :-]) @ Why are exceptions (and continuations) "not necessarily non-functional"? I'd like to know the metric you use to judge "functionalness." @ If, by your definition of "functionalness," continuations turn out to be functional, then why are assignments denied the same privilege? In other words, what are the nice properties of "functionalness" that are violated by assignment but preserved by adding first-class continuations. (I concur with you that continuations and assignment affect a functional language in remarkably different ways: which is but natural, since they are two distinct extensions to the base language.) >... >Two features of Prolog are particularly outstanding: backtracking, and >logic variables. ... > >Each family have interesting strengths, and provide a rich environment >for future research. In particular, I believe these two families >provide the most hope for effective parallel implementation. It is probably only moderately well-known that a functional language with extrafunctional facilities like assignment and continuations can fairly easily embed (note: "embed" is better than "model") a logic programming language with extralogical facilities such as Prolog. The literature on this subject (i.e., embedding only, _not_ suggested combinations of log+fun, which are rife) is confined to two short but interesting papers, one by Chris Haynes and the other by Matthias Felleisen, and probably one by Srivastava, Oxley & Srivastava which I haven't seen. It might be interesting to see if the gulf has been bridged from the other side, i.e., embedding (functional + assignment + continuations) in a (logic + cut) language. --dorai -- ------------------------------------------------------------------------------- It may be that the gulfs will wash us down; It may be we shall touch the Happy Isles. -------------------------------------------------------------------------------
markv@phoenix.Princeton.EDU (Mark T Vandewettering) (11/20/89)
In article <3055@brazos.Rice.edu> dorai@titan.rice.edu (Dorai Sitaram) writes: My claim originally was: >>Exceptions are not necessarily a non-functional construct, it is >>relatively simple to design a moderately effective exception handling >>mechanism if you adopt a language in which continuations are first >>class. Imagine all applications have not just and operator and an operand, but also a continuation. The result of application is the result of applying the continuation to the result of applying the operator to the operand. This is the basic notion of a continuation passing language. What particular feature of this is non-functional? The flow of control is a bit more convoluted, and analysis of such programs may be more difficult, but I fail to see any reason to toss out such constructs. Continuations are no more complicated or unfunctional that higher order functions. My formal background is weak however. Anyone else have some good ideas? >@ If, by your definition of "functionalness," continuations turn out to > be functional, then why are assignments denied the same privilege? Assignments destroy potential parallelism by introducing context dependance. A simple substitution semantics provides a wide variety of sites where expression reduction might occur. The only requirement is that all inputs to a (strict) function be present before application can begin. When assignment is allowed, potential parallelism is lost because the meaning of the program changes dependant on the current value of the variable. Referential transparency is a very useful property. I have been informal in my description of what I perceive to be as a functional language. Roughly, I would say that something evaluated according to a simple substitution style semantics would be functional. It is my belief that continuations can be well understood in this framework. I would like to hear examples or counterexamples of course. Mark
gateley@m2.csc.ti.com (John Gateley) (11/21/89)
In article <11632@phoenix.Princeton.EDU> markv@phoenix.Princeton.EDU (Mark T Vandewettering) writes: >My formal background is weak however. Anyone else have some good ideas? >[on why continuations are non-functional] I have seen a combination of continuations and letrec (I'm using Scheme) which created an object with state (i.e. non-referentially transparent). I didn't look at it closely enough to determine if it was because of the implementation of letrec (which uses side effects), or the definition (based on Y). John gateley@m2.csc.ti.com