ronny@cs.kun.nl (Ron Wichers Schreur) (06/14/91)
Version 0.7 of the Concurrent Clean System is now available for the Macintosh and the Sun3. It is distributed free for educational and research purposes and can be obtained by anonymous FTP from phoibos.cs.kun.nl (131.174.81.1) from the directories pub/Clean/CleanMac and pub/Clean/CleanSun3. If you don't have FTP-access, we can send you a copy by e-mail. The article attached to this message briefly describes the functional programming language Concurrent Clean and the Concurrent Clean System application for the Macintosh. If you download the Concurrent Clean System, please let us know. We would like to keep track of who is using our system. Please send inquiries about the Concurrent Clean System to clean@cs.kun.nl. Ron Wichers Schreur (ronny@cs.kun.nl) ------------------------------------------------------------------- The Concurrent Clean System - Functional Programming on the Macintosh M.J. Plasmeijer, M.C.J.D. van Eekelen, E.G.J.M.H. Nocker, J.E.W. Smetsers, University of Nijmegen Department of Computer Science Toernooiveld 1 6525 ED Nijmegen E-mail: clean@cs.kun.nl. Functional programming languages Functional programming languages are general purpose, highlevel languages based on the mathematical notion of functions. A functional program consists of a set of (possibly recursive) function definitions. The execution of a program consists of the evaluation of an indicated function application. Programs written in a functional language are generally very compact and also very elegant. This is mainly due to the availability of pattern matching, guards and higher-order functions. Modern functional languages use lazy evaluation which means that expressions are only evaluated when their values are actually needed in a calculation. This makes it possible to define infinite data structures. A programmer never has to worry about memory management or pointers. There is no assignment statement. As a consequence, there are no side-effects possible such that one can reason about functional programs using traditional mathematical proof techniques like induction and symbolic substitution. The expressive power is the same as with ordinary languages such as C. Another property of a functional program is that the order in which functions are evaluated cannot change the outcome of a computation. This makes functional programs also very suited for parallel execution. For all these reasons an increasing number of universities use functional languages in introductory programming courses. Functional languages are also very suited for rapid prototyping. A disadvantage of functional languages was that programs ran very, very slow and that they consumed a large amount of memory. At several universities much attention has been paid to improve the compilation techniques which has led to good compilers for several languages (Hope (Burstall et al. 1980), Lml (Johnson (1984), Haskell (Hudak et al. (1990)). However, good compilers for personal computers such as the Macintosh were not available until now. Concurrent Clean The University of Nijmegen developed Concurrent Clean: (Brus et al. (1987), Nocker et al. (1991)) an experimental, higher order lazy functional programming language suited for evaluation on a range of computer architectures varying from personal computers to parallel machine architectures. The most important features of Concurrent Clean are: * It is a lazy and purely functional programming language based on Term Graph Rewriting (Barendregt et al. (1987)). * It is a strongly typed language (based on the well-known Milner (1978) type inferencing scheme) including polymorphic types, abstract types, algebraic types and synonym types, as well as basic types (integers, reals, characters, booleans, strings, lists, tuples and files). * It has a module structure with implementation modules and definition modules offering a facility to implicitly and explicitly import definitions from other modules; it includes predefined modules (libraries) for basic operations (delta rules) on objects of basic types. Example of a Concurrent Clean program: the definitions of the factorial function and the function Map: IMPLEMENTATION MODULE example ; IMPORT delta ; RULE :: Fac INT -> INT ; Fac 0 -> 1 | Fac n -> *I n (Fac (--I n)) ; :: Map (=> x y) [x] -> [y] ; Map f [] -> [] | Map f [a|b] -> [f a|Map f b] ; :: Start -> [INT] ; Start -> Map Fac [2,3,4] ; In this program the factorial function is applied to each element of the list [2,3,4]. Each function definition, optionally preceded by a type specification, consists of a number of alternatives. Square brackets are used for denoting lists: [] is an empty list, [a|b] denotes a list consisting of a list b prefixed with an element a. The example also shows the use of higher order functions such as Map. Types of higher order functions are specified using => (prefix notation) which corresponds to -> (infix notation) as used in most other functional languages. In the example the predefined functions being used (integer multiplication (*I) and decrement (--I)) are imported with one simple import statement. * Annotations can be added to a function definition. With these annotations the evaluation order can be controlled by the programmer: functions can be made (partially) strict instead of lazy. When a function is known to be strict in a certain argument, the argument can be evaluated before the function is called. Such functions are in general more efficient. Further speed-ups can be obtained by defining (partially) strict data structures (Nocker & Smetsers (1990)). It is also possible to split up the execution of the program in parts that are to be evaluated interleaved or in parallel. Processes can be created dynamically with arbitrary process topologies (for instance cyclic structures). The communication between processes does not have to be explicitly defined but is handled automatically. The sending and receiving of information between processes is not explicitly defined but handled automatically. Example to show how divide-and-conquer parallelism can be specified in Concurrent Clean: MODULE dfib ; IMPORT delta ; RULE :: Start -> INT ; Start -> DFib 22 ; :: Threshold -> INT ; Threshold -> 15 ; :: DFib INT -> INT ; DFib n -> IF (<=I n Threshold) (Fib n) (PFib n) ; :: Fib INT -> INT ; Fib 1 -> 1 | Fib 2 -> 1 | Fib n -> +I (Fib (-I n 1)) (Fib (-I n 2)) ; :: PFib INT -> INT ; PFib n -> +I ({P} DFib (-I n 1)) (DFib (-I n 2)); The {P} annotation in the definition of the function Pfib means that the corresponding call of Fib has to be evaluated in parallel. This function application is sent to another processor for evaluation. The father process will continue with the calculation of the other call of Fib after which it will wait until the results of parallel calculation are copied back such that addition can take place. The Concurrent Clean System The Concurrent Clean System is especially designed for the Macintosh following the Mac's user interface philosophy. The current version of the system (version 0.7) contains: * A Macintosh program development environment including a project manager and a simple text-editor. * A fast code generator for the Mac (both 68000 as 68020). Due to special compilation techniques, such as automatic strictness analysis (Nocker (1988)), the code generator is one of the best for functional programming languages currently available (over 1.000.000 function calls per second on a Mac-fx, see Table 1). Clean Clean Clean Clean Clean(u!) Lml Hope C MacIIfx MacIIsi Mac+ Sun3 Sun3 Sun3 Sun3 Sun3 nfib 2.6 5.2 53 4.5 4.5 25 5.4 11 tak 2.6 5.3 53 4.9 4.9 40 7.2 11 sieve 4.4 9.4 260 8.1 6.8 25 9.1 4.5 queens 15 41 240 28 14 62 16 4.1 reverse 31 63 620 64 50 110 65 -- twice 0.86 1.8 OutOfHeap 1.7 0.5 SegFault 0.3 -- rnfib 6.1 13 2000 11 11 26 33 19 fast 14 30 OutOfHeap 34 19 OutOfHeap OutOfHeap 9 fourier Table 1. Concurrent Clean compared with other well-known implementations using some standard benchmarks (nfib 30, tak 24 16 8, sieve 10000, queens 10, reverse 3000, twice 4 incr, rnfib 26.0 using reals, fastfourier on 8K complex numbers). The first three columns give the speed figures measured on different Macs using a 2Mb heap (only 1Mb for the Mac+). All times are in seconds. To make a proper comparison possible all programs are also tested on a SUN3/280, M68020 processor on 25Mhz clock, 2Mb heap. In Clean (u!) strictness annotations are added by the programmer. Lml is a lazy functional language, Hope is a non-lazy functional language and C is a non-lazy non-functional language. * A linker is included that can generate stand-alone Mac applications. They can also be sub-launched from the Clean system. There is an option to generate assembly code for the Mac as well as for the Sun3. * An interpreter is included that can simulate the execution of parallel programs; it includes facilities for tracing and debugging. * The interpreter can produce several kinds of statistical information about the simulated behaviour of parallel execution. With an additional application especially designed for the Mac this information can be graphically displayed and the run-time behaviour can be examined. The Pfib example above executed by the simulator simulating a parallel machine with 9 processors produces the following results: ** Note (Ron Wichers Schreur) ** ** The following graph is an approximation of the ** ** one in the original paper. ** #active processors |____________________________________________ 8| |__ | |_ 6| |__ | | 4| | | |__ 2| | | | 0|_____________._____________._____________._____________.___|_ 0 10000 20000 30000 40000 simulated time in milliseconds (of interpreter) Speedup 776% #processes 34 #suspensions 33 communication 2244 bytes Availability Version 0.7 of the Concurrent Clean System with all the features mentioned above is now available for both the Macintosh as well as Sun3 and is distributed free for educational and research purposes. It can be obtained via anonymous FTP (phoibos.cs.kun.nl (131.174.81.1) in the directory pub/Clean) or by electronic mail (clean@cs.kun.nl) or by sending two floppy disks (for the Mac) or a cartridge (for the SUN3) to the address above. The Macintosh version runs on any Mac with system 6.0 (or higher), needs at least 1.5 megabyte and requires a multi-finder to make sub- launching possible. ** Note (Ron Wichers Schreur) ** ** ** ** Actually, the Macintosh version only requires ** ** system 4.1 (or better). MultiFinder is not ** ** required, but sub-launching is much faster with ** ** the MultiFinder. ** Future plans For the final version of the Concurrent Clean System the following extensions are planned: * the efficiency of the sequential code will be further improved; * more syntactical sugar will be added (guards, infix notation, overloading); * more sophisticated annotations for parallel evaluation will be added; * an even more liberal type system based on intersection types (Coppo (1980)) will be added; * IO facilities that make menu and dialogue handling possible in Clean applications; * the possibility to import Miranda(TM) scripts (Turner (1985)); * a parallel version for the Mac, using several Macs connected via the Appletalk network; * a code generator for our 64-node Parsytec Transputer system. Conclusions With the Concurrent Clean System (parallel) functional programming has become available on the Macintosh. The system is used for teaching students functional programming in general as well as for studying the behaviour of functional programs on parallel machine architectures. Combined with a student textbook version 1.0 of the Concurrent Clean System will be made widely available in the beginning of 1992 (Plasmeijer & van Eekelen (1990)). References - Barendregt H.P., Eekelen M.C.J.D. van, Glauert J.R.W., Kennaway J.R., Plasmeijer M.J., Sleep M.R. (1987), 'Term Graph Rewriting, Proceedings of Parallel Architectures and Languages Europe (PARLE), part II, Eindhoven, The Netherlands, LNCS Vol. 259, pp. 141-158, June 1987. - Brus, T., Eekelen, M.C.J.D. van, Leer, M. van, Plasmeijer, M.J. (1987). Clean - A Language for Functional Graph Rewriting. Proc. of the Third International Conference on Functional Programming Languages and Computer Architecture (FPCA '87), Portland, Oregon, USA, Springer Lec. Notes on Comp.Sci. 274, 364 - 384. - Burstall R.M., MacQueen D.B., and Sanella D.T. (1980), 'Hope: An Experimental Applicative Language', Proceedings of the 1980 LISP Conference, 136 - 143. - Coppo, M., Dezani-Ciancaglini, M. An Extension of the Basic Functionality Theory for the l-calculus. Notre Dame, Journal of Formal Logic 21 (4), 1980, page 685-693. - Hudak, P., Wadler, Ph., Arvind, Boutel, B., Fairbairn, J., Fasel, J., Hammond, K., Hughes, J., Johnsson, Th., Kieburtz, D., Nikhil, R., Peyton Jones, S., Reeve, M., Wise, D., Young, J. (1990). Report on the programming language Haskell. Version 1.0. - Johnsson Th. (1984). Efficient compilation of lazy evaluation. Proceedings of the ACM SIGPLAN '84, Symposium on Compiler Construction. SIGPLAN Notices 19/6. - Milner R.A. (1978). Theory of Type Polymorphism in Programming. Journal of Computer and System Sciences, Vol. 17, no. 3, 348 - 375. - Nocker E.G.J.M.H. (1988). 'Strictness Analysis based on Abstract Reduction of Term Graph Rewrite Systems. in Proceedings of the Workshop on Implementation of Lazy Functional Languages', University of Goteborg and Chalmers University of Technology, Programming Methodology Group, Report 53. - Nocker E.G.J.M.H., Smetsers J.E.W., (1990). 'Partially Strict Data Types', in Proceedings of the Second International Workshop on Implementation of Functional Languages on Parallel Architectures, pp. 237-255, Technical Report no. 90-16, October 1990, University of Nijmegen. - Nocker E.G.J.M.H., Smetsers J.E.W., Eekelen M.C.J.D. van, Plasmeijer M.J. (1991). 'Concurrent Clean', to be published in the Proceedings of the Conference on Parallel Architectures and Languages Europe 1991 (PARLE). - Plasmeijer M.J., Eekelen M.C.J.D. van (1990). Functional Programming and Parallel Graph Rewriting. Draft Lecture Notes. University of Nijmegen. Final version to be published by Addison Wesley, spring 1992. - Turner, D.A. (1985) Miranda: A non-strict functional language with polymorphic types. Proc. of the conference on Functional Programming Languages and Computer Architecture, Springer Lec. Notes Comp. Sci. 201, 1 - 16. Miranda(TM) is a trademark of Research Software Ltd.