From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA01983; Mon, 5 May 2003 15:18:15 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA02464 for ; Mon, 5 May 2003 15:18:13 +0200 (MET DST) Received: from mail1.tpgi.com.au (mail.tpgi.com.au [203.12.160.57]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h45DIBH02386 for ; Mon, 5 May 2003 15:18:12 +0200 (MET DST) Received: from ozemail.com.au (syd-ts22-2600-037.tpgi.com.au [203.26.30.37]) (authenticated (0 bits)) by mail1.tpgi.com.au (8.11.6/8.11.6) with ESMTP id h45DHqI04025; Mon, 5 May 2003 23:17:53 +1000 Message-ID: <3EB6647F.2020008@ozemail.com.au> Date: Mon, 05 May 2003 23:17:51 +1000 From: John Max Skaller User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2.1) Gecko/20010901 X-Accept-Language: en-us MIME-Version: 1.0 To: Mattias Waldau CC: "'Diego Olivier Fernandez Pons'" , caml-list@inria.fr Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list) References: <049301c312f7$12f58c10$0200a8c0@gateway> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; ozemail:01 caml-list:01 mattias:01 waldau:01 polynomial:01 functorial:01 algol:01 expr:01 hackery:01 generic:01 suboptimal:01 gcaml:01 threading:01 python:01 hashes:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Mattias Waldau wrote: > It would be interesting to see how a typed scripting language (maybe > built on top of ocaml) with advanced built-in datastructures (with > syntax support) would look like. There are two things you can look at: (1) FISh 2 when it finally comes out, will support general polynomial data structures with functorial polymorphism: at the moment only FISh 1 is available but gives the flavour: http://www-staff.it.uts.edu.au/~cbj/FISh/ (2) Felix: http://felix.sf.net isn't nearly as ambitious, indeed, its a stock Algol like language with a couple of twists which includes heavy support for purely functional programming with eager evaluation. At the moment, the only 'advanced' data structure built-in to the language is the ability to build O(n) regular expression matching used like: regmatch string_expr with | regexp1 => ... | regexp2 => .. [and there is some hackery here ..] Contrary to providing 'built-in' advanced data structures, Felix is exactly the opposite: it has no built-in data types at all. Instead, it provides powerful data constructors such as anonymous sums and products, as well as functions of course. These are strong enough to construct bool in the standard library. In addition, it provides a way to lift data types from C/C++. For example: type int = "int"; fun add: int * int -> int = "$1 + $2"; Each of these "user defined primitives" is defined in C/C++ and provided as an abstract data type, accessed by user specified primitive functions (like "add" above). Primitives can now also be generic: type vector[t] = "std::vector"; I'm explaining all this because in my opinion, providing some fixed "efficient/advanced" data structure "built-in" to the language is in fact suboptimal, and unnecessary. The trick, instead, is to provide CORE functionality which can be used to conveniently construct and access such data structures. For example you can write: s[1 to 20] to subscript a string. It's just syntactic sugar for: subscript(s,1,20) and subscript is just a function: for a given string like type, the user has to define it. Some of the other features that make Felix friendly include an advanced overloading scheme which fixes many of the problems in the C++ mechanism (and contrary to GCaml, is even more "open" than the C++ mechanism) The most advanced feature "builtin" is, in fact, not a data structure but a control structure: Felix performs blocking reads on a central message queue by yielding control (without using hardware threading). [I call the suspended states continuations, but technically I think they're resumptions] It is likely I will provided synactic sugar for some other concepts such as iterators. What's important in scripting languages, apart from automatic storage management, is that the syntax be convenient. There is nothing in Python dictionaries or Perl hashes that can't be done in C++ or Ocaml: the primary advantage is NOT that these data structures are built in. What's important is the easy use which specific syntax provides. Felix will try to provide the convenience without actually building anything in: instead, it provides a way to bind the syntax to user defined types. Operator overloading and the like are the simplest and easiest way to do this, although it's painful compared with what FISh 2 seeks to do: allow functorially polymorphic algorithms to be written. I have to recommend consideration of the protocols definitions in Python, and the container and iterator definitions in the C++ Standard. Both of these systems handle, in a different way, the notion of Sequence and Associative Container fairly well. Similarly, SQL embodies well the notions of relational algebra (and in some sense is a generalisation of sequences and associative containers). Its clear, however, that no one has much idea what to do with trees and graphs (yacc like parser tools are the closest thing to tree management syntaxes, and they're usual extrinsic rather than embedded in the language). In the end, convenient use of advanced data structures -- and i don't mean simply sequences and associative containers -- depends on theoreticians developing the right general calculi to deal with them in a compact way. Only then can language designers provide generalised syntax that goes beyond overloading and stuff like address ["fred"] = "20 Smith St Paris" -- John Max Skaller, mailto:skaller@ozemail.com.au snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia. voice:61-2-9660-0850 ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners