brunjes@kadsma.kadsm (Roy Brunjes) (09/14/88)
I have seen several postings lately talking about functional programming and how suitable Forth is for that. My question is, I hope, more simple. What IS functional programming? Hopefully it is not as vague as some other concepts, such as 4GL's (to name one). Roy Brunjes ...rochester!kodak!kadsma!brunjes Disclaimer: My opinions only, blah blah.
bts@sas.UUCP (Brian T. Schellenberger) (09/23/88)
In article <180@kadsma.kadsm> brunjes@kadsma.UUCP (Roy Brunjes) writes: |I have seen several postings lately talking about functional programming and |how suitable Forth is for that. My question is, I hope, more simple. What |IS functional programming? Functional program is where you program without side effects. That is, whenever you call something, it only returns information and does not set global variables and so on. It is most commonly associated with LISP. In most languages, it is bloody awkward because returning multiple values is awkward or impossible. In FORTH it's easy--in fact, setting global variables is what's relatively awkward in FORTH. -- --Brian, __________________________________________________ the man from |Brian T. Schellenberger ...!mcnc!rti!sas!bts Babble-On |104 Willoughby Lane work: (919) 467-8000 x7783 ____________________________|Cary, NC 27513 home: (919) 469-9389
Paktor@cup.portal.com (10/04/88)
In article <1015.3.219.2 Re: Functional Programming> <9/22/88 16:21 bts@sas.UUCP (Brian T. Schellenberger)> writes, referring to functional programming: > In most languages, it is bloody awkward because returning multiple values > is awkward or impossible. In FORTH it's easy--in fact, setting global > variables is what's relatively awkward in FORTH. To the latter assertion, I reply: Au contraire, mon frere; setting global variables in Forth is just as piece-of-cakey as pie. For a ready example, consider the variable, STATE , commonly used in most Forth implementations to distinguish between when the outer interpreter is compiling, and when it is actively interpreting. It is set by : (the colon-word which starts a definition), cleared by ; (the semi-colon word which ends a definition), and used by the word INTERPRET , which is the essence of the outer interpreter... Another handy example is the subtle use of the variable DPL (Decimal-PLace), which is used by NUMBER when interpreting a number that has a decimal point in it, in many Forth implementations. The number is then expanded to a two-cell number-pair, equivalent to the number as if it had no dec- imal point; the value of DPL is then the only thing that indicates the true magnitude of the number as originally entered. If the number had no decimal point, then DPL is set to -1. Other examples of global variables whose values are set within words that per- form other functions can be found both in the elementary Forth implementa- tion and in myriad applications... David ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ === Mister Systems === | "You know the times David L Paktor | you impress me the most | are the times when you don't try; Paktor@cup.Portal.com | when you don't even try." -- Joni M. | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sean@lfcs.ed.ac.uk (Sean Matthews (AI)) (10/08/88)
In article <628@sas.UUCP> bts@sas.UUCP (Brian T. Schellenberger) writes: >In article <180@kadsma.kadsm> brunjes@kadsma.UUCP (Roy Brunjes) writes: >|I have seen several postings lately talking about functional programming and >|how suitable Forth is for that. My question is, I hope, more simple. What >|IS functional programming? > >Functional program is where you program without side effects. That is, >whenever you call something, it only returns information and does not >set global variables and so on. It is most commonly associated with LISP. It is rather more than that in most cases. Most good functional programming languages are a lot more flexible than lisp (unless you think of scheme--- and even there only by pushing *hard*). Yes, basically a functional programming language is one without side effects, but people who use them associate them at least as much with what are called higher order functions; i.e., a functional programming language does not treat a piece of code any differently from any other data object (apart from the obvious distinctions---equivalence on functions is not decidable, for instance). The provenance of Fuctional programming languages is therefore the same as Lisp --- lambda calculus and combinatory logic, but they share very little to nothing today. a very small example: if we define the fuctions inject and map: inject f terminal nil = terminal; inject f terminal [head|tail] = f head (inject terminal tail). map f nil = nil; map f [head|tail] = [(f head)|(map f tail)]. then it is possible to write a lot of powerful functions in one line. sum = inject plus 0. prod = inject times 1. inc = plus 1. inc-list = map inc. are two simple examples, then we can say: sum [1 2 3] = 6. prod [1 2 3] = 6. inc 1 = 2. inc-list [1 2 3] = [2 3 4]. or more complex: length list = sum (map \x.1 list). /* \x.foo is a function lambda abstracted on x */ then: length [1 2 3 4 5] = 5. the strength of functional programming languages is in the simplicity, once you grasp the idiom, of programs, especially where very complex programs are being written. The point is rather lost in these short examples (it is possible using a standard set of higher order functions--- like map and inject---to write a lot of algorithms with *no* explicit control structure. I can write quicksort in two lines. They are very good for prototyping and for one off progams. They are one popular suggestion for a suitable style of language for very parallel computers. They are very bad where a lot of calculation has to be done or when the program is mostly i/o. Having said this I once used a functional programming language as a specification language rather than as a programming language and described a simple full screen editor in about 100 lines. (it was a bity slow but it did clear up a lot of problems that would otherwise only have come to light *much* later). If you want to get some idea of what they involve then I suggest you try the ML programming book in Prentice Hall International (the series edited by Tony Hoare). And for a description of a particulary radical language, John Backus's ACM Turing lecture (I cant remember the title, it is something like: `can programming be liberated from the Von Neumann bottle neck'. The best fuctional programming language I know is standard ML, (the fact that it was invented here is of course irrelevant), unfortunately the compliler I use, which is *very* fast needs a sun-3 with approx 16meg of real memory to work properly so is is not going to move into the forth community in the immediate future. (ML is essentially a syntactically sugared version of the typed lambda calculus with lots of bells and whistles). As for forth as a fuctional programming language, forget it. This would be like OOprogramming in Fortran, it could I suppose be done, the language does have a stack, but the effort would not repay itself. After all you can do fuctional programming on a Turing Machine, all it would involve would be a little programming to prepare the ground. I do not subscribe to this group, I fell into this discussion while browsing so if you object violently to any of the above mail me at home. Se\'an.
orr@cs.glasgow.ac.uk (Fraser Orr) (10/11/88)
In article <9714@cup.portal.com> Paktor@cup.portal.com writes: > >In article <1015.3.219.2 Re: Functional Programming> > <9/22/88 16:21 bts@sas.UUCP (Brian T. Schellenberger)> > writes, referring to functional programming: > >> In most languages, it is bloody awkward because returning multiple values >> is awkward or impossible. In FORTH it's easy--in fact, setting global >> variables is what's relatively awkward in FORTH. > >To the latter assertion, I reply: Au contraire, mon frere; setting global > variables in Forth is just as piece-of-cakey as pie. Indeed you are correct. Of course, the inability to return multiple values in most programming languages is merely a deficiency in the syntax of that language. I see no reason why it cannot be done (moreover why it cannot be done in a type secure manner.) I might also say that provision is made for this in Miranda (and other Functional languages') syntax. I might say that altough seting and using global variables is not as easy as the use of the stack in forth (though as David Paktor points out it isn't really that hard), I find the original poster's self righteous attitude ammusing. He seems to imply that when forth was designed they decided that they would make global access deliberately more dificult to discourage it. In reality though it is clear that global variables were added as a "useful" hack. >David Regards, ===Fraser
UNBCIC@BRFAPESP.BITNET (03/26/91)
> I am glad that you have said this. I don't like to be picky, but I do > want to say that it was kind of confusing to start your previous message > with "hehehe, I'll show you that you are wrong". Sorry. My intention was to show that your arguments were not new. Just that. > These are the examples I suggested. However, the fact that these > examples arose in the context of functional programming does not mean > that they ARE functional programming. I didn't want to say that they ARE functional programming. I'm saying, instead, that they are PART of functional programming. > If you claim that these examples ARE "the functional paradigm", then Since I don't claim this... > you cannot make the statement that these are "operators to improve > functional programming." You must instead claim that these are > operators necessary for the implementation of functional programming. Sorry. Better wait and bring you all the reference. > I. We show that the functional paradigm does not imply the style I suggest. > > The following Scheme function: > (define (factorial n) > (if (= n 1) > 1 > (* n (factorial (- n 1))))) > is functional, since it does not make any assignments. However, it is > not written in the style I suggest. That would look like: > (define (factorial n) > (accumulate * 1 (enumerate-interval 1 n))) The first example is a poor use of functional programmi~rng. Yes, it avoids side effects, but that's not all we want to do. Yes example is a true functional program. That's why I claim what you suggest is functional programming. > Part II is important because it means we can program without explicit > control structures in a language like Forth without first making Forth > a functional language. I am also planning on using this style in C. Nothing is pure. You are pressuposing that anything that, by one way or other, have non-functional elements is non-functional. Then, almost everything is nothing. Right? > This is an interesting example, but I hope you understand that it is > not actually in the style I suggest, and so I will not be pursuing it. If you can program without any IFs, ok. I was suggesting a better structure to use instead of IFs, if you don't like IFs. > Adam (8-DCS) Daniel C. Sobral UNBCIC@BRFAPESP.BITNET
UNBCIC@BRFAPESP.BITNET (03/29/91)
First, the references relating Dijkstra (sometimes mispelled) and Functional
Programming were wrong. The correct is John Backus. Other references, including
guarded-commands, were right.
Second, as my poor knowledge of english language makes impossible to me to
continue the discussion, I'll just give the references.
J. Backus. "Programming Language Semantics and Closed Applicative Languages"
Conf. Record ACM Symp. on Principles of Programming Languages (Boston, Oct.
1973): 71-86.
J. Backus. "Can Programming Be Liberated from the von Neumann Style? A
Functional Style and Its Algebra of Programs." Comm. ACM 21 8 (Ago. 1978):
613-641.
(8-DCS)
Daniel C. Sobral
UNBCIC@BRFAPESP.BITNET