Lambda the Ultimate

If you're a fringe language enthusiast and in the DC area this weekend,
stop by our next meeting. We are interested in all uncommon languages
and have both informal and formal meetings in our organization. (formal
meetings have a speaker- We'll have our next formal speaker on March
24th)

Hope to see you there!

- Conrad Barski, M.D.

http://www.lisperati.com/fringedc.html

Dear Ultimate Lambdas,

I'm to collect criticisms on the state of the art of functional programming. Up to now I've found Wadler's paper on "Why no one uses functional languages?". Could you please send me pointers to other papers written on the subject?

Tobin-Hochstandt & Felleisen, "Interlanguage Migration: From Scripts to Programs", (Dynamic Languages Symposium 2006)

As scripts grow into full-fledged applications, programmers
should want to port portions of their programs from script-
ing languages to languages with sound and rich type sys-
tems. This form of interlanguage migration ensures type-
safety and provides minimal guarantees for reuse in other
applications, too.
In this paper, we present a framework for expressing this
form of interlanguage migration. Given a program that con-
sists of modules in the untyped lambda calculus, we prove
that rewriting one of them in a simply typed lambda calcu-
lus produces an equivalent program and adds the expected
amount of type safety, i.e., code in typed modules can’t go
wrong. To ensure these guarantees, the migration process
infers constraints from the statically typed module and im-
poses them on the dynamically typed modules in the form
of behavioral contracts.

See also: Typed Scheme by Sam Tobin-Hochstadt:

...a version of PLT Scheme's core with an "occurrence type system".
.. Next we will develop a cross-language refactoring tool that assists programmers with the task of translating one module in a program system from the untyped language into the typed one. [The paper above] lays out the theoretical framework for this research.

(from Felleisen's Projects page)

In http://lambda-the-ultimate.org/node/1930 and http://lambda-the-ultimate.org/node/1944 i described a lambda calculus with quotation and a program logic. Ever the one to believe that theory and practice should verify each other, i have put together, here (http://svn.biosimilarity.com/src/rlambda/), a first draft implementation of the ideas in OCaml.

Currently, the system supports a very brittle command line REPL for a pretty raw syntax. The main point of interest is that the code is factored more or less along the lines of the specification, making use of recursive modules. That is, syntax and structural equivalence are functors of a module type IDENTIFIER. Then a reflective module is made by interpreting the IDENTIFER operations using terms. See the code. (Note: i wanted to have the operational semantics module also be a functor and recursively instantiate, but i couldn't get the OCaml compiler to get the three-level functor to work properly. Email me at lgreg.meredith@biosimilarity.com for further discussion.)

In an upcoming update i will add a simplistic model-checker for the logic.

System requirements

i have only tested the code on Mac OS X (tiger) using "OCamlDuce version 3.09.2pl2", but i'm pretty sure that a plain vanilla version of OCaml at or around version 3.09.x should build and run the code. The make files are written for

lgmaclt:~/work/src/projex/biosimilarity/reflection/rlambda/ocaml lgm$ `which make` --version
GNU Make 3.80
Copyright (C) 2002 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
lgmaclt:~/work/src/projex/biosimilarity/reflection/rlambda/ocaml lgm$

Copyright

The source files say Copyright: Biosimilarity LLC. All rights reserved. But, everything on the site is under GPL. So, you are free to do what you want with the code -- such as it is -- as long as you respect GPL.

I've been reading up on multi-stage programming recently and came accross Eta-expansion does The Trick which interests me because partial evaluation is something I think deserves higher visibility in programming in general.

I've seen η-expansion in the context of the various λ-calculi before but I can't seem to translate this to algol style languages. I must be missing something trivial or obvious. Could anyone please enlighten me?

                Web Of Code

        http://idiki.dyne.org/wiki/WoC

WoC stands for Web Of Code.

The basic idea is to add hyperlink capacities to source code documents,
creating, in this way, a new Web, of code.

The Idiki article describes the idea and shows how it can be implemented using
existing tools, f.e. ViewVC, cscope and Vim.

Another idea explored by the article is:
       
       #!/usr/bin/python
       from :openssl.org/ssl: import RSA*

The article is here: WoC

Best regards.

dear forum,

I am not a programmer but I am very (and I mean, very) interested in programming. There are programmers who work real hard and for very understandable reasons are not very interested in history and fundamentals, but I am. I hope you guys will be friendly enough to give me directions, the reason I am doing this in a forum all about programming languages is that I know no one personally who can help me with this, and this thread can serve others.

I've heard (read) so much about Smalltalk (specifically, how cute it is as a language) but unfortunately the omniscient web didn't help me much (I know, weird). I have a fair bit of understanding of Java and (to a lesser extent) C++ (I am not comfortable with template wizadry, to be specific). The language I like most so far is Haskell, feel free to use any of these to make a point. What I am interested about the most is the difference between Java and Smalltalk.

I went to www.smalltalk.org, www.squeak.org, and some other websites. They had free books. But most of those books are in very weird formats (pictures embedded in PDF for example) and taught programming in Smalltalk itself, but I am not going to *use* Smalltalk anyway. I have a feeling that none of the articles/tutorials/books/documentations highlighted the *ideas* behind Smalltalk. They are mostly about how OO influences software construction. We know that pretty well by now. But I want to know why Smalltalk is the definitive OO language.

The questions I have are very naive (so if you don't feel like it, please just point me to relevant books or, better, webpages):
- classes are first-class objects? whatever does that mean? examples?
- the difference between 'self' and 'this' (in Java)?
- isn't Smalltalk dynamically typed? how do classes interact with dynamic typing?
- both functional languages and Smalltalk exhibit 'minimal' syntax in a sense, am I right? why? how? is there a very easy way to embed one into another? does currying have a Smalltalk counterpart?
- why do people call Smalltalk "pure OO"? apart from the superficial primitive types in Java, aren't everything else objects? what does it mean to be "pure OO"?
- interfaces? do they make sense?
- is there any intuitive reflection mechanism in Smalltalk?

So, in a sense, what I really need is a language report, not tutorials and introduction to OO principles. is there any? the functional counterpart of what I am looking for would be the Haskell98 report. with a bit of explanation on what is there and what is left out and why. please raise other questions as well.

cheers! may 2007 bring joy and happiness to your life. specially if 2006 didn't ;)

[PostScript: I noticed the frames and slots thread and I think the questions I want answers of could appear there as well, I'm keeping an eye on that one too!]

Frames and slots were hot in the 80s but now the terminology seems to be rarely used. Is this because the frame model are a subset of the OO model?

After reading the thread about PL puzzles I decided for a change to design my own puzzle instead of my own PL.

How about this - "mirror an immutable binary tree preserving existing sharing"?

So in Haskell, I would take this data type:

data Tree = Leaf | Node Tree Tree

and write a function that maps leaves to leaves, and nodes to nodes with swapped children.
"mirror an immutable binary tree" was easy. What about "preserving existing sharing"?
For that I need to cheat a bit and augment my data type with identifiers, and pretend that meets the requirements of the puzzle.

Or I may use StableName, but then I will end up inside IO kitchen sink.
One may argue that ability to recognize sharing is not referentially transparent, and therefore it's a feature that it's available only inside IO computations. I however feel that this binary choice between purity and impurity is too harsh - can I have an indulgence, please?

To be constructive, I decided to redesign the puzzle so it is a fair game.
Now it sounds as: "clone an immutable binary tree obtaining maximum sharing".
I believe that while pure code cannot recognize sharing, it can at least manifest its desire to create sharing (subject to compiler's whim, of course).

The full tree of depth n (having 2ⁿ-1 nodes) will therefore be compressed to a DAG of n nodes - impressive ratio!

Additional points if your code does not create intermediate structures (this is unfair towards PLs without implicit stack, BTW), if it traverses the original tree only once, if it can be reused for other data types, and if you can state it's computational complexity and/or maximum size of the stack (sure, some of these tasks are much harder than others).

Walter Bright's D programming language 1.0 was released today!

A sampling of its many great features:

Garbage collection
Scope expressions
Lazy expressions
Auto-type inference
Built in arrays/strings and associative arrays.
templates and mixins
Design by contract
RAII

http://www.digitalmars.com/d/changelog.html
http://ftp.digitalmars.com/dmd.1.00.zip

Cheers.