Hot answers tagged

12 votes
Accepted

Is this a generic way to convert any recursive procedure to tail-recursion?

Your description of your algorithm is really too vague to evaluate it at this point. But, here are some things to consider. CPS In fact, there is a way to transform any code into a form that uses ...
user avatar
6 votes

Can we prove mathematical induction statements in Lisp?

Let me try to clarify a point that seems to be confusing you: you seem to be conflating 2 related, but different concepts. The first is the concept of a proof system, which allows you to specify and ...
user avatar
  • 7,744
6 votes
Accepted

How do you represent LISP as mathematical / logical model?

"Old" programming languages like Fortran, Cobol and LISP arose before serious mathematical theory of programming languages was developed. They inspired the development of such theory, but are full of ...
user avatar
  • 28.3k
6 votes
Accepted

Description of lists with functions in LISP

In PL theory, this is known as (a variant of) the Church-encoding of pairs. The idea is the following: assume for the moment you only have a language with primitive booleans (true, false, if-then-...
user avatar
  • 14.2k
5 votes
Accepted

Is it possible to do Dependent Types in Typed Racket?

Dependent Types in Racket are being worked on by Andrew Kent at Indiana University. There is a set of slides. There is a talk. Of interest, this potentially also impacts Typed Clojure, which is ...
user avatar
  • 1,189
2 votes
Accepted

Claimed problems with Lisp dynamic scoping

With fact, the primary problem is with f. If n is 0, ...
user avatar
2 votes
Accepted

SICP: Pascal's triangle problem

Your code has an "off by one" mistake: in the $n$'th row, it prints $\binom{n}{1},\ldots,\binom{n}{n+1}$ (the condition i <= n should be corrected to <...
user avatar
2 votes
Accepted

Lambda Calculus Conversion

The thing to notice here is that your function sum is defined on lists, which are inductively defined. Theoretically, the inductive definition of a list defines for ...
user avatar
  • 181
1 vote

Continuation passing transform

I would recommend trying a few examples for yourself to see how the transformation works. Think of the CPS transformation this way: Results are passed to continuations. Continuations are passed to ...
user avatar
  • 19.1k
1 vote

Is JavaScript a homoiconic language?

Given your definition, the answer is "no". JavaScript syntax is not a subset of JavaScript's literal syntax. The fact that a value a literal represents can be produced by evaluating the literal is ...
user avatar
1 vote

how to deduce a function subtype rule from a given function type definition

The intersection rule should be derivable, but it isn't purely a subtyping rule. Basically we reason as follows (I've translated into a notation that's a bit more familiar to me): I'm presuming that ...
user avatar
  • 2,135
1 vote
Accepted

What is the difference between a block and a procedure?

Such terminology is language specific. In programming languages I've seen, they are not the same. A procedure (or function) definition is a block of code with a header, that specifies 0 or more ...
user avatar
  • 4,686
1 vote

Why pointer dereference was once called "decrement"?

OK, I found a lead. Just needed to know what to search for: https://en.wikipedia.org/wiki/CAR_and_CDR The 704 and its successors has a 36-bit word length and a 15-bit address space. These ...
user avatar
  • 1,358
1 vote
Accepted

How did MacLisp's garbage collector "run in the register set"?

The 16 high-speed registers of the PDP-10 ISA were addressible as locations 0-15 of physical memory, so that the code literally could run in the registers if it was short enough and you could devote a ...
user avatar
1 vote

Suggestions for Short Examples Contrasting Functional Programming Languages

Project Euler has nice problems for showcasing the core of a programming language. An important part of a programming language are user defined (container) data structures. Bread and butter containers ...
1 vote
Accepted

How does time/space complexity work with lisp

You get the fib(n) running time if you only expand one invocation of fib at a time. You haven't been told the exact execution model for several reasons: It is messy. It's not important. It could ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible