LtU Forum

Higher abstraction through NLP and automatic code derivation?

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
- connect neighboring high-intensity pixels
- high-intensity - values exceeding a threshold
- neighboring pixels of an image
- 8 pixels surrounding the pixel in question
- image is a 2d array of pixels, variable width and height
- pixels come one by one
- pixels are 8 bits, but can be larger
- threshold is variable at run time
- use png files as test images

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?
If not---why not?

To start working on this, here is what I want to do (in my spare time):
- P. Norvig's PAIP has a chapter about solving simple math questions written in English. That's my starting point to derive some sort of meaning from English language description.
- Get from meaning to code. Probably, I will have to search through a code space to satisfy the meaning derived.

I like to hear your reasons on why it is or is not possible!

New Wiki about Structured Backus-Naur Form?

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.

here is the content

Function arity with currying and call-by-push-value

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.
It seems that call-by-push-value(CBPV) allows dealing with arities in a convenient way, as discussed below, though that was not the main design goal. My questions are:

  1. Is this true?
  2. Is this already known?
  3. Would you recommend call-by-push-value, or are there downsides which make it unsuitable?

Below I explain the details.

Applications of arity:
(1) In GHC, that's useful to deal differently with partial applications — because e.g. a function body only computes after specifying enough arguments (in simple cases, that is barring some optimizations, as many arguments as specified in the left-hand side of the equations defining the function).
(2) In my case, I'm working on a program transformation: transforming a function f gives a function f* that returns f's final result and all its intermediate results. This can be useful for incremental computation (along ideas by Liu and Teitelbaum (1995)). Here, too, it seems silly to return intermediate results of a partial application.

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
($) = id

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.
U is a type constructor for values representing thunks.

(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.

- is this a good way to define a notion of arity?
- would it be better to just introduce multi-argument functions? I suspect not, because those prevent abstracting over arity, while CBPV you can still write forall A B. (A -> B).
- does the translation have downsides? I imagine that ($) = id transforms to something more complicated in CBPV, which would involve (the equivalent of) a full eta-expansion first.
- The GHC core language does have a notion of arity, but it does not seem as elegant as far as I can tell.
- is there an extension of CBPV to calculi richer than STLC, say to System F? I've heard people saying that focusing and polarity runs into some form of trouble with System F, but I haven't heard why. Interestingly, Levy's own paper dealing with System F ( does not use CBPV, but Jump-With-Argument.


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.
Hammer, M. A., Phang, K. Y., Hicks, M., and Foster, J. S. Adapton: Composable, Demand-driven Incremental Computation. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (New York, NY, USA, 2014), PLDI ’14, ACM, pp. 156–166.

Programming by page faulting

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:

I'm a fan of reading the ****ing manual and thus you're preaching to the choir on that. But I'm not an evangelical baptist about it. Truth is that most people program by page faulting - writing some code, hitting a bug, and googling for a solution, lather rinse repeat.

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?

Database programming language review

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!)


ACM SIGPLAN Programming Languages Mentoring Workshop, Mumbai, India

Wednesday, January 14, 2015

Co-located with POPL 2015

PLMW web page:

After the resounding success of the first three Programming Languages
Mentoring Workshops at POPL 2012, 2013, and 2014, we proudly announce
the 4th SIGPLAN Programming Languages Mentoring Workshop (PLMW),
co-located with POPL 2015 and organised by Derek Dreyer, Aditya Kanade,
Ruzica Piskac, Alan Schmitt, and Ross Tate.

The purpose of this mentoring workshop is to encourage graduate students
and senior undergraduate students to pursue careers in programming
language research. This workshop will provide technical sessions on
cutting-edge research in programming languages, and mentoring sessions
on how to prepare for a research career. We will bring together leaders
in programming language research from academia and industry to give
talks on their research areas. The workshop will engage students in
a process of imagining how they might contribute to our research

So far, we have the following speakers confirmed to speak at the
workshop, and we expect about 7 additional speakers as well:

- Adam Chlipala (MIT)
- Sumit Gulwani (Microsoft Research)
- Mike Hicks (University of Maryland, College Park)
- Shriram Krishnamurthi (Brown)
- Matt Might (University of Utah)

We especially encourage women and underrepresented minority students to
attend PLMW.

This workshop is part of the activities surrounding POPL, the Symposium
on Principles of Programming Languages, and takes place the day before
the main conference. One goal of the workshop is to make the POPL
conference more accessible to newcomers. We hope that participants will
stay through the entire conference.

A number of sponsors (listed below) have generously donated scholarship
funds for qualified students to attend PLMW. These scholarships should
cover reasonable expenses (airfare, hotel, and registration fees) for
attendance at both the workshop and the POPL conference.

Students attending this year will get one year free student membership
of SIGPLAN, unless they prefer to opt out during their application.

The workshop registration is open to all. Students with alternative
sources of funding are welcome.

APPLICATION for PLMW scholarship:

The scholarship application can be accessed from the workshop web site
( The deadline for full
consideration of funding is FRIDAY, SEPTEMBER 19. Selected participants
will be notified by OCTOBER 1 or earlier, and will need to pre-register
for the workshop (i.e. declare intent to attend) by OCTOBER 10. Note
the early date!!

The reason for this early pre-registration has to do with obtaining
visas for travel to India. To apply for a “conference visa”, all
attendees of POPL and PLMW must register their intent to attend the
event by October 10. More details concerning the visa application
process will be provided soon.


Jane Street Capital


A kickstarter project. Abstract:

CodeSpells revolves around the idea of crafting your own magical spells to interact with the world, solve problems, and fight off foes. To do this, we’ve created an intuitive, sleek coding interface using a drag-and-drop Javascript-based language. This interface is designed for individuals (young and old) who want to learn coding for the first time. Skilled coders will also enjoy using their coding skills in new and creative ways! Players will be able to craft their own spells to build mountains, make an impenetrable force field around your character, or even make a golem creature out of the surrounding rocks. The sky is the limit!

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!).

Program in a program

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.)

SPLASH 2014 - Call For Participation

ACM Conference on
Systems, Programming, Languages, and Applications:
Software for Humanity (SPLASH'14)

Portland, Oregon, USA
20-24 October, 2014

Sponsored by ACM SIGPLAN


The ACM SIGPLAN conference on Systems, Programming, Languages and Applications: Software for Humanity (SPLASH) embraces all aspects of software construction and delivery to make it the premier conference at the intersection of programming, languages, and software engineering. SPLASH is now inviting calls for participation.

19 September 2014 (Early Deadline)


** KEYNOTE Speakers **
Gary McGraw (Cigital): Software Security — A Study in Technology Transfer
Peter Norvig (Google): Machine Learning for Programming
Bret Victor (WorryDream): Humane Representation of Thought: A Trail Map for the 21st Century

** OOPSLA Research Papers**
Papers that address any aspect of software development are welcome, including requirements, modeling, prototyping, design, implementation, generation, analysis, verification, testing, evaluation, maintenance, reuse, replacement, and retirement of software systems. Papers may address these topics in a variety of ways, including new tools (such as languages, program analyses, and runtime systems), new techniques (such as methodologies, design processes, code organization approaches, and management techniques), and new evaluations (such as formalisms and proofs, corpora analyses, user studies, and surveys).

** Onward! Research Papers **
Onward! is a premier multidisciplinary conference focused on everything to do with programming and software: including processes, methods, languages, communities, and applications. Onward! is more radical, more visionary, and more open than other conferences to ideas that are well-argued but not yet proven. We welcome different ways of thinking about, approaching, and reporting on programming language and software engineering research.

** Onward! Essays **
Onward! Essays is looking for clear and compelling pieces of writing about topics important to the software community. An essay can be an exploration of a topic, its impact, or the circumstances of its creation; it can present a personal view of what is, explore a terrain, or lead the reader in an act of discovery; it can be a philosophical digression or a deep analysis. It can describe a personal journey, perhaps that by which the author reached an understanding of such a topic. The subject area should be interpreted broadly and can include the relationship of software to human endeavors, or its philosophical, sociological, psychological, historical, or anthropological underpinnings.

** Dynamic Languages Symposium (DLS) **
DLS is the premier forum for researchers and practitioners to share knowledge and research on dynamic languages, their implementation, and applications. The influence of dynamic languages — from Lisp to Smalltalk to Python to Javascript — on real-world practice, and research, continues to grow. We invite high quality papers reporting original research, innovative contributions, or experience related to dynamic languages, their implementation, and applications.

** Wavefront **
The SPLASH Wavefront track is looking for presentations and technology talks of interest to the software community, particularly to software professionals working in companies large and small. Wavefront is a forum for presenting experience reports and tutorials about innovative tools, technologies, and software practices.

** Panels **
The Panels track offers exciting discussion about topics related to SPLASH.

** SPLASH-E **
The SPLASH-E track brings together researchers and educators to share educational results, ideas, and challenges centered in Software and Programming Languages. Submission formats vary, including papers, tool demos, lightning talks, challenge-topics for discussion, and suggested themes for "unconference" sessions. Help us create an engaging forum for educational issues related to SPLASH!

** Artifacts **
The Artifact Evaluation process is a service provided by the community to help authors of accepted papers provide more substantial supplements to their papers so future researchers can more effectively build on and compare with previous work. The Artifact Evaluation Committee has been formed to assess how well paper authors prepare artifacts in support of such future researchers. Roughly, authors of papers who wish to participate are invited to submit an artifact that supports the conclusions of the paper.

** Workshops **
The SPLASH Workshops track will host a variety of high-quality workshops (14 in total), allowing their participants to meet and discuss research questions with peers, to mature new and exciting ideas, and to build up communities and start new collaborations. SPLASH workshops complement the main tracks of the conference and provide meetings in a smaller and more specialized setting. Workshops cultivate new ideas and concepts for the future, optionally recorded in formal proceedings.

** Tutorials **
The SPLASH Tutorials track will consist of prestigious tutorials on current topics in software, systems, and languages research. The scope of the tutorials is the same as the conference itself: all aspects of software construction and delivery at the intersection of programming, languages, and software engineering. The tutorials in particular focus on the nexus between research and practice, including work that takes inspiration from or builds connections to areas not commonly considered at SPLASH. Tutorials should introduce researchers to current research in an area, or show important new tools that can be used in research.

** Demos **
The SPLASH Demonstrations track is an excellent vehicle for sharing your latest work with an experienced and technically savvy audience. Live demonstrations show the impact of software innovation. Demonstrations are not product sales pitches, but rather an opportunity to highlight, explain, and present interesting technical aspects of running applications in a dynamic and highly interactive setting. Presenters are encouraged to actively solicit feedback from the audience, which should lead to very interesting and entertaining demonstration sessions.

** Posters **
The SPLASH Poster track provides an excellent forum for authors to present their recent or ongoing projects in an interactive setting, and receive feedback from the community. We invite submissions covering any aspect of programming, systems, languages and applications. The goal of the poster session is to encourage and facilitate small groups of individuals interested in a technical area to gather and interact. It is held early in the conference, to promote continued discussion among interested parties. Posters can be independent presentations or associated with one of the other parts of SPLASH.

** Doctoral Symposium **
The SPLASH Doctoral Symposium provides students with useful guidance for completing their dissertation research and beginning their research careers. The Symposium will provide an interactive forum for doctoral students who have progressed far enough in their research to have a structured proposal, but will not be defending their dissertation in the next 12 months.

** Student Research Competition **
The ACM SIGPLAN Student Research Competition (ACM SRC) is an internationally-recognized venue that enables undergraduate and graduate students to experience the research world, share their research results with other students and SPLASH attendees. The competition has separate categories for undergraduate and graduate students and awards prizes to the top three students in each category. The ACM SIGPLAN Student Research Competition shares the Poster session’s goal to facilitate interaction with researchers and industry practitioners; providing both sides with the opportunity to learn of ongoing, current research.

** Co-located Events **

ACM SIGAda’s Annual International Conference High Integrity Language Technology (HILT)

Multicore Parallel Programming Course:
- Offers experienced programmers an opportunity to learn about multicore programming and gain mastery of cutting-edge parallel programming tools.
- Contact: Danny Dig:

** Location **

Portland Marriott
Downtown Waterfront Hotel
Portland, Oregon, USA

** Organization **

SPLASH General Chair: Andrew Black (Portland State University)
OOPSLA Papers Chair: Todd Millstein (University of California, Los Angeles)
Onward! Papers Chair: Shriram Krishnamurthi (Brown University)
Onward! Essays Chair: Bernd Bruegge (TU Munich)
DLS Papers Chair: Laurence Tratt (King’s College, London)
SPLASH-E Chair: Kathi Fisler (Worcester Polytechnic Institute)
Wavefront Co-Chairs: David Archer (Galois) and Dennis Mancl (Alcatel-Lucent)
Artifacts Co-Chairs: Matthias Hauswirth (university of Lugano) and Robby Findler (Northwestern University)
Workshop Co-Chairs: Stephanie Balzer (Carnegie Mellon University) and Du Li (Carnegie Mellon University)
Tutorials Chair: James Noble (Victoria University of Wellington)
Demos Chair: Floreal Morandat (Enseirb-Matmeca)
Posters Co-Chairs: K R Jayaram (IBM Research) and Nick Sumner (Simon Fraser University)
Doctoral Symposium Chair: Lukasz Ziarek (State University of New York, Buffalo)
Student Research Competition Co-Chairs: Isil Dillig (University of Texas, Austin) and Sam Guyer (Tufts University)
Student Volunteer Co-Chairs: Jonathan Bell (Columbia University) and Darya Kurilova (Carnegie Mellon University)
Publicity and Web Chair: Craig Anslow (University of Calgary)
Web Technology Chair: Eelco Visser (Delft University of Technology)
Publications Chair: Joseph Ruskiewicz (Portland State University)
Student Mentoring Chair: Carlos Jensen (Oregon State University)
Mobile App Chair: Reid Holmes (University of Waterloo)

Patent on "safe" transitive immutability for object types — prior art?

Apparently, Microsoft applied for a patent on "safe" transitive immutability for object types. I use "safe" to summarize a useful feature: even though object constructors can set fields of an immutable object, the mutable reference to this cannot escape the constructor and become visible to other code. I say "transitive" because contained objects are immutable even though their types would be mutable.

  • On, people asked for prior art on this patent application. The question listed some obvious answers, including functional languages (ML, Scala, Rust), but most seem not to be for transitive immutability (except D), or not necessarily to be safe. IANAL, but it seems to me that prior art must match pretty tightly with the content of the patent claims, so one would probably need prior art on a combination with both features.
  • A curiosity: Is is common to apply (and get) patents for PL features? As a researcher in the field, should I worry about patent infringement?

Patent abstract:

A language extension that advances safety in system programming in that an entire type may be declared to be immutable in the case in which all instances of that type are immutable. The immutable type declaration automatically causes any instances of that type to be treated as immutable, and automatically causes all directly or indirectly reachable members (e.g., fields, methods, properties) of the instance to also be treated as immutable. Furthermore, any construction time reference that allows for field assignment of the instance is not permitted to survive beyond the point at which the instance becomes accessible to its creator. Accordingly, this instance, and any other instance of that same type, will be immutable from the very time of construction. The ability to classify all such instances as immutable is beneficial as the immutable characteristic permits actions that normally would not be allowed due to resource access safety.

XML feed