Tag: Programming Language

Cross-compiling Java to Objective-C for the iPhone

It seems that you can cross compile Java to Objective-C on the iPhone. I didn’t dig any deeper than that.
Here is the blurb for the technologies used:

The goal of XMLVM is to offer a flexible and extensible cross-compiler toolchain. Instead of cross-compiling on a source code level, XMLVM cross-compiles byte code instructions from Sun Microsystem’s virtual machine and Microsoft’s Common Language Runtime. The benefit of this approach is that byte code instructions are easier to cross-compile and the difficult parsing of a high-level programming language is left to a regular compiler. In XMLVM, byte code-based programs are represented as XML documents. This allows manipulation and translation of XMLVM-based programs using advanced XML technologies such as XSLT, XQuery, and XPath.

Apple’s iPhone has generated huge interest amongst users and developers alike. Like MacOS X, the iPhone development environment is based on Objective-C as the development language and Cocoa for the GUI library. The iPhone SDK license agreement does not permit the development of a virtual machine. Using XMLVM, we circumvent this problem by cross-compiling Java to the iPhone. Just like a Java application can be cross-compiled to AJAX, XMLVM can be used to cross-compile a Java application to Objective-C. The cross-compilation is also accomplished by mimicking a stack-based machine in Objective-C. Consider the instruction (integer remainder) that pops two integers off the stack and pushes their remainder after division back onto the stack. Using the following XSL template, the instruction can be mapped to Objective-C.

(via the PLT Mailing List)

How to handle large data in DrScheme

In the PLT discussion list thread titled “How to handle large data”, Kenichi wanted to load a very large file into DrScheme, 120,000 lines long, and it was hanging. Noel explained that because of debugging and performance instrumentation, DrScheme adds a lot of overhead, and that MzScheme could load the file just fine. Eli explained that DrScheme’s overhead could be made much smaller by making the contents of that file one big piece of quoted data, and that the overhead could be completely eliminated by putting the data in a file and then loading it.
The following code is a generalization of the two approaches that he described there, which were tailored to Japanese postal data.

(define info-list-data
  '(("Alpha" "Bravo" 1)
    ("Delta" "Echo" 2)))
(define-struct info (fname lname budget))
(define (info-data->info entry)
  (make-info (first entry) (second entry) (third entry)))
(define info-list
  (map info-data->info info-list-data))
(define info-list-from-file
  (map info-data->info
       (call-with-input-file "data-overhead-elimination.data" read)))
(display "Total budget: ")
(display (apply + (map (λ (info) (info-budget info)) info-list-from-file)))
(newline)

All Scheme Search

All Scheme Search is a Google based search engine for “Everything about the Scheme Programming Language”.
If seven pages of search results for “keyword arguments” is any measure, this looks pretty interesting :).
Addendum: 01/05/08
Here are two more: Scheme from the Florida Keys (actively updated) and Search PLT Scheme (not actively updated).

Automata via Macros

Last year I asked a question about Automata via Macros to the PLT Discussion List. The paper is about an extended example of a problem posed by Shriram Krishnamurthi at the Lightweight Languages 1 conference. I was trying to understand how one might use the same FSA language to generate different outputs. Many folks explained how that would work and the thread finished. It didn’t finish for me, though. To say my understanding of the solution was superficial would be an overstatement. I knew I didn’t “get it”, and kept it on my list to revisit once I had a better grasp on things. That was a year and a half ago.
Over my holiday I revisited the paper and found, for lack of a better way to say it, that it “made sense”. In the past year I’ve tried to: read a lot, write a lot of code, read other people’s code, and most importantly do so with some discipline and attention to detail that I had not applied before. That seems to have paid off; as it felt like I was reading the paper with brand new eyes.
This time around, I also listened to a recording of the presentation itself and watched the PowerPoint that went along with it. This was especially valuable because it drew attention to various tidbits that appeared in the paper but were much easier to delineate by virtue of Shriram pointing them out in context of the presentation. It was those comments, along with what I had learned in the past year that really got me thinking about things again.
In a conversation with Aaron Hsu, he once said something to the effect that “Scheme is hard because it is subtle.”, and that sort of rang true with my intuition, but I had a difficult time verbalizing exactly why I thought that to be true. Outwardly Scheme appears to be “simple”, but the more you learn about it and the deeper you dig, you start to see that it is Deceptively Simple.
Scheme seems to take only a few days to learn, but a few years to master; but why? I don’t know yet, but what I do know is that some of the ideas and topics presented in this paper and presentation are surely some of the aforementioned “subtleties” that serve as landmarks on this multi-year path towards understanding Scheme. For my own reference, and for others who may be studying Scheme and wondering exactly why “Subtlety is hard”, perhaps this paper will serve to shed some light on things.
My advice: read LAMBDA: The Ultimate Imperative and LAMBDA: The Ultimate GOTO first.

Abstract

Lisp programmers have long used macros to extend their language. Indeed, their success has inspired macro notations for a variety of other languages, such as C and Java. There is, however, a paucity of effective pedagogic examples of macro use. This paper presents a short, non-trivial example that implements a construct not already found in mainstream languages. Furthermore, it motivates the need for tail-calls, as opposed to mere tail-recursion, and illustrates how support for tail-call optimization is crucial to support a natural style of macro-based language extension.

Key notes from the audio

These are mostly my notes and summaries for some key points that rang true with me. The ideas that they represent may or may not be contained within my summary as it would be too far outside the scope of this blog post to address them. Such work is better done by other papers and presentations.

  • 09:00: Without the hidden gems, syntax, macros, and tail calls, it all falls apart.
  • 11:16: What you generate must fit well into the language.
  • 18:00: It is really tail-transfer (tail-calls) that matter, not tail-recursion.
  • 21:00: Scheme is really an indentation based language.
  • 23:00: Macro languages belong in modules; you can use your data (DSL) where you wish.
  • 25:30: If you claim to be smart, leverage the work of others.
  • 26:10: Scheme is subtle. Takes years to understand what is beautiful. You can look at a book but you won’t notice. The language hides it jewels.
  • 26:45 If you don’t get tail calls, you don’t get it.

Key notes from the paper

  • P2P3: “A macro gives the programmer a consistent, representation-independent means of describing the datum
    while still resolving the representation before compilation.”
  • P7P4: Macros are likely to be used to optimize the abstraction that the data represents.
  • P8P3: Scheme’s macro system could be called “a lightweight compiler API”.
  • P9P2: Tail-calls ought to be called tail-transfer per Steele. I wonder why they didn’t push that definition more.
  • P9P3: Here is a good explanation of tail calls.
  • P9P5: “languages represent the ultimate form of reuse, because we get to reuse everything from the mathematical (semantics) to the practical (libraries), as well as decades of research and toil in compiler construction (Hudak, 1998).”
  • P13P2: “it shows how features that would otherwise seem orthogonal, such as macros and tail-calls, are in fact intimately wedded together; in particular, the absence of the latter would greatly complicate use of the former.”

The automaton language

; An automaton that recognizes the language c(ad)*r
(define m
  (automaton init
             (init :
                   (c → more))
             (more :
                   (a → more)
                   (d → more)
                   (r → end))
             (end : accept)))

Dynamically avoiding duplicate identifiers in PLT Scheme

In this thread on the PLT discussion list, the original poster was encountering a problem while implementing a DSL where definitions were getting defined more than once in the code that he was generating. The problem is that the define function will not define the same name twice:

(define x 10)
(define x 12)
=> duplicate definition for identifier in: x

The solution would be to check if the given name is already bound before defining: if it was not defined, the define function should be used, otherwise the set! function should be used:

(define x 10)
(set! x 12)

Here is Andre’s solution from the thread:

(define-syntax define-if-not
  (λ (stx)
    (syntax-case stx ()
      [(_ var val)
       (with-syntax ([set!define (if (identifier-binding #'var 0)
                                      #'set!
                                      #'define)])
         (syntax
          (set!define var val)))])))

identifier-binding returns true unless the name is a top level binding or is not bound at all. If the name is already bound, use set!; otherwise use define.

Undergrad Scheme Projects

Fred Martin wrote to the PLT Discussion List that:

You may have noticed a number of emails from my students at UMass Lowell. I had assigned a final project in our required “Organization of Programming Languages” course which is based on the SICP text. This is the first time that the course included a significant, independent project component, and I did encourage them to ask you for assistance.
I am happy to report that the projects were wildly successful.

Here are some of the projects:

(via PLT Discussion List)
Addendum: 01/09/09
Today, in the original thread, Fred replied to some interesting questions about the projects:

Hi everyone,
This is a belated reply to Eric Tanter and Shriram Krishnamurthi’s
questions about how I structured student projects in my last
semester’s junior-level PL course, which was based on Scheme and SICP.
This was the first time that students were required to do projects in
our undergrad PL course, and they were quite successful. Since I
wrote last, I graded the projects. Broadly, I’d categorize them as
1/3 excellent, 1/3 decent, and 1/3 weak (I suppose that’s a normal
distribution of anything we do…). But that’s still 2/3 of students
really exercising ideas in Scheme and PLs (functional programming,
map/filter, recursion) for their own purposes, which I think could be
quite valuable in the long run.
from Eric:
> Can you tell us more about how the projects
> were conceived? did they all pop up out of students’ mind, if so,
> under which guidelines if any? or did you have a pool of project ideas?
I started out by telling them about the project on the first class
meeting, letting students know that the project would be worth 25% of
their overall grade (the final exam was only worth 20%!). Here’s what
I wrote in the syllabus:
“In the final project, you will apply the ideas developed in the class
in an original software implementation. You may thus connect the ideas
of the class with your own interests—music, robotics, art, databases,
the web, networking, gaming, etc. The learning goal of the project is
to have you find some real-world relevance of the ideas in the class.”
Then, during the semester, I showed/mentioned real-world projects done
in Scheme. I showed a movie of the real-time
writing-scheme-code-as-a-musical-performance work done by the Impromtu
team in Australia http://impromptu.moso.com.au/gallery.html. I
discussed FP techniques practiced by Jane St. Capital, a Wall St
trading firm, http://portal.acm.org/citation.cfm?id=1394798.
In early November, I assigned preliminary work: students had to
download and play with at least two different libraries from the
PLaneT repository. I demonstrated in class the HTTP Get library. We
also talked in class about project ideas, including the robotics,
gaming, and networking concepts that ultimately students implemented
(most networking stuff they did went far beyond any class
discussions).
Just before Thanksgiving, their project proposal was due. This was
supposed to be based on the exploratory work they had already
completed (and in many cases, it was). In giving them the guidelines
for the proposal document, I also gave them the grading criteria for
the final project. These were:
* an explicit connection to ideas that were introduced in the course
* an explicit connection to some outside piece of technology (e.g.,
images, sound, networking, database, etc)
* an interesting overall concept
* something that you personally are interested in and care about
* a writeup that explains what you accomplished
* a demo that lets people (or yourself) interact with your project
They had 2.5 weeks after the Thanksgiving holiday to work on their
projects for real. In class, I was covering the metacircular
interpreter, and they had a problem set on this that was due 5 days
AFTER the project deadline had passed. (This was a bit squeezed.)
I used the final class meeting date for a project open-house, which
was set up in our department’s main lobby. I provided drinks and
snacks for that, and we had a decent turnout, including several other
faculty.
To me, the best projects were ones where students really did connect
Scheme and the course’s ideas to something of personal interest. As I
look back over the project list, I’d say that in more than half of the
projects, students really did something they were interested in, and
made explicit connections in their implementations to course material.
(A number more did have the conceptual connections, but the thematic
matter was not really something the student was passionate about.)
As an example of a success story, there was a project where a student
imported baseball stats from a public web site into Scheme via XML
translation. A number of students did stuff with XML, but this one
stood out because the student really cared about the baseball data.
He was really excited that he was able to reveal data that the web
site had collected, but did not make available in its standard web
presentation. The project was not as advanced as some others, but
because of the student’s true interest in the material, it was quite
well done.
(All the projects are written up at
http://www.cs.uml.edu/ecg/index.php/OrganizationProgrammingLanguagesFall2008/Project)
Onto Shriram’s questions:
> – This is an impressive list of projects, but how much evaluation was
> there of how well they did what they promised?
At the public demo day, I visited each project and had a 5-minute
conversation with each student, taking quick notes. Then students
turned in their code, with additional documentation explaining it
(e.g., drawing out the ways their code exemplified ideas in the
class). (BTW – I didn’t make them post the code and notes on their
public project web pages.)
I graded their projects based on the criteria previously discussed
with them, with separate marks for: the quality of the proposal,
explicit connection to course concepts, use of external technology, an
innovation/creativity mark, the final writeup, and the quality of the
live demonstration.
I was lenient with the “did they do what they promised.” In fact, I
had told them that up front: if you end up getting stuck or otherwise
needing to go in a different direction than you described in your
proposal, that was fine. But I still used the same rubric for grading
(I just didn’t penalize if it was different than the proposal).
> – How good is their code? What’s the measure of goodness? Did they
> get administered code-walks?
This is a good/hard question. As I mentioned earlier, one of my star
students commented that now he understood what people meant when they
were talking about “elegant code,” and that he wanted to go back and
re-write code he had written in the past (code that was not written in
Scheme). This was the person who built a hash table of lambda
functions to process a variety of possible reply packets from a
serially-connected hardware device.
So, to answer — no there wasn’t an administered code-walk. That’s a
great idea — I wish I had time for that. I did however read through
all of their code, and sync’ing that with their documentation notes,
was able to determine what kind of ideas they worked through in their
implementations. This was the basis of the grading, particularly for
the “connection to course concepts” category.
One of the additional benefits of the project from my vantage point is
that it gave me a brand-new window into my students’ abilities. From
quiz scores and class participation, I could tell that about 1/3 of
the class was strong, and 1/3 was weak, but there was the middle band
that I was mentally lumping with the “weak” category — they didn’t
speak up in class, and their quiz scores were not great.
But from the projects, a bunch of this middle band really shined, and
I gained new appreciation for them. As it turned out, they *were*
paying attention, and through the project, really engaged with the
class material.
So I’ll definitely be running the projects again when I teach the
course in the spring. I should be able to do a better job working
through the main curriculum so that the metacircular material (which
is clearly central) isn’t so squeezed at the end. Hopefully too I’ll
be able to establish the value of the projects in my colleagues’ eyes
so they have a chance of living beyond my tenure with the course.
There’s one more Q&A below — it’s somewhat of a digression on
integrating Scheme and C++, so I’ll end this note here and leave it as
a P.S.
Thanks again everyone for your attention and encouragement.
Fred