A recent paper by Oleg Kiselyov and Yukiyoshi Kameyama at the university of Tsukuba discusses weaknesses and areas for improvement to Prolog.
The paper mentions the strength of the approach used by miniKanren (which embeds logic programming with fairer search strategy than normal Prolog into Scheme) and Hansei (which embeds probability based nondeterminism into Ocaml using delimited continuations to allow direct-style expression of monadic code).
After motivating some choices by studying the prototypical example of running append backwards they cover running parsers with "maximal munch" rule backwards - something that cannot be (declaratively) expressed in prolog.
A very interesting paper on logic programming! It also thanks Tom Schrijvers of CHR fame at the end.
Dear Lambda The Ultimate,
I've been working very hard recently on writing something I thought would be entirely straightforward: A scheme to C compiler that bootstraps - nothing I do seems to work. On my first attempt (which was able to compile and run its own parser) there was no GC or tail calls so it demanded >8GB of memory and failed, on my next the emitted code blows up so huge that it grinds to a halt. I hope someone could give me some advice on what I should do or what I need to learn to complete this? It would also be interesting to discuss and read about other members experiences.
I've been interested in programming languages since I started programming a long time ago, and have explored and written parsers, type checkers and interpreters for a fair selection of different types of programming languages like lisp (of course!), prolog (and minikanren), a cut down version of haskell with hindly milnor type checking as well as some unusual things like linear and reversible programming languages.
A long time ago I read Marc Feeley - 90 Minute Scheme to C compiler when it came up on this site and it was fascinating to understand (or so I thought) how a scheme compiler could be done, in particular using the CPS transform to deal with tail calls and call-with-current-continuation. This got me interested in continuations and I studied Appel - Compiling with Continuations but I didn't write a compiler back then.
Since then I've read about Abstracting and Representing Control from Olivier Danvy and written metacircular interpreters that emit continuation semantics (pure lambda terms without any control operators). I also came to prefer delimited continuations rather than call-with-current-continuation and decided that I would like to implement those directly in my own compiler. I noticed that in Marc Feeley's compiler he was able to just use the continuation semantics of call-with-current-continuation as is because it's already in CPS form, on the other hand the continuation semantics for shift and reset are not in CPS form so this technique cannot be used: one would have to CPS transform twice to get the necessary metacontinuations - but this also causes a huge blowup in the number of lambda terms. So I studied other approaches to direct implementation of shift/reset:
In the end I felt like building a runtime for my compiler to target (in C) that handled delimited continuations was something I could add later on but for now I should forget about that (and if it was require in bootstrapping I had an easy way to interpret them), so I just used Matt Might's very clear and simple explanation of hybrid higher order CPS transform How to Compile with Continuations.
When the got the idea to write a self hosting scheme compiler I quickly wrote out a parser that's able to parse as much of scheme as I needed as well as the file itself. Then I initially came up with something very simple that just performed closure conversion: It was a surprise to me that this was basically enough to execute lambda using C procedures for code and vectors for their environment - it just lacked garbage collection and tail call elimination. I pushed on with this hoping lack of optimisations wouldn't be an issue ending up with a system that had one compiler pass per file as well, some utility functions and a script that chained them all together. This quite successfully compiles all the small simple scheme programs I gave to it (getting a program with the Y combinator to compile and run for the first time was very exciting!) but it just isn't good enough to bootstrap.
So I looked back a bit and read over Guy Steele's RABBIT paper and decided to start again from scratch. This time I started with a C runtime that had a simple two space copy and collect GC which uses the stack as the root - the stack itself is executed by a trampoline (a while loop that pops a continuation off the stack and calls it) and the continuations pop arguments off the stack, compute something with them then push a continuation onto the stack and return. I wrote some tests for the runtime: for example compiling recursive and iterative factorial functions by hand. The value of this approach is that you get tail call optimisation "for free" it only requires doing a CPS transform in the compiler.
So the overall architecture of the compiler is now:
after that actual C source code is emitted and some simple programs like an infinite lazy stream of fibonacci numbers do execute (with the correct space usage i.e. TCO and GC are working) - but when I started to head towards bootstrapping just adding a recursive definition of the EQUAL? function blow up horrible creating 40k lines of C.
Looking for more to read
I've looked for more modern things to read that might help me build a self hosting scheme compiler like:
and tried to find short readable implementations (studying real world compilers is just too hard since they are so complex and enormous)
but all in all I just don't know what I'm missing - I don't want to give up though because I think there's an important difference between understanding something and actually doing it. In particular I feel like I can't progress in my study of programming languages until I pass this block (I want to experiment with building compilers using Futamura projections like PyPy does after I complete this for one thing).
While waiting for my plane and thinking about a what a VHDL/Verilog killer would look like, I had a very (un!)original idea: describe what is to be done in English, and let the killer do the code derivation.
Here is an example of a description of how I want my blob detection (a computer vision application) be done on incoming images:
blob detection, image processing
This description is enough for a human to write the code, but not so for a computer, that has no understanding of any of these words.
Now my question is, is there anyone working on this?
To start working on this, here is what I want to do (in my spare time):
I like to hear your reasons on why it is or is not possible!
Hi all :)
I'm thinking about extending Wikipedia with a new page: Structured BNF. Is anyone interested in helping in changing content or lecturing it before I publish it? I would appreciate any comment, even if you think that this is not a thing to place in Wiki.
In Î»-calculus, all functions are unary, and n-ary functions are encoded through currying. But knowing the arity of a function can be useful for optimization â€” a curried function starts computing only after applying it to at least N arguments, and this N can be useful to know.
Below I explain the details.
Applications of arity:
But function arity is a tricky concept in Î»-calculus. For instance, id should be unary, Haskell's ($) is binary, but ($) is defined as equal to id:
($) :: (a -> b) -> a -> b
So, a notion of arity seems tricky, and one of my colleague keeps repeating it's a bad idea.
Today, while reading a paper using CBPV (Hammer et al. 2014), I got a hunch that the call-by-push-value (CBPV) lambda calculus seems to allow for a natural notion of arity. But Googling does not find this spelled out anywhere, maybe because CBPV seems typically used in theoretical contexts. I'm
So, why should CBPV help?
(1) It distinguishes values (A) and computations (C): Computations are either functions (A -> C) which take values and return computations, or base computations F A which wrap values in a "return" expression:
C ::= A -> C | F A
So, the return type of a function is wrapped by the F constructor. In particular, this distinguishes A1 -> A2 -> F A3 (a binary function) from A1 -> F (U (A2 -> F A3)), a unary function returning another unary function.
(2) Moreover, we also distinguish partial and full applications: since a full application produces a result of type F A, we need to use the elimination form for F.
Thus, after conversion to CBPV, we can distinguish syntactically between partial and full applications.
Liu, Y. A., and Teitelbaum, T. Caching intermediate results for program improvement. In Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation (New York, NY, USA, 1995), PEPM â€™95, ACM, pp. 190â€“201.
I would normally post this to G+, but I'm in a 3 day vacation weekend behind the great firewall, so here goes. Pursuing a CLOS submission on hackernews this morning, I came across an awesome quote in the comments section:
Many would find this very controversial, but it is increasingly true for younger programmers (and I've gotten into this habit myself). It has serious implications on programming language design: efficient feedback loops are much more important as design occurs more by doing than being done up front, functionality should be discoverable at least by searching. What else?
I am currently searching for anything that calls itself a "Database Programming Language", and in particular any reviews or helpful comparisons.
The purpose is something of a long term hobby project, non-commercial but also non-academic. I'm most interested in languages that have at least some prospect of finding users with real problems to solve and real data to manage, but I'm also interested in more esoteric ideas for their future prospects.
My list currently includes (no particular order) : Datalog, DBPL/Tycoon, Dataphor/D4, Tutorial D, Business System 12, Rel Project, Kleisli, Xduce, Links, Cduce. I would be interested to add to the list.
It would be helpful to know of any confirmed deaths. In particular, it's impossible to Google for Links. Does it live?
I'm working my way (slowly) through the C2 Wiki -- bit of a mixed blessing -- and I know about the DBPL conference and the DBLP bibliography site (confusing). Other resources would be appreciated too.
Call for Scholarship Applications: Programming Languages Mentoring Workshop - a POPL workshop (Deadline: September 19!)
CALL FOR SCHOLARSHIP APPLICATIONS (Deadline September 19!)
ACM SIGPLAN Programming Languages Mentoring Workshop, Mumbai, India
Wednesday, January 14, 2015
Co-located with POPL 2015
PLMW web page: http://plmw15.iisc-seal.net/
After the resounding success of the first three Programming Languages
The purpose of this mentoring workshop is to encourage graduate students
So far, we have the following speakers confirmed to speak at the
- Adam Chlipala (MIT)
We especially encourage women and underrepresented minority students to
This workshop is part of the activities surrounding POPL, the Symposium
A number of sponsors (listed below) have generously donated scholarship
Students attending this year will get one year free student membership
The workshop registration is open to all. Students with alternative
APPLICATION for PLMW scholarship:
The scholarship application can be accessed from the workshop web site
The reason for this early pre-registration has to do with obtaining
A kickstarter project. Abstract:
Programming as the basis of a magic system seems like a great idea, though I think the challenges would be in balancing (resource consumption of the spell must be restricted!).
A couple of weeks ago (the database LtU seems corrupted so I can't find the link) I posted about my theory of data parallel computing. I make a bunch of claims (not necessarily in that paper) why my idea can lead to more efficient software than some other parallel programming systems, and I was wondering why.
At some level, my Integrative Model for Parallelism is based on dataflow, as an Intermediate Representation, to be exact. And I think one reason dataflow approaches can be efficient is that the dataflow graph is a representation of the program in the program. By building up a dataflow graph, the program reconstructs a limited version of itself that can then be analyzed by a higher level tool than either the compiler or a traditional runtime.
My question to this esteemed audience: surely I'm not the first one to observe this. Is there a formalism, or at least a vocabulary to describe this phenomenon?
(Background info: I know that dataflow is a 1980, early 90s at best, phenomenon, but it's been in resurgence, with OpenMP tasks (OMP v3 and later), Intel TBB & CnC, and dedicated linear algebra software such as SuperMatrix and Quark. In all these cases the C/Fortran program creates a task graph out of ordinary function pointers and submits it to some scheduler which can be defined on a fairly high level, in a library itself written in C.)
Active forum topics
New forum topics