Lambda the Ultimate

I'm most familiar with the Common Lisp style implementation of the multiple-value-return feature.

But I notice that several other languages, including Python, use tuple return values and do destructuring on these tuples.

What are the advantages/disadvantages to each? Semantically? Implementation and performance?

Are there other (better) models of multiple-value-return that I should study?

Thanks much!

Scott
- No, I'm not a student :-)

Define dead-end theorems to be theorems that are not used to prove other results. What percentage of proofs in PLT papers are of dead-end theorems?

For example, a type soundness result is not often used to prove more fundamental results. It is just a "house keeping" theorem.

Does this percentage tell us anything important?

Last few years i have been playing with creating my own programming languages, I've got a pretty good idea of what i want it to do and what i want it to look like. I've finally decided to go with the CLR virtual machine as the back end (simply because I'm working on a RAD language and not anything low level. If i need raw speed i will use asm, c, or forth) My problem is that all the common language runtime work i have done has been writing il code for basically toy languages and scripting tools, so while i know what i am getting into as to the ins and outs of compiler design what i don't know is if i could create erlang like green threads in any reasonable manor on the clr.
Anyone have a basic run down of how green threads are implemented in erlang and if i could do something similar on .net?

keep in mind the language will be pure functional sort of like haskell. I have a strong interest in making it erlang like with the concurrency because erlang simply got it right (though the syntax sucks).

Even if all you have is a link i'm cool with that, i'm not afraid to do a lot of research on my own =P

I haven't found anything more on this yet via Googling around; anybody know more? If it really means that all I/O is referentially transparent, it would be interesting to this newbie to see compare/contrast with e.g. Monadic approaches to I/O.

From FOLDOC

It has a continuation-based I/O system with referential transparency and is capable of handling all common I/O tasks such as terminal and file I/O, signal handling and interprocess communications.

It seems to me that PL theory focuses on type systems with respect to what they prove about all well-typed programs. It seems to me that PL theory does not focus on type systems with respect to what they can be made to prove about some well-typed programs.

Is my perception of this focus correct, and, if so, is this a good state of affairs?

I am open to the idea that the answer is "yes, that is PL theory's focus, and that is a good state of affairs since the rest is pragmatics, i.e. software engineering, not PL theory." But I guess I wouldn't have asked the question if I didn't have suspicions to the contrary.

Another way of asking it is, does PL theory treat type systems primarily as a way language designers help programmers, and only secondarily as a way language designers help programmers help themselves? Or does it treat neither role as primary? Or are these roles inseparable?

Comments?

Call for Participation:

ALTA 2008

Architectures and Languages for Throughput Applications

Program:

1. Chuck Moore, AMD
Accelerated Computing in the Multi-core Era

2. Havard Bjerke, CERN
High Throughput Computing for CERN's Large
Hadron Collider

3. Michael Shebanow, NVIDIA
Title TBD

4. Doug Carmean, Intel
Title TBD

5. Weiwu Hu, Chinese Academy of Sciences
A Brief Introduction to Loongson Processors

6. Sun Chan, Simplight Electronics
Towards a sequential programming model
for a multi-threaded architecture

7. Gabriel Loh, Georgia Tech
The Cost of Uncore in Throughput-Oriented
Many-Core Processors

8. Paul Peng, Intel
SEE: A Scalable Execution Environment
for Heterogeneous Processing Architectures”

9. Wing-Yee Lo, Jiqiang Song, Daniel Pak-Kong Lun,
Wan-Chi Siu
SIMD Throughput Bottleneck Improvement
Using Vector Load/Store and Configurable
SIMD Support

10. Changhai Zhao, Xiaohua Shi, Haihua Yan, Lei Wang,
Beihang University
Exploiting Coarse-Grained Data Parallelism
in Seismic Processing

11. Oscar Hernandez, Lei Huang, Barbara Chapman,
University of Houston, Danesh Tafti, Pradeep
Gopalkrishnan, Virginia Tech
Experiences Tuning an OpenMP Application

Sunday, 22nd June, Beijing, China

This is a workshop held in conjunction with ISCA 2008. For registration, see:

http://isca2008.cs.princeton.edu/
http://www.regonline.com/Checkin.asp?EventId=165151
(For registration)

For the ALTA website, see:

http://www.sei.buaa.edu.cn/alta08/

Program Committee
Doug Carmean, Intel Corporation
Tom Conte North Carolina State University
Mike Houston AMD
Michael McCool RapidMind Inc.
Michael Garland Nvidia
Sun Chan Simplight Nanoelectronics
Xiaohua Shi Beihang University

Organizers
Anwar Ghuloum, Intel Corporation
Gansha Wu, Intel Corporation
Michael Liao, Intel Corporation
Josh Fryman, Intel Corporation

Hello All

(I hope this forum is the appropriate place to ask)

I'm working within GCC on a Lisp translator (from some Lisp dialect, called MELT, to C) to be used for GCC middle end analysis; the motivation is to be able to code GCC middle end analyzers & passes in my Lisp dialect.

The code is updated several times a day on the GCC SVN. See MELT for details (or ask me).

The lisp dialect is not really documented yet. The major difference is that MELT has both boxed and unboxed values. Also, most primitives are not called as in Lisp (but most control operators are the same, let is somehow a let*, ...). Primitives are described by giving their expansion to C. MELT files have a *.bysl extension (because MELT was called Basilys at first).

The MELT dialect is a lisp like dialect (a Lisp1 in C.Queinnec terminology), with dynamic types and lexical scoping (a la Scheme).

Here is the familiar 2nd order function to map a function into a list.

(defun list_map (lis f)
  (if (is_list lis)
      (if (is_closure f)
	  (let ( (reslis (make_list discr_list)) 
		 (curpair (list_first lis)) )
	    (forever lisloop
		     (if (not (is_pair curpair)) 
			 (return reslis))
		     (let ( (curelem (pair_head curpair)) )
		       (list_append reslis (f curelem)))
		     (setq curpair (pair_tail curpair)))
	    ))))

In the code above, defun if let forever return setq are "keywords" ie have a special significance to the compiler. is_list is_closure make_list list_first not is_pair pair_head list_append pair_tail are primitives (expanded to some C code). lis f lisploop reslis curpair curelem are locally bound names and the function list_map is globally defined by the defun

Here is the not (boolean not, on unboxed longs) and is_list (on values) primitive:

(defprimitive not (:long i) :long "(!(" i "))")

(defprimitive is_list (li) :long
  "(basilys_magic_discr((" li ")) == OBMAG_LIST)")

The first :long occurrence in not before i tells that formal i is an unboxed long, and the second :long occurrence tells that the result of not primitive is an unboxed long.

The is_list primitive definition tells that the result of is_list is an unboxed long, and how to expand it into C. The quoted strings are actually C code fragments appearing in the generated code.

Lists in MELT are not just pairs. A List is actually a structure keeping the first & the last pair of a linked list of pairs.

First, some fact about my implementation (available on GCC SubVersion repository in the MELT branch).

I'm working within GCC, closely following the trunk (future 4.4)

I have a runtime, which means a garbage collector & various primitives coded in C. See files gcc/basilys.c & gcc/basilys.h - it is debugged well enough to be able to run many minutes. (BTW debugging a garbage collector is a nightmare). MELT garbage collector is built above the existing GGC collector in GCC.

I have a cold translator, coded in Common Lisp (CLISP actually). File contrib/cold-basilys.lisp. It is able to translate some MELT code *.bysl into *.c ; I do know it is buggy, but I want to maintain it as little as possible. Conceptually the only purpose of this cold translator is to be able to handle warm-basilys.bysl below

The real stuff is the warm translator, in file gcc/melt/warm-basilys.bysl it is translated by CLISP running cold-basilys.lisp to coldbuilt-warm-basilys.c & coldbuilt-warm-basilys.so (a plugin dynamically loaded by my cc1 - the C compiler proper of gcc).

my cc1 with the above generated coldbuilt-warm-basilys.so is able to translate (except bugs) any *.bysl file into *.c (so it does the same work as cold-basilys.lisp, but in principle better, and coded in MELT). in particular it is able to translate itself, ie warm-basilys.bysl into warm-basilys-1.c etc..

my cc1 with warm-basilys-1.so is able to generate warm-basilys-2.c from the same warm-basilys.bysl. Sadly, warm-basilys-2.c is not the same as warm-basilys-1.c (it should)

my cc1 with warm-basilys-2.so produces warm-basilys-3.c from warm-basilys.bysl. warm-basilys-2.c & warm-basilys-3.c are identical (but buggy).

The buggy bootstrap (with warm-basilys-2 & warm-basilys-3 identical but buggy) actually happenned in svn rev135845

I am chasing a meta-bug, in the following sense.. The function pairlist_to_multiple in warm-basilys.bysl near line 2183 is incorrectly translated by warm-basilys.bysl (actually by coldbuilt-warm-basilys.so) - founding that one of the badly translated function is this one is non trivial. It behaves differently in coldbuilt-warm-basilys.so (works ok there) and in warm-basilys-1.so (incorrectly returns nil).

I am experimenting that chasing metabug is challenging, and quite difficult.

Do you have horror stories, hints, insights, theoretical papers, personal experiences, about these?

How do you find such metabugs? (it is meta in the sense that the generated code behave wrongly).

Regards.

I've a question for the group concerning domain-specific languages. One taxon by which DSLs can be categorized is whether or not they are standalone or embedded (my terms; don't know if there are better or more precise terms for the concepts in the literature). A standalone DSL is one which contains little or no trace of the language used to implement it (and indeed, implementations of the DSL may be written in any decent general-purpose language, with similar effort). When general-purpose computing constructs (flow control, recursion, arithmetic, error handling, type processing) is needed, it must be added as part of the DSL.

HTML, to the extent that it is a programming language, would be one example.

An embedded DSL is one which extends, in some fashion, an existing general-purpose language which I shall refer to as the host language (one which is typically the language of implementation)--code written in the host language, or a subset thereof, is also valid in the DSL. In such languages. Such language may be implemented via macros or similar "compile-time" metaprogramming means; by standalone programs which translate the DSL into the host language, or by interpreters which include the ability to evaluate statements in the host language (possibly relying on an eval() facility present in the host language itself). Generally, such DSLs are tightly coupled to their host, and writing code in the DSL will often require knowing the host language. Writing the DSL implementation in a different language than the host may be difficult; especially if the DSL is interpreted. (Writing a DSL compiler/translator is more easily done in a "third" language).

Yacc is one example; while the part of the language for describing productions themselves isn't dependent on any other language, semantic actions pretty much have to be written in C/C++. If you want to write a LALR(1) parser in some other language, you're better off with a different tool. The universe is replete with experimental languages which compile into Java, and which typically allow Java to be embedded within. (Java generics started off this way, although adding decent polymorphism to Java is hardly domain-specific).

The questions are: What are the design trade-offs between the two approaches? The embedded approach seems to be easier, especially in a language with decent metaprogramming. The standalone approach seems better for a language which is intended to be used by non-programmers, or which need to spread beyond a single project, organization, or language community--but when general-purpose programming facilities are needed, that wheel is often implemented poorly. (And in the degenerate case, the result is not really a DSL but yet another general-purpose language--quite a few general-purpose languages started off as DSLs but became generalized).

According to a Management Insights study software designers have incentives to pursue more complex solutions than necessary.

I guess that the language and language platform is part of that complexity... I did not read the actual paper (not a free download).

Addendum
Ruediger Hanke provided this link which details better the scope of the study. Notably:

Drawing upon existing theory, we subject participants in our experiments to a context in which they act as agents for a principal, and have to convince this principal of their capability in order reap financial incentives. [...]Theory suggests that the difficulty of the task influences their expected gain in reputation. The data from the experiment supports that people have a higher propensity to choose a difficult solution as the expected reputation they can gain by choosing this solution increases.

Hello,

I'm not a languages researcher, but since the authors of "The Reasoned Schemer" frequent this board, I figured they might be interested to know that I translated the system from their book to Clojure. Here's the post to the Clojure group.

post

Jim

(First time poster, so I hope this is appropriate.)