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 ...
- 632
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 ...
- 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 ...
- 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-...
- 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 ...
- 1,189
2
votes
Accepted
Claimed problems with Lisp dynamic scoping
With fact, the primary problem is with f. If n is 0, ...
- 632
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 <...
- 270k
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 ...
- 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 ...
- 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 ...
- 11.8k
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 ...
- 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 ...
- 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 ...
- 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 ...
- 126
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 ...
- 270k
Only top scored, non community-wiki answers of a minimum length are eligible