Lambda the Ultimate

Hello everyone,

I am currently trying to understand what the trade-offs are between uniqueness typing and monads. On the surface uniqueness typing seems a little easier to grasp and read (code wise), but it seems there is a lot of fascination with Monads.

I was curious how one would judge whether to use one or the other in order to model side-effects in a pure functional language. Which strategy gives the most 'bang-for-the-buck' in regards to language semantics but also in regards to learning curve?

Thank you everyone in advance for being so helpful. =)

Regards,

-M.

Hi,

I don't know if any of you are interested in this but, the weekly BBC Radio 4 program "In Our Time" last installment divoted the whole program to the development and history of Artifical Intelligence (AI).

As you are probably aware, BBC Radio 4 offers a "listen again" service where past programs are streamed to you via Real Player so that you can enjoy missed programmes at your leisure. However, "IOT" is one of the few programs where you can actually download the programme as an MP3 as well.

"IOT"'s webiste is here: http://www.bbc.co.uk/radio4/history/inourtime/inourtime.shtml.
Looks for the links on the left hand side of the page to either listen again via RealPlayer or download the MP3 if your interested in listening to this programme. (The MP3 is DRM free, BTW)

The next episode (about the Peterloo Massacre) is on Thursday morning and this new episode will replace this current edition about AI, so you may need to "digitus extractus" if you want to catch the programme and listen to it.

Enjoy
Cheers
Barry Carr
Scotland

I am implementing a new language whose fundamental blocks are two structures called "Connect" and "Signal".

The "Signal" carries the data from one connect to another.

A Connect takes a signal as an input and gives another signal as the output.The behaviour of the connect depends on the following things:
- Their type(all connect's are not the same, type not as in programming theory)
- The data present on the signal
- Current state of the connect.(It acts like a Finite State Machine)

Can i call this a new way of doing things, a paradigm?

I am steadily growing frustrated with the programming languages and more importantly their implementations that I use both at work and at home. I won't bore you with why. So I thought I'd have a go at creating a language and RTL that I would like to use.

Personally, I happen to think OO is greatly overrated and prefer a functional/procedural approach and would probably prefer to use CPS for the implementation but would rather shy away from the complexities of garbage collection. But as far as I can tell it seems impossible to implement continuation passing style (and closures, of course) without garbage collection. Correct?

(I can tell as I write this that anyone responding is just going to say 'GC has decades of research behind it and these days can be extremely efficient while remaining relatively simple. What's the problem?' so rather than explain why I don't want GC perhaps my question can be taken as a hypothetical inquiry. :))

In my day-job as a Java programmer I use a lot of tools that relies heavily on reflection, and I've come up with quite a few uses of reflection that can simplify my day job. Having also become quite fond of OCaml and it's powerful type systems I've started wondering if combining reflection with a powerful type system is possible. The two features seem quite at odds with each other, reflection completely undermines the type system, something I also see every day in my day-job.

Has anyone looked at ways of combining the power of these two language features? In OCaml I'll have to resort to something like camlp4 if I want to do the stuff I use reflection for in Java. But it's seems to me that there might be a middle ground between syntactic extension and the metaprogramming allowed by reflection. Or is there some fundamental reason why this is impossible? As you probably understand I really don't have any clue what this is called, or if it exists, or if it's useful, so I'm curious about anything that might shed some light on it.

... we show how to use our new technique to copy and reconstitute the stack on MSIL.Net using exception handlers. This establishes that Scheme’s first-class continuations can exist on non-cooperative virtual machines.

Continuations from Generalized Stack Inspection (pdf)

I've written a graph pattern-matcher (Common Lisp), and I was wondering if anyone could offer comments regarding primitives or operators to modify or add. Mostly, I tried to extend regexes to graphes (or any data structure that can contain references), and make it easier to extend the language. Maybe I should have posted this on my own webspace and pasted a link. If it is the case, simply tell me and I'll fix that.

Ob-Grocery list of features: circularity-aware (for the graph that is to be matched, not the pattern against which to match - circular code is wrong ;), not biased towards any data structure, easily extensible and, of course, a dreaded sexp-based syntax.

The core of the language is:

• alt: like the | operator in regexes, it provides ways to define failover patterns. (alt f1 f2 f3 ...) tries to match the corresponding subgraph against f1, and, if it fails, tries f2, f3, and so on. (alt) fails automatically.
• and: Succeeds if all of its subclauses match against the subgraph (the subclauses are matched in left to right order). Fails as soon as any of the subclauses fail.
• access: (access accessor pattern) Matches the pattern against the result of applying accessor (any common-lisp function) on the corresponding graph node. Backtracks gracefully when the accessor throws an error.
• pred: (pred predicate) Succeeds if the predicate (a full-blown Common Lisp function) returns true on the graph node, fails otherwise.

• Digression: I also allow a limited form of state in the presence of matching. Basically (so far), I can bind matches to a name, and each bindings only succeeds if all the matches bound to a given name are all deeply equal. For that reason, pred [when its optional second argument is true] can also fail or succeed based on the result of predicates on both the graph node and the names bound (with the subgraphs to which they are bound) so far. I think this could be comparable to one-way unification.

  bindpred: (bindpred predicate). Succeeds or fails based on the result of a predicate on the current graph node and the names bound so far. If the predicate succeeds, its second return value is the updated alist of bindings.

And that's it for the primitives. Lazy, one-level deep, macroexpansion (to allow recursive macros) does the rest.

Other operators are defined in terms of the previously described primitives and macroexpansion.

• atom: (atom) matches any atom. (atom foo) matches any atom that is equal to foo.
• any: (any) matches anything. (any type) matches anything that is of that type.
• bind: (bind name pattern) tries to bind "name" to the graph node if "pattern" matches against the node. It expands to:

  (and pattern
       (%bind-now name))

  where %bind-now expands into a bindpred clause. %bind-now does the "tries to bind 'name' to the graph node" part of bind's job description. If there is no previous bindings to "name" or it is deeply equal to the current graph node, it succeeds (and saves a bindings from name to the graph node if needed); otherwise, it fails.

• rep: The star of the show, and the only recursive construct so far. rep is analogous to the (kleene?) star in regexes.

  (rep pattern pattern-final &rest accessors) [everything after pattern-final is kept in a list of accessors] matches a graph node against "pattern," and if that is successful, all of that node's children (those that are accessed through the accessors) against "pattern," and so on. When "pattern" doesn't match, it still succeeds if "pattern-final" matches against the same graph node and fails otherwise. rep is implemented purely in terms of macroexpansion: (rep pattern pattern-final accessor1 accessor2 ...) expands into:

  (alt (and pattern
           (access accessor1 (rep pattern pattern-final accessor1 accessor2 ...))
           (access accessor2 (rep pattern pattern-final accessor1 accessor2 ...))
           ...)
       pattern-final)
  

  Note that the expansion is recursive, which is why macroexpansion is lazy.

• cons: The only datastructure-specific operator. (cons &key (car-clause '(any)) (cdr-clause '(any)))

  Matches any cons whose car matches car-clause (which defaults to (any), which matches anything) and whose cdr matches cdr-clause (same default). It expands into:

  (and (pred consp)            ;;consp is a predefined predicate
       (access car car-clause)
       (access cdr cdr-clause))

  (with the appropriate defaults)

Example usage:

To match any combination of cons with only 2 atoms in it:

(rep (cons)
     (alt (bind a (atom))
          (bind b (atom)))
     car cdr)

It traverses conses' car and cdr, matching any cons. When the current node isn't a cons, it saves the corresponding atom under the names a or b. If "a" is already bound to something that isn't equal to the current node, it tries to bind it to "b". If, again, "b" is already bound to something that isn't equal to the current node, the matching fails. Thus, it can only match up to two different non-cons atoms (I think there is some redundance here ;). Note that when it does match successfully, the bindings' alist is returned as a second return value. No point in wasting all that work!

Now, it obviously wouldn't be very hard to build a recursive function to do the same job -- in fact, this is exactly what the matcher will do. However, making the same function work in the presence of circularity would make this already repetitive job a tad more tedious.

Comments, questions or suggestions (additional operators or another syntax, for example) would be appreciated.

Paul Khuong

EDIT: How _I_ expect to use this: I want to write a compiler that works, as much as possible, through graph rewriting. I hope the matcher can help a lot there.

EDIT2: Fixed the expansion for rep

I've become enamored with Backus's FP language (and the lesser known follow-up FL) as of late. Does anyone know of *any* programs written in either of these languages that are outside the 1-3 line toy variety? I've found nothing. Even 10+ line toy programs would be fine, but a larger program would be even better.

(For programs in a related style there's Iverson's J, but I'd still like to see some real FP programs.)

The workshop on Synchronization and Concurrency in Object-Oriented Languages has a nice, accessible collection of papers on software transactional memory and other language-based approaches to building concurrent systems.

A giant (and messy!) collection of PL musings, links, and citations. I enjoyed the polymorphism page the most.