Showing posts with label scheme. Show all posts
Showing posts with label scheme. Show all posts

02 September 2013

Lambda

Playing with λ-calculus is fascinating. That everything we do with computers can be represented simply with unary functions is mind-blowing.

But when I think about it too much, I begin to doubt the applicability of λ-calculus to what we actually do in practice. We don’t use Church numerals. We use two’s compliment binary integers and IEEE floating-point and—when necessary—various arbitrary precision numbers. Our conditionals aren’t based on Church Booleans but on conditional instructions built into our microprocessors. Our lists may be built out of pairs, but our pairs aren’t functions. We don’t use the Y-combinator to express recursion; we simply give our functions names, which get turned into jumps.

Granted, closures in Scheme—much like functions in the λ-calculus—are used to build higher level features. (And, of course, the keyword for creating closures is “lambda” in reference to the λ-calculus.) But lots of the lower level stuff isn’t built from closures because it wouldn’t be efficient enough. (Could it be if the effort was made to design hardware for it?)

Edit: Here’s some example code.

03 June 2013

Scheme implementations

One of the difficulties in getting started with the Scheme programming language is picking an implementation. There are a bunch. Many of them are very good. Each has strengths and weaknesses. But those strengths and weaknesses don’t always readily line up with uses. So, recommending an implementation can be tricky.

Here is a pretty good guide to picking an implementation: “an opinionated guide to scheme implementations

I know a lot less about Scheme than (wingo). I just play with it and use it instead of Bash/Perl/Python/Ruby whenever I can at work. Still, I was a Scheme newbie once, so here’s my suggestion:

If you’re using Linux or BSD, check to see if Guile is installed. (If you’ve got Mac ports or fink installed on your Mac, you might fall into this category as well.) There are things I love about Guile, and there are things I hate about it. But it is hard to argue with it already being installed on your machine. Grab a copy of SICP or The Little Schemer or whatever and go...

If you’re on Linux or BSD and you don’t have Guile installed, check your package manager for it.

If you don’t have Guile or if you’re ready for something more than Guile, get Racket. While the people working on Scheme standards are trying to figure out how to please academics and pragmatists, Racket has built a Scheme that is good for learning/teaching the language and has much of the “batteries included” that some other languages claim you should expect.

If you want Racket but without the GUI bits, you’ll have to dig a bit for Racket Textual.

Once you’ve had a taste of Scheme with Guile and/or Racket, then you can start to delve into what makes all those other implementations unique.

18 May 2013

Fake call/values

For the programmers in the audience. Knowledge of Scheme is assumed.

(λ)

Lisping currently comes with TinyScheme. TinyScheme doesn’t support multiple return values (i.e. values and call-with-values). So, I did this...

;;; How to fake multiple return values
(define values list)
(define (call-with-values producer consumer)
  (apply consumer (producer)))

It was a bit surprising to me that it was that easy to fake.

This isn’t quite equivalent to the real values and call-with-values. e.g. Given a single argument, the real values function returns that argument, but my fake one returns a list instead. Which, in fact, broke another part of my code where I was using values as an identity function rather than for returning multiple values.

;;; The real values function
(values 5) → 5
;;; My fake values function
(values 5) → (5)

I imagine that real multiple return values can be more efficient than a list. On the other hand, it seems like a smart compiler could optimize-out the list in the fake version too.

Edit 21 May 2013: There is some interesting discussion here.

[...] Matthias Blume argued passionately against the presence of values/call-with-values in Scheme on the grounds that they add nothing to the language as a language—that is, they grant no additional expressiveness beyond what is already possible with list and apply [...]

The primary arguments in favour of values/call-with-values were that they allow implementors to optimise generated code in ways that are impossible or more difficult in the list/apply case.

17 May 2013

Lisping

Lisping is an iPad editor for the Scheme programming language (or Clojure). It is pretty much what I imagined in 2010 when I wrote about a Viaweb/RTML-style Scheme editor.

21 January 2013

My dream text editor and word processor

There’s a discussion on Branch about Your Dream Text Editor / Word Processor. I submitted an answer, but it won’t show up unless I get approved to join the branch. In fact, there doesn’t even seem to be a way for me to see what I wrote until/unless I get added to the branch. Weird. (But then it took me a while just to figure out how to add the branch to my Branch “drawer”.) So, it goes here too.

My dream text editor would be mostly like Vim, but with Scheme underneath.

I’ve had to work on enough systems where vi was the only practical editor that I found it easier to use Vim on the systems where I could install something more powerful. I’ve really come to like it except for its ad hoc scripting language. I’d envy the Emacs people except that I think elisp would just annoy me by being almost Scheme. ^_^

My dream word processor would be something akin to Amaya or UX Write. I want the output to be clean HTML. I want to be able to do semantic formatting as I write without having to type raw HTML, LaTeX, or Markdown.

Plus I’d like a high quality HTML to PDF/print converter. HTML+CSS has features that ought to allow generating LaTeX quality print.

07 December 2009

Prefix notation via closures

For the programmers in the audience...

Recently I’d read yet again someone saying that prefix notation is one of the things keeping more people from using Lisp. As I’ve said before, I find it hard to believe that this is an obstacle in practice. Especially since so many languages limit infix notation to essentially numbers (and only built-in numeric types at that) and Boolean values.

(Keep in mind that I’m saying this as someone who was raised on C rather than Lisp.)

Then I started thinking about the way that method invocation in many object-oriented languages is infixish. Consider Smalltalk: "hello" at: 3 Or Java: "hello".charAt(3) Or even: bigInt.add(anotherBigInt)

So, by using the closure-as-object idiom in Scheme...

(define (number-object-ctor n)
(λ (op arg)
  (if op
      (number-object-ctor (op n (arg #f #f)))
      n)))

(define (print-number-object n)
(display (n #f #f))
(newline))

(define x (number-object-ctor 4))
(define y (number-object-ctor 5))

(print-number-object (x + y))
(print-number-object ((x * x) + (y * y)))

It’s not as practical as an infix macro. I just thought it was interesting, however, that prefix notation could be twisted into infix notation that way.

12 November 2009

The problem with Javascript’s map

This is about Javascript programming. If you’re not interested in Javascript programming, bail now.

Say you have a Javascript array of strings that you want to convert to numbers.

['1', '2', '3'].map(parseInt) ⇒ [1, NaN, NaN]

Hmm. Why didn’t that work? Because parseInt takes an optional parameter (the radix)...

parseInt('ff', 16) ⇒ 255
parseInt('2', 1) ⇒ NaN // Because a radix of 1 always returns NaN
parseInt('3', 2) ⇒ NaN // Because 3 isn’t a valid binary digit

...and map passes an optional second parameter (the index).

[1, 2, 3].map(function(n, i) [n, i]) ⇒ [[1, 0], [2, 1], [3, 2]]

Occasionally it is very handy to have map give you that index. Often, however, I want to give map a function—like parseInt—that wasn’t explicitly designed to be used with map.

Here’s how to fix it.

['1', '2', '3'].map(function(_){return parseInt(_);});

Yuck. Not only is that verbose, it looks downright silly since the closure looks pointless.

Expression closures can address the verbosity...

array.map(function(_) parseInt(_));

..., but (currently) only Firefox versions 3.0 and later support that. Plus, it still obscures why you’re doing it.

In Scheme, I’d use cute from SRFI 26. It allows you to specify some parameters of a function. The “<>” is used for parameters that you don’t want to specify.

(map (cute string->number <> 10) '("1" "2" "3"))

Of course, while string->number takes an optional radix parameter like parseInt, Scheme’s map doesn’t pass the index, so this isn’t necessary.

Back to Javascript. A “unaryize” function looks nicer than an explicit closure and makes what you’re doing clearer.

function unaryize(f) {
return function(_) {
return f(_);
}
}

['1', '2', '3'].map(unaryize(parseInt)) ⇒ [1, 2, 3]

We could generalize unaryize to naryize.

function naryize(f, n) {
return function() {
return f.apply(null,
Array.prototype.slice.call(arguments, 0, n));
}
}

['1', '2', '3'].map(naryize(parseInt, 1)) ⇒ [1, 2, 3]

In practice, I’ve run into uses of unaryize several times, but I haven’t yet run into a need for naryize. Also, naryize is less efficient than unaryize.

What if we want to specify a radix? We could create a Javascript version of cute. I’ll use undefined instead of “<>” for the slot specifier.

function cute() {
var cutargs = Array.slice(arguments);
var f = cutargs.shift();
return function() {
var args = Array.slice(arguments);
var fargs = [];
var i;
for(i = 0; i < cutargs.length; ++i) {
if(undefined === cutargs[i]) {
fargs.push(args.shift());
} else {
fargs.push(cutargs[i]);
}
}
return f.apply(null, fargs);
};
}

['a', 'b', 'c'].map(cute(parseInt, undefined, 16)) ⇒ [10, 11, 12]

Again, I haven’t yet run into many cases where I’d want to use cute that unaryize doesn’t suffice. In this specific case, I think I’m happy with the explicit closure.

['a', 'b', 'c'].map(function(_){return parseInt(_, 16);});

Additional notes:

Array.map can be implemented in Javascript and added without any changes to the interpreter. I’m using Prototype’s.

Expression closures can’t be added without changes to the interpreter, but they can be faked with strings. See Functional Javascript

While cute can be implemented as a function, SRFI-26’s cut has to be a macro. Likewise, a cute macro is more efficient than the procedure implementation.

27 August 2009

A tale of two Schemes

The Scheme Steering Committee is going to try splitting Scheme into two languages. See their position statement.

The “split” language seems a little off, but the plan seems sound. The “large” language will be a superset of the “small” one, so it’s not like it is a complete fork.

I really have a hard time understanding the controversy. I suppose I’m in the target group of the “large” language, but I want to use a language that meets the expectations of the target group of the “small” language. I don’t see any reason why a single language and a single standard can’t serve both groups.

But it does make sense to separate the various concerns. There is no need to try to fit the core language and the standard libraries into a single effort. Building and ratifying them should be separate processes. In fact, I’d go farther and say that there shouldn’t be a single, monolithic set of standard libraries.

Which begins to look an awful like like R5RS + the SRFIs, huh? At least, if you squint a bit. There was certainly need for improvement, but R6RS seemed to have run off the rails a bit. I mean, it isn’t so bad, but it isn’t really what was needed.

Anyway, it’ll be interesting to see where things go from here. It looks like for the foreseeable future I’ll still be programming in PLT Scheme or Guile more than in any standard Scheme. (Not that I get time to do it much.)

21 May 2009

More on M.I.T. 6.001

See the previous post

My follow-up question that I meant to post: Assuming Sussman’s opinion is true, is this a practical assessment of an unfortunately reality? Or is the the natural evolution of software engineering?

Dan Weinreb has weighed in on the subject.

I absolutely agree with Dan’s point that the language is somewhat beside the point.

After reading his post, my question is: Should a university be teaching students things they will encounter in the field or things that they won’t encounter in the field?

My perspective on this has changed a lot between the time I entered college and now—after having dropped out and worked as a programmer for 15 years.

(I suspect M.I.T.’s answer may be: Both! This one course shouldn’t be used to characterize the entire program.)

26 March 2009

Scheme in the browser (again)

I found myself reading “Popularity” over at Brendan’s Roadmap Updates...again.

This time, a comment by Mike Ivanov stood out to me:

It took almost a decade for ‘average developer’ to grok JavaScript. Now it is understood, at least. How much time would pass before Scheme achieved the same level of acceptance? I bet forever.

Which again has me questioning that. I can’t believe that anyone who has really “grokked” Javascript couldn’t have grokked Scheme. After all, Javascript essentially is Scheme with C syntax. Grokking the language behind that syntax is much more difficult than grokking the syntax.

I think that Javascript was in a unique position. I suspect almost no-one learned Javascript for its own sake. People learned Javascript because it was (essentially) the only game in town for the role it played. (Indeed, it is still too difficult, IMHO, to use Javascript outside that role.)

That’s certainly why I learned it. At the time, I would’ve much rather used Perl, but my customers had Javascript built into their browsers. I wasn’t going to ask them to install client-side Perl.

Likewise, I suspect that Javascript is one of those languages that was the first programming language for a lot of people. Those are people who aren’t coming in with syntax-bias.

Which may be pointless speculation, but that’s what thinking-out-loud is for. I still give thanks to Brendan that I’m required to regularly, at work, program in Scheme/Self even if it is with C syntax.

24 March 2009

Why MIT 6.001 switched from Scheme to Python

From wingolog: international lisp conference—day two:

The “debate” had an interlude, in which Costanza asked Sussman why MIT had switched away from Scheme for their introductory programming course, 6.001. This was a gem. He said that the reason that happened was because engineering in 1980 was not what it was in the mid-90s or in 2000. In 1980, good programmers spent a lot of time thinking, and then produced spare code that they thought should work. Code ran close to the metal, even Scheme—it was understandable all the way down. Like a resistor, where you could read the bands and know the power rating and the tolerance and the resistance and V=IR and that’s all there was to know. 6.001 had been conceived to teach engineers how to take small parts that they understood entirely and use simple techniques to compose them into larger things that do what you want.

But programming now isn’t so much like that, said Sussman. Nowadays you muck around with incomprehensible or nonexistent man pages for software you don’t know who wrote. You have to do basic science on your libraries to see how they work, trying out different inputs and seeing how the code reacts. This is a fundamentally different job, and it needed a different course.

So the good thing about the new 6.001 was that it was robot-centered—you had to program a little robot to move around. And robots are not like resistors, behaving according to ideal functions. Wheels slip, the environment changes, etc—you have to build in robustness to the system, in a different way than the one SICP discusses.

And why Python, then? Well, said Sussman, it probably just had a library already implemented for the robotics interface, that was all.

SICP is the textbook, Structure and Interpretation of Computer Programs.

04 March 2009

My first quine

I’ve started trying some of the études at the Programming Praxis blog and came to A Self-Reproducing Program. I realized that I’d never actually attempted a quine before.

I decided to open DrScheme and just dive right into typing and see where it’d lead me. After a couple of false starts, I found myself with something like this:

#!r6rs
(define text '("#!r6rs\n(import (rnrs))\n(define text '(" ??? ")\n(for-each display text)"))
(for-each display text)

It then wasn’t far from there to...

#!r6rs
(import (rnrs))
(define text '("#!r6rs\n(import (rnrs))\n(define text '" #f
")\n(for-each(lambda(item)(if item(display item)(write text)))text)\n"))
(for-each(lambda(item)(if item(display item)(write text)))text)

Not particularly clever, but it works. I think my C background is showing.

The “answer” given at Programming Praxis is really an expression that evaluates to itself rather than a program that prints itself, which I suppose is more “Schemish”.

I then set about trying to modify it to be nicely formatted and to reproduce that formatting. That actually proved rather tricky without resorting to a pretty printing library.

Check The Quine Page for lots of quines.

05 February 2009

equal = pattern matching

Joe Marshall quoting (I believe) Gerry Sussman: “Pattern matching is a generalization of equality.”

Suddenly I’m much more comfortable with Scheme’s many forms of equality.

philosecurity—Interview with an Adware Author

Interview with an Adware Author is a fascinating read.

First off, he used the Scheme programming language. His Scheme code has run on possibly as many as 10 million personal computers. Looks like Scheme can be practical as well as academic.

Then there are insights into the shady business and the perspective that results.

S: How private is people’s information today?

M: Not at all.

S: Do you think that in our society we delude ourselves into thinking we have more privacy than we really do?

M: Oh, absolutely. If you think about it, when I use a credit card, the security model is the same as that of handing you my wallet and saying, “Take out whatever money you think you want, and then give it back.”

S: …and yet it seems to be working.

M: Most things don’t have to be perfect. In particular, things involving human interactions don’t have to be perfect, because groups of humans have all these self-regulations built in.

This, however, really struck me:

It really showed me the power of gradualism. It’s hard to get people to do something bad all in one big jump, but if you can cut it up into small enough pieces, you can get people to do almost anything.

08 April 2008

Scheme in the browser

The creator of JavaScript on it’s creation:

Brendan’s Roadmap Updates: Popularity

As I’ve often said, and as others at Netscape can confirm, I was recruited to Netscape with the promise of “doing Scheme” in the browser.

Interesting. I wish he hadn’t also had the mandate to give it Java-esque syntax.

I think. Sometimes, though, I almost think that I enjoy JavaScript more than Scheme.

12 January 2008

Scheme vs. Common Lisp

A Comparison Between Scheme and Common Lisp
Functions are really first class: Although Common Lisp is a functional language it makes programming functionally much harder than Scheme. For example to call a function that was returned as a result you have to use the funcall expression. Likewise special operations are required to access the function value of a variable. This seems unnecessary to me.
This is one of those things that has really bugged me whenever I’ve been tempted to use Common Lisp instead of Scheme.

Objective-C++

It has long seemed to me that C++ and Objective-C are very complimentary. It is interesting that they are actually very easy to combine. The result is known as “Objective-C++”. C++ is nice for “value” classes. i.e. Classes whose instances tend to the value of variables. Operator overloading is particularly nice for numeric classes or “smart” pointers. Exceptions are nice too. (Though I still wish C++ had “finally”. Yeah, I know the usual C++ alternative, but that doesn’t mean it can’t be convenient.) Objective-C is nice for “reference” classes. i.e. Classes whose instances tend to be referenced by pointer or reference variables. Add automatic garbage collection for the Objective-C objects, and you’ve got a really nice set of language features. Last I looked, just about all those pieces where there, but getting them to work together on whatever platform you’re on could be difficult. These days, though, I’m preferring vanilla C, Scheme, or even EcmaScript over C++ or Objective-C.

19 October 2007

Inheritance is over-rated

Some more observations based on my experiences with EcmaScript (a.k.a. Javascript) as compared to C++ and Java:

(I suppose I could try to generalize and consider EcmaScript a representative of the Smalltalk tradition versus C++ and Java as representatives of the Simula tradition; but that probably opens a lot of other issues.)

It occurs to me that most classes I’ve written in C++ or Java have not needed inheritance. They provided only encapsulation. (Which I can do just fine in C—no object-orientation required.)

When I have needed inheritance, it has most often been for polymorphism. In EcmaScript, you don’t need inheritance for polymorphism.

(With C++, you can have polymorphism without inheritance, but that requires the complexity of templates. Likewise, in Java you can use reflection to achieve the same sorts of things, but you get more complexity with it.)

Sometimes I’ve abused inheritance in C++ or Java to work around limitations. Such as adding additional methods to an existing class. In EcmaScript, I can add methods to objects (or objects serving class-like roles) directly.

In EcmaScript, I only really need to use inheritance when I need to share an implementation, and that just doesn’t seem to come up as often in my experience.

(Moreover, I find closures—which EcmaScript has but C++ and Java lack—extremely useful.)

Now, there are—of course—trade-offs involved. EcmaScript isn’t all roses by any means. Give it a static debugger (like MrSpidey/MrFlow), and I think it could hold its own versus C++ or Java for many applications.

Give it hygienic macros (on the road-map for Javascript 3) and first-class continuations, and it starts to stack up well against Scheme as well.

08 October 2007

EcmaScript, IF, and DSLs

Since I’ve been programming so much in EcmaScript (a.k.a. Javascript) at work, I decided to install the stand-alone version of Spidermonkey at home. That’s the EcmaScript implementation from Firefox. Partly because I’m interested in being able to write web applications that use the same language on both the browser-side and the server-side.

Of course, there are a few server-side EcmaScript solutions out there, but I’m used to rolling my own light-weight version when investigating such things.

I didn’t want to jump right into that, however, so I tried to come up with an idea for a command-line program I could start with. Spidermonkey comes with a command-line interpreter, but it is very minimal. Hardly more than readline and print.

So, I thought of text adventures (a.k.a. interactive fiction). I had the basics of Cloak of Darkness mocked up PDQ. It went faster and farther than I think any of my other attempts at such a program has gone in any language. My opinion of the EcmaScript is continuing to increase. I began to think I should break out some of my old text adventure ideas.

The thing is, though, I’d have to make some significant enhancements to Spidermonkey’s command-line interpreter to really make it practical for IF. It would make a lot more sense to just use browser-based EcmaScript (instead of command-line) or to use Inform, so that people besides just me could actually play it.

Inform is a DSL (domain specific language) for interactive fiction. That’s fancy computer geek jargon for a language specialized for a specific purpose.

C, C++, Java (no relation to Javascript), Perl, Python, Ruby, Lisp, and Scheme are general-purpose programming languages. They can be used to build programs for a wide range of applications. (Although, certainly, some are better for some applications than others.)

HTML and Postscript are domain specific languages. (Incidentally, HTML is not a programming language, but Postscript is.)

EcmaScript isn’t really a domain specific language, but as it is most widely and most easily used within web browsers, it often tends to be one in practice.

I’m all for DSLs, but the problem I have with most of them is that they’re wholly new languages. Ideally, a DSL—unless really simple—should be an extension or a subset of an existing language. This is the resistance I have towards using Inform.

The Lisp and Scheme advocates like to point out how they often extend their languages to create DSLs within them, which I’m finding to be a very compelling argument.