The Little Schemer

Daniel P. Friedman, Matthias Felleisen

Mentioned 33

"drawings by Duane Bibby" foreword by Gerald J. Sussman "I learned more about LISP from this book than I have from any of the other LISP books I've read over the years. . . . While other books will tell you the mechanics of LISP, they can leave you largely uninformed on the style of problem-solving for which LISP is optimized. The Little LISPer teaches you how to think in the LISP language. . . an inexpensive, enjoyable introduction." -- Gregg Williams, Byte The notion that "thinking about computing is one of the most exciting things the human mind can do" sets both "The Little Schemer" (formerly known as "The Little LISPer" ) and its new companion volume, "The Seasoned Schemer," apart from other books on LISP. The authors' enthusiasm for their subject is compelling as they present abstract concepts in a humorous and easy-to-grasp fashion. Together, these books will open new doors of thought to anyone who wants to find out what computing is really about. "The Little Schemer" introduces computing as an extension of arithmetic and algebra -- things that everyone studies in grade school and high school. It introduces programs as recursive functions and briefly discusses the limits of what computers can do. The authors use the programming language Scheme, and interesting foods to illustrate these abstract ideas. "The Seasoned Schemer" informs the reader about additional dimensions of computing: functions as values, change of state, and exceptional cases. "The Little LISPer" has been a popular introduction to LISP for many years. It had appeared in French and Japanese. "The Little Schemer" and "The SeasonedSchemer" are worthy successors and will prove equally popular as textbooks for Scheme courses as well as companion texts for any complete introductory course in Computer Science. Download DrScheme - a graphical environment for developing Scheme programs

More on Amazon.com

Mentioned in questions and answers.

It wasn't that long ago that I was a beginning coder, trying to find good books/tutorials on languages I wanted to learn. Even still, there are times I need to pick up a language relatively quickly for a new project I am working on. The point of this post is to document some of the best tutorials and books for these languages. I will start the list with the best I can find, but hope you guys out there can help with better suggestions/new languages. Here is what I found:

Since this is now wiki editable, I am giving control up to the community. If you have a suggestion, please put it in this section. I decided to also add a section for general be a better programmer books and online references as well. Once again, all recommendations are welcome.

General Programming

Online Tutorials
Foundations of Programming By Karl Seguin - From Codebetter, its C# based but the ideas ring true across the board, can't believe no-one's posted this yet actually.
How to Write Unmaintainable Code - An anti manual that teaches you how to write code in the most unmaintable way possible. It would be funny if a lot of these suggestions didn't ring so true.
The Programming Section of Wiki Books - suggested by Jim Robert as having a large amount of books/tutorials on multiple languages in various stages of completion
Just the Basics To get a feel for a language.

Books
Code Complete - This book goes without saying, it is truely brilliant in too many ways to mention.
The Pragmatic Programmer - The next best thing to working with a master coder, teaching you everything they know.
Mastering Regular Expressions - Regular Expressions are an essential tool in every programmer's toolbox. This book, recommended by Patrick Lozzi is a great way to learn what they are capable of.
Algorithms in C, C++, and Java - A great way to learn all the classic algorithms if you find Knuth's books a bit too in depth.

C

Online Tutorials
This tutorial seems to pretty consise and thourough, looked over the material and seems to be pretty good. Not sure how friendly it would be to new programmers though.
Books
K&R C - a classic for sure. It might be argued that all programmers should read it.
C Primer Plus - Suggested by Imran as being the ultimate C book for beginning programmers.
C: A Reference Manual - A great reference recommended by Patrick Lozzi.

C++

Online Tutorials
The tutorial on cplusplus.com seems to be the most complete. I found another tutorial here but it doesn't include topics like polymorphism, which I believe is essential. If you are coming from C, this tutorial might be the best for you.

Another useful tutorial, C++ Annotation. In Ubuntu family you can get the ebook on multiple format(pdf, txt, Postscript, and LaTex) by installing c++-annotation package from Synaptic(installed package can be found in /usr/share/doc/c++-annotation/.

Books
The C++ Programming Language - crucial for any C++ programmer.
C++ Primer Plus - Orginally added as a typo, but the amazon reviews are so good, I am going to keep it here until someone says it is a dud.
Effective C++ - Ways to improve your C++ programs.
More Effective C++ - Continuation of Effective C++.
Effective STL - Ways to improve your use of the STL.
Thinking in C++ - Great book, both volumes. Written by Bruce Eckel and Chuck Ellison.
Programming: Principles and Practice Using C++ - Stroustrup's introduction to C++.
Accelerated C++ - Andy Koenig and Barbara Moo - An excellent introduction to C++ that doesn't treat C++ as "C with extra bits bolted on", in fact you dive straight in and start using STL early on.

Forth

Books
FORTH, a text and reference. Mahlon G. Kelly and Nicholas Spies. ISBN 0-13-326349-5 / ISBN 0-13-326331-2. 1986 Prentice-Hall. Leo Brodie's books are good but this book is even better. For instance it covers defining words and the interpreter in depth.

Java

Online Tutorials
Sun's Java Tutorials - An official tutorial that seems thourough, but I am not a java expert. You guys know of any better ones?
Books
Head First Java - Recommended as a great introductory text by Patrick Lozzi.
Effective Java - Recommended by pek as a great intermediate text.
Core Java Volume 1 and Core Java Volume 2 - Suggested by FreeMemory as some of the best java references available.
Java Concurrency in Practice - Recommended by MDC as great resource for concurrent programming in Java.

The Java Programing Language

Python

Online Tutorials
Python.org - The online documentation for this language is pretty good. If you know of any better let me know.
Dive Into Python - Suggested by Nickola. Seems to be a python book online.

Perl

Online Tutorials
perldoc perl - This is how I personally got started with the language, and I don't think you will be able to beat it.
Books
Learning Perl - a great way to introduce yourself to the language.
Programming Perl - greatly referred to as the Perl Bible. Essential reference for any serious perl programmer.
Perl Cookbook - A great book that has solutions to many common problems.
Modern Perl Programming - newly released, contains the latest wisdom on modern techniques and tools, including Moose and DBIx::Class.

Ruby

Online Tutorials
Adam Mika suggested Why's (Poignant) Guide to Ruby but after taking a look at it, I don't know if it is for everyone. Found this site which seems to offer several tutorials for Ruby on Rails.
Books
Programming Ruby - suggested as a great reference for all things ruby.

Visual Basic

Online Tutorials
Found this site which seems to devote itself to visual basic tutorials. Not sure how good they are though.

PHP

Online Tutorials
The main PHP site - A simple tutorial that allows user comments for each page, which I really like. PHPFreaks Tutorials - Various tutorials of different difficulty lengths.
Quakenet/PHP tutorials - PHP tutorial that will guide you from ground up.

JavaScript

Online Tutorials
Found a decent tutorial here geared toward non-programmers. Found another more advanced one here. Nickolay suggested A reintroduction to javascript as a good read here.

Books
Head first JavaScript
JavaScript: The Good Parts (with a Google Tech Talk video by the author)

C#

Online Tutorials
C# Station Tutorial - Seems to be a decent tutorial that I dug up, but I am not a C# guy.
C# Language Specification - Suggested by tamberg. Not really a tutorial, but a great reference on all the elements of C#
Books
C# to the point - suggested by tamberg as a short text that explains the language in amazing depth

ocaml

Books
nlucaroni suggested the following:
OCaml for Scientists Introduction to ocaml
Using Understand and unraveling ocaml: practice to theory and vice versa
Developing Applications using Ocaml - O'Reilly
The Objective Caml System - Official Manua

Haskell

Online Tutorials
nlucaroni suggested the following:
Explore functional programming with Haskell
Books
Real World Haskell
Total Functional Programming

LISP/Scheme

Books
wfarr suggested the following:
The Little Schemer - Introduction to Scheme and functional programming in general
The Seasoned Schemer - Followup to Little Schemer.
Structure and Interpretation of Computer Programs - The definitive book on Lisp (also available online).
Practical Common Lisp - A good introduction to Lisp with several examples of practical use.
On Lisp - Advanced Topics in Lisp
How to Design Programs - An Introduction to Computing and Programming
Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp - an approach to high quality Lisp programming

What about you guys? Am I totally off on some of there? Did I leave out your favorite language? I will take the best comments and modify the question with the suggestions.

Java: SCJP for Java 6. I still use it as a reference.

Haskell:

O'Reilly Book:

  1. Real World Haskell, a great tutorial-oriented book on Haskell, available online and in print.

My favorite general, less academic online tutorials:

  1. The Haskell wikibook which contains all of the excellent Yet Another Haskell Tutorial. (This tutorial helps with specifics of setting up a Haskell distro and running example programs, for example.)
  2. Learn you a Haskell for Great Good, in the spirit of Why's Poignant Guide to Ruby but more to the point.
  3. Write yourself a Scheme in 48 hours. Get your hands dirty learning Haskell with a real project.

Books on Functional Programming with Haskell:

  1. Lambda calculus, combinators, more theoretical, but in a very down to earth manner: Davie's Introduction to Functional Programming Systems Using Haskell
  2. Laziness and program correctness, thinking functionally: Bird's Introduction to Functional Programming Using Haskell

Some books on Java I'd recommend:

For Beginners: Head First Java is an excellent introduction to the language. And I must also mention Head First Design Patterns which is a great resource for learners to grasp what can be quite challenging concepts. The easy-going fun style of these books are ideal for ppl new to programming.

A really thorough, comprehensive book on Java SE is Bruce Eckel's Thinking In Java v4. (At just under 1500 pages it's good for weight-training as well!) For those of us not on fat bank-bonuses there are older versions available for free download.

Of course, as many ppl have already mentioned, Josh Bloch's Effective Java v2 is an essential part of any Java developer's library.

Let's not forget Head First Java, which could be considered the essential first step in this language or maybe the step after the online tutorials by Sun. It's great for the purpose of grasping the language concisely, while adding a bit of fun, serving as a stepping stone for the more in-depth books already mentioned.

Sedgewick offers great series on Algorithms which are a must-have if you find Knuth's books to be too in-depth. Knuth aside, Sedgewick brings a solid approach to the field and he offers his books in C, C++ and Java. The C++ books could be used backwardly on C since he doesn't make a very large distinction between the two languages in his presentation.

Whenever I'm working on C, C:A Reference Manual, by Harbison and Steele, goes with me everywhere. It's concise and efficient while being extremely thorough making it priceless(to me anyways).

Languages aside, and if this thread is to become a go-to for references in which I think it's heading that way due to the number of solid contributions, please include Mastering Regular Expressions, for reasons I think most of us are aware of... some would also say that regex can be considered a language in its own right. Further, its usefulness in a wide array of languages makes it invaluable.

C: “Programming in C”, Stephen G. Kochan, Developer's Library.

Organized, clear, elaborate, beautiful.

C++

The first one is good for beginners and the second one requires more advanced level in C++.

I know this is a cross post from here... but, I think one of the best Java books is Java Concurrency in Practice by Brian Goetz. A rather advanced book - but, it will wear well on your concurrent code and Java development in general.

C#

C# to the Point by Hanspeter Mössenböck. On a mere 200 pages he explains C# in astonishing depth, focusing on underlying concepts and concise examples rather than hand waving and Visual Studio screenshots.

For additional information on specific language features, check the C# language specification ECMA-334.

Framework Design Guidelines, a book by Krzysztof Cwalina and Brad Abrams from Microsoft, provides further insight into the main design decisions behind the .NET library.

For Lisp and Scheme (hell, functional programming in general), there are few things that provide a more solid foundation than The Little Schemer and The Seasoned Schemer. Both provide a very simple and intuitive introduction to both Scheme and functional programming that proves far simpler for new students or hobbyists than any of the typical volumes that rub off like a nonfiction rendition of War & Peace.

Once they've moved beyond the Schemer series, SICP and On Lisp are both fantastic choices.

For C++ I am a big fan of C++ Common Knowledge: Essential Intermediate Programming, I like that it is organized into small sections (usually less than 5 pages per topic) So it is easy for me to grab it and read up on concepts that I need to review.

It is a must read for me the night before and on the plane to a job interview.

C Primer Plus, 5th Edition - The C book to get if you're learning C without any prior programming experience. It's a personal favorite of mine as I learned to program from this book. It has all the qualities a beginner friendly book should have:

  • Doesn't assume any prior exposure to programming
  • Enjoyable to read (without becoming annoying like For Dummies /
  • Doesn't oversimplify

For Javascript:

For PHP:

For OO design & programming, patterns:

For Refactoring:

For SQL/MySQL:

  • C - The C Programming Language - Obviously I had to reference K&R, one of the best programming books out there full stop.
  • C++ - Accelerated C++ - This clear, well written introduction to C++ goes straight to using the STL and gives nice, clear, practical examples. Lives up to its name.
  • C# - Pro C# 2008 and the .NET 3.5 Platform - Bit of a mouthful but wonderfully written and huge depth.
  • F# - Expert F# - Designed to take experienced programmers from zero to expert in F#. Very well written, one of the author's invented F# so you can't go far wrong!
  • Scheme - The Little Schemer - Really unique approach to teaching a programming language done really well.
  • Ruby - Programming Ruby - Affectionately known as the 'pick axe' book, this is THE defacto introduction to Ruby. Very well written, clear and detailed.

I have been programming in Python, PHP, Java and C for a couple or years now, and I just finished reading Hackers and Painters, so I would love to give LISP a try!

I understand its totally diferent from what i know and that it won't be easy. Also I think (please correct me if I'm wrong) there's way less community and development around LISP. So my question is: what's the best way to learn LISP?

I wouldn't mind buying books or investing some time. I just don't want it to be wasted.

The "final" idea would be to use LISP for web development, and I know that's not so common so... I know it's good to plan my learning before picking the first book or tutorial and spending lots of time on something that may not be the best way!

Thank you all for your answers!

edit: I read Practical Common Lisp and was: ... long, hard, interesting and definitely got me rolling in Lisp, after that i read the little schemer, and it was short, fun and very very good for my overall programming. So my recommendation would be to read first the little schemer, then (its a couple of hours and its worth it) if you decide lisp(or scheme or whatever dialect) is not what you where looking for, you will still have a very fun new way of thinking about recursion!

You might want to start with The Little Schemer as a warm-up. It's not a practical book about writing production Lisp programs, but it's a great book for learning how to think in Lisp.

Pick up The Land of Lisp by Conrad Barski. It is a fun filled introduction to Lisp programming using cartoons and games.

I enjoyed reading Practical Common LISP and ANSI Common LISP.

On LISP looks interesting, but at $190 seems a little expensive for a book.

I know there are a few different dialects of Lisp. Having decided that learning Lisp would be a new intellectual experience, I would like to know which Lisp dialect to learn, and why.

Is there one which is more popular than the others? Is any one of them more "complete", as in, better documented and supported? What are the pros and cons of this dialect?

I would say Scheme, solely because of the Little Schemer, which is one of the most mind-blowingly fun yet extremely hard books I've ever tried to read.

I like to study languages outside my comfort zone, but I've had a hard time finding a place to start for functional languages. I heard a lot of good things about Structure and Interpretations of Computer Programs, but when I tried to read through it a couple of years ago it just seemed to whiz over my head. I do way better with books than web sites, but when I visit the local book store the books on LISP look kind of scary.

So what's a good starting point? My goal is to be able to use a functional programming language to solve simple problems in 6 months or so, and the ability to move to more advanced topics, recognize when a functional language is the right tool for the job, and use the language to solve more problems over the course of 2-3 years. I like books that are heavy on examples but also include challenges to work through. Does such a thing exist for functional languages?

I found The Little Schemer a great, great introduction to functional programming. It's entirely based on simple, bite sized examples which are built up upon as the book goes on.

The Little Schemer teaches recursion really well, and it's fun and simple to read.

I also liked The Scheme Programming Language for a broader introduction into the language.

Since there are a bunch of different functional programming languages, it's hard to recommend books. But if you're interested in Common Lisp, recently I've been reading "Practical Common Lisp" by Peter Seibel, which you can check out online for free before dropping your hard earned cash on it. It's a pretty gentle introduction to CL, with great explanations and tons of examples. Seibel's a great writer (example: read the story of Mac,) he's good at keeping you engaged, which is really where SICP falls down, I think. It's just so dry! But while Practical Common Lisp is pretty example-heavy, it doesn't really have challenges to work through, although the examples are mostly designed to let you continue to work and build on them.

Another good book, this one Scheme-oriented: How to Design Programs. (Online) I haven't had as much time with this book, being more of a Lisper than a Schemer myself, but it's well written, has good explanations and examples, and has lots of exercises to work on. It seems pretty popular in the Scheme crowd.

Check out Introduction to functional programming. It offers a different perspective.

I have heard good things about Haskell Functional Programming, but I also found this list of functional programming books at amazon that might be helpful to you.

In an attempt to be a better programmer, I am planning to read a lot of books and learn at least one new language (which I think is going to be python) during the 3-month long holiday that I am going to have.

The list of books that I am planning to read --

Ebooks:

The list of things that I want to do --

  • Start using Linux (probably starting with Ubuntu).
  • Learning to use the bunch of tools mentioned here.
  • Setup a blog (hopefully).

I enjoy watching lectures as well, so, along with Introduction to Algorithms I am going to watch a bunch of Stanford Courses.

A little background: I am a 17 year old guy and I really enjoy programming and every aspect related to it. I have been programming in C and C++ for a while now. The former is more stronger than the latter. I was hoping to utilize the time that I have got on hand thoroughly. Any changes needed with the plan or any additions?

EDIT: Did not mention programming projects.

  1. Making a game using Allegro.
  2. Using QT4 to create a GUI-based database for my school.

Do not just passively read all that information, instead practice after every book chapter or lecture. Practice by writing those algorithms or regexpes for yourself, check your previous code in the light of what code complete has taught you and so on.

If that doesn't give you enough time to do it all, doesn't matter, you better learn properly instead of swallowing material as fast as you can. And all of that is probably too much to do it in only three months anyway, so prioritize by your interests. Take one book and a set of lectures and go at them until finished, then pickup the next, never forgetting to put in practice the concepts shown.

Along with the excellent books you and others listed here I recommend The Little Schemer which will give you a perspective of functional programming. Do not lock yourself into imperative languages (C, C++, C#, Pascal, Java,.. ) while you can dive into different paradigms easily. 17 is a great age :-) Enjoy your journey!

These probably won't fit within your three month plan, but should you wish to master C and Unix, long have I been glad that I spent the time to follow The Loginataka. After that, I found Lions' Commentary on UNIX 6th Edition to be deeply enlightening.

I would add the following two books if you haven't read them already:

Programming Pearls by Jon Bentley

Code by Charles Petzold

Even as it stands, you're going to have a very busy, hopefully productive break. Good luck!

Response to question edit: If you're interested in learning about databases, then I recommend Database in Depth by Chris Date. I hope by "create a GUI-based database" you mean implementing a front-end application for an existing database back end. There are plenty of database solutions out there, and it will be well worth it for your future career to learn a few of them.

I've got a little experience with Python (enough to where I can do if/else/elif and some random number generation), but I've always had a weird fascination with the Lisp languages. I downloaded some scheme source code to look at the syntax but it was pretty much gibberish to me.

For a programmer with only a little programming experience like myself, given some good books, websites, and some time, would it be particularly difficult to learn either Common Lisp or Scheme? Which of the two would be easier? How do they compare with Python and C, as far as ease of learning?

Thanks

Given some good books, websites, and some time, would it be particularly difficult to learn either Common Lisp or Scheme?

No.

Which of the two would be easier?

Scheme, because

How do they compare with Python and C, as far as ease of learning?

I think it's harder to learn C than to learn either Python or Scheme, because to learn C you really have to grok the machine model, pointers, and dynamic memory.

Between Scheme and Python, it is really hard to predict how any individual learner will react. I really like Python's significant whitespace, and I find Scheme's parentheses annoying and distracting. Lots of people really like Scheme's parentheses, and they find Python's significant whitespace annoying and distracting. (There are important semantic differences, but it is hard to escape the tyranny of syntax.)

What books should I use? (question you should have asked and didn't)

Don't use Structure and Interpretation of Computer Programs (SICP). That book's point of view is "let's show off how smart we are by coding all of computer science in Scheme." The book is a tremendous intellectual tour de force, but it is not at all suitable for beginners. When MIT used it in 6.001, it was as a "weedout" course because 30–40% of all MIT students wanted to major in EECS, and they were trying to turn people away. SCIP is a terrific for a senior CS student or a programmer with 5 years of experience. Don't try to learn from it.

Some good books to learn from:

  • How to Design Programs by Felleisen et al has been carefully crafted and honed through years of experience. It uses Scheme and teaches you exactly what it claims in the title. Highly recommended.

  • Simply Scheme by Harvey and Wright is an introductory CS book by people who felt that SCIP needed a "prequel." I enjoyed reading it but I haven't taught from it.

  • If you can stand cuteness, The Little Schemer by Felleisen and Friedman has a very unusual dialectical style, with tons of examples, that you might like.

I hear all the time that Erlang is a functional language, yet it is easy to call databases or non side-effect free code from a function, and commands are easily ordered by using "," commas between them just like Ruby or another language, so where is the "functional" part of Erlang?

There's a meme that functional languages must have immutable values and be side-effect free, but I say that any language with first-class functions is a functional programming language.

It is useful and powerful to have strong controls over value mutability and side effects, but I believe these are peripheral to functional programming. Nice to have, but not essential. Even in languages that do have these properties, there is always a way to escape the purity of the paradigm.1

There is a grayscale continuum between truly pure FP languages that you can't actually use for anything practical and languages that are really quite impure but still have some of the FP nature to them:

  • Book FP: Introductory books on FP languages frequently show only a subset of the language, with all examples done within the language's REPL, so that you never get to see the purely functional paradigm get broken. A good example of this is Scheme as presented in The Little Schemer.

    You can come away from reading such a book with the false impression that FP languages can't actually do anything useful.

  • Haskell: The creators of Haskell went to uncommon lengths to wall off impurity via the famous I/O monad. Everything on one side of the wall is purely functional, so that the compiler can reason confidently about the code.

    But the important thing is, despite the existence of this wall, you have to use the I/O monad to get anything useful done in Haskell.2 In that sense, Haskell isn't as "pure" as some would like you to believe. The I/O monad allows you to build any sort of "impure" software you like in Haskell: database clients, highly stateful GUIs, etc.

  • Erlang: Has immutable values and first-class functions, but lacks a strong wall between the core language and the impure bits.

    Erlang ships with Mnesia, a disk-backed in-memory DBMS, which is about as impure as software gets. It's scarcely different in practice from a global variable store. Erlang also has great support for communicating with external programs via ports, sockets, etc.

    Erlang doesn't impose any kind of purity policy on you, the programmer, at the language level. It just gives you the tools and lets you decide how to use them.

  • OCaml and F#: These closely-related multiparadigm languages include both purely functional elements as well as imperative and object-oriented characteristics.

    The imperative programming bits allow you to do things like write a traditional for loop with a mutable counter variable, whereas a pure FP program would probably try to recurse over a list instead to accomplish the same result.

    The OO parts are pretty much useless without the mutable keyword, which turns a value definition into a variable, so that the compiler won't complain if you change the variable's value. Mutable variables in OCaml and F# have some limitations, but you can escape even those limitations with the ref keyword.

    If you're using F# with .NET, you're going to be mutating values all the time, because most of .NET is mutable, in one way or another. Any .NET object with a settable property is mutable, for example, and all the GUI stuff inherently has side-effects. The only immutable part of .NET that immediately comes to mind is System.String.

    Despite all this, no one would argue that OCaml and F# are not functional programming languages.

  • JavaScript, R, Lua, Perl...: There are many languages even less pure than OCaml which can still be considered functional in some sense. Such languages have first-class functions, but values are mutable by default.


Foototes:

  1. Any truly pure FP language is a toy language or someone's research project.

  2. That is, unless your idea of "useful" is to keep everything in the ghci REPL. You can use Haskell like a glorified calculator, if you like, so it's pure FP.

I want to learn some language from Lisp family. It may be CL or Scheme and try to use it for web programming. Just for fun. I have significant C++ experience (prefessional development).

But I want my choice be modern language without legacy (in language itself and library), because I want learn good design patterns from the start.

I can't decide what is better: CL or Scheme. CL has much greater and standartized library and frameworks (Weblocks), but I heard that it has MUCH of legacy in its syntax and libraries. Scheme is another: simple, concise syntax but poor library. I'd prefer CL if it has no legacy.

I don't like to learn another monster like C++. Is it true that CL is like C++ in Lisp family? And Scheme is like, say, C# or Java - "revised" C++.

Edit: I want to write in functional style, OOP may be, but optional.

I'm a fan of Scheme because it was designed from the ground up to be consistent and simple, but still have advanced features not found in most other languages. For those reasons, it's especially popular in education and academia.

I'd recommend the book The Little Schemer and either Racket or Petite Chez Scheme (both are free) if you want to learn functional programming.

Common LISP and Emacs LISP have the atom type predicate. Scheme and Clojure don't have it. http://hyperpolyglot.wikidot.com/lisp

Is there a design reason for this - or is it just not an essential function to include in the API?

In the book The Little Schemer, atom? is defined as follows:

(define (atom? x)
  (and (not (pair? x))
       (not (null? x))))

Noting that null is not considered an atom, as other answers have suggested. In the mentioned book atom? is used heavily, in particular when writing procedures that deal with lists of lists.

In an application I'm working on in Racket I need to take a list of numbers and partition the list into sub-lists of consecutive numbers: (In the actual application, I'll actually be partitioning pairs consisting of a number and some data, but the principle is the same.)

i.e. if my procedure is called chunkify then:

(chunkify '(1 2 3  5 6 7  9 10 11)) -> '((1 2 3) (5 6 7) (9 10 11))  
(chunkify '(1 2 3)) ->  '((1 2 3))  
(chunkify '(1  3 4 5  7  9 10 11 13)) -> '((1) (3 4 5) (7) (9 10 11) (13))  
(chunkify '(1)) -> '((1))  
(chunkify '()) -> '(())  

etc.

I've come up with the following in Racket:

#lang racket  
(define (chunkify lst)  
  (call-with-values   
   (lambda ()  
     (for/fold ([chunk '()] [tail '()]) ([cell  (reverse lst)])  
       (cond  
         [(empty? chunk)                     (values (cons cell chunk) tail)]  
         [(equal? (add1 cell) (first chunk)) (values (cons cell chunk) tail)]  
         [else (values   (list cell) (cons  chunk tail))])))  
   cons))  

This works just fine, but I'm wondering given the expressiveness of Racket if there isn't a more straightforward simpler way of doing this, some way to get rid of the "call-with-values" and the need to reverse the list in the procedure etc., perhaps some way comepletely different.

My first attempt was based very loosely on a pattern with a collector in "The Little Schemer" and that was even less straightforward than the above:

(define (chunkify-list lst)  
 (define (lambda-to-chunkify-list chunk) (list chunk))

 (let chunkify1 ([list-of-chunks '()] 
                 [lst lst]
                 [collector lambda-to-chunkify-list])
   (cond 
     [(empty? (rest lst)) (append list-of-chunks (collector (list (first lst))))]
     [(equal? (add1 (first lst)) (second lst))  
      (chunkify1 list-of-chunks (rest lst)
                 (lambda (chunk) (collector (cons (first lst) chunk))))] 
     [else
      (chunkify1 (append list-of-chunks
                         (collector (list (first lst)))) (rest lst) list)]))) 

What I'm looking for is something simple, concise and straightforward.

Here's how I'd do it:

;; chunkify : (listof number) -> (listof (non-empty-listof number))
;; Split list into maximal contiguous segments.
(define (chunkify lst)
  (cond [(null? lst) null]
        [else (chunkify/chunk (cdr lst) (list (car lst)))]))

;; chunkify/chunk : (listof number) (non-empty-listof number)
;;               -> (listof (non-empty-listof number)
;; Continues chunkifying a list, given a partial chunk.
;; rchunk is the prefix of the current chunk seen so far, reversed
(define (chunkify/chunk lst rchunk)
  (cond [(and (pair? lst)
              (= (car lst) (add1 (car rchunk))))
         (chunkify/chunk (cdr lst)
                         (cons (car lst) rchunk))]
        [else (cons (reverse rchunk) (chunkify lst))]))

It disagrees with your final test case, though:

(chunkify '()) -> '()  ;; not '(()), as you have

I consider my answer more natural; if you really want the answer to be '(()), then I'd rename chunkify and write a wrapper that handles the empty case specially.

If you prefer to avoid the mutual recursion, you could make the auxiliary function return the leftover list as a second value instead of calling chunkify on it, like so:

;; chunkify : (listof number) -> (listof (non-empty-listof number))
;; Split list into maximal contiguous segments.
(define (chunkify lst)
  (cond [(null? lst) null]
        [else
         (let-values ([(chunk tail) (get-chunk (cdr lst) (list (car lst)))])
           (cons chunk (chunkify tail)))]))

;; get-chunk : (listof number) (non-empty-listof number)
;;          -> (values (non-empty-listof number) (listof number))
;; Consumes a single chunk, returns chunk and unused tail.
;; rchunk is the prefix of the current chunk seen so far, reversed
(define (get-chunk lst rchunk)
  (cond [(and (pair? lst)
              (= (car lst) (add1 (car rchunk))))
         (get-chunk (cdr lst)
                    (cons (car lst) rchunk))]
        [else (values (reverse rchunk) lst)]))

I already have a parser for a language I've been working on. Is making it interpreted difficult? I was thinking its simple. The parsing and syntax check is done. I just have a tree of objects. Everytime an object is created I create a branch and store its type (string, int, float, class/obj). Then everytime a new member is added to the object I create a branch and repeat.

I try to make it sound simple. I still need to check of object A can be added to object B and such.

Is it actually fairly simple after AST and syntax check is done or is there still a lot more work?

It depends on how complex a language you want to write an interpreter for and your choice of tools. Simple interpreters are simple.

Consider the following as the definition on an AST in Haskell for a language that supports higher order functions and numbers:

data Exp = Lam String Exp 
         | App Exp Exp 
         | Var String 
         | Num Int

Now you can write an interpreter for it as the simple "eval" function:

eval (App e1 e2) env = (unF (eval e1 env)) (eval e2 env)
eval (Lam x e) env   = F (\v -> (eval e ((x,v):env)))
eval (Num n) env     = N n
eval (Var x) env     = case (lookup x env) of 
                         Just v -> v
                         Nothing -> error ("Unbound variable " ++ x)

And that's it. The few boring supporting definitions are as follows.

data Val = F (Val -> Val)  | N Int
unF (F x) = x
instance Show Val where 
    show (F _) = "<procedure>"
    show (N n) = show n

In other words, if you copy paste the above three blocks of code into a Haskell source file you will have a working interpreter, which you can test using ghci as follows:

*Main> eval (App (Lam "x" (Var "x")) (Num 1)) []
1
*Main> eval (Var "x") []
*** Exception: Unbound variable x

You could read about creating languages in the classic SICP or EOPL or the little book. If you wish to build a typed language, you may have to read some more.

That said, if you are going to build languages, might I strongly recommend lots of reading first. For one, its very rewarding. And secondly too many hideous languages have been inflicted on the world by people who don't know how to create languages (many of which have become very popular for various historical reasons) and we are stuck with them.

In The Little Schemer there is a function to check, whether the list is flat:

(define lat?
  (lambda (l)
    (cond
     ((null? l) #t)
     ((atom? (car l)) (lat? (cdr l)))
     (else #f))))

I'm trying to write the same recursive function in Haskell, but have no success:

is_lat :: [a] -> Bool
is_lat [] = True
is_lat ???

How do i check that the parameter is not in the form [[a]]? In other words, [1,2,3] is a valid input, but [[1,3], [2,4]] and [[[1,2,3]]] aren't.

I want to use this further in recursive functions that accept lists to make sure that i deal with flat lists only.

EDIT: I see that people are confused because of the is_lat :: [a] -> Bool type signature. I agree now, that i shouldn't check type on runtime. However, is it possible to check the type on compile-time? How can i make the function work only for flat lists? Or should i completely change my way of thinking?

You can't really think of nested lists the same way in Haskell as in Scheme, because they're not the same data structure. A Haskell list is homogenous, where as a Lisp "list" is actually closer to a rose tree (as pointed out by C.A.McCann below). As an illustrative example, take a look at how the WYAS48 parsing section defines LispVal.

If you really, really, really want to do runtime type checking, even though it's usually a bad idea and very unconventional in Haskell, look into Data.Typeable. This response might be useful too.

The real answer to this question is "You need to think about your arguments differently in Haskell than in Lisp, which results in never needing to perform this check yourself at runtime" (and I say this as a Common Lisper, so I understand how frustrating that is to start with).

Addendum: In response to your edit, Haskell's type system automatically ensures this. If you have a function of type foo :: [Int] -> Int, for example, and you pass it ["One", "Two", "Three"] or [[1, 2, 3]], you'll get a compile-time error telling you what just exploded and why. If you want to specialize a function, just declare a more specific type.

For instance (don't write code like this, it's just for illustrative purposes), say you have a simple function like

myLookup index map = lookup index map 

If you load this into GHCi and run :t myLookup, it'll tell you that the functions' type is myLookup :: Eq a => a -> [(a, b)] -> Maybe b which means that it can take a key of any type that derives Eq (anything you can run == on). Now, say that for whatever reason you want to ensure that you only use numbers as keys. You'd ensure that by adding a more specific type declaration

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup index map = lookup index map 

Now, even though there's nothing in the body of the function preventing it from dealing with other key types, you'll get a type error at compile time if you try to pass it something other than an Int index or something other than an [(Int, a)] map. As a result, this

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup ix lst = lookup ix lst

main :: IO ()
main = putStrLn . show $ myLookup 1 [(1, "Foo")]

will compile and run fine, but this

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup ix lst = lookup ix lst

main :: IO ()
main = putStrLn . show $ myLookup "Nope.jpg" [("Foo", 1)]

will do neither. On my machine it errors at compile time with

/home/inaimathi/test.hs:5:35:
    Couldn't match expected type `Int' with actual type `[Char]'
    In the first argument of `myLookup', namely `"Nope.jpg"'
    In the second argument of `($)', namely
      `myLookup "Nope.jpg" [("Foo", 1)]'
    In the expression:
      putStrLn . show $ myLookup "Nope.jpg" [("Foo", 1)]
Failed, modules loaded: none.

I really hope that didn't confuse you further.

many (may be all?) programming language consist of assembly language

how lisp implemented in assembly language?

is there any good reference, manual, tutorial, or keyword for google?

any official rule/convention for build your own lisp implementation?

such as tail recursion should follow some embodiment rule or something..

thanks

Although the other comments and posts are right, this question is overly vague and maybe a bit confused, I can't help but share some recommendations. I've collected a number of links and books on implementing Lisp as I have recently developed a bit of a fascination with language implementation. It's a deep topic, of course, but reading the stuff related to Lisp is especially compelling because you can skip a lot of the intense reading on parsing if you implement a Lisp compiler or interpreter in Lisp, and just use read. This allows the authors to get to the meat of compilation or interpretation quickly. These recommendations are books I've read or started or am reading, and mostly deal with Scheme, not Common Lisp, but still might be of some interest.

If you've got no background in language implementation, and have never had the pleasure of reading about the classic Lisp and Scheme "metacircular evaluators", I would recommend Structure and Interpretation of Computer Programs. If you've seen Lisp-in-Lisp (or Scheme-in-Scheme...) you can skip ahead. In the last two chapters of SICP, the authors present a few different interpreters for Lisp/Scheme and a few variants, as well as a byte-code compiler and a virtual machine. It's simply a brilliant book, and free.

If you don't have time to read SICP, or don't want to slog through it just to get to the interpretation and compilation chapters, I would recommend The Little Schemer. Even though it's very short and intended for newcomers to Lisp and Scheme, if you've never seen a Lisp interpreter written in Lisp, they do present one, and it's quite a delightful book, but might not be for everyone due to the cute style.

There's another free book on Scheme similar to SICP, called An Introduction to Scheme and its Implementation, which I haven't read but used as a reference for a few bits. There are sections on interpreters and compilers in there, and it seems to go a bit deeper than SICP, dealing with hairier things like parsing too. It maybe needed an editor, but it's an impressive offering nonetheless.

With a decent idea of how to do Lisp in Lisp, you can approach implementing Lisp in something lower level.

Lisp in Small Pieces is frequently recommended. I've read most of it, and can say it's definitely a great book, full of nitty gritty stuff. I'm going back over it with a fine comb, because it's easy to skim when you don't understand stuff. I also struggled with getting the code from the author's site to run; if you get it, I recommend using Gambit Scheme and running the code that relies on Meroonet with Meroon, from this distribution. Lisp in Small Pieces presents a number of interpreters written in Scheme as well as a byte-code compiler and a compiler-to-C.

Lisp in Small Pieces moves fast, and it's quite dense. If it's too much for you, perhaps start with The Essentials of Programming Languages. I've read some of it and it's quite good, but it's more interpreters. Apparently one of the older editions (1st? I'm not sure...) included a compiler. There seems to be a lot of change between the 3 editions, but the first is super cheap on Amazon, so check it out.

As for compilation to C, this is kind of a gross subject with lots of hairy bits. Compilation to C brings up all these weird corner issues, like how to optimize tail-calls and handle closures, first-class continuations and garbage collection, but it's pretty interesting, and a lot of "real" implementations of Scheme go this route. Marc Feeley's presentation on this is pretty interesting, titled The 90 Minute Scheme to C compiler.

I have fewer resources on compiling all the way down to assembly, but there is a often recommended paper which introduces compilation of Scheme to x86, called An Incremental Approach to Compiler Construction. It assumes little of the reader, however I found that it simply goes too fast and doesn't fill in enough details. Maybe you'll have better luck.

A lot of the above recommendation comes from this monster comment on Hacker News from over a year ago, from mahmud. It references a number of ML resources, and compilation using continuations. I haven't gotten that far in my study, so I can't say what's good or not. But it's an incredibly valuable comment. The referenced works include Andrew Appel's "Compiling with Continuations" and Paul Wilson's "Uniprocessor Garbage Collection Techniques" paper.

Good luck!

That it's a big question to answer well.

Short answer: JIT.

Big answer: Dragon book.

Currently, I am using Javascript - The Definitive Guide for learning Javascript from scratch. Having learnt Java, PERL and other programming languages, I am in a habit of solving small exercises to check/better understand what I have been learning as well. In case of Javascript, I found the book to be severely lacking in exercises. Infact, I did not find exercises in the only other book [ Beginning Javascript ] I have either.

Is there any source that I can refer to for exercises in Javascript?

I would suggest reading everything Douglas Crockford has to say about JavaScript, reading The Good Parts, writing as many programs as possible and running them all through JSLint with "the Good Parts" and rewriting them until it stops complaining, and reading the source of jQuery. It also wouldn't hurt to read Dmitry A. Soshnikos' rendition of the ECMA-262 spec. (It's very specific and goes into minute detail but it also covers every possible aspect of the language)

It would probably be good to mention that you don't need to follow Crockford's conventions to the letter if you don't want to (though I would recommend writing for ES5 strict) but limiting yourself to them while you learn the language is definitely the way to go.

Once you get a good grasp on the syntax, Crockford has a page that compares javascript with Scheme and takes you through a short book The Little Schemer. The article is appropriately named The Little JavaScripter.

After reading the book, I was changed. Or perhaps transformed. Or altered. In a good way. There are very few books that deeply change the way that you think. This is one of those books.

He's gone through the chapters and translated the functions into javascript. As an exercise, you could do the same and compare your solutions.

I know there is one, but it's not easy to implement the way I want.

I would like to know the steps to interpret the lisp language and what functions are essential to be implemented.

If you want to implement a basic lisp in a higher level language, you might get some mileage out of the later chapters of The Little Schemer (where you're shown how to write a meta-circular evaluator in Scheme), the entirety of WYAS48 (where you're shown how to implement an R5RS Scheme in Haskell) and these two Norvig articles (wherein he implements a basic lisp-like in Python).

First, you learn Lisp, then read LiSP and (given you know ActionScript well enough) you just start. PAIP also has sections about implementing Lisp interpreters and compilers.

To get an idea how it generally can be approached, you can have a look at Write Yourself a Scheme in 48 hours. It uses Haskell as an implementation language, but it would give you an idea.

It surely wouldn't be trivial, but it has been done quite often, and there is much to learn from doing it.

;; compute the max of a list of integers

(define Y
  (lambda (w)
    ((lambda (f)
       (f f))
     (lambda (f)
       (w (lambda (x)
            ((f f) x)))))))

((Y
  (lambda (max)
    (lambda (l)
      (cond ((null? l) -1)
            ((> (car l) (max (cdr l))) (car l))
            (else (max (cdr l)))))))
 '(1 2 3 4 5))

I wish to understand this construction. Can somebody give a clear and simple explanation for this code?

For example, supposing that I forget the formula of Y. How can I remember it , and reproduce it long after I work with it ?

The best explanation I've found so far it's in the book "The Little Schemer", chapter 9. The whole chapter explains step-by-step how the Y-Combinator works, and how to derive the combinator starting from an arbitrary recursive procedure.

I am trying to make a function that takes 2 numbers and will create a list using the first number as a starting number and the second number as the ending value while filling in the values between the starting and ending numbers.

For example:

User passes in 3 and 7:

the output should be (3 4 5 6)

I was trying to do this and use recursion but I am struggling:

 (define (createlist start end)
   (if(= start end)
      '())
   (cons start '())
    (createlist (+ 1 start) end))

There's a repeating pattern found in the solution to this sort of problems where you have to build a list along the way using recursion. Let me illustrate the general steps, I'll let you fill-in the blanks:

(define (createlist start end)
  (if (= <???> <???>) ; the problem is solved when start and end are the same
      '()             ; lists end in null
      (cons <???>  ; if we are not done yet, we `cons` the current value of start
            (createlist <???> end)))) ; with the result of calling the recursion
            ; notice that start is one step closer to the end, so we increment it

The idea of the algorithm is that at each step we add the current start value to the list that is being built with cons, and increment start until it reaches end, at this point the recursion ends.

You should take a look at either The Little Schemer or How to Design Programs, both books will teach you how to structure the solution for this kind of recursive problems over lists.

UPDATE:

Now that you've posted the code you've written so far, I can show you the right answer. Please be very careful with parenthesis [ the closing parenthesis of an if goes after the else part ] and white spaces [ if( is not the same as if ( ], they matter a lot in Scheme. Also indent correctly your code, it'll help you find a lot of bugs:

(define (createlist start end)
  (if (= start end)
      '()
      (cons start
            (createlist (+ 1 start) end))))

Now you can see how the <???> get correctly filled.

I found this article on partial evaluation which looked pretty cool: (the long link gives a HTML version) http://webcache.googleusercontent.com/search?q=cache:sZ6qu87l4u8J:openmap.bbn.com/~kanderso/performance/postscript/essence.ps+&cd=1&hl=en&ct=clnk&gl=us

I thought I'd read it and run the code as I went along. However, I could not get the code to run in either Racket Scheme or SBCL.

Is anyone familiar with this paper, and know what language it is written in?

From the text:

Software examples are given in a Scheme like dialect of Common Lisp where define replaces defvar, defun, and defmethod. While this may be confusing to some, the idea is to keep the software abstract and free of unnecessary detail, since the point is to show how such a language can be easily and efficiently implemented. The ideas expressed here should port to other languages as well, perhaps with a bit more work.

Sounds like the Dijkstra school. If you want practical books you can code along with, I'd suggest SICP or Practical Common Lisp. If you weren't past the basics, I'd also suggest the Schemer Trilogy. Also, if you're ok with writing in non-Lisp languages, check out Write Yourself a Scheme.

I have recently started following the examples from The Little Schemer and when trying out the examples in DrScheme, I have realised that there are some minor syntax changes from the examples in the book to what I can write in DrScheme.

First of all, as a language in DrScheme, I chose Pretty Big (one of the Legacy Languages).
Is this the correct choice for trying the examples in the book?


As regards the syntax changes I have noticed that, for example, I need to prefix the identifiers with a ' in order for them to work.

For example:

(rember 'jelly '(peanut butter jelly))

Are there any more changes (syntactical or not) that I need to be aware of when trying the examples from the 'The Little Schemer' book ?

IIRC, the book uses a different font for quoted pieces of data, and in real Scheme code that requires using quote. As for your use of PLT Scheme -- the "Pretty Big" language is really there just as a legacy language. You should use the Module language, and have all files start with #lang scheme (which should be there by default).

(The "new" way of using different languages in DrScheme is to always be in the Module "language" and specify the actual language using a #lang line.)

I'm new to Scheme and this is my very first Functional language. Implementing almost everything recursively seems to be awkward for me. Nevertheless, was able to implement functions of Factorial and Fibonacci problems having a single integer input.

However, what about when your function has an input of a list? Suppose this exercise:

FUNCTION: ret10 - extracts and returns as a list all the numbers greater than 10 that are found in a given list, guile> (ret10 ‘(x e (h n) 1 23 12 o)) OUTPUT: (23 12)

Should I have (define c(list)) as the argument of my function in this? or is there any other way?

Please help. Thanks!


Here's my derived solution based on sir Óscar López's answer below.. hope this helps others:

(define (ret10 lst)
    (cond
        ((null? lst) '())

        ((and (number? (car lst)) (> (car lst) 10))
            (cons (car lst)
            (ret10 (cdr lst))))

        (else (ret10 (cdr lst)))
    )
)

This kind of problem where you receive a list as input and return another list as output has a well-known template for a solution. I'd start by recommending you take a look at The Little Schemer or How to Design Programs, either book will teach you the correct way to start thinking about the solution.

First, I'll show you how to solve a similar problem: copying a list, exactly as it comes. That'll demonstrate the general structure of the solution:

(define (copy lst)
  (cond ((null? lst)                ; if the input list is empty
         '())                       ; then return the empty list
        (else                       ; otherwise create a new list
         (cons (car lst)            ; `cons` the first element
               (copy (cdr lst)))))) ; and advance recursion over rest of list

Now let's see how the above relates to your problem. Clearly, the base case for the recursion will be the same. What's different is that we cons the first element with the rest of the list only if it's a number (hint: use the number? procedure) and it's greater than 10. If the condition doesn't hold, we just advance the recursion, without consing anything. Here's the general idea, fill-in the blanks:

(define (ret10 lst)
  (cond (<???> <???>)          ; base case: empty list
        (<???>                 ; if the condition holds
         (cons <???>           ; `cons` first element
               (ret10 <???>))) ; and advance recursion
        (else                  ; otherwise
         (ret10 <???>))))      ; simply advance recursion

Don't forget to test it:

(ret10 '(x e (h n) 1 23 12 o))
=> '(23 12)

As a final note: normally you'd solve this problem using the filter procedure - which takes as input a list and returns as output another list with only the elements that satisfy a given predicate. After you learn and understand how to write a solution "by hand", take a look at filter and write the solution using it, just to compare different approaches.

Last days, I am struggling to understand closures. I am very big fan of C# so my main testbed is this language, so I would like to learn about it's closure support. As I studied and experimented, I found out that many people, when trying to blog about closures, they do it by following a completely wrong direction. They project a certain buggy use of closures like the well known for-statement and they are trying to explain it. Instead I would like to see a mathematical approach (First-class citizen, free/bound variables, lambdas, etc). However this makes me consider that I would like to know what bugs may come up when coding without closures in mind.

Furthermore, do all languages have the same interpretation of the mathematical construct of closures?

I didn't have an FP course nor an advanced programming languages in uni. But I know the role of side effects in the procedural code and their inexistent one at pure virtual languages. Are closures in C# just a trick? What (e.g.) F# closures have more than C# closures?

It sounds to me like you want to learn functional programming in general. Doing that, you can't avoid learning the "right" way to use closures because they are so central to functional programming.

Unfortunately I don't know a good functional programming reference for C#. Searching a bit turns up this intro article: Introduction to Functional Programming in C#.

If you don't mind working with another language, you might consider The Little Schemer. It uses Scheme, but uses only the parts you actually need for the book. It is easy to follow but delves directly into to the hard parts of functional programming.

As for your other question, I have found that if you don't mutate variables, closures behave the same in most languages--even Java's anonymous inner classes. (Although, like kvb said, it is true that functional languages like F# and Haskell prevent you from mistakenly mutating a variable when you didn't mean to.)

Probably a trivial question for most of the more advanced schemers here, but as a newcomer, I've found this to be a problem.

I need a way to construct a new list that is in the same order it was when it came in. As an example, say we are given a list '(1 2 0 3 4 0 0 5). But traversing the list and passing the cdr back as the 1st argument ends up constructing the new list backwards.

Here's an example in code:

I pass it an "old-list" that needs work done on it and an empty list as "new-list" to be formed and returned.

note that taking 0s out is just here as "some condition" that the new list must meet

  (define (form-new-list old-list new-list)
    (cond ((null? old-list) new-list)
          (else
           (if (eq? (car old-list) 0) (form-new-list (cdr old-list) new-list)
               (form-new-list (cdr old-list) (cons (car old-list) new-list))))))

  ;test
  (form-new-list '(1 2 0 3 4 0 0 5) '()) ; gives (5 4 3 2 1)
  ;but want (1 2 3 4 5)

I DO NOT just want to reverse the list that is returned with a reverse procedure, but rather, want the new list to be put together in the correct order in the first place.

Is there some kind of "trick" to this, like making the recursive call somewhere else perhaps?

Any advice is greatly appreciated.

You're looking for the natural way to traverse a list using recursion. Use this procedure as a template for your solution - it simply copies a list exactly as it is received:

(define (copy lst)
  (if (null? lst)
      '()
      (cons (car lst)
            (copy (cdr lst)))))

Notice the following points:

  • The recursion ends when the input list is null, and given that we're building a new list, the correct value to return is the null list
  • We're interested in building a new list, we do this by consing a new element for the output list, which in this case happens to be the first element of the input list (its car part)
  • Finally, the recursive step advances by invoking the procedure with the rest of the input list (its cdr part)

As usual, I end up my answers to people learning how to think recursively by recommending you take a look at either The Little Schemer or How to Design Programs, both books will teach you how to grok recursive processes in general, using Scheme.

Greets,

Reading Simply Scheme Chapter 09 and from what I can see, Lambda seems important. I'd like to practice it to the bone so I'm looking for beginner exercises (preferably non recursive) vis à vis Project Euler that focus on lambda. Let inclusive is bonus. Got any resources?

Online, I found this and references to Simply Scheme. I understand there are good books, but I'm really just looking for exercises.

Many Thanks.

If you're learning Scheme, you have to understand recursion from the very start. I'd suggest The Little Schemer for this, and for your question, take a look at Chapter 8: Lambda the Ultimate - there you'll find plenty of exercises (in Q&A format) dealing with lambda. Its follow-up, titled The Seasoned Schemer, is also a fantastic book with chapters and exercises explaining let.

Another beginner's level book, great for teaching yourself Scheme, would be How to Design Programs. And finally, for a more advanced book with more math-flavored exercises, you can't miss Structure and Interpretation of Computer Programs, it will change forever the way you think about programming. Of course, all of the books mentioned will have exercises related to lambda ... among many other subjects.

If you have a list ( (1 4 5) 5 (6 2 5) ), and another list (5 1 3 7 5 (9 2 4) ), I need to write a procedure that compares items from the first list and sees if they're in the second. For example, (1 4 5) appears 0 times in (5 1 3 7 5 (9 2 3) ). 5 appears in this list 2 times, and (9 2 4) appears 0 times. So the list will return (0 2 0)

I need help writing a scheme procedure frequency that takes in two lists, the first being the one that has each component compared, and the second being the one that counts the number of occurrences of the first list. The procedure should return a list of the occurrences.

Thanks!

This is clearly a homework, so I won't give you a straight answer. Instead, I'll point you in the right direction. For starters, split the problem in two procedures:

  • The first procedure, let's call it counter, receives an element and a list of elements. It traverses the list of elements asking, for each of them, if it's equal to the element passed as parameter. It adds one to the accumulated result if a match is found or continues with the next element if not. The list traversal ends when the null list is reached, and for this the counter returns zero.

  • The second procedure, called frequency receives the two lists in the question and traverses the first list (the list of elements to compare against). For each of those elements, it calls counter to find out the result, building up a list along the way.

Here's the general structure of the solution, you must fill-in the blanks:

(define (counter ele lst)
  (cond ((null? lst)
         <???>)
        ((equal? ele <???>)
         (<???> (counter ele <???>)))
        (else
         (counter ele <???>))))

(define (frequency els lst)
  (if (null? els)
      <???>
      (cons <???>
            (frequency <???> lst))))

Notice that in counter I'm assuming that the element is being searched at the base level in the list, for instance this won't find the element:

(counter 5 '((5)))
=> 0

If you have to find matches like the one on the above example, then the problem is a bit more interesting - you'll need to recursively traverse the list of lists in a tree-like fashion. There are countless examples of that in Stack Overflow or elsewhere in Internet; if you're feeling a bit lost I'd recommend you take a look at either The Little Schemer or How to Design Programs, both books will teach you how to grok recursive processes in general.

I get this

(define (ident x) x)

is the same as

(define ident (lambda (x) x))

But why use lambda when you can simply use the former here? Doesn't it seem a bit more simple?

Here's an example using the short form and lambda in the same procedure:

(define (make-generator from step-proc) ; short form
  (lambda () ; the lambda here is the procedure returned
    (let ((tmp from))
      (set! from (step-proc from))
      tmp)))

;; can't use short form here since make-generator
;; returns the procedure
(define natural 
  (make-generator 1 
                  ;; use an anonymous procedure
                  ;; to increase the previous number by 1
                  (lambda (x) (+ 1 x)))) 

(natural) ; ==> 1
(natural) ; ==> 2
(natural) ; ==> 3

;; can't use short form here since make-generator
;; returns the procedure
(define rational 
  (make-generator 1 
                  ;; use an anonymous procedure
                  ;; to halve the previous number
                  (lambda (x) (/ x 2)))) 

(rational) ; ==> 1
(rational) ; ==> 1/2
(rational) ; ==> 1/4

Now, Scheme didn't originally have the short form (not until R3RS in 1986, 11 years after the first specification), but now that it's been around for several revisions it's safe to use it always as long as one understands it is the same. Some books first editions predates R3RS and some haven't updated to use it since it may be confusing having more than one way to define procedures. One of these books is the excellent Little Schemer.

I'm trying to create a specific response for a given list if it has shared elements with another list. As in if I have a list that is (My name is John) and I have another list of (John Adam Jacob) I would want the first list to be able to see that John is in the second list, and be able to print something along the lines of (this is a known name) or something similiar.

The code I have thought of uses map, and member.

(define (specific-reply user-list)
     (cond (member (map (lambda (user-list)) '(John Adam Jacob)))
            (write (this is a known name))
      (else 
            (write (this is not a known name)))))

I'm extremely knew to both racket and scheme however and I haven't really gotten it to compile yet so I think I'm largely off.

Any help would be greatly appreciated.

You don't need to complicate the problem if your task is to just find if a is a member of (a b c),

Here's a piece of Scheme code that can tell if a is a member of lat. It's just a simple recursive function that compares each element of lat with a for a match.

(define member?
    (lambda (a lat)
        (cond
            ((null? lat) #f)
            ((eq? a lat) #t)
            (else
                 (member? a (cdr lat))))))

If you want to take this further and find the intersection of two lists, we can do something like this!

(define intersect
    (lambda (set1 set2)
            (letrec
              ((I (lambda (set)
                      (cond
                           ((null? set) (quote ()))
                           ((member? (car set) set2)
                            (cons (car set)
                                  (I (cdr set))))
                           (else (I (cdr set)))))))
            (I set1))))

You can use this code as such. Tested from guile compiler

(begin
      (display (intersect `(1 2 3) `(1 3 4 5 2)))
      (newline))

>> (1 2)

EDIT

I recommend you read The Little Schemer and the The Seasoned Schemer to get more familiar with these kind of concepts

I'm trying to have the following program work, but for some reason it keeps telling me that my input doesnt contain the correct amount of arguments, why? here is the program

(define (sum f lst)
   (cond
     ((null? lst)
       0)
     ((pair? (car lst))
      (+(f(sum (f car lst))) (f(sum (f cdr lst)))))
     (else
       (+ (f(car lst)) (f(sum (f cdr lst)))))))

and here is my input: (sum (lambda (x) (* x x)) '(1 2 3))

Thanks!

btw I take no credit for the code, Im just having fun with this one (http://groups.engin.umd.umich.edu/CIS/course.des/cis400/scheme/listsum.htm)

You're indeed passing the wrong number of arguments to the procedures sum and f, notice that the expressions (sum (f car lst)), (sum (f cdr lst)) are wrong, surely you meant (sum f (car lst)), (sum f (cdr lst)) - you don't want to apply f (a single-parameter procedure) to the two parameters that you're passing, and sum expects two arguments, but only one is passed. Try this instead:

(define (sum f lst)
  (cond ((null? lst)
         0)
        ((pair? (car lst))
         (+ (sum f (car lst)) (sum f (cdr lst))))
        (else
         (+ (f (car lst)) (sum f (cdr lst))))))

More important: you're calling the f procedure in the wrong places. Only one call is needed in the last line, for the case when (car lst) is just a number and not a list - in the other places, both (car lst) and (cdr lst) are lists that need to be traversed; simply pass f around as a parameter taking care of correctly advancing the recursion.

Let's try the corrected procedure with a more interesting input - as it is, the procedure is capable of finding the sum of a list of arbitrarily nested lists:

(sum (lambda (x) (* x x)) '(1 (2) (3 (4)) 5))
> 55

You should take a look at either The Little Schemer or How to Design Programs, both books will teach you how to structure the solution for this kind of recursive problems over lists of lists.

I'm trying to write a Scheme function that counts all the items in a list, but unlike the length function that is available would count inner lists also so countAll '(a (a b)) would return 3 and not 2.

the first check is for an empty list, the second is supposed to check if the head of the list is currently a list itself, it should then add the length of THAT list to the total and call the next recursive call, if it isn't, it should simply skip to the third part which will add one to the total and call the function recursively.

I'm getting syntactical errors and I'm unsure about my approach. Am I going about this the right way? Are there better/Easier ways to do this?

(define countAll 
  (lambda (list)

    (if (null? list)
        0

        ((if (list? (car list)
                    (+ length (car list)
                       (countAll (cdr list))))))

        (+ 1
           (countAll (cdr list))))))     
  (+ 1
   (countAll(cdr list)
  )))))

The solution to this kind of problem follows a well-known structure, a recipe if you wish, for traversing a list of lists. This looks like homework, so I'll help you with the general idea and you go ahead filling-in the blanks:

(define (countAll lst)
  (cond ((null? lst)               ; if the list is empty.
         <???>)                    ; then it doesn't have any elements
        ((not (list? (car lst)))   ; if the first element in the list is not a list
         (<???> (countAll <???>))) ; add one and advance the recursion over the `cdr`
        (else                      ; otherwise
         (+ (countAll <???>)       ; add the result of the recursion over the `car`
            (countAll <???>)))))   ; with the result of the recursion over the `cdr`

If you need more help understanding how to structure a solution to this kind of problems dealing with lists of lists, I'd recommend you take a look at either The Little Schemer or How to Design Programs, both books will teach you how to grok recursive processes in general.

; A list-of-images is either   
; empty      
;    or       (cons n lon),
; where n is an image and lon is a list-of-images.

how would you develop a function height-total that consumes a list of images and returns the sum of all the images heights? i am confused. Could you use the function image-height for this?

The solution follows naturally as a recursive procedure; because this looks like homework I'll let you figure out the details, and of course you'll have to use the image-height procedure:

(define (height-total list-of-images)
  (if <???>                      ; if the list is empty
      <???>                      ; then what's the height sum of an empty list?
      (+ (image-height <???>)    ; else add the height of the first image and
         (height-total <???>)))) ; advance recursion to the rest of the list

Notice that the solution to this and many other problems over lists adheres to the same basic recursive structure, I'd recommend you take a good look at either How to Design Programs or The Little Schemer to better understand how to solve this kind of problems.

This is using MIT Scheme, coming from the infamous SICP. I just can't wrap my head around what is happening. Here's a procedure to compute N!.

(define (factorial n)
     (if (= n 0)
          1
          (* n (factorial (- n 1)))))

Here's a procedure to compute Fibonacci

(define (fib n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
   (else (+ (fib (- n 1))
            (fib (- n 2))))))

In the SICP book there's a clear, step-by-step explanation of how linear recursion works (for the factorial example), and there's also a good explanation complete with a nice tree diagram detailing tree recursion (for the fibonacci example).

If you need an easier-to-understand explanation of how recursion works in general in a Scheme program, I'd recommend you take a look at either The Little Schemer or How to Design Programs, both books will teach you how to grok recursive processes in general.

(defun prefix (a y) (cond ((null y) nil)
    (t (cons (cons a (car y)) (prefix a (cdr y))))))
(setq result prefix(a (cons 1 2)))
(print result)

This function cdr's through the list y, printing (a (car y)) recursively. If P is the first parameter, and y is the list (1 2 3), it should return ((P1) (P2) (P3)). However, I can't get the function to work when I try to give it parameters and execute it. What is incorrect here?

Please take a look at the introductory lisp texts available before you do anything else.

[dons code-review hat]

(defun prefix (a y) (cond ((null y) nil)
    (t (cons (cons a (car y)) (prefix a (cdr y))))))

(setq result prefix(a (cons 1 2)))

(print result)

Firstly, these definitions don't do what your prose description says they should; you don't have any printing in as part of your recursive function. You print result, but that's after the prefixed list has been put together in its entirety. Your prefix function also doesn't return new symbols, but rather pairs.


There's no need to set intermediate values in order to print them; Lisp functions return implicitly and can be composed without setq

(defun prefix (a y) 
  (cond ((null y) nil)
         (t (cons (cons a (car y)) 
              (prefix a (cdr y))))))

(print prefix(a (cons 1 2)))

Lisp is entirely prefix notated, and function names appear inside of the calling parentheses.

...

(print (prefix a (cons 1 2)))

a in your prefix call is an unbound variable. I think you either meant to use "the symbol a", which is 'a, or "the keyword a", which is :a. If you merely pass a, Lisp will try to evaluate that name as a variable, and fail if you don't have a value assigned to it.

...

(print (prefix 'a (cons 1 2)))

Your second argument to prefix isn't a proper list; it's a pair. In order to see the difference, you need to take a look at the underlying pointer structure of both constructs.

(cons 1 2) => [ 1 | 2 ]
(list 1 2) => [ 1 |   ]
                    \
                  [ 2 |  ]
                        \
                        NIL

If you try to use a pair where a function is expecting a proper list, you'll get the error #<TYPE-ERROR expected-type: LIST datum: 2> because the tail of a pair is not a list, whereas the tail of a list is.


(defun prefix (a y) 
  (cond ((null y) nil)
         (t (cons (cons a (car y)) 
              (prefix a (cdr y))))))

(print (prefix 'a (list 1 2)))

At this point, you've got a runnable program. Evaluating (print (prefix 'a (list 1 2))) at the REPL after defining that function should give you

CL-USER> (print (prefix 'a (list 1 2)))

((A . 1) (A . 2)) 
((A . 1) (A . 2))

Note that we've got duplicate output; this is because the Lisp REPL automatically prints the return value of any form you evaluate, which means that you can actually drop print entirely.

CL-USER> (prefix 'a (list 1 2))
((A . 1) (A . 2))

In order to do what you said you wanted (create a new list of symbols with the first argument as the prefix), you'll actually need to use some string operations and intern to create symbols.

(defun prefix (a y) 
  (cond ((null y) nil)
         (t (cons (intern (format nil "~a~a" a (car y)))
              (prefix a (cdr y))))))

(prefix 'a (list 1 2)) should now return (A1 A2). Note that Common Lisp is case-insensitive, automatically converting lower-case symbols to upper-case.


Recursion is a good learning tool, and tail recursion is the principal iteration construct in Scheme, but it's usually a good idea to do things iteratively if you can. Note that CL doesn't guarantee tail-call optimizations, so this typically means using loop or mapcar (or dolist in some situations).

(defun iterative-prefix (a a-list)
  (loop for elem in a-list
        collect (intern (format nil "~a~a" a elem))))

(defun map-prefix (a a-list)
  (mapcar 
   (lambda (elem) (intern (format nil "~a~a" a elem)))
   a-list))

These will both give you the same output as the recursive version, but don't have the same risk of running out of stack space if you give them a sufficiently long list.

CL-USER> (prefix 'a (make-list 100000 :initial-element 1))
Control stack guard page temporarily disabled: proceed with caution
Control stack guard page temporarily disabled: proceed with caution
; Evaluation aborted on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {1004D674F3}>.

CL-USER> (iterative-prefix 'a (make-list 100000 :initial-element 1))
(A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 ...)

CL-USER>